基于L2范數的局部保持投影算法

丁銘,賈維敏,姚敏立

(1.第二炮兵工程大學907教研室, 710025, 西安;2.第二炮兵工程大學403教研室, 710025, 西安)

?

基于L2范數的局部保持投影算法

丁銘1,賈維敏1,姚敏立2

(1.第二炮兵工程大學907教研室, 710025, 西安;2.第二炮兵工程大學403教研室, 710025, 西安)

針對傳統(tǒng)局部保持投影算法對外點敏感的問題,提出了一種基于L2范數的局部保持投影算法。該算法通過采用L2范數定義目標函數并重新定義了權值矩陣,多次迭代計算投影矩陣得到局部最小值,直至達到收斂條件,進而獲得最終的最優(yōu)投影矩陣;通過利用最優(yōu)投影矩陣將原始數據投影到最優(yōu)的投影子空間,降低高維數據維度,同時能夠保持原有數據特征。合成數據實驗結果表明,與傳統(tǒng)局部保持投影算法相比,所提基于L2范數的局部保持投影算法能夠有效地降低數據維度,改善了算法對外點的敏感問題,提高了算法的魯棒性。人臉識別實驗結果表明,該算法能夠取得較高且較為穩(wěn)定的人臉識別率,人臉識別率可達80%。

降維;局部保持投影;L2范數

隨著信息爆炸時代的來臨,信息獲取的數據量越來越大,這些信息、數據,特別是高維數據的有效處理,成為了迫切需要解決的問題和巨大的挑戰(zhàn)。因此,如何降低數據維度[1-3]成為處理高維數據的必要過程。降維算法旨在尋找一個低維子空間來表示高維數據固有的內在結構,通過將高維數據投影到低維子空間,剔除高維數據中不相關的部分,使固有的內在結構得到更清晰的表示。

經典的數據降維方法有主成分分析(principal component analysis, PCA)[3]、線性判別分析(linear discriminant analysis, LDA)[4]以及局部保持投影算法(locality preserving projections, LPP)[5-7],然而PCA、LDA均將原始高維數據假定為線性結構繼而進行線性降維。近期研究表明,當高維數據存在于一個低維流形時,不能將高維數據假定為線性結構,因此,采用流形學習的方式對數據進行降維是當前的趨勢。LPP作為流形學習中的一種算法,具有更為廣泛的應用,當原始數據非線性時,LPP可以使數據得到較為準確的表示,并且提供從高維空間到低維空間的顯式映射;同時,PCA與LDA均是注重保持數據的全局結構,而在人臉識別[8-10]、信息檢索等領域,數據的局部結構對于識別更為重要,LPP注重保持數據的局部結構有利于進行識別。

LPP雖然能夠對數據進行相對準確的表征,保持局部信息,但是分析LPP算法的目標函數可以發(fā)現,其目標函數采用的是L2范數的平方,對外點敏感。為此,本文提出了一種基于L2范數的局部保持投影算法(locality preserving projections based on L2 norm, LPP-L2),該算法在有效降低數據維度的基礎上,能夠保證較高的目標識別正確率,同時降低對外點的敏感度,提高算法的魯棒性。

1 基于L2范數局部保持投影算法

1.1 算法原理

LPP算法能夠克服PCA算法與LDA算法的不足,并且很好地保持了高維數據固有的幾何結構和局部結構。LPP算法中的目標函數為

‖yi-yj‖2Sij

(1)

式中:輸入數據為X={x1,x2,x3,…,xn},X∈Rd×n;yi=WTxi表示xi在投影矩陣W∈Rd×m構成的子空間上的投影;S是權值矩陣。

式(1)中運用了L2范數的平方,將會使高維數據中的外點呈平方倍放大,這樣會導致LPP算法對于外點十分敏感,導致無法對高維數據進行準確的降維,同時進行分類識別時識別準確率降低。

為了克服上述LPP算法存在的問題,借鑒文獻[11-13]聚類方法的思想,將其引入到降維算法中,提出了LPP-L2算法。文獻[11]中對傳統(tǒng)的歸一化割聚類模型進行改進,設有n個數據點{x1,…,xn}∈Rd×1,W∈Rn×n為構造圖所需的權值矩陣,Q=[q1,q2,…,qc]∈Rn×c為聚類指標矩陣,其中qk∈Rn×1為矩陣Q的第k列,傳統(tǒng)的歸一化割聚類模型表示為

(2)

當xi與xj屬于同一聚類時,此時式(7)中Q的最優(yōu)解為qi=qj,對于一些數據對(i,j)存在‖qi-qj‖2=0,因此使用范數作為目標函數,將其改進為

根據文獻[13]中的改進方式,改進LPP算法的目標函數,即LPP-L2算法的目標函數為

‖WTxi-WTxj‖2

(3)

