결국 고유값 문제로 수렴되는 선형판별분석(LDA)

지난 번에 주성분분석(PCA)를 포스팅하면서, 고유값 분해가 어떻게 머신러닝에 활용되는지 알아보았다. 오늘 정리하는 선형판별분석(linear discriminant analysis; LDA)도 결국은 어떤 행렬의 고유값 문제로 귀결된다. 고유값 그거 참 신통방통한 친구다. 그러니 고유값 분해에 대해서 아직 잘 모른다면, 공부하는 것이 좋다. 머신러닝, 딥러닝을 연구하는데 있어서 선형대수학에 대한 이해는 필수적이다. 물론 잘 몰라도 사용할 수는 있겠지만, 제대로 이해하고 사용하는 것과는 천지차이다.  

▶ LDA의 물리적 이해

LDA는 다른 클래스에 속하는 데이터들을 선형으로 분류가 가능하도록 데이터 포인트들을 투영시키는 머신러닝 알고리즘이다. LDA는 PCA와 비교해가면서 이해하는 것이 좋다. PCA와 LDA 모두 둘 다 투영(projection)이라는 기법을 사용하기 때문이다.  

PCA는 데이터들을 어떠한 벡터로 투영시켰을 때, 투영들의 분산이 큰 벡터들을 찾는다. 투영들의 분산이 적게 만드는 벡터들은 제거해줌으로 데이터의 차원을 감소시킨다. 고차원의 데이터를 저차원으로 감소시켜 시각화가 가능하게 하거나 노이즈를 제거하는 것이 PCA의 목적이었다. 

반면 LDA는 데이터를 하나의 선으로 투영시킨다. PCA와 달리 데이터들이 어떤 클래스에 속하는지 알아야 한다. 

LDA는 아래와 같은 두 가지 성질을 가진 벡터를 찾는다.

 

1) 데이터 포인트들을 투영시켰을 때 각 클래스에 속하는 투영들의 평균간의 거리의 합이 최대가 되게 하는 벡터. 다른 말로, 클래스 간(between-class)의 거리가 최대가 되게 하는 벡터. 

2) 데이터 포인트들을 투영시켰을 때 클래스 내의 투영들의 분산이 최소가 되게 하는 벡터. 다른 말로, 클래스 내(within-class)의 분산이 최소가 되게 하는 벡터.

아래 그림을 보면 이게 무슨 말인지 좀 더 이해가 될 것이다. 

 

그림 1. LDA는 클래스 간의 거리가 최대가 되게 하면서, 동시에 클래스 내의 분산이 최소가 되게 하는 벡터를 찾는다.

그림 1과 같이 클래스 내의 분산이 최소가 되게 하고, 클래스 간의 거리가 최대가 되게 하는 벡터를 찾아 데이터 포인트들을 투영시키는 것이 LDA가 하는 일이다. 

▶ LDA의 수학적 이해

이제 LDA가 하는 일을 수식 유도 과정을 통해 살펴보자. 물리적으로 이해한 것이 수학적 이해를 통해 더 깊어질 것이다. 

먼저 수식 유도 과정에 쓰는 기호들을 먼저 정리하고 가겠다. 

: 클래스 수

: 클래스 i 내 샘플의 개수

: 전체 샘플의 개수

: 클래스 i 내 j 번째 샘플

여기서

임을 쉽게 알 수 있다. 

클래스부터 클래스까지의 데이터포인트들을 나열하면 아래와 같을 것이다.

이 데이터 포인트들의 벡터로의 투영을 생각해보자. 여기서 벡터는 우리가 원하는 조건들을 만족시키는 그 벡터다.

이제 이 투영들을 가지고 두 가지를 구할 것이다. 

1) 클래스 간의 거리의 합

2) 각 클래스 내의 분산의 합

클래스 간의 거리의 합은 클수록 좋고, 각 클래스 내의 분산의 합은 작을 수록 좋다는 것이 LDA의 기본 원리이기 때문이다. 

1) 클래스 간의 거리의 합

