multi dimensional scaling as 차원감소

https://en.wikipedia.org/wiki/Multidimensional_scaling

 

Multidimensional scaling - Wikipedia

들어가며

Machine Learning problem을 풀다보면, 종종 high dimensional 데이터를 다뤄야할 일이 생긴다. 그런데 dimension 높은 데이터를 다루다보면 여러 문제가 발생하는데, 높은 dimension으로 인해 생기는 대표적인 문제가 예전 글에서 다뤘던 Curse of dimensionality이다. 또한 많은 algorithm들에서 dimension이 complexity에 영향을 주는 경우가 많으므로 높은 dimension은 알고리즘의 성능에 악영향을 미치는 경우가 많다. 그렇기 때문에 많은 경우 데이터의 dimension이 높다면 다양한 방식의 dimenionality reduction 기술을 적용해 데이터의 차원을 낮추는 작업을 한다. 일반적으로 많이 사용하는 Dimensionality Reduction으로는 LDA와 PCA가 있으며, ICA, CCA 등의 방법도 종종 사용되며, 그 이외에도 RBM, Auto-encoder 등의 Neural network와 관련된 모델들도 존재한다. 이 글에서는 가장 많이 사용되는 방법들인 LDA와 PCA에 대해서만 다룰 것이다.

Recall: Curse of Dimensonality

Curse of Dimensionality는 데이터의 차원이 높아질수록 발생하는 여러 문제들을 통틀어 일컫는 말이다. 이런 문제가 발생하는 이유는 차원이 높아질수록 우리가 일반적으로 사용하는 Euclidean distance가 예상치 못한 방식으로 동작하기 때문이다. 예를 들어 d-차원 공간에서 임의의 점으로부터 거리가 1인 점들을 모아놓은 공간을 생각해봤을 때, d가 점점 커지면 커질수록 그 구의 대부분의 부피가 거의 surface에 가까운 엄청나게 얇은 shell에 존재한다는 것을 이미 예전 글에서 증명한바 있다. 다시 말해서 아주 높은 차원의 데이터는 우리가 원하지 않는 방향으로 움직일 가능성이 크다.

Feature Extraction

많은 상황에서 차원의 크기는 feature의 개수를 의미한다. 예를 들어 키, 몸무게, 나이, 성별이라는 네 가지 정보를 가지고 클러스터링을 한다고 생각해보자. 이 경우 데이터의 차원은 4이다. 그런데 아마도 이 네 가지 정보 이외에도 소득, 학력, 자산크기 등의 정보 등을 추가로 사용해 클러스터링을 한다면 더 좋은 클러스터링이 가능할지도 모른다. 문제는, 모든 feature가 전부 의미있는 feature는 아닐 수 있다는 것이다. 몸무게 정보를 사용하여 클러스터링한 것과 사용하지 않고 클러스터링한 것 중에서 몸무게 정보를 사용하지 않고 클러스터링 한 것이 더 좋을 수도 있다는 것이다. 이렇게 주어진 정보들 중에서 정말 의미 있는 feature를 뽑아내는 과정을 feature extration이라고 한다. 가장 간단한 feature extraction은 모든 feature를 사용해보기도 하고 사용해보지 않기도 하면서 2d2d 개의 조합을 모두 확인해보는 것이다. 그러나 이 방법은 차원의 크기에 exponential할 뿐 아니라, 만약 기존 feature가 highly correlate되어있고, 여러 개의 feature를 묶어서 한 feature로 만들어야 성능이 좋아지는 경우 등에 대해 좋은 성능을 내기 어렵다. 따라서 이런 상황에서도 dimensionality reduction 방법을 사용해 feature를 뽑아낼 수 있다. 만약 우리가 100개의 feature를 가지고 있을 때, ‘가장 좋은’ 30개의 feature만 뽑기 위해서 30차원으로 dimensionality reduction을 하는 것이다.

Dimensionality Reduction

