基于核理論的非線性鑒別分析方法的研究

楊旭+業(yè)寧+李勇智

摘要：人臉識(shí)別是模式識(shí)別領(lǐng)域中一個(gè)比較熱的研究課題。人臉一般是高維數(shù)據(jù)，我們需要通過對(duì)數(shù)據(jù)降維進(jìn)行特征提取，就是將原始數(shù)據(jù)對(duì)應(yīng)的高維空間數(shù)據(jù)映射到低維空間中，在低維空間中進(jìn)行線性的鑒別分析。由于實(shí)際問題中原始樣本的分布通常是非線性的，該文運(yùn)用核方法，將PCA和FDA進(jìn)行了非線性推廣，比較了核主成分分析（KPCA）和核Fisher判別分析（KFDA）以及核最大間距準(zhǔn)則（KMMC）三種非線性特征提取方法。

關(guān)鍵詞：特征提?。蝗四樧R(shí)別；核主成分分析；核Fisher判別方法；核最大間距準(zhǔn)則

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）04-0191-04

A Study on the Nonlinear Discriminant Analysis Method Based on the Kernel Theory

YANG Xu，YE Ning， LI Yong-zhi

（School of Information Science and Technology， Nanjing Forestry University， Nanjing 210037， China）

Abstract ： Face recognition is a hot research topic in the field of pattern recognition. Face is generally high dimensional data， so We need to extract the feature of data dimension reduction . That is to say，we should map the original data to the high dimensional data to the low dimensional space and do the linear discriminant analysis in low dimensional space. Because the distribution of the original sample is usually non-linear in the practical problems， This paper uses kernel method and carries out the PCA and FDA in a nonlinear extension.In addition，it compares the kernel principal component analysis （KPCA） and kernel Fisher discriminant analysis （KFDA） as well as the kernel maximum space criterion （KMMC） for three kinds of nonlinear feature extraction meth ods.

Key words： feature extraction； face recognition； KPCA； KFDA； KMMC

人臉識(shí)別是基于人的臉部特征信息而進(jìn)行的身份識(shí)別的一種生物識(shí)別技術(shù)。在核函數(shù)還沒被運(yùn)用到模式識(shí)別中之前，一般都采用線性算法在低維空間中進(jìn)行模式分析。但是往往遇到高維的或者非線性的運(yùn)算，線性算法就會(huì)存在局限性。自從核函數(shù)出現(xiàn)后，人們發(fā)現(xiàn)了用核方法的模式識(shí)別算法可以更好地解決了非線性問題。

1 基于核方法的特征提取

核方法運(yùn)用到了核映射。人臉的實(shí)際的原始數(shù)據(jù)一般都是高維的，在高維空間里是非線性的。這時(shí)就需要用核方法用非線性映射將原始數(shù)據(jù)由高維空間映射到了低維特征空間上，然后在特征空間中運(yùn)用線性算法。

定義一個(gè)非線性映射：

[ f：x∈Rn→fx∈F] （1）

可得到相應(yīng)的核函數(shù)為：

[ kx，y=fx，fy] （2）

其中[，]表示在特征空間F上的內(nèi)積運(yùn)算。

因此，常用的核函數(shù)有：

多項(xiàng)式核函數(shù)：

[kx，y=ax?y+bd] [d>0]且[a，b∈R] （3）

高斯核函數(shù)（徑向基核函數(shù)）：

[kx，y=e-x-y2∕σ2] [σ∈R] （4）

Sigmoid核函數(shù)：

[ kx，y=tanhvx?y+c] [v，c∈R] （5）

2 核主成分分析方法（KPCA）的數(shù)學(xué)模型

現(xiàn)設(shè)有訓(xùn)練集[S：x1，x2，…，xN∈Χ]，核映射[Φ]將它們映射到核空間[F]中，核空間中的訓(xùn)練集為[lx1，lx2，…lxn]。記[Χ=x1，x2，…，xN，lΧ=lx1，lx2，…lxn]。

在核空間中對(duì)子空間進(jìn)行降維變換，即

[y=wTlx] （6）

