一種優(yōu)化的近鄰保持嵌入降維算法研究

李燕燕,閆德勤

(1.河北建筑工程學院,河北 張家口 075000;2.遼寧師范大學,遼寧 大連 116081)

0 引 言

大數(shù)據(jù)環(huán)境下的高維數(shù)據(jù)在人臉識別、圖像檢索[1-3]等領(lǐng)域有著廣泛的應用前景,是數(shù)據(jù)挖掘和模式識別領(lǐng)域的研究熱點。但是高維數(shù)據(jù)具有冗余度大、空間維數(shù)高等特點,難以發(fā)現(xiàn)其內(nèi)在的特征規(guī)律。降維是消除高維數(shù)據(jù)維度上冗余的一種技術(shù)手段,目的是克服維數(shù)災難,獲取數(shù)據(jù)本質(zhì)特征,以實現(xiàn)數(shù)據(jù)可視化。

降維分為線性降維和非線性降維。線性降維算法主要有主成分分析(principal component analysis,PCA[4])、多維尺度變換(multidimensional scaling,MDS[5])、線性判別分析(linear discriminant analysis,LDA[6])等。這類方法的優(yōu)勢在于處理線性結(jié)構(gòu)的數(shù)據(jù)集時具有很好的降維效果。但現(xiàn)實生活中大多都是高維非線性數(shù)據(jù),例如人臉數(shù)據(jù),因此非線性降維方法應運而生。基于特征值的非線性降維方法是其中一個重要研究方向。這類方法是保持高維數(shù)據(jù)與低維數(shù)據(jù)的某個“不變特征量”以找到低維特征表示。主要的基于特征值的非線性降維算法有等規(guī)度映射(isometric feature mapping,ISOMAP[7)、局部切空間算法(Local tangent space alignment,LTSA[8])、局部線性嵌入(locally linear embedding,LLE[9])、拉普拉斯特征映射(Laplacian eigenmaps,LE[10])、近鄰保持嵌入(neighborhood preserving embedding,NPE[11])等。ISOMAP算法保持的不變特征量是測地距離;LTSA算法保持的不變特征量是利用局部PCA投影后的局部線性化;LLE算法和NPE算法類似,保持的不變特征量都是局部重構(gòu)系數(shù);LE算法保持的不變特征量則是數(shù)據(jù)鄰域關(guān)系。

目前,學者們已經(jīng)在人臉識別[12]、語音識別[13]等眾多領(lǐng)域?qū)PE算法展開了廣泛的應用研究。例如,王志強對非控環(huán)境下獲取的高維人臉圖像進行降維研究,期望尋找一種映射或者投影,得到高維復雜數(shù)據(jù)中的低維本質(zhì)結(jié)構(gòu)[14];Zhen Ye等人提出了基于稀疏或協(xié)同表示的降維方法,將稀疏或協(xié)同系數(shù)作為圖像的權(quán)值,有效地減少重建誤差[15]。但是在進行線性重構(gòu)時沒有考慮到類間的權(quán)值信息以及類內(nèi)的密度信息,因此在數(shù)據(jù)降維上仍有局限性。梁春燕等人通過構(gòu)建鄰接圖以獲得數(shù)據(jù)的局部鄰域結(jié)構(gòu),同時通過有監(jiān)督訓練對數(shù)據(jù)進行類別標注[16]。盡管考慮到了數(shù)據(jù)類間之間的信息情況,進一步提高數(shù)據(jù)的識別性能,但對數(shù)據(jù)類內(nèi)信息欠學習,算法的性能需進一步提高。Sumet Mehta等人[17]提出了一種加權(quán)鄰域保持嵌入算法(WNPEE),構(gòu)造了一個相鄰圖的集合,使得最近鄰的數(shù)目k的選擇是變化的,這種方法對鄰域大小參數(shù)的敏感性相比NPE要低得多,盡管敏感度有所下降,但沒有有效考慮到數(shù)據(jù)的類別信息,算法的優(yōu)越性也會有所下降。