데이터의 차원을 낮춘다는 것의 의미는, 현재 데이터가 존재하는 차원에서 그보다 낮은 다른 차원으로 데이터들을 mapping시키는 map을 찾는다는 것과 같다고 할 수 있다. 이때 어떤 임의의 차원에서 그보다 낮은 임의의 낮은 차원으로 가는 mapping은 셀 수 없이 많다. 그렇다면 우리는 어떤 mapping을 선택해야할까? 예를 들어 가장 간단한 방법으로, d 차원 데이터를 d’ 차원으로 보내고 싶을 때, 앞에서 설명했던 간단한 방법처럼 임의의 d’ 개의 축을 골라서 그 축만 사용하는 방법도 있을 수 있고, d에서 d’으로 가는 linear map을 임의로 하나 고르는 것도 가능하다. 물론 non linear map도 가능하지만, 이 글에서 다룰 LDA와 PCA 두 가지 방법은 모두 linear mapping을 찾는 알고리즘이다. LDA는 supervised learning이며, PCA는 unsupervised learning에 해당하게 된다. 모든 문제에서 데이터는 matrix XX로 표기되며, 데이터의 차원은 d이고, 개수는 n개이다. 따라서 XX는 d by n matrix가 된다.

LDA

Linear Discriminant Analysis (LDA)는 Dimensionality reduction만을 위한 방법은 아니다. LDA로 약어가 표시되는 것들이 꽤 많아서 (예: Latent Dirichelt Allocation) 이 모델을 처음 제안한 사람의 이름을 따서 Fisher’s LDA 라고 부르기도 한다. LDA는 여러 클래스가 존재할 때 그 클래스들을 최대한 잘 분리시키는 projection을 찾는다. 철학은 굉장히 단순한데, projection 시킨 데이터들에서 같은 클래스에 속하는 데이터들의 variance는 최대한 줄이고 (σwithinσwithin), 각 데이터들의 평균 값들의 variance는 최대한 키워서 (σbetweenσbetween) 클래스들끼리 최대한 멀리 떨어지게 만드는 것이다. 이를 수식으로 표현하면 다음과 같은 수식을 얻을 수 있다.

S=σ2betweenσ2withinS=σbetween2σwithin2

일단 가장 간단한 상황인 클래스가 2개일 때의 상황만 고려해보도록하자. 참고로 LDA의 결과는 항상 클래스 개수 - 1 개까지의 벡터 밖에 찾을 수 없기 때문에, 이 상황에서 우리가 찾게 될 projection은 1차원 projection을 찾는 것이므로 간단하게 vector ww로 기술하도록 하겠다. 클래스가 2개 뿐이라면, 위의 식은 엄청 간단한 수식으로 바뀌게 된다. 먼저 σbetweenσbetween은 데이터가 단 두 개 뿐이기 때문에 간단하게 (w⋅μ1−w⋅μ2)2(w⋅μ1−w⋅μ2)2으로 표현이 된다. 이때, μ1,μ2μ1,μ2는 각각 1번째 클래스와 2번째 클래스에 속한 데이터들의 평균 값이다. 다음으로 σwithinσwithin 역시 어렵지 않게 계산할 수가 있다. Projection을 하게 되면 데이터의 variance는 w⊤Σww⊤Σw로 표현이 되기 때문에, 1번 클래스와 2번 클래스에 대해 이 값을 계산하고 더해주기만 하면 된다. 식을 정리해보면

w=argminwσ2betweenσ2within=argminw(w⋅μ1−w⋅μ2)2w⊤Σ1w+w⊤Σ2ww=arg⁡minwσbetween2σwithin2=arg⁡minw(w⋅μ1−w⋅μ2)2w⊤Σ1w+w⊤Σ2w

그리고 위 식을 w에 대해 미분하고 좀 정리해보면 w∝(Σ1+Σ2)−1(μ1−μ2)w∝(Σ1+Σ2)−1(μ1−μ2) 라는 식을 얻을 수 있다.

