[데이터 마이닝] 주성분 분석 (Principal Component Analysis, PCA)과 차원 축소

1. 차원 축소 (Dimensionality reduction)

대부분의 경우, 현실 세계의 문제는 가공되지 않은 데이터를 처리해야 한다. 예를 들어, 머신 러닝 모델을 이용하여 증명사진에 있는 인물의 성별을 맞추는 문제가 있을 때, 이 문제를 풀기 위해 우리는 성별이 표시된 증명사진을 머신 러닝 모델의 학습 데이터로 이용할 것이다. 하나의 사진이 200X200의 이미지라고 하면, 해당 사진은 총 40,000개의 feature를 갖는 벡터로 표현이 될 것이다. 그러나 대부분의 머신 러닝 모델은 입력 데이터의 차원이 클 경우, 차원의 저주와 학습 속도가 저하되는 문제를 갖고 있다. 이를 위해 생각해볼 수 있는 것은 이미지에서 인물에 대한 정보를 포함하지 않는 부분을 제거하여 입력 데이터의 차원을 낮추는 것이다. 예를 들어, 증명사진의 왼쪽과 오른쪽 상단은 단색의 배경이기 때문에 인물에 대한 정보를 포함하지 않으며, 배경 부분을 제거하여 모델을 학습하여도 성능에는 큰 차이가 없을 것이다. 이와 같이 데이터에서 불필요한 feature를 제거하는 작업을 차원 축소라고 한다.

2. 특징 선택 (Feature selection)과 특징 추출 (feature extraction)

차원 축소는 주어진 데이터 $x \in \mathbb{R}^{d \times 1}$를, $z \in \mathbb{R}^{p \times 1}$로 변환하는 것을 말한다. 이때, $p$는 $d$보다 작은 양의 정수이다. 데이터의 차원을 축소하기 위한 방법으로는 크게 특징 선택 (feature selection)과 특징 추출 (feature extraction)이 있다. 특징 선택은 $d$ 차원의 데이터 $x$를 구성하는 각 feature $e_1, e_2, ..., e_d$ 중에서 어떠한 기준을 만족하는 $p$개의 feature를 선택한다. 반면에 특징 추출은 기존의 feature $e_1, e_2, ..., e_d$를 조합하여 새로운 feature $z_1, z_2, ..., z_p$를 생성한다. 이 글에서는 특징 추출 방법 중에서도 가장 간단한 선형 특징 추출 알고리즘에 대해 서술한다.

특징 추출을 위한 가장 기본적인 방법은 $z_j = w_{1j}x_1 + w_{2j}x_2 + ... + w_{dj}x_d$와 같이 기존의 feature를 선형 결합하여 새로운 feature를 생성하는 것이다. 선형 특징 추출 알고리즘의 구현은 변환 행렬 (transformation matrix),

$$W^T = \begin{bmatrix} w_{11} & w_{12} & \dots & w_{1p}\\ \vdots & \vdots & \ddots & \vdots \\ w_{d1} & w_{d2} & \dots & w_{dp}  \end{bmatrix}^T$$

를 어떠한 기준으로 어떻게 결정하는가에 따라 달라진다. 이 글에서는 선형 특징 추출 방법의 가장 대표적인 알고리즘인 주성분 분석 (principal component analysis, PCA)에 대해 서술한다.

3. 주성분 분석 (PCA)

PCA의 목적은 $d$ 차원의 feature space에 존재하는 $N$개의 데이터 $X \in \mathbb{R}^{d \times N}$를 $p$ 차원의 feature space에 존재하는 $N$개의 데이터 $Z \in \mathbb{R}^{p \times N}$로 변환하는 것이다. 이때 $X$는 행렬로 표현되며, $X$의 열벡터 $X_k = [x_{1k} \; x_{2k} \; ... \; x_{dk}]^T$는 $k$번째 데이터를 나타내고, $x_{ik}$은 $k$번째 데이터의 $i$번째 요소를 의미한다. PCA는 원본 데이터 $X$를 다음의 두 가지 기준을 만족하는 새로운 feature space로 사상한다.

• 새로운 feature space를 구성하는 feature인 $z_1, z_2, ..., z_p$는 서로 선형 독립이다.
• 원본 데이터 $X$를 $z_j$축으로 사상할때, 분산이 최대화되도록 $z_j$를 결정한다. 이때 $z_1$축은 가장 큰 분산을 갖는 축이며, $z_2$는 두 번째로 큰 분산을, $z_j$는 $j$번째로 큰 분산을 갖는다.

