非線性距離的最近鄰特征空間嵌入改進方法*

杜弘彥，王士同

江南大學 數字媒體學院，江蘇 無錫 214122

非線性距離的最近鄰特征空間嵌入改進方法*

杜弘彥+，王士同

江南大學 數字媒體學院，江蘇 無錫 214122

最近鄰特征空間嵌入（nearest feature space embedding，NFSE）方法選取最近鄰特征空間時使用歐氏距離度量，導致樣本的類內離散度和類間離散度同步變化，無法準確反映樣本在高維空間的分布；選取每個樣本最近鄰特征空間都要遍歷所有類，導致訓練時間長。針對以上問題，提出非線性距離的最近鄰特征空間嵌入改進方法（nearest feature space embedding method based on nonlinear distance metric，NDNFSE），引入非線性距離公式選取最近鄰特征空間，并使用結合夾角度量的最近鄰分類器，提高了識別率；僅在樣本的近鄰類中選取最近鄰特征空間，有效減少了訓練時間。實驗表明，NDNFSE的訓練時間明顯低于NFSE，識別率總體高于各對比算法。

人臉識別；非線性距離；夾角；最近鄰特征空間嵌入；近鄰類

1 引言

在過去的幾十年中，模式識別領域的人臉識別越來越為人們所關注，與之相關的技術應運而生，國內外眾多學者提出各種算法致力于提高人臉識別的效率和精度，取得了一定的成果。主成分分析（principal components analysis，PCA）[1]方法是一種經典的降維方法，通過線性變換將原始樣本映射到低維空間，應用廣泛。文獻[2]提出的近鄰保持嵌入（neighborhood preserving embedding，NPE）方法是無監督降維方法，能夠保留局部鄰近結構。文獻[3]提出的拉普拉斯特征臉方法也可以保留樣本的局部結構。拉普拉斯特征映射（Laplacian eigenmaps，LE）[1]和非監督判別投影（unsuperviseddiscriminantprojection，UDP）[4]等方法則可以產生其他非線性流形結構，從而保留樣本的局部信息。

無監督的降維算法有時并不能滿足所有的應用需要，有監督的算法可以充分利用樣本的類標簽信息。線性判別分析（linear discriminant analysis，LDA）[5]是最受歡迎的經典的線性降維算法之一，常用于人臉識別。LDA方法利用同類的點到點的向量來計算類內離散度，不同類的點到點的向量計算類間離散度，能夠使類間離散度和類內離散度比值最大的判別向量組成最優的轉換矩陣，即樣本降維的最佳投影方向。LDA是基于整體的學習方法，當樣本為線性分布時，收到較好的效果；但當樣本不符合線性分布時，則可能難以發現樣本的真實結構。

針對上述問題，學者們提出了局部線性嵌入（locally linear embedding，LLE）[6-7]、局部保留投影（locally preserving projection，LPP）[3]、邊界費舍爾分析（marginal Fisher analysis，MFA）[8]等基于局部的學習方法。樣本的全局非線性結構可視為局部線性，因此LLE通過局部的線性結構來揭示全局的非線性結構。因為缺乏明確的樣本投影，所以LLE很難得到測試集中樣本點的圖像。線性降維方法LPP能夠保留樣本固有的幾何結構，產生適合于訓練樣本和測試樣本的明確線性投影，更適合應用于人臉識別。不過，LPP有著大多數基于流形的學習方法共有的局限性，其目標函數只是最小化局部數量，與分類并不具有直接關系，致使在某些情況下，不能確定生成的是有利于分類的投影矩陣。為了打破LDA和LPP的限制，文獻[8]結合LDA與LPP的優勢，提出了MFA，使用圖嵌入框架，綜合樣本的局部信息和類別信息來刻畫同類樣本的緊密程度和異類樣本的離散程度，對樣本的分布沒有特殊要求，應用范圍較廣。

MFA計算離散度時使用樣本點到樣本點的向量，文獻[9]提出了最近鄰特征空間嵌入（nearest feature space embedding，NFSE）方法，借鑒MFA選取類邊界樣本點參與離散度計算的方法，融入了最近鄰特征線（nearest feature line，NFL）[10]匹配方法的思想，以線、面等形成的特征子空間代替單獨的點來表示每個類，包含了更多的類別信息，能夠更好地表示某個類別的樣本，有利于提高分類精度。皋軍等多位學者對NFSE進行改進，均取得了一定的成果[11-12]。但是，NFSE在求最近鄰特征空間時采用線性的歐氏距離公式進行度量，引起類間離散度和類內離散度同步變化，降低了識別率。作者曾提出基于非線性距離和夾角組合的最近鄰特征空間嵌入方法（nearest feature space embedding method based on the combination of nonlinear distance metric and included angle，NL_IANFSE），引入非線性距離公式計算樣本點到特征空間的距離，保證類內距離的變化速率遠小于類間距離變化速率，使得類間離散度與類內離散度的比值增大，得到判別力更強的投影矩陣；另外，NL_IANFSE在測試階段使用結合夾角度量的最近鄰分類器代替傳統的最近鄰（nearest neighbor，NN）分類器，將不同樣本的相似性和它們的位置關系都納入考慮范圍，最終得到了比NFSE更高的識別率。

