董 琰

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

0 引 言

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

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

1 相關(guān)技術(shù)

LDA［3］是統(tǒng)計模式識別中最基本和常用的分類方法，其準(zhǔn)則函數(shù)如下

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

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

圖1 PCA用于兩類分類示例

圖2 考慮分類后的PCA及分類結(jié)果

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

2 算法提出

對于包含c類樣本的分類問題，類中的所有樣本是已知的對原始類最可能的描述。但是樣本分類時，不僅依賴對類內(nèi)共性的描述，更多的是依賴于對類間差異的描述。直觀上，通過對每類單獨描述，提取最能體現(xiàn)類內(nèi)共性和類間差異的特征，可以提高對類模式描述的準(zhǔn)確性和全面性，從而減小分類的錯誤。提出的算法分為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類的類內(nèi)散度矩陣以及用于特征子空間提取的投影矩陣，與經(jīng)典的LDA最大散度比準(zhǔn)則不同，每個投影矩陣的求解采用最大散度差準(zhǔn)則

即求得使JF（w）最大的投影矩陣w，根據(jù)廣義瑞利商極值特性，最優(yōu)解是由矩陣Sb－Swi的前k個最大特征值對應(yīng)的特征向量組成的投影矩陣。同傳統(tǒng)的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(luò)＋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

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

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

3 試驗與分析

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

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

表1 測試數(shù)據(jù)集描述

表2 分類性能比較 （數(shù)據(jù)集a，b）

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

表3 分類性能比較 （數(shù)據(jù)集c，d，e）

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

4 結(jié)束語

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

表4 分類性能比較 （數(shù)據(jù)集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］.計算機工程與應(yīng)用，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］. 計 算 機 學(xué) 報，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的幅度譜子空間雷達(dá)目標(biāo)識別 ［J］.系統(tǒng)工程與電子技術(shù)，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ìn)的實時反走樣透視陰影圖算法及實現(xiàn) ［J］.計算機工程與設(shè)計，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的改進(jìn)D—LDA人臉識別算法［J］.計算機工程與應(yīng)用，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］.系統(tǒng)仿真學(xué)報，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］.計算機工程與應(yīng)用，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）. ［趙松，潘可，張培仁.對稱性在人臉識別中的應(yīng)用：對稱Fisherface［J］.中國科學(xué)技術(shù)大學(xué)學(xué)報，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.