（推薦）線性判別分析LDA與主成分分析PCA

1、線性判別分析（LDA）與主成分分析（PCA）,重慶大學(xué)余俊良,1,第一部分線性判別分析（LDA）,2,介紹,線性判別分析(LinearDiscriminantAnalysis,LDA)，也叫做Fisher線性判別(FisherLinearDiscriminant,FLD)，是模式識別的經(jīng)典算法，1936年由Ronald Fisher首次提出，并在1996年由Belhumeur引入模式識別和人工智能領(lǐng)域。,3,例子,舉一個例子，假設(shè)我們對一張100*100像素的圖片做人臉識別，每個像素是一個特征，那么會有10000個特征，而對應(yīng)的類別標(biāo)簽y僅僅是0，1值，1代表是人臉。這么多特征不僅訓(xùn)練復(fù)雜，而

2、且不必要特征對結(jié)果會帶來不可預(yù)知的影響，但我們想得到降維后的一些最佳特征（與y關(guān)系最密切的），怎么辦呢？,4,基本思想,線性判別分析的基本思想是將高維的模式樣本投影到最佳鑒別矢量空間，以達到抽取分類信息和壓縮特征空間維數(shù)的效果。投影后保證模式樣本在新的子空間有最大的類間距離和最小的類內(nèi)距離，即模式在該空間中有最佳的可分離性。因此，它是一種有效的特征抽取方法。使用這種方法能夠使投影后模式樣本的類間散布矩陣最大，并且同時類內(nèi)散布矩陣最小。,5,下面給出一個例子，說明LDA的目標(biāo)：,可以看到兩個類別，一個綠色類別，一個紅色類別。左圖是兩個類別的原始數(shù)據(jù)，現(xiàn)在要求將數(shù)據(jù)從二維降維到一維。直接投影到x1

3、軸或者x2軸，不同類別之間 會有重復(fù)，導(dǎo)致分類效果下降。右圖映射到的直線就是用LDA方法計算得到的，可以看到，紅色類別和綠色類別在映射之后之間的距離是最大的，而且每個類別內(nèi) 部點的離散程度是最小的（或者說聚集程度是最大的）。,6,7,LDA,要說明白LDA，首先得弄明白線性分類器(Linear Classifier) ：因為LDA是一種線性分類器。對于K-分類的一個分類問題， 會有K個線性函數(shù)：,當(dāng)滿足條件：對于所有的j，都有Yk Yj,的時候，我們就說x 屬于類別k。對于每一個分類，都有一個公式去算一個分值， 在所有的公式得到的分值中，找一個最大的，就是所屬的分類 。,權(quán)向量（weight

4、vector） 法向量（normal vector）,閾值（threshold） 偏置（bias）,8,LDA,上式實際上就是一種投影，是將一個高維的點投影到一條高維的直線上，LDA的目標(biāo)是，給出一個標(biāo)注了類別的數(shù)據(jù)集，投影到了一條直線之后，能夠使得點盡量的按類別區(qū)分開，當(dāng)k=2即二分類問題的時候，如下圖所示：,紅色的方形的點為0類的原始點、藍色的方形點為1類的原始點，經(jīng)過原點的那條線就是投影的直線，從圖上可以清楚的看到，紅色的點和藍色的點被原點明顯的分開了。下面我來推導(dǎo)一下二分類LDA問題的公式：,9,LDA,假設(shè)用來區(qū)分二分類的直線（投影函數(shù))為： LDA分類的一個目標(biāo)是使得不同類別之間的

5、距離越遠越好，同 一類別之中的距離越近越好，所以我們需要定義幾個關(guān)鍵的值:,類別i的原始中心點(均值)為：（Di表示屬于類別i的點): 類別i投影后的中心點為： 衡量類別i投影后，類別點之間的分散程度（方差）為： 最終我們可以得到一個下面的公式，表示LDA投影到w后的目標(biāo)優(yōu)化函數(shù)：,10,LDA,我們分類的目標(biāo)是，使得類別內(nèi)的點距離越近越好（集中），類別間的點越遠越好。,分母表示每一個類別內(nèi)的方差之和，方差越大表示一個類別內(nèi)的點越分散，分子為兩個類別各自的中心點的距離的平方，我們最大化J(w)就可以求出最優(yōu)的w,11,LDA,我們定義一個投影前的各類別分散程度的矩陣，其意思是，如果某一個分類的

6、輸入點集Di里面的點距離這個分類的中心點mi越近，則Si里面元素的值就越小，如果分類的點都緊緊地圍繞著mi，則Si里面的元素值越更接近0. 帶入Si，將J(w)分母化為：,12,LDA,同樣的將J(w)分子化為： 這樣目標(biāo)優(yōu)化函數(shù)可以化成下面的形式：,13,LDA,14,LDA,15,LDA,至此，我們只需要求出原始樣本的均值和方差就可以求出最佳的方向w，這就是Fisher于1936年提出的線性判別分析。 看上面二維樣本的投影結(jié)果圖：,16,LDA,對于N(N2)分類的問題，就可以直接寫出以下的結(jié)論： 這同樣是一個求廣義特征值的問題，求出的第i大的特征向量，即為對應(yīng)的Wi。 （此處推導(dǎo)過程見附

