차원 축소 기법

차원 축소를 위한 접근 방법

투영^projection

• 예를 들어 3차원 데이터셋에 모든 훈련 샘플이 거의 평면 형태로 놓여 있는 경우
• 이것이 고차원(3D) 공간에 있는 저차원(2D) 부분 공간^subspace
• 모든 훈련 샘플을 이 부분 공간에 수직으로 (i.e. 샘플과 평면 사이의 가장 짧은 직선을 따라) 투영하면 2D 데이터셋을 얻는다.

매니폴드 학습^{manifold learning}

• 많은 차원 축소 알고리즘이 훈련 샘플이 놓여 있는 매니폴드를 모델링하는 식으로 작동
• 대부분 실제 고차원 데이터셋이 더 낮은 저차원 매니폴드에 가깝게 놓여 있다는 매니폴드 가정^{manifold assumption} 또는 매니폴드 가설^{manifold hypothesis}에 근거
• 매니폴드 가정은 처리해야 할 작업(e.g. 분류나 회귀)이 저차원의 매니폴드 공간에 표현되면 더 간단해질 것이란 가정을 종종 암묵적으로 병행 (항상 유효하지는 않다.)

d차원 매니폴드 : 국부적으로 d차원 초평면으로 보일 수 있는 n차원 공간의 일부 (d<n)

---

주성분 분석^{principal component analysis}(PCA)

가장 인기 있는 차원 축소 알고리즘
데이터에 가장 가까운 초평면^hyperplane을 정의한 다음, 데이터를 이 평면에 투영

분산 보존

저차원의 초평면에 훈련 세트를 투영하기 전에 먼저 올바른 초평면을 선택
분산이 최대로 보존되는 축을 선택하는 것이 정보가 가장 적게 손실되므로 합리적
i.e. 원본 데이터셋과 투영된것 사이의 평균 제곱 거리를 최소화하는 축

주성분^{principal component}(PC)

• PCA는 훈련 세트에서 분산이 최대인 축을 찾는다.
• 첫 번째 축에 직교하고 남은 분산을 최대한 보존하는 두 번째 축을 찾는다.
• 고차원 데이터셋이라면 PCA는 이전의 두 축에 직교하는 세 번째 축을 찾으며 데이터셋에 있는 차원의 수만큼 네 번째, 다섯 번째, ... n번째 축을 찾는다.

i번째 축이 이 데이터의 i번째 주성분

주성분 행렬

특잇값 분해^{singular value decomposition}(SVD)라는 표준 행렬 분해 기술로 훈련 세트 행렬 X를 세 개 행렬의 행렬 곱셈인 $U\sum V^{T}$로 분해
모든 주성분의 단위 벡터가 V에 담겨 있다.
$V=\begin{pmatrix}
\mid &\mid & &\mid \\
c_ {1} &c_ {2} &\cdots &c_ {n}\\
\mid &\mid & &\mid
\end{pmatrix}$

d차원으로 투영하기

초평면에 훈련 세트를 투영하고 d차원으로 축소된 X^d-proj을 얻기 위해서는 행렬 X와 V의 첫 d열로 구성된 행렬 W_d를 행렬 곱셈

훈련 세트를 d차원으로 투영하기

$X_ {d-proj}=XW_ {d}$

설명된 분산의 비율^{explained variance ratio}

각 주성분의 축을 따라 있는 데이터셋의 분산 비율

적절한 차원 수 선택하기

축소할 차원 수를 임의로 정하기보다는 충분한 분산(e.g. 95%)이 될 때까지 더해야 할 차원 수를 선택하는 것이 간단
데이터 시각화를 위해 차원을 축소하는 경우에는 차원을 2개나 3개로 줄이는 것이 일반적

압축을 위한 PCA

압축된 데이터셋에 PCA 투영의 변환을 반대로 적용하여 원본의 차원 수로 되돌릴 수도 있다.
투영에서 일정량의 정보(유실된 분산)를 잃어버렸기 때문에 이렇게 해도 원본 데이터셋을 얻을 수는 없지만 원본 데이터와 비슷할 것
원본 데이터와 재구성된 데이터 (압축 후 원복한 것) 사이의 평균 제곱 거리를 재구성 오차^{reconstruction error}라고 한다.

원본의 차원 수로 되돌리는 PCA 역변환

$X_ {recovered}=X_ {d-proj}W_ {d}^{T}$

랜덤 PCA^{randomized PCA}

확률적 알고리즘을 사용해 처음 d개의 주성분에 대한 근삿값을 빠르게 찾는다.

점진적 PCA^{incremental PCA}(IPCA)

훈련 세트를 미니배치로 나눈 뒤 IPCA 알고리즘에 한 번에 하나씩 주입
훈련 세트가 클 때 유용하고 온라인으로 (i.e. 새로운 데이터가 준비되는 대로 실시간으로) PCA를 적용할 수도 있다.

