一種最近鄰線非參數(shù)鑒別分析算法

第第頁一種最近鄰線非參數(shù)鑒別分析算法摘要：特征提取是模式識別研究領(lǐng)域的一個熱點問題。為了更好地解決人臉識別中的特征提取問題，在分布的非參數(shù)間距最大準則算法的基礎上，根據(jù)最近鄰線的算法思想，在點?線距離的基礎上，提出一種新的算法，即最近鄰線非參數(shù)鑒別分析算法，并通過在人臉數(shù)據(jù)庫上的識別，驗證了該算法的有效性。

關(guān)鍵詞：特征提??；最近鄰線非參數(shù)鑒別分析；算法；人臉識別

中圖分類號：TN702.2?34；TP391.41文獻標識碼：A文章編號：1004?373X（2015）13?0145?04

Abstract：Featureextractionisoneofthehottopicsinthefieldofpatternrecognition.Tosolvetheproblemoffeatureextractioninfacerecognition，anewalgorithmwhichiscallednearestneighborlinenonparametricdiscriminatinganalysis（NNL?NDA）algorithmisproposed.Itisbasedonthealgorithmofdistributednonparametricmaximumspacingcriteria，accordingtonearestneighborlineideaandincomparisonwithpointtolinedistance.Thevalidityofthealgorithmisverifiedbyrecognitioninfacedatabase.

Keywords：featureextraction；NNL?NDA；algorithm；facerecognition

在線性特征提取方法中，通常采用Fisher線性鑒別準則[1?2]。但做特征提取時Fisher線性鑒別準則對原始樣本的分布情況提出兩個要求[3]：樣本的分布須是單峰值的；每類樣本均值須不同。但在實際應用中很難達到這兩個要求。因此，F(xiàn)ukunaga等提出了非參數(shù)鑒別分析[4?5]（NonparametricDiscriminantAnalysis，NDA）的方法，這個方法將原先的Fisher鑒別準則法進行優(yōu)化，即利用相應的散布矩陣差替代相應的散布矩陣的比值，不過NDA方法仍受相應的散布矩陣奇異的影響。因此，可用分步的非參數(shù)間距最大準則[6]算法來解決這個問題。根據(jù)最近鄰線思想[7?10]，在點?線距離的基礎上提出了一種新的稱為最近鄰線非參數(shù)鑒別分析[11]的算法，并且通過在ORL人臉庫進行實驗識別驗證了此算法的有效性。

1間距最大準則（MMC）

MMC準則的目的是要將原始的高維空間數(shù)據(jù)壓縮到低維空間并且仍然能夠保證較好的可分性。所以，在特征提取的過程中，應當在變化之后的低維空間內(nèi)保持類間距離的最大化。那么，特征提取的準則定義如下：

[J=12i=1Cj=1CdCi，Cj]（1）

式（1）表示的是任意兩類之間的距離，可定義其為最大鑒別準則，MMC的準則目的就是要使這個[J]值盡可能大。

類與類之間的距離，通過類中心點的距離來度量，即：

[dCi，Cj=dmi，mj]（2）

式中：[mi，][mj]分別代表類別[Ci]和[Cj]的類中心，但是如果簡單就以[dCi，Cj]作為分類依據(jù)，在距離度量中，可能會出現(xiàn)散布矩陣的奇異。所以在出現(xiàn)不同樣本分布混亂或重疊時，這種分類就不可行。

重新對類間距離進行定義：

[dCi，Cj=dmi，mj-SCi-SCj]（3）

式中：[SCi]表示[Ci]的散布度量的值。在實際使用時，用[trSi]來代替[SCi]，表示類別[Ci]的散布度量的信息。

將[trSi]代入式（3），得出：

[J=12i=1Cj=1Cdmi，mj-SCi-SCj=12i=1Cj=1Cdmi，mj-trSi-trSj=12i=1Cj=1Cdmi，mj-12i=1Cj=1CtrSi+trSj]（4）

其中式（4）的后半部分可以簡化成如下形式：

[12i=1Cj=1CtrSi+trSj=i=1CtrSi=tri=1CSi=trSw]（5）

對于公式（4）的前半部分，采用歐氏距離，可以得出：

[12i=1Cj=1Cdmi，mj=12i=1Cj=1Cmi-mjTmi-mj=12i=1Cj=1Cmi-m0+m0-mjTmi-m0+m0-mj]（6）

將公式（6）展開并加入如下公式：

[i=1Cm0-mi=0]（7）

可推出與公式（6）等價的一個公式：[12i=1Cj=1Cmi-m0+m0-mjTmi-m0+m0-mj=tri=1Cmi-m0mi-m0T=trSb]（8）

因此，特征提取準則函數(shù)公式（1）可轉(zhuǎn)化成如下形式：