7、錄PDF）,17,第二部分主成分分析（PCA）,18,介紹,在實際問題中，我們經(jīng)常會遇到研究多個變量的問題，而且在多數(shù)情況下，多個變量之 間常常存在一定的相關(guān)性。由于變量個數(shù)較多再加上變量之間的相關(guān)性，勢必增加了分析問 題的復(fù)雜性。如何從多個變量中綜合為少數(shù)幾個代表性變量，既能夠代表原始變量的絕大多 數(shù)信息，又互不相關(guān)，并且在新的綜合變量基礎(chǔ)上，可以進一步的統(tǒng)計分析，這時就需要進行主成分分析。,19,基本思想,主成分分析所要做的就是設(shè)法將原來眾多具有一定相關(guān)性的變量，重新組合為一組新的相互無關(guān)的綜合變量來代替原來變量。通常，數(shù)學(xué)上的處理方法就是將原來的變量做線性組合，作為新的綜合變量，但是這種

8、組合如果不加以限制，則可以有很多，應(yīng)該如何選擇呢？,20,基本思想,如果將選取的第一個線性組合即第一個綜合變量記為F1 ，自然希望它盡可能多地反映原來變量的信息，這里“信息”用方差來測量，即希望Var(F1)越大，表示F1包含的信息越多。因此在所有的線性組合中所選取的F1應(yīng)該是方差最大的，故稱F1為第一主成分。如果第一主成分不足以代表原來p 個變量的信息，再考慮選取F2即第二個線性組合，為了有效地反映原來信息,F1已有的信息就不需要再出現(xiàn)在F2中， 用數(shù)學(xué)語言表達就是要求Cov(F1 ,F2)=0，稱F2為第二主成分，依此類推可以構(gòu)造出第三、四第p 個主成分。,21,最大方差理論,在信號處理中

9、認(rèn)為信號具有較大的方差，噪聲有較小的方差，信噪比就是信號與噪聲的方差比，越大越好。因此我們認(rèn)為，最好的k維特征是將n維樣本點轉(zhuǎn)換為k維后，每一維上的樣本方差都很大。,22,最大方差理論,比如左圖有5個樣本點，右圖將樣本投影到某一維上，這里用一條過原點的直線表示 假設(shè)我們選擇兩條不同的直線做投影，那么左右兩條中哪個好呢？根據(jù)我們之前的方差最大化理論，左邊的好，因為投影后的樣本點之間方差最大。,23,最大方差理論,24,最大方差理論,Su = u,這是一個標(biāo)準(zhǔn)的特征值表達式了，對應(yīng)的特征值，u對應(yīng)的特征向量。 由此var = uTSu = var取得最大值的條件就是最大，也就是取得最大的特征值的時

10、候。假設(shè)我們是要將一個D維的數(shù)據(jù)空間投影到M維的數(shù)據(jù)空間中（M D)， 那我們?nèi)∏癕個特征向量構(gòu)成的投影矩陣就是能夠使得方差最大的矩陣了。同時，由于u是實對稱矩陣的特征向量，因此特征向量之間正交，投影得到的綜合變量彼此獨立，協(xié)方差為0。,25,最大方差理論,因此，我們只需要對協(xié)方差矩陣進行特征值分解，得到的前k大特征值對應(yīng)的特征向量就是最佳的k維新特征，而且這k維新特征是正交的。得到前k個u以后，樣例xi通過以下變換可以得到新的樣本。 其中的第j維就是xi在uj上的投影。通過選取最大的k個u，使得方差較小的特征（如噪聲）被丟棄。,26,PCA小結(jié),PCA技術(shù)的一大好處是對數(shù)據(jù)進行降維的處理。我

11、們可以對新求出的“主元”向量的重要性進行排序，根據(jù)需要取前面最重要的部分，將后面的維數(shù)省去，可以達到降維從而簡化模型或是對數(shù)據(jù)進行壓縮的效果。同時最大程度的保持了原有數(shù)據(jù)的信息。PCA技術(shù)的一個很大的優(yōu)點是，它是完全無參數(shù)限制的。在PCA的計算過程中完全不需要人為的設(shè)定參數(shù)或是根據(jù)任何經(jīng)驗?zāi)Ｐ蛯τ嬎氵M行干預(yù)，最后的結(jié)果只與數(shù)據(jù)相關(guān)，與用戶是獨立的。但是，這一點同時也可以看作是缺點。如果用戶對觀測對象有一定的先驗知識，掌握了數(shù)據(jù)的一些特征，卻無法通過參數(shù)化等方法對處理過程進行干預(yù)，可能會得不到預(yù)期的效果，效率也不高。,27,總結(jié),28,PCA與LDA對比,PCA與LDA的降維對比： PCA選擇樣

12、本點投影具有最大方差的方向，LDA選擇分類性能最好的方向。,29,PCA與LDA對比,LDA的全稱是Linear Discriminant Analysis（線性判別分析），是一種supervised learning。主成分分析（PCA）與LDA有著非常近似的意思，LDA的輸入數(shù)據(jù)是帶標(biāo)簽的，而PCA的輸入數(shù)據(jù)是不帶標(biāo)簽的，所以PCA是一種unsupervised learning。LDA通常來說是作為一個獨立的算法存在，給定了訓(xùn)練數(shù)據(jù)后，將會得到一系列的判別函數(shù)（discriminate function），之后對于新的輸入，就可以進行預(yù)測了。而PCA更像是一個預(yù)處理的方法，它可以將原本的數(shù)據(jù)降低維度，而使得降