基于判別正則化的局部保留投影

高云龍 胡康立 鐘淑鑫 潘金艷張逸松

(1.廈門(mén)大學(xué)航空航天學(xué)院,福建廈門(mén) 361102;2.華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣東廣州 510006;3.中山大學(xué)數(shù)據(jù)科學(xué)與計(jì)算機(jī)學(xué)院,廣東廣州 510006;4.集美大學(xué)信息工程學(xué)院,福建廈門(mén) 363102)

1 引言

在高維空間里,數(shù)據(jù)常常帶有大量的特征,這不僅增加了后續(xù)算法的訓(xùn)練時(shí)間,也對(duì)數(shù)據(jù)的存儲(chǔ)提出了更高的要求.此外高維數(shù)據(jù)常常帶有噪聲和不相關(guān)特征,這嚴(yán)重影響了后續(xù)算法的性能.為了解決這些問(wèn)題,維數(shù)約簡(jiǎn)被提出.維數(shù)約簡(jiǎn)的目的是將高維數(shù)據(jù)投影到低維空間,此外盡可能多地保持原始數(shù)據(jù)的內(nèi)在信息,從而使得高維數(shù)據(jù)能夠表示在低維空間中.維數(shù)約簡(jiǎn)包括特征選擇[1-4]和特征提取[5-6]兩種方式,特征選擇是通過(guò)移除原始數(shù)據(jù)特征的不相關(guān)項(xiàng)或弱相關(guān)項(xiàng),從而達(dá)到維數(shù)約簡(jiǎn)的目的;而特征提取是通過(guò)轉(zhuǎn)化或聯(lián)合原始數(shù)據(jù)的特征,從而達(dá)到維數(shù)約簡(jiǎn)的目的.本文主要討論特征提取.

特征提取包括線性維數(shù)約簡(jiǎn)和基于流形學(xué)習(xí)的非線性維數(shù)約簡(jiǎn).線性維數(shù)約簡(jiǎn)最典型的約簡(jiǎn)方法包括:主成分分析(principal component analysis,PCA)[7]和線性判別分析(linear discriminant analysis,LDA)[8].它們已經(jīng)被廣泛應(yīng)用于模式識(shí)別、數(shù)據(jù)挖掘、計(jì)算機(jī)視覺(jué)等領(lǐng)域.作為一種典型的無(wú)監(jiān)督學(xué)習(xí)方法,PCA的目標(biāo)是尋找一組最優(yōu)投影正交基,使得投影后的數(shù)據(jù)方差最大化;而從重構(gòu)誤差的角度來(lái)看,則是使得投影后的數(shù)據(jù)反映射到原空間后的重構(gòu)誤差最小化.盡管PCA能夠較好地重構(gòu)原始數(shù)據(jù),但是由于PCA沒(méi)有利用判別信息,所以獲得的投影正交基未必是最優(yōu)的[9].因此,利用了標(biāo)簽判別信息的線性維數(shù)約簡(jiǎn)方法LDA被提出來(lái).LDA的目標(biāo)是尋找一組最優(yōu)投影向量來(lái)最大化類(lèi)間散度矩陣和類(lèi)內(nèi)散度矩陣之間的比值,使得同一類(lèi)數(shù)據(jù)盡可能聚集在一起,不同類(lèi)的數(shù)據(jù)盡可能分開(kāi).但是這些方法都屬于線性維數(shù)約簡(jiǎn)方法,無(wú)法提取數(shù)據(jù)的非線性結(jié)構(gòu)特征.為了解決這個(gè)問(wèn)題,最直觀的思路是基于核對(duì)線性模型進(jìn)行非線性擴(kuò)展[10],但是基于核的方法計(jì)算負(fù)擔(dān)大,而且無(wú)法提取數(shù)據(jù)的局部結(jié)構(gòu)特征.因此近年來(lái)眾多基于流形學(xué)習(xí)的非線性維數(shù)約簡(jiǎn)方法得到廣泛研究,如:等距映射(isometric mapping,ISOMAP)[11]、局部線性嵌入(locally linear embedding,LLE)[12]和拉普拉斯特征映射(Laplacian eigenmaps,LE)[13]等.ISOMAP 模 型 通過(guò)計(jì)算樣本點(diǎn)之間的測(cè)地距離,來(lái)保持高維流形數(shù)據(jù)的原有幾何結(jié)構(gòu).而LLE和LE通過(guò)保持原始數(shù)據(jù)中局部幾何關(guān)系,來(lái)保持原始數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu),最終實(shí)現(xiàn)非線性原始數(shù)據(jù)的維數(shù)約簡(jiǎn).

