一種兩階段判別分析方法

曾青松

（廣州番禺職業技術學院信息工程學院，廣東 廣州 511483）

一種兩階段判別分析方法

曾青松

（廣州番禺職業技術學院信息工程學院，廣東 廣州 511483）

為了解決LDA對復雜分布數據的表達問題，本文提出了一種新的非參數形式的散度矩陣構造方法。該方法能更好的刻畫分類邊界信息，并保留更多對分類有用的信息。同時針對小樣本問題中非參數結構形式的類內散度矩陣可能奇異，提出了一種兩階段鑒別分析方法對準則函數進行了最優化求解。該方法通過奇異值分解把人臉圖像投影到混合散度矩陣的主元空間，使類內散度矩陣在投影空間中是非奇異的，通過CS分解，從理論上分析了同時對角化散度矩陣的求解，并證明了得到的投影矩陣滿足正交約束條件。在ORL，Yale和YaleB人臉庫上測試的結果顯示，改進的算法在性能上優于PCA+LDA，ULDA和OLDA等子空間方法。

非參數化鑒別分析；CS分解；人臉識別；主成份分析；子空間

1 引言

線性鑒別分析(Linear Discriminant Analysis，LDA)是一種有監督的特征提取方法，其主要思想是求解投影向量使得同類樣本變得緊湊，異類樣本盡可能分開。LDA使用參數化形式的散度矩陣，且沒有包含高階的統計量，因此無法很好的表達數據的復雜分布。非參數鑒別分析(Nonparametric Discriminant Analysis,NDA)采用非參數形式構造散度矩陣，更多的考慮樣本分布的局部結構特征，能更好的刻畫分類邊界信息，強化分類邊界樣本的貢獻。Fukunaga[1]通過構造非參數化形式的類間散度矩陣來解決兩分類問題。Li[2]和Zeng[3]擴展了經典的非參數鑒別分析算法，以支持多類情況，但是基于局部方法構造的類內散度矩陣仍然可能奇異[2]。

LDA提取的特征個數受到類別數的限制，實際使用時會遭遇小樣本問題[4]。運用正則化方法，通過矩陣平滑可以使類內散度矩陣Sw變得非奇異[5]，但是計算量大。PCA+LDA使用PCA把特征維數從D降到N-M(N是樣本數，M是類別數)使Sw變得非奇異[6]，但是Sw的維數由D降到N-M會損失一些鑒別信息。LDA/QR[7]首先將人臉樣本投影到一個子空間，然后在該子空間中進行線性判別分析，不僅克服了LDA的奇異問題，而且大大降低了計算復雜度，但是由于LDA/ QR的第一步事實上是將人臉樣本投影到類間散度矩陣的值空間，從而如果樣本均值估計有偏，則會導致LDA/QR識別性能的下降，這就是LDA/QR的所謂對類中心估計敏感的問題。Chen證明了Sw的零空間中包含了大部分的鑒別信息，因而可以在Sw的零空間中來求解最優化問題[8]。楊等人提出了具有統計不相關的圖像投影鑒別分析方法[9]，Ye對此改進并提出了ULDA(Uncorrelated LDA，ULDA)算法[10]，并對ULDA進行正交化約束擴展提出正交LDA(Orthogonal LDA，OLDA)[11]，OLDA得到的所有的鑒別向量都是相互正交的，因此即使在散度矩陣奇異的時候都可以執行，最近被廣泛的應用和擴展。

文章首先運用樣本的局部結構特征，構造具有非參數化形式的散度矩陣，該方法很好的刻畫分類邊界信息，突出邊界樣本對分類的貢獻，可以應用復雜分布數據的處理。基于局部特征構造的散度矩陣，有效的克服樣本均值估計有偏的問題。其次通過SVD分解移除混合散度矩陣的零空間克服類內散度矩陣奇異問題。最后通過應用CS正交分解同時對角化散度矩陣來求解最優化問題，并在計算過程中運用QL分解避免了矩陣求逆操作。

2 非參數散度矩陣的構造

假設樣本是d維的，訓練集包含c個類C1，C2，…，Cc，其中Ck類有nk個樣本，共個樣本。設表示來自第k類的第i個樣本，則整個訓練集表示為

