半監(jiān)督局部線性嵌入算法在人臉識別中的應用

沈 杰，楊月全，王正群，唐擁政，王明輝

(1.鹽城工學院 現(xiàn)代教育技術(shù)中心，江蘇 鹽城 224051;2.揚州大學 信息工程學院，江蘇 揚州 225009)

流形學習(Manifold Learning，ML)［1，2］是近幾年興起的一種新型機器學習思想，在模式識別、數(shù)據(jù)挖掘和計算機視覺等領域受到了廣泛的關(guān)注和應用。隨著信息技術(shù)的飛速發(fā)展，人們獲得的數(shù)據(jù)呈現(xiàn)出海量、高維和不確定性等特點，如何對高維數(shù)據(jù)采用某種維數(shù)約簡方法進行降維處理就顯得尤為迫切，也是目前的研究熱點。傳統(tǒng)的降維方法如主成分分析［3］(Principal Component Analysis，PCA)和線性判別分析［4］(Linear Discriminant Analysis，LDA)在高維數(shù)據(jù)集具有線性結(jié)構(gòu)和高斯分布時能有比較好的效果，但是當數(shù)據(jù)集在高維空間呈現(xiàn)高度扭曲時，它們很難發(fā)現(xiàn)嵌入在數(shù)據(jù)集中的非線性結(jié)構(gòu)和恢復內(nèi)在的結(jié)構(gòu)。流形學習方法提供了一種新的研究途徑［5］。

流形學習的目標是對訓練集中的高維數(shù)據(jù)空間進行非線性降維，揭示其流形分布，從而找出隱藏在高維觀測數(shù)據(jù)中的有意義的低維結(jié)構(gòu)，以便從中提取易于識別的特征。2000年Seung、Tenenbaum和Roweis等人在《Science》上發(fā)表了3篇論文［6－8］，從認知的角度探討了流形學習，不僅首次使用了“Manifold Learning”這一術(shù)語，而且還給出了可行性算法，為維數(shù)約簡提供了一個新的研究方向，從而引起了流形學習的研究熱潮。著名的流形學習算法有:等距映射［7］(Isometrical Mapping，ISOMAP)、局部線性嵌入［8］(Locally Linear Embedding，LLE)、拉普拉斯特征映射［9］(Laplacian Eigenmap，LE)、局部切空間排列［10］(Local Tangent Space Alignment，LTSA)等。這些算法均能較好的保持原始數(shù)據(jù)的拓撲結(jié)構(gòu)，并有效的解決數(shù)據(jù)處理中的維數(shù)災難問題。

局部線性嵌入算法是流形學習中的經(jīng)典方法，是一種借助局部線性關(guān)系描述全局非線性結(jié)構(gòu)的降維思想。針對LLE算法非監(jiān)督學習的缺陷，Ridder等人提出了一種監(jiān)督局部線性嵌入［11］(Supervised Locally Linear Embedding，SLLE)算法，但監(jiān)督學習算法需要所有樣本具有標簽信息，在機器學習相關(guān)問題中，所獲取的大多是不帶標簽的數(shù)據(jù)，帶標簽的數(shù)據(jù)則相對有限，因此半監(jiān)督流形學習成為模式識別和機器學習領域研究的一個新的熱點。本文引入半監(jiān)督思想，提出了一種基于半監(jiān)督局部線性嵌入［12］(Semi－Supervised Locally Linear Embedding，SSLLE)的人臉圖像識別方法，對經(jīng)典LLE算法進行了改進，增加了部分樣本的標簽信息，使之能適應半監(jiān)督流形學習［13］，最后使用最近鄰分類器進行分類識別，在Yale和ORL人臉庫上進行了實驗比較，驗證了本文提出的算法具有較高的識別率。

1 局部線性嵌入(LLE)

局部線性嵌入算法是由Roweis和Saul提出的一種非線性流形學習方法［8］。LLE算法的基本假設是:①流形上的任意一個樣本點都能由其鄰域點線性重構(gòu)而成，并且重構(gòu)權(quán)值可以保證樣本點與鄰域點的線性重構(gòu)誤差最小;②在映射過程中保持這種線性關(guān)系不變，即在低維空間中保持每個鄰域中的重構(gòu)權(quán)值不變，這樣可以得到高維數(shù)據(jù)在低維空間的嵌入。

設數(shù)據(jù)集中有 N 個樣本點 xi，xi∈RD，i∈［1，N］，降維后的 N 個樣本點為 yi，yi∈Rd，i∈［1，N］，d?D。LLE 算法步驟如下［14］:

步驟1:選取鄰域。一般使用K近鄰法，即對數(shù)據(jù)集中的每個樣本點xi，尋找歐氏距離與其最近的k個點作為它的近鄰。另外也可采用ε鄰域方法來確定鄰域。

步驟2:計算重構(gòu)權(quán)值矩陣W。由上步確定的鄰域關(guān)系，每一個樣本點xi都可以由它的k個近鄰點通過權(quán)值Wij線性加權(quán)表示。最小化如下定義的代價函數(shù)，可以得到約束的權(quán)值矩陣W。