그러면 먼저 클래스 간의 거리의 합에 대해서 구해보자. 클래스 간의 거리는 각 클래스의 투영들의 평균 간의 거리로 구한다. 클래스 i에 속하는 데이터 포인트들의 투영들의 평균은 아래와 같이 구할 수 있다.

여기서 

는 클래스 i의 데이터 포인트들의 평균을 의미한다. 즉, 투영 전의 데이터 포인트들의 평균이다. 그럼 이제 클래스 평균 간의 거리를 모두 더한다. 만약 클래스가 3개라면 3개 중에 2개를 순서에 상관없이 선택하는 조합과 같으므로 총 개의 거리를 구해서 더해야 한다. 클래스 1과 클래스 2의 거리, 클래스 1과 클래스 3의 거리, 클래스 2와 클래스 3의 거리를 구해서 더해야 한다. 만약 클래스가 L개라면, 개의 거리를 구해서 더해야 한다. 이를 식으로 나타내면, 

 

와 같이 매우 길다. 이것을 시그마를 이용해서 간단히 표현하면, 

로 쓸 수 있다. 이것은 아래와 같이 전개된다.

여기서 는 between-class scatter matrix라고 불리고, 아래와 같이 정리가 가능하다. 좀 길지만 한 줄 한 줄 적어가면서 따라가면 그다지 어렵진 않다. 선형대수학에 대한 지식이 부족하면 그냥 결과만 확인해도 무방하다. 

마지막 줄에서 

는 전체 데이터 포인트들의 평균이다. 왜냐하면, 

 

이기 때문이다. 따라서 이 전체 데이터 포인트의 평균을 의미하는 기호로 놓으면, 

이 된다. 따라서 between-class scatter matrix는 다음과 같이 계속해서 정리된다. 

between-class scatter matrix에 대해 길게 정리했는데, 처음과 끝만 남겨두면 다음과 같다. 

위 식을 잘 살펴보면, 각 클래스의 평균 사이의 거리들의 합은 각 클래스의 평균과 전체 평균간의 거리들의 합과 같다는 뜻임을 알 수 있다(그림2 참고). 

그림 2. between-class scatter matrix의 함의: 각 클래스 평균 사이의 거리들의 합은 각 클래스 평균과 전체 평균간의 거리들의 합과 같다.

2) 각 클래스 내의 분산의 합

이제 두번째로 각 클래스의 투영들의 분산의 합을 구하자. 우선 클래스 i의 투영들의 분산은 다음과 같다. 

따라서 모든 클래스의 투영들의 분산의 합은 아래와 같이 계산된다. 

여기서 는 within-class scatter matrix라고 불린다.

이 식을 잘 살펴보면 즉 각 클래스 내의 데이터포인트들과 클래스의 평균 사이의 거리를 모두 더한 것임을 알 수 있다(그림3 참고).

그림3. within-class scatter matrix의 함의: 각 클래스 내의 데이터포인트들과 각 클래스의 평균 사이의 거리를 모두 더한다.

3) 클래스 간의 거리는 최대로, 클래스 내의 분산은 최소로

클래스 간의 거리의 합과 클래스 내의 분산의 합을 구했으므로 이제 아래와 같은 최적화 문제를 풀면 우리가 원하는 그 벡터를 찾을 수 있다. 그 벡터란 데이터포인트들을 그 벡터 위로 투영시켰을 때 클래스 간의 거리는 멀게 하고, 클래스 내의 분산은 크게 하는 벡터를 의미함을 잊지 말자. 

분자에 클래스 간의 거리가 놓여있고 분모에 클래스 내의 분산이 놓여있다. 이 경우 분자는 클수록 좋은 것이고 분모는 작을 수록 좋은 것이므로 이 분수가 최대가 되게 하는 벡터를 찾으면 되는 것이다. 벡터의 경우 크기는 중요하지 않고 방향만 중요하므로, 분모를 1이 되게 하는 제약 조건을 주어도 무방하다. 즉, 다음과 같이 쓸 수 있다. 

이는 제약 조건이 있는 최적화 문제이므로 라그랑주 승수법에 의해 제약 조건이 없는 최적화 문제로 바꿔줄 수 있다. 라그랑주 승수법은 목적함수와 제약 조건을 새로운 변수 를 이용해 보조방정식을 만든 후에, 모든 변수에 대한 편미분 값이 0이 되는 변수의 해를 찾는 것이다. 라그랑주 승수법에 의해 만들어진 보조방정식은 다음과 같다. 