NFL匹配規則可用于人臉識別的測試階段，將NN中求兩個樣本點之間的距離改為求樣本點到它在特征線上投影點的距離，分類效果比NN好，但所花費時間卻更長。NL_IANFSE和NFSE都是把NFL通過判別分析嵌入到轉換過程中，相當于把求特征點到特征子空間距離的計算從測試階段轉移到訓練階段，故二者的訓練時間都較長。

為了降低NL_IANFSE訓練階段的時間復雜度，本文借用文獻[13]提出的加強的邊界費舍爾分析（enhanced marginal Fisher analysis，EMFA）的思想，先通過比較某樣本點所在類的類中心與其他類中心的距離，選出若干個近鄰的類，然后再計算這個樣本點到近鄰類的各個特征子空間的距離，并分別取出每個類中相同數目的最小距離參與類間離散度的計算。這樣做有效避免了求樣本點到其他類別的特征子空間距離時遍歷訓練集中所有類別的做法，節省了大量的時間。實驗表明，采用這種方法，在大幅度提升訓練效率的情況下仍能得到和NL_IANFSE相當的分類準確率。

2 相關研究

2.1 最近鄰特征空間嵌入

最近鄰特征空間嵌入方法綜合前人算法的優點，利用LPP方法保留局部結構，將最近鄰特征空間度量、鄰近結構保留和分類相結合。用每一類中若干個特征點線性結合形成的特征子空間來分別表示各個類，依次求出每個樣本點到同類和不同類特征子空間的向量，根據向量長度排序，取出同類特征子空間中前K1個長度最短的向量和不同類特征子空間中前K2個長度最短的向量。在計算離散度時，借助拉普拉斯矩陣來簡化計算，然后最大化Fisher準則以得到最優轉換矩陣。

2.2 基于非線性距離和夾角組合的最近鄰特征空間嵌入方法

NL_IANFSE在NFSE的基礎上，引入非線性距離公式選取最近鄰特征空間，使得類間離散度的變化速度遠大于類內離散度的變化速度，從而嵌入空間中同類樣本更為接近，不同類樣本相距較遠，更便于分類。另外，針對傳統最近鄰分類器只考慮樣本間直線距離而無法如實反映高維空間中樣本分布的問題，NL_IANFSE使用結合夾角度量的分類器，提高了最終識別率。

2.2.1 非線性距離計算公式

有監督的局部線性嵌入（supervised locally linear embedding，SLLE）[14]算法中加入樣本類別信息構造鄰域。文獻[15]對構造鄰域時用到的距離公式進行改進，提出非線性距離公式。設xi、xj為兩個樣本點，二者之間的非線性距離計算公式可寫作：

其中，A是xi、xj兩個樣本點間的歐氏距離；B是所有樣本點兩兩之間的歐式距離的均值；α是一個屬于[0,1]區間的參數，表示樣本點類別信息的結合程度，調節不同類的樣本之間的距離。

2.2.2 結合夾角度量的最鄰近分類器

由于樣本間的相似性越大，其夾角越小，而同類樣本間的相似性要比異類樣本間的相似性更大，通過樣本間夾角大小來輔助判斷兩個樣本類標簽是否相同是可行的。文獻[16]將樣本兩兩之間的夾角和其直線距離相結合，得到結合夾角度量的最近鄰分類器。相比最近鄰分類器，結合夾角度量的最近鄰分類器的優點在于，當高維空間中樣本間直線距離趨同時，可以憑借夾角的大小反映樣本分布情況，更適合高維數據分類。

首先，通過余弦定理求出兩個高維空間樣本xi和xj的夾角：

然后，通過以下公式計算得到關于xi、xj的融合值：

其中，β∈[0,1]，是融合系數；Di·表示 xi和其他所有樣本點的直線距離；θi·表示xi和其他所有樣本點的夾角。與xi融合后取得最小值的樣本所屬的類即是xi所屬的類。