在經典LDA中，計算類間散度矩陣，只用到每一類樣本的均值與整體均值的差，很明顯，一類樣本的均值反映的是樣本的整體信息，沒有抓住邊界的結構。Zeng等[3]從圖論的角度出發，考慮樣本點之間的局部鄰域結構，提出一種新的矩陣的構造方法來提升非參數鑒別分析，同時強化訓練集合中樣本點的邊界信息和局部結構。可以證明LDA的類間散度矩陣和式等價[12]，

定義3Ck類樣本的局部混合鄰域均值定義為：

定義4Ck類樣本的Cl類局部類間鄰域均值定義為：

定義3和定義4中 ||·表示集合的基數。根據定義5，在計算Ck類相對于Cl局部類內鄰域均值時，首先利用類間鄰域的樣本計算出的Cl類局部類間鄰域均值x，然后以此作為中心求出x的類間鄰域Nδ(x,k)的均值。這種計算充分利用邊界附近的點來計算類間鄰域均值和類內鄰域均值，刻畫了分類邊界的結構。

定義兩個矩陣A和B的分塊劃分：A=[A1,…,Ac]，那么，Sb可以看成是所有類別的均值相減，(μk-μl)(μk-μl)T，反映了Ck類和Cl類樣本均值之間的差異信息。但是如果某兩個類別差別很大，那么這兩個類別的均值的差所組成的協方差矩陣可能在Sb中占主導地位，如此得到的投影軸就會過于區分這兩個類別，導致無法很好的區分其它相近的類別。因此通過對不同類別的差值引入加權的思想，使得所得到的投影更注重不好區分的類別以及強化分類邊界信息。

其中α∈(0,∞)是控制參數，用來調節距離比的改變速度，‖‖·表示向量范數。對那些靠近分類邊界的樣本，逼近0.5，并且當樣本遠離分類邊界的時候趨于零，因此強化了訓練樣本集的邊界信息。圖1描述了類別1的樣本點P的局部鄰域均值

圖1 樣本點P的局部鄰域均值示意圖

3 兩階段鑒別分析算法

3.1 預處理步驟

定理1如果A＝QR表示 A∈Rm×n的QR分解，A＝[a1,…,an] ，Q＝[q1,…,qm] 是 列 分 塊 矩 陣 ，那 么span{a1,…,ak}=span{q1,…,qk}，k=1，…，n。[13]

根據矩陣的知識，St的值空間和Ht的值空間相同。設Ht=QR表示 Ht的QR分解，對任意的正交矩陣W，設

考慮最優化問題

對于小樣本問題，Sw的零空間的維數很高，然而Sw零空間中并非所有的向量都能提供有效的鑒別信息。Chen等[8]證明了N(St)=N(Sb)?N(Sw)，因此Sw的有用的零空間是Sw零空間的一個子集:N(Sw)-N(St)，在降維后的子空間中散度矩陣不再奇異，因此可以直接運用經典的LDA方法。

設Ht=QR表示Ht的QR分解，R=UΣVT表示R的奇異值分解，其中U和V是正交矩陣，包含Ht的非零奇異值，其主對角元素按照非遞減有序排列，t=rank(Ht)=rank(Sw)。由于，

設 U=(U1,U2)是 U的分塊劃分，其中 U1∈?m×t，U2∈?m×(m-t)，那么可以通過將數據投影到U1生成的列子空間來消除St的零空間。

綜合上述分析，首先構造Ht，然后將最優化問題轉化為等價問題的求解，最后通過奇異值分解，移除Ht的零空間得到一個較低維數的子空間，在這個子空間中，散度矩陣是非奇異的，因而可以直接運用經典的LDA方法。預處理的步驟為：

步驟1 構造混合散度矩陣Ht；

步驟2 計算QR分解 Ht=QR,t←rank(Ht)；

步驟3 計算SVD分解R=UΣVT；

步驟4 U1←U(:,1:t)；

步驟5 輸出G←QU1，算法結束。

3.2 LDA/CS算法

正交化約束的LDA方法得到的投影矩陣的列向量互相正交，已有的研究證明這一類方法具有較好的性能[11]。本文提出基于CS分解的鑒別分析方法(LDA via Cos-sin decomposition，LDA/CS)。LDA/CS的目標是求解最優化問題，運用CS分解算法同時對角化散度矩陣，得到正交約束的鑒別矢量，并利用QL分解避免計算過程中矩陣的求逆。