傳統(tǒng)流形學(xué)習(xí)通過(guò)非線性映射發(fā)現(xiàn)嵌入在高維空間中的低維流形結(jié)構(gòu).然而這種非線性映射不僅計(jì)算成本高,而且僅僅定義在訓(xùn)練樣本集上.對(duì)于一個(gè)新的測(cè)試樣本點(diǎn),無(wú)法給出從高維到低維嵌入的映射關(guān)系,即存在著out-of-sample問(wèn)題.因此對(duì)于新的高維樣本點(diǎn),只能重新對(duì)所有數(shù)據(jù)進(jìn)行再次處理,從而大大增加了計(jì)算成本.為了解決這個(gè)問(wèn)題,目前有兩類(lèi)典型的學(xué)習(xí)方法,一類(lèi)是基于相似性保留的線性化流形學(xué)習(xí)方法,典型算法如:鄰域保持嵌入(neighborhoods preserving embedding,NPE)[14]和局部保留投影(locality preserving projections,LPP)[15],此類(lèi)算法通過(guò)線性嵌入來(lái)保留數(shù)據(jù)的流形結(jié)構(gòu)特征;另一類(lèi)是基于回歸的流形結(jié)構(gòu)保留算法,如SEANC[16],RCFE[17]和SEC[18],這類(lèi)算法通過(guò)線性回歸的方式來(lái)近似數(shù)據(jù)的非線性流形結(jié)構(gòu).

在流形學(xué)習(xí)中,首先需要采用圖來(lái)描述數(shù)據(jù)的本質(zhì)結(jié)構(gòu),圖的優(yōu)劣決定著流形學(xué)習(xí)方法能否有效提取數(shù)據(jù)的本質(zhì)結(jié)構(gòu)特征.因此眾多圖學(xué)習(xí)(graph-learning)方法被提出來(lái),典型的學(xué)習(xí)方法如kNN[19],ε-ball[20]等.但是這些圖構(gòu)造方法受局部領(lǐng)域大小選擇的影響極大.為此,不少學(xué)者提出基于正則化的相似性學(xué)習(xí)方法,實(shí)現(xiàn)局部領(lǐng)域大小的自適應(yīng)選擇,典型算法如:Chen等人[21]將高斯核和局部線性描述結(jié)合在一起來(lái)學(xué)習(xí)局部相似性,通過(guò)對(duì)相似性的一階正則化,限制局部領(lǐng)域的大小.Li等人[22]在局部線性描述的基礎(chǔ)上利用L1范數(shù)對(duì)相似性的稀疏性進(jìn)行約束;在文獻(xiàn)[23]中,Nie等人則在最近鄰的基礎(chǔ)上,通過(guò)添加L2范數(shù)的正則項(xiàng),來(lái)學(xué)習(xí)局部領(lǐng)域和局部相似性.但是這些方法是在原空間,而不是在嵌入空間中學(xué)習(xí)樣本點(diǎn)之間的相似性,因此受噪聲的影響較大,所學(xué)習(xí)到的圖(graph)無(wú)法很好地描述數(shù)據(jù)的本質(zhì)結(jié)構(gòu)特征.

為了提高圖對(duì)數(shù)據(jù)本質(zhì)結(jié)構(gòu)特征的描述能力,更好地解決維數(shù)災(zāi)難問(wèn)題,近年來(lái)眾多自適應(yīng)圖學(xué)習(xí)的方法被提出來(lái),如:Wang等人[24]提出了DCLA,Nie等人[23]提 出PCAN,Wang等 人[25]提 出DUDR,Wang等人[16]提出了SEANC.這些方法在嵌入的過(guò)程中自適應(yīng)構(gòu)建圖,避免了對(duì)超參數(shù)的選擇,提高對(duì)噪聲的魯棒性,有效避免了維數(shù)災(zāi)難對(duì)數(shù)據(jù)本質(zhì)結(jié)構(gòu)特征的影響.但是上面的這些方法著眼于建立能夠?qū)?shù)據(jù)本質(zhì)結(jié)構(gòu)特征具有良好描述的圖形構(gòu)建上,在嵌入過(guò)程中缺少對(duì)圖描述的進(jìn)一步分析和挖掘,當(dāng)圖對(duì)數(shù)據(jù)本質(zhì)結(jié)構(gòu)特征描述不恰當(dāng)時(shí),在嵌入過(guò)程中不易實(shí)現(xiàn)流形數(shù)據(jù)本質(zhì)結(jié)構(gòu)的有效提取.

如何在給定流形數(shù)據(jù)圖描述的條件下,提高對(duì)流形數(shù)據(jù)本質(zhì)結(jié)構(gòu)特征的提取能力,近年來(lái),一些新穎的線性化的流形學(xué)習(xí)方法被提了出來(lái),如:柯西圖嵌入(CEG)[26]、基于L2,1范數(shù)的LPP[27]、局部稀疏保留投影(LSPP)[28]、判別稀疏保留圖嵌入(DSPGE)[29]等.其中CGE利用類(lèi)柯西分布強(qiáng)調(diào)對(duì)流形的局部性和拓?fù)潢P(guān)系保留能力.但是CGE為了保留數(shù)據(jù)的拓?fù)潢P(guān)系,過(guò)度強(qiáng)調(diào)局部結(jié)構(gòu)特征,這容易造成流形結(jié)構(gòu),特別是分布稀疏的區(qū)域,在嵌入空間中斷裂成多個(gè)局部領(lǐng)域,即流形結(jié)構(gòu)的整體性特征沒(méi)有得到有效保留.這種嵌入模型對(duì)于多流形數(shù)據(jù)容易造成不同流形在嵌入空間中的交疊,不同流形數(shù)據(jù)之間的可分性不明顯.基于L2,p范數(shù)的LPP,可以等價(jià)看作為L(zhǎng)2范數(shù)意義下,對(duì)相似性重新加權(quán)的過(guò)程.這類(lèi)型方法強(qiáng)調(diào)相似性,對(duì)局部稠密分布的流形結(jié)構(gòu),容易過(guò)多引入非局部信息,從而破壞流形數(shù)據(jù)的局部拓?fù)潢P(guān)系.LSPP,DSPGE利用了稀疏描述和樣本的自然判別信息這兩個(gè)特征.這兩種方法在嵌入過(guò)程中,除了考慮樣本點(diǎn)之間的局部性,而且考慮了樣本之間的稀疏重建關(guān)系,有效提高了對(duì)數(shù)據(jù)局部本質(zhì)結(jié)構(gòu)特征的提取能力.但是稀疏表示只描述了局部相似性,對(duì)局部判別信息考慮不足.