Multiclass LDA

그러면 클래스가 2개보다 많을 때, 벡터 ww가 아닌 subspace UU를 찾는 과정은 어떻게 되는지 살펴보도록하자. 다시 σwithinσwithin과 σbetweenσbetween을 살펴보자. 먼저 σbetweenσbetween은 위와 비슷한 형태로 표현할 수 없다. 그러나 우리가 각각의 클래스의 평균을 μiμi라고 정의한다면, 그냥 이 값들의 variance를 계산하기만 하면 된다. 이 variance는 ∑i(μi−μ)(μi−μ)⊤∑i(μi−μ)(μi−μ)⊤로 표현이 된다. 이때 μμ는 모든 평균들의 평균이다. 이 variance가 있으므로, projection하여 얻는 variance도 앞 뒤에 proejction matrix를 곱해 쉽게 계산할 수 있다. σwithinσwithin은 위와 비슷한 방식으로 σwithin=U⊤(∑iΣi)Uσwithin=U⊤(∑iΣi)U로 표현할 수 있다. 이때 ΣiΣi는 i번째 클래스의 variance이다. 이 식을 정리해보면 다음과 같은 식을 얻는다.

U=argminUσ2betweenσ2within=argminUU⊤(∑i(μi−μ)(μi−μ)⊤)UU⊤(∑iΣi)U=argmaxUU⊤AUU⊤BU=arg⁡minUσbetween2σwithin2=arg⁡minUU⊤(∑i(μi−μ)(μi−μ)⊤)UU⊤(∑iΣi)U=arg⁡maxUU⊤AUU⊤B

AA와 BB는 각각 괄호 안에 있는 값을 의미한다. 위 식에서 보게 되면, 분자에 해당하는 부분이 rank가 클래스 개수 - 1 이기 때문에, 우리가 이 식을 풀었을 때도 UU의 rank가 클래스 개수 - 1이 되므로 LDA가 구할 수 있는 subspace의 축 개수가 클래스 개수 - 1로 제한되는 것이다. 이 식을 풀기 위해서는 eigenvalue를 계산하는 것으로 간단하게 식을 풀 수 있다. 지금부터 왜 이 식이 eigenvalue를 푸는 것으로 해결이 가능한지를 살펴보자.

General Eigenvector problem

문제를 간단하게 하기 위해 전체 subspace가 아닌 vector ww만 고려해보도록 하자. 따라서 식은

minww⊤Aww⊤Bwminww⊤Aww⊤Bw

로 표현 가능하다. 이제 이 식을 w에 대해서 미분해보면 다음과 같은 식을 얻게 된다

(w⊤Bw)2[2Aw(w⊤Bw)−2Bw(w⊤Aw)]=0(w⊤Bw)2[2Aw(w⊤Bw)−2Bw(w⊤Aw)]=0

이를 잘 정리하면

Aw=w⊤Aww⊤BwBwAw=w⊤Aww⊤BwBw

로 표현이 되고, 우리가 원래 풀려고 했던 w⊤Aww⊤Bww⊤Aww⊤Bw를 λλ라고 정의하면 식이 Aw=λBwAw=λBw라는 엄청 간단한 식이 나오게 된다. 이런 형태를 만족하는 λλ를 찾는 문제를 general eigenvalue problem이라 부른다. 만약 BB가 Identity matrix라면 우리가 아는 일반 eigenvalue problem이 된다. 따라서 원래 문제가 λλ의 minimum을 찾는 것이었으니 이제 가장 작은 general eigenvalue를 찾기만 하면 우리가 풀고 싶었던 문제를 풀 수 있는 것이다.

PCA