2.3 加強的邊界費舍爾分析

傳統的邊界費舍爾分析用k1和k2兩個參數分別控制類內樣本的緊密度和類間樣本的分散度，其中k1表示距離樣本xi最近的與xi同類的樣本點的個數，k2表示距離xi最近的位于其他類邊界的樣本點的個數。參數k2的確定對于正確劃分不同類樣本至關重要。假設訓練集共有N個類，傳統的MFA在選取xi到其他類的最近鄰樣本時，遍歷除xi所在類之外的N-1個類，求出xi到這些類中每個樣本點的距離，將這些距離按照從小到大的順序排列，取出前k2個到xi距離最小的樣本點參與后續的類間離散度矩陣的計算。

這樣做可能帶來兩個問題：第一，求每個樣本的類間近鄰點都遍歷N-1個類會耗費大量的時間，降低算法效率。第二，直接從所有與xi不同類的樣本點中選擇前k2個到xi距離最小的樣本點，可能漏掉某些類的邊界點，導致邊界點選取有誤差，不利于投影空間中的樣本分類。

因此，文獻[13]提出加強的邊界費舍爾分析。首先求出各類的類均值和xi所在類與其他類的距離，然后選出距離最小亦即最接近xi所在類的Ne個類。依次計算xi到Ne個類中每個類的所有樣本的直線距離，從每個類中選取距離最小的Ke個樣本點，共計Ne×Ke個樣本點。用得到的Ne×Ke個樣本點代替傳統MFA選取的k2個類間近鄰點參與類間離散度的計算。如圖1所示，Ne=2，Ke=3，第B類樣本集和第C類樣本集是第A類樣本集的最近鄰樣本集，B、C中的到xi最近的邊界點用連線標出。

3 非線性距離的最近鄰特征空間嵌入改進方法

NFSE和NL_IANFSE在訓練階段，計算類間離散度之前尋找每個訓練樣本的不同類的最近鄰特征子空間，需要遍歷訓練集的所有類，耗費大量的時間。為提高效率，本文引入EMFA先求近鄰類再取邊界點的思想，提出了非線性距離的最近鄰特征空間嵌入改進方法（nearest feature space embedding method based on nonlinear distance metric，NDNFSE），在求類間最近鄰特征子空間之前先求出xi所在類的近鄰類，然后只遍歷這些鄰近類中的特征子空間，計算其到xi的距離，最后排序取出距離xi最近的特征子空間。這樣做有效減少了訓練時間，同時能夠保證識別率比NFSE高，和NL_IANFSE基本持平。下文將對此方法進行詳細介紹。

Fig.1 Selecting marginal points of one sample圖1 選取某樣本類邊界點

3.1 尋找每個類的近鄰類

減少訓練時間的關鍵是僅從xi所在類的近鄰類中選取邊界點，而不再要求每次取訓練樣本邊界點時都遍歷所有類。因此，通過以下方法先求出每個類的鄰近類。假設訓練集共有Nc個類，每類有mi(i=1,2,…,Nc)個樣本。Xi(i=1,2,…,Nc)表示訓練集中第i類的樣本集，每類樣本的平均向量即均值用vi(i=1,2,…,Nc)表示，計算類均值的公式如下：

求出各類均值后，利用這些均值兩兩之間的歐氏距離表示每類樣本集之間的中心距離，以此來衡量類與類之間的遠近。如以下公式所示，用q表示某類的中心，Cab表示第a類和第b類樣本集的類中心距離的平方：

其中，a,b∈{1,2,…,Nc}，a≠b。φi={Xri|i=1,2,…,Nc,r=1,2,…,Ne}表示與第 i個類近鄰的Ne個類，如果Xr∈φi，則可以認為第r個類的樣本接近于第i個類的樣本，即第r個類是第i個類的近鄰類。

3.2 選取樣本點的近鄰特征子空間

特征線比特征點包含更多的信息，能夠更好地表示類，文獻[10]使用一類中兩個樣本點線性組合形成的特征線來表示該類樣本，提出了一種更利于樣本分類的最近線性組合的分類器。假設每個類中有mi(i=1,2,…,Nc)個樣本，每個子空間由Q個樣本點生成，此時第i個類總共可以產生個特征子空間。當Q=1時，特征子空間為一個特征點；當Q=2時，特征子空間為一條特征線；當Q=3時，特征子空間為一個特征面；進而可推廣至Q＞3。由于沒有證據表明，當Q≥3時NFSE算法最終的分類效果更佳，故本文只討論Q=2時的情況。為第i類的第j個樣本，設xm、xn為不同于的兩個同類樣本點，通過xm、xn的直線即為xm、xn所在類的特征線，的投影點記為p(2)(xji)，可以用xm、xn的線性組合表示為，根據文獻[10]，。

