基于多子空間線性判別分析的特征提取與分類

董 琰

（中石化勝利油田分公司ERP支持中心，山東東營257000）

0 引 言

特征提取和分類始終是模式識別研究的重要課題，在生物特征識別，基因圖譜分析，遙感影像分類，空間數據挖掘等應用領域更有著廣泛的實用價值。隨著數據的復雜性和規模急劇增長，特征提取和分類的難點主要表現為數據集中樣本的特征維數遠遠大于每類樣本數量。由于樣本的稀疏造成樣本類的統計特征描述不充分，在利用經典的線性判別分析方法 （LDA）進行分類時往往因類內散度矩陣的奇異性而無法求解，即模式識別中的高維小樣本問題［1］。而實踐中常用Fisherface方法來解決高維小樣本問題［2］，它由主成分分析 （PCA）和線性判別分析 （LDA）組成，先通過PCA實現降維，從而消除類內散度矩陣的奇異性并有效降低運算復雜度，但是PCA的作為最佳描述特征的提取方法是以投影后方差最大為準則，并沒有判別分析能力，降維時沒有考慮樣本的類屬信息，在維度縮減的同時，也帶來分類判別信息的缺失。LDA的目標是使特征提取后的樣本類間離散度和類內離散度的比值最大化，即各類樣本在特征空間中有最佳的可分離性。該方法利用最大散度比準則將所有類的樣本投影到同一個特征空間中，而忽略了各類樣本在特征分布上的差異；同時，對于一個特定的模式識別問題，表達和識別模式的特征具有不同的形式，而且在物理意義上也不是完全相同的，并且在數量級也有很大差別，簡單基于距離的匹配劃分難以實現客觀的分類判別。

本文針對常用PCA和LDA在降維和判別分析上的不足，在算法設計中，一方面借鑒了PCA在維數縮減上的作用，另一方面盡可能多地保留類的判別信息。算法的簡單思想就是通過對每類樣本進行特征提取以有效地保留判別信息和降維。提出的多子空間線性判別分析，對不同樣本類分別描述，針對每類樣本提取最適合分類的特征子空間；分類時綜合考慮投影后樣本的概率分布模型，以概率距離作為隸屬置信度，并以此作為分類的依據，選取最可能的類屬劃分。

1 相關技術

LDA［3］是統計模式識別中最基本和常用的分類方法，其準則函數如下

LDA使用最大散度比準則，目的是求使準則Jd（w）最大的投影w，在此投影下可以使樣本的類間散度矩陣Sb與類內散度矩陣Sw的比值最大，使得經過特征提取后的樣本有最大的類間距離和最小的類內距離，即模式在該空間中有最佳的可分離性。當Sw非奇異時，根據Lagrange乘數法可得w是由矩陣S－1wSb的特征向量組成的矩陣，但在高維小樣本的情況下，Sw非奇異的前提常常無法滿足。

根據子空間分析理論，解決高維小樣本問題的關鍵是去除由冗余特征組成樣本空間的稀疏部分，這些冗余特征所具有的判別信息往往很少或沒有，是類內散度矩陣奇異的根源，針對LDA方法在解決高維小樣本問題的困境，先后 有 Fisherface （PCA ＋ LDA），Direct－LDA［4］， Dual－LDA［5］，Generalized LDA［6］等方法提出，其中PCA＋LDA作為有效的方法廣泛應用在人臉識別領域。在PCA＋LDA處理中，首先利用PCA進行維度縮減，作為一種全局提取技術，PCA的目標是尋找一組正交向量使得所有樣本經過投影后的方差最大，而PCA在降維過程中并沒有考慮樣本的類別標志，因此在以分類為目標的特征提取技術中并不是最優的，提取后的特征反而可能弱化了原始數據的分類能力［7］。下面以2維兩類分類問題為例，說明PCA在以分類為目標的場合下，作為特征提取手段的不足。

圖1 PCA用于兩類分類示例

圖2 考慮分類后的PCA及分類結果

圖1 、圖2中的淺灰和深灰 （其中圖1（a），圖2（a）中左下側為淺灰，右上側為深灰；圖1（b），圖2（b）中左側淺灰，右側深灰）分別代表不同類的數據樣本，將樣本數據分別投影到PCA第一主元方向ω1和新提取的投影方向ω1′，樣本數據由2維降為1維。比較圖1與圖2降維后的數據直方圖分布，可以看出在圖2（b）中，兩類數據在投影后得到更好的分離。由此可知PCA并不是面向分類的特征提取方法，一般情況下，由其得到的特征是最佳描述特征，而不是最佳分類特征。

2 算法提出

