1. 주성분 분석

1) 개요

- 주성분 분석(principal component analysis, PCA)은 여러 개의 데이터들이 어떤 양상으로 분포하고 있을 때 이 분포의 주성분(그 방향으로 데이터들의 분산이 가장 큰 방향벡터)을 분석하는 기법을 말한다.

- 기하학적으로 어떤 행렬의 고유벡터는 그 행렬에 관한 좌표축을, 고유값은 그 행렬이 그 고유벡터 방향으로 치우친 정도를 의미한다고 볼 수 있으므로, 여러 차원의 성분을 갖는 데이터들을 적절히 수정해 정사각 행렬로 만든 후 고유값 분해를 해 고유벡터들과 고유값을 얻어 이러한 분석을 할 수 있다. 정사각 행렬을 만드는 방법으로서 보통은 다음과 같이 정의되는 행렬을 이용한다.

- 예를 들어 \(m\)개의 \(n\)-벡터 \(\mathbf{x}_i\)가 주어졌을 때, 다음과 같은 행렬을 정의할 수 있다.

\(C = {1 \over {m} } \sum_{i=1}^n { (\mathbf{x}_i - \mathbf{m}) (\mathbf{x}_i - \mathbf{m})^T }\) (단, \(\mathbf{m}\)는 \(\mathbf{x}_i\)의 중심 벡터)

- 위 행렬 \(C\)를 흔히 공분산 행렬이라 하며, 각 성분은 기하학적으로 ‘데이터셋이 그 두 벡터의 축으로 함께 퍼진 정도’를 뜻한다. 이 \(C\)는 대칭행렬이므로 [\(m \times m\) 회전행렬(흔히 \(W\)라 한다) ]\(\times\) [\(m \times m\) 대각행렬(흔히 \(D\)라 한다)] \(\times\) [\(W^T\) ] 꼴로 직교대각화 할 수 있다. 이때 \(W\)와 \(D\)는 다음 의미를 갖는다.

  • \(W\): 데이터들이 주로 분포하고 있는 방향벡터(주성분)에 관한 정보를 담고 있는 회전행렬. \(C\)의 고유벡터들로 이루어져 있다.

  • \(D\): 데이터들이 \(W\)의 각 벡터들의 방향으로 얼마나 응집되어 있는지를 담고 있는 대각행렬. \(C\)의 고유값들로 이루어져 있다. 크기가 왼쪽 위 성분부터 오른쪽 아래 성분 순으로 정렬돼 있는 것으로 전제한다.

- 이외에도 정사각 행렬을 만드는 방법으로서 m개의 n-벡터를 이어붙여 \(n \times m\) 행렬을 만든 후, 이 행렬을 대각선 왼쪽 아래와 오른쪽 위 부분으로 나눈 후 각각에 대하여 정사각 대칭행렬을 만든 후 직교대각화 하는 방법이 있다. 이 방식으로 직교대각화를 한 후 몇개의 고유벡터와 고유값만 떼와 다시 곱해 행렬을 만드는 식으로 원본 데이터셋을 저차원으로 압축한 데이터셋을 구할 수도 있다.

2) 공분산 행렬의 직교대각화를 이용한 데이터 압축-복원

- 공분산 행렬의 직교대각화를 이용해 고차원의 데이터셋을 저차원으로 압축하면서 정보 손실을 최소로 하는 함수를 구할 수 있고, 또 그렇게 압축된 데이터셋을 다시 원본 데이터셋과 가장 유사한 데이터셋으로 복원하는 함수를 구할 수도 있다.

- 결론부터 말하면, \(n\)-벡터 \(\mathbf{x}\)를 입력으로 받아 \(l\)-벡터를 결과값으로 갖는 인코딩 함수 \(f(\mathbf{x}) = D^T \mathbf{x}\)이고, \(l\)-벡터 \(\mathbf{c}\)를 입력으로 받아 \(n\)-벡터를 결과값으로 갖는 디코딩 함수 \(g(\mathbf{c}) = D \mathbf{c}\)이다. (단, \(D = \begin{bmatrix} \mathbf{d}_1 & \cdots & \mathbf{d}_l \end{bmatrix}, \mathbf{d}_1, \cdots, \mathbf{d}_l\) 는 데이터셋 \(\mathbf{x}_i\)로 만든 공분산 행렬의 가장 큰 \(l\)개의 고유값에 해당하는 고유벡터들.) 다음 과정을 통해 이를 증명할 수 있다.

- 기본적인 아이디어는 고차원 벡터를 입력으로 받으면 결과값으로 저차원 벡터를 내는 인코딩 함수 \(f\)와 저차원 벡터를 입력으로 받으면 결과값으로 고차원 벡터를 내는 디코딩 함수 \(g\)가 있을 때 처음의 입력 \(\mathbf{x}_0\)과 \(g(f(\mathbf{x}_0))\)의 값의 차이를 최소로 하는 \(f\)와 \(g\)를 찾는 것을 목표로 한다.

(1) \(f\), \(g\) 구하기

일단, \(g(\mathbf{c})= D\mathbf{c}\) (단, \(D = \begin{bmatrix} \mathbf{d}_1 & \cdots & \mathbf{d}_l \end{bmatrix}, \mathbf{d}_1, \cdots, \mathbf{d}_l\) 는 모두 orthonormal인 \(n\)-벡터)라 하고 \(f(\mathbf{x})\)를 \(F(f) = \int | \mathbf{x} - g(f(\mathbf{x})) | _{2}^2 d\mathbf{x} \) 값을 최소로 하는 함수라 하자.