本文研究在給定流形數(shù)據(jù)圖描述的條件下,如何提高對(duì)流形數(shù)據(jù)本質(zhì)結(jié)構(gòu)特征的提取能力.在嵌入過(guò)程中,通過(guò)對(duì)圖描述進(jìn)一步分析和挖掘,提出了判別正則化LPP,本文的貢獻(xiàn)在于:

1) 在給定流形數(shù)據(jù)圖描述的條件下,通過(guò)樣本點(diǎn)之間的相似度閾值確定局部領(lǐng)域.因?yàn)槔绽咕仃嚨臍w一化約束,相似度閾值具有尺度無(wú)關(guān)性,這使得局部領(lǐng)域的大小,能夠根據(jù)分布特征自適應(yīng)調(diào)整;

2) 自適應(yīng)確定局部領(lǐng)域內(nèi)、外樣本點(diǎn)之間的處理方式.對(duì)于分布稀疏的領(lǐng)域內(nèi),通過(guò)采用L2范數(shù)與L2,1范數(shù)的組合方式確定數(shù)據(jù)在嵌入空間中的距離,利用L2,1范數(shù)對(duì)大距離樣本點(diǎn)較不敏感,L2范數(shù)對(duì)近距離樣本點(diǎn)較不敏感的特性,避免了大距離樣本點(diǎn)對(duì)局部拓?fù)潢P(guān)系的提取所帶來(lái)的影響,同時(shí)也防止了流形數(shù)據(jù)在嵌入過(guò)程中,斷裂成多個(gè)局部領(lǐng)域.特別是對(duì)于具有多個(gè)不同流形的嵌入而言,防止了每個(gè)流形數(shù)據(jù)集斷裂成多個(gè)不同的局部領(lǐng)域,同時(shí)不同流形交疊嚴(yán)重的情況發(fā)生.

3) 對(duì)于分布稠密的區(qū)域,此時(shí)提取該局部判別信息,以防止過(guò)多非局部信息的引入,造成流形結(jié)構(gòu)在嵌入過(guò)程中的扭曲和對(duì)局部拓?fù)潢P(guān)系的破壞,形成流形結(jié)構(gòu)的光滑嵌入.對(duì)于多流形數(shù)據(jù),有效突出不同流形結(jié)構(gòu)在線性嵌入空間中的可分性.

4) 在人造合成流形數(shù)據(jù)以及實(shí)際標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了大量實(shí)驗(yàn),結(jié)果表明了判別正則化的局部保留投影(discriminant and regularization locality preserving projections,DRLPP)算法的性能對(duì)比其他算法有著顯著的優(yōu)勢(shì).

本文分成5章,在剩下章節(jié)中:第2章介紹相關(guān)算法;第3章介紹基于判別正則化的局部保留投影(DRLPP)模型,以及模型的相關(guān)計(jì)算步驟;第4章介紹DRLPP算法與相關(guān)算法在人造合成數(shù)據(jù)以及標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行的大量實(shí)驗(yàn),以及對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行的分析.第5章對(duì)論文進(jìn)行總結(jié).

2 相關(guān)算法概述

2.1 符號(hào)定義

本文中:X代表訓(xùn)練集,Y代表投影后的樣本,n代表樣本個(gè)數(shù),d代表訓(xùn)練樣本的維數(shù).本文中的符號(hào)以及定義總結(jié)在表1中.

2.2 局部保留投影(LPP)

LPP是一種線性維數(shù)約簡(jiǎn)的方法,是非線性維數(shù)約簡(jiǎn)方法LE的線性近似.其思想核心是使得高維空間中距離較近的樣本點(diǎn)嵌入到低維空間中依然保持這種較近的距離關(guān)系,通過(guò)這樣的方式來(lái)保留數(shù)據(jù)的局部拓?fù)浣Y(jié)構(gòu).

因此LPP目標(biāo)是尋找一個(gè)投影矩陣W ∈Rd×m將訓(xùn)練集X映射到低維空間,Y是得到的投影后樣本點(diǎn).其中:n為樣本的數(shù)量,d為樣本的維數(shù),m是樣本嵌入到低維空間后的維數(shù).投影矩陣W可以通過(guò)對(duì)目標(biāo)函數(shù)的極小化獲得.

LPP的目標(biāo)函數(shù)可以寫(xiě)成如下形式:

其中S矩陣的定義如下:

其中:t是一個(gè)熱核參數(shù)且t≥0,‖·‖2是L2范數(shù)符號(hào),N(xi)表示距離xi最近k個(gè)樣本集合.矩陣S是一個(gè)權(quán)值矩陣,用于描述數(shù)據(jù)的局部結(jié)構(gòu)特征,也被稱為相似度矩陣.通過(guò)對(duì)目標(biāo)函數(shù)的極小化,該算法可將高維空間中距離較近的樣本點(diǎn)嵌入到低維空間中,并能夠保持這種較近的距離關(guān)系.

表1 本文用到的符號(hào)及其定義Table 1 Notations used in this paper

假定Y=WTX,通過(guò)簡(jiǎn)單的線性代數(shù)知識(shí)進(jìn)行化簡(jiǎn),可以將目標(biāo)函數(shù)改寫(xiě)為

因此目標(biāo)函數(shù)可以寫(xiě)為以下形式:

利用拉格朗日乘子法,可以將求解目標(biāo)函數(shù)變?yōu)榍蠼庖韵碌膹V義特征值問(wèn)題

從中可知矩陣XLXT和XDXT是一個(gè)對(duì)稱半正定矩陣.而投影矩陣W是由前m小的特征值對(duì)應(yīng)的特征向量[w1w2··· wm]所組成的.

2.3 相似性和多樣性

相似性圖(相似度矩陣)是一個(gè)描述空間中樣本點(diǎn)之間的鄰域局部相似性結(jié)構(gòu)的親和矩陣,而多樣性圖(多樣性矩陣)則是一個(gè)體現(xiàn)了空間中樣本點(diǎn)多樣性信息的親和矩陣.這兩個(gè)圖的結(jié)合可以更好描述數(shù)據(jù)的局部本質(zhì)結(jié)構(gòu),為特征提取提供一個(gè)更加精確的準(zhǔn)則[30].相似度矩陣的定義有如式(2),而Gao等人[30]為了更好保持?jǐn)?shù)據(jù)的流形結(jié)構(gòu),利用了數(shù)據(jù)的類(lèi)別信息,建立了如下的有監(jiān)督學(xué)習(xí)相似度矩陣:

其中:τi表示第i類(lèi)數(shù)據(jù)簇,N(xi)表示距離xi最近的k個(gè)樣本集合.該相似度矩陣通過(guò)建立了最近k個(gè)相同類(lèi)和最近k個(gè)不同類(lèi)的相似性關(guān)系,更好地描述了流形數(shù)據(jù)的局部結(jié)構(gòu)特征.

多樣性矩陣定義如下:

從該多樣性權(quán)值矩陣可知,當(dāng)距離較遠(yuǎn)的高維樣本點(diǎn)xi和xj嵌入到低維空間后樣本距離相距較近時(shí),Aij將給予較重的懲罰.通過(guò)這種方式,嵌入的過(guò)程考慮了樣本之間分布的多樣性,更好地保留了數(shù)據(jù)的本質(zhì)結(jié)構(gòu)特征.

3 基于判別正則化的局部保留投影-DRLPP

盡管在文獻(xiàn)[30]中Gao等人提出了采用兩個(gè)不同的圖對(duì)數(shù)據(jù)本質(zhì)結(jié)構(gòu)特征進(jìn)行描述.特別是引入了多樣性圖實(shí)現(xiàn)對(duì)局部本質(zhì)結(jié)構(gòu)多樣性信息描述,但多樣性圖其實(shí)質(zhì)是突出空間中相互距離較遠(yuǎn)的樣本點(diǎn)的可分性,無(wú)法突出不同流形數(shù)據(jù)之間邊界的可分性,因此該方法對(duì)于離群點(diǎn)比較敏感,模型魯棒性差.為了更好解決這個(gè)問(wèn)題,本文提出了基于判別正則化的局部保留投影(DRLPP).該方法首先通過(guò)局部判別分析提取數(shù)據(jù)間的判別信息,在局部判別分析中利用L2,1范數(shù)來(lái)度量樣本在嵌入空間的距離,降低離群點(diǎn)對(duì)局部判別信息的影響.并將局部判別分析作為正則項(xiàng),與LPP結(jié)合,最終建立判別正則化的局部保留投影-DRLPP.

3.1 基于相似度閾值的判別分析

假定空間中有一流形數(shù)據(jù),在局部鄰域內(nèi),對(duì)于相互距離較近的樣本點(diǎn)屬于同一類(lèi)的可能性較大,反之屬于不同類(lèi)的可能性相對(duì)較大.為了劃分樣本是否屬于同一類(lèi),定義δ為樣本點(diǎn)的相似度閾值.如圖1所示,在以深灰圓點(diǎn)為中心,δ為半徑的圓內(nèi)的3個(gè)黑點(diǎn)明顯與深灰點(diǎn)屬于同一類(lèi),在嵌入到低維空間中依然保留這種近鄰關(guān)系;而對(duì)于淺灰三角形來(lái)說(shuō),其與深灰點(diǎn)距離大于δ,和深灰點(diǎn)屬于不同類(lèi)別,則在嵌入過(guò)程中需要最大化淺灰三角形與圓內(nèi)數(shù)據(jù)的間隔,以突出兩類(lèi)數(shù)據(jù)之間的判別信息.

