차원축소 - PCA,MDS

PCA 알고리즘을 소개하겠습니다.

차원축소는 왜 하나요?

1.훈련속도의 상승 ▷ 그러나 항상 더 좋은 solution 을 제공하진 않는다.
2.데이터 시각화를 통한 패턴감지 및 통찰

차원축소 방법

1. Projection
2. Manifold Larning

Mnist Data

머신러닝을 공부하다보면 앞으로 항상 보개될 대표적 데이터셋인
Mnist 데이터를 소개하겠습니다.

손글씨를 0~255 숫자로 명암을 나타 내고 있습니다.
각 이미지는 28*28 픽셀이므로 784차원의 데이터입니다.
이 고차원 속에 유의미한 숫자 데이터는 아주 작은 공간에 있습니다.
(흰 여백이 많다는 의미입니다.)
Mnist 데이터를 두고 고차원의 임베딩 공간을 통해 스위핑 및 커브하는
낮은 차원의 매니폴드 라고 정의하기도 합니다.
또한, 주변공간으로 부터 튀어나온 촉수같은 돌출부로 생각 할 수도 있습니다.

이 데이터를 이제 2차원의 입장에서 보도록 하겠습니다.

대부분의 데이터가 구별이 안되는데 빨강점인 3과
초록점인 2는 어느정도 구별이 되는것 같습니다.
이러한 2차원의 각도를 정할때 어떤 시점에서
데이터를 바라 보는것이 최적의 관점인지
이를 알아내기위해 PCA라는 알고리즘을 이용 할 수 있습니다.

PCA 알고리즘

pca를 할때 투영할 초평면을 선택해야 합니다. 이때 선택 할 초평면을 어떻게 결정하는가?
pca알고리즘은 분산이 최대한 보존되는 축을 선택하는것이 정보가 가장 적게 손실된다 합니다.
이는 다른말로, 원본 데이터셋과 투영된것 사이의 거리를 최소화 하는 축을 뜻합니다.
(Reconstruction error 최소화 -> 이후 LLE 알고리즘 부분에서 다루도록 하겠습니다.)

투영후 분산의 최대화

처음 분산의 최대화 라는것이 이해가 되지않아 그림으로 조금 더 알아보도록 하겠습니다.
직관적으로 오른쪽 3개의 투영데이터 중 데이터의 보존이 가장 잘 된 것은 1번 그림임을 알 수 있습니다.
3번 데이터는 원 데이터의 속성이 거의 없어졌음을 알수 있죠.
이는 차원 축소후 데이터의 분산값이 커야 정보 손실이 없음을 알 수 있습니다.

step1. 평균을 0으로 맞추기

$$X = X-\hat { X }$$

step2. 분산값 계산

$v\quad =\quad ({ w }^{ T }X)({ w }^{ T }X)^{ T }=w^{ T }XX^{ T }w=nw^{ T }Sw$ $max\quad w^{ T }Sw$ $s.t. w^Tw = 1$

이 문제를 해결해야하는데, 라그랑주 승수를 사용하여 식을 풀어 보도록하겠습니다. $L\quad =\quad { w }^{ T }Sw-\lambda ({ w }^{ T }w-1)\\ \frac { \partial L }{ \partial w } \quad =\quad (S\quad +{ S }^{ T })w-2\lambda w\\ \quad \qquad \quad =2Sw-2\lambda w\\ \qquad \quad \quad =0\\ \therefore \quad Sw=\lambda w$

즉, 위의 식을 만족하는 w벡터가 바로 분산을 최대화 한다는 것이죠.
$\lambda값은\quad S공분산의\quad 고유값(eigenvalue)이며\quad eigenvector로\quad 투영했을때\quad 분산이\quad 됩니다.$
이때 고유벡터의 열벡터를 주성분이라 합니다. 따라서, 고유벡터에 투영하는것이 분산이 최대가 되는것입니다.
고유값을 구하기 위해서는 eigenvalue-decomposition, SVD 두가지 방법이 있습니다. (SVD방법이 조금 더 효율적이라고 하는데.. 자세한건 SVD 방법을 포스팅때 다루겠습니다.)