3.3 轉換矩陣

人臉識別算法中時常用到Fisher準則，這是利用了類別信息的判別準則函數，定義為類間離散度和類內離散度的比，通過最大化這個比值得到優化的判別投影軸，使得樣本投影到投影空間后不同類樣本間距離較大，同類樣本間距離較小，更容易進行分類。由3.2節得到集合，用以計算類內離散度矩陣和類間離散度矩陣。取Q=2，假設經過yi=wTxi轉換后的低維空間中的樣本集合為T={y1,y2,…,yN}，T中的樣本點兩兩之間共可產生個特征子空間，即條特征線，用 p(2)表示。樣本點yi到特征線的投影點表示為p(2)(yi)，yi到特征線的向量yi-p(2)(yi)用ym和yn表示，共有個向量，公式推導如下：

其中，λm,n、λn,m是低維空間中的權重，滿足條件λm,n+λn,m=1。

計算離散度矩陣的公式如下：

找出樣本點yi到最近的K個特征子空間的判別向量進行判別分析，向量yi-p(2)(yi)的長度為||yig(2)(yi)||，寫出NDNFSE的目標函數，當此目標函數取得最小值時，線性變換yi=wTxi中的w即為所求的轉換矩陣。

其中，權值矩陣ω(2)(yi)表示N個特征點和它們對應的投影點之間的連接關系。

目標函數F可以看作由K個部分組成，分別為各個樣本點到第K近的特征線的距離的平方和，逐步推導成便于計算的拉普拉斯矩陣的形式。

式中，Mi,j(K)是一個稀疏矩陣，表示yi和距離它第K近的特征線的連接關系。M的每一行有且只有兩個相加和為1的非零值。例如，Mi,j(1)是yi和最近鄰特征線的連接關系矩陣，i≠m≠n。Mi,m(1)=λn,m，Mi,n(1)=λm,n，并且滿足 Mi,m(1)+Mi,n(1)=1，Mi,j(1)中第 i行的其他列元素均為0。同理，Mi,j(2)是yi和第二近的特征線的連接關系矩陣，Mi,m(2)=λn,m，。

依此類推。當i=j時，Wi,j(K)=(M(K)+M(K)T-M(K)TM(K))i,j，當 i≠j時，Wi,j(K)=0。另外，D=(D(1)+D(2)+…+D(K))/K，W=(W(1)+W(2)+…+W(K))/K。

根據矩陣的跡的性質||S||2=SST，離散度矩陣可以化簡成拉普拉斯矩陣的形式：

其中，LW=DW-WW表示類內的情況，LB=DB-WB表示類間的情況。

求出類內離散度和類間離散度的表達式后，最大化Fisher準則得到轉換矩陣。

3.4 NDNFSE算法步驟

結合以上敘述，總結出NDNFSE的算法步驟如下。

輸入：N 個訓練樣本 s1,s2,…,sN，參數 R、K1、K2、Ke、Ne、α、β、r。

輸出：轉換矩陣w=wPCAw*。

步驟1每個訓練樣本為一個列向量，通過PCA算法將訓練樣本降到R維，使樣本維數小于樣本總數，從而避免小樣本問題。由此得到第一個轉換矩陣wPCA和降維后的訓練樣本xi=wPCAsi，i=1,2,…,N。

步驟2 通過式（4）、（5）求出 xi所在類的 Ne個近鄰類。

步驟3求出xi在特征空間中的投影點p(2)(xi)，i=1,2,…,N。對于每個樣本點，依據式（1）計算其到類內特征子空間的距離，并按照距離大小排序，選出K1個最近鄰特征空間；再求出xi到Ne個近鄰類的特征子空間的距離，在Ne個類的每類中都選出距離xi最近的 Ke個特征空間，共 Ke×Ne個，記 K2=Ke×Ne。

步驟4根據式（7）、（8）計算類內離散度和類間離散度。

步驟5最大化Fisher得到第二個轉換矩陣w*=。取最大的r個特征值對應的特征向量組成w*。

步驟6得到最終的轉換矩陣w=wPCAw*。

步驟7通過w將測試集也投影到低維空間，利用式（3）判斷測試樣本所屬類別。

3.5 NDNFSE算法效率分析

