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

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

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

1 算法介紹

1.1 LDA算法

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

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

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

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

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

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

1.2 SRDA算法

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

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

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

1.3 SRDLPP算法

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

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

W是對稱的矩陣,最小化目標函數就是要確保當ai和aj距離很近時，yi和yj的距離也很近。

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

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

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

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

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

根據定理1：

①求解特征問題式（11）得到y.

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

又因為存在一個線性函數：yi=aTxi

則特征方程(11)為：

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

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

2 SRDA嵌入到LPP中

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

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

3 實驗結果與分析

3.1 Yale人臉庫

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

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

3.2 ORL人臉庫

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

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

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

3.3 擴展 Yale_B人臉庫

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

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

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

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

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

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

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