선형판별분석 (Linear Discriminant Analysis, LDA)

LDA는 전통적인 선형 학습법이며, 이진 분류 문제에서 Ronald A. Fisher가 가장 먼저 사용하였기 때문에 Fisher's discriminant analysis (FDA)라고도 불린다. 아이디어는 간단하지만 강력하다. 훈련 데이터를 어떠한 직선 위에 투영시킨 점을 다른 클래스끼리는 최대한 멀게 위치하게 하고, 동일 클래스에 속한 샘플들끼리는 최대한 가깝게 위치하도록 하는 것이다. ([그림 1] 참조)

같은 클래스끼리는 가깝게, 다른 클래스끼리는 멀게

이진 분류 문제에서 각 클래스 내 데이터 집합을 Xi\mathcal{X}_i, i0,1i \in {0, 1}이라 하고 각 데이터 집합의 평균벡터와 공분산행렬을 각각 μi\bm{\mu}_i, Σi\bm{\Sigma}_i라 하자. 훈련 데이터를 어떠한 벡터 w\mathbf{w}에 projection하여 y=wTxy=\mathbf{w}^T\mathbf{x}를 얻었다면, 두 클래스의 공분산은 wTΣ0w\mathbf{w}^T\bm{\Sigma}_0\mathbf{w}wTΣ1w\mathbf{w}^T\bm{\Sigma}_1\mathbf{w}이 되고, 각 클래스의 중심점은 wTμi\mathbf{w}^T\bm{\mu}_i로 표현할 수 있다.

[그림 1] LDA의 개념 (source: [1] 재구성)

두 클래스를 잘 분류하려면 벡터 w\mathbf{w}에 projection된 점들이 동일 클래스끼리는 최대한 가까이 분포하여야 하고, 다른 클래스 간에는 가능한 멀리 떨어져야 한다. 즉, wTΣ0w+wTΣ1w\mathbf{w}^T\bm{\Sigma}_0\mathbf{w}+\mathbf{w}^T\bm{\Sigma}_1\mathbf{w}는 최대한 작게하면서 동시에 wTμ0wTμ12\|\mathbf{w}^T\bm{\mu}_0 - \mathbf{w}^T\bm{\mu}_1\|^2은 크게하는 벡터 w\mathbf{w}를 찾으면 두 클래스를 잘 분류할 수 있을 것이다.

wTΣ0w+wTΣ1w\mathbf{w}^T\bm{\Sigma}_0\mathbf{w}+\mathbf{w}^T\bm{\Sigma}_1\mathbf{w}는 최대한 작게
wTμ0wTμ12\|\mathbf{w}^T\bm{\mu}_0 - \mathbf{w}^T\bm{\mu}_1\|^2은 최대한 크게

따라서 다음과 같은 목적함수를 최대화하는 문제를 생각해볼 수 있다.

J=wTμ0wTμ12wT(Σ0+Σ1)w=wT(μ0μ1)(μ0μ1)TwwT(Σ0+Σ1)w=wTSbwwTSww(1)\tag{1} \begin{aligned} J &= \frac{\| \mathbf{w}^T\bm{\mu}_0 - \mathbf{w}^T\bm{\mu}_1 \|^2}{\mathbf{w}^T(\bm{\Sigma}_0+\bm{\Sigma}_1)\mathbf{w}} \\ &= \frac{\mathbf{w}^T(\bm{\mu}_0-\bm{\mu}_1)(\bm{\mu}_0-\bm{\mu}_1)^T\mathbf{w}}{\mathbf{w}^T(\bm{\Sigma}_0+\bm{\Sigma}_1)\mathbf{w}} \\ &= \frac{\mathbf{w}^T\mathbf{S}_b\mathbf{w}}{\mathbf{w}^T \mathbf{S}_w \mathbf{w}} \end{aligned}