在訓練階段，計算樣本的類間離散度之前需要選出每個訓練樣本在不同類樣本中的K2個最近鄰特征空間。因此，NFSE算法依次求出各樣本到Nc-1個類中所有特征子空間的距離，亦即到特征子空間的投影點的歐氏距離，將得到的個距離進行排序，取最小的前K2個。NL_IANFSE方法在這一步需要計算的距離數目與NFSE相等，但它采用非線性距離度量，根據式（1）的參數要求，預先遍歷所有類，計算所有訓練樣本到各個類的特征子空間的歐氏距離之和，取其均值作為式（1）的參數B。NDNFSE方法同樣使用了非線性距離公式，但改變了NFSE遍歷所有類尋找最近鄰特征子空間的做法，先通過計算每類樣本中心及類中心兩兩之間的距離求出每類樣本的Ne個近鄰類，求每個樣本的類間最近鄰特征子空間時，只要計算每個樣本到所在類的這Ne個近鄰類中特征子空間的個非線性距離即可。當數據集的類別數較多時，控制Ne的取值，可以使NDNFSE的訓練時間遠遠小于NFSE和NL_IANFSE算法的訓練時間。

在測試階段，NFSE使用傳統的最近鄰匹配方法，依次求出每個測試樣本到各訓練樣本的歐氏距離，將距離最近的訓練樣本的類標作為預測的結果。設每類有mi個訓練樣本，則對于一個測試樣本，需計算Nc×mi個距離。NL_IANFSE和NDNFSE使用結合夾角的最近鄰分類器，除了計算測試樣本到訓練樣本的歐氏距離外，還要利用式（2）求測試樣本與訓練樣本之間的夾角，并進而通過式（3）得到樣本間的融合值，所需時間較長。

4 實驗設計及結果分析

4.1 數據集與實驗設計

本文使用Yale B、ORL、CMU PIE[17]和AR共4個人臉數據集進行實驗。Yale B數據集是耶魯大學建立的，由10位志愿者的面部圖像組成，每人585幅，實驗選用其中的640幅圖像，每人64幅。由劍橋大學創建的ORL人臉數據集采集了40位志愿者的圖像，每人10張表情不同的正面照，總共400張。CMU PIE數據集包含68名志愿者在不同的姿勢、光照、表情下的面部圖像，共有4萬多張，本文選用了其中67人的照片，每人170張。AR數據集由西班牙巴塞羅那計算機視覺中心創建，本文使用120名志愿者的面部圖像，每人26幅。

實驗之前需要進行圖像的歸一化處理，減少背景和頭發對識別的影響，將每幅圖像裁剪成32×32像素大小的灰度圖像。每類隨機抽出一定數目的樣本組成訓練集，其余作為測試集，再使用PCA算法將原始訓練集降到R維（R小于訓練樣本數N）以避免小樣本問題。用隨機選取的方式分別將每個數據集以不同比例劃分為訓練集和測試集，觀察訓練樣本的數量對識別率和訓練時間的影響。

按照經驗，式（1）中的參數 α設為0.5，式（3）中結合夾角度量的最近鄰分類器中的融合參數 β設為0.2。為了研究最終轉換空間維數對識別率的影響，對于轉換矩陣w*的維數r，實驗取5至80之間的不同值。

實驗著重對比了K2取不同值時，NDNFSE識別率和訓練時間的變化。相應地，對NDNFSE中的參數Ne和Ke進行調整，比較當選取的不同類最近鄰特征空間數目大約相同時，NDNFSE和NFSE、NL_IANFSE的識別率及訓練時間。

實驗中的對比算法包括PCA+LPP[3]、PCA[1]、PCA+LDA[5]、PCA+NPE[2]、PCA+NFSE[9]以及 PCA+NL_IANFSE。在測試階段，PCA+LPP、PCA、PCA+LDA、PCA+NPE、PCA+NFSE用NN規則，也就是最近鄰分類器來匹配，NL_IANFSE和NDNFSE則使用結合夾角度量的最近鄰分類器。下文列出的每個識別率都是分別在相同條件下運行10次后求取的平均值。

實驗平臺：上述4個數據集均在Intel Core i3-3240×2CPU的Windows操作系統的計算機上進行實驗，主頻為3.4 GHz，內存為4 GB，編程環境為Matlab R2015a。

4.2 實驗結果與分析

將實驗所得數據整理歸納，用圖、表的形式表示。下面按數據集歸類展示結果，并進行必要的描述和分析。

4.2.1 Yale B數據集

