主成分分析與線性判別分析兩種數據降維算法的對比研究

董虎勝

（蘇州經貿學院，蘇州　215009）

主成分分析與線性判別分析兩種數據降維算法的對比研究

董虎勝

（蘇州經貿學院，蘇州215009）

在模式識別與機器學習中，為了降低高維數據帶來的巨大運算量，通常需要對數據進行降維預處理。在常用的數據降維算法中，主成分分析（PCA）與線性判別分析（LDA）是兩種最常用的降維方法。由于這兩種算法具有較強的內在聯系而不易理解，對這兩種算法的工作原理與實現進行對比分析，并對兩者的應用與擴展進行討論。

機器學習；數據降維；PCA；LDA

蘇州經貿學院科研項目（No.KY-ZR1407）

0　引言

在模式識別與機器學習的研究與應用中，經常需要面對高維的數據，例如計算機視覺中進行人臉識別與行人檢測、生物信息學中對蛋白質結構預測時，為了獲得關于目標對象更為豐富的信息，所提取的樣本通常達到上千或上萬維度。另外，為了能夠統計分析出數據內在的模式，在研究中我們希望數據量越多越好。而且在很多應用中，數據樣本是每時每刻都在增加的，例如視頻監控所記錄的畫面、天氣預報系統所記錄的氣候資料、網絡購物平臺的交易數據等。如此大量、高維的數據在分析研究時給運算處理帶來了相當高的難度。盡管目前硬件設備的運算能力已經得到大幅提升，但在處理海量高維數據時仍然力不從心。大數據的存儲傳輸、“維數災”等困擾也由此而來。

為了應對這種挑戰，人們在處理大量的高維數據時已經提出一些解決方案，例如基于分布式運算的Hadoop、MapReduce，基于稀疏表達的壓縮感知等。另一類更為廣泛應用的處理手段即為數據降維，其思想是從原始數據中抽取最具有判別力的維度，或者是通過變換的手段將樣本由原始空間投影到低維空間，但盡可能地保持原有數據在某方面的結構或性質。在高維樣本中一些維上可能有強相關性，而且會存在大量的噪聲，通過降維不僅可以帶來運算量上的降低，還可以實現降噪與去相關。因此，目前數據降維技術廣泛地應用于數據樣本的預處理中。

在數據降維處理中，比較常用且有效的方法為線性變換技術，即通過線性投影將原樣本數據投影到低維子空間中，其中典型的有PCA與LDA。本文對這兩種技術的實現原理與應用進行了對比分析研究，并對兩者的擴展也進行了討論。

1　主成分分析PCA

PCA是一種無標簽的數據降維種方法，其目標是通過線性投影將高維數據映射到低維空間中表示，但同時滿足在所投影的子空間中，各維度上數據的方差保持最大化。由此實現使用較少的維度表示原始數據，但保留原始數據各維度的分布特性。由于方差信息的保留，也使得PCA是數據降維技術中對于原始數據信息丟失最少的一種線性降方法。

設原始樣本為X∈Rd×n，其中d為樣本維度，n為樣本數，第i個樣本表示為xi。根據PCA的最大方差的目標，我們需要求得一個投影矩陣W∈Rd×d'，其中d'≤d，為了求得W，設W=［w1，w2，…wk，…，wd'］，其中wk∈Rd為一單位投影向量，即由于投影后的新樣本為在新的d'維度子空間的表達，因此WT即為過渡矩陣，亦即d'空間的基，這里我們要求各個基為標準正交基，即＜wk，wl>=0（k≠l）。由此可以建立下面的目標函數：

其中C為樣本的協方差矩陣，即：

式（3）為一等式約束的最優化問題，可以采用Lagrange乘子法進行求解。我們可以建立如下的Lagrange方程：

對式（4）求關于W的導數有：

并令其為0，可得CW=λW。考慮W的第k列wk，可以發現Cwk=λwk為一特征值求解問題，若將C的各特征值按由大到小排序，wk即為第k個特征值所對應的特征向量。所以只需對C作特征值分解后，將特征值按降序排序后，取前d'個特征向量拼合后即獲得W。由于數值求解中，使用奇異值（SVD）分解可以獲得更好的數值穩定性，因此也可以對協方差矩陣C采用SVD分解：

