개시하다

학교 과제와 함께 선형 판별 분석(Liner Discriminant Analysis, LDA)의 유명한 알고리즘인 Fisher의 선형 판별을 썼습니다. 이해하기 어려운 부분도 있다고 생각합니다. 양해해 주십시오.

선형 판별 분석

선형 판별 분석은'가장 두 종류를 판별할 수 있는'직선을 구하는 방법이다.
데이터가 직선의 어느 쪽에 있는지 보면 어느 종류에 속하는지 판단할 수 있다. 이 직선은 경계를 결정한다고 한다. 이해하기 편리하도록 각종 데이터가 2차원 데이터에 속한다면 경계는 아래 그림과 같은 이미지이다.

비록'직선의 어느 쪽을 보느냐'라고 하지만 실제 데이터를 식별할 때 적당한 선형 변환을 통해 데이터를 직선z에 비추면 두 가지 유형을 쉽게 분별할 수 있다. 데이터를 1차원으로 압축하면임계값의 표량값으로 적당한 설정을 통해 어떤 종류에 속하는지 판단할 수 있습니다. Fisher의 선형 판별 분석은 투영 목표의 직선z를 찾는 방법 중 하나입니다.
　

선형 변환이 행렬 공식으로 표시될 때

y_n = w^T x_n

xn은 D차원 데이터이고 w는 선형 변환 벡터(xn과 같은 D차원 벡터)이며 yn은 선형 변환 후의 1차원 데이터(표량)이다.
그나저나 선형 판별 분석의 판별 대상은 두 개의 등급이 아니라 여러 개의 등급도 대응할 수 있다.
또한 각종 데이터는 2차원에 적용되지 않고 3차원 이상에도 적용된다. 이런 상황에서 경계를 결정하는 것은 직선이 아니라 평면이나 초평면이다.

Fisher의 선형 판별 분석 내보내기

실제적으로 데이터를 보면서 Fisher의 선형 판별을 내보냅니다.Fisher의 선형 판별은 각종 투영의 분리도가 가장 큰 선형 변환 벡터 w(투영 데이터의 직선z의 경사)를 찾아내는 방법입니다.
우선 다음 데이터 C1과 C2를 고려하십시오.

클래스 Ck의 데이터 수가 Nk인 경우 각 클래스의 평균은 입니다.

m_1 = \frac{1}{N_1}\sum_{n \in C_1}x_n

m_2 = \frac{1}{N_2}\sum_{n \in C_2}x_n

이 m1과 m2를 각 단계의 대표점으로 하고 이 두 점이 선형 변환 벡터 w로 투영될 때 가장 멀리 떨어진다. 즉,

w^T m_1 - w^T m_2 = w^T (m_1 - m_2)

그러나 필요한 것은 최대치의 벡터 w의 경사를 주는 것이기 때문에 벡터 w 자체의 크기를 늘려도 의미가 없다. 따라서 w는 단위 길이의 제약이다.

|w|=1

라그랑의 날이 정해지지 않은 곱셈법으로 최대치를 구하다

w \propto (m_1 - m_2)

이것은 w와 각종 평균치를 연결하는 라인이 평행하다는 것을 의미한다. 실제로 이 벡터 w에서 경계를 결정하는 직선을 뺀다. 경계를 결정하는 직선은 w와 정교하고 각종 평균치를 연결하는 라인의 중점을 통해 아래 그림과 같다.

C1의 파란색 점도 경계를 결정하는 직선에 있어서 이것만으로는 판별할 수 없다.
실제로 각 학급의 평균치만 보면 판별이 잘 안 된다. 예를 들어 C1의 파란색 점은 C2의 빨간색 점이 밀집된 위치에 섞여 있고, 다른 한편으로는 C2에서 멀리 떨어진 곳에 파란색 점이 많이 존재한다면 평균적으로 두 학급은 분리된 것이다.각 반의 점 편차가 크면 평균 위치가 갈라져도 적당한 결정 경계를 그을 수 없다.
여기에 벡터 w를 확정하기 위해 또 다른 조건을 더한다. 즉, 같은 종류의 데이터는 투영 후에 가능한 한 밀집되기를 원한다. 즉, 투영 후 각종 내의 분산이 작아진다. 투영 후 각종 분산은 공식으로 표시하면,

s_1^2 = \sum_{n \in C_1} (w^T x_n - w^T m_1)^2

s_2^2 = \sum_{n \in C_2} (w^T x_n - w^T m_2)^2

따라서 각 학급의 분산을 줄이기 위해

s^2 = s_1^2 + s_2^2

