基于譜回歸判別分析的LPP算法*

楊 凡，張銀玲，牛 靜(浙江師范大學(xué) 數(shù)理與信息工程學(xué)院，浙江 金華321004)

人臉識別中的維數(shù)約簡是一個關(guān)鍵問題，流行的維數(shù)約簡方法包括主成分分析PCA（Principal Component Analysis）[1]、線性判別分析 LDA（Linear Discriminant Analysis）[2]、局部保持投影 LPP(Locality Preserving Projection)[3]等。LPP被認為是一種有效的維數(shù)約簡方法，它在保持數(shù)據(jù)集的局部結(jié)構(gòu)的同時，通過鄰接圖來確認流形結(jié)構(gòu)模型的一種線性變換，它已經(jīng)成功應(yīng)用于許多鄰域[4]。LPP的目的是尋找一個投影矩陣，在投影后，兩個樣本點的距離最小，然而，它卻忽略了樣本間的判別信息。參考文獻[5]中，Yu提出了判別局部保持投影DLPP(Discriminant Locality Preserving Projection）算法，他在 LPP算法中加入了判別信息來提高識別率。但是，在DLPP算法計算過程中,需要解決密度矩陣的特征分解問題，這給時間和內(nèi)存方面帶來了非常高的計算成本。參考文獻[6]中，Cai證明了LDA的空間復(fù)雜度為：O(mnt+t3)，并且占用內(nèi)存為：O(mn+mt+nt),其中m是樣本的個數(shù)，n是類個數(shù)，t=min(m,n)。當(dāng)m和n很大時，應(yīng)用到較大的數(shù)據(jù)集上，幾乎是不可行的。最近，譜方法作為一種有效的維數(shù)約簡方法已經(jīng)運用到人臉識別中。參考文獻[6]中，Cai提出一個新的判別分析算法，即譜回歸判別分析SRDA(Spectral Regression Discriminant Analysis)。通過使用譜圖分析，SRDA將判別分析投射到回歸框架上，它只需要解決一系列正則化的最小二乘問題，而不需要計算特征向量，節(jié)省了時間和內(nèi)存的消耗，在計算方面明顯地優(yōu)于LDA算法。本文提出了一種新的改進算法——譜回歸判別局部保持投影SRDLPP(Spectral Regression Discriminant Locality Preserving Projection)。其在LPP算法中加入了譜回歸判別分析算法,這樣可以避免解密度矩陣特征分解時帶來的高昂的內(nèi)存和時間的消耗。分別在Yale、Orl和擴展Yale_B人臉庫上進行實驗，實驗結(jié)果表明，本算法優(yōu)于其他算法。

1 算法介紹

1.1 LDA算法

線性判別分析LDA(Linear Discriminant Analysis)是從高維特征空間中提取出最具有判別能力的低維特征，以達到抽取分類信息和壓縮特征空間維數(shù)的效果，投影后保證樣本在新的子空間有最大的類間距離和最小的類內(nèi)距離。算法思想如下：

假設(shè)對于一個 Rn空間有{xi}個樣本分別為 x1,x2,…,xm，即每個 x是一個 N×M行的矩陣，假設(shè)有 C個類，則n1+n2+…+ni+…+nc=m。

樣本類間離散度矩陣定義為：

樣本類內(nèi)離散度矩陣定義為：

LDA的目的是尋找一個變換矩陣W：

在過去的幾十年中，有人提出各種各樣的方法來解決這個問題(例如SVD、PCA+LDA等方法)[2,8-11]。譜回歸判別分析算法思想來源于譜方法SR(Spectral Regression)。SR算法從根本上是基于回歸和譜圖分析[12]。SR能夠有效地應(yīng)用標(biāo)記點和非標(biāo)記點來發(fā)現(xiàn)數(shù)據(jù)內(nèi)在的固有的判別式結(jié)構(gòu)。這個圖用于得到標(biāo)記點和非標(biāo)記點的學(xué)習(xí)響應(yīng)。一旦得到響應(yīng)，嵌入函數(shù)可以通過一般的回歸模型得到。SR算法避免了解密度矩陣的特征分解問題。根據(jù)SR算法，CAI提出SRDA算法。

1.2 SRDA算法

為了有效解決LDA方程(4)的特征問題，利用如下定理：

定理1求特征方程(4)的解，從下列兩步獲得：

稱為正則化，在統(tǒng)計學(xué)中有很好的研究。正則的最小二乘法同樣被稱為脊回歸[13]。該算法是在圖的譜分析之后對LDA的特征方程進行回歸處理,因此稱為譜回歸判別分析，簡記為SRDA。

1.3 SRDLPP算法

根據(jù)以上的分析可知，LDA的計算包括解密度矩陣的特征分解，這使得時間內(nèi)存上都帶來了很大的消耗。SRDA算法可以有效地節(jié)省時間和內(nèi)存。受SRDA算法啟發(fā)，本文提出一種改進的LPP算法：譜回歸判別局部保持投影 SRDLPP(Spectral Regression Discriminant Locality Preserving Projection)。算法如下：

LPP的目的是尋找xi經(jīng)過投影后在低維空間中對應(yīng)的 點 yi，yi=aTxi。 Y=[y1,y2,…,ym], 是 一 個(d×m)矩 陣(d<

W是對稱的矩陣,最小化目標(biāo)函數(shù)就是要確保當(dāng)ai和aj距離很近時，yi和yj的距離也很近。

(1)創(chuàng)建鄰接圖：設(shè)G是表示m個頂點的圖，每一個頂點代表一個數(shù)據(jù)點。W是對稱的m×m矩陣,表示連接點i和j的權(quán)值為Wij。這里采用K鄰域法構(gòu)造權(quán)值矩陣W。

用 Nk(xj)表示 xi的 K鄰域集。

在一定的約束條件下使得式(8)中y是最佳的，描述為：

那么a就是下列方程最小特征值問題對應(yīng)的特征向量：

(2)特征分解：計算特征方程(13)的解，可以從以下兩步中獲得：

根據(jù)定理1：

①求解特征問題式（11）得到y(tǒng).

其中最優(yōu)化的y是下列特征問題的最大特征向量

又因為存在一個線性函數(shù)：yi=aTxi

則特征方程(11)為：

(3)正則化最小二乘問題：根據(jù)上面分析，最小化方程(14)可能是病態(tài)的，所以加入一個范數(shù)a：

找到 d 個向量 a1,…，ad∈Rn,aj=(j=1,…,c-1)。

2 SRDA嵌入到LPP中

設(shè) A=[a1,…，ad]，A 是 n×(c-1)變換矩陣，樣本數(shù)據(jù)點可以嵌入 c-1維空間中：xi→yi=ATxi,A=[a1,a2,…，ad]

y是樣本點數(shù)據(jù)的d維表示，A是本文算法的轉(zhuǎn)變矩陣。根據(jù)以上分析，在數(shù)據(jù)庫上進行實驗。

3 實驗結(jié)果與分析

3.1 Yale人臉庫

Yale人臉庫共有165張人臉圖像，每個人有11張的表情照片，歸一化為32×32人臉圖像。這些照片有戴眼鏡、不戴眼鏡、開心、悲傷等，共11種表情。Gp/Pq表示每人隨機選取p張訓(xùn)練集人臉訓(xùn)練，q張測試集人臉測試。 每一個訓(xùn)練集選取（3，4，5，6，7，8）圖像，例如：3 訓(xùn)練集表示訓(xùn)練圖像共有45張人臉用來訓(xùn)練，剩余8測試集共120張人臉用來測試。為了確保實驗結(jié)果的可靠性，每次實驗重復(fù)20次，取平均識別率和時間消耗值，正則化參數(shù)a根據(jù)經(jīng)驗選擇0.01。實驗結(jié)果如表1、表2所示。表1、表2顯示了Yale人臉庫上的識別率和時間消耗,可以看出,本文算法的結(jié)果優(yōu)于DLPP和LPP算法。DLPP需要計算密度矩陣特征分解問題，它占用更多的時間和內(nèi)存；對于LPP來說，當(dāng)訓(xùn)練數(shù)增加時，識別率下降；本文提出的算法最高識別率達到94.53%。表2表示每一次識別的平均時間，當(dāng)訓(xùn)練樣本數(shù)增加時，DLPP時間消耗越多。

表1 Yale人臉庫識別率 (%)

3.2 ORL人臉庫

表3 在ORL人臉庫識別率 (%)

表4 在ORL人臉庫上時間消耗 (s)

ORL人臉庫，共有40人，每人有10幅圖像，這些圖像包含表情和姿態(tài)變化。原圖像的大小為112×92，在預(yù)處理階段，統(tǒng)一歸一化成32×32大小的人臉圖像。隨機選擇每人(3，4，5，6，7，8)圖像 集作為 訓(xùn)練,其他作為測試。例如：3訓(xùn)練集共120個人臉圖像作為訓(xùn)練，余下7測試集共280個人臉圖像作為測試。為了確保得到穩(wěn)定的實驗結(jié)果，每次實驗重復(fù)20次。取平均識別率和平均時間消耗。實驗結(jié)果如表3、表4所示。 DLPP 的 識別率優(yōu)于本文提出的算法和LPP算法。但是它同時也消耗了大量的時間。計算平均數(shù)據(jù)集每一次所占用的時間消耗，最高的達到50 s。

3.3 擴展 Yale_B人臉庫

擴展的Yale_B人臉數(shù)據(jù)庫包含16 128幅人臉圖像，共38類，9種姿態(tài)65種細節(jié)下進行，本文選擇正面且所有的圖片細節(jié)不同，每人得到64圖片。所有人臉圖片剪裁為 32×32像素，256灰度級。 特征(像素值)在[0，1]之間（除以256）。實驗結(jié)果如表 5、表6所示。

表5 在擴展Yale_B人臉庫識別率 (%)

表6 在擴展Yale_B人臉庫上時間消耗(s)

表5、表6為在擴展的Yale_B人臉庫上的識別率和時間消耗?？梢?，DLPP的識別率比較高，但是占用了太多的時間，平均識別一次所需要時間最高達到900 s。本文提出的算法最高識別率達到95.91%.

綜合以上3個實驗結(jié)果可知，本文提出的算法，在一定程度上提高了識別率，特別是時間消耗方面具有明顯的優(yōu)勢，尤其是在數(shù)據(jù)集較大的情況下，優(yōu)勢越明顯。

本文提出一種新的人臉識別算法——譜回歸判別局部保持投影算法SRDLPP（Spectral Regression Discriminant Locality Preserving Projection）。它利用譜回歸判別分析的思想加入到局部保持投影中。實驗結(jié)果表明，雖然DLPP的識別率有較好的效果，但是由于它需要計算密度矩陣求解特征問題，占用了很大的時間和內(nèi)存消耗，在實際運用中存在弊端。譜回歸判別分析算法只需要解決一系列正則化的最小二乘問題，而不需要計算特征問題，這大大地節(jié)省了時間和內(nèi)在的消耗。SRDLPP算法不僅提高了識別率而且時間和內(nèi)存的消耗都比較少。分別在Yale、Orl及擴展Yale_B人臉庫上進行實驗，結(jié)果表明該算法具有高效的識別率、低的時間及內(nèi)存消耗。

[1]MARDIA K V,KENT J T,BIBBY J M.Multivariate analysis[M].Academic Press,1980.

[2]SWETS D L,WENG J Y,Using discriminant eigenfeatures for image retrieval[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1996,18(8):831-836.

[3]He Xiaofei,NIYOGI P.Locality preserving projections[A].Neural Information Processing System[C].Vancouver:MIT Press,2003.

[4]FOLEY D H,SAMMON J W Jr.An optimal set of discriminant vectors,IEEE Transactions on Computer,1975,C-24(3):281-289.

[5]Yu Weiwei,Teng Xiaolong,Liu Chongqing.Face recognition using discriminant locality preserving projections[J].Image and Vision Computer,2006(24):239-248.

[6]Cai Deng,He Xiaofei,Han Jiawei.SRDA：an efficient algorithm for large scale discriminant analysis[J].IEEE Transactions on Knavledge and Data Engineering,2008,20(1):1-12.

[7]FUKUNAGA K.Introduction to statistical pattern recognition 2nd edition[M].Academic Press,1990.

[8]TORKKOLA K.Linear discriminant analysis in document classification[C].Proceedings of IEEE ICDM Workshop Text Mining,2001.

[9]HOWLAND P,PARK H.Generalizing discriminant analysis sing the generalized singular value decomposition[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(8):995-1006.

[10]YE J.Characterization of a family of algorithms for generalized discriminant analysis on undersampled problems[J].Journal of Machine Learning Research,2005(6):483-502.

[11]FRIEDMAN J H.Regularized discriminant analysis[J].Journal of the American Statistical Association,1989,84(405):165-175.

[12]CHUNG F R K.Spectral graph theory[M].AMS,1997.

[13]HASTIE T,TIBSHIRANI R,FRIEDMAN J.The elements of statistical learning:data mining,inference,and prediction[M].New York:Springer-Verlag,2001.