이 방정식을 두 개의 변수에 대해 각각 편미분한다.  

 

따라서, 위의 최적화 문제는 아래와 같은 일반화된 고유값 문제의 최대 고유값을 찾는 것으로 해결됨을 알 수 있다.

 

결국 PCA와 같이 고유값 문제로 LDA도 수렴되었다. 큰 순서대로 여러 개의 고유값들을 찾는 PCA와 달리, LDA는 단 하나의 가장 큰 고유값을 찾아준다. 

▶ 커널 기반 LDA (KLDA)

KLDA는 말 그대로 커널 기법을 이용해 주어진 데이터 포인트들을 고차원의 특성 공간으로 사상해준 다음에 LDA를 적용하는 것이다. 수학적 유도는 생략한다. 

▶ LDA 활용 데이터 분석 예제

라벨 값을 가진 2차원 데이터 포인트들에 LDA를 활용해서 분류하는 예제를 하나 구현해보겠다. 클래스의 개수는 2개이므로 데이터를 두 개의 그룹으로 분류하는 문제이다. 우선 데이터는 아래와 같이 분포되어 있다.

그림4. 데이터 포인트들

빨간색 클래스(class1)에 속하는 데이터가 4개, 파란색 클래스(class2)에 속하는 데이터가 3개이다. 우리는 LDA를 통해 찾은 선은 그림 5와 같다. 

그림5. 데이터 포인트들과 LDA로 찾아낸 벡터(선). 이 선으로 투영되었을 때 위에서 언급한 두 가지 조건이 만족된다.

이 선 위로 데이터 포인트들을 투영시키면 그림 6과 같다. 

그림6. 데이터 포인트들이 선 위로 투영된 결과.

투영 결과 두 클래스가 잘 분리되어 있고, 동일한 클래스 내의 데이터포인트들은 가까이 모여있음을 확인할 수 있다. 그러면 이제 클래스를 모르는 데이터가 있다고 가정해보자(그림 7).

그림7. 어떤 클래스에 속하는지 모르는 새로운 데이터 포인트(연두색).

새로운 데이터의 투영과 클래스1의 투영들과의 거리, 새로운 데이터의 투영과 클래스2의 투영들과의 거리를 비교하면 어떤 그룹에 속하는지 판단할 수 있다. 물론 이 경우에는 눈으로도 분명히 확인되지만 말이다. 

그림8. 테스트 데이터 포인트가 그 선으로 투영된 모습

그림9. 예측 결과 테스트 데이터 포인트는 class1에 속한다고 판정되었다.

 

이상의 내용을 MATLAB으로 코딩했다. 코드는 아래와 같다. 주석을 상세히 달아놓았다. 

clc, clear, close all

cls1_data = [2.93 6.634; 2.53 7.79; 3.57 5.65; 3.16 5.47]; % class1인 데이터 포인트들

cls2_data = [2.58 4.44; 2.16 6.22; 3.27 3.52]; % class2인 데이터 포인트들

% mean

E_cls1 = mean(cls1_data); % class1 데이터 포인트들의 평균값

E_cls2 = mean(cls2_data); % class2 데이터 포인트들의 평균값

E_all = mean([cls1_data; cls2_data]); % 전체 데이터 포인트들의 평균값

% 데이터 분포 그림으로 확인

plot(cls1_data(:, 1), cls1_data(:, 2), '*r'); % class1인 데이터 포인트들

hold on 

plot(cls2_data(:, 1), cls2_data(:, 2), '*b'); % class2인 데이터 포인트들

axis([0 10 0 10]);

% between-class scatter matrix

x1 = E_cls1 - E_all;

x2 = E_cls2 - E_all;

Sb = (4/7)*x1'*x1 + (3/7)*x2'*x2;

% within-class scatter matrix

y1 = 0;

for i = 1:4

   y1 = y1 + (cls1_data(i, :) - E_cls1)'*(cls1_data(i, :) - E_cls1); 