降維變換又稱投影變換，w就是它的投影方向。降維后數(shù)據(jù)總體的離散度為

[Clt=1Ni=1Nyi-yyi-yT=wT1Ni=1Nlxi-llxi-lT w=wTSl tw] （7）

其中，[l=1Ni=1Nlxi]是核空間中的樣本均值。

將核空間中的樣本中心化，即令[lxi=lxi-l]，

并記[lX=lx1，lx2，…，lxN] ，則核空間中的總體樣本協(xié)方差陣為

[Slt=1Ni=1Nlxi-llxi-lT=1Ni=1NlxilxiT=1NlXlXT] （8）

核空間中的PCA的最大準(zhǔn)則函數(shù)為：

[max JKPCAw=wTSltw ] （9）

由于最大化[JKPCAw]就是對(duì)[Slt]作特征值分解，w就是[Slt]的特征向量，因此有

[ λw=Sltw=1Ni=1NlxilxiTw=i=1N1NlxiTwlxi] （10）

令

[w=i=1Nαilxi=lXα] （11）

其中[α=α1，α2，…，αNT]是線性組合系數(shù)。

首先將公式（11）代入式（6）中，有

[y=wTlx=αTlxTlx=αTlx-lxENTlx]

[=αTkX，x-ENkX，x] （12）

其中[kX，x=kx1，x，kx2，x，…，kxN，xT]，[EN]為元素[1∕N]的N階矩陣。

將式（11）代入準(zhǔn)則函數(shù)式（9）中，并結(jié)合式（8），有

[ JKPCAw=wTSltw=1NαTlXTSltlXα=1NαTlXTlX2α=1NαTK2α ] [（13）]

其中

[K=lXTlX=lX-lXENTlX-lXEN]

[=K-ENK-KEN+ENKEN] （14）

K為式（15）定義的核矩陣。對(duì)核空間中的總體樣本協(xié)方差陣[Slt]作特征值分解：

[Sltw=λ∕Nw] （15）

其中N是樣本容量。將式（11）代入式（15），并兩邊同時(shí)左乘[lXT]，有

[lXTSltlXα=λ∕NlXTlXα] （16）

根據(jù)式（13）和（14），可將式（16）寫為

[ K2α=λKα] （17）

簡(jiǎn)化得：

[Kα=λα] （18）

即最佳組合系數(shù)[α]就是矩陣[K]的最大特征值所對(duì)應(yīng)的特征向量。

一般令[wTw=1]。

由于

[wTw=αTlXTlXα=λαTα] （19）

所以組合系數(shù)應(yīng)滿足的條件為

[λαTα=1] （20）

其中[λ]是特征向量[α]所對(duì)應(yīng)的特征值。

3 核Fisher判別分析方法（KFDA）的數(shù)學(xué)模型

訓(xùn)練樣本集[x1，x2，…，xN ]經(jīng)過非線性映射[Φ]后，訓(xùn)練樣本為[Φxii=1，…，N]在特征空間[F]上的類間散度矩陣[Sφb]、類內(nèi)散度矩陣[Sφw]，以及總體散度矩陣[Sφt]為：

[Sφb=i=1CNimφi-mφmφi-mφT] （21）

[ Sφw=i=1Cj=1NiΦxj-mφiΦxj-mφiT] （22）

[ Sφt= Sφw+Sφb=i=1NΦxi-mφΦxi-mφT] （23）

其中[mφi=1Nij=1NiΦxj]為第[Ci]類樣本在特征空間[F]上的均值向量，

[mφ=1Nj=1NΦxj]為所有訓(xùn)練樣本在特征空間[F]上的均值向量。

特征空間[F]中廣義的Fisher判別準(zhǔn)則函數(shù)為：

[maxJφw=WTSφbWWTSφtW] （24）

要使Fisher判別準(zhǔn)則函數(shù)最大化，就要要尋找一組最優(yōu)判別向量[w=w1，w2，…，wd]。

由于[maxJφw]，[w∈F]，因此，[w1，w2，…，wd]即為特征方程[Sφbw=λSφtw ]的前[d]個(gè)最大特征值所對(duì)應(yīng)的單位特征向量。