其中U為由左特征向量組成的矩陣，∑為一對角矩陣，其對角線元素為各奇異值，V為由右特征矩陣。采用SVD分解的另一個優勢在于分解后∑中各奇異值已經按降序排序，我們可以直接取左特征值矩陣U的前d'列即為W。

由上述求解過程可知，若要對樣本矩陣作PCA降維處理，可以采用如下的步驟：

（2）計算樣本的協方差矩陣；

（3）對協方差矩陣作特征值分解，將特征值按降序排序，并取前d'個特征值所對應的特征向量組成投影矩陣W，當然，也可以采用上面介紹的SVD分解方法；

（4）計算X'=WTX，X'∈Rd'×n即為投影后的新樣本矩陣。

在實際應用中，對于新維度d'的設定上，可以根據需要手工指定，也可以根據所截取的特征值之和占所有特征值和的比率來確定，這種確定特征值的方法也被稱為能量（或貢獻率）確定法。若取能量保留100%，即為完全能量的PCA投影，此時投影后樣本的維度為min（n，d）-1。

2　線性判別分析LDA

LDA的出發點與PCA類似，同樣是將樣本由高維空間投影到低維空間，但其在保留原有數據的特性上與PCA存在差異。LDA要求投影后的樣本點能夠實現屬于同一類別的樣本之間的距離更小，而不同類別的樣本點在投影后的空間中距離更遠，從而實現在低維子空間中將不同的類別樣本區分開的目標。因此LDA是一種帶有標簽的降維技術。

設樣本矩陣X∈Rd×n中有c個類別，其中屬于第i類ωi的樣本有ni個各類別樣本的中心點為所有樣本的中心點為若投影矩陣為W∈Rd×d'，則投影后的樣本為Z=WTX，投影后的第i類Ωi中心點為所有樣本的中心點為

根據LDA的類內緊致、類間疏遠的思想，定義投影后新樣本空間中類間離散度JB為：

定義投影后的樣本的類內緊致度JW為：

其中JB度量了各個類別的中心點到所有樣本中心間的距離且由對各個類進行了加權，JW則度量了所有類別樣本距離自己所在類的中心點的距離。為了便于表達，可定義類間散布矩陣SB與類內散布矩陣SW為：

從而可將JB與JW簡化為：

根據Fisher判別準則可建立目標函數為：

與PCA類似，考慮W的第k列wk，此時上式轉化為：

建立Lagrange方程：

對wk求導并令導數為0，可解得SW-1SB=λwk，即wk為S與S的廣義特征向量。為了使得BW取值最大，只需取SW-1SB前k個最大特征值所對應的特征向量即可拼得W。但是由于SB的秩最大為c-1，因此k≤c-1，即LDA最多只能投影到c-1維的子空間中。

由上述的LDA的推導可以歸納出使用LDA進行數據降維及分類的過程為：

（1）根據給定樣本矩陣計算各類樣本的中心點與所有樣本的中心點；

（2）計算各樣本內類散布矩陣SW與內間散布矩陣SB；

（3）對SW-1SB作特征值分解，將特征值按降序排序，并取前k個特征值所對應的特征向量組成投影矩陣W，當然，也可以采用SVD分解方法；

（4）計算X'=WTX，X'Rd'×n即為投影后的新樣本矩陣。

3　PCA與LDA的差異與聯系

從整體上說PCA與LDA同屬于降維方法，而且兩者在求解投影矩陣時均轉化為求解特征值問題，兩者具有比較強的相似性。在應用中，PCA與LDA也常結合使用，即首先使用PCA進行無監督降維，再使用LDA進行有監督的降維及分類。為了取得比較好的效果，在應用這兩者之前最好進行去數據規范化處理。但PCA在工作中無需樣本的類別信息，因此屬于無監督的降維，而LDA在工作中需要利用樣本的類別標簽，所以其屬于有監督的降維。此外，兩者的差異主要有：

（1）PCA的目的是使投影后的樣本在各個維度上方差保持最大，而LDA在投影后則是要求各個類別之間盡可能分得開。

（2）在使用PCA時，降維后的維度可以根據需要指定，但對于LDA降維后最大不能超出c-1維。

