董虎勝

（蘇州經(jīng)貿(mào)學(xué)院，蘇州　215009）

主成分分析與線性判別分析兩種數(shù)據(jù)降維算法的對(duì)比研究

董虎勝

（蘇州經(jīng)貿(mào)學(xué)院，蘇州215009）

在模式識(shí)別與機(jī)器學(xué)習(xí)中，為了降低高維數(shù)據(jù)帶來的巨大運(yùn)算量，通常需要對(duì)數(shù)據(jù)進(jìn)行降維預(yù)處理。在常用的數(shù)據(jù)降維算法中，主成分分析（PCA）與線性判別分析（LDA）是兩種最常用的降維方法。由于這兩種算法具有較強(qiáng)的內(nèi)在聯(lián)系而不易理解，對(duì)這兩種算法的工作原理與實(shí)現(xiàn)進(jìn)行對(duì)比分析，并對(duì)兩者的應(yīng)用與擴(kuò)展進(jìn)行討論。

機(jī)器學(xué)習(xí)；數(shù)據(jù)降維；PCA；LDA

蘇州經(jīng)貿(mào)學(xué)院科研項(xiàng)目（No.KY-ZR1407）

0　引言

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

為了應(yīng)對(duì)這種挑戰(zhàn)，人們?cè)谔幚泶罅康母呔S數(shù)據(jù)時(shí)已經(jīng)提出一些解決方案，例如基于分布式運(yùn)算的Hadoop、MapReduce，基于稀疏表達(dá)的壓縮感知等。另一類更為廣泛應(yīng)用的處理手段即為數(shù)據(jù)降維，其思想是從原始數(shù)據(jù)中抽取最具有判別力的維度，或者是通過變換的手段將樣本由原始空間投影到低維空間，但盡可能地保持原有數(shù)據(jù)在某方面的結(jié)構(gòu)或性質(zhì)。在高維樣本中一些維上可能有強(qiáng)相關(guān)性，而且會(huì)存在大量的噪聲，通過降維不僅可以帶來運(yùn)算量上的降低，還可以實(shí)現(xiàn)降噪與去相關(guān)。因此，目前數(shù)據(jù)降維技術(shù)廣泛地應(yīng)用于數(shù)據(jù)樣本的預(yù)處理中。

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

1　主成分分析PCA

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

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

其中C為樣本的協(xié)方差矩陣，即：

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

對(duì)式（4）求關(guān)于W的導(dǎo)數(shù)有：

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

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

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

（2）計(jì)算樣本的協(xié)方差矩陣；

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

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

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

2　線性判別分析LDA

LDA的出發(fā)點(diǎn)與PCA類似，同樣是將樣本由高維空間投影到低維空間，但其在保留原有數(shù)據(jù)的特性上與PCA存在差異。LDA要求投影后的樣本點(diǎn)能夠?qū)崿F(xiàn)屬于同一類別的樣本之間的距離更小，而不同類別的樣本點(diǎn)在投影后的空間中距離更遠(yuǎn)，從而實(shí)現(xiàn)在低維子空間中將不同的類別樣本區(qū)分開的目標(biāo)。因此LDA是一種帶有標(biāo)簽的降維技術(shù)。

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

根據(jù)LDA的類內(nèi)緊致、類間疏遠(yuǎn)的思想，定義投影后新樣本空間中類間離散度JB為：

定義投影后的樣本的類內(nèi)緊致度JW為：

其中JB度量了各個(gè)類別的中心點(diǎn)到所有樣本中心間的距離且由對(duì)各個(gè)類進(jìn)行了加權(quán)，JW則度量了所有類別樣本距離自己所在類的中心點(diǎn)的距離。為了便于表達(dá)，可定義類間散布矩陣SB與類內(nèi)散布矩陣SW為：

從而可將JB與JW簡化為：

根據(jù)Fisher判別準(zhǔn)則可建立目標(biāo)函數(shù)為：

與PCA類似，考慮W的第k列wk，此時(shí)上式轉(zhuǎn)化為：

建立Lagrange方程：

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

由上述的LDA的推導(dǎo)可以歸納出使用LDA進(jìn)行數(shù)據(jù)降維及分類的過程為：

（1）根據(jù)給定樣本矩陣計(jì)算各類樣本的中心點(diǎn)與所有樣本的中心點(diǎn)；

（2）計(jì)算各樣本內(nèi)類散布矩陣SW與內(nèi)間散布矩陣SB；

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

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

3　PCA與LDA的差異與聯(lián)系

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

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

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

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

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

4　PCA與LDA的擴(kuò)展方法

從對(duì)PCA與LDA的推導(dǎo)中可以看出，兩者本質(zhì)上均為將原始樣本線性投影到低維子空間中，但這對(duì)于一些存在非線性結(jié)構(gòu)的數(shù)據(jù)處理上卻存在不足，為了對(duì)這類數(shù)據(jù)的降維，研究人員提出了基于核方法的KernelPCA［4］與KernelLDA［5］。另外，雖然PCA能夠降噪與去相關(guān)，但對(duì)于大的噪聲與嚴(yán)重的異常點(diǎn)，PCA卻不能良好應(yīng)對(duì)，而RobustPCA［6］則可以較好地處理，因?yàn)樗僭O(shè)噪聲是稀疏的而不考慮噪聲的強(qiáng)弱。對(duì)于LDA來說，其對(duì)于服從高斯分布的數(shù)據(jù)具有比較好的降維效果，但在樣本不服從高斯分布時(shí)效果則不夠理想，但此時(shí)可以將局部信息引入從而發(fā)展出帶局部信息的LDA（Local Fisher Discriminant Analysis，LFDA）［7］或考慮邊緣樣本關(guān)系的MFA（Marginal Fisher Analysis）［8］。

圖1　PCA與LDA對(duì)2維數(shù)據(jù)的降維對(duì)比

5　結(jié)語

PCA與本文對(duì)PCA與LDA兩種常用的線性變換降維技術(shù)進(jìn)行了對(duì)比分析研究，并根據(jù)實(shí)驗(yàn)對(duì)兩者的聯(lián)系與區(qū)別進(jìn)行了詳細(xì)的討論。此外，本文還對(duì)這兩種方法的擴(kuò)展進(jìn)行了簡要的闡述。作為數(shù)據(jù)分析中重要的降維技術(shù)，基于PCA與LDA思想的數(shù)據(jù)降維方法也還在不斷發(fā)展之中。

［1］楊淑瑩.模式識(shí)別與智能計(jì)算：MATLAB技術(shù)實(shí)現(xiàn)（第2版）.北京：電子工業(yè)出版社，2011.8.

［2］R.O.Duda，P.E.Hart，李宏東等譯.模式分類（第2版）.北京：機(jī)械工業(yè)出版社，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-），男，講師，研究方向?yàn)闄C(jī)器學(xué)習(xí)與計(jì)算機(jī)視覺

2016-08-11

2016-10-20