任何一個(gè)最優(yōu)化準(zhǔn)則函數(shù)式（24）的解向量[w]一定位于特征空間[F]中。所以[w]在訓(xùn)練樣本[Φx1]，[Φx2，…，ΦxN]所生成的空間內(nèi)，即

[w∈spanΦx1，Φx2，…，ΦxN]，則有：

[w=i=1NαiΦxi=Qα] （25）

其中：[Q=Φx1，Φx2，…，ΦxN]，

[α=α1，α2，…，αNT∈RN]

把特征空間[F]中的樣本[Φx]投影到[w]上，則有：

[wTΦx=i=1Nαikxi，x=αTkx1，x，…，kxN，xT=αTξX] （26）

其中，[ξx=kx1，x，…，kxN，xT]為核樣本向量。[α]為特征空間[F]中最佳判別向量[w]的最佳核判別向量。

把特征空間[F]中的訓(xùn)練樣本類均值向量和總體均值向量分別投影到[w]上：

[wTmφi=αT1Nij=1NiΦTx1Φxj，…，ΦTxNΦxjT=αTμi] （27）

[wTmφ=αT1Nj=1NΦTx1Φxj，…，ΦTxNΦxjT=αTμ] （28）

其中：

[μi=1Nij=1NiΦTx1Φxj，…，1Nij=1NiΦTxNΦxjT] （29）

[μ=1Nj=1NΦTx1Φxj，…，1Nj=1NΦTxNΦxjT] （30）

由（27）式和（28）式可得：

[wTSφbw=αTKbα] （31）

[wTSφWw=αTKWα] （32）

[wTSφtw=αTKtα] （33）

其中：

[Kb=Nii=1C μi-μ μi-μT] （34）

[Kw=i=1Cj=1Niξxj-μiξxj-μiT] （35）

[Kt=Kb+Kw=i=1Nξxi-μξxi-μT] （36）

式（34）、（35）、（36）中的[Kb]、[Kw]、[Kt]分別為核類間散度矩陣、核類內(nèi)散度矩陣、核總體散度矩陣。

將式（31）和式（33）代入式（24）中，可以得到高維特征空間[F]中廣義Fisher判別準(zhǔn)則函數(shù)式為：

[ Jφw=wTSφbwwTSφtw=αTKbααTKtα=Jα] （37）

求出變量[α]的解，即能通過式（25）得到[w]的解。

求解核Fisher判別分析問題變成了求解[Kbα=λKwα]的最大特征值對(duì)應(yīng)的特征向量。

4 核最大間距判別準(zhǔn)則（KMMC）的數(shù)學(xué)模型

設(shè)有[C]個(gè)模式類，[Xij∈RN]表示原輸入空間的第[i]類的第[j]個(gè)訓(xùn)練樣本。訓(xùn)練樣本集為[X=Xjii=1，2，…，C；j=1，2，…，Ni]，[Ni]為第[i]類訓(xùn)練樣本的數(shù)目，可知[N1+N2+…+NC=N]。經(jīng)過非線性映射[?]變換后，[?X11，?X12，…，?X1N1，…，?XC1，…，?XCN1]表示高維空間[F]上[N]個(gè)訓(xùn)練樣本。

設(shè)第[i]類均值和總體均值分別為[mi]和[m]，則

[m?i=1Nij=1Ni?Xij]

[m?=1Ni=1Cj=1Ni?Xij] （38）

[S?b]為類間散度矩陣，[S?w]為類內(nèi)散度矩陣，即

[S?b=i=1CNiNm?i-m?m?i-m?T] （39）

[S?w=1Ni=1Cj=1NiΦXij-m?iΦXij-m?iT] （40）

特征空間[F]上最大間距準(zhǔn)則的判別函數(shù)為：

[maxJ?w=j=1dwTjS?b-S?wwj] （41）

其中[w=w1，w2，…，wd∈RL×d，wi∈RL]為特征空間內(nèi)的任意非零向量。我們要基于最大間距準(zhǔn)則判別函數(shù)最大的情況下，在特征空間[F]上尋找一組最優(yōu)鑒別向量[w1，w2，…，wd]。式（41）的解向量[w]一定在高維空間[F]中的[N]個(gè)訓(xùn)練樣本向量[?X1，?X2，…，?XN]所張成的空間內(nèi)，即