圖1 局部鄰域相似性和多樣性的描述圖Fig.1 Description of local similarity and diversity structure

按照以上的思路,δ為局部領(lǐng)域半徑的大小.顯然該局部領(lǐng)域的選擇不具有尺度不變性,因此基于δ的局部領(lǐng)域選擇不具有自適應(yīng)性.為了避免這個(gè)問(wèn)題,本文使用相似度Sij約束局部領(lǐng)域,對(duì)于Sij≥δ的情況,認(rèn)為xi和xj屬于同一類(lèi),應(yīng)該保留其相似性結(jié)構(gòu);而對(duì)于Sij <δ的情況,認(rèn)為xi和xj屬于不同類(lèi),應(yīng)該突出其多樣性判別信息.因此有

基于文獻(xiàn)[1]和文獻(xiàn)[31],本文將局部判別分析模型建模為

但是這里使用了L2范數(shù)的平方作為樣本之間距離的度量準(zhǔn)則,增加了相互距離遠(yuǎn)的樣本對(duì)目標(biāo)函數(shù)的影響,這導(dǎo)致了目標(biāo)函數(shù)對(duì)于噪聲和異常樣本點(diǎn),或者是非局部信息極其敏感.為了避免非局部信息的影響,可以考慮選擇一種具有較好魯棒性的距離度量方式.有相關(guān)研究結(jié)果表明[32],使用L2,1范數(shù)度量樣本點(diǎn)之間的距離,可以有效抑制這種影響,提高對(duì)局部拓?fù)浣Y(jié)構(gòu)的保留能力,因此將上述式(10)改寫(xiě)為以下形式:

當(dāng)δ設(shè)置不當(dāng)或者局部分布比較均勻的時(shí)候,很容易出現(xiàn)?Sij <δ,這時(shí)局部判別分析模型就會(huì)變?yōu)?顯然,該模型無(wú)法在嵌入空間中提取并保留數(shù)據(jù)的局部拓?fù)浣Y(jié)構(gòu).為了降低δ參數(shù)設(shè)置的影響,提高δ對(duì)任意數(shù)據(jù)分布特征的適應(yīng)性,本文將局部判別分析與LPP結(jié)合起來(lái),把局部判別分析作為L(zhǎng)PP的正則化項(xiàng),建立目標(biāo)函數(shù)如下:

3.2 DRLPP

增加約束條件并將式(12)重寫(xiě)為

式(13)涉及L2,1范數(shù),無(wú)法直接求得閉合解.根據(jù)文獻(xiàn)[33-34],本文使用迭代的方式去求解目標(biāo)函數(shù).首先將該式改寫(xiě)為如下形式:

利用拉格朗日函數(shù)對(duì)式(17)求解:

對(duì)W,α進(jìn)行求導(dǎo),得出式(19),可以通過(guò)求解式(19)的廣義特征問(wèn)題來(lái)得到其特征值以及特征向量:

根據(jù)LPP的知識(shí),投影矩陣W是由前m小的特征值對(duì)應(yīng)的特征向量[w1w2··· wm]所組成的.

當(dāng)問(wèn)題轉(zhuǎn)化為式(19)形式后,根據(jù)文獻(xiàn)[33-34]可知,可通過(guò)迭代算法來(lái)求解該目標(biāo)函數(shù),并保證迭代過(guò)程中目標(biāo)函數(shù)值的收斂性,算法偽代碼程序可見(jiàn)算法1.

算法1DRLPP算法偽代碼.

輸入:訓(xùn)練集X ∈[x1x2··· xn]∈Rd×n,參數(shù)λ和δ.

初始化:由式(2)計(jì)算得到的相似度矩陣S以及拉普拉斯矩陣L=D-S,由式(14)計(jì)算得到的矩陣B,以及隨機(jī)生成投影矩陣W ∈Rd×m.

while not converged do

根據(jù)式(16)計(jì)算S′以及L′=D′-S′.

根據(jù)式(17)計(jì)算Lλ.

根據(jù)式(19)計(jì)算Wt.

end while

輸出:投影矩陣W ∈[w1w2··· wn]∈Rd×m.

4 實(shí)驗(yàn)分析

在本章中將本算法與PCA[7],LPP[15],LFDA[35],ISOP[36],NPE[14],OLPP[37],ULGE[38]和LSPP[28]進(jìn)行對(duì)比驗(yàn)證,數(shù)據(jù)采用人造合成流形數(shù)據(jù)和實(shí)際標(biāo)準(zhǔn)數(shù)據(jù)集,標(biāo)準(zhǔn)數(shù)據(jù)集部分代表圖像如圖2所示.在人造合成流形數(shù)據(jù)實(shí)驗(yàn),與PCA,LPP和LFDA進(jìn)行對(duì)比驗(yàn)證.在實(shí)際標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)與ISOP,NPE,LPP,ULGE,OLPP和LSPP進(jìn)行對(duì)比驗(yàn)證,并且在實(shí)驗(yàn)過(guò)程中,首先用PCA對(duì)數(shù)據(jù)集進(jìn)行處理,去除噪聲和冗余特征.另外,本文確保LPP,OLPP,ULGE與DRLPP算法的相似度矩陣S是一致的,并對(duì)S矩陣進(jìn)行歸一化處理.