步驟3:計算低維嵌入。構(gòu)造代價函數(shù)

其中，yi是xi的低維映射矢量，yj是xi的近鄰xj的低維映射矢量。最小化代價函數(shù)ε(y)，使得低維重構(gòu)誤差最小，則yT(y是由所有yi為列向量所組成的矩陣)取M的最小d個非零特征值所對應的特征向量，M=(I－W)T(I－W)。在實際處理過程中，由于M的最小非零特征值幾乎接近于零，所以yT通常取M最小的第2個到第d+1個非零特征值所對應的特征向量。

2 監(jiān)督局部線性嵌入(SLLE)

LLE算法是一種非監(jiān)督的算法，沒有利用樣本的類別信息，針對此缺點，Ridder等人提出了一種監(jiān)督局部線性嵌入［11］(Supervised Locally Linear Embedding，SLLE)算法。SLLE算法與傳統(tǒng)LLE算法的主要區(qū)別在于第1步鄰域的構(gòu)造:LLE算法在構(gòu)造鄰域時是根據(jù)樣本點間的歐氏距離來尋找k個近鄰點，而SLLE算法在處理這一步時，增加了樣本點的類別信息。SLLE算法的其余步驟同LLE算法一致。

在計算樣本點之間的距離時，SLLE算法采用如下公式:

其中D'是計算后的距離;D定義為樣本點之間的距離;max(D)表示類與類之間的最大距離;△取0或1，當兩個樣本點屬于同類時，△取0，否則取1;α是控制點集之間的距離參數(shù)，當α取0時，此時的SLLE算法和LLE算法相同。

3 半監(jiān)督局部線性嵌入(SSLLE)

本文將半監(jiān)督思想引入LLE算法，提出了一種基于半監(jiān)督局部線性嵌入［12］(Semi－Supervised Locally Linear Embedding，SSLLE)算法，通過部分帶標簽的樣本來重新調(diào)整距離矩陣，使得LLE算法能夠更準確的構(gòu)造樣本點的鄰域。

其中r(0＜r＜1)是調(diào)節(jié)系數(shù)，一般取經(jīng)驗值，可以用來判定帶標簽樣本和不帶標簽樣本是否可以被選為近鄰點。

在確定了每個樣本點的k個近鄰點后，SSLLE算法的其余步驟與LLE算法相同。SSLLE算法可以有效的學習非線性流形結(jié)構(gòu)，考慮了樣本的類別信息，利用部分樣本的標簽信息來重新調(diào)整距離矩陣，實現(xiàn)了不同類別標簽樣本之間的良好可分，并取得了較好的降維效果。

4 實驗結(jié)果及分析

實驗是在Yale和ORL人臉庫上完成的(實驗環(huán)境:Intel酷睿2雙核E84003.0 GHz;Matlab 7.0)，分別用LLE算法和本文SSLLE算法來提取人臉有效特征，最后通過最近鄰分類器測試了這兩種算法的識別效果(經(jīng)過多次重復實驗，取其平均值)，并進行了綜合比較和分析。Yale人臉庫15個人每人隨機取5幅圖像共75幅進行訓練，剩余每人6幅圖像共90幅進行測試。ORL人臉庫40個人每人隨機取5幅圖像共200幅進行訓練，剩余每人5幅圖像共200幅進行測試。對于本文SSLLE算法而言，Yale和ORL人臉庫都是每人取5幅圖像具有類別標簽，另調(diào)節(jié)系數(shù)r取經(jīng)驗值 0.5。

圖1～圖2是LLE算法與本文SSLLE算法在Yale和ORL人臉庫中識別率隨著鄰域數(shù)目k變化的對比曲線圖。對LLE算法而言，Yale人臉庫在k=10和k=12時識別率達到最大，ORL人臉庫在k=6時識別率達到最大;對本文SSLLE算法而言，Yale人臉庫在k=8時識別率達到最大;ORL人臉庫在k=6時識別率達到最大。所以后續(xù)實驗里，LLE算法在Yale和ORL人臉庫中鄰域數(shù)目k分別取值為10和6，本文SSLLE算法在Yale和ORL人臉庫中鄰域數(shù)目k分別取值為8和6。另外k值對識別率有著一定的影響，一定范圍內(nèi)隨著k值的增大，識別率會有所提高，但是當k取值較大以后，識別率將有所回落并趨于穩(wěn)定。

圖1 LLE算法與本文SSLLE算法在Yale人臉庫中鄰域數(shù)目k與識別率的關(guān)系Fig.1 The relations between neighborhood number k and recognition rate of LLE algorithm and SSLLE algorithm on Yale face database

圖2 LLE算法與本文SSLLE算法在ORL人臉庫中鄰域數(shù)目k與識別率的關(guān)系Fig.2 The relations between neighborhood number k and recognition rate of LLE algorithm and SSLLE algorithm on ORL face database

