? 特征選擇(亦即降維)是數(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
1
和m
1
分別表示C1類數(shù)據(jù)投影之前個投影之后的均值,易知m
1
=ω
T
m
1,
同理m
2
=ω
T
m
2
?? 令s 1 2 和s 2 2 分別表示C1和C2類數(shù)據(jù)在投影之后的散布(scatter),亦即s 1 2 = ∑ (ω T x t -m1) 2 r t ,s 2 2 =∑(ω T x t -m2) 2 (1-r t )其中如果x t ∈C1,則r t =1,否則r t =0。
? 我們希望|m 1 -m 2 |盡可能的大,而s 1 2 +s 2 2 盡可能的小, Fisher線性判別式 就是最大化下面式子的ω:
? J(ω)=(m 1 -m 2 ) 2 /(s 1 2 +s 2 2 ) ? ? 式子-1
? 改寫式子-1中的分子: ? (m 1 -m 2 ) 2 =? (ω T m 1 -ω T m 2 ) 2 =ω T ( m 1 - m 2 )( m 1 - m 2 ) T ω=ω T S B ω
? 其中 S B =( m 1 - m 2 )( m 1 - m 2 ) T ? ?式子-2
? 是 類間散布矩陣 (between class scatter matrix)。
? 改寫式子-1中的分母:
? ∑(ω T x t -m1) 2 r t =∑ω T (x t - m 1 )(x t - m 1 ) T ωr t =ω T S 1 ω, 其中 S 1 =∑r t (x t - m 1 )(x t - m 1 ) T 是C1的 類內(nèi)散布矩陣 (within class scatter matrix)。
? 令 S W = S 1 + S 2 ,是 類內(nèi)散布的總和 ,則s 1 2 +s 2 2 =ω T S W ω。
? 所以式子-1可以改寫為:
? J(ω)=(ω T S B ω)/(ω T S W ω) ? ?式子-3
? 我們只需要使式子-3對于ω求導(dǎo),然后使導(dǎo)數(shù)等于0,便可以求出ω的值:ω=c S W -1 ( m 1 - m 2 ),其中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
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