X_center = X-np.mean(X)
S = np.dot(X_center.T,X_center)/(X.shape[0]-1)
eig_val, eig_vecs = np.linalg.eig(S)

idx = np.random.choice(70000,500,replace=False)

reduce_dimension = 154
W = eig_vecs[:,:reduce_dimension]
new_mnist = X.dot(W)
new_mnist_sample = new_mnist[idx,:]

with plt.style.context("seaborn-darkgrid"):
    label = np.unique(y)
    for l in label:
        plt.scatter(new_mnist_sample[y[idx]==l,1], new_mnist_sample[y[idx]==l,2],label=l)
    plt.xlabel("pc1")
    plt.ylabel("pc2")
    plt.legend()
    plt.show()

이제 PCA로 구한 주성분으로 Mnist 데이터를 보도록합시다.
pca에서 나온 주성분축이 어떤 관점인지 시각적으로 보도록 하겠습니다.

처음 임의의 2차원을 선택한것 보다 확실히 데이터의 정보가 손실 되지 않은 것을 알수있습니다.
직관적으로 0과 1은 구별이 잘 되는 것을 알 수 있습니다.

그렇다면 지금 나타내는 PC1 , PC2가 어떤속성 값인지 파악해보도록 하겠습니다.
즉, PC1으로 투영했을때 PC1이 어떤 방향으로 데이터를 투영하는지 시각화를 통해 알아 보는것 입니다.
고유벡터 또한 784차원 이므로 28*28 픽셀로 만들어 시각화 합니다.

붉은 부분이 뜻하는것은 양의 값을 뜻하고 반대로 하늘색은 음의 값을 뜻합니다.
대부분 0값은 PC1 값에 투영시 음의 값을 가지게 되고, 반대로 1의값은 양의 값을 가지게 됩니다.
그렇기에 PC1을 통해 0/1이 구별이 잘 되는것으로 생각할수 있습니다.

이 예시를 통해 주성분벡터가 어떤 의미를 가지는지 좀더 직관적으로 파악 하셨길 바랍니다.

차원축소의 성능평가

차원축소가 얼마나 잘 되었나 평가하는 방법은 2가지정도 존재합니다.

1. 예측분류기에 원데이터와 축소데이터를 넣어 성능비교를 합니다. -> 이과정에서 성능의 차이가 크지 않아야 합니다.
2. 축소후 원래 차원으로 복원시킨후 reconstruction error 를 측정하는것입니다. -> 하지만 안타깝게도 모든 차원축소 알고리즘이 복원이 가능하거나 그리 쉽지는 않습니다.(pca는 쉽다)

복원 후 정보의 손실이 어느 정도인지 확인해 보도록 하겠습니다. ${ w }^{ T }X\quad -->\quad w{ w }^{ T }X$

recon_mnist = new_mnist.dot(W.T)
re_image1 = recon_mnist[500,:].real.reshape(28,28) 
ori_image1 = X[500,:].real.reshape(28,28) 
plt.imshow(ori_image1,cmap='hot', interpolation='nearest')
plt.imshow(re_image1,cmap='hot', interpolation='nearest')

선명도의 차이가 있을뿐 0이라는 모양의 정보는 거의 손실되지 않았습니다.
(이는 분산이 95%되는 지점까지 차원축소를 하였기 때문입니다. 즉 정보의 손실이 5%입니다)

PCA 단점 및 한계

pca의 단점으로는 전체 데이터를 사용하여 eigen decomposition을 진행하기 때문에
새로운 데이터가 들어오면 새롭게 진행해야합니다.
이를 해결하기위해 IPCA(Incremental PCA) 또는 Online PCA 라고 하는 알고리즘을 사용가능합니다.
(sklearn 패키지 활용)

non linear 데이터(스위스롤) 같은 데이터에 pca를 적용시 좋은 효과를 볼 수 없습니다.
kernel PCA 같은 기법은 이를 해결해 줄수 있습니다.

randomize PCA 는 차원의 수를 많이 줄이거나,
쇼핑Item 데이터 처럼 n*d에서 d가 매우 큰 데이터셋에서
PCA보다 좋은 성능을 나타낸다고 합니다.

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 전체 수식 참조

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

$${ { 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()

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

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

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

NEXT..

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