從Yale B數據集的每類中隨機抽取一定數量的樣本用于訓練，其余留作測試集，并通過PCA算法將訓練集降到100維，每個訓練樣本的類內最近鄰特征空間的個數 K1設為10，Ne依次設為3、6、9，Ke設為3，于是每個訓練樣本的不同類最近鄰特征空間依次取9、18、27個。表1列出了NDNFSE、NL_IANFSE和N FSE在每類訓練樣本數分別為10和15個，K2值不同時的最高識別率、標準差和相應的轉換空間維數，以及運行1次平均需要花費的訓練時間。

由表1得，在參數K2相近時，NDNFSE在5到80維的最高識別率均明顯高于NFSE的最高識別率，略高于NL_IANFSE；NDNFSE單次運行所花的訓練時間均少于NL_IANFSE和NFSE的訓練時間。

表2列出了各算法的最高和最低識別率及所在維數、標準差，圖2則描繪了在NDNFSE方法K2=27，NFSE方法K2=30時，各算法在不同維數投影空間的識別率。可以看出，NDNFSE在各個維數的識別率幾乎都要高于對比算法，標準差也較低，說明NDNFSE較為穩定。

Table 1 Recognition rates and training time on Yale B database表1 Yale B數據集上的識別率和訓練時間

Table 2 The highest and the lowest recognition rates,standard derivations on Yale B database表2 Yale B數據集上的最高識別率、最低識別率及標準差

Fig.2 Recognition rates versus dimensionality reduction with various training samples on Yale B database圖2 各算法將Yale B數據集降到不同維數時的識別率

4.2.2 ORL數據集

當ORL數據集每類任取4個樣本組成訓練集時，用PCA算法降至120維，設K1=3；當每類任取5個樣本進行訓練時，訓練集用PCA算法降至160維，設K1=6。NDNFSE中參數Ne，即每類樣本的近鄰類的數目，分別取10、15、20，參數 Ke都取3。在 K2值分別不同的條件下，NDNFSE、NL_IANFSE和NFSE最高識別率、訓練時間等對比如表3所示。

根據實驗結果可知，在參數相同的情況下，NDNFSE用更短的訓練時間達到了和NL_IANFSE、NFSE幾乎相當的最高識別率，尤其當K2值為60的時候NDNFSE的識別率比NFSE高1.96%，但所用的訓練時間只有NFSE的66.1%。

NDNFSE與NFSE的參數K2都設為60時，NDNFSE與對比算法的最高識別率、最低識別率如表4所示。從中可知，NDNFSE的最高識別率高于各對比算法，最低識別率雖然低于某些對比算法，但比NFSE稍高。

4.2.3CMU數據集

PCA算法將CMU訓練集降到300維，設K1為10，Ke為1。表5列出了訓練集每類9個、14個樣本時NDNFSE、NL_IANFSE、NFSE在不同K2值的最高識別率和訓練時間。可見，當K2值相等時，NDNFSE的最高識別率與NL_IANFSE基本持平，比NFSE高出5%左右，而訓練時間要遠遠少于NL_IANFSE和NFSE。

圖3畫出了NDNFSE與對比算法在5～70維的識別率變化曲線，NDNFSE及NFSE均設 K2為30。NDNFSE在各維度的識別率都優于對比算法，在較高維度表現出更明顯的優勢。隨著維數的增大，識別率穩步提升，逐漸趨于穩定。

Table 3 Recognition rates and training time on ORL database表3 ORL數據集上的識別率及訓練時間

Table 4 The highest and the lowest recognition rates,standard derivations on ORL database表4 ORL數據集上的最高識別率、最低識別率及標準差

Table 5 Recognition rates and training time on CMU database表5 CMU數據集上的識別率及訓練時間

Fig.3 Recognition rates versus dimensionality reduction with various training samples on CMU database圖3 各算法將CMU數據集降到不同維數時的識別率

4.2.4 AR數據集

與CMU數據集相同，AR數據集的訓練集通過PCA算法降到300維，Ke=1。每類4個訓練樣本時K1=3，每類6個訓練樣本時K1=6。

NDNFSE、NL_IANFSE和NFSE在不同參數條件下的最高識別率和訓練時間如表6所示。表7是K2=30時NDNFSE與對比算法在各維度投影空間的最高和最低識別率。NDNFSE的最高識別率幾乎高于所有對比算法，而且訓練時間只有NL_IANFSE和NFSE的1/6到1/3。

4.2.5 測試時間

根據3.5節中對測試方法的分析可知，NFSE、NL_IANFSE和NDNFSE的測試時間與K1、K2取值無關，只與訓練集、測試集的劃分比例有關。表8列出了Yale B、ORL、CMU和AR數據集上的參數設置，以及在不同參數設置下3種算法求出單個測試樣本類別所用的測試時間。

