丁銘,賈維敏,姚敏立

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

?

基于L2范數(shù)的局部保持投影算法

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

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

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

降維;局部保持投影;L2范數(shù)

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

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

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

1 基于L2范數(shù)局部保持投影算法

1.1 算法原理

LPP算法能夠克服PCA算法與LDA算法的不足,并且很好地保持了高維數(shù)據(jù)固有的幾何結(jié)構(gòu)和局部結(jié)構(gòu)。LPP算法中的目標(biāo)函數(shù)為

‖yi-yj‖2Sij

(1)

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

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

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

(2)

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

根據(jù)文獻(xiàn)[13]中的改進(jìn)方式,改進(jìn)LPP算法的目標(biāo)函數(shù),即LPP-L2算法的目標(biāo)函數(shù)為

‖WTxi-WTxj‖2

(3)

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

運(yùn)用拉格朗日函數(shù)解式(3)得到

‖WTxi-WTxj‖2-

tr(Λ(WTXDXTW-Im))

(4)

(5)

(6)

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

tr(Λ(WTXDXTW-Im))=

(7)

1.2 收斂性證明

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

(1)對于標(biāo)量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。顯然,當(dāng)x>0時(shí),f″(x)<0且f″(x)當(dāng)且僅當(dāng)x=1時(shí),存在f′(x)=0。由于x=1時(shí),f(x)=0,即當(dāng)x>0時(shí),f(x)單調(diào)遞減且f(x)≤0,則f(x2)≤0,即2|x|-x2-1≤0。

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

(9)

證明 由步驟1可以得到

根據(jù)上述不等式可以得到收斂性定理,即目標(biāo)函數(shù)式(3)為單調(diào)遞減函數(shù),經(jīng)過每一次迭代均會收斂到一個(gè)局部最小值。

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

因此可以得到

(10)

根據(jù)步驟2可以得到

(11)

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

(12)

2 實(shí)驗(yàn)與結(jié)果

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

2.1 S curve曲線合成數(shù)據(jù)實(shí)驗(yàn)

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

圖1 加入100個(gè)外點(diǎn)時(shí)的“S curve”曲線

圖2 LPP算法的降維結(jié)果

圖3 LPP-L2算法的降維結(jié)果

圖4 加入200個(gè)外點(diǎn)時(shí)的“S curve”曲線

圖5 LPP算法的降維結(jié)果

圖6 LPP-L2算法的降維結(jié)果

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

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

2.2 AR人臉數(shù)據(jù)庫實(shí)驗(yàn)

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

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

圖7 選定3幅圖像作為訓(xùn)練樣本時(shí)的分類準(zhǔn)確率

圖8 選定7幅圖像作為訓(xùn)練樣本時(shí)的分類準(zhǔn)確率

圖9 選定13幅圖像作為訓(xùn)練樣本時(shí)的分類準(zhǔn)確率

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

表1 不同算法的CPU耗時(shí)

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

在實(shí)際應(yīng)用中,可以根據(jù)應(yīng)用對魯棒性和計(jì)算耗時(shí)的要求來選擇算法。如果對魯棒性要求高而對計(jì)算耗時(shí)要求不高時(shí),可以選擇LPP-L2算法;如果對計(jì)算耗時(shí)要求高而對魯棒性要求不高時(shí),可以選擇LPP算法。

3 結(jié) 論

[1] 張麗梅. 面向降維的圖學(xué)習(xí)研究及應(yīng)用 [D]. 南京: 南京航空航天大學(xué), 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] 何曉飛. 人臉識別的幾何觀點(diǎn): 拉普拉斯臉 [J]. 科學(xué)觀察, 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—),女,碩士生;姚敏立(通信作者),男,教授,博士生導(dǎo)師。 基金項(xiàng)目:國家自然科學(xué)基金青年科學(xué)基金資助項(xiàng)目(61401471)。

時(shí)間:2016-01-07

10.7652/xjtuxb201602006

TP391.4

A

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

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160107.1232.002.html