1-3. 차원축소 - Feature Extraction(1); PCA, MDA

feature 성질을 유지하며 차원 축소하는 기법

---

PCA(Principal Component Analysis, 주성분 분석)

• 목표: 분산을 보존하는 직교기저 찾기
• 데이터 행렬 $X$를 기저 $w$에 사영한 결과 $w^{T}X$에 대한 공분산 행렬 $w^{T}Sw$에 대해, $w^{T}Sw$가 최대가 되도록 하는 기저 $w$는 $S$의 고유벡터이다.
  (고유값 λ이 큰 고유벡터 $v$가 분산을 보존하는 기저)
• 고유값 계산으로 k번째 기저에 사영했을 때, 보존되는 분산량을 구할 수 있다.
  $\frac{\lambda_k}{\lambda_1+\lambda_2+\ldots+\lambda_d}$
• 몇 개의 주성분을 사용하는 것이 적절한지 판단하기 위해 아래의 방법을 사용한다.
  • 주성분 별 보존되는 분산량 그래프에서 elbow point 찾기
  • 누적 보존 분산량 그래프에서 일정 수준 분산량을 만족하는 주성분 찾기

데이터 행렬 $X$를 기저 $w$에 사영한 결과 $w^{T}X$에 대한 공분산 행렬 구하기

$\mathrm{V}=\frac{1}{n}\left(\mathbf{w}^{\mathrm{T}} \mathbf{X}\right)\left(\mathbf{w}^{\mathrm{T}} \mathbf{X}\right)^{\mathrm{T}}=\frac{1}{n} \mathbf{w}^{\mathrm{T}} \mathbf{X} \mathbf{X}^{\mathrm{T}} \mathbf{w}=\mathbf{w}^{\mathrm{T}} \mathbf{S} \mathbf{w}$

 

$w^{T}Sw$가 최대가 되도록 하는 기저 $w$ 구하기

$\max \mathbf{w}^T \mathbf{S} \mathbf{w} \quad$ s.t. $\mathbf{w}^T \mathbf{w}=1$
$L=\mathbf{w}^T \mathbf{S} \mathbf{w}-\lambda\left(\mathbf{w}^T \mathbf{w}-1\right)$
$\frac{\partial L}{\partial \mathbf{w}}=0 \Rightarrow \mathbf{S} \mathbf{w}-\lambda \mathbf{w}=0 \Rightarrow(\mathbf{S}-\lambda \mathbf{I}) \mathbf{w}=0$

$w: S$'s eigenvector, $\lambda: S$'s eigenvalue

 

---

 

MDS(Multidimensional Scaling, 다차원 척도법)

• 목표: 객체 간 거리를 보존하는 좌표시스템 만들기
• 객체 간의 distance matrix $D$(nxn)로 부터 inner product matrix $B$(nxn)를 만들고
  inner product matrix $B$(nxn)로 부터 좌표시스템 $X$(dxn)를 만든다.

객체 간의 distance matrix $D$는 다음과 같이 표현된다.

$d_{r s}^2=\left(\mathbf{x}_r-\mathbf{x}_s\right)^T\left(\mathbf{x}_r-\mathbf{x}_s\right)$

 

Inner product matrix $B$ ($B=XX^{T}$) 각 항목 $b_{rs}$를 $d_{rs}$로 표현하면 다음과 같다.

$\begin{aligned} b_{r s} & =\mathbf{x}_r^T \mathbf{x}_s \\ & =-\frac{1}{2}\left(d_{r s}^2-\mathbf{x}_r^T \mathbf{x}_r-\mathbf{x}_s^T \mathbf{x}_s\right) \\ & =-\frac{1}{2}\left(d_{r s}^2-\frac{1}{n} \sum_{s=1}^n d_{r s}^2-\frac{1}{n} \sum_{r=1}^n d_{r s}^2+\frac{1}{n^2} \sum_{r=1}^n \sum_{s=1}^n d_{r s}^2\right)\end{aligned}$

 

Inner product matrix $B$는 symmetric, positive-definite조건으로 다음과 같이 표현할 수 있다.

$\mathbf{B}=\mathbf{V} \boldsymbol{\Lambda} \mathbf{V}^T, \quad \boldsymbol{\Lambda}=\operatorname{diag}\left(\lambda_1, \lambda_2, \ldots, \lambda_n\right), \mathbf{V}=\left[\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\right]$

 

좌표시스템 $X$가 $n$개의 벡터로 이뤄진 $p$차원의 matrix일 때, Inner product matrix $B$는 $(n-p)$개의 zero eigenvalue를 가지므로 $B_{1}$으로 다시 표현하면 다음과 같다.

$\mathbf{B}_1=\mathbf{V}_1 \boldsymbol{\Lambda}_1 \mathbf{V}_1^T, \quad \boldsymbol{\Lambda}_1=\operatorname{diag}\left(\lambda_1, \lambda_2, \ldots, \lambda_p\right), \mathbf{V}_1=\left[\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_p\right]$

 

좌표시스템 $X$는 다음과 같이 구할 수 있습니다.

$\begin{aligned} \mathbf{B}_1 & =\mathbf{V}_1 \boldsymbol{\Lambda}_1 \mathbf{V}_1^T \\ & =\left(\mathbf{V}_1 \boldsymbol{\Lambda}_1^{\frac{1}{2}}\right)\left(\mathbf{V}_1 \boldsymbol{\Lambda}_1^{\frac{1}{2}}\right)^T \\ & =\mathbf{X X}^T\end{aligned}$

 

 

---

출처

• 01-4: Dimensionality Reduction - PCA
  https://youtu.be/bEX6WPMiLvo
• 01-5: Dimensionality Reduction - MDA
  https://youtu.be/Yv00AT4pLC4