차원축소(2) - MDS | Ho’s blog

차원축소 기법중 2번째 MDS 알고리즘을 소개하겠습니다.

정보의 압축

본격적 알고리즘 소개에 앞서 이러한 방식의 차원축소가 왜 필요하지 생각해 보겠습니다.

앞서 PCA를 통한 차원축소의 장점으로 메모리 절약, 속도향상, 시각화 등등 여러가지 장점을 나열했습니다. 이중 시각화 라는 부분은 데이터를 가공하여 데이터를 직관적으로 파악 할수 있다는 것입니다.

조금 더 구체적으로 설명 하겠습니다.

고객 정보는 대개 다음과 같은 요소들로 표현됩니다.

신상정보(나이, 주소 등), 취미와 관심사(고객이 직접 입력한), 각종 활동 기록들(구매한 상품들의 목록 등). 하지만 이런 요소들은 그 고객의 본질적인 특성, 즉, 구매 성향이라든지, 그 고객이 진짜로 관심있어하는 상품의 종류, 이런 것들을 직접적으로 보여주지 못합니다.

(뜬금없이 이런 주제를 던지는것은 MDS 알고리즘이 마케팅영역에서 활용도가 높기 때문입니다..)

고차원 공간의 거리를 저차원으로

고차원상에 뒤틀린 상태로 놓여 있는 매니폴드로 부터 원래의 저차원 유클리디안 공간을 구한는 것이 차원축소의 핵심이 됩니다.

다시말해, d개의 필드로 이루어진 레코드를, r개의 필드로 나타내는것입니다.(d>r)

$d차원데이터\quad x_{ i },{ x }_{ j }가 존재\quad 한다고\quad 가정합시다.$ $실제거리를\quad d(x_{ i },x_{ j })라고\quad 정의합니다.$ 그리고 앞으로 우리가 구할 r차원의 공간 $z_{i},z_{j}$ 라고 하겠습니다.

$\left\| { z }_{ i }-{ z }_{ j } \right\| =\quad d(x_{ i },x_{ j }) \quad\quad ...(1)$

이식의 의미가 앞서 설명한 정의를 반영 하는 식이 되겠습니다. 이 처럼 개체의 거리값이 동일하게 유지되는 유클리디안 공간으로 맵핑하는 것을 목적으로 하는것을 Multi-dimensional scaling (MDS) 라고 합니다.

이제 이 Z 를 어떻게 구할 것인가에 대해 고민해보겠습니다.

STEP1 먼저 Z벡터들의 합을 0으로 만들어주어야합니다.

STEP2 (1)식의 변형(양변을 제곱)을 통해 ${ d }_{ ij }^{ 2 }= {z }_{ i}^{T }{z }_{i }+{z }_{ j}^{T }{z }_{j }-{2z }_{ i}^{T }{z }_{j }$ 식을 유도해 냅니다.

자세한 계산 과정은 참조문건으로 달아두겠습니다. MDS 전체 수식 참조

여기서 중요한것은 이 계산과정이 어떻게 나왔는지 흐름을 파악하셔야 합니다.

Imgur

${ { z }_{ i }^{ T }{ z }_{ j } }\quad =\quad \frac { 1 }{ 2 } (d^{ 2 }_{ ij }-\frac { 1 }{ n } \sum _{ i=1 }^{ n }{ d^{ 2 }_{ ij } } -\frac { 1 }{ n } \sum _{ j=1 }^{ n }{ d^{ 2 }_{ ij } } +\frac { 1 }{ n^{ 2 } } \sum _{ i=1 }^{ n }{ \sum _{ j=1 }^{ n }{ d^{ 2 }_{ ij } } } )$

최종적으로 새롭게 만들어지는 Z(n x r)메트릭스의 내적값은 DistanceMatrix(n X n ) 메트릭스의 적절한 선형결합으로 표현이 가능해 진다는 것입니다.

두 벡터의 내적은 흔히 두 개체의 유사도(similarity)를 표현하는 방법으로 쓰입니다. 예를들면 Cosine Similarity , Kernel function 있습니다. 커널 함수는 주어진 데이터의 공간보다 무한차원공간에서의 내적으로 정의 됩니다. (커널함수를 포스팅할때 조금 더 자세히 다루도록 하겠습니다.)