end

y2 = 0;

for i = 1:3

   y2 = y2 + (cls2_data(i, :) - E_cls2)'*(cls2_data(i, :) - E_cls2); 

end

Sw = (4/7)*y1 + (3/7)*y2;

% 데이터포인트들을 투영시킬 벡터 찾기

[eig_vec, eig_val] = eig(inv(Sw)*Sb); % (Sw^-1)Sb 행렬의 고유값과 고유벡터 구하기

[largest_eig_val, index] = max(max(eig_val)); % 가장 큰 고유값 찾기

vector = eig_vec(:, index); % 가장 큰 고유값에 대응하는 고유벡터, 우리가 찾는 바로 그 벡터(방향)!

% 그 벡터로 데이터포인트 투영

new_cls1_data = cls1_data*vector;

new_cls2_data = cls2_data*vector;

% 그래프에 그 벡터 그리기

a = vector(2)/vector(1); % 그 벡터의 기울기 

plot([0, 10], [0, 10*a], '-g'); % 그 벡터 그리기 (원점에서부터 x=10에 해당하는 y값까지만 그렸음) 

% 데이터포인트들이 투영된 모습 그리기

for i = 1:4

    new_x = (cls1_data(i, 1) + a*cls1_data(i, 2))/(a^2 + 1);

    new_y = a*new_x;

    plot(new_x, new_y, '*r'); % class 1 데이터포인트들이 그 벡터에 투영된 모습

    plot([cls1_data(i, 1), new_x], [cls1_data(i, 2), new_y], '--k');

end

for i = 1:3

    new_x = (cls2_data(i, 1) + a*cls2_data(i, 2))/(a^2 + 1);

    new_y = a*new_x;

    plot(new_x, new_y, '*b'); % class 2 데이터포인트들이 그 벡터에 투영된 모습

    plot([cls2_data(i, 1), new_x], [cls2_data(i, 2), new_y], '--k');

end

% 새로운 데이터 포인트의 클래스 예측하기

test_data = [4.81, 3.46];

plot(test_data(1), test_data(2), '*g'); % 테스트 데이터 포인트 그리기

result = test_data*vector; % 그 벡터로 테스트 데이터 포인트 투영

projected_test_data_x = (test_data(1) + a*test_data(2))/(a^2 + 1);

projected_test_data_y = a*projected_test_data_x;

plot(projected_test_data_x, projected_test_data_y, '*g'); % 그 벡터로 테스트 데이터 포인트가 투영된 모습

plot([test_data(1), projected_test_data_x], [test_data(2), projected_test_data_y], '--k');

temp1 = new_cls1_data - result; % 클래스1에 속하는 데이터의 투영들과 테스트 데이터의 투영의 차이

temp2 = new_cls2_data - result; % 클래스2에 속하는 데이터의 투영들과 테스트 데이터의 투영의 차이

if (min(abs(temp1)) < min(abs(temp2)))

    prediction = 'class1(red)'

else

    prediction = 'class2(blue)'

end

▶ 정리

LDA도 PCA와 유사하게 고유값 분해와 투영이라는 방식을 활용한다. PCA는 데이터를 좀 더 잘 이해하기 위해 데이터의 분산이 넓어지는 벡터들로 투영시켜주는 것이라면, LDA는 데이터를 클래스에 따라 분류하기 위해 클래스간의 거리는 멀게 해주고 클래스내의 분산은 작게 해주는 벡터로 투영시켜주는 것이다. 

포스팅을 하면서 저 스스로 이해가 한결 더 깊어짐을 느낍니다. 그러나 여전히 부족함이 있는 글이라 생각됩니다. 제 설명이 잘못된 부분이 있으면 피드백 해주시면 감사하겠습니다. 한 수 가르쳐주세요! 또한 조금이나마 이 글이 도움이 되셨다면 댓글이나 공감으로 격려해주시면 감사하겠습니다.^^ 

<참고자료>

[1] http://www.cnblogs.com/pinard/p/6244265.html, LDA에 대한 중국 블로그의 설명

[2] https://blog.naver.com/macchiholic/221323294567, 점과 직선 사이의 거리 구하는 공식