定義6矩陣X的QL分解指矩陣X能夠被分解為X=QL，其中Q∈?m×m具有列正交向量，L∈?m×n是一個下三角矩陣。

其中Q1∈?m×n，Q2∈?p×n，m＜n，p＜n是一個小樣本問題，如果Q是列正交的，那么存在正交矩陣U∈?m×m，V∈?p×p以及非奇異矩陣W∈?n×n和分塊對角化矩陣C∈?m×n，S∈?p×n滿足Q1=UCWT，Q2=VSWT，即

其中CTC+STS=I。

如果Sb，Sw，Hb和Hw如前面所定義，設F=QR表示F的QR分解，即

其中Q1∈?m×n，Q2∈?p×n，Q是列正交的，R∈?n×n是一個上三角矩陣，那么通過CS分解，得到Q1=UCWT，Q2=VSWT，其中U∈?m×m，V∈?p×p是正交矩陣，W∈?n×n是非奇異矩陣，C∈?m×n和 S∈?p×n是滿足CTC+STS=I的分塊對角矩陣，因此設 Z=(WTR)-1，那么

設Y=RTW，通過QL分解Y=ΦL計算正交矩陣Φ，因而Z=(WTR)-1=(LTΦT)-1=ΦR1，這樣避免求逆操作，其中R1=(LT)-1是一個上三角矩陣。因此，J(G)=tr(ZTSwZ)-1(ZTSbZ)= tr((ΦTSwΦ)-1ΦTSbΦ)，設Φ*=[Φ1,Φ2,…,Φr]，Φi是Φ 的第i列，r=rank(Z)，因為span{Z1,…,Zr}=span{Φ1,…,Φr}，所以G=Φ*滿足最優化問題。LDA/CS的主要特征是鑒別向量相互正交，也就是說變換矩陣是正交的。

考慮參數化LDA問題，由于 St=Sb+Sw，所以ZTStZ=ZT(Sb+Sw)Z=I，因此可以同時對角化Sb、Sw和St，并且是統計無關的。LDA/CS算法的具體步驟為：

步驟2 計算F的QR分解F=QR,其中Q=[Q1;Q2]；

步驟3對Q應用CS分解得到矩陣W；

父親離世時說了兩句話：做人要實在，不欺他人，任何時候都無事；同情他人，以禮待人，留下好評，一代一代都會有用。

步驟4 計算Y←RTW；

步驟5 計算Y的QL分解Y=ΦL；

步驟6 輸出G←[Φ1,Φ2,…,Φr]，算法結束。

3.3 LDA/CS-QR算法

結合預處理和LDA/CS得到二階段組合算法(Twostage LDA via CS and QR decomposition，LDA/CS-QR)，該算法有效的擴展了現有的正交化方法在非參數條件下不能應用的問題，并提高了鑒別分析的準確度。LDA/CS-QR算法的步驟為：

步驟1 構造散度矩陣Hb，Hw，和Ht，t←rank(Ht)；

步驟2計算QR分解Ht=QR；

步驟3 計算SVD分解R=UΣVT，U1←U(:,1:t)；

步驟6 輸出G←QU1G*，算法結束。

算法的第1步根據需要可以構造參數化形式的散度矩陣，也可以構造非參數化形式的散度矩陣。

4 實驗結果

本文在ORL、Yale和YaleB人臉數據庫上比較LDA/CS、LDA/CS-QR與經典的PCA+LDA、ULDA和OLDA算法。

4.1 實驗設置

ORL人臉數據庫包含40人共400張面部圖像，部分圖像包括了姿態、表情和面部飾物的變化。Yale人臉數據庫包含15位志愿者的165張圖片，包含光照、表情和姿態的變化，其中每個主題包含11張圖片。YaleB擴展庫包含了38個人的16128幅9種姿態、64種光照的圖像。其中的姿態和光照變化的圖像都是在嚴格控制的條件下采集的，主要用于光照和姿態問題的建模與分析。

本文對數據庫中的所有圖像做如下的處理：圖像被歸一化為32×32像素并進行直方圖均衡化；采用最近鄰法分類器。在每個數據庫上隨機選取P張圖像作為訓練集，剩余的圖像作為測試集。使用20次隨機試驗的平均識別率。實驗中LDA/CS和LDA/CS-QR表示使用參數方法構造散度矩陣，LDA/CS-N和LDA/CS-QR-N表示使用非參數化方法構造散度矩陣，使用非參數方法時，計算時局部鄰域參數p=5，公式中α=3。