[J=trSb-trSw=trSb-Sw]（9）

這樣實現(xiàn)了不同類之間的距離最大，同類之間的距離最小，也就是使同類間距離最緊湊。

MMC的方法在一定范圍內(nèi)能有效地解決Fisher方法中產(chǎn)生的問題，但解決類內(nèi)散布矩陣的問題還需要進一步探討。Qiu等提出了分步式非參數(shù)間距最大準則（StepwiseNonparametricMarginMaximumCriterion，SNMMC）方法。

2分步式非參數(shù)間距最大準則（SNMMC）

SNMMC的目的與MMC方法一樣，盡量使類間距離最大而類內(nèi)距離最小。在該算法設計中，不去具體定義類的中心點，只是考慮某一樣本與它周圍樣本的分布情況，從而來定義相應的散布矩陣。算法的思想描述如下：

對于一個樣本[x∈Ci][i=1，2，…，C]，那么定義相應的類間最近距離：

[xE=x?Cix-x≤z-x，?z?Ci]（10）

類推，得到類內(nèi)最遠距離的定義：

[xI=x∈Cix-x≥z-x，?z∈Ci]（11）

因此，找出每個點的類間最近點和類內(nèi)最遠點，以此來計算每個樣本點[x]的非參數(shù)類間和類內(nèi)差異：

[ΔE=x-xE]（12）

[ΔI=x-xI]（13）

由此，得到新的類間散布矩陣和類內(nèi)散布矩陣定義如下：

[Sb=i=1NωiΔEiΔEiT]（14）

[Sw=i=1NωiΔEiΔEiT]（15）

式中的[ωi]為樣本的權(quán)值，定義如下：

[ωi=ΔIiαΔIiα+ΔEiα]（16）

式中：[α]作為一個控制參數(shù)來使用，取值在0到無窮大之間。這個樣本的取值盡量不靠近樣本中心點。公式（16）的值越大說明樣本離類別的邊界越近，反之值越小說明樣本越靠近類中心。[α]控制其變化的過程。

公式（12）和（13）給出，[ΔEi]表示的是樣本[xi]和不在樣本[xi]類中的最臨近點之間的距離，而[ΔIi]表示的是樣本[xi]和屬于樣本[xi]所在類空間內(nèi)的最遠點之間的距離。

對于給定樣本[xi，]相應的非參數(shù)距離可以表示如下：

[θi=ΔEi2-ΔIi2]（17）

對于一個樣本[xi]而言，相應的非參數(shù)距離大小可以去估計分類的準確性。即非參數(shù)距離值越小，樣本分類的正確性越低，反之，值越大其正確率越高。

假設樣本在進行特征提取后可以得到[d]維空間的特征向量，可以得出一個轉(zhuǎn)換矩陣[W]（[n×d]），由此得出投影矩陣[xnew=WTx。]投影之后的非參數(shù)類間和類內(nèi)差異分別是：

[δE=WTΔE]（18）

[δI=WTΔI]（19）

其目的是使得非參數(shù)距離[δEi2-δIi2]越大越好。

[W=argmaxWi=1NωiδEi2-δIi2]（20）

在這個優(yōu)化過程中，致力于找到這樣的樣本，使其并非在原始樣本空間而是在投影空間上，使得類間距離最大，而類內(nèi)距離最小。

基于這樣的考慮，有：

[i=1NωiδEi2-δIi2=i=1NωiWTΔEiTWTΔEi-i=1NωiWTΔIiTWTΔIi=tri=1NωiWTΔEiWTΔEiT-tri=1NωiWTΔIiWTΔIiT=trWTi=1NωiΔEiΔEiTW-trWTi=1NωiΔIiΔIiTW=trWTSbW-trWTSwW=trWTSb-SwW]（21）

式中：[tr?]代表矩陣的秩；[Sb]和[Sw]分別代表矩陣的非參數(shù)類間散布矩陣和矩陣的類內(nèi)散布矩陣。

因此，公式（20）可以寫為：

[W=argmaxWtrWTSb-SwW]（22）

公式（22）被稱為非參數(shù)最大間距準則。

3最近鄰線非參數(shù)鑒別分析（NNL?NDA）

3.1最近鄰線算法（NNL）

最近鄰線的定義：假設[xN1i]和[xN2i]是樣本[x]在第[i]類中的兩個最近的鄰點，那么樣本[x]在第[i]類中的最近鄰線就用這兩個點構(gòu)成的直線[xN1ixN2i]來表示。那么最近鄰線距離就是點[x]到最近鄰線[xN1ixN2i]的距離，其定義如下：

[dx，xN1ixN2i=x-piN1N2]（23）

式中樣本[x]在最近鄰線[xN1ixN2i]上的投影點表示為[piN1N2]。