정리하자면, d차원 데이터를 먼저 새롭게 r차원으로 줄이기위해, r차원 벡터인(z)를 고안해 냅니다. 이 z벡터들의 내적값은 d차원 데이터들의 Distance(유사도) matrix 값들로 표현이 가능해집니다. distance 를 통한 매핑이라고 이해 할 수 있겠습니다.

STEP3

$ZZ^T=HDH$ $H\quad =\quad I- \frac { 1 }{ n } { 11 }^{ T }$

(H메트릭스를 양옆에 곱해주면 centering 됩니다.) 모양의 식을 얻을수 있습니다.

여기서 D 메트릭스는 일반적인 유클리디안 거리를 이용한다면 $D\quad =\quad -\frac { 1 }{ 2 } { d }_{ ij }^{ 2 }$ 인 MDS 알고리즘이 되는것이고, D의 정의에 따라 커널기법, Isomap(geodesic), LLE 등 다양한 알고리즘으로 변환 됩니다. (앞으로 다룰 매니폴드는 이 D의 정의만 다를 뿐 기본 Mapping 방법은 같습니다.)

STEP4

실제 Z의 계산 과정은 무척쉽습니다.

HDH 메트릭스는 symmetric, positve semi-definite(psd) 입니다. (n-r)개의 0 eigenvalue를 가지고 있기 때문에, 이를 제외한 r개의 eigenvector 로 차원축소가 가능해 집니다. (by Eigen-decomposition)

$rank(ZZ^{ T })\quad =\quad rank(Z)\quad =\quad r$ $HDH\quad =\quad V\Lambda V^{ T }$ $ZZ^{ T }\quad = \quad V_{ r }\Lambda _{ r }V^{ T }_{ r }$ $Z=V_{ r }\Lambda _{ r }^{ \frac { 1 }{ 2 } }$

r차원이상으로 차원을 줄이게 된다면 정보의 손실이 더 일어 나게 됩니다.

MDS code

step1. D메트릭스 구하기

dists = np.zeros((len(X),len(X)))

for i in range(len(X)):
    print(i)
    for j in range(len(X)):
        dists[i,j] = (np.sum((X[i,:]-X[j,:])**2))

step2. HDH 계산을 통한 Centering

n = len(dists)
H = np.eye(n)-(1/n)*(np.ones((n,n)))
B = -H.dot(dists).dot(H)/2

step3. Eigen-decomposition 고유벡터 구하기

eigen_value,eigen_vector = np.linalg.eig(B)
inverseEigenVectors = np.linalg.inv(eigen_vector) 
diagonal= inverseEigenVectors.dot(B).dot(eigen_vector)

step4. 원하는 차원으로 축소

dimension = 2
B_1 = eigen_vector[:,0:dimension].dot(diagonal[0:dimension,0:dimension]).dot(eigen_vector[:,0:dimension].T)
diagonal[diagonal<1] = 0
coordinate_X = eigen_vector[:,0:dimension].dot(np.sqrt(diagonal[0:dimension,0:dimension]))

step5. 시각화

with plt.style.context("seaborn-darkgrid"):
    for l in label:
        plt.scatter(coordinate_X[y==l,0], coordinate_X[y==l,1],label=l)
    plt.xlabel("dimension 1")
    plt.ylabel("dimension 2")
    plt.legend()
    plt.show()

Imgur

위 사진을 보면 앞선 pca와 유사하게 데이터가 모이는것을 볼 수 있습니다. 다만 워낙 고차원의 데이터이기 때문에 겹치는 부분이 많이 존재합니다.

mds의 단점은 Distance 메트릭스를 만들기위해 시간이 많이 걸리는 것입니다. 앞서 다루었던 pca를 통해서 차원축소후 mds 를 활용하면 시간을 단축할수있고, 더 좋은 시각적 결과를 나타낼 때도 있습니다.

Imgur

좀더 데이터의 군집이 잘 된거 같은 모습을 보여주고있고, D메트릭스 계산 속도도 많이 줄어 들었습니다.

PCA와 유사한 ICA(Independent Component Analysis)와 앞서 언급한 거리의 정의에 따른 다른 매니폴드 알고리즘(Isomap, LLE, SNE ..)을 알아보겠습니다.

MDS 전체 수식 참조

정보의 압축

고차원 공간의 거리를 저차원으로

MDS code

next