4.2 分類實驗

在ORL庫和Yale庫上隨機選擇了P（P=5,6,7）張人臉圖片作為訓練集，在YaleB庫上隨機選擇P（P=5,10,20）張人臉圖片作為訓練集，剩余的全部圖片作為測試。ORL，Yale和YaleB人臉數據庫上的實驗結果分別列在表1，表2和表3中。從表1和表3可知LDA/CS-QR-N算法在ORL庫和YaleB庫上都取得最好的比別率。表2中，在P=6，7時，LDA/ CS-QR-N算法也取得最好的識別率。

表1 在ORL人臉數據庫上的識別率比較

LDA/CS-N LDA/CS-QR-N 96.55±1.71 96.75±1.78 97.75±1.32 98.00±1.13 97.08±1.37 97.42±1.39

表2 在Yale人臉數據庫上的識別率比較

表3 在YaleB人臉數據庫上的識別率比較

為揭示訓練樣本數量對識別率的影響，在ORL和Yale數據庫中隨機選擇P(P=3,4,5,6,7,8)張圖像作為測試集。圖2(a)和圖2(b)分別列出了各種算法在ORL和Yale庫上的比較結果。分析圖2得出：所有算法隨著訓練樣本的增加，識別率都穩定上升。圖2(a)表明選擇不同的數量的訓練樣本時，LDA/ CS-N和LDA/CS-QR-N算法的識別率高于PCA+LDA和ULDA算法，但是與OLDA算法相當。圖2(b)顯示在訓練樣本較多的時候，LDA/CS-QR-N取得比OLDA更好的識別率。

圖2 ORL庫和Yale庫上識別率隨鑒別矢量個數的變化趨勢

4.3 鑒別向量數量對分類準確度的影響實驗

從表1～表3的結果發現OLDA算法和LDA/CS-QR算法的最佳識別率在所有數據庫中測試結果相同，但是由于選擇不同數量的鑒別向量會對識別率差生一定的影響。為進一步揭示兩個算法的區別，在ORL庫和Yale庫隨機選擇P=7幅圖像作為訓練集，YaleB庫隨機選擇P=10幅圖像作為訓練集，其它全部圖像作為測試集。比較了選擇不同數量的特征向量LDA/CS和LDA/CS-QR算法的性能，并與PCA+LDA、ULDA、OLDA算法比較。圖3(a)、圖3(b)和圖3(c)分別列出了ORL、Yale和YaleB庫上的比較結果。分析圖3，發現LDA/CS和LDA/CS-QR算法在選擇較少的特征向量就能達到比較穩定的識別率，并且LDA/CS-QR算法在選擇較少特征向量時比其它算法識別率更高，并且識別率曲線的斜率比較大，說明隨著選擇的特征向量數量的增加，識別率更快的趨于穩定的值。

圖3 特征向量數量與識別結果之間的關系

4.4 參數化方法與非參數化方法比較

分析表1-3的結果，發現使用參數化方法和非參數化方法構造散度矩陣時，尤其是在非參數化條件下，改進的算法性能更好。

如圖4所示，LDA/CS-N和LDA/CS-QR-N在特征向量較少時識別率更高。在ORL和Yale庫等很少樣本的數據庫中測試，如圖4(a)和(b)所示，非參數方法比參數方法性能更好。

圖4 參數化與非參化數構造散度矩陣的識別率比較

5 結束語

本文從樣本的局部鄰域出發，利用樣本局部結構信息構造散度矩陣，通過強化分類邊界結構有效的提取鑒別信息。對于人臉識別等小樣本問題，通過局部方法構造的類內散度矩陣可能是奇異的，因此文章提出了一種兩階段的非參數鑒別分析算法，通過去除混合散度矩陣的零空間有效的解決散度矩陣奇異問題，并通過QL分解有效的避免計算過程矩陣求逆問題。在ORL，Yale和YaleB人臉庫上的實驗結果說明算法比PCA+LDA，ULDA和OLDA有更高的識別率。

