LDA(Linear Discriminant Analysis)

Fisher's Discriminant Ratio

Fisher's Discriminant Ratio($J(w)$)는 클래스 간 분산과 클래스 내 분산의 비율로 정의되는 식이다.

 

수식 형태로 써보면

$$ Fisher's Discriminant Ratio = \frac{S_{b}(Between-Class Scatter)}{S_{w}(Within-Class Scatter)} $$

 

1. 클래스 간 분산(Between-Class Scatter) : 클래스 간 분산은 각 클래스의 평균 벡터와 전체 데이터의 평균 벡터 사이 차이를 계산한 뒤 클래스에 속하는 데이터의 갯수를 가중치로 곱해서 모든 클래스에 더한 값이다. $$ S_{b} = \sum^{K}_{i = 1}N_{i}(m_{i} - m)(m_{i} - m)^{T}, m = \frac{1}{K}\sum^{K}_{i=1}m_{i} $$
   • 여기서 $N_{i}$는 클래스 i에 속하는 데이터의 갯수, $m_{i}$는 클래스 i에 속하는 데이터의 평균 벡터, $m$은 전체 데이터의 평균 벡터이다.
2. 클래스 내 분산(Within-Class Scatter) : 클래스 내 분산은 각 클래스 내에서 각 데이터와 해당 클래스의 평균 벡터 사이의 차이를 계산한 뒤 모든 클래스와 데이터에 대해 더한 값이다. $$ S_{w} = \sum^{K}_{i=1}S_{i}, S_{i} = \sum_{t}r^{t}_{i}(x^{t} - m_{i})(x^{t} - m_{i})^{T} $$
   • 여기서 $x^{t}$는 클래스 i에 속한  데이터 샘플 각각의 값이고, $m_{i}$는 해당 클래스 i 내 샘플의 평균이다.

 

Fisher's Discriminant Analysis는 Ratio 값을 최대화하는 W를 찾는 것이고, 이를 수식으로 표현하면 다음과 같다.

$$ J(W) = \frac{|w^{T}S_{b}w|}{|w^{T}S_{w}w|} = \frac{|w^{T}(m_{1} - m_{2})|^{2}}{|w^{T}S_{w}w|}$$

 

이것이 최대화 되기 위해서는 클래스 간 분산은 최대화되어야 하며(클래스 간의 거리가 최대화 되어야 하며) 클래스 내 분산은 최소화 되어야 한다(클래스 내의 데이터는 가능한 한 가까이 모여 있어야 한다)

 

주어진 $J(W)$ 값을 최대화하는 W(선형 판별 벡터)를 찾는 것이 클래스 간 분리를 극대화하는 선형 분류 방향을 찾아내는 것이다.

(보통 이러한 분류 기법은 선형 분류 기법으로 이진 분류 문제에 주로 사용되며 클래스 간 겹치는 영역이 크거나 비선형적인 구분이 필요한 경우는 다른 분류 기법이 필요할 수 있다)

 

LDA

LDA(Linear Discriminant Analysis)란 분류(Classification) 문제에서 사용되는 차원 축소 방법이다.

고차원의 데이터를 저차원의 공간에 투영한다는 것은 PCA와 유사하지만, class 정보를 활용하여 차원을 축소하는데 초점을 두고 있다는 것에서 PCA와는 다르다.

 

LDA와 PCA의 차이점 (출처 : https://data101.oopy.io/easy-understand-pca-lda)

 

다음의 그림은 PCA와 LDA의 차이점을 나타낸 그림이다. 그림에서 보여지는 것과 같이 같은 데이터라도 투영하는 방식이 PCA와 LDA가 다름을 볼 수 있다.

 

이는 차원 축소의 목적에서의 차이로 인한 것이라고 설명할 수 있다. PCA는 데이터의 분산을 최대로 보존하면서 차원을 축소하는 것을 목표로 하는 반면 LDA는 클래스 간 거리(between-class distance)를 최대화하고 클래스 내부 거리(within-class distance)를 최소화하여 데이터를 구분하는 데 필요한 축을 찾아내는 것을 목표로 한다.

 

또한 방식 측면에서 PCA는 가장 큰 분산을 가지는 주성분(principal component)를 뽑아내는 것을 목표로 하는 반면 LDA는 클래스 간 거리와 클래스 내부 거리 모두를 고려하여 최적을 축을 찾아낸다. 즉, LDA는 PCA의 목적인 분산을 최대화하기 위해 차원 축소를 수행하는 것이 아닌, 데이터를 분류하는데 필요한 정보를 최대한 유지하기 위해 차원 축소를 수행한다.

 

이렇듯 projection을 통해서 두 그룹으로 잘 분리했다고 할 수 있다는 것은 projection된 두 데이터 집단 중심(평균) 사이의 거리가 멀고, 분산이 작을수록 잘 분리가 되었다고 말 할 수 있다.

 

LDA를 식으로 표현하면 다음과 같다

 

$$ J(w) = \frac{S_{b}(Between-Class Scatter)}{S_{w}(Within-Class Scatter)} = \frac{(m_{1} - m_{2})^{2}}{s_{1}^{2} + s_{2}^{2}} $$

 

여기서 $m_{1} = \frac{\sum_{t}w^{T}x^{t}r^{t}}{\sum_{t}r^{t}}$이고 $s_{1}^{2} = \sum_{t}(w^{T}x^{t} - m_{1})^{2}r^{t}$

 

1. 클래스 간 분산(Between-Class Scatter) : $ (m_{1} - m_{2})^{2} $ $$ (m_{1} - m_{2})^{2} = (w^{T}m_{1} - w^{T}m_{2})^{2} = w^{T}(m_{1} - m_{2})(m_{1} - m_{2})^{T}w = w^{T}S_{b}w $$
   • 여기서 $S_{b} = (m_{1} - m_{2})(m_{1} - m_{2})^{T}$
2. 클래스 내 분산(Within-Class Scatter) : $s_{1}^{2}$ $$ s_{1}^{2} = \sum_{t}(w^{T}x^{t} - m_{1})^{2}r^{t} = \sum_{t}w^{T}(m_{1} - m_{2})(m_{1} - m_{2})^{T}wr^{t} = w^{T}S_{1}w$$
   • 여기서 $S_{1} = \sum_{t}(m_{1} - m_{2})(m_{1} - m_{2})^{T}r^{t}$
   • $s_{1}^{2} + s_{2}^{2} = w^{T}S_{w}w, S_{w} = S_{1} + S_{2}$

 

Fisher's Discriminant Ratio에서 설명한 것처럼 클래스 간 분산은 최대화 되어야 하고, 클래스 내 분산은 최소화시켜 $J(W)가 최대가 되게 만드는 W(선형 분리 벡터)를 구해 클래스를 나눠야 한다.

 

J(W)가 최대가 되기 위해서는 W에 대한 미분값이 0이어야 하며($\frac{dJ(w)}{dw} = 0$)

위 수식을 미분하여 정리하면 다음과 같은 최종 식이 나온다

 

$$W = c X S_{w}^{-1}(m_{1} - m_{2})$$

 

Parametric한 Solution으로는 다음과 같은 식으로 써줄 수 있다.

$w = \sum^{-1}(\mu_{1} - \mu_{2})$ (when $p(x|C_{i}) ~ N(\mu_{i}, \Sigma)$)

 

 

Reference

https://knowable.tistory.com/41

[인공지능] Fisher Discriminant Analysis(선형판별분석)