[w∈span?X1，?X2，…，?XN]，則有：

[w=i=1Nai?Xi=Φα] （42）

其中[Φ=?X1，…，?XN]，[α=a1，a2，…，anT∈RN]。

把[?Xik]投影到[w]上，則有

[wTaXik=αTΦTaXik =αT?X1T?Xik，…，?XNT?XikT]

[=αTkX1，Xik，…，kXN，XikT=αTζik] （43）

則[ζik=kX1，Xik，…，kXN，XikT]，則稱[ζik]為核樣本向量，向量[α=a1，a2，…，anT∈RN]為核鑒別向量。

若把特征空間[F]上的類別均值向量[m?i]和總體均值向量[m?]分別投影到向量[w]上：

[ wTm?i=αT1Nij=1NikX1，Xij，…，kXN，XijT=αTμi] （44）

[ wTm?=αT1Ni=1Cj=1NkkX1，Xij，…，kXN，XijT=αTμ] （45）

其中： [μi=1Nij=1Niζij] ； [μ=1Ni=1Cj=1Niζij]

根據(jù)式（44）和（45），可知

[wTS?bw=αTKbα] （46）

[ wTS?ww=αTKwα] （47）

其中：

[Kb=i=1CNiNμi-μμi-μT] （48）

[Kw=1Ni=1Cj=1Niζij-μiζij-μiT] （49）

[Kt=Kb+Kw=1Ni=1CjNiζij-μζij-μT] （50）

由式（46）和（47）可知特征空間[F]上的最大間距準(zhǔn)則函數(shù)式（41）等價(jià)于

[maxJ?w=j=1dwTjS?b-S?wwj]

[=j=1dαTjKb-Kwαj]

[maxJkα=j=1dαTjKb-Kwαj] （51）

稱式（51）為核最大間距準(zhǔn)則函數(shù)。矢量[αi∈RN]稱為最優(yōu)核鑒別向量。特征方程[Kb-KwX=λX]的前[d]個(gè)最大特征值所對(duì)應(yīng)的特征向量為最優(yōu)核鑒別向量[α1，α2，…，αd]。

5 ORL人臉庫上的仿真實(shí)驗(yàn)

本實(shí)驗(yàn)所用的人臉圖像的訓(xùn)練樣本和測(cè)試樣本均來自O(shè)RL（Olivetti Research Library）標(biāo)準(zhǔn)人臉庫。圖1是ORL人臉庫中某一個(gè)人的10幅人臉圖像。實(shí)驗(yàn)中，我們將ORL人臉庫中的圖像處理成為[23×28]維的形式。在本仿真實(shí)驗(yàn)中，在ORL人臉庫上，每類分別取4、5、6個(gè)樣本為訓(xùn)練樣本。共計(jì) 160個(gè)樣本（或200個(gè)樣本或240個(gè)樣本）為訓(xùn)練樣本。

這里選用的核函數(shù)是高斯函數(shù)[kX，Y=exp -γX-Y2]，其中[γ=0.03125]。圖2表示每類分別選取4個(gè)樣本（或5個(gè)樣本或6個(gè)樣本）為訓(xùn)練樣本并且在不同的特征維數(shù)下（2、4、6、…、20），KPCA、KFDA和KMMC三種方法的識(shí)別率的變化情況。圖2（a）表示每類取4個(gè)訓(xùn)練樣本；圖2（b）表示每類取5個(gè)訓(xùn)練樣本；圖2（c）表示每類取6個(gè)訓(xùn)練樣本。

（a）每類取4個(gè)訓(xùn)練樣本

（b）每類取5個(gè)訓(xùn)練樣本

（c）每類取6個(gè)訓(xùn)練樣本

表1表示每類分別選取4個(gè)樣本（或5、6個(gè)樣本）為訓(xùn)練樣本并且特征維數(shù)取值范圍為2、4、6、8、…、20時(shí)，KPCA、KFDA和KMMC三種鑒別方法所達(dá)到的最佳的識(shí)別率和對(duì)應(yīng)的特征維數(shù)的取值。