由于本文中外點即數值較大的點,采用范數作為目標函數與采用范數的平方作為目標函數相比,外點的值將不會造成平方倍的增大,即運用L2范數代替原有的L2范數的平方,可以避免在存在外點的情況下,大部分局部近鄰的數據之間的距離最小化,而個別近鄰數據的距離卻相距很遠,但是使用范數作為目標函數抑制外點由此帶來的問題就是計算復雜度的提高,2.2節(jié)對計算復雜度進行了理論分析與實驗說明。

運用拉格朗日函數解式(3)得到

‖WTxi-WTxj‖2-

tr(Λ(WTXDXTW-Im))

(4)

(5)

(6)

根據式(6),式(4)可以簡化為

tr(Λ(WTXDXTW-Im))=

(7)

1.2 收斂性證明

要證明收斂性,首先需要證明以下兩個不等式成立。

(1)對于標量x,存在

2|x|-x2-1≤0

(8)

證明 令f(x)=2x1/2-x-1,可以得到f′(x)=x-1/2-1,f″(x)=-1/2x-3/2。顯然,當x>0時,f″(x)<0且f″(x)當且僅當x=1時,存在f′(x)=0。由于x=1時,f(x)=0,即當x>0時,f(x)單調遞減且f(x)≤0,則f(x2)≤0,即2|x|-x2-1≤0。

(2)對于任意非零向量v和v0,存在

(9)

證明 由步驟1可以得到

根據上述不等式可以得到收斂性定理,即目標函數式(3)為單調遞減函數,經過每一次迭代均會收斂到一個局部最小值。

證明 根LPP-L2據算法的源理,將迭代計算得到的更新投影矩陣定義為

因此可以得到

(10)

根據步驟2可以得到

(11)

將式(10)、式(11)相加得到

(12)

2 實驗與結果

本節(jié)通過合成數據實驗以及人臉識別實驗來驗證算法的魯棒性和有效性。

2.1 S curve曲線合成數據實驗

合成的“S curve”曲線數據中包含500個數據點,同時加入不同數目的外點以驗證算法的魯棒性。分別在合成數據中加入100個和200個隨機外點,“S curve”曲線由以下方式合成:x=12.5[cost,-cost],y=h,x=6[sint,2-sint],其中t∈[-π,π/2],h∈[0,41]。隨機的外點滿足以下條件:x∈[0,30],y∈[0,40],z∈[0,30]。之后運用傳統(tǒng)的LPP算法以及LPP-L2算法對已加外點的三維合成數據進行降維,將其投影到二維空間。圖1～圖3分別為加入100個外點時的“S curve”曲線和運用LPP算法及LPP-L2算法降維的結果,圖4～圖6分別為加入200個外點時的“S curve”曲線和運用LPP算法及LPP-L2算法降維的結果,其中X、Y、Z軸均為Matlab R2014a自動生成,坐標軸的數值沒有實際意義,對實驗結果不會產生不良影響。

圖1 加入100個外點時的“S curve”曲線

圖2 LPP算法的降維結果

圖3 LPP-L2算法的降維結果

圖4 加入200個外點時的“S curve”曲線

圖5 LPP算法的降維結果

圖6 LPP-L2算法的降維結果

根據圖1～圖3可以發(fā)現,即使在外點數僅有100個的情況下,LPP算法的降維效果受到了外點極大的影響,但LPP-L2算法仍然能夠提取有效的特征,使得投影后的結果仍然是“S curve”曲線。

根據圖4～圖6可知,在外點數較多(200個)的情況下,LPP-L2算法能夠很好地保持“S curve”的固有結構,克服了原有LPP算法對于外點十分敏感的問題。

2.2 AR人臉數據庫實驗

AR人臉數據庫由西班牙巴塞羅那計算機視覺中心建立,包含兩組圖像,分別是間隔2周所拍攝。每組120人,其中65人為男性,55人為女性,每組每人13幅圖片,前4幅為表情變化,5～7幅為光照變化,8～10幅為佩戴眼鏡,11～13幅為佩戴圍巾。每幅圖片大小為50×40像素。

在AR人臉數據庫上進行實驗時,選擇特定圖片作為訓練樣本,本文將2周拍攝的圖像進行合并編號,即每人26幅圖像,共進行了3種不同的選擇。首先選擇每人的第5～第7幅圖像作為訓練樣本,剩余為測試圖像;其次選擇每人前7幅圖像作為訓練樣本,剩余為測試圖像;最后選擇前13幅圖像作為訓練樣本,剩余為測試圖像。實驗結果如圖7～圖9所示,橫軸為特征向量的維數,縱軸為運用最近鄰分類器的分類準確率。表1為AR人臉數據庫中進行3種不同實驗時LPP算法與LPP-L2算法所需要耗費的CPU時間,其中選擇降低的維數為100維,算法均在主頻為3.30 GHz和內存為16 GB的計算機上的Matlab R2014a上運行。

圖7 選定3幅圖像作為訓練樣本時的分類準確率

圖8 選定7幅圖像作為訓練樣本時的分類準確率

圖9 選定13幅圖像作為訓練樣本時的分類準確率