[1]Fukunaga K，Mantock J M．Nonparametric Discriminant Analysis [J].Pattern Analysis and Machine Intelligence，IEEE Transactions on，1983，5(6)：671-678．

[2]Li Z，Lin D，Tang X．Nonparametric discriminant analysis for face recognition[J]．Pattern Analysis and Machine Intelligence，IEEE Transac?tions on，2009，31(4)：755-61．

[3]Zeng Q，Wang C．NPDA/CS：Improved Non-parametric Dis?criminant Analysis with CS Decomposition and its Application to Face Recorgnition[C]．Image Processing(ICIP)，2010 17th IEEE International Conference on，Hong Kong，2010：4537-4540．

[4]Zheng Yujie，Yang Jingyu，Xu Yong，et al．A New Feature Extrac?tion Method Based on Fisher Discriminant Minimal Criterion[J]．Journal of Computer Research and Development，2006，43(7)：1201-1206．（鄭宇杰，楊靜宇，徐勇，等．一種基于Fisher鑒別極小準則的特征提取方法[J].計算機研究與發展，2006，43(7)：1201-1206．）

[5]Dai D-Q，Yuen P C．Regularized discriminant analysis and its ap?plication to face recognition[J]．Pattern Recognition，2003，36(3)：845-847．

[6]Belhumeur P N，Hespanha J P，Kriegman D J．Eigenfaces vs．Fish?erfaces：recognition using class specific linear projection[J]．Pattern Analysis and Machine Intelligence，IEEE Transactions on，1997，19(7)：711-720．

[7]Ye J，Li Q．A two-stage linear discriminant analysis via QR-de?composition[J]．IEEE Trans Pattern Anal Mach Intell，2005，27(6)：929-41．

[8]Chen L．A new LDA-based face recognition system which can solve the small sample size problem[J]．Pattern Recognition，2000，33(10)：1713-1726．

[9]Yang Jian，Yang Jingyu．Uncorrelated image projection discrimi?nant analysis and face recorgnition[J]．Journal of Computer Research and Development，2003，40(3)：447-452．（楊鍵，楊靜宇．具有統計不相關的圖像投影鑒別分析及人臉識別[J]．計算機研究與發展，2003，40(3)：447-452．）

[10]Ye J，Li T，Xiong T，et al．Using Uncorrelated Discriminant Anal?ysis for Tissue Classification with Gene Expression Data[J]．IEEE/ACM Transactions on Computational Biology and Bioinformatics，2004，1(4)：181-190．

[11]Ye J．Characterization of a Family of Algorithms for Generalized Discriminant Analysis on Undersampled Problems[J]．J．Mach．Learn．Res．，2005(6)：483-502．

[12]Price J R，Gee T F．Face Recognition Using Direct，Weighted Linear Discriminant Analysis and Modular Subspaces[J]．Pattern Recogni?tion，2005，38(2)：209-219．

[13]Golub G，Van Loan C．Matrix computations[M]．Johns Hopkins University Press，1996．

ATwo-stage DiscriminantAnalysis Method

Zeng Qingsong
(School of Information and Technology,Guangzhou Panyu Polytechnic,Guangzhou 511483,Guandong)

In order to tackle the problem of representing the distribution of complicated data using LDA,this paper proposes a novel method for constructing the non-parametric scatter matrix.Compared to classical LDA,our method can describe the classification boundary in a better way while preserving more useful information for classification.Since the non-parametric within-class scatter matrix may be singular for small sample-size problem,we propose a two-stage discriminant analysis method to optimize the criterion function.The human face images are projected onto the principal component subspace of the mixture scatter matrix via SVD so that the within-class scatter matrix in the projection subspace is singular.Via CS decomposition,we theoretically analyze the problem of solving the diagonal scatter matrix and prove that the projection matrix satisfies the orthogonally constraint.The experimental results on three face databases,i.e.,the ORL database,the Yale database and the YaleB database,demonstrate the improvement of the proposed method over the traditional subspace methods.

non-parametric discriminant analysis;cosine-sine decomposition;face recognition;PCA;subspace

TP391.41

A

1008-6609(2016)05-0014-06

曾青松，男，湖南邵東人，博士，副教授，研究方向：模式識別，數據挖掘。

廣東省自然科學基金：基于圖像集的人臉識別若干關鍵技術研究，項目編號：2015A030313807。