NL_IANFSE和NDNFSE使用的結合夾角度量的最近鄰分類器比NFSE使用的傳統最近鄰分類器更復雜，對于每一個測試樣本，都需要求出其與所有訓練樣本的直線距離及夾角，并分別計算距離和夾角的最大、最小值，最后得出待測試樣本與訓練樣本的融合值。因此，當訓練樣本數目越大時，所需的測試時間越長。

Table 6 Recognition rates and training time onAR database表6 AR數據集上的識別率及訓練時間

Table 7 The highest and the lowest recognition rates,standard derivations onAR database表7 AR數據集上的最高識別率、最低識別率及標準差

Table 8 Testing time of single sample algorithms spending on 4 databases表8 在4個數據集上求出單個測試樣本類別所需時間

由表8可以看出，Yale B、ORL數據集上各算法的測試時間差距不是很大，訓練樣本數較多的CMU和AR數據集上，NL_IANFSE和NDNFSE的測試時間明顯比NFSE長。

根據以上4個數據集的實驗結果，可以歸納出以下幾點：

（1）當K2值相等或接近時，NDNFSE的最高識別率與NL_IANFSE相差很小，基本在1%以內，在Yale B和CMU這兩個數據集上比NFSE高5%左右；

（2）NDNFSE運行一次的訓練時間要比NL_IANFSE和NFSE大幅度減少；

（3）在除ORL數據集之外的3個數據集的實驗中，沒有發現NDNFSE得到的識別率隨K2的增大而提高，但是卻發現訓練時間隨K2的增大而迅速增加；

（4）隨著每類訓練樣本數和樣本維數的增加，樣本信息增加，各算法識別率有不同程度提高；

（5）在4個數據集的實驗中，NDNFSE的標準差大多在1%上下，性能比較穩定；

（6）NDNFSE 與 PCA+LPP、PCA、PCA+LDA、PCA+NPE等經典算法相比也具有一定的優勢；

（7）由于分類器不同，NDNFSE和NL_IANFSE的測試時間比NFSE長，并且數據集中訓練樣本數越多，測試時間越長。

5 結束語

本文以NFSE算法為基礎，結合非線性距離公式[14]和結合夾角度量的最近鄰分類器[17]，在一定程度上解決了高維空間中樣本歐氏距離無法準確描述樣本分布的問題，在匹配時充分利用樣本間相似性與其夾角的關系，達到提高識別率的目的。引入文獻[13]中先求近鄰類再選取邊界點的方法，避免了尋找每個樣本的類間最近鄰特征空間時都要遍歷所有類的樣本，節省了大量訓練時間。實驗表明，較之NL_IANFSE、NFSE，NDNFSE單次運行的訓練時間明顯大幅減少，同時能夠保持識別率與NL_IANFSE基本相當，比NFSE等5個經典算法更高。NDNFSE的不足之處是測試階段花費時間比NFSE長，今后工作中需要尋找效率更高的匹配方法。

[1]Turk M A,Pentland A P.Face recognition using eigenfaces[C]//Proceedings of the 1991 Computer Society Conference on Computer Vision and Pattern Recognition,Maui,USA,Jun 3-6,1991.Piscataway,USA:IEEE,1991:586-591.

[2]He Xiaofei,Cai Deng,Yan Shuicheng,et al.Neighborhood preserving embedding[C]//Proceedings of the 10th International Conference on Computer Vision,Beijing,Oct 17-21,2005.Washington:IEEE Computer Society,2005:1208-1213.[3]He Xiaofei,Yan Shuicheng,Hu Yuxiao,et al.Face recognition using Laplacian faces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(3):328-340.

[4]Zhang Taiping,Fang Bin,Tang Yuanyan,et al.Topology preserving non-negative matrix factorization for face recognition[J].IEEE Transactions on Image Processing,2008,17(4):574-584.

[5]Belhumeur P N,Hespanha J P,Kriegman D J.Eigenfaces vs.Fisherfaces:recognition using class specific linear projection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,19(7):711-720.

[6]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(22):2323-2326.

[7]Saul L K,Roweis S T.Think globally,fit locally:unsupervised learning of low dimensional manifolds[J].Journal of Machine Learning Research,2003,4(2):119-155.

