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

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

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

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

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

1 局部線性嵌入(LLE)

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

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

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

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

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

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

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

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

在計(jì)算樣本點(diǎn)之間的距離時，SLLE算法采用如下公式:

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果及分析

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

圖1～圖2是LLE算法與本文SSLLE算法在Yale和ORL人臉庫中識別率隨著鄰域數(shù)目k變化的對比曲線圖。對LLE算法而言，Yale人臉庫在k=10和k=12時識別率達(dá)到最大，ORL人臉庫在k=6時識別率達(dá)到最大;對本文SSLLE算法而言，Yale人臉庫在k=8時識別率達(dá)到最大;ORL人臉庫在k=6時識別率達(dá)到最大。所以后續(xù)實(shí)驗(yàn)里，LLE算法在Yale和ORL人臉庫中鄰域數(shù)目k分別取值為10和6，本文SSLLE算法在Yale和ORL人臉庫中鄰域數(shù)目k分別取值為8和6。另外k值對識別率有著一定的影響，一定范圍內(nèi)隨著k值的增大，識別率會有所提高，但是當(dāng)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人臉庫中對應(yīng)不同特征維數(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可以看出，在對應(yīng)不同特征維數(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í)驗(yàn)數(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人臉庫上對一幅測試圖像進(jìn)行分類識別所需時間的比較。從表中可看出，本文SSLLE算法以較小的時間代價提高了識別率，完全滿足人臉識別系統(tǒng)的實(shí)時性要求。

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

5 結(jié)論

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

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

［2］解洪勝，王連國.流形學(xué)習(xí)中三種非線性降維算法的比較研究［J］.云南民族大學(xué)學(xué)報:自然科學(xué)版，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］王玨，周志華，周傲英.機(jī)器學(xué)習(xí)及其應(yīng)用［M］.北京:清華大學(xué)出版社，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］.計(jì)算機(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］王朝.基于流形學(xué)習(xí)的人臉識別算法的研究［D］.大連:大連理工大學(xué)，2009.

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