線性判別分析LDA

LDA算法入門LDA算法概述：線性判別式分析(LinearDiscriminantAnalysis,LDA)，也叫做Fisher線性判別(FisherLinearDiscriminant,FLD),是模式識別的經(jīng)典算法，它是在1996年由Belhumeur引入模式識別和人工智能領(lǐng)域的。線性鑒別分析的基本思想是將高維的模式樣本投影到最佳鑒別矢量空間，以達到抽取分類信息和壓縮特征空間維數(shù)的效果，投影后保證模式樣本在新的子空間有最大的類間距離和最小的類內(nèi)距離即模式在該空間中有最佳的可分離性。因此，它是一種有效的特征抽取方法。使用這種方法能夠使投影后模式樣本的類間散布矩陣最大，并且同時類內(nèi)散布矩陣最小。就是說，它能夠保證投影后模式樣本在新的空間中有最小的類內(nèi)距離和最大的類間距離，即模式在該空間中有最佳的可分離性。LDA假設(shè)以及符號說明：假設(shè)對于一個Rn空間有m個樣本分別為x1,x2，?…x，即每個x是一個n行的12m矩陣，其中n表示屬第i類的樣本個數(shù)，假設(shè)一共有c個類，則in+n+...n+.??+n—m。12ic°S：類間離散度矩陣bS：類內(nèi)離散度矩陣wn:屬于i類的樣本個數(shù)ix:第i個樣本iu：所有樣本的均值u:類i的樣本均值i三．公式推導，算法形式化描述根據(jù)符號說明可得類i的樣本均值為：_1vUi_nX(I)ixwclassi

同理我們也可以得到總體樣本均值：u=丄遲xmii=1根據(jù)類間離散度矩陣和類內(nèi)離散度矩陣定義，可以得到如下式子S=工n(u-u)(u-u)Tbiiii=1S=工工(u-x)(u-x)twikiki=1x^classi當然還有另一種類間類內(nèi)的離散度矩陣表達方式：S=工P(i)(u-u)(u-u)tbiii=1S=》Pi)工(u-x)(u-x)wnikiki=1ixpclassi=工P⑴E\u-x)(u-x)tIxgclassi)iii=1(1.2)(1.3)(1.4)(1.5)(1.6)其中P（i）是指i類樣本的先驗概率，即樣本中屬于i類的概率P(1.2)(1.3)(1.4)(1.5)(1.6)mP（i）代入第二組式子中，我們可以發(fā)現(xiàn)第一組式子只是比第二組式子都少乘了11—，我們將在稍后進行討論，其實對于乘不乘該一，對于算法本身并沒有影響，mm現(xiàn)在我們分析一下算法的思想，我們可以知道矩陣（u-u）（u-u）t的實際意義是一個協(xié)方差矩陣，這個矩陣ii所刻畫的是該類與樣本總體之間的關(guān)系，其中該矩陣對角線上的函數(shù)所代表的是該類相對樣本總體的方差（即分散度），而非對角線上的元素所代表是該類樣本總體均值的協(xié)方差（即該類和總體樣本的相關(guān)聯(lián)度或稱冗余度），所以根據(jù)公式（1.3）可知（1.3）式即把所有樣本中各個樣本根據(jù)自己所屬的類計算出樣本與總體的協(xié)方差矩陣的總和，這從宏觀上描述了所有類和總體之間的離散冗余程度同理可以的得出（1.4）式中為分類內(nèi)各個樣本和所屬類之間的協(xié)方差矩陣之和，它所刻畫的是從總體來看類內(nèi)各個樣本與類之間（這里所刻畫的類特性是由是類