PCA에서 분산을 최대화하는 새로운 feature (축)를 찾는 이유는 다음의 예제를 보면 명확히 이해할 수 있다. 아래의 [그림 1]과 같이 두 개의 class $C_1, C_2$로 구성되며, 2차원 공간에 존재하는 데이터 $X$가 있다.

[그림 1] 예제 데이터의 분포

2차원 공간에 존재하는 $X$를 1차원으로 차원 축소를 해야 하는 상황에서 우리는 데이터를 단순히 x-축으로 사상하는 방법을 생각해볼 수 있다. 만약 $X$를 x-축으로 사상한다면, 데이터는 1차원 feature space에서 [그림 2]와 같이 분포할 것이다.

[그림 2] 예제 데이터에 대한 x-축 사상

[그림 2]에서 A와 B에 해당하는 영역은 각각 $C_1$과 $C_2$에 속하는 데이터가 x-축에 사상되는 영역을 나타내며, C에 해당하는 영역은 $C_1$과 $C_2$의 데이터가 겹쳐지는 영역을 의미한다. Classification 또는 clustering의 관점에서 차원 축소 문제를 볼 때, C에 해당하는 영역이 클수록 classification 또는 clustering 알고리즘의 정확도는 하락할 것이다. 반면에 C에 해당하는 영역이 아예 존재하지 않는다면 100%의 정확도를 갖는 classification 또는 clustering 알고리즘을 만드는 것은 그리 어려운 일이 아닐 것이다. 따라서, C 영역을 최소화하도록 차원 축소를 수행하는 것은 매우 타당한 선택 중 하나이며, 이 목표는 데이터의 분산을 최대화하도록 차원 축소를 진행함으로써 간접적으로 달성할 수 있다. 이러한 관점에서 PCA는 [그림 3]의 z-축과 같은 주성분 (principal component)를 찾는다.

[그림 3] 예제 데이터에 대한 주성분, z-축 사상

4. PCA 알고리즘

$d$ 차원에 존재하는 표준화 (standardization)된 $N$개의 데이터 $X \in \mathbb{R}^{d \times N}$와 PCA의 변환 행렬 $W \in \mathbb{R}^{d \times p}$에 대해 차원 축소를 통해 생성된 $p$ 차원의 $N$개의 데이터 $Z \in \mathbb{R}^{p \times N}$는 식 (1)과 같은 관계를 갖는다.

$$Z = W^T X \tag{1}$$

변환된 데이터 $Z$의 공분산 행렬 (covariance matrix) $\Sigma \in \mathbb{R}^{p \times p}$은 아래와 같이 계산된다.

$$\Sigma = \frac{1}{N}ZZ^T = \frac{1}{N}(W^TX)(W^TX)^T = \frac{1}{N}W^TXX^TW \tag{2}$$

$W^T$의 첫 번째 열벡터를 $W_1^T$라 하고, $X$의 공분산 행렬인 $\frac{1}{N}XX^T$를 $S$라 할 때, PCA에서 풀고자 하는 문제는 $W_1^TSW_1$를 최대화하는 $W_1$를 결정하는 문제가 된다. $W_1$의 크기가 1이라고 가정할 때, Rayleigh quotient에 의해 $W_1^TSW_1$의 최댓값은 $S$의 가장 큰 eigenvalue와 같다. 이때, $W_1$은 $S$의 가장 큰 eigenvalue와 대응되는 eigenvector이며, 벡터의 크기는 1이다. $d$ 차원의 데이터를 1 차원의 데이터로 축소한다면, 가장 큰 eigenvalue와 대응하는 $W_1$만 찾으면 된다. 만약 $p (> 1)$ 차원의 데이터로 축소하고자 한다면, $W_2$는 $S$의 두 번째로 큰 eigenvalue와 대응하는 eigenvector로 설정하고, $W_p$는 $p$번째로 큰 eigenvalue와 대응하는 eigenvector로 설정하면 된다. PCA 알고리즘을 요약하면 아래와 같다.

1) 표준화된 데이터 $X$의 공분산 행렬인 $S = \frac{1}{N}XX^T$를 계산한다.

2) $S$의 eigenvalue를 계산하고, 값이 큰 순서대로 eigenvalue들과 그에 대응하는 eigenvector들을 정렬한다.

3) 큰 순서대로 $p$개의 eigenvalue와 그에 대응하는 eigenvector를 선택하고, 각 eigenvector를 $W^T$의 열벡터로 설정한다.