여기서 Sw\mathbf{S}_wSb\mathbf{S}_b는 각각 집단 내 산포행렬(within-class scatter matrix)집단 간 산포행렬(between-class scatter matrix) 로 모두 대칭행렬이며 다음과 같이 정의된다.

Sw=Σ0+Σ1=xX0(xμ0)(xμ0)T+xX1(xμ1)(xμ1)TSb=(μ0μ1)(μ0μ1)T(2)\tag{2} \begin{aligned} \mathbf{S}_w &= \bm{\Sigma}_0 + \bm{\Sigma}_1 \\ &= \sum_{\mathbf{x} \in \mathcal{X}_0}(\mathbf{x} - \bm{\mu}_0)(\mathbf{x} - \bm{\mu}_0)^T + \sum_{\mathbf{x} \in \mathcal{X}_1}(\mathbf{x} - \bm{\mu}_1)(\mathbf{x} - \bm{\mu}_1)^T\\ \mathbf{S}_b &= (\bm{\mu}_0-\bm{\mu}_1)(\bm{\mu}_0-\bm{\mu}_1)^T \end{aligned}

식 (1)은 분자와 분모 모두 w\mathbf{w}의 이차항이다. 따라서 식 (1)의 해는 w\mathbf{w}의 크기와는 무관하며 벡터의 방향과 관련이 있다. 즉, wTSww=1\mathbf{w}^T \mathbf{S}_w \mathbf{w}=1로 가정하여 최적화 문제를 다음과 같이 다시 쓸 수 있다.

maxwwTSbw   s.t.  wTSww=1(3)\tag{3} \max_{\mathbf{w}} \mathbf{w}^T\mathbf{S}_b\mathbf{w} \ \ \ s.t. \ \ \mathbf{w}^T\mathbf{S}_w\mathbf{w}=1

Contrained optimization 문제를 풀기 위해 Lagrange multiplier 방법을 사용하여 다음과 같이 unconstrained optimization 문제로 치환한다.

maxwwTSbwλ(wTSww1)(4)\tag{4} \max_{\mathbf{w}} \mathbf{w}^T\mathbf{S}_b\mathbf{w} - \lambda(\mathbf{w}^T\mathbf{S}_w\mathbf{w}-1)

식 (4)를 w\mathbf{w}에 대하여 미분한 결과가 영벡터(zero vector)가 되도록 식을 정리하면 다음과 같다 1.

Sbw=λSww(5)\tag{5} \mathbf{S}_b\mathbf{w} = \lambda \mathbf{S}_w \mathbf{w}

여기서 식 (2)에 의해 Sbw=(μ0μ1)×c\mathbf{S}_b\mathbf{w}=(\bm{\mu}_0-\bm{\mu}_1) \times c가 된다. 여기서 ccw\mathbf{w}에 의해 결정되는 스칼라인데, 우리는 w\mathbf{w}의 크기는 관심이 없으므로 c=λc=\lambda로 가정할 수 있다. 이 결과를 식 (5)에 다시 대입하면 다음고 같이 w\mathbf{w}의 해를 구할 수 있다.

w=Sw1(μ0μ1)(6)\tag{6} \mathbf{w} = \mathbf{S}_w^{-1}(\bm{\mu}_0-\bm{\mu}_1)

Sw\mathbf{S}_w의 역행렬을 구하는 과정은 수치적으로 불안정하다. 따라서 의사역행렬(pseudo inverse matrix)을 구하기 위해 SVD를 이용할 수도 있다.

LDA의 기본 개념은 PCA와 유사하지만 PCA는 데이터의 분산이 최대한 축과 이와 직교하는 축들을 찾는 반면, LDA는 클래스를 최적으로 구분할 수 있는 특성 부분 공간을 찾는 것이다 [2]. 그리고 PCA는 비지도 학습인 반면, LDA는 지도 학습이다.

파이썬 예제