對于包含c類樣本的分類問題，類中的所有樣本是已知的對原始類最可能的描述。但是樣本分類時，不僅依賴對類內共性的描述，更多的是依賴于對類間差異的描述。直觀上，通過對每類單獨描述，提取最能體現類內共性和類間差異的特征，可以提高對類模式描述的準確性和全面性，從而減小分類的錯誤。提出的算法分為2個步驟，即面向分類的特征提取和分類匹配，具體算法如下：

2.1 面向分類的特征提取

（1）computeSb

（2）initialize i＝0

（3）for i＝1＋1

（4） computeSb－Swi

（5） compute eigenvectors toSb－Swi，return projection matrixWi

（6）until i＝c

（7）returnW1，W2，…，Wc

（8）end

其中：Sb，Swi，Wi分別代表類間散度矩陣，第i類的類內散度矩陣以及用于特征子空間提取的投影矩陣，與經典的LDA最大散度比準則不同，每個投影矩陣的求解采用最大散度差準則

即求得使JF（w）最大的投影矩陣w，根據廣義瑞利商極值特性，最優解是由矩陣Sb－Swi的前k個最大特征值對應的特征向量組成的投影矩陣。同傳統的LDA相比，特征提取不需要對Swi求逆，有效地避免了因Swi奇異無法求解的難題，通過計算可以分別得到c個投影矩陣。

2.2 分類匹配

（1）initialize test samplex，i＝0，feature subspace extraction matricesW1，W2，…，Wc

（2）for i＝i＋1

（3）projectxi＝

（4） Initialize j＝0

（5） for j＝j＋1

（6） calculate probability measurebetweenxiandrepresenting projection of classωjonto subspaceWi

（7） until j＝c

（8）scan nearest measure over allcclasses in i－th subspace：J（i）＝argma

（9）until i＝c

（10）scan nearest measure over all c classes and c subspaces：I＝argma

（11）returnI

（12）end

分類是通過兩層遍歷排序實現，內層遍歷求得在某一特征空間內的分類匹配排序，外層遍歷則求出在所有特征空間內的分類匹配排序，最終按照最大原則或者k緊鄰原則判斷測試樣本的所屬類別。與以往的基于距離的判別方法不同，在此按照貝葉斯規則［8］，以概率距離作為對隸屬置信度的衡量，判別時選擇具有最高置信度的類別。概率度量d用于評價待測樣本類別隸屬的置信度，在此對類內樣本的條件概率分布采用正態分布假設，即

式中：Wi，，μj，Σj——第i類的投影矩陣和轉置，以及第j類樣本的均值向量和協方差矩陣。

3 試驗與分析

實驗數據來自于數據庫UCI，選用的測試數據集描述如表1所示，其中Congressional Voting Records和Breast Cancer是簡單數據，顯而易見，分類的性能與訓練樣本數量和提取的特征數量有關。為了減小誤差，實驗采用10倍交叉驗證進行評價。

為了對比算法性能，我們選擇了線性判別方法：LDA和Fisherface［9－10］以及非線性判別方法：KPCA和KLDA作為比較對象。對比算法選擇是基于可比性上的考慮［11］，一方面選擇的兩種線性判別方法和提出的算法都是基于二階統計特性，都需要計算樣本的一二階統計矩；除此之外三者子空間的提取都需要進行特征值分解而非其他復雜的線性分解技術；另一方面，作為一種擬合非線性判別分析的方法，與基于核方法的非線性判別分析KPCA和KLDA比較可以更充分說明問題。測試是在2.2GHz AMD CPU，1G內存的計算機上進行。結果列于表2，3，4；其中m代表提取特征的維數。

表1 測試數據集描述

表2 分類性能比較 （數據集a，b）

從表2可以看出在線性可分的測試集a和b上本文方法并沒有突出優勢，5種方法的性能差距＜5%；從表3中可以看出，當原始特征維數增大后，KPCA和KLDA在分類性能提升明顯；而在具有線性不可分的測試集f和g上，PCA和LDA由于線性判別的局限，效果并不理想；而KPCA也由于PCA的本質則更適合于特征描述而非分類，KLDA則在分類上優于KPCA；而本文的方法在平均處理時間上遠低于KLDA和KPCA，且具有更高的分類識別率。

表3 分類性能比較 （數據集c，d，e）

在高維小樣本分類問題中，尤其在生物特征的識別中，類模式往往是線性不可分的，更有效的是依靠非線性判別分析；然而在非線性判別分析中普遍存在著難以選擇合適的非線性變換以及計算的高復雜性，這使得其在實際應用中受到限制。而提出的方法本質上是利用多線性判別分析分類分段擬合非線性判別分析，不但提高了分類的準確率而且保持了線性判別分析在計算上的簡捷性，特別適合于存在類重疊的情形。另一個優于PCA、LDA等單子空間方法的方面在于其靈活性，在單子空間方法中特征空間中的特征向量維數是一致的，而在多子空間方法中可以根據每類樣本的情況選擇更適合的向量維數。算法存在的不足在于計算復雜度與類的數量c有關，特別是對每一個測試樣本都需要進行c2次概率距離計算。