圖7～圖9表明,AR人臉數據庫中采用LPP-L2算法的識別率優(yōu)于采用LPP算法的識別率。在訓練樣本數較少的情況下,LPP-L2算法仍然可以取得較高的人臉識別率;相較于LPP算法,LPP-L2算法在訓練樣本數不同的條件下,能夠保持相對穩(wěn)定的識別率,即LPP-L2算法能夠在很大程度上克服不同因素的影響,取得較高較穩(wěn)定的人臉識別率。

表1 不同算法的CPU耗時

表1結果表明,由于LPP-L2算法采用了迭代的計算方法,在本次實驗中迭代次數選擇為200次,相較LPP算法將會消耗更多的CPU時間,但是,LPP-L2算法能夠更好地克服外點造成的不良影響,即用相對較多的時間獲得了更準確的識別率。LPP-L2算法的不足在于計算耗時較多,其算法魯棒性的提高是以犧牲計算效率換來的。

在實際應用中,可以根據應用對魯棒性和計算耗時的要求來選擇算法。如果對魯棒性要求高而對計算耗時要求不高時,可以選擇LPP-L2算法;如果對計算耗時要求高而對魯棒性要求不高時,可以選擇LPP算法。

3 結 論

[1] 張麗梅. 面向降維的圖學習研究及應用 [D]. 南京: 南京航空航天大學, 2012.

[2] YAN Shuicheng, XU Dong, ZHANG Benyu, et al. Graph embedding and extensions: a general framework for dimensionality reduction [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(1): 40-51.

[3] JOLLIFFE I T. Principal component analysis [M]. Berlin, Germany: Springer, 2002: 2-5.

[4] MARTINEZ A M, KAK A C. PCA versus LDA [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(2): 228-233.

[5] NIYOGI P, HE Xiaofei. Locality preserving projections [J]. Advances in Neural Information Processing Systems, 2003: 153-162.

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

[7] 何曉飛. 人臉識別的幾何觀點: 拉普拉斯臉 [J]. 科學觀察, 2010, 5(6): 67-68. HE Xiaofei. Face recognition: Laplasse’s face [J]. Science Focus, 2010, 5(6): 67-68.

[8] PTUCHA R, TSAGKATAKIS G, SAVAKIS A. Manifold learning for simultaneous pose and facial expression recognition [C]∥Proceedings of the IEEE International Conference on Computer Vision. Piscataway, NJ, USA: IEEE, 2011: 3021-3024.

[9] TURK M, PENTLAND A. Eigenfaces for recognition [J]. Journal of Cognitive Neuroscience, 1991, 3(1): 71-86.

[10]RAO A, NOUSHATH S. Subspace methods for face recognition [J]. Computer Science Review, 2010, 4(1): 1-17.

[11]NIE Feiping, WANG Hua, HUANG Heng, et al. Unsupervised and semi-supervised learning via L1-norm graph [C]∥Proceedings of the 2011 IEEE International Conference on Computer Vision. Piscataway, NJ, USA: IEEE, 2011: 2268-2273,

[12]HUANG Heng, XU Dong, NIE Feiping. Semi-supervised dimension reduction using trace ratio criterion

[J]. IEEE Transactions on Neural Network Learning System, 2012, 23(3): 519-526.

[13]SYMEON N, ANASTASIOS T, LOANNIS P. Maximum margin projection subspace learning for visual data analysis [J]. IEEE Transactions on Image Processing, 2014, 23(10): 4413-4425.

(編輯 武紅江)

A Projection Algorithm with Local Preservation Based on L2 Norm

DING Ming1,JIA Weimin1,YAO Minli2

(1. Staff Room 907, The Second Artillery Engineering University, Xi’an 710025, China;2. Staff Room 403, The Second Artillery Engineering University, Xi’an 710025, China)

A projection algorithm with locality preserving projections based on the L2 norm (LPP-L2) is proposed to solve the problem that objective functions of traditional projection algorithms with local preservation (LPP) are based on the squared L2 norm and very sensitive to outliers. The weight matrix of the algorithm is recalculated using an iterative method and the objective function is also simplified, as a result, the optimized projection matrix is obtained. The algorithm converges to a local optimum in each iteration. The optimized projection matrix is used to project the original data into an optimal projection subspace with reduced dimension, while the characters of original data are preserved. Experimental results on synthesized data and a comparison with the LPP algorithm show that the LPP-L2 algorithm effectively reduces the data dimension and makes the algorithm more robust to outliers, it gains higher accurate and steady classification rate in face recognition, and a recognition rate of 80% is obtained.

dimensionality reduction; locality preserving projections; L2 norm

2015-07-08。

丁銘(1991—),女,碩士生;姚敏立(通信作者),男,教授,博士生導師。 基金項目:國家自然科學基金青年科學基金資助項目(61401471)。

時間:2016-01-07

10.7652/xjtuxb201602006

TP391.4

A

0253-987X(2016)02-0033-05

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160107.1232.002.html