【降維方法】- 線性判别分析（LDA）

參考：refenrence

簡介

線性判别分析（Linear Discriminant Analysis）作為一種監督式的降維方法，同時也用作分類器，它主要思想是：使得對原空間進行投影運算後，類間的樣本點資料分布間隔大，而類内樣本點資料分布方差小。

原理

有了上述思想後，我們嘗試着自己一步步把這個思想具體化。最近在看《數學之旅》，王教授提到學習數學需要重要培養的一個能力：抽象能力。

數學就是現實世界的高度抽象，它容易抓住問題本質，比如圖論中點和邊的概念，這個概念注重抓住不同物體之間的拓撲關系，而非具體研究這個點是什麼有多大，邊是什麼材質等等。是以，使用數學這個工具，可以友善地直接研究與解決問題，因為其強大的抽象能力。

下面看看我們如何把 【使得對原空間進行投影運算後，類間的樣本點資料分布間隔大，而類内樣本點資料分布方差小】這個思想進行抽象。

我們的研究對象是：資料集 D={(x1,y1),(x2,y2),...,(xm,ym)} D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } , 其中 xi∈Rn x i ∈ R n ， yi∈{0,1} y i ∈ { 0 , 1 } 。定義 Nj(j=0,1) N j ( j = 0 , 1 ) 為第 j j 類樣本的個數，Xj(j=0,1)Xj(j=0,1)為第 j j 類樣本的集合，而μj(j=0,1)μj(j=0,1)為第 j j 類樣本的均值向量，定義∑j(j=0,1)∑j(j=0,1)為第 j j 類樣本的協方差矩陣（嚴格說是缺少分母部分的協方差矩陣）。

其中，∑j∑j 表示如下：

Σj=∑x∈Xj(x−μj)(x−μj)T(j=0,1) Σ j = ∑ x ∈ X j ( x − μ j ) ( x − μ j ) T ( j = 0 , 1 )

首先，我們想讓樣本點投影後（ xi=w⋅xTi x i = w ⋅ x i T ）兩個類之間的間隔大，一種可行的抽象方式，或者說數學表達方式是：最大化 ||wTμ0−wTμ1||22 | | w T μ 0 − w T μ 1 | | 2 2 。同時，同類樣本點方差盡可能小，即最小化 wTΣ0w+wTΣ1w w T Σ 0 w + w T Σ 1 w ，最後結合兩者就得到了需要優化的目标式：

argmaxwJ(w)=||wTμ0−wTμ1||22wTΣ0w+wTΣ1w=wT(μ0−μ1)(μ0−μ1)TwwT(Σ0+Σ1)w a r g m a x ⏟ w J ( w ) = | | w T μ 0 − w T μ 1 | | 2 2 w T Σ 0 w + w T Σ 1 w = w T ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T w w T ( Σ 0 + Σ 1 ) w

上面的優化問題的求解，可以借助矩陣理論求出，這裡直接給出結論：

w=S−1w(μ0−μ1) w = S w − 1 ( μ 0 − μ 1 )

其中 Sw=Σ0+Σ1=∑x∈X0(x−μ0)(x−μ0)T+∑x∈X1(x−μ1)(x−μ1)T S w = Σ 0 + Σ 1 = ∑ x ∈ X 0 ( x − μ 0 ) ( x − μ 0 ) T + ∑ x ∈ X 1 ( x − μ 1 ) ( x − μ 1 ) T

從上述一步步推導可以看出，最重要的還是使用數學工具對目标問題的抽象，我們需要學習多種常見的抽象方式，然後在實際問題中使用這些思想去解決新的問題。

算法流程（二分類問題）

輸入：資料集 D={(x1,y1),(x2,y2),...,(xm,ym)} D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } ,其中任意樣本 xi x i 為 n n 維向量，yi∈{C0,C1}yi∈{C0,C1}，降維到的次元 d d 。

輸出：降維後的樣本集D'D′。

• 計算類内散度矩陣 Sw S w
• 計算類間散度矩陣 Sb=(μ0−μ1)(μ0−μ1)T S b = ( μ 0 − μ 1 ) ( μ 0 − μ 1 ) T
• 計算矩陣 S−1w⋅Sb S w − 1 ⋅ S b
• 計算 S−1w⋅Sb S w − 1 ⋅ S b 的最大的 d d 個特征值和對應的dd個特征向量 (w1,w2,...wd) ( w 1 , w 2 , . . . w d ) ,得到投影矩陣 W W
• 得到輸出樣本集D'={(z1,y1),(z2,y2),...,(zm,ym)}D′={(z1,y1),(z2,y2),...,(zm,ym)}

代碼：

Github

讨論

各降維方法的讨論：here