圖2 標(biāo)準(zhǔn)數(shù)據(jù)集的部分圖像Fig.2 Some images of benchmark database

其中,DRLPP算法的參數(shù)δ選取了S矩陣的均值,而參數(shù)λ的選擇則是參考文獻(xiàn)[24]根據(jù)模型的結(jié)果在[0.01,10]的范圍內(nèi)調(diào)整,ULGE算法的參數(shù)根據(jù)論文獻(xiàn)[38]進(jìn)行設(shè)置.在分類(lèi)驗(yàn)證效果階段,使用歐式距離來(lái)度量樣本之間的相似性,并且使用最鄰近分類(lèi)器(1-NN)進(jìn)行分類(lèi)計(jì)算其準(zhǔn)確率.此外,本文還對(duì)算法進(jìn)行收斂性實(shí)驗(yàn)證明.

4.1 人造合成數(shù)據(jù)集

該數(shù)據(jù)集是一個(gè)隨機(jī)生成的二維高斯矩陣,該矩陣包含兩類(lèi)高斯分布的數(shù)據(jù)簇,高斯數(shù)據(jù)的協(xié)方差矩陣為[0.01,0;0,4],均值向量分別為[±3,0],[±1,0]和[±0.5,0].本文分別使用了PCA,LPP,LFDA以及DRLPP對(duì)其進(jìn)行降維,目的是尋找一組投影向量來(lái)使得降維后數(shù)據(jù)可分性強(qiáng).4種算法的比較結(jié)果如圖3所示.觀察圖3,可以知道:當(dāng)兩數(shù)據(jù)簇相距較遠(yuǎn)時(shí),4種方法都可以輕易找到最佳的投影方向;然而,當(dāng)兩數(shù)據(jù)簇相距較近的時(shí)候,PCA由于只考慮全局本質(zhì)結(jié)構(gòu)忽略了局部拓?fù)浣Y(jié)構(gòu),造成效果不佳;而當(dāng)兩數(shù)據(jù)簇相距很近的時(shí)候,LPP因?yàn)橹粡?qiáng)調(diào)數(shù)據(jù)之間的相似性,而忽略了不同流形之間的判別信息,破壞了數(shù)據(jù)的局部本質(zhì)結(jié)構(gòu)特征,導(dǎo)致無(wú)法找到最優(yōu)的投影向量.DRLPP因其能保留局部鄰域內(nèi)樣本的相似性,又考慮了局部判別信息,所以該算法在3種情況下都能找到一組較好的投影向量.特別地,在兩數(shù)據(jù)簇相距很近的情況下,能夠提取某個(gè)數(shù)據(jù)簇區(qū)域的局部判別信息,同時(shí)防止另外一個(gè)數(shù)據(jù)簇的非局部信息的引入,避免了流形結(jié)構(gòu)在嵌入過(guò)程中的扭曲和對(duì)局部拓?fù)潢P(guān)系的破壞,有效突出不同流形結(jié)構(gòu)在線性嵌入空間中的可分性.此外,和有監(jiān)督LFDA算法相比,DRLPP算法也不遜色.

圖3 人造合成數(shù)據(jù)實(shí)驗(yàn)結(jié)果Fig.3 Experimental result on synthetic data

4.2 標(biāo)準(zhǔn)數(shù)據(jù)集

4.2.1 Coil20標(biāo)準(zhǔn)數(shù)據(jù)集

Coil20數(shù)據(jù)集是來(lái)自于哥倫比亞圖像數(shù)據(jù)庫(kù)(columbia object image library)的數(shù)據(jù)集,里面包含了20類(lèi)樣本在旋轉(zhuǎn)一周范圍內(nèi)不同的角度下拍攝的照片,每類(lèi)樣本包含72張圖片,共1440張圖片.在實(shí)驗(yàn)中,將所有原圖片處理為32×32像素大小的圖片,并分別將其轉(zhuǎn)換為向量xi ∈R1×1024,組成一個(gè)X ∈R1440×1024的數(shù)據(jù)集.對(duì)于這些數(shù)據(jù)集,作者分別隨機(jī)抽取10%,20%,30%,40%的數(shù)據(jù)來(lái)用作訓(xùn)練集,其余數(shù)據(jù)作為測(cè)試集.為了避免偶然性的影響,每種劃分方式作者都會(huì)重復(fù)進(jìn)行10次實(shí)驗(yàn).圖4展示了4種劃分情況下Coil20數(shù)據(jù)集平均識(shí)別準(zhǔn)確率與投影維度變化曲線圖,表2展示了各個(gè)算法的最優(yōu)平均識(shí)別率的均值以及最優(yōu)平均識(shí)別率均值的標(biāo)準(zhǔn)差.

圖4 Coil20數(shù)據(jù)集平均識(shí)別準(zhǔn)確率與投影維度變化曲線圖Fig.4 Average classification accuracy versus the projection vectors number on the Coil20 database

表2 各算法在Coil20數(shù)據(jù)集的最優(yōu)平均識(shí)別率對(duì)比(均值±標(biāo)準(zhǔn)差)Table 2 The top average classification accuracy and corresponding standard deviation on the Coil20 database