4 結束語

使用PCA方法和LDA方法都能大大降低原始特征空間的維數，結合這兩種方法Fisherface方法已在人臉識別中得到了的應用；然而PCA方法得到的特征是最佳描述特征而不是最佳分類特征，LDA方法則難以處理類重疊。本文提出的方法首先利用最大散度差準則對每類樣本進行線性判別分析，通過特征值分解獲得各類的投影矩陣，從而可以獲得面向分類的最佳描述特征，最后利用貝葉斯判別得到最高隸屬置信度作為判別依據。這樣，既利用了線性判別分析方法的線性計算的優點，又彌補了它們在處理類重疊和線性不可分上的不足，同時使分類器的設計更加簡潔、有效，提高了對高維復雜數據的識別率。

表4 分類性能比較 （數據集f，g）

［1］Koel Das，ZoranNenadic.An efficient discriminant－based solution for small sample size problem ［J］.Pattern Recognition，2009，42（5）：857－866.

［2］ZHU Minghan，SHAO Xiangyi.Based on the vector group Fisher linear discriminant analysis method ［J］.Computer Engineering and Applications，2011，47 （6）：205－207 （in Chi－nese）.［朱明旱，邵湘怡.基于向量組的Fisher線性鑒別分析方法 ［J］.計算機工程與應用，2011，47 （6）：205－207.］

［3］SHI Jin，HU Ming，SHI Xin.Text segmentation based on model LDA ［J］.Chinese Journal of Computer，2008，31 （10）：1865－1873 （in Chinese）.［石晶，胡明，石鑫.基于LDA模型 的 文 本 分 割 ［J］. 計 算 機 學 報，2008，31 （10）：1865－1873.］

［4］LIU Jin，ZHANG Junying，ZHAO Feng.Radar HRRP target recognition in amplitude spectrum subspace based on direct LDA［J］.Journal of Systems Engineering and Electronics，2008，30（10）：1815－1818 （in Chinese）. ［劉敬，張軍英，趙峰.基于direct LDA的幅度譜子空間雷達目標識別 ［J］.系統工程與電子技術，2008，30 （10）：1815－1818.］

［5］WU Ting，CHENG Yaqi，ZHANG Yanjun.Improved real－time anti－aliasing perspective shadow maps algorithm and its implementation［J］.Computer Engineering ＆ Design，2011，32（10）：3435－3437 （in Chinese）. ［吳婷，程亞奇，張延軍.改進的實時反走樣透視陰影圖算法及實現 ［J］.計算機工程與設計，2011，32 （10）：3435－3437.］

［6］ZHAO Chuanqiang，WANG Huiyuan.Face recognition method using improved D－LDA based on DCT ［J］.Computer Engineering and Applications，2007，43 （20）：245－248 （in Chinese）. ［趙傳強，王匯源.一種基于DCT的改進D—LDA人臉識別算法［J］.計算機工程與應用，2007，43 （20）：245－248.］

［7］Myoung SooPark，JinYoungChoi.Theoretical analysis on feature extraction capability of class－augmented PCA ［J］.Pattern Recognition，2009，42 （11）：2353－2362.

［8］DENG Haisong，MA Yizhong，SHAO Wenze.Research on meta－modeling using bayesian hierarchical priors ［J］.Journal of System Simulation，2011，23 （11）：2291－2295 （in Chinese）.［鄧海松，馬義中，邵文澤.基于貝葉斯多層先驗的元建模研究 ［J］.系統仿真學報，2011，23 （11）：2291－2295.］

［9］WANG Huize，GONG Shengrong，LIU Chunping.Fisherfaces based on fusion of global and local features［J］.Computer Engineering and Applications，2008，44 （24）：194－196 （in Chinese）. ［王慧澤，龔聲蓉，劉純平.融合全局和局部特征的Fisherfaces方法 ［J］.計算機工程與應用，2008，44 （24）：194－196.］

［10］ZHAO Song，PAN Ke，ZHANG Peiren.Face recognition using face symmetry：Symmetrical Fisherface［J］.Journal of University of Science and Technology of China，2009，39（11）：1183－1188 （in Chinese）. ［趙松，潘可，張培仁.對稱性在人臉識別中的應用：對稱Fisherface［J］.中國科學技術大學學報，2009，39 （11）：1183－1188.］

［11］Dacheng Tao.Discriminative linear and multilinear subspace methods［D］.School of Computer Science and Information Systems，Birkbeck College，University of London，2009.