다음 코드는 LDA 실습을 위한 파이썬 코드이다. 사실 알고리즘을 명확히 이해하려면 모든 수식을 직접 짜보아야 하는데, 대학원 졸업한지도 너무 오래되었고... 나이가 들어서인지 좀 귀찮다.ㅜ

아래 코드를 실행해보면 다음과 같은 이진 분류 데이터에 LDA를 적용한다. (데이터는 랜덤하게 생성되므로 예제와 다를 수 있다.)

위 그림에서 학습 데이터는 2차원 평면에 분포해있지만 yy-축 값의 범위는 두 클래스간 차이점을 찾기 어렵고, xx-축은 두 클래스가 밀집되어 있는 위치가 다르다. 따라서 LDA를 적용해보면 위 그림에서의 빨간색 실선으로 데이터들을 투영시키면 아래 그림과 같은 히스토그램을 얻을 수 있다. 따라서 1차원 정보만을 이용하여 두 클래스의 구분할 수 있게 된다.

from sklearn.datasets import make_classification
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
import matplotlib.pyplot as plt
import numpy as np

# generate example data
x, y = make_classification(n_samples=500, n_features=2, n_informative=1, n_redundant=0, n_clusters_per_class=1, n_classes=2, random_state=42)

# split data set into train and test data set
train_input, test_input, train_target, test_target = train_test_split(x, y, random_state=42)

# standardization
scaler = StandardScaler()
scaler.fit(train_input)
train_scaled = scaler.transform(train_input)
test_scaled = scaler.transform(test_input)

# LDA
clf = LinearDiscriminantAnalysis()
clf.fit(train_scaled, train_target)
train_lda = clf.transform(train_scaled)
test_lda = clf.transform(test_input)

# dimension of lda output (reduced to 1 dim.)
print(train_lda.shape, test_lda.shape)


# visualization
slope = clf.coef_[0,1] / clf.coef_[0,0]
t = np.arange(np.min(x[:,0]), np.max(x[:,0]), 0.1)

label0 = y==0
label1 = y==1
# plt.subplot(1,3,1)
plt.plot(t, slope*t, color='red')
plt.scatter(x[label0,0], x[label0,1])
plt.scatter(x[label1,0], x[label1,1])
plt.xlim(np.min(x[:,0])-0.1, np.max(x[:,0])+0.1)
plt.ylim(np.min(x[:,1])-0.1, np.max(x[:,1])+0.1)
plt.xlabel('feature #1')
plt.ylabel('feature #2')
plt.legend(labels=['w', 'class 0', 'class 1'])
plt.title('before transform')

plt.figure()
plt.hist(train_lda[train_target==0], 100)
plt.hist(train_lda[train_target==1], 100)
plt.title('train data')

plt.figure()
plt.hist(test_lda[test_target==0], 100)
plt.hist(test_lda[test_target==1], 100)
plt.title('test data')

Footnotes

1: 사실 식 (1)을 w\mathbf{w}에 대하여 바로 미분하더라도 쉽게 동일한 결과를 도출할 수 있다. 분수의 미분에서 분모의 제곱 값은 우리는 관심 없으므로 분수의 미분법을 이용하여 분자가 되는 값이 영벡터가 되도록 정리하면 동일한 결과를 얻는다 [3].

참고자료

[1] 조우쯔화 저/김태헌 역, "단단한 머신러닝 머신러닝 기본 개념을 제대로 정리한 인공지능 교과서," 제이펍, 2020.

[2] 장철원, "선형대수와 통계학으로 배우는 머신러닝 with 파이썬 최적화 개념부터 텐서플로를 활용한 딥러닝까지," 비제이퍼블릭, 2021.

[3] https://200315193.tistory.com/1737

[4] https://en.wikipedia.org/wiki/Linear_discriminant_analysis

[5] https://towardsdatascience.com/linear-discriminant-analysis-in-python-76b8b17817c2

[6] https://bskyvision.com/351

profile
연구와 개발의 중간 어디쯤

0개의 댓글