通過(guò)分析曲線圖和表格數(shù)據(jù)可知,所有方法的識(shí)別準(zhǔn)確率均隨著投影維度的增加而提高,但DRLPP算法相比其余算法最早達(dá)到識(shí)別準(zhǔn)確率的最優(yōu)值,同時(shí)DRLPP算法在不同投影維度的情況下,識(shí)別準(zhǔn)確率都顯著高于其他算法.

4.2.2 Yale標(biāo)準(zhǔn)數(shù)據(jù)集

Yale數(shù)據(jù)集是來(lái)自于耶魯大學(xué)計(jì)算機(jī)視覺(jué)中心(UCSD computer vision)的數(shù)據(jù)集,該數(shù)據(jù)庫(kù)包含15類(lèi)樣本共165張圖片,每一類(lèi)都有11個(gè)圖像,每一類(lèi)的圖片均包括光照、人臉表情和配飾的變化.對(duì)于該數(shù)據(jù)集,先將所有原圖片處理為32×32 像素大小的圖片,每張圖片裁剪為向量組成實(shí)驗(yàn)數(shù)據(jù)集.作者會(huì)分別從每一類(lèi)中隨機(jī)抽取i(i=3,4,5,6)張圖片來(lái)用作訓(xùn)練集,剩余的圖片作為測(cè)試集.每種劃分方式都會(huì)重復(fù)進(jìn)行10次實(shí)驗(yàn).圖5展示了4種劃分情況下Yale數(shù)據(jù)集平均識(shí)別準(zhǔn)確率與投影維度變化曲線圖,表3展示了各個(gè)算法最優(yōu)平均識(shí)別率的均值以及最優(yōu)平均識(shí)別率均值的標(biāo)準(zhǔn)差.

通過(guò)曲線圖以及表格可見(jiàn),DRLPP投影維度較高情況下最優(yōu)平均識(shí)別率能夠較明顯優(yōu)于其余算法,而且隨著訓(xùn)練樣本的增加,訓(xùn)練集包含更多的信息,所有算法的識(shí)別率都有較明顯的提高,但DRLPP算法的識(shí)別率提高較快,使得DRLPP算法在投影維度不斷增加的情況下,與其他算法相比,平均識(shí)別率的優(yōu)勢(shì)也越大.但是DRLPP在投影維度較低的情況下,性能稍微弱于LSPP,造成這種結(jié)果的的原因?yàn)?與Coil20,ORL兩個(gè)數(shù)據(jù)集相比,Yale數(shù)據(jù)集中某些圖像光線變化差異較大,這造成人臉圖像在高維空間中的流形結(jié)構(gòu)特征不明顯.而LSPP結(jié)合了稀疏表示來(lái)學(xué)習(xí)數(shù)據(jù)的本質(zhì)幾何結(jié)構(gòu),稀疏表示對(duì)噪聲的魯棒性使得LSPP在投影維度較低的情況下體現(xiàn)出較好的性能.但是隨著投影維度的增加,從原始數(shù)據(jù)中提取的有用信息增加,本文所提算法比LSPP 體現(xiàn)出更優(yōu)異的性能.該實(shí)驗(yàn)結(jié)果說(shuō)明DRLPP能夠更好地提取數(shù)據(jù)的判別信息,表征數(shù)據(jù)的本質(zhì)結(jié)構(gòu).

圖5 Yale數(shù)據(jù)集平均識(shí)別準(zhǔn)確率與投影維度變化曲線圖Fig.5 Average classification accuracy versus the projection vectors number on the Yale database

表3 各算法在Yale數(shù)據(jù)集的最優(yōu)平均識(shí)別率對(duì)比(均值±標(biāo)準(zhǔn)差)Table 3 The top average classification accuracy and corresponding standard deviation on the Yale database

4.2.3 ORL標(biāo)準(zhǔn)數(shù)據(jù)集

ORL人臉數(shù)據(jù)集是來(lái)自于劍橋大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室(Cambridge university computer laboratory)的數(shù)據(jù)集.該數(shù)據(jù)集的樣本包含40個(gè)人,每人10張不同的圖片,共400張灰度圖片,圖片分辨率為112×92.每個(gè)人的圖片都是在不同時(shí)間、不同光線情況下拍攝的.照片中每個(gè)人都包含旋轉(zhuǎn)及傾斜的人臉照片,并且人的面部表情有睜眼、閉眼、微笑以及不微笑,而面部配飾則有戴眼鏡和不戴眼鏡.在實(shí)驗(yàn)中,類(lèi)似Coil20數(shù)據(jù)集的預(yù)處理后,分別從每一類(lèi)中隨機(jī)抽取i(i=3,4,5,6)張圖片來(lái)用作訓(xùn)練集,剩余的圖片作為測(cè)試集.每種劃分方式作者都會(huì)重復(fù)進(jìn)行10 次實(shí)驗(yàn).圖6展示了4種劃分情況下ORL數(shù)據(jù)集平均識(shí)別準(zhǔn)確率與投影維度變化曲線圖,表4展示了各個(gè)算法最優(yōu)平均識(shí)別率的均值以及最優(yōu)平均識(shí)別率均值的標(biāo)準(zhǔn)差.

