[인사이드 머신러닝] 차원축소: 선형판별분석 (Linear Discriminant Analysis, LDA)

cleansky·2021년 8월 31일

Dimension Reduction FDA Fisher's Discriminant Analysis LDA Linear Discriminant Analysis cleansky 기계학습 딥러닝 머신러닝 선형판별분석 이진분류 인공지능 인사이드 머신러닝 차원의 저주 차원축소

인사이드 머신러닝

목록 보기

7/12

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

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

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

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

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

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

$\mathbf{w}^T\bm{\Sigma}_0\mathbf{w}+\mathbf{w}^T\bm{\Sigma}_1\mathbf{w}$ 는 최대한 작게
$\|\mathbf{w}^T\bm{\mu}_0 - \mathbf{w}^T\bm{\mu}_1\|^2$ 은 최대한 크게

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

\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}

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

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

\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 문제로 치환한다.

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

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

\tag{5} \mathbf{S}_b\mathbf{w} = \lambda \mathbf{S}_w \mathbf{w}

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

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

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

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

파이썬 예제

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

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

text

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

text

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')