? 特征選擇(亦即降維)是數(shù)據(jù)預(yù)處理中非常重要的一個步驟。對于分類來說，特征選擇可以從眾多的特征中選擇對分類最重要的那些特征，去除原數(shù)據(jù)中的噪音。主成分分析(PCA)與線性判別式分析(LDA)是兩種最常用的特征選擇算法。關(guān)于PCA的介紹，可以見我的 另一篇博文 。這里主要介紹線性判別式分析(LDA)，主要基于Fisher Discriminant Analysis with Kernals[1]和Fisher Linear Discriminant Analysis[2]兩篇文獻(xiàn)。

? LDA與PCA的一大不同點在于，LDA是有監(jiān)督的算法，而PCA是無監(jiān)督的，因為PCA算法沒有考慮數(shù)據(jù)的標(biāo)簽(類別)，只是把原數(shù)據(jù)映射到一些方差比較大的方向(基)上去而已。而LDA算法則考慮了數(shù)據(jù)的標(biāo)簽。文獻(xiàn)[2]中舉了一個非常形象的例子，說明了在有些情況下，PCA算法的性能很差，如下圖：? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?我們用不同的顏色標(biāo)注C1,C2兩個不同類別的數(shù)據(jù)。根據(jù)PCA算法，數(shù)據(jù)應(yīng)該映射到方差最大的那個方向，亦即Y軸方向，但是如果映射到Y(jié)軸方向，C1,C2兩個不同類別的數(shù)據(jù)將完全混合在一起，很難區(qū)分開，所以使用PCA算法進(jìn)行降維后再進(jìn)行分類的效果會非常差。但是使用LDA算法，數(shù)據(jù)會映射到X軸方向。

? LDA算法會考慮到數(shù)據(jù)的類別屬性，給定兩個類別C1、C2，我們希望找到一個向量ω,當(dāng)數(shù)據(jù)映射到ω的方向上時，來自兩個類的數(shù)據(jù)盡可能的分開，同一個類內(nèi)的數(shù)據(jù)盡可能的緊湊。數(shù)據(jù)的映射公式為：z=ω ^T x, ?其中z是數(shù)據(jù)x到ω上的投影，因而也是一個d維到1維的維度歸約。

? 令 m ₁ 和m ₁ 分別表示C1類數(shù)據(jù)投影之前個投影之后的均值，易知m ₁ =ω ^T m _1, 同理m ₂ =ω ^T m ₂

?? 令s ₁ ² 和s ₂ ² 分別表示C1和C2類數(shù)據(jù)在投影之后的散布(scatter)，亦即s ₁ ² = ∑ (ω ^T x ^t -m1) ² r ^t ，s ₂ ² =∑(ω ^T x ^t -m2) ² （1-r ^t ）其中如果x ^t ∈C1,則r ^t =1，否則r ^t =0。

? 我們希望|m ₁ -m ₂ |盡可能的大，而s ₁ ² +s ₂ ² 盡可能的小， Fisher線性判別式 就是最大化下面式子的ω：

? J(ω)=(m ₁ -m ₂ ) ² /(s ₁ ² +s ₂ ² ) ? ? 式子-1

? 改寫式子-1中的分子： ? (m ₁ -m ₂ ) ² =? (ω ^T m ₁ -ω ^T m ₂ ) ² =ω ^T ( m ₁ - m ₂ )( m ₁ - m ₂ ) ^T ω=ω ^T S _B ω

? 其中 S _B =( m ₁ - m ₂ )( m ₁ - m ₂ ) ^{T ?} ?式子-2

? 是 類間散布矩陣 (between class scatter matrix)。

? 改寫式子-1中的分母：

? ∑(ω ^T x ^t -m1) ² r ^t =∑ω ^T (x ^t - m ₁ )(x ^t - m ₁ ) ^T ωr ^t =ω ^T S ₁ ω, 其中 S ₁ =∑r ^t (x ^t - m ₁ )(x ^t - m ₁ ) ^T 是C1的 類內(nèi)散布矩陣 (within class scatter matrix)。

? 令 S _W = S ₁ + S ₂ ，是 類內(nèi)散布的總和 ，則s ₁ ² +s ₂ ² =ω ^T S _W ω。

? 所以式子-1可以改寫為：

? J(ω)=(ω ^T S _B ω)/(ω ^T S _W ω) ? ?式子-3

? 我們只需要使式子-3對于ω求導(dǎo)，然后使導(dǎo)數(shù)等于0，便可以求出ω的值：ω=c S _W ^-1 ( m ₁ - m ₂ ),其中c是一個參數(shù)，我們只對ω的方向感興趣，所以c可以取值為1.

? 另外，最后求得的?J(ω)的值等于λ _k ，λ _k 是 S _W ^-1 S _B 的最大的特征值，而ω則是 S _W ^-1 S _B 的最大特征值所對應(yīng)的特征向量。

? 最后有一些關(guān)于LDA算法的討論，出自文獻(xiàn)[1]：

? 1. Fisher LDA對數(shù)據(jù)的分布做了一些很強的假設(shè)，比如每個類的數(shù)據(jù)都是高斯分布，各個類的協(xié)方差相等。雖然這些強假設(shè)很可能在實際數(shù)據(jù)中并不滿足，但是Fisher LDA已經(jīng)被證明是非常有效地降維算法，其中的原因是線性模型對于噪音的魯棒性比較好，不容易過擬合，缺點是模型簡單，表達(dá)能力不強，為了增強Fisher LDA算法的表達(dá)能力，可以引入核函數(shù)，參見我的另外一篇博客 機(jī)器學(xué)習(xí)-核Fisher LDA算法 。

? 2. 準(zhǔn)確的估計數(shù)據(jù)的散布矩陣是非常重要的，很可能會有較大的偏置。用式子-2進(jìn)行估計在樣本數(shù)據(jù)比較少(相對于維數(shù)來說)時會產(chǎn)生較大的變異性。

?

? 參考文獻(xiàn)：

? [1] Fisher Discriminant Analysis with Kernals . Sebastian Mika, Gunnar Ratsch, Jason Weston, Bernhadr Scholkopf, Klaus-Robert Muller.

? [2] Fisher Linear Discriminant Analysis . Max Welling.

? [3] 機(jī)器學(xué)習(xí)導(dǎo)論。 Ethem Alpaydin

機(jī)器學(xué)習(xí)-特征選擇(降維) 線性判別式分析(LDA)