Fisher's linear discriminant (FLD) 는 데이터를 여러 변수들의 선형결합으로 표현하였을 때 서로 다른 그룹을 잘 구분할 수 있게 해 주는 coefficient 를 찾는 방법이다. 그림으로 보자면 다음과 같다.
위는 그림으로 그려서 보이기 편하라고 2개의 변수만을 사용하여 나타낸 것인데, 저렇게 두 그룹을 잘 구분할 수 있는 직선의 방정식을 찾는 방법이 Fisher's linear discriminant 를 이용한 방법이다. 위 직선의 방정식에 필요한 상수는 closed-form 으로 정확히 구해진다. 원리를 알아 보고, matlab 으로 테스트도 해보고, C++로 구현해서 써먹어 보자. (오늘은 원리와 matlab 으로의 테스트까지만. 구현은 내일 해보자)
직관적으로 생각할 수 있는 것은, D-차원의 데이터 집합 X := { xi } 를 선형결합에 의하여 직선으로 projection 시켰을 때 서로 다른 class lable 을 갖고 있는 두 그룹이 '직선 위'에서 구분이 잘 되어야 한다는 것이다. 즉, 이것은 다시, d-차원에서 직선을 하나 그을 것인데 어떻게 그어야 그룹이 잘 구분이 되는가, 하는 문제이다. 위의 그림에서 그려진 저 직선을 어떻게 찾을까 하는 문제. projection 이 될 (a line on which data will be projected) 직선은 저 위처럼 그룹을 잘 구분시켜 주는 직선에 대한 orthogornal vector 가 된다, 사실은. 그림으로 보자면 다음과 같다1.
최종적인 계산 결과로 나오는 vector 는 canonical direction 으로 표시된 저 벡터이다. 즉, data들을 canonical direction 을 갖는 벡터로 projection 시키면 그 위에서 두 그룹의 데이터가 적게 겹치되 된다는 것이다2. 그렇다면 저런 canonical direction 을 어떻게 찾을 수 있을까? projection 시켰다는 가정 하에, 어떤 특성을 갖도록 projection 되어야 하는가를 생각해 보자.
만약 projection이 그림의 projection1 과 같이 되었다면 두 그룹 사이에 겹치는 것이 많이 있으므로 좋지 않다. 반면 projection 2 처럼 된다면 분리가 잘 되고 있다. projection 을 시켰을 때 바로 저렇게 될 수 있는 그러한 vector를 찾으면 되겠다. 그렇다면 위의 projection 1보다 projection 2 가 '좋다'라고 말할 때, 어떤 수치를 기준으로 그런 말을 할 수 있을까? 이 때 Fisher는 다음과 같은 아이디어를 사용한다. 두 그룹의 center of mass 는 멀리 떨어지되, 각 그룹 내의 variance 는 작을 것. 다시 말해, 두 그룹이 잘 분리된다는 것은, 두 그룹의 '중점'의 거리가 멀고, 각각의 그룹 내의 요소들이 될 수 있으면 가까이 몰려 있어서 variance 가 작아야 한다는 것. 만약 두 그룹의 중점이 멀리만 한다면 두 그룹에 큰 수를 곱하면 중점은 무조건 멀리 떨어지게 될 뿐 두 데이터는 여전히 겹치게 된다.
위의 projection 2와 projection 3은 두 그룹의 중심거리는 같지만 projection 2가 각 그룹의 분산이 projection 3보다 작아서 잘 분리가 되는 것을 알 수 있다. 이렇게, 우리가 찾아야 할 것은 projection 시켰을 때 다음의 두 조건을 만족시킬 수 있는 직선을 찾는 것이다.
위와 같은 아이디어를 수학적으로 표현하면 다음과 같다.
각각의 데이터 xi는 다음과 같이 d개의 벡터 공간에 있는 요소라 하고, weight vector w를 이용하여 projection 시킨 값을 y 라 하자.
(식 3에서 알 수 있듯이 y는 scalar다, 직선으로 projection 되었으니 당연히)
위와 같은 상황에서, 저 위의 두 조건을 모두 고려할 수 있는 수치로 Fisher는 다음과 같은 수치를 고안한다. 우선 각 그룹의 '중심'은 단순히 center of mass와 같은 형태를 띄도록 다음과 같이 사용한다.
이 때, C1과 C2 는 각각 그룹 1 과 그룹 2의 원소의 집합이며, N1 과 N2 는 C1과 C2 각각에 속해 있는 원소의 개수이다. 위의 m1 과 m2 는 원래 space 에서의 중심인데, 위의 식 5 를 이용하여 이 점들을 w 를 이용하여 projection 시키면
이 된다. 따라서 중심의 거리는 다음이 되고(bold체로 된 m 은 원래 공간에서의 중심이고 bold 체가 아닌 m은 projection 된 선 위에서의 중심이다),
그 다음으로는 projection 된 선 위에서 각 그룹의 분산(within-class variance)인데, 우리가 일반적으로 다루는 1차원 공간에서와 정확히 같기 때문에 다음과 같이 정의해도 무리가 없다.
그룹 2개의 분산이 모두 작으면 좋은 것이니까, 전체 그룹내분산 (total within-class variance)는 각 그룹의 그룹내분산의 합으로 정의한다. 이제, 가장 최종적인 Fisher criterion 이 만들어 졌다.
위 식은 다음과 같은 과정에 의하여 식 24처럼 간단히 표현할 수 있다.
약간 tricky한 곳은 17에서 18로 넘어 가는 곳과 21에서 22 으로 넘어 가는 곳인데, wT(m2-m1)은 scalar 이기 때문에 그 자신과 transpose 시킨 값이 같고, 따라서 위처럼 등식이 성립한다. 이제, 위의 식 24에서 J(w) 의 값을 최대화시키는, 바로 그런 w 를 찾으면 되는 것이다. 위의 식 24 를 w 에 대해서 미분해서 구해 보면 J(w) 는 다음과 같은 조건에서 최대값을 갖는다.
위의 식 27 에서 (wTSBw) 와 (wTSWw) 는 scalar 이기 때문에 r 로 놓으면 다음과 같은 최종식을 얻을 수 있다.
아... 멋진 식이 얻어 졌다. 위에 나온 수식에 대한 latex 코드는 아래에 있다3.
자, 위에서 살펴 본 원리를 matlab 으로 테스트 해보자. m 파일은 다음과 같다. 멋진 28번 식에서 알 수 있듯이 m 파일이 매우 짧다.
m 파일.
m 파일을 여기서 설명하지는 않고 - 다음에 올릴 실제 구현에 관한 글에서 위 m 파일을 설명한다. matlab에서의 matrix 다루는 방식이 위의 수식에서 간주하는 것과 좀 달라서 위 m 파일은 약간 복잡할 수 있다 - , 위 m 파일을 실행시키면 다음과 같은 그림 두 개를 얻을 수 있다.
위의 그림은 2차원에서 테스트 한 예이고, 그려진 vector 는 위의 식 29 번으로 구한 w 에 orthogonal 한 vector 이다. 시작점으로는 m 파일의 [c] 로 된 변수에서 보듯이 두 그룹 모두에 대하여 center를 사용했다. 실제로 projection 된 데이터에 대한 빈도를 histogram 으로 확인해 보면 아래쪽 그림과 같음을 알 수 있다. 완벽히 분리될 수 없는 데이터인만큼 어느 정도 겹치는 부분이 있긴 하지만 분리가 어느 정도 되도록 잘 projection 된 것을 확인할 수 있다.
오늘은 여기까지만. 실제로 C++ 로 구현하는 것은 내일 해보자.
위는 그림으로 그려서 보이기 편하라고 2개의 변수만을 사용하여 나타낸 것인데, 저렇게 두 그룹을 잘 구분할 수 있는 직선의 방정식을 찾는 방법이 Fisher's linear discriminant 를 이용한 방법이다. 위 직선의 방정식에 필요한 상수는 closed-form 으로 정확히 구해진다. 원리를 알아 보고, matlab 으로 테스트도 해보고, C++로 구현해서 써먹어 보자. (오늘은 원리와 matlab 으로의 테스트까지만. 구현은 내일 해보자)
직관적으로 생각할 수 있는 것은, D-차원의 데이터 집합 X := { xi } 를 선형결합에 의하여 직선으로 projection 시켰을 때 서로 다른 class lable 을 갖고 있는 두 그룹이 '직선 위'에서 구분이 잘 되어야 한다는 것이다. 즉, 이것은 다시, d-차원에서 직선을 하나 그을 것인데 어떻게 그어야 그룹이 잘 구분이 되는가, 하는 문제이다. 위의 그림에서 그려진 저 직선을 어떻게 찾을까 하는 문제. projection 이 될 (a line on which data will be projected) 직선은 저 위처럼 그룹을 잘 구분시켜 주는 직선에 대한 orthogornal vector 가 된다, 사실은. 그림으로 보자면 다음과 같다1.
최종적인 계산 결과로 나오는 vector 는 canonical direction 으로 표시된 저 벡터이다. 즉, data들을 canonical direction 을 갖는 벡터로 projection 시키면 그 위에서 두 그룹의 데이터가 적게 겹치되 된다는 것이다2. 그렇다면 저런 canonical direction 을 어떻게 찾을 수 있을까? projection 시켰다는 가정 하에, 어떤 특성을 갖도록 projection 되어야 하는가를 생각해 보자.
만약 projection이 그림의 projection1 과 같이 되었다면 두 그룹 사이에 겹치는 것이 많이 있으므로 좋지 않다. 반면 projection 2 처럼 된다면 분리가 잘 되고 있다. projection 을 시켰을 때 바로 저렇게 될 수 있는 그러한 vector를 찾으면 되겠다. 그렇다면 위의 projection 1보다 projection 2 가 '좋다'라고 말할 때, 어떤 수치를 기준으로 그런 말을 할 수 있을까? 이 때 Fisher는 다음과 같은 아이디어를 사용한다. 두 그룹의 center of mass 는 멀리 떨어지되, 각 그룹 내의 variance 는 작을 것. 다시 말해, 두 그룹이 잘 분리된다는 것은, 두 그룹의 '중점'의 거리가 멀고, 각각의 그룹 내의 요소들이 될 수 있으면 가까이 몰려 있어서 variance 가 작아야 한다는 것. 만약 두 그룹의 중점이 멀리만 한다면 두 그룹에 큰 수를 곱하면 중점은 무조건 멀리 떨어지게 될 뿐 두 데이터는 여전히 겹치게 된다.
위의 projection 2와 projection 3은 두 그룹의 중심거리는 같지만 projection 2가 각 그룹의 분산이 projection 3보다 작아서 잘 분리가 되는 것을 알 수 있다. 이렇게, 우리가 찾아야 할 것은 projection 시켰을 때 다음의 두 조건을 만족시킬 수 있는 직선을 찾는 것이다.
1. 두 그룹의 중심 거리가 멀어야 한다.
2. 각 그룹의 분산이 작아야 한다.
2. 각 그룹의 분산이 작아야 한다.
위와 같은 아이디어를 수학적으로 표현하면 다음과 같다.
각각의 데이터 xi는 다음과 같이 d개의 벡터 공간에 있는 요소라 하고, weight vector w를 이용하여 projection 시킨 값을 y 라 하자.
(식 3에서 알 수 있듯이 y는 scalar다, 직선으로 projection 되었으니 당연히)
위와 같은 상황에서, 저 위의 두 조건을 모두 고려할 수 있는 수치로 Fisher는 다음과 같은 수치를 고안한다. 우선 각 그룹의 '중심'은 단순히 center of mass와 같은 형태를 띄도록 다음과 같이 사용한다.
이 때, C1과 C2 는 각각 그룹 1 과 그룹 2의 원소의 집합이며, N1 과 N2 는 C1과 C2 각각에 속해 있는 원소의 개수이다. 위의 m1 과 m2 는 원래 space 에서의 중심인데, 위의 식 5 를 이용하여 이 점들을 w 를 이용하여 projection 시키면
이 된다. 따라서 중심의 거리는 다음이 되고(bold체로 된 m 은 원래 공간에서의 중심이고 bold 체가 아닌 m은 projection 된 선 위에서의 중심이다),
그 다음으로는 projection 된 선 위에서 각 그룹의 분산(within-class variance)인데, 우리가 일반적으로 다루는 1차원 공간에서와 정확히 같기 때문에 다음과 같이 정의해도 무리가 없다.
그룹 2개의 분산이 모두 작으면 좋은 것이니까, 전체 그룹내분산 (total within-class variance)는 각 그룹의 그룹내분산의 합으로 정의한다. 이제, 가장 최종적인 Fisher criterion 이 만들어 졌다.
위 식은 다음과 같은 과정에 의하여 식 24처럼 간단히 표현할 수 있다.
약간 tricky한 곳은 17에서 18로 넘어 가는 곳과 21에서 22 으로 넘어 가는 곳인데, wT(m2-m1)은 scalar 이기 때문에 그 자신과 transpose 시킨 값이 같고, 따라서 위처럼 등식이 성립한다. 이제, 위의 식 24에서 J(w) 의 값을 최대화시키는, 바로 그런 w 를 찾으면 되는 것이다. 위의 식 24 를 w 에 대해서 미분해서 구해 보면 J(w) 는 다음과 같은 조건에서 최대값을 갖는다.
위의 식 27 에서 (wTSBw) 와 (wTSWw) 는 scalar 이기 때문에 r 로 놓으면 다음과 같은 최종식을 얻을 수 있다.
아... 멋진 식이 얻어 졌다. 위에 나온 수식에 대한 latex 코드는 아래에 있다3.
자, 위에서 살펴 본 원리를 matlab 으로 테스트 해보자. m 파일은 다음과 같다. 멋진 28번 식에서 알 수 있듯이 m 파일이 매우 짧다.
% Fisher's linear discriminant.
% : xi is column vector of which element is test metric.
% Therefore size of row is the number of test metrics.
% Number of column is the number of data sets.
x1 = rand(2, 30) + 0.75.*ones(2,30); %[d1(:,c1) d1(:,c2)]';
x2 = rand(2, 30) + 0.3 .*ones(2,30); %[d2(:,c1) d2(:,c2)]';
m1 = mean(x1')';
m2 = mean(x2')';
m = m1 + m2;
Sw1 = zeros(size(x1, 1), size(x1,1));
Sw2 = zeros(size(x1, 1), size(x1,1));
for i = 1:size(x1,2)
Sw1 = Sw1 + (x1(:,i)-m1)*(x1(:,i)-m1)';
end
for i = 1:size(x2,2)
Sw2 = Sw2 + (x2(:,i)-m2)*(x2(:,i)-m2)';
end
Sw = Sw1 + Sw2;
w = Sw^(-1)*(m2-m1);
scatter(x1(1,:), x1(2,:), 10, 'ro');
hold on;
scatter(x2(1,:), x2(2,:), 10,'bo');
c = 0.5.*m;
quiver(c(1,1), c(2,1), 1, -w(1,1)/w(2,1));
quiver(c(1,1), c(2,1), -1, w(1,1)/w(2,1));
%quiver(w(1,1),w(2,1), 0.5)
hold off;
figure;
y1 = x1'*w;
y2 = x2'*w;
hist([y1 y2])
% : xi is column vector of which element is test metric.
% Therefore size of row is the number of test metrics.
% Number of column is the number of data sets.
x1 = rand(2, 30) + 0.75.*ones(2,30); %[d1(:,c1) d1(:,c2)]';
x2 = rand(2, 30) + 0.3 .*ones(2,30); %[d2(:,c1) d2(:,c2)]';
m1 = mean(x1')';
m2 = mean(x2')';
m = m1 + m2;
Sw1 = zeros(size(x1, 1), size(x1,1));
Sw2 = zeros(size(x1, 1), size(x1,1));
for i = 1:size(x1,2)
Sw1 = Sw1 + (x1(:,i)-m1)*(x1(:,i)-m1)';
end
for i = 1:size(x2,2)
Sw2 = Sw2 + (x2(:,i)-m2)*(x2(:,i)-m2)';
end
Sw = Sw1 + Sw2;
w = Sw^(-1)*(m2-m1);
scatter(x1(1,:), x1(2,:), 10, 'ro');
hold on;
scatter(x2(1,:), x2(2,:), 10,'bo');
c = 0.5.*m;
quiver(c(1,1), c(2,1), 1, -w(1,1)/w(2,1));
quiver(c(1,1), c(2,1), -1, w(1,1)/w(2,1));
%quiver(w(1,1),w(2,1), 0.5)
hold off;
figure;
y1 = x1'*w;
y2 = x2'*w;
hist([y1 y2])
m 파일.
FLDA.mm 파일을 여기서 설명하지는 않고 - 다음에 올릴 실제 구현에 관한 글에서 위 m 파일을 설명한다. matlab에서의 matrix 다루는 방식이 위의 수식에서 간주하는 것과 좀 달라서 위 m 파일은 약간 복잡할 수 있다 - , 위 m 파일을 실행시키면 다음과 같은 그림 두 개를 얻을 수 있다.
위의 그림은 2차원에서 테스트 한 예이고, 그려진 vector 는 위의 식 29 번으로 구한 w 에 orthogonal 한 vector 이다. 시작점으로는 m 파일의 [c] 로 된 변수에서 보듯이 두 그룹 모두에 대하여 center를 사용했다. 실제로 projection 된 데이터에 대한 빈도를 histogram 으로 확인해 보면 아래쪽 그림과 같음을 알 수 있다. 완벽히 분리될 수 없는 데이터인만큼 어느 정도 겹치는 부분이 있긴 하지만 분리가 어느 정도 되도록 잘 projection 된 것을 확인할 수 있다.
오늘은 여기까지만. 실제로 C++ 로 구현하는 것은 내일 해보자.
- 이 곳에서는 그림으로 표현하기 쉽기 때문에 주로 2차원을 사용할 것이다. 즉 두 종류의 검사(parameter)만을 그림으로 표현한다. 하지만, 우리는, 일반성을 잃지 않고(without loss of generality) N 차원으로 확장시킬 수 있음을 안다. :-) [본문으로]
- 저 그림은 원래 matlab 으로 그렸는데, quiver 함수로 그린 하늘색/빨강색 vector 는 계산된 canonical vector에 대한 orthogornal vector를 손으로 계산해 얻은 값이다. 이런 함수가 있는지 없는지... [본문으로]
- 초큼... 지저분하다. 그런데, 비록 Texmaker 를 사용하긴 하지만 GUI 를 거의 안쓰고 죄다 손으로 쳤다는 거... 가끔은 vi로도 하니까... 내가 이건 좀 불편해서 F5 에 pdf 만들도록 mapping 해서 쓰긴 했었지만, 어쨌는 난 약간은 구식?을 좋아하는 듯. ㅋㅋ [본문으로]
'컴퓨터 > 수학이랑' 카테고리의 다른 글
| 상관계수2 (0) | 2011.08.30 |
|---|---|
| Fisher's linear discriminant 구현 (4) | 2010.12.03 |
| 통계 분석 - 평균 비교에 대하여 (0) | 2010.10.21 |
| 엑셀에서 z-score로 p-value 계산하기 (1) | 2010.10.12 |
| 알고리즘 관련 글의 병목 현상에 대하여 (0) | 2010.08.29 |