Principal Component Analysis (PCA)는 Dimensionality reduction의 가장 대표적인 방법 중 하나이다. PCA는 projection된 데이터의 variance가 최대화되는 projection matrix를 찾는 문제이다. 그런데 Eckart–Young theorem에 의해서, 이 문제의 답이 데이터 XX에 대한 Singular value decomposition(SVD)으로 계산할 수 있다는 것이 알려져 있다. 그래서 PCA를 variance를 maximize하는 원래 정의대로 설명이 하는 경우도 많고, low rank matrix 문제로 설명하는 경우도 있다. 이 글에서는 low rank matrix estimation 문제로 설명하도록 하겠다. 이 문제의 objective는 아래 식과 같다.

minrank(Z)=k∥X−Z∥2Fminrank(Z)=k‖X−Z‖F2

이때 ∥A∥F‖A‖F는 Frobenius norm을 의미한다. 이 norm은 matrix의 모든 element들의 제곱을 더한 값이며, ∥A∥2F=tr(AA⊤)=tr(A⊤A)‖A‖F2=tr(AA⊤)=tr(A⊤A) 라는 특성이 알려져있다. 이제 위의 식에서 ZZ를 UV decomposition한 후 대입해보면 다음과 같은 식을 얻는다.

minU∈Rd×k,V∈Rn×k,U⊤U=I∥X−UV⊤∥2FminU∈Rd×k,V∈Rn×k,U⊤U=I‖X−UV⊤‖F2

이 식을 VV에 대해 미분하면 optimal한 V는 V=X⊤UV=X⊤U로 표현이 됨을 알 수 있으며, 이를 위의 식에 대입한 후, Frobenius norm의 성질을 잘 활용하면 아래와 같은 식이 나온다.

maxU∈Rd×k,U⊤U=Itr(U⊤XX⊤U)maxU∈Rd×k,U⊤U=Itr(U⊤XX⊤U)

가 되며, 이 식의 답은 SVD를 통해 계산할 수 있다는 것을 알 수 있다. 그러나 만약 XX의 mean이 0가 아니게 되면 UV decomposition을 하는 과정에서 문제가 생기게 되서 같은 방식으로 깔끔하게 구할 수가 없다. 이 과정은 다소 복잡하므로 생략하고 결과만 얘기하면, 그냥 X^=X−1nX1X^=X−1nX1을 SVD하면 된다. 뒤에 있는 term은 그냥 X의 평균값이다.

정리하면, 임의의 데이터 X에 대한 PCA는 다음과 같이 구할 수 있다.

1. 데이터 XX의 empirical mean을 계산한 후 모든 데이터에서 평균을 빼준다.
2. 새로 만들어진 데이터 X^X^의 가장 큰 singular value부터 k번째 큰 singular value까지에 대응하는 singular vector들을 구한다. (SVD를 통해)
3. 뽑아낸 k개의 singular vector로 U를 구성하고 return한다.

쉽지만 그만큼 강력하다. 하지만 PCA의 경우 Frobenius norm의 제곱값을 사용하므로 각 element들이 norm을 계산할 때 한 번 제곱되고, 다시 전체에 제곱을 취할 때 또 제곱이 취해지므로 조금이라도 원래 데이터와 다른 outlier가 존재하게 된다면 그 효과가 굉장히 극적으로 증폭되기 때문에 noise에 취약하다. 이를 방지하기 위해 objective의 norm을 1-norm으로 바꾸거나 하는 등의 robust PCA 연구도 활발하게 진행되고 있다.

정리

Dimensionality Reduction은 매우 유용하고 많이 쓰이는 툴이다. 특히 PCA는 굉장히 빈번하게 사용되고 알고리즘도 매우 간단하기 때문에 알아두면 쓰임새가 많다. 이 글에서는 LDA와 PCA만 다뤘지만, ICA, CCA, RBM 등 굉장히 많은 dimensionality reduction 기술들이 존재한다. 이 중 RBM은 추후에 다시 한 번 자세하게 설명하도록 하겠다.

---

 

• 521,744

 

• 266

 

• 409

Machine Learning2016.08.22 16:00

 

