一種優化的近鄰保持嵌入降維算法研究

李燕燕,閆德勤

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

0 引 言

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

降維分為線性降維和非線性降維。線性降維算法主要有主成分分析(principal component analysis,PCA[4])、多維尺度變換(multidimensional scaling,MDS[5])、線性判別分析(linear discriminant analysis,LDA[6])等。這類方法的優勢在于處理線性結構的數據集時具有很好的降維效果。但現實生活中大多都是高維非線性數據,例如人臉數據,因此非線性降維方法應運而生。基于特征值的非線性降維方法是其中一個重要研究方向。這類方法是保持高維數據與低維數據的某個“不變特征量”以找到低維特征表示。主要的基于特征值的非線性降維算法有等規度映射(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算法類似,保持的不變特征量都是局部重構系數;LE算法保持的不變特征量則是數據鄰域關系。

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

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

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

1 NPE算法

1.1 NPE算法的思想

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

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

NPE算法可以歸結為三步：

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

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

(1)

在高維空間中尋找每個樣本點的k近鄰點。距離公式通常可以用式(2)表示：

(2)

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

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

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

(3)

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

(4)

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

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

(5)

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

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

1.2 NPE算法降維失效的原因

總的來說,NPE算法對局部鄰域信息量不足、存在短路以及流形曲率大等稀疏數據降維失效有兩個原因：一是NPE算法在k近鄰選擇時只是單純利用歐氏距離確定樣本點的線性結構,沒有考慮到數據間的類別信息,可能使得不同類別的數據交織在一起,影響降維效果。二是稀疏數據間的密度變化較大,僅單純利用Wij進行低維幾何拓撲結構的重建,不能很好地反映k近鄰的密度信息。基于上述原因導致局部信息難以正確刻畫,難以反映數據間的幾何拓撲結構,導致降維失敗。

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

2.1 類間權值的刻畫

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

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

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

2.2 ONPE算法的基本思想

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

(6)

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

(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,結合約束條件,將公式(8)改為：

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

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

利用Lagrange乘子,則有：

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

根據上式可得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=MTX。

3 實驗結果及分析

3.1 圖像檢索應用

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

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

圖2 Coil-20檢索結果對比

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

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

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

表2 LLE的檢索結果平均排序

表3 NPE的檢索結果平均排序

表4 ONPE的檢索結果平均排序

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

3.2 實驗結果分析

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

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

3.3 時間復雜度分析

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

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

4 結束語

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

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