（3）從上面的推導還可以看出PCA的投影矩陣在求解中是要求各個列（即新空間中的各個基向量）都是單位正交的，但對于LDA卻沒有施加此約束。也就是LDA僅考慮投影后樣本類別間的差異而不考慮是否坐標系為正交。

圖1給出了PCA與LDA對于2維示例樣本的投影結果比較。由圖中可以看出PCA的投影方向與LDA的投影方向明顯不同。PCA投影后的樣本的方差信息得了最大程度的保留。而對于LDA來說，選擇的是能夠把兩類樣本更區分開的方向。

4　PCA與LDA的擴展方法

從對PCA與LDA的推導中可以看出，兩者本質上均為將原始樣本線性投影到低維子空間中，但這對于一些存在非線性結構的數據處理上卻存在不足，為了對這類數據的降維，研究人員提出了基于核方法的KernelPCA［4］與KernelLDA［5］。另外，雖然PCA能夠降噪與去相關，但對于大的噪聲與嚴重的異常點，PCA卻不能良好應對，而RobustPCA［6］則可以較好地處理，因為它假設噪聲是稀疏的而不考慮噪聲的強弱。對于LDA來說，其對于服從高斯分布的數據具有比較好的降維效果，但在樣本不服從高斯分布時效果則不夠理想，但此時可以將局部信息引入從而發展出帶局部信息的LDA（Local Fisher Discriminant Analysis，LFDA）［7］或考慮邊緣樣本關系的MFA（Marginal Fisher Analysis）［8］。

圖1　PCA與LDA對2維數據的降維對比

5　結語

PCA與本文對PCA與LDA兩種常用的線性變換降維技術進行了對比分析研究，并根據實驗對兩者的聯系與區別進行了詳細的討論。此外，本文還對這兩種方法的擴展進行了簡要的闡述。作為數據分析中重要的降維技術，基于PCA與LDA思想的數據降維方法也還在不斷發展之中。

［1］楊淑瑩.模式識別與智能計算：MATLAB技術實現（第2版）.北京：電子工業出版社，2011.8.

［2］R.O.Duda，P.E.Hart，李宏東等譯.模式分類（第2版）.北京：機械工業出版社，2003.9.

［3］C.M.Bishop.Pattern Recognition and Machine Learning，Springer，2006.

［4］Sch lkopf B，Smola A，Müller K R.Kernel Principal Component Analysis［J］.Advance in Kernel Methods-Support Vector Learning，2009，27（4）：555-559.

［5］Ye Fei，Z.Shi，and Z.Shi.A Comparative Study of PCA，LDA and Kernel LDA for Image Classification.IEEE International Symposium on Ubiquitous Virtual Reality，2009：51-54.

［6］Candès E J，Li X，Ma Y，et al.Robust Principal Component Analysis［J］.Journal of the ACM，2011，58（3）：1-73.

［7］Sugiyama M.Dimensionality Reduction of Multimodal Labeled Data by Local Fisher Discriminant Analysis［J］.Journal of Machine Learning Research，2007，8（1）：1027-1061.

［8］Yan，Shuicheng，et al.Graph Embedding and Extensions：A General Framework for Dimensionality Reduction.IEEE Transaction on Pattern Analysis and Machine Intelligence，2007，29（1）：40-51.

Machine Learning；Dimension Reduction；PCA；LDA

Comparative Analysis of Two Dimension Reduction Algorithms of PCA and LDA

DONG Hu-sheng
（Suzhou Institute of Trade and Commerce，Suzhou 215009）

To lower the heavy computation induced by high dimensional data in pattern analysis and machine learning，the data is often preprocessed by dimension reduction methods.In the dimension reduction algorithms，Principle Component Analysis（PCA）and Linear Discriminative Analysis（LDA）are two most important and widely used methods.However，they are easily to be confused for the inherent relationship.Presents a detailed comparative analysis of their working principle and implementation，furthermore，discusses their application and extension.

1007-1423（2016）29-0036-05

10.3969/j.issn.1007-1423.2016.29.008

董虎勝（1981-），男，講師，研究方向為機器學習與計算機視覺

2016-08-11

2016-10-20