[1-4] Dimensionality Reduction : PCA

2019-08-17 이민예

Curse of Dimensionality (차원의 저주)

차원의 저주는 Richard Bellman, Dynamic Programming (1957) 에서 처음 소개되었다. 유클리드 공간에 차원이 증가하게 되면, 부피가 기하급수적으로 증가한다는 것이다.

차원과 부피

N(표본의 수) = 20 이 균등하게 4구역으로 나눠진 1차원 공간에 분포되있다고 가정한다면, 공간은 4가 되고, 밀도는 20/4 = 5가 된다.

차원

부피

밀도

1

4 (1*4)

20/4 = 5

2

16 (4*4)

20/16 = 1.25

3

64 (16*4)

20/64 = 0.31

차원을 확장한다고 하면, 부피는 기하급수적으로 증가하고, 밀도는 희소하게 되는데, 1차원 일때 한 구역당 평균 5개의 샘플이 존재했다면, 3차원일 경우 한 구역당 약 0.31개의 샘플이 존재한다는 것이다. 밀도는 다음의 식과 비례한다.

N1/DN^{1/D}

따라서, 20개의 샘플이 있었을 때 3차원도 같은 밀도를 가지기 위해서는 8000개의 데이터가 필요하다.

201/1=x1/320^{1/1} = x^{1/3}

이러한 차원의 저주를 늘리기 위해, 학습 데이터량을 늘리는 방법이 있지만 데이터 셋의 크기에 비해, 차원은 기하급수적으로 증가하기 때문에 매우 힘든 방법이다.

차원의 축소

차원을 축소하기 위한 방법에는 특징 추출과 특징 선택이 있다.

PCA(Primary Component Analysis)

Principle Component Analysis (PCA)는 대표적인 차원 축소 알고리즘이며, 다음과 같은 단계로 이루어진다.

  1. 학습 데이터셋에서 분산이 최대인 축(axis)을 찾는다.

  2. 이렇게 찾은 첫번째 축과 직교(orthogonal)하면서 분산이 최대인 두 번째 축을 찾는다.

  3. 첫 번째 축과 두 번째 축에 직교하고 분산을 최대한 보존하는 세 번째 축을 찾는다.

  4. 1~3과 같은 방법으로 데이터셋의 차원(특성 수)만큼의 축을 찾는다.

1. 분산이 최대인 축을 찾음

분산이 가장 큰 축에 있는 데이터가 데이터를 가장 잘 설명할 수 있는 제 1주성분, PC1 이라고 한다. 다수의 두 변량 값들 간의 분산을 구하기 위하여, 공분산을 행렬을 사용한다.

Σ=cov(X)=1/(n−1)XXTΣ=cov(X)=1/(n-1) XX^T

공분산 행렬과 같은 방향이지만, 크기만 커진 벡터는 고유벡터이고, 고유값이 가장 큰 값이 분산이 최대인 축에 해당한다.

A 행렬로 선형 변환을 하는 경우, 고유 벡터는 A 행렬에 벡터가 작용하는 힘의 크기를 나타냅니다. 만일 이 행렬이 공분산 행렬일 경우에 이 공분산 행렬의 고유 벡터는 데이터가 어떤 방향으로 크게 분산되어 있는지, 즉 어떤 방향으로 큰 힘이 작용하는 지를 나타냅니다.

2. 서로 다른 고유벡터끼리는 서로 직교함

제 1주성분을 찾은 후, 제 2성분을 찾기 위해, 제 1 주성분을 뺀다. 아래와 같이 제 1 주성분을 x축이 되도록 돌리면 제 1 주성분의 영향이 0이 된다.

이 상태에서 가장 분산이 큰 축은 x축이 된 제 1 주성분과 직교하면서 분산이 최대 선일 것이다. 이 축이 PC2, 제 2 주성분이 된다. 이런 식으로 변수의 주성분을 뽑게 된다.

A는 공분산행렬 Σ 에 대한 고유벡터이다.

ΣA=ΛAΣA=ΛA

다시 쓰자면, 다음과 같다.

Σ=AΛA−1Σ=AΛA^−1

공분산행렬 Σ은 대칭행렬이므로 공분산 행렬의 전치행렬은 원래의 공분산행렬과 같다.

ΣT=(A−1)TΛAT=AΛA−1=ΣΣ^T=(A^−1)^TΛA^T = AΛA^−1=Σ

정리하자면, 다음과 같다.

A−1=ATA^−1=A^T

따라서, 공분산 행렬의 고유벡터는 서로 직교한다.

ATA=IA^TA=I

3. 데이터셋의 차원(특성 수)만큼의 반복하여 고유벡터, 고유값 찾음

590*590 공분산 행렬이 존재할 때, 데이터셋의 특성 수인 590 만큼의 고유벡터가 존재한다. PCA 주성분 분석후, 분석가가 판단한 특징 수를 기준으로 벡터를 만든 후, centering된 1567*590 데이터행렬에 생성된 벡터를 곱하여, 저차원으로 변환한다.

예제: PCA로 반도체 제조 데이터 차원 축소하기

https://colab.research.google.com/drive/1xwkkehAYEmHAQMvasTjXYrLXojDAxpXD

[ Reference ] :

https://skymind.com/kr/wiki/eigenvector

https://kkokkilkon.tistory.com/169

부록

고유값과 고유벡터

고유 벡터(eigenvector 아이건벡터)는 행렬 A의 선형 변환이 일어난 후에도 자기 자신의 상수배가 되어 방향이 변하지 않는, 영벡터가 아닌 벡터이다.

고윳값(eigenvalue 아이건밸류)은 고유 벡터의 길이가 변하는 배수, 이 상수값이다.

입력벡터는 A행렬과 같은 방향으로 더 크기만 커진 출력벡터가 됨.

  • A라는 행렬에 입력벡터가 곱해져서 출력벡터가 나옴.

  • 입력벡터와 출력벡터는 기본적으로 달라야함.

  • 벡터에는 길이와 방향이 있음.

  • 하지만, A라는 행렬에 선형 변환을 통해서 방향은 변하지 않고, 크기만 람다배로 바뀜.

  • 이 벡터와 이 상수값을 둘 다 찾아야 함.

PreviousMDSNextNovelty Detection

Last updated