投影點[piN1N2]的計算如下：

[piN1N2=t1ixN1i+t2ixN2i]（24）

其中：

[t1i+t2i=1]（25）

根據(jù)LLE算法能得到：

[tji=kC-1jklmC-1lm]（26）

其中：

[C=Clml=1，2；m=1，2]（27）

[Cjk=x-xNjiTx-xNkj]（28）

其中最近鄰線的定義為：

[xN1nearxN2near=argminidx，xN1ixN2i]（29）

3.2算法的實現(xiàn)

在本文的方法中，NNL算法可以用來對距離進行度量計算。這里可以通過相應的非參類間和類內(nèi)距離來實現(xiàn)相關(guān)的散布矩陣。

算法中使用的非參類間和類內(nèi)差異進行重新定義：

[ΔE=x-pE]（30）

[ΔI=x-pI]（31）

式中：[pE]是通過最近鄰線思想取得的點，這個途徑是從不同于樣本[x]所屬的類別[Ck]中獲得；[pI]則與[pE]相反，是由[xN1far，][xN2far]得到的點。

由此可以定義新的非參類間：

[Sb=i=1MωiΔEiΔEiT]（32）

定義新的類內(nèi)散布矩陣：

[Sw=i=1MωiΔIiΔIiT]（33）

根據(jù)以下定義的函數(shù)：

[WNNL-NDA=argmaxtrWWTSb-SwW]（34）

式中限定[WTW=I，]可以計算得到相應的投影矩陣。

由此，可以將NNL?NDA算法描述如下：

通過[T]次變換后得到一個轉(zhuǎn)換矩陣[W]。假設，在經(jīng)過[t]步轉(zhuǎn)換之后得到[dt]維的數(shù)據(jù)，得到的維數(shù)應滿足[dt-1>dt>dt+1]，其中[d0=D]，[dT=d]。[D]和[d]分別代表了圖像的原始維數(shù)和要經(jīng)過轉(zhuǎn)換后需要得到的維數(shù)。

假定循環(huán)次數(shù)為[T]，算法描述如下：

（1）根據(jù)最近鄰線的思想得出每一個樣本的[pE]和[pI]值；

（2）根據(jù)公式（32）和（33）計算得出在[dt-1]維下的類間散布矩陣和類內(nèi)散布矩陣；

（3）根據(jù)公式（34）計算得到在[dt-1]維下的轉(zhuǎn)換矩陣[Wt]，其中的[Wt]是一個[dt-1×dt]的矩陣；

（4）進行投影矩陣的映射，得到新維數(shù)下的樣本矩陣[x=WTtx]。

令[W=t=1TWt，]可以構(gòu)成最終的變換矩陣。

4實驗與分析

實驗在ORL人臉數(shù)據(jù)庫上進行。訓練樣本集的產(chǎn)生是從樣本庫中隨機挑選每個類別中的9個人臉來進行，這樣，訓練樣本集的人臉的個數(shù)就是40×9，測試樣本集就是從余下的人臉數(shù)據(jù)產(chǎn)生，針對不同的訓練樣本數(shù)，均進行10次不相同的實驗。其結(jié)果見表1，表2。

表1和表2分別顯示了NNL?NDA與其他經(jīng)典的人臉識別算法在ORL人臉數(shù)據(jù)庫上的識別性能的比較；圖1和圖2分別顯示了在類別數(shù)目不同的情況下采用不同的分類器方法得到的識別率。

5結(jié)語

本文在最近鄰線思想的基礎上，提出了一種新的特征提取方法――NNL?NDA方法。在新方法中，特征提取的過程運用NNL的思想理論將樣本的結(jié)構(gòu)信息融入其中，通過在ORL人臉數(shù)據(jù)庫中的實驗，很好地驗證了該算法的有效性。

參考文獻

[1]戴文戰(zhàn)，周昌亮.一種改進Fisher準則的線性鑒別分析方法[J].計算機工程與應用，2013（3）：210?212.

[2]崔法毅.改進的Fisher鑒別分析兩步算法研究及其在人臉識別中的應用[D].秦皇島：燕山大學，2012.

[3]CHENGYQ，ZHUANGYM，YANGJY.Optimalfisherdiscriminantanalysisusingtherankdecomposition[J].PatternRecognition，1992，25（1）：101?111.

[4]曹林，陳登.基于小波近似分量非參數(shù)鑒別分析人臉識別算法[J].北京信息科技大學學報：自然科學版，2011（6）：20?23.

[5]薛寺中，戴飛，陳秀宏.一種非參數(shù)核函數(shù)鑒別分析法及其在人臉識別中的應用[J].計算機科學，2012（6）：507?518.

[6]CHERKASSKYV，MULIERF.Learning