圖2（a）（b）（c）可以看出，三種鑒別方法里，KMMC的識(shí)別率整體優(yōu)于KPCA和KFDA。當(dāng)每類分別選取5個(gè)樣本（或6個(gè)樣本）為訓(xùn)練樣本時(shí)，KPCA方法和KMMC方法的最佳識(shí)別率總是高于KFDA方法的最佳識(shí)別率。因此，在規(guī)模較大的人臉數(shù)據(jù)庫上，KMMC鑒別方法的識(shí)別效果也有比較好的表現(xiàn)。三是KFDA的識(shí)別率明顯是低于KPCA的識(shí)別率的。

6 結(jié)束語

本文首先對(duì)核方法做了簡(jiǎn)單的介紹，并學(xué)習(xí)和研究了三種基于核理論的非線性鑒別分析方法，分別是核主成分分析，核Fisher判別分析以及核最大間距準(zhǔn)則，并在ORL人臉庫上進(jìn)行仿真。由仿真結(jié)果可知，KMMC方法提取鑒別信息的有效性整體高于KPCA和KFDA方法，在規(guī)模較大的人臉數(shù)據(jù)庫上，KMMC鑒別方法的識(shí)別效果也有比較好的表現(xiàn)。

參考文獻(xiàn)：

[1] 章毓晉. 基于子空間的人臉識(shí)別[M].北京：清華大學(xué)出版社，2009.

[2] 李國棟，李勇智. 一種基于核最大間距準(zhǔn)則改進(jìn)的特征提取方法[J].江蘇大學(xué)學(xué)報(bào)，2008，19（7）：1670-7775.

[3] 胡迎春. 人臉圖像特征點(diǎn)眼睛的定位與提取[J].廣西工學(xué)院學(xué)報(bào)，2003（1）.

[4] 王映輝. 人臉識(shí)別——原理、方法與技術(shù)[M].北京：科學(xué)出版社，2010.

[5] 周杰，盧春雨，張長水，等. 人臉自動(dòng)識(shí)別方法綜述[J].電子學(xué)報(bào)，2000，28（4）：102-106.

[6] 王振海. 融合奇異值分解和最大間距準(zhǔn)則的人臉識(shí)別方法[J].計(jì)算機(jī)工程與應(yīng)用學(xué)報(bào)，2011，47（8）：164-166.

[7] 王本超，馬軍偉，顧宏. 基于KPCA和SVM的人臉識(shí)別研究[D]. 大連： 大連理工大學(xué)，2008.

[8] 高秀梅，楊靜宇，楊健. 一種最優(yōu)的核Fisher鑒別分析與人臉識(shí)別[J].系統(tǒng)仿真學(xué)報(bào)，2004，16（12）：2864-2868

（下轉(zhuǎn)第201頁）

（上接第194頁）

[9] 楊健，楊建宇，金忠. 最優(yōu)鑒別特征的抽取及圖像識(shí)別[J].計(jì)算機(jī)研究與發(fā)展，2001，38（11）.

[10] 郭躍飛，黃修武，楊靜宇，等. 一種求解Fisher最佳鑒別矢量的新算法及人臉識(shí)別[J].中國圖象圖形學(xué)報(bào)，1999，4（2）：95-98

[11] 徐勇，楊靜宇，金忠，等. 一種基于核的快速非線性鑒別分析方法[J].計(jì)算機(jī)研究與發(fā)展，2005，42（3）：367-374.

[12] 許建華，張學(xué)工，李衍達(dá). 一種基于核函數(shù)的非線性感知器算法[J].計(jì)算機(jī)學(xué)報(bào)，2002，25（7）：689-695.

[13] Liu K， Cheng Y Q， Yang Y Y.A generalized optimal set of discriminant vectors，Pattern Recognition ， 1992，25 （7） ：731-739.

[14] Yang L，Gong W， Gu X，et al. Liang，Null space discriminant locality preserving projections for face recognition，Neurocomputing ， 2008（71）：3644-3649.