---

커널 PCA^{kernel PCA}(kPCA)

고차원 특성 공간에서의 선형 결정 경계는 원본 공간에서는 복잡한 비선형 결정 경계에 해당
위를 PCA에 적용해 차원 축소를 위한 복잡한 비선형 투영을 수행
투영된 후에 샘플의 군집을 유지하거나 꼬인 매니폴드에 가까운 데이터셋을 펼칠 때도 유용

커널 선택과 하이퍼파리미터 튜닝

kPCA는 비지도 학습이기 때문에 좋은 커널과 하이퍼파리미터를 선택하기 위한 명확한 성능 측정 기준이 없지만 차원 축소는 종종 지도 학습(e.g. 분류)의 전처리 단계로 활용되므로 그리드 탐색을 사용하여 주어진 문제에서 성능이 가장 좋은 커널과 하이퍼파라미터를 선택할 수 있다.
완전한 비지도 학습 방법으로, 가장 낮은 재구성 오차를 만드는 커널과 하이퍼파라미터를 선택하는 방식도 있다.

---

지역 선형 임베딩^{locally linear embedding}(LLE)

또 다른 비선형 차원 축소^{nonlinear dimensionality reduction}(NLDR) 기술
각 훈련 샘플이 가장 가까운 이웃^{closest neighbor}(c.n.)에 얼마나 선형적으로 연관되어 있는지 측정하고 국부적인 관계가 가장 잘 보존되는 훈련 세트의 저차원 표현을 찾는다.

LLE 단계 1 : 선형적인 지역 관계 모델링

$\hat{W}=\underset{W}{\text{argmin}}\sum_ {i=1}^{m}(x^{(i)}-\sum_ {j=1}^{m}w_ {i,j}x^{(j)})^{2}$
$\text{[조건]}\begin{cases}w_ {i,j}=0 & x^{(j)}\text{가 }x^{(i)}\text{의 최근접 이웃 }k\text{개 중 하나가 아닐 때} \\
\sum_{j=1}^{m}w_ {i,j}=1 & i=1,2,\cdots ,m\text{일 때}
\end{cases}$
먼저 알고리즘이 각 훈련 샘플 $x^{(i)}$에 대해 가장 가까운 k개의 샘플을 찾는다.
그런 다음 $x^{(i)}$와 $\sum_ {j=1}^{m}w_ {i,j}x^{(j)}$ 사이의 제곱 거리가 최소가 되는 $w_ {i,j}$를 찾는다.
$x^{(j)}$가 $x^{(i)}$의 가장 가까운 k개 이웃 중 하나가 아닐 경우에는 $w_ {i,j}=0$
$\sum_{j=1}^{m}w_ {i,j}=1$은 각 훈련 샘플 $x^{(i)}$에 대한 가중치를 단순히 정규화

LLE 단계 2 : 관계를 보존하는 차원 축소

$Z=\underset{Z}{\text{argmin}}\sum_{i=1}^{m}(z^{(i)}-\sum_ {j=1}^{m}\hat{w}_ {i,j}z^{(j)})^{2}$
$z^{(i)}$가 d차원 공간에서 $x^{(i)}$의 상이라면 가능한 한 $z^{(i)}$와 $\sum_ {j=1}^{m}\hat{w}_ {i,j}z^{(j)}$ 사이의 거리가 최소화되어야 한다.
샘플을 고정하고 최적의 가중치를 찾는 대신, 반대로 가중치를 고정하고 저차원의 공간에서 샘플 이미지의 최적 위치를 찾는다.

---

다른 차원 축소 기법

랜덤 투영^{random projection}

랜덤한 선형 투영을 사용해 데이터를 저차원 공간으로 투영

다차원 스케일링^{multidimensional scaling}(MDS)

샘플 간의 거리를 보존하면서 차원을 축소

Isomap

각 샘플을 가장 가까운 이웃과 연결하는 식으로 그래프를 만들고 샘플 간의 지오데식 거리^{geodesic distance}를 유지하면서 차원을 축소

t-SNE^{t-distributed stochastic neighbor embedding}

비슷한 샘플은 가까이, 비숫하지 않은 샘플은 멀리 떨어지도록 하면서 차원을 축소
주로 시각화에 많이 사용되며 특히 고차원 공간에 있는 샘플의 군집을 시각화할 때 사용

선형 판별 분석^{linear discriminant analysis}(LDA)

분류 알고리즘
훈련 과정에서 클래스 사이를 가장 잘 구분하는 축을 학습
이 축은 데이터가 투영되는 초평면을 정의하는 데 사용
투영을 통해 가능한 한 클래스를 멀리 떨어지게 유지시키므로 SVM 분류기 같은 다른 분류 알고리즘을 적용하기 전에 차원을 축소시키는 데 좋다.

---

실습코드링크 : 차원의 저주