한편 입력으로 함수를 받아 함수값으로 스칼라값을 내는 함수를 범함수(functional)라 하는데, 위 식의 \(F(f)\)가 이러한 범함수라 할 수 있다. 범함수의 최솟값은 변분법(calculus of variations)으로 구할 수 있으며, 변분법으로 \(F(f)\)의 최솟값을 구하려면 다음을 만족하는 \(f\)를 구하면 된다.

\[\nabla_f \| \mathbf{x} - g(f(\mathbf{x})) \|_2^2 = 0\]

이 식을 정리하면 \(f(\mathbf{x}) = D^T \mathbf{x}\) 일 때 \(F(f)\)가 최솟값을 가짐을 알 수 있다.

즉, \(\mathbf{x}_0\)과 \(g(f(\mathbf{x}_0))\)의 값의 차이를 최소로 하는 \(f(\mathbf{x}) = D^T \mathbf{x}\) , \(g(\mathbf{c})= D\mathbf{c}\) (단, \(D = \begin{bmatrix} \mathbf{d}_1 & \cdots & \mathbf{d}_l \end{bmatrix}, \mathbf{d}_1, \cdots, \mathbf{d}_l\) 는 모두 orthonormal인 \(n\)-벡터) 이다.

(2) 그러면 이제 이 식의 \(D\) 행렬이 각 성분으로 어떤 값을 갖는 행렬인지를 찾으면 인코딩 함수와 디코딩 함수가 어때야 하는지를 정확히 알 수 있다. 이는 다음 방법으로 찾을 수 있다.

먼저, \(X\)와 \(R\)을 다음과 같이 정의하자.

\[X = \begin{bmatrix} \mathbf{x}_1^T \\ \vdots \\ \mathbf{x}_m^T \end{bmatrix}, R = \begin{bmatrix} g(f(\mathbf{x}_1))^T \\ \vdots \\ g(f(\mathbf{x}_m))^T \end{bmatrix} = \begin{bmatrix} \mathbf{x}_1^T D D^T \\ \vdots \\ \mathbf{x}_m^T D D^T \end{bmatrix} = XDD^T\]

이때, \(E = X-R = X-XDD^T\)로 정의하면, 여기서 찾고자 하는 \(D\)는 \(E\)의 Frobenius norm(\(|E|_F\))을 최소로 하는 \(D\)이다.

그런데 \(|E|_ F\)를 정리하면 \(-\mathrm{tr}(D^T X^T X D) = - \sum_{i=1}^l \mathbf{d}_i^T X^T X \mathbf{d}_i\)를 얻는다.

이 식은 각 \(\mathbf{d}_i\)에 대한 \(X^T X\)의 이차형식의 합이므로, 각 이차형식을 최대로 하는 벡터(=\(X^T X\)의 고유벡터들)를 \(\mathbf{d}_i\)로 하면 최적의 \(D\)를 구함을 알 수 있다.

따라서, \(\mathbf{d}_1, \cdots, \mathbf{d}_l\)이 \(X^T X\)의 가장 큰 \(l\)개의 고유값에 해당하는 고유벡터들일 때 최적의 \(D\)를 얻는다.

2. 특이값 분해(singular value decomposition, SVD)

- 모든 \(m \times n\) 행렬은 [\(m \times m\) 회전행렬(흔히 \(U\)라 한다)] \(\times\) [\(m \times n\) 대각행렬(흔히 \(D\)라 한다)] \(\times\) [\(n \times n\) 회전행렬(흔히 \(V\)라 한다)의 전치행렬] 꼴로 인수분해 할 수 있으며, 이러한 인수분해를 특이값 분해(singular value decomposition)이라 한다. 각 행렬은 직교대각화를 이용하여 구한다. (역행렬이 존재하는 어떤 행렬과 그 전치행렬의 곱은 대칭행렬이 된다는 성질을 이용한다. 참고로 이는 전치행렬의 자명한 성질인데 전치행렬은 \((AB)^T = B^T A^T\)가 성립하기 때문이다.)

- 행렬의 곱셉은 좌표계 변환으로 볼 수 있다고 했으므로, 특이값 분해를 통해 \(m \times n\) 행렬을 다음과 같은 과정을 거쳐 얻어낸 행렬로 볼 수 있다.

(1) n차원 직교좌표계 벡터(=항등행렬)를 회전행렬 V로 회전시킨다.

(2) 회전된 결과의 각 축을 대각행렬 D로 증폭시킨다. (m이 n보다 크다면, 이때 m-n개의 새로운 축이 추가된다.)

(3) 앞선 결과를 회전행렬 U로 회전시킨다.

- 특이값 분해를 하면 PCA보다 더 간단한 방법으로 응집성 분석 및 데이터 압축을 할 수 있다. n개의 m-벡터로 \(m \times n\) 행렬을 만든 후, 이의 특이값 분해 U, D, V 행렬을 구해 각 행렬의 왼쪽에서부터 p개(단, n > p)의 열벡터를 골라(단, D 행렬의 대각선 성분이 크기순으로 정렬돼있는 것으로 전제한다) 이들로 새로운 U, D, V 행렬을 구해 곱하면 처음 행렬의 근사 행렬이 구해진다.