曾青松
(廣州番禺職業(yè)技術(shù)學(xué)院信息工程學(xué)院,廣東 廣州 511483)
一種兩階段判別分析方法
曾青松
(廣州番禺職業(yè)技術(shù)學(xué)院信息工程學(xué)院,廣東 廣州 511483)
為了解決LDA對復(fù)雜分布數(shù)據(jù)的表達(dá)問題,本文提出了一種新的非參數(shù)形式的散度矩陣構(gòu)造方法。該方法能更好的刻畫分類邊界信息,并保留更多對分類有用的信息。同時(shí)針對小樣本問題中非參數(shù)結(jié)構(gòu)形式的類內(nèi)散度矩陣可能奇異,提出了一種兩階段鑒別分析方法對準(zhǔn)則函數(shù)進(jìn)行了最優(yōu)化求解。該方法通過奇異值分解把人臉圖像投影到混合散度矩陣的主元空間,使類內(nèi)散度矩陣在投影空間中是非奇異的,通過CS分解,從理論上分析了同時(shí)對角化散度矩陣的求解,并證明了得到的投影矩陣滿足正交約束條件。在ORL,Yale和YaleB人臉庫上測試的結(jié)果顯示,改進(jìn)的算法在性能上優(yōu)于PCA+LDA,ULDA和OLDA等子空間方法。
非參數(shù)化鑒別分析;CS分解;人臉識別;主成份分析;子空間
線性鑒別分析(Linear Discriminant Analysis,LDA)是一種有監(jiān)督的特征提取方法,其主要思想是求解投影向量使得同類樣本變得緊湊,異類樣本盡可能分開。LDA使用參數(shù)化形式的散度矩陣,且沒有包含高階的統(tǒng)計(jì)量,因此無法很好的表達(dá)數(shù)據(jù)的復(fù)雜分布。非參數(shù)鑒別分析(Nonparametric Discriminant Analysis,NDA)采用非參數(shù)形式構(gòu)造散度矩陣,更多的考慮樣本分布的局部結(jié)構(gòu)特征,能更好的刻畫分類邊界信息,強(qiáng)化分類邊界樣本的貢獻(xiàn)。Fukunaga[1]通過構(gòu)造非參數(shù)化形式的類間散度矩陣來解決兩分類問題。Li[2]和Zeng[3]擴(kuò)展了經(jīng)典的非參數(shù)鑒別分析算法,以支持多類情況,但是基于局部方法構(gòu)造的類內(nèi)散度矩陣仍然可能奇異[2]。
LDA提取的特征個(gè)數(shù)受到類別數(shù)的限制,實(shí)際使用時(shí)會遭遇小樣本問題[4]。運(yùn)用正則化方法,通過矩陣平滑可以使類內(nèi)散度矩陣Sw變得非奇異[5],但是計(jì)算量大。PCA+LDA使用PCA把特征維數(shù)從D降到N-M(N是樣本數(shù),M是類別數(shù))使Sw變得非奇異[6],但是Sw的維數(shù)由D降到N-M會損失一些鑒別信息。LDA/QR[7]首先將人臉樣本投影到一個(gè)子空間,然后在該子空間中進(jìn)行線性判別分析,不僅克服了LDA的奇異問題,而且大大降低了計(jì)算復(fù)雜度,但是由于LDA/ QR的第一步事實(shí)上是將人臉樣本投影到類間散度矩陣的值空間,從而如果樣本均值估計(jì)有偏,則會導(dǎo)致LDA/QR識別性能的下降,這就是LDA/QR的所謂對類中心估計(jì)敏感的問題。Chen證明了Sw的零空間中包含了大部分的鑒別信息,因而可以在Sw的零空間中來求解最優(yōu)化問題[8]。楊等人提出了具有統(tǒng)計(jì)不相關(guān)的圖像投影鑒別分析方法[9],Ye對此改進(jìn)并提出了ULDA(Uncorrelated LDA,ULDA)算法[10],并對ULDA進(jìn)行正交化約束擴(kuò)展提出正交LDA(Orthogonal LDA,OLDA)[11],OLDA得到的所有的鑒別向量都是相互正交的,因此即使在散度矩陣奇異的時(shí)候都可以執(zhí)行,最近被廣泛的應(yīng)用和擴(kuò)展。
文章首先運(yùn)用樣本的局部結(jié)構(gòu)特征,構(gòu)造具有非參數(shù)化形式的散度矩陣,該方法很好的刻畫分類邊界信息,突出邊界樣本對分類的貢獻(xiàn),可以應(yīng)用復(fù)雜分布數(shù)據(jù)的處理?;诰植刻卣鳂?gòu)造的散度矩陣,有效的克服樣本均值估計(jì)有偏的問題。其次通過SVD分解移除混合散度矩陣的零空間克服類內(nèi)散度矩陣奇異問題。最后通過應(yīng)用CS正交分解同時(shí)對角化散度矩陣來求解最優(yōu)化問題,并在計(jì)算過程中運(yùn)用QL分解避免了矩陣求逆操作。
假設(shè)樣本是d維的,訓(xùn)練集包含c個(gè)類C1,C2,…,Cc,其中Ck類有nk個(gè)樣本,共個(gè)樣本。設(shè)表示來自第k類的第i個(gè)樣本,則整個(gè)訓(xùn)練集表示為
在經(jīng)典LDA中,計(jì)算類間散度矩陣,只用到每一類樣本的均值與整體均值的差,很明顯,一類樣本的均值反映的是樣本的整體信息,沒有抓住邊界的結(jié)構(gòu)。Zeng等[3]從圖論的角度出發(fā),考慮樣本點(diǎn)之間的局部鄰域結(jié)構(gòu),提出一種新的矩陣的構(gòu)造方法來提升非參數(shù)鑒別分析,同時(shí)強(qiáng)化訓(xùn)練集合中樣本點(diǎn)的邊界信息和局部結(jié)構(gòu)??梢宰C明LDA的類間散度矩陣和式等價(jià)[12],
定義3Ck類樣本的局部混合鄰域均值定義為:
定義4Ck類樣本的Cl類局部類間鄰域均值定義為:
定義3和定義4中 ||·表示集合的基數(shù)。根據(jù)定義5,在計(jì)算Ck類相對于Cl局部類內(nèi)鄰域均值時(shí),首先利用類間鄰域的樣本計(jì)算出的Cl類局部類間鄰域均值x,然后以此作為中心求出x的類間鄰域Nδ(x,k)的均值。這種計(jì)算充分利用邊界附近的點(diǎn)來計(jì)算類間鄰域均值和類內(nèi)鄰域均值,刻畫了分類邊界的結(jié)構(gòu)。
定義兩個(gè)矩陣A和B的分塊劃分:A=[A1,…,Ac],那么,Sb可以看成是所有類別的均值相減,(μk-μl)(μk-μl)T,反映了Ck類和Cl類樣本均值之間的差異信息。但是如果某兩個(gè)類別差別很大,那么這兩個(gè)類別的均值的差所組成的協(xié)方差矩陣可能在Sb中占主導(dǎo)地位,如此得到的投影軸就會過于區(qū)分這兩個(gè)類別,導(dǎo)致無法很好的區(qū)分其它相近的類別。因此通過對不同類別的差值引入加權(quán)的思想,使得所得到的投影更注重不好區(qū)分的類別以及強(qiáng)化分類邊界信息。
其中α∈(0,∞)是控制參數(shù),用來調(diào)節(jié)距離比的改變速度,‖‖·表示向量范數(shù)。對那些靠近分類邊界的樣本,逼近0.5,并且當(dāng)樣本遠(yuǎn)離分類邊界的時(shí)候趨于零,因此強(qiáng)化了訓(xùn)練樣本集的邊界信息。圖1描述了類別1的樣本點(diǎn)P的局部鄰域均值
圖1 樣本點(diǎn)P的局部鄰域均值示意圖
3.1 預(yù)處理步驟
定理1如果A=QR表示 A∈Rm×n的QR分解,A=[a1,…,an] ,Q=[q1,…,qm] 是 列 分 塊 矩 陣 ,那 么span{a1,…,ak}=span{q1,…,qk},k=1,…,n。[13]
根據(jù)矩陣的知識,St的值空間和Ht的值空間相同。設(shè)Ht=QR表示 Ht的QR分解,對任意的正交矩陣W,設(shè)
考慮最優(yōu)化問題
對于小樣本問題,Sw的零空間的維數(shù)很高,然而Sw零空間中并非所有的向量都能提供有效的鑒別信息。Chen等[8]證明了N(St)=N(Sb)?N(Sw),因此Sw的有用的零空間是Sw零空間的一個(gè)子集:N(Sw)-N(St),在降維后的子空間中散度矩陣不再奇異,因此可以直接運(yùn)用經(jīng)典的LDA方法。
設(shè)Ht=QR表示Ht的QR分解,R=UΣVT表示R的奇異值分解,其中U和V是正交矩陣,包含Ht的非零奇異值,其主對角元素按照非遞減有序排列,t=rank(Ht)=rank(Sw)。由于,
設(shè) U=(U1,U2)是 U的分塊劃分,其中 U1∈?m×t,U2∈?m×(m-t),那么可以通過將數(shù)據(jù)投影到U1生成的列子空間來消除St的零空間。
綜合上述分析,首先構(gòu)造Ht,然后將最優(yōu)化問題轉(zhuǎn)化為等價(jià)問題的求解,最后通過奇異值分解,移除Ht的零空間得到一個(gè)較低維數(shù)的子空間,在這個(gè)子空間中,散度矩陣是非奇異的,因而可以直接運(yùn)用經(jīng)典的LDA方法。預(yù)處理的步驟為:
步驟1 構(gòu)造混合散度矩陣Ht;
步驟2 計(jì)算QR分解 Ht=QR,t←rank(Ht);
步驟3 計(jì)算SVD分解R=UΣVT;
步驟4 U1←U(:,1:t);
步驟5 輸出G←QU1,算法結(jié)束。
3.2 LDA/CS算法
正交化約束的LDA方法得到的投影矩陣的列向量互相正交,已有的研究證明這一類方法具有較好的性能[11]。本文提出基于CS分解的鑒別分析方法(LDA via Cos-sin decomposition,LDA/CS)。LDA/CS的目標(biāo)是求解最優(yōu)化問題,運(yùn)用CS分解算法同時(shí)對角化散度矩陣,得到正交約束的鑒別矢量,并利用QL分解避免計(jì)算過程中矩陣的求逆。
定義6矩陣X的QL分解指矩陣X能夠被分解為X=QL,其中Q∈?m×m具有列正交向量,L∈?m×n是一個(gè)下三角矩陣。
其中Q1∈?m×n,Q2∈?p×n,m<n,p<n是一個(gè)小樣本問題,如果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如前面所定義,設(shè)F=QR表示F的QR分解,即
其中Q1∈?m×n,Q2∈?p×n,Q是列正交的,R∈?n×n是一個(gè)上三角矩陣,那么通過CS分解,得到Q1=UCWT,Q2=VSWT,其中U∈?m×m,V∈?p×p是正交矩陣,W∈?n×n是非奇異矩陣,C∈?m×n和 S∈?p×n是滿足CTC+STS=I的分塊對角矩陣,因此設(shè) Z=(WTR)-1,那么
設(shè)Y=RTW,通過QL分解Y=ΦL計(jì)算正交矩陣Φ,因而Z=(WTR)-1=(LTΦT)-1=ΦR1,這樣避免求逆操作,其中R1=(LT)-1是一個(gè)上三角矩陣。因此,J(G)=tr(ZTSwZ)-1(ZTSbZ)= tr((ΦTSwΦ)-1ΦTSbΦ),設(shè)Φ*=[Φ1,Φ2,…,Φr],Φi是Φ 的第i列,r=rank(Z),因?yàn)閟pan{Z1,…,Zr}=span{Φ1,…,Φr},所以G=Φ*滿足最優(yōu)化問題。LDA/CS的主要特征是鑒別向量相互正交,也就是說變換矩陣是正交的。
考慮參數(shù)化LDA問題,由于 St=Sb+Sw,所以ZTStZ=ZT(Sb+Sw)Z=I,因此可以同時(shí)對角化Sb、Sw和St,并且是統(tǒng)計(jì)無關(guān)的。LDA/CS算法的具體步驟為:
步驟2 計(jì)算F的QR分解F=QR,其中Q=[Q1;Q2];
步驟3對Q應(yīng)用CS分解得到矩陣W;
父親離世時(shí)說了兩句話:做人要實(shí)在,不欺他人,任何時(shí)候都無事;同情他人,以禮待人,留下好評,一代一代都會有用。
步驟4 計(jì)算Y←RTW;
步驟5 計(jì)算Y的QL分解Y=ΦL;
步驟6 輸出G←[Φ1,Φ2,…,Φr],算法結(jié)束。
3.3 LDA/CS-QR算法
結(jié)合預(yù)處理和LDA/CS得到二階段組合算法(Twostage LDA via CS and QR decomposition,LDA/CS-QR),該算法有效的擴(kuò)展了現(xiàn)有的正交化方法在非參數(shù)條件下不能應(yīng)用的問題,并提高了鑒別分析的準(zhǔn)確度。LDA/CS-QR算法的步驟為:
步驟1 構(gòu)造散度矩陣Hb,Hw,和Ht,t←rank(Ht);
步驟2計(jì)算QR分解Ht=QR;
步驟3 計(jì)算SVD分解R=UΣVT,U1←U(:,1:t);
步驟6 輸出G←QU1G*,算法結(jié)束。
算法的第1步根據(jù)需要可以構(gòu)造參數(shù)化形式的散度矩陣,也可以構(gòu)造非參數(shù)化形式的散度矩陣。
本文在ORL、Yale和YaleB人臉數(shù)據(jù)庫上比較LDA/CS、LDA/CS-QR與經(jīng)典的PCA+LDA、ULDA和OLDA算法。
4.1 實(shí)驗(yàn)設(shè)置
ORL人臉數(shù)據(jù)庫包含40人共400張面部圖像,部分圖像包括了姿態(tài)、表情和面部飾物的變化。Yale人臉數(shù)據(jù)庫包含15位志愿者的165張圖片,包含光照、表情和姿態(tài)的變化,其中每個(gè)主題包含11張圖片。YaleB擴(kuò)展庫包含了38個(gè)人的16128幅9種姿態(tài)、64種光照的圖像。其中的姿態(tài)和光照變化的圖像都是在嚴(yán)格控制的條件下采集的,主要用于光照和姿態(tài)問題的建模與分析。
本文對數(shù)據(jù)庫中的所有圖像做如下的處理:圖像被歸一化為32×32像素并進(jìn)行直方圖均衡化;采用最近鄰法分類器。在每個(gè)數(shù)據(jù)庫上隨機(jī)選取P張圖像作為訓(xùn)練集,剩余的圖像作為測試集。使用20次隨機(jī)試驗(yàn)的平均識別率。實(shí)驗(yàn)中LDA/CS和LDA/CS-QR表示使用參數(shù)方法構(gòu)造散度矩陣,LDA/CS-N和LDA/CS-QR-N表示使用非參數(shù)化方法構(gòu)造散度矩陣,使用非參數(shù)方法時(shí),計(jì)算時(shí)局部鄰域參數(shù)p=5,公式中α=3。
4.2 分類實(shí)驗(yàn)
在ORL庫和Yale庫上隨機(jī)選擇了P(P=5,6,7)張人臉圖片作為訓(xùn)練集,在YaleB庫上隨機(jī)選擇P(P=5,10,20)張人臉圖片作為訓(xùn)練集,剩余的全部圖片作為測試。ORL,Yale和YaleB人臉數(shù)據(jù)庫上的實(shí)驗(yàn)結(jié)果分別列在表1,表2和表3中。從表1和表3可知LDA/CS-QR-N算法在ORL庫和YaleB庫上都取得最好的比別率。表2中,在P=6,7時(shí),LDA/ CS-QR-N算法也取得最好的識別率。
表1 在ORL人臉數(shù)據(jù)庫上的識別率比較
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人臉數(shù)據(jù)庫上的識別率比較
表3 在YaleB人臉數(shù)據(jù)庫上的識別率比較
為揭示訓(xùn)練樣本數(shù)量對識別率的影響,在ORL和Yale數(shù)據(jù)庫中隨機(jī)選擇P(P=3,4,5,6,7,8)張圖像作為測試集。圖2(a)和圖2(b)分別列出了各種算法在ORL和Yale庫上的比較結(jié)果。分析圖2得出:所有算法隨著訓(xùn)練樣本的增加,識別率都穩(wěn)定上升。圖2(a)表明選擇不同的數(shù)量的訓(xùn)練樣本時(shí),LDA/ CS-N和LDA/CS-QR-N算法的識別率高于PCA+LDA和ULDA算法,但是與OLDA算法相當(dāng)。圖2(b)顯示在訓(xùn)練樣本較多的時(shí)候,LDA/CS-QR-N取得比OLDA更好的識別率。
圖2 ORL庫和Yale庫上識別率隨鑒別矢量個(gè)數(shù)的變化趨勢
4.3 鑒別向量數(shù)量對分類準(zhǔn)確度的影響實(shí)驗(yàn)
從表1~表3的結(jié)果發(fā)現(xiàn)OLDA算法和LDA/CS-QR算法的最佳識別率在所有數(shù)據(jù)庫中測試結(jié)果相同,但是由于選擇不同數(shù)量的鑒別向量會對識別率差生一定的影響。為進(jìn)一步揭示兩個(gè)算法的區(qū)別,在ORL庫和Yale庫隨機(jī)選擇P=7幅圖像作為訓(xùn)練集,YaleB庫隨機(jī)選擇P=10幅圖像作為訓(xùn)練集,其它全部圖像作為測試集。比較了選擇不同數(shù)量的特征向量LDA/CS和LDA/CS-QR算法的性能,并與PCA+LDA、ULDA、OLDA算法比較。圖3(a)、圖3(b)和圖3(c)分別列出了ORL、Yale和YaleB庫上的比較結(jié)果。分析圖3,發(fā)現(xiàn)LDA/CS和LDA/CS-QR算法在選擇較少的特征向量就能達(dá)到比較穩(wěn)定的識別率,并且LDA/CS-QR算法在選擇較少特征向量時(shí)比其它算法識別率更高,并且識別率曲線的斜率比較大,說明隨著選擇的特征向量數(shù)量的增加,識別率更快的趨于穩(wěn)定的值。
圖3 特征向量數(shù)量與識別結(jié)果之間的關(guān)系
4.4 參數(shù)化方法與非參數(shù)化方法比較
分析表1-3的結(jié)果,發(fā)現(xiàn)使用參數(shù)化方法和非參數(shù)化方法構(gòu)造散度矩陣時(shí),尤其是在非參數(shù)化條件下,改進(jìn)的算法性能更好。
如圖4所示,LDA/CS-N和LDA/CS-QR-N在特征向量較少時(shí)識別率更高。在ORL和Yale庫等很少樣本的數(shù)據(jù)庫中測試,如圖4(a)和(b)所示,非參數(shù)方法比參數(shù)方法性能更好。
圖4 參數(shù)化與非參化數(shù)構(gòu)造散度矩陣的識別率比較
本文從樣本的局部鄰域出發(fā),利用樣本局部結(jié)構(gòu)信息構(gòu)造散度矩陣,通過強(qiáng)化分類邊界結(jié)構(gòu)有效的提取鑒別信息。對于人臉識別等小樣本問題,通過局部方法構(gòu)造的類內(nèi)散度矩陣可能是奇異的,因此文章提出了一種兩階段的非參數(shù)鑒別分析算法,通過去除混合散度矩陣的零空間有效的解決散度矩陣奇異問題,并通過QL分解有效的避免計(jì)算過程矩陣求逆問題。在ORL,Yale和YaleB人臉庫上的實(shí)驗(yàn)結(jié)果說明算法比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鑒別極小準(zhǔn)則的特征提取方法[J].計(jì)算機(jī)研究與發(fā)展,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.(楊鍵,楊靜宇.具有統(tǒng)計(jì)不相關(guān)的圖像投影鑒別分析及人臉識別[J].計(jì)算機(jī)研究與發(fā)展,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
曾青松,男,湖南邵東人,博士,副教授,研究方向:模式識別,數(shù)據(jù)挖掘。
廣東省自然科學(xué)基金:基于圖像集的人臉識別若干關(guān)鍵技術(shù)研究,項(xiàng)目編號:2015A030313807。