上述降維算法都有較強的計算優(yōu)勢,但是在處理局部鄰域信息量不足、存在短路以及流形曲率大等稀疏數(shù)據(jù)時,原始數(shù)據(jù)的幾何拓撲結(jié)構(gòu)損壞嚴重?；诖?本文對NPE算法中的數(shù)據(jù)類間信息進行優(yōu)化,構(gòu)造類間權(quán)值矩陣,在鄰域選擇中可對數(shù)據(jù)類間信息進行很好的區(qū)分;并在低維局部重建時引入類內(nèi)密度信息。從數(shù)據(jù)類內(nèi)和類間兩個維度出發(fā),更好地避免數(shù)據(jù)在近鄰選取方向上的缺失,提出了一種優(yōu)化的近鄰保持嵌入算法(optimal NPE,ONPE)。

為了驗證ONPE算法的實用性和有效性,將ONPE算法與LLE、NPE在Coil-20數(shù)據(jù)庫上進行了對比實驗,并對實驗結(jié)果進行了分析,證明了新算法具有較強的魯棒性。

1 NPE算法

1.1 NPE算法的思想

NPE算法是一種非常重要的子空間學習算法,認為每一個數(shù)據(jù)點都可以由其近鄰點的線性加權(quán)組合構(gòu)造得到。因此,NPE算法的降維原理是試圖在降維過程中保持樣本局部的線性結(jié)構(gòu)不變,以在低維空間中進行二次特征提取。

假設(shè)高維空間RD中有N個樣本訓練集X=[x1,x2,…,xN],xi∈RD,通過LLE算法尋求一個最優(yōu)的映射變換矩陣M,將X映射到低維空間Rd中,從而得到低維數(shù)據(jù)集Y=[y1,y2,…,yN],yi∈Rd,且d?D。

NPE算法可以歸結(jié)為三步：

(1)尋找每個樣本點的k個近鄰點。

NPE算法把xi表示成如公式(1)所示的凸組合形式,也就是xi可由k個最近鄰線性表示,所以要求數(shù)據(jù)所在流形為凸集。

(1)

在高維空間中尋找每個樣本點的k近鄰點。距離公式通?？梢杂檬?2)表示：

(2)

一般選用P=2,采用歐氏距離表示兩點之間的實際距離。

(2)計算出樣本點的局部重建權(quán)值矩陣。

定義一個誤差函數(shù)ε(W),其中Wij(i=1,2,…,N)可以存儲在N×N的稀疏矩陣W中,這個矩陣并不是對稱的,即Wij≠Wji,對于兩個近鄰的點而言,它們各自的近鄰程度是不同的。

(3)

其中,xj(j=1,2,…,k)為xi的k個近鄰點;Wij是xi與xj之間的權(quán)值,且要滿足條件：

(4)

其中,Wi=[Wi1,Wi2,…,WiN]為第i個樣本點的局部重建權(quán)值。

(3)將所有的樣本點映射嵌入到低維空間Rd中。映射嵌入滿足如下條件：

(5)

利用權(quán)值向量Wij重構(gòu)數(shù)據(jù)間的局部幾何拓撲結(jié)構(gòu),并使局部重建損失函數(shù)φ(Y)取值最小,從而得到低維嵌入數(shù)據(jù)集Y=[y1,y2,…,yN]。

NPE算法其實是一個線性重建的過程,利用局部的線性來逼近全局的非線性,通過相互重疊的局部信息提供全局結(jié)構(gòu)的信息。

1.2 NPE算法降維失效的原因

總的來說,NPE算法對局部鄰域信息量不足、存在短路以及流形曲率大等稀疏數(shù)據(jù)降維失效有兩個原因：一是NPE算法在k近鄰選擇時只是單純利用歐氏距離確定樣本點的線性結(jié)構(gòu),沒有考慮到數(shù)據(jù)間的類別信息,可能使得不同類別的數(shù)據(jù)交織在一起,影響降維效果。二是稀疏數(shù)據(jù)間的密度變化較大,僅單純利用Wij進行低維幾何拓撲結(jié)構(gòu)的重建,不能很好地反映k近鄰的密度信息?；谏鲜鲈?qū)е戮植啃畔㈦y以正確刻畫,難以反映數(shù)據(jù)間的幾何拓撲結(jié)構(gòu),導致降維失敗。

2 改進的近鄰保持嵌入(ONPE)

2.1 類間權(quán)值的刻畫