[8]Yan Shuicheng,Xu Dong,Zhang Benyu,et al.Graph embedding and extensions:general framework for dimensionality reduction[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(1):40-51.

[9]Chen Y N,Han C C,Wang C T,et al.Face recognition using nearest feature space Embedding[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(6):1073-1086.

[10]Li S Z,Lu Juwei.Face recognition using the nearest feature line method[J].IEEE Transactions on Neural Networks,1999,10(2):439-433.

[11]Gao Jun,Huang Lili,Wang Shitong.Local sub-domains based maximum margin criterion[J].Control and Decision,2014,29(5):827-832.

[12]Chen Y N,Ho G F,Fan K C,et al.Orthogonal nearest neighbor feature space embedding[C]//Proceedings of the 8th International Conference on Intelligent Information Hiding and Multimedia Signal Processing,Piraeus-Athens,Greece,Jul 18-20,2012.Piscataway,USA:IEEE,2012:166-169.

[13]Huang Pu,Chen Caikou.Enhanced marginal Fisher analysis for face recognition[C]//Proceedings of the 2009 International Conference on Artificial Intelligence and Computational Intelligence,Shanghai,Nov 7-8,2009.Washington:IEEE Computer Society,2009:403-407.

[14]Ridder D D,Kouropteva O,Okun O,et al.Supervised locally linear embedding[C]//LNCS 2714:Proceedings of the 2003 Joint International Conference on Artificial Neural Net-works and Neural Information Processing,Istanbul,Turkey,Jun 26-29,2003.Berlin,Heidelberg:Springer,2003:333-341.

[15]Zhang Shiqing,Li Lemin,Zhao Zhijin.Speech emotion recognition based on an improved supervised manifold learning algorithm[J].Journal of Electronics&Information Technology,2010,32(11):2724-2729.

[16]Liu Jiamin,Luo Fulin,Huang Hong,et al.Locally linear embedding algorithm based on fusion angle measurement[J].Opto-Electronic Engineering,2013,40(6):97-105.

[17]Sim T,Baker S,Bsat M.The CMU pose,illumination,and expression database[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2003,25(12):1615-1618.

附中文參考文獻：

[11]皋軍,黃麗莉,王士同.基于局部子域的最大間距判別分析[J].控制與決策,2014,29(5):827-832.

[15]張石清,李樂民,趙知勁.基于一種改進的監督流形學習算法的語音情感識別[J].電子與信息學報,2010,32(11):2724-2729.

[16]劉嘉敏,羅甫林,黃鴻,等.融合夾角度量的局部線性嵌入算法[J].光電工程,2013,40(6):97-105.

DU Hongyan was born in 1990.She is an M.S.candidate at Jiangnan University.Her research interests include artificial intelligence and pattern recognition.

杜弘彥（1990—），女，山西太原人，江南大學碩士研究生，主要研究領域為人工智能，模式識別。

WANG Shitong was born in 1964.He is a professor and Ph.D.supervisor at Jiangnan University.His research interests include artificial intelligence,pattern recognition,image processing and application.

王士同（1964—），男，江蘇揚州人，江南大學教授、博士生導師，主要研究領域為人工智能，模式識別，圖像處理及應用。

Nearest Feature Space Embedding Method Based on Nonlinear Distance Metric*

DU Hongyan+,WANG Shitong
College of Digital Media,Jiangnan University,Wuxi,Jiangsu 214122,China

Nearest feature space embedding(NFSE)method uses traditional Euclidean distance measure to select the nearest feature spaces,which causes within-class scatters and between-class scatters changing synchronously and cannot reflect the distribution of samples in the higher dimensional space accurately.Traversing all the classes when selecting the nearest feature space classes of every sample makes the training time long.To solve above problems,this paper proposes the nearest feature space embedding method based on nonlinear distance metric(NDNFSE),by using nonlinear distance formula to select the nearest feature spaces and using the nearest neighbor classifier combined with Euclidean distance and included angle between two samples to improve the recognition rate.NDNFSE only selects the nearest feature spaces within the nearest classes of every sample to save the training time.According to the experimental results,NDNFSE outperforms comparison algorithms for classification as a whole,with much shorter training time than that of NFSE.

face recognition;nonlinear distance;included angle;nearest feature space embedding;nearest classes

2017-03, Accepted 2017-05.

A

TP181

+Corresponding author:E-mail:18800585201@163.com

DU Hongyan,WANG Shitong.Nearest feature space embedding method based on nonlinear distance metric.Journal of Frontiers of Computer Science and Technology,2017,11(9)：1461-1473.

10.3778/j.issn.1673-9418.1703034

*The National Natural Science Foundation of China under Grant No.61272210(國家自然科學基金).

CNKI網絡優先出版: 2017-05-16, http://kns.cnki.net/kcms/detail/11.5602.TP.20170516.1306.002.html