圖6 ORL數(shù)據(jù)集平均識(shí)別準(zhǔn)確率與投影維度變化曲線圖Fig.6 Average classification accuracy versus the projection vectors number on the ORL database

表4 各算法在ORL數(shù)據(jù)集的最優(yōu)平均識(shí)別率對(duì)比(均值±標(biāo)準(zhǔn)差)Table 4 The top average classification accuracy and corresponding standard deviation on the ORL database

通過(guò)曲線圖6以及表5可見(jiàn),DRLPP算法的平均識(shí)別率在各個(gè)維數(shù)變化下均高于其他算法,在投影維數(shù)為1至40維時(shí),DRLPP算法的平均識(shí)別率提高顯著,并最早達(dá)到最優(yōu)值.

同時(shí),當(dāng)維數(shù)為20至40時(shí),DRLPP算法的識(shí)別率優(yōu)勢(shì)明顯,其次,隨著投影維度的不斷的增加,LPP,ULGE和LSPP算法出現(xiàn)識(shí)別率明顯下滑以及NPE,ISOP和OLPP算法識(shí)別率不再增加的現(xiàn)象,而DRLPP 算法在此情況下,平均識(shí)別率仍能很好地保持在最優(yōu)值,甚至仍有一定提升,說(shuō)明DRLPP算法不僅能夠有效提取數(shù)據(jù)的判別信息和數(shù)據(jù)的本質(zhì)結(jié)構(gòu),同時(shí)也具有一定的魯棒性.

從Coil20,Yale 和ORL 數(shù)據(jù)集的實(shí)驗(yàn)可以看出,Coil20數(shù)據(jù)集在少訓(xùn)練集,較低的維度的情況下,就可以達(dá)到相對(duì)較高的識(shí)別精度.而針對(duì)Yale和ORL人臉數(shù)據(jù)集的識(shí)別精度,隨著投影維度的增加,識(shí)別精度增加較緩慢,在較高投影維度的情況下,識(shí)別精度才達(dá)到最優(yōu)值.同時(shí),隨著訓(xùn)練數(shù)據(jù)集的增加,針對(duì)人臉數(shù)據(jù)集的識(shí)別精度增加明顯.說(shuō)明Yale和ORL人臉數(shù)據(jù)集的數(shù)據(jù)復(fù)雜程度,要高于Coil20數(shù)據(jù)集.

4.2.4 收斂性實(shí)驗(yàn)

圖7展示了本文算法在Coil20,Yale和ORL這3個(gè)數(shù)據(jù)集上迭代次數(shù)和目標(biāo)函數(shù)值的變化曲線.

圖7 DRLPP在3個(gè)數(shù)據(jù)庫(kù)的收斂曲線Fig.7 Convergence curves of DRLPP on three databases

從圖7中可見(jiàn),目標(biāo)函數(shù)值隨迭代過(guò)程不斷減小,最終達(dá)到收斂,同時(shí)目標(biāo)函數(shù)值在迭代十次內(nèi),能夠達(dá)到收斂狀態(tài).通過(guò)收斂性實(shí)驗(yàn),從實(shí)驗(yàn)的角度反映了算法的收斂性.

5 結(jié)論

本文提出了一種新的維數(shù)約簡(jiǎn)算法-基于判別正則化的局部保留投影(DRLPP).DRLPP建立一個(gè)局部判別分析來(lái)學(xué)習(xí)數(shù)據(jù)的局部拓?fù)浣Y(jié)構(gòu)以及樣本空間分布的多樣性,并將局部判別分析作為L(zhǎng)PP的正則項(xiàng),克服了基于相似性學(xué)習(xí)算法只強(qiáng)調(diào)相似性學(xué)習(xí)而忽略多樣性學(xué)習(xí)的缺點(diǎn).因此,DRLPP不僅能很好保持?jǐn)?shù)據(jù)的局部拓?fù)浣Y(jié)構(gòu),也能很好保持局部樣本分布的多樣性,更好地描述了數(shù)據(jù)的局部本質(zhì)結(jié)構(gòu)特征.從人造合成流形數(shù)據(jù)、Coil20數(shù)據(jù)集、Yale 數(shù)據(jù)集以及ORL 數(shù)據(jù)集的實(shí)驗(yàn)中也體現(xiàn)了DRLPP 算法具有以下優(yōu)勢(shì):1)DRLPP算法通過(guò)樣本點(diǎn)之間的相似度閾值來(lái)確定局部領(lǐng)域,使得局部領(lǐng)域的大小,能夠根據(jù)分布特征自適應(yīng)調(diào)整,同時(shí)通過(guò)L2范數(shù)和L2,1范數(shù)之間的相互關(guān)系,從而刻畫(huà)局部領(lǐng)域內(nèi)的分布特征差異,使得DRLPP算法更有效地提取數(shù)據(jù)的判別信息;2)DRLPP算法由于采用L2范數(shù)和L2,1范數(shù)的組合學(xué)習(xí)的方式,使得算法具有一定的魯棒性;3)從人造數(shù)據(jù)集實(shí)驗(yàn)可以看出,DRLPP算法在考慮數(shù)據(jù)流形結(jié)構(gòu)的條件下,突出了不同流形之間的判別信息.