선형판별분석 LDA 이해하기

안녕하세요 고공입니다 :)

곧있으면 제가 4월부터 시작한 프로젝트가 9월 말에 마무리가 되는데요, 이후 바로 새로운 프로젝트에 투입이 됩니다. 곧 있을 새로운 프로젝트에는 선형모델을 적용해야 합니다. 이를 위해 선형 모델에 대해 공부해볼까합니다. 제 블로그에 선형 회귀, 다항 회귀, 로지스틱 회귀에 대해 공부한 것이 있으니 이번에는 LDA에 대해 선형대수를 곁들여서 정리하고자 합니다. 이론 중심이라 정리하는 것도 어려웠지만 개념 맛보기 정도로 생각하시면 될 것 같습니다!

 

 

1. LDA이란?

 

LDA는 Linear Discriminant Analysis으로 우리말로는 선형판별분석이라고 합니다. LDA는 전통적인 선형 학습법으로 PCA와 마찬가지로 차원 축소 방법 중 하나입니다. 어떤 데이터 셋을 공간으로 투영하여 차원을 축소한다는 점에서 PCA와 비슷하지만 차이점이 있습니다. PCA와 다른 점으로 LDA는 Classification, 분류모델에 사용한다는 점입니다.

 

 

2. LDA의 원리

 

LDA가 작동하는 원리는 매우 단순합니다. 훈련 데이터 셋을 정하고 샘플을 하나의 직선 위에 투영시키면 되기 때문입니다.

 

같은 클래스에 속하는 샘플들을 가능한 한 가까운 투영점에 놓고 서로 다른 클래스에 속한 샘플들은 그 투영점에서 최대한 먼 위치에 위치하도록 합니다. 새로운 데이터에 대해 분류를 진행할 때 해당 직선상에 투영되도록 하고, 투영된 위치에 따라 해당 데이터의 클래스를 분류합니다.

 

아래의 그림을 통해 좀더 쉽게 이해해보도록 하겠습니다.

 

 

우리는 + 클래스와 - 클래스로 이루어진 데이터 셋을 가지고 있다고 가정합시다. +와 -를 분류하고 싶어 각각 $x_1$과 $x_2$에 점선으로 투영했습니다.   

 

과연 어떤 직선이 잘 분류되었다고 할 수 있을까요?

 

바로 빨간색 타원으로 표시된 $x_2$입니다. $x_1$에 투영했을때, 파란색 타원에 보이는 것 같이 +와 -는 서로 겹치는 부분들이 있습니다. 하지만 $x_2$는 +는 +끼리, -는 -끼리 잘 분류되어 있는 것을 볼 수 있습니다.

 

LDA가 바로 빨간색 타원처럼 분류해주는 기법입니다. 투영 후 같은 클래스들은 최대한 가까이 하고, 다른 클래스들은 최대한 멀리하는 방식입니다. 이를 적용할려면 같은 클래스 내 분산은 최소로 만들어 같은 클래스는 최대한 가까이 만들고, 다른 클래스 간 분산은 최대한 크게 만들어 다른 클래스 간의 거리를 최대한 멀게 만드는 겁니다.  

 

 

이제 선형대수를 곁들어서 다시 설명해볼게요.

 

 

데이터 셋 $D = \left\{(x_{i}, y_{i})\right\}_{i=1}^{m}, y_{i}\in \left\{0, 1 \right\}$에서 $X_{i}, \mu_{i}, \Sigma_{i}$를 각각 $i \in \left\{0,1\right\}$번째 클래스의 집합, 평균벡터, 공분산행렬로 정의해볼게요.

 

만약 데이터를 직선 $\omega$ 위에 투영한다면 두 클래스의 샘플들 $\mu_{0}$,  $\mu_{1}$의 중심으로 직선상의 $\omega^{\top}\mu_{0}$,  $\omega^{\top}\mu_{1}$로 각각 투영됩니다. 만약 모든 샘플들이 직선에 투영된다면 두 클래스의 공분산은 각각 $\omega^{\top}\Sigma_{0}\omega$,  $\omega^{\top}\Sigma_{1}\omega$로 나타낼 수 있습니다. 이때, 직선은 1차원이므로 $\omega^{\top}\mu_{0}$,  $\omega^{\top}\mu_{1}$,  $\omega^{\top}\Sigma_{0}\omega$,  $\omega^{\top}\Sigma_{1}\omega$는 모두 실수입니다.

 

만약 같은 클래스 샘플들의 점을 최대한 가까이 하려면 공분산을 최대한 작게 만들어주면 됩니다. 즉, $\omega^{\top}\Sigma_{0}\omega$,  $\omega^{\top}\Sigma_{1}\omega$를 최대한 작게 만드는 것이죠.

 

