PCA vs MDS
둘 다 차원축소 개념
PCA(Principle Component Analysis)
데이터: d차원 공간상에 있는 n개의 인스턴스, 따라서 nxd 행렬로부터 시작 x∈R^d
목적: 원래 데이터의 분산을 보존하는 기저의 부분집합 찾기
출력값: d차원 공간의 d개의 고유벡터/고유값
MDS(MultiDimensional Scaling)
데이터: n개의 인스턴스 간의 근접도 행렬, 따라서 nxn 행렬로부터 시작 D_nxn
목적: 인스턴스의 거리 정보를 보존하는 좌표계 찾기
출력값: d차원에 있는 각 n개의 인스턴스의 좌표값
ILMA 이용한 MDS 알고리즘
Input: 거리행렬 D, 반복횟수 M
Output: MDS 코드행렬 X (좌표)
*밑의 그림은 1차원 상에서 수행한 듯, 좌표=거리
-
Initial Stage
Distance Matrix에서 Randomly하게 Non-Diagonal entry 하나 초기값 가져오기(대각 성분은 자기자신과의 거리, 다 0이라서)
각 노드거리 행렬 초기세팅
-> 1개의 노드 i에 대해 N-1개의 노드 j
-> 2개의 노드 i, i_2에 대해 N-2개의 노드 j_2
즉, A 집합 원소가 N개 되기 전까지 A 집합에 속하지 않는 j 가져와서
standard LM 알고리즘 적용: nCn-1 = n(n-1)/2 원소갯수만큼의 크기 행렬 계산 수행, 유클리디안 거리
(LM 알고리즘의 안의 정해진 iteration으로 x_j 최적화, x_j에 대해 미분한 값이 0이 되도록)
j를 A 집합에 추가, 최적화된 x_j를 X 집합에 set -
Adjustment Stage
M번 반복
1~N까지의 랜덤순열 생성 -> ex) N=4일 때, (4,2,1,3)
for 편향 줄이기, 노드의 업데이트 순서를 무작위함으로써
해당하는 x 가져와서
standard LM 알고리즘 적용
x 업데이트
일정 오차 안에 들면 Break
Iterated Levenberg-Marquardt Algorithm(ILMA)
간단히 설명하면 파라미터 p가 해애서 멀어진 경우, Gradient-Descent 방식이 사용되고, 파라미터 P가 해에서 가까워진 경우, Gauss-Newton 방식이 사용됨.
Gradient-Descent: 1차 미분으로 이동 방향을 잘 설정하지만, 이동 크기는 잘 설정하지 못함.
Gauss-Newton: 2차 미분으로 해 주변에서 크기를 잘 설정하지만, 극소점이 아닌 극대점으로도 수렴할 수 있는 문제 갖고 있음.