NPE算法是用兩數(shù)據(jù)點間重構(gòu)權(quán)值Wij來保持數(shù)據(jù)在低維空間的幾何拓撲結(jié)構(gòu)不變。但是NPE算法沒有考慮到數(shù)據(jù)間的類別信息,在近鄰選擇時,容易把不同類別的數(shù)據(jù)劃分到一個近似線性的局部流形結(jié)構(gòu)中,從而造成在實際應用中無法揭示數(shù)據(jù)內(nèi)在的真實結(jié)構(gòu),如圖1所示。

圖1 未考慮到類別信息的近鄰選擇情況

為了解決上述問題,盡量使類內(nèi)距離最小,而類間距離最大。因此,采取以下解決方案,一是在ONPE算法中引入了類間權(quán)值,以增加類間的離散度,使降維后不同類別之間具有最優(yōu)的分離性。二是在類內(nèi)引入密度信息,并用密度信息來調(diào)整類內(nèi)權(quán)值距離矩陣,以使類內(nèi)分散度盡量小。

2.2 ONPE算法的基本思想

假設(shè)高維空間中有數(shù)據(jù)集X={x1,x2,…,xN},xi∈RD,將X嵌入映射得到低維空間中的數(shù)據(jù)集Y={y1,y2,…,yN},yi∈Rd(d?D)。將訓練樣本X分成t類,X=(X1,X2,…,Xt),低維嵌入為Y=(Y1,Y2,…,Yt)T,ONPE算法將公式(5)的目標函數(shù)定義為：

(6)

將上述公式(6)中的φ(W)函數(shù)變化為：

(7)

對公式(7)進行化簡：

MTS(I-Z)T(I-Z)STM=

MTX(I-Wt)T(I-Wt)XTM-

MTS(I-Z)T(I-Z)STM=

tr(MTB1M-MTB1M)=

tr(MT(B1-B2)M)

(8)

其中,

B1=X(I-Wt)T(I-Wt)XT

B2=S(I-Z)T(I-Z)ST

對于公式(8)的限制條件為YYT=NI,結(jié)合約束條件,將公式(8)改為：

L(M)=MT(B1-B2)M-λ(YYT-NI)=

MT(B1-B2)M-λ(MTXXTM)

利用Lagrange乘子,則有：

?2(B1-B2)M=2λXXTM

根據(jù)上式可得M=(a0,a1,…,ad-1),其中a0,a1,…,ad-1為(XXT)-1(B1-B2)的廣義特征值λ0,λ1,…,λd-1所對應的特征向量。進而得到低維空間坐標為Y=MTX。

ONPE算法的過程描述如下：

Step3：計算(XXT)-1(B1-B2),將其進行特征分解,得到特征值λ0>λ1>…>λD及其對應的特征向量矩陣U=[a0,a1,…,aD];

Step4：取U的前d個最大特征值所對應的特征向量M=(a0,a1,…,ad-1),得到Y(jié)=MTX。

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

3.1 圖像檢索應用

實驗采用Columbia object image library的Coil-20數(shù)據(jù)庫作為實驗對象, 此數(shù)據(jù)庫共含14類不同的物體,每類都是從72個不同角度拍攝得到的,共1 008幅圖像。

利用LLE、NPE和ONPE三種算法對Coil-20數(shù)據(jù)庫進行圖像檢索。提取圖像的Zernike矩作為圖像的形狀特征,得到基于形狀的特征空間。圖2是分別利用LLE、NPE和ONPE三種算法對第45號圖像作為目標圖像進行檢索的結(jié)果圖,并顯示前20個圖像的返回結(jié)果。

圖2 Coil-20檢索結(jié)果對比

采用查準率(Precision)和查全率(Recall)作為圖像相似度評價標準來驗證ONPE算法的有效性[18]。其中查準率P定義為檢索結(jié)果隊列中檢索到的目標圖像數(shù)與檢索結(jié)果隊列中所有的圖像數(shù)之比,即P=X/Y,其中X為目標圖像數(shù),Y的值等于20,為結(jié)果隊列中所有的圖像數(shù)[18]。查全率R定義為檢索結(jié)果隊列中檢索到的目標圖像數(shù)與數(shù)據(jù)庫中全部的目標圖像數(shù)之比,即R=X/F,F的值等于72,為數(shù)據(jù)庫中全部的目標圖像總數(shù)[18]。由精確度和查全率的定義可知,P∈[0,1],R∈[0,1]。