또한 다른 클래스에 속한 새픔들의 점을 최대한 멀리 하려면 각 클래스 중심점 간의 거리를 최대한 멀게 만들면 됩니다. 즉, $\left\|\omega^{\top}\mu_{0} - \omega^{\top}\mu_{1} \right\|_{2}^{2}$를 최대한 크게 만드는 것입니다. 

 

같은 클래스들의 점을 최대한 가까이 하고, 다른 클래스 간의 중심점의 거리를 최대한 멀게 만들려면 다음 식을 최대화하면 됩니다. 

 

$$\begin{align*} R &= \frac{\left\|\omega^{\top}\mu_{0} - \omega^{\top}\mu_{1} \right\|_{2}^{2} }{\omega^{\top}\Sigma_{0}\omega + \omega^{\top}\Sigma_{1}\omega}\\ &= \frac{\omega^{\top}(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{\top}\omega }{\omega^{\top}(\Sigma_{0}+\Sigma_{1})\omega} \end{align*}$$

 

위의 식을 집단 내 산포행렬과 집단 간 산포행렬을 이용해 다시 정리해볼 수 있습니다.

 

 

집단 내 산포행렬의 식은 다음과 같고,

$$\begin{align*} S_{\omega} &= \Sigma_0 + \Sigma_1\\ &= \sum_{x \in X_{0}}(x - \mu_0)(x - \mu_0)^\top + \sum_{x \in X_{1}}(x - \mu_1)(x - \mu_1)^\top \end{align*} $$

 

집단 간 산포행렬의 식은 다음과 같습니다.

$$S_b = (\mu_0 - \mu_1)(\mu_0 - \mu_1)^\top$$

 

이 두 식을 R 에 대입하면 다음과 같이 정리할 수 있습니다.

$$R = \frac{\omega^{\top}S_b\omega }{\omega^{\top}S_{\omega}\omega}$$

 

따라서 위 식은 같은 클래스들의 점을 최대한 가까이 하고, 다른 클래스 간의 중심점의 거리를 최대한 멀게 만드는 식입니다. LDA를 최대화할 때 이용하는 식이라고 할 수 있습니다.

 

우리는 이때 함수 R을 Rayleigh Quotient라고 부릅니다.

 

 

그렇다면 $\omega$는 어떻게 계산할까요?

 

$$R = \frac{\omega^{\top}S_b\omega }{\omega^{\top}S_{\omega}\omega}$$

 

위의 식을 다시 자세히 보면 분자와 분모가 모두 $\omega$에 대해 이차 항인걸 알 수 있습니다. $\omega$은 직선이자 벡터이기 때문에 길이는 상관없고, 방향만 관련이 있습니다. 

 

따라서 $\omega^{\top}S_{\omega}\omega$ = 1이라면 위의 식은 다음과 같이 정리할 수 있습니다.

 

$$\begin{align} \underset{\omega}{min} &\quad -\omega^{\top}S_b\omega\\ s.t. &\quad \; \omega^{\top}S_{\omega}\omega=1 \end{align}$$

 

이 식은 다시 라그랑주 승수법에 의해 아래 식과 같아집니다.

 

$$S_b\omega = \lambda S_{\omega}\omega$$

 

위 식에서 $\lambda$는 랑그랑주 곱셈자입니다. 이때, $S_b{\omega}$는 아래와 같은 식으로 표현할 수 있습니다.

 

$$S_b{\omega} = \lambda (\mu_0-\mu_1)$$

 

위 식을 $S_b{\omega}=\lambda S_{\omega}\omega$에 다시 대입하면 아래의 식으로 정리할 수 있습니다. 

 

$$\omega = S_{\omega}^{-1}(\mu_0-\mu_1)$$

 

이제 우리는 위의 식을 통해 $\omega$의 값을 구할 수 있는 거죠.

 

사실 $\omega$의 값을 구하려면 $S_{\omega}^{-1}$도 구하는 방법을 알아야 하는데 SVD(Singular Value Decomposition), 특잇값 분해를 알아야 합니다. $S_{\omega}^{-1}$는 $S_{\omega}$의 특잇값으로 구하는 방법이 따로 있습니다. 이 부분은 또 다른 공부가 필요하기 때문에 다음에 들고 오겠습니다.  

 

 

 

여기까지 따라오시느라 고생많으셨습니다. 혹시 제 글이 어려우시면 다음 블로그들이 더 쉽게 설명했으니 살포시 눌러서 놀러가주세요. 자 그럼 모두들 안녕!

 

 

 

참고 글1

머신러닝 - 18. 선형판별분석(LDA)

참고 글2 

Rayleigh quotients 과 최대값 (18.065)