최소화하면 돼.
적당한 w를 찾기 위해,

각종 간의 평균 차이는 최대한 커지고 선형 전환 후의 두 종류는 최대한 멀리한다.

선형 변환 후의 각종 별내의 데이터를 밀집시키기 위해 각종 별내의 분산은 가능한 한 줄인다.

의 두 조건이 필요하다. 이 두 조건은 점수를 하나의 조건으로 처리할 수 있다. 즉,

J(w) = \frac{(クラス間の平均に関する最大化問題)}{(クラス内の分散に関する最小化問題)}

이런 공식은 평가 함수 J(w)를 최대화하면 된다.
그러나 분자와 분모를 똑같이 처리하기 위해 분자도 평균이 아니라 분산된 형태로 표시한다.
즉,

w^T (m_1 -m_2)

부터 시작하다

w^T (m_1 - m_2) (m_1 - m_2)^T w

이때,

S_B = (m_1 - m_2) (m_1 - m_2)^T

유간 협방차 행렬이라고 한다.
그래서

w^T S_B w

이렇게 써도 돼요.
분모는,

s^2 = s_1^2 + s_2^2 = \sum_{n \in C_1} (w^T x_n - w^T m_1)^2 + \sum_{n \in C_2} (w^T x_n - w^T m_2)^2

하지만

S_W = \sum_{n \in C_1} (x_n - m_1)^2 + \sum_{n \in C_2} (x_n - m_2)^2

먼 곳,

s^2 = w^T S_W w

이때 SW는 반 전체 분산 행렬이라고 불린다.
따라서 평가 함수 J(w),

J(w) = \frac{w^T S_B w}{w^T S_W w}

w를 최대화합니다. 라그랑의 정해지지 않은 곱셈법으로 해답을 구한 후,

w \propto {S_W}^{-1} S_B w \propto {S_W}^{-1} (m_1 - m_2)

되다
결론은 D차원의 데이터에서 각종 내의 평균값과 전체 클래스 내의 협방차 행렬의 역행렬을 구하면 선형 변환 벡터 w를 얻어 경계를 확정한다.

실제로 해보니 경계를 결정하는 직선이 잘 그려진 것 같다.
데이터를 적당히 생성하고, 경계를 긋는 프로그램을 Fisher의 선형 판별으로 써 보세요.
fisher.py

#coding: utf-8

import numpy as np
import matplotlib.pyplot as plt

DIM = 2 #データの次元数

#直線の式
def f(x, a, b):
    return a*x+b

#図示
def plot(cls1, cls2, line=None):
    x,y = cls1.T
    plt.plot(x, y, 'bo', ms=3, label='class1')
    x, y = cls2.T
    plt.plot(x, y, 'ro', ms=3, label='class2')

    if not (line is None):
        plt.plot(line[0], line[1], 'k-', ms=5)

    plt.xlim(-10,10)
    plt.ylim(-10,10)

    plt.show()

def fisher(cls1, cls2):
    #リストからnp.arrayに変換（行列の転置や逆行列を扱うため）
    cls1 = np.array(cls1)
    cls2 = np.array(cls2)

    #各クラスの平均値
    mean1 = np.mean(cls1, axis=0)
    mean2 = np.mean(cls2, axis=0)

    #総クラス内共分散行列
    sw = np.zeros((DIM,DIM))
    for xn in cls1:
        xn = xn.reshape(DIM,1)
        mean1 = mean1.reshape(DIM,1)
        sw += np.dot((xn-mean1),(xn-mean1).T)
    for xn in cls2:
        xn = xn.reshape(DIM,1)
        mean2 = mean2.reshape(DIM,1)
        sw += np.dot((xn-mean2),(xn-mean2).T)

    #総クラス内共分散行列の逆行列
    sw_inv = np.linalg.inv(sw)

    #wを求める
    w = np.dot(sw_inv,(mean1-mean2))

    #決定境界直線を図示する
    mean = (mean1 + mean2)/2 #平均値の中点
    a = -w[0]/w[1] #wと直交する
    b = a*mean[0]+mean[1]
    x = np.linspace(-8, 8, 1000)
    y = f(x,a,b)

    plot(cls1, cls2, (x,y))

    return w

if __name__ == '__main__':
    #テスト用2次元データ
    cov = [[3,1],[1,3]] #共分散
    cls1 = np.random.multivariate_normal([-5,-5], cov, 50)
    cls2 = np.random.multivariate_normal([5,5], cov, 50)

    #fisherで線形変換ベクトルwを求める
    w = fisher(cls1, cls2)
    print('w =', w, '\n')