對Coil-20數(shù)據(jù)庫中的14類圖像分別進行圖像檢索,并計算出各個圖像的查準率和查全率,如表1所示。通過表1的結(jié)果可以看出,經(jīng)過改進后的ONPE算法在查準率和查全率上明顯優(yōu)于LLE和NPE。

表1 LLE、NPE和ONPE檢索結(jié)果的查準率和查全率

表2 LLE的檢索結(jié)果平均排序

表3 NPE的檢索結(jié)果平均排序

表4 ONPE的檢索結(jié)果平均排序

最后再做進一步精確判斷,由于檢索出來的圖像的顯示順序(由左到右,由上到下)是按照圖像間的相似距離由小到大進行排列的。因此,當越排在前面的圖像越與目標圖像相似時,說明算法越優(yōu)。通過圖2可見,利用ONPE檢索出的20個圖像全都是想要得到的目標圖像,并且與樣本圖像相似的圖像均排在前19位,只有一個圖像與樣本圖像稍有差別,它則是排在最后一位的。而LLE和NPE均沒有這樣的優(yōu)勢效果。這也體現(xiàn)出提出的ONPE算法在提取圖像的Zernike矩作為圖像的形狀特征時,有效地保持了Zernike矩的旋轉(zhuǎn)不變性。因此,在檢索的精確性上來說相對于LLE和NPE較高。

3.2 實驗結(jié)果分析

從上述實驗可以看出,NPE和LLE作為經(jīng)典的流形學習算法,均能保持流形的局部結(jié)構(gòu)不變。但ONPE在處理稀疏數(shù)據(jù)時降維效果卻遠優(yōu)于NPE和LLE,其主要原因分析如下：

(1)ONPE算法考慮到數(shù)據(jù)間的類別信息,引入了類間權(quán)值矩陣,類間距離對數(shù)據(jù)類別的可分性起著重要作用。在特征選擇和特征提取時,可確保使得類間分散度盡量大。

3.3 時間復雜度分析

降維算法的時間復雜度主要是由數(shù)據(jù)點的個數(shù)N、原始維數(shù)D以及近鄰點的個數(shù)k進行確定。

LLE和NPE算法的時間復雜度均是o(pN2)(其中p是稀疏矩陣中非零元與零元的比率)。ONPE同NPE在算法執(zhí)行過程中不同之處在于類間權(quán)值矩陣和類內(nèi)密度信息的構(gòu)造,計算類間權(quán)值矩陣所需時間為o(2DN2),計算類內(nèi)密度信息所需時間為o(kN)。綜上,ONPE的時間復雜度亦是o(pN2),類間權(quán)值矩陣和密度信息的計算并沒有增加算法總的時間復雜度。

4 結(jié)束語

該文對經(jīng)典的流形學習算法LLE和NPE進行研究,針對處理局部鄰域信息量不足、存在短路以及流形曲率大等稀疏數(shù)據(jù)時失效的問題,提出了一種優(yōu)化的近鄰保持嵌入降維算法ONPE。在ONPE算法中引入了類間權(quán)值,以增加類間的離散度,使降維后不同類別之間具有最優(yōu)的分離性;在類內(nèi)引入密度信息,并用密度信息來調(diào)整類內(nèi)權(quán)值距離矩陣,以使類內(nèi)分散度盡量小。ONPE算法能夠更好地保持稀疏數(shù)據(jù)的原始幾何拓撲結(jié)構(gòu),具有魯棒性。通過在手工流形、圖像檢索、可視化等實際領(lǐng)域中的應用,證明了算法的實用性和有效性。

對于該算法進一步的工作思路,是降低鄰域大小參數(shù)的敏感性,由于ONPE算法對于每個樣本點的k近鄰的選取是固定的,因此對于不同類別數(shù)據(jù)間近鄰選取方向上會造成偏差。當處理含有噪聲或者局部信息量不足的數(shù)據(jù)集時,找到一個較恰當?shù)泥徲騻€數(shù)對于降維效果的影響還是非常大的。因此,可引入壓縮感知技術(shù)進行子空間的優(yōu)化,減少降維過程中由于近鄰個數(shù)選取的不當帶來的誤差,從而增加了算法的穩(wěn)定性。