36. 자율학습 두번째 (Principal Component Analysis) : PCA Algorithm

 

 

앞에서 살펴본 data compression 또는 dimensionalilty reduction 을 이용해서 오늘날까지 널리 사용되고 인기있는 알고리즘이 바로 PCA(Principal Component Analysis) Algorithm 입니다.

2차원의 데이터를 1차원으로 줄이기 위해서 아래 그림과 같이 직선을 하나 그립니다. 그리고 이 직선에 모든 2차원 데이터들을 투영시켜서 한점으로 나타낼 수 있게 됩니다. 이때의 두 점과의 거리 즉, 2차원 데이터의 점과 직선에 투영되어 생성된 점 사이의 거리를 때로는 projection error 라고 불리우기도 합니다.

이 projection error가 가장 최소화 되는 직선을 찾고 이로 인해서 2차원 데이터를 1차원으로 낮추는대 사용이 됩니다.

 

 

만약에 왼쪽 대각선으로 생긴 분홍색의 직선이 있다고 가정해보겠습니다. 이 직선에 투영되어 생성된 점들과 본래의 2차원 데이터들과의 거리를 보면 상당히 긴 거리가 됨을 알 수 있습니다. 이것이 우리가 이전에 배웠던 linear regression과 비슷해 보이지만 다른 점이 되겠습니다. 사실 완전히 다른 알고리즘입니다.

 

 

2차원의 데이터들에서 이러한 직선을 찾는 방법은 아래 그림과 같이 2차원 데이터에 vector를 그리고 그 vector가 그리는 직선을 찾는 것입니다. 이때 - 방향의 vector가 되더라도 크게 상관이 없는것이 같은 직선상에 있게 되기 때문입니다. 그렇게 생성된 직선에 projection error가 가장 작은 직선을 찾으면 됩니다.

 

 

3차원이 되어도 마찬가지입니다. 2차원으로 낮추기 위해서 2개의 vector를 그리고 이 vector 가 표현하는 사각형의 면을 하나 생성을 합니다. 그리고 3차원의 데이터들이 이 면에 투영되어 생기는 점들과의 거리를 계산해서 가장 적은 projection error가 되는 면을 찾는 것입니다. 

이러한 원리로 n차원의 데이터를 k차원으로 낮추기 위해서 k개의 vector가 생성이 될 것이고 이것이 이루는 면에 투영시켜서 가장 적은 projection error가 되는 것을 찾으면 되겠습니다.

 

 

위에 잠시 이야기 했던것처럼 PCA는 linear regression과 전혀 다른 알고리즘입니다. 매우 비슷해 보이기는 하지만 가장 다른 점은 y가 예측된 결과값이 였으나 여기서는 그런 값이 없다는 것입니다. 결과를 예측하기 위해서 비슷한 값이 되는 직선을 찾는 linear regression과는 달리 투영하기 위한 가장 최소 거리를 갖는 직선 또는 면을 찾는 것이 PCA algorithm이 되겠습니다. 이때 투영이 되면서 직선과 수직상의 거리를 측정하게 되는 것이 가장 큰 차이점이 됩니다. (vertical distance)

 

 

Preprocessing (feature scaling / mean normalization)

PCA 알고리즘을 수행하기 이전에 prepocessing 을 먼저 하는것이 좋습니다. 우리가 supervised learning에서 배운것과 거의 동일한 방식으로 하면 됩니다. 여기에는 두가지 방법이 있는데 하나는 mean normalization 입니다. 이것은 거의 대부분의 경우에 항상 해주는 것이 좋습니다. 아래 그림의 uj 식과 같이 되며 이때 xj - uj 를 xj(i)로 치환하여 사용합니다.

