一種最近鄰線非參數鑒別分析算法

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

關鍵詞： 特征提??； 最近鄰線非參數鑒別分析； 算法； 人臉識別

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

Abstract： Feature extraction is one of the hot topics in the field of pattern recognition. To solve the problem of feature extraction in face recognition， a new algorithm which is called nearest neighbor line nonparametric discriminating analysis （NNL?NDA） algorithm is proposed. It is based on the algorithm of distributed nonparametric maximum spacing criteria， according to nearest neighbor line idea and in comparison with point to line distance. The validity of the algorithm is verified by recognition in face database.

Keywords： feature extraction； NNL?NDA； algorithm； face recognition

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

1 間距最大準則（MMC）

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

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

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

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

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

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

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

[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）

因此，特征提取準則函數公式（1）可轉化成如下形式：

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

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

MMC的方法在一定范圍內能有效地解決Fisher方法中產生的問題，但解決類內散布矩陣的問題還需要進一步探討。Qiu等提出了分步式非參數間距最大準則（Stepwise Nonparametric Margin Maximum Criterion， SNMMC）方法。

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

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

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

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

類推，得到類內最遠距離的定義：

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

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

[ΔE=x-xE] （12）

[ΔI=x-xI] （13）

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

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

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

式中的[ωi]為樣本的權值，定義如下：

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

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

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

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

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

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

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

[δE=WTΔE] （18）

[δI=WTΔI] （19）

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

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

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

基于這樣的考慮，有：

[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]分別代表矩陣的非參數類間散布矩陣和矩陣的類內散布矩陣。

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

[W=argmaxWtrWTSb-SwW] （22）

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

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

3.1 最近鄰線算法（NNL）

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

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

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

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

[piN1N2=t1ixN1i+t2ixN2i] （24）

其中：

[t1i+t2i=1] （25）

根據LLE算法能得到：

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

其中：

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

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

其中最近鄰線的定義為：

[xN1nearxN2near=argmini dx，xN1ixN2i] （29）

3.2 算法的實現

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

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

[ΔE=x-pE] （30）

[ΔI=x-pI] （31）

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

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

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

定義新的類內散布矩陣：

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

根據以下定義的函數：

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

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

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

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

假定循環次數為[T]，算法描述如下：

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

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

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

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

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

4 實驗與分析

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

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

5 結 語

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

參考文獻

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

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

[3] CHENG Y Q， ZHUANG Y M， YANG J Y. Optimal fisher discriminant analysis using the rank decomposition [J]. Pattern Recognition， 1992， 25（1）： 101?111.

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

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

[6] CHERKASSKY V， MULIER F. Learning from data： concepts， theory and methods [M]. New York：John Viley Sons， 1997.

[7] 仲媛.最近鄰分類的若干改進算法研究[D].南京：南京理工大學，2012.

[8] VICKERS A J. Parametric versus non?parametric statistics in the analysis of randomized trials with non?normally distributed data [J]. BMC Medical Research Methodology， 2005， 5（1）： 1?12.

[9] 金忠，楊靜宇，陸建峰.一種具有統計不相關性的最優鑒別矢量集[J].計算機學報，1999，22（10）：1105?1108.

[10]BELHUMEUR P N， HESPANHA J P， KRIEGMAN D J. Eigenfaces vs. fisherfaces： recognition using class specific linear projection [C]// 1996 the 4th European Conference on Computer Vision Cambridge. UK： ECCV， 1996， 19（7）： 711?720.

[11] 鄭宇杰.特征提取方法及其應用研究[D].南京：南京理工大學，1996.