內(nèi)各個樣本的平均值矩陣構(gòu)成)離散度，其實從中可以看出不管是類內(nèi)的樣本期望矩陣還是總體樣本期望矩陣，它們都只是充當一個媒介作用，不管是類內(nèi)還是類間離散度矩陣都是從宏觀上刻畫出類與類之間的樣本的離散度和類內(nèi)樣本和樣本之間的離散度。LDA做為一個分類的算法，我們當然希望它所分的類之間耦合度低，類內(nèi)的聚合度高，即類內(nèi)離散度矩陣的中的數(shù)值要小，而類間離散度矩陣中的數(shù)值要大，這樣的分類的效果才好。這里我們引入Fisher鑒別準則表達式:J◎=容(1.7)fisher9TS9w其中9為任一n維列矢量。Fisher線性鑒別分析就是選取使得J,C)達到最fisher大值的矢量申作為投影方向，其物理意義就是投影后的樣本具有最大的類間離散度和最小的類內(nèi)離散度。我們把公式(1.4)和公式(1.3)代入公式(1.7)得到fisher工n申tfisher工n申t(u-u)(u-u)r申iiii=1工工申T(U—X)(U—X)t申ikik(1.8)i=1xpclassi我們可以設(shè)矩陣R=申T(u—u)其中申可以看成是一個空間，也就是說i9T(u—u)是(u—u)構(gòu)成的低維空間(超平面)的投影。ii申T(u—u)(u—u)t申也可表示為RtR，而當樣本為列向量時，RRt即表示ii(u—u)在申空間的幾何距離的平方。所以可以推出Fisher線性鑒別分析表達式i的分子即為樣本在投影9空間下的類間幾何距離的平方和，同理也可推出分母為樣本在投影9空間下的類內(nèi)幾何距離的平方差，所以分類問題就轉(zhuǎn)化到找一個低維空間使得樣本投影到該空間下時，投影下來的類間距離平方和與類內(nèi)距離平方和之比最大，即最佳分類效果。所以根據(jù)上述思想，即通過最優(yōu)化下面的準則函數(shù)找到有一組最優(yōu)鑒別矢量構(gòu)成1的投影矩陣W（這里我們也可以看出一可以通過分子分母約掉，所以前面所optm提到的第一組公式和第二組公式所表達的效果是一樣的）。WtSW(1.9)W=argmaxb—(1.9)optWtSww可以證明，當S為非奇異（一般在實現(xiàn)LDA算法時，都會對樣本做一次pcaw算法的降維，消除樣本的冗余度，從而保證S是非奇異陣，當然即使S為奇異ww陣也是可以解的，可以把S或\對角化，這里不做討論，假設(shè)都是非奇異的情wb況）時，最佳投影矩陣W的列向量恰為下來廣義特征方程opts申=^S申（1.10）bw的d個最大的特征值所對應的特征向量（矩陣S-1S的特征向量），且最優(yōu)投影軸wb的個數(shù)d<c—1。根據(jù)（1.10）式可以推出s申"S申（1.11）biwi又由于w=,申申］12d下面給出驗證：把（1.10）式代入（1.9）式可得：S9=九S99TS9二9t九S9b11w11b111w1??????n:????S9bd=九S9dwd9tS9:dbd=9t九S9ddwd(1.12)9tS99T九S9九9tS9nmax=丨ibi二Jiiwi=iiwi=X9tS9Iiwi9tS91iwi9tS9iiwi根據(jù)公式的意義來看，要使得max最大則只要取九即可。所以根據(jù)公式（1.9）i可得出結(jié)論：投影矩陣W的列向量為d（自?。﹤€最大特征值所對應的特征opt向量，其中d<c-1。

四．算法的物理意義和思考4.1用一個例子闡述LDA算法在空間上的意義下面我們利用LDA進行一個分類的問題：假設(shè)一個產(chǎn)品有兩個參數(shù)來衡量它是否合格，我們假設(shè)兩個參數(shù)分別為：2.956.632.537.793.575.653.165.472.584.473.52沃沁數(shù)據(jù)來源：/kardi/tutorial/LDA/Numerical%20Example.html所以我們可以根據(jù)上圖表格把樣本分為兩類，一類是合格的，一類是不合格的所以我們可以創(chuàng)建兩個數(shù)據(jù)集類：cls1_data=2.95006.63002.53007.79003.57005.65003.16005.4700cls2_data=2.58004.46002.16006.22003.27003.5200其中cls1_data為合格樣本，cls2_data為不合格的樣本，我們根據(jù)公式（1.1）,1.2）可以算出合格的樣本的期望值，不合格類樣本的合格的值，以及總樣本期望：E_cls1=3.05256.3850E_cls2=2.67004.7333E_all=2.88865.6771我們可以做出現(xiàn)在各個樣本點的位置圖一其中藍色‘*'的點代表不合格的樣本，而紅色實點代表合格的樣本，天藍色的倒三角是代表總期望，藍色三角形代表不合格樣本的期望，紅色三角形代表合格樣本的期望。從x，y軸的坐標方向上可以看出，合格和不合格樣本區(qū)分度不佳。我們在可以根據(jù)表達式（1.3），（1.4）可以計算出類間離散度矩陣和類內(nèi)離散度矩陣：Sb=0.03580.15470.15470.6681Sw=0.5909-1.3338-1.33383.5596我們可以根據(jù)公式（1.10），（1.11）算出S1S特征值以及對應的特征向量：wbL=0.0000002.8837對角線上為特征值，第一個特征值太小被計算機約為0了與他對應的特征向量為V=-0.9742-0.92300.2256-0.3848根據(jù)取最大特征值對應的特征向量：（-0.9230,-0.3848），該向量即為我們要求的子空間，我們可以把原來樣本投影到該向量后所得到新的空間（2維投影到1維，應該為一個數(shù)字）new_cls1_data=-5.2741-5.3328-5.4693-5.0216為合格樣本投影后的樣本值new_cls2_data=-4.0976-4.3872-4.3727為不合格樣本投影后的樣本值，我們發(fā)現(xiàn)投影后，分類效果比較明顯，類和類之間聚合度很高，我們再次作圖以便更直觀看分類效果藍色的線為特征值較小所對應的特征向量，天藍色的為特征值較大的特征向量，其中藍色的圈點為不合格樣本在該特征向量投影下來的位置，二紅色的‘*'符號的合格樣本投影后的數(shù)據(jù)集，從中個可以看出分類效果比較好（當然由于x，y軸單位的問題投影不那么直觀）。我們再利用所得到的特征向量，來對其他樣本進行判斷看看它所屬的類型，我們?nèi)颖军c（2.81，5.46），我們把它投影到特征向量后得到：result=-4.6947所以它應該屬于不合格樣本。4.2LDA算法與PCA算法在傳統(tǒng)特征臉方法的基礎(chǔ)上，研究者注意到特征值打的