또 다른 하나는 feature scaling 입니다. 이것은 우리의 dataset의 features이 단위가 크게 차이가 날 경우에만 필요에 따라서 사용하면 되겠습니다. 이때에는 xj(i) - uj(i) 를 sj로 나눠주어 xj(i)를 만들어줍니다. 이때 sj 는 max - min 의 값으로 사용해도 되고 일반적으로는standard deviation(표준편차)를 많이 사용합니다.

 

 

2차원에서 1차원으로 낮추는 방식에서 핵심은 u(i) vector를 찾는 일입니다. 이 u vector를 기준으로 직선이나 면을 생성하고 모든 x data들을 투영하여 차원을 낮추게 되는 기준이 되기 때문이지요.

이러한 u vector를 수학적으로 풀이하기에는 어려운일이 될수 있습니다. 하지만 한번 알아두면 그다음에는 쉽게 사용이 가능하게 될 것입니다.

 

 

 

PCA algorithm

이제 본격적으로 PCA algorithm에 대해서 알아보겠습니다.

n 차원의 데이터를 k 차원으로 낮추기 위해서는 다음의 두가지 방식을 사용하여 연산을 하게 됩니다. 

하나는 Covariance Matrix(공분산행렬)을 이용하는 것입니다. 이것은 두개의 변수에 대한 상관관계를 나타내는 것으로 확률과 통계를 이용한 방식이라고 합니다. 이러한 상관관계를 통해서 두가지 변수에 대한 선형의존도를 나타내기도 합니다. 여기서는 아래와 같이 Upper case Sigma 기호로 표현이 되는 공식이 됩니다. 이 sigma는 summation 기호와는 다른 의미이니 혼동 하지 않기를 바랍니다. 이 Sigma는 nx1의 크기를 갖는 x(i)와 1xn의 크기를 갖는 x(i)T와의 곱으로 이루어지므로 nxn의 크기를 갖는 matrix가 됩니다.  

또 하나는 Eigenvector(고유벡터)를 이용하는 것입니다. 이것은 선형대수학에서 고유벡터로 불리우는 벡터로서 0이 아닌 값을 가지면서 선형변형이 일어난 이후에도 방향이 변하지 않는 벡터를 의미한다고 합니다. 여기서는 Sigma의 값을 svd로 연산을 하게 되는데 이때의 svd는 Singular Value Decomposition의 약자로서 eigenvector 보다 안정적인 수학적 방식이라고 합니다. 

 

 

svd(Sigma) 연산으로 부터 얻은 U matrix는 아래 그림의 nxn 크기의 matrix와 같이 생겼습니다. 여기서 우리는 n차원을 k차원으로 낮추기 위해서 u(1)부터 u(k)까지를 사용하여 z vector를 만들게 됩니다. 아래 그림의 하단에 matrix 공식과 같이 z vector는 k 크기를 갖는 vector가 되며, U matrix에서 1부터 k까지를 가지고 와서 Ureduce matrix를 생성하고 Ureduce T * X를 하여 z vector를 연산하게 됩니다.

z = (Ureduce)T * x

 

 

mean normalization에 대해서 조금더 살펴보겠습니다.

Sigma는 아래와 같이 x(i) x(i)T로 구성이 되며 이것은 Octave 에서 구현할때 Sigma = (1/m) * X' * X;와 같이 심플하게 됩니다.

또 [U, S, V] = svd(Sigma) 를 Octave 에서 구현할때 Ureduce = U(: , 1:k);로 k 크기로 잘라서 x와 곱하기 연산을 하면 z를 생성할 수 있습니다. z = Ureduce' * X;

이때 x0 값을 고려하지 않고 합니다.

 

지금까지 배운 차원을 낮추기 위해 사용되는 PCA 알고리즘을 간단하게 요약을 하면 다음과 같습니다.

1. Preprocessing

2. Calculate sigma (covariance matrix)

3. Calculate eigenvectors with svd

4. Take k vectors from U (Ureduce= U(:,1:k);)

5. Calculate z (z =Ureduce' * x;)

출처: https://daeson.tistory.com/214?category=654766 [대소니]