Fisher 판별 알고리즘

관련 논문

ip10-ayrun[1].pdf

 

 Fisher의 분산분석 개념 이용

선형 판별 분석법은 특징 벡터 차원의 축소 기법 중 하나이다. 간단히 정의하면 클래스간 분산(between-class scatter)과 클래스내 분산(within-class scatter)의 비율을 최대화 하는 방식이다.

집단을 나누는데 좋은 변수란 그 변수에 의해 집단이 소집단으로 나누어 졌을때 그 소집단 자체는 가능하면 동질적이야 하고 소 집단 간에는 가능하면 이질적이어야 합니다.

즉 다른 말로 하면 소집단내의 분산(WSS)은 작아야 하고 소집단 간의 분산(BSS)은 가능하면 커야 합니다. 그래서 Fisher의 아이디어는 (소집단간의 변동/전체 변동)=(BSS/TSS)를 최대로 만들어 주는 집단의 절단선을 찾는 것입니다.

(1) 선형판별분석
- LDA, Linear Discriminant Analysis
➟ 클래스간 분산(between-class scatter)과 클래스내 분산(within-class scatter)의 비율을
최대화하는 방식으로 데이터에 대한 특징 벡터의 차원을 축소하는 방법

2진 분류에 적용된 LDA

 각 클래스의 평균점(중심) 이 멀면 멀수록 클래스간 분류가 쉽다.  표본 x,y의 평균벡터를 각각μ1, μ2 라고 하자 이제 사영된 데이터들의 중심간의 거리를 목적함수로 ㅎ선택하면 다음과 같다.

	J(W) = |μ1-μ2| = |W^t* (μ1-μ2)|

이 목적함수는 사영 벡터 중심간의 거리가 클래스 간의 분산을 전혀 고려하고 있지 않으므로 좋은 척도라고 할 수 없다. 즉 클래스내의 분산이 커서 서로 겹칠 수도 있다는 것이다. 이러한 문제를 보완하여 피셔(Fisher)는 클래스내 분산이라는 척도로 평균 간의 차이를 정규화하여 함수로 표현하고 이 목적함수를 최대화 하는 방법을 제안하였다.

(S1^2+s2^2) 을 사영표본의 클래스 내 분산이라고 한다.  동일한 클래스의 표본들은 인접하게 사영을 취하고, 동시에 클래스 간의 사영은 중심이 가능한 멀리 떨어지게 하는 변환행렬(W)을 찾는 것이다.

	J(W) =  |μ1-μ2| ^2/(S1^2+s2^2)

J(W)를 최대화하는 변환행렬W*은 어떻게 찾을 것인가...

 

각각의 분산을 S1,S2로 놓고 S1+S2=Sw 라고 할때 행렬 S2를 클래스내 분샌행렬이라하고, 표본 Sw는 공분산 행렬에 비례한다.

분산행렬이 포함된 함수로 표현하면

	S1^2+S2^2 = (W^t)(Sw)W

마찬가지로 다음과 같이 표현할 수도 있다.

	|μ1-μ2| ^2 =( W^t)(Sb)W

 Sb를 클래스간 분산이라 부르며, 두벡터간의 외적이므로 이행렬의 랭크는 1이 된다. 최종 피셔의 목적함수를 Sw와 Sb항으로 간략히 정의할 수 있다.

 

	J(W) = ( W^t)(Sb)W / (W^t)(Sw)W

기울기가 0인 지접을 찾기위해(최대값을 찾기위해 ) 미분하여 0으로 놓는다.

Sw^-1SbW= JW 의 해법으로 W는 Sw^-1Sb의 고유벡터가 되므로  W*=Sw^-1(μ1-μ2)가 된다. W는 고유벡터 J는 고유값.

 또한 최대화 정리로 분자를 클래스간 평균의 차인 상수로 취급하면, 다음과 같은 최적화 변환행렬 W*를 구할 수 있다.