圖3～圖4是LLE算法與本文SSLLE算法在Yale和ORL人臉庫中對應不同特征維數(shù)d時，所取得的識別率的對比曲線圖。對LLE算法而言，Yale人臉庫在d=25和d=60時獲得最高識別率(91.6%)，ORL人臉庫在d=30時獲得最高識別率(91.2%);對本文SSLLE算法而言，Yale人臉庫在d=55時獲得最高識別率(95.6%)，ORL人臉庫在d=40時獲得最高識別率(94.5%)。另外d值對識別率有著明顯的影響，最初隨著d值的增加，識別率會迅速上升(有時會有波動，比如Yale人臉庫SSLLE算法)然后中間出現(xiàn)一個峰值(Yale人臉庫LLE算法比較特殊，出現(xiàn)兩次峰值)，以后隨著d值的增加，識別率將有所回落并趨向于穩(wěn)定。從圖3和圖4可以看出，在對應不同特征維數(shù)d時，本文SSLLE算法取得的識別率整體上要比LLE算法高。

圖3 LLE算法與本文SSLLE算法在Yale人臉庫中識別率與特征維數(shù)的關(guān)系Fig.3 The relations between recognition rate and feature dimension of LLE algorithm and SSLLE algorithm on Yale face database

圖4 LLE算法與本文SSLLE算法在ORL人臉庫中識別率與特征維數(shù)的關(guān)系Fig.4 The relations between recognition rate and feature dimension of LLE algorithm and SSLLE algorithm on ORL face database

表1給出本文SSLLE算法和其它算法在Yale和ORL人臉庫上所獲得的平均識別率的實驗數(shù)據(jù)。從表中可看出，本文SSLLE算法在Yale和ORL人臉庫上都獲得了較高的識別率。

表1 各算法在Yale和ORL人臉庫上的平均識別率Table 1 The average recognition rate of each algorithm on Yale and ORL face database %

表2給出本文SSLLE算法和其它算法在Yale和ORL人臉庫上對一幅測試圖像進行分類識別所需時間的比較。從表中可看出，本文SSLLE算法以較小的時間代價提高了識別率，完全滿足人臉識別系統(tǒng)的實時性要求。

表2 各算法在Yale和ORL人臉庫上的分類識別時間(ms)Table 2 The recognition time of each algorithm on Yale and ORL face database

5 結(jié)論

本文在對局部線性嵌入(LLE)算法分析的基礎上提出了一種半監(jiān)督局部線性嵌入(SSLLE)算法，并將該算法應用于人臉識別。針對LLE算法非監(jiān)督的缺陷，對其進行了改進，增加了部分樣本的標簽信息，使之能適應半監(jiān)督流形學習。在Yale和ORL人臉庫上的實驗結(jié)果表明，本文SSLLE算法具有良好的降維效果和較高的識別率，利用較少的標簽信息有效的提高了人臉識別的性能，符合現(xiàn)代工程應用的實時性要求。

［1］周波.2種基于譜方法的流形學習算法研究［J］.云南民族大學學報，2008，17(4):370－373.

［2］解洪勝，王連國.流形學習中三種非線性降維算法的比較研究［J］.云南民族大學學報:自然科學版，2009，18(2):151－156.

［3］Turk M，Pentland A.Eigenfaces for recognition［J］.Journal of Cognitive Neuroscience，1991，3(1):71－86.

［4］Belhumeur P N，Hespanha J P，Kriegman D J.Eigenface vs.fisherfaces:recognition using class specific linear projection［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19:711－720.

［5］王玨，周志華，周傲英.機器學習及其應用［M］.北京:清華大學出版社，2006.

［6］Seung H S，Lee D D.The manifold ways of perception［J］.Science，2000，290(5500):2268－2269.

［7］Tenenbaum J B，de Silva V，Langford J C.A global geometric framework for nonlinear dimensionality reduction［J］.Science，2000，290(5500):2319－2323.

［8］Roweis S T，Saul L K.Nonlinear dimensionality reduction by locally linear embedding［J］.Science，2000，290(5500):2323－2326.

［9］Belkin M，Niyogi P.Laplacian eigenmaps for dimensionality reduction and data representation［J］.Neural Computation，2003，15(6):1373－1396.

［10］Zhang Z Y，Zha H Y.Principal manifolds and nonlinear dimensionality reduction via tangent space alignment［J］.SIAM Journal of Scientific Computing，2004，26(1):313－338.

［11］De Ridder D，Kouropteva O，Okun O，et al.Supervised locally linear embedding［C］.Artificial Neural Networks and Neural Information Processing－ICANN/ICONIP 2003 Lecture Notes in Computer Science，2003，2714:333－341.

［12］張長帥，周大可，楊欣.一種基于核的半監(jiān)督局部線性嵌入方法［J］.計算機工程，2011，37(20):157－159.

［13］Yang X，F(xiàn)u H Y，Zha H Y，et al.Semi－supervised nonlinear dimensionality reduction［C］.Proceedings of the 23th International Conference on Machine Learning，2006:1065－1072.

［14］王朝.基于流形學習的人臉識別算法的研究［D］.大連:大連理工大學，2009.

［15］李見為，樊超，王瑋.監(jiān)督局部線性嵌入在人臉識別中的應用［J］.重慶大學學報，2010，33(2):92－97.