基于Kernel Rank-order距離的重構權重局部線性嵌入算法

鞠 玲 王正群 徐春林 楊 洋

1(揚州大學信息工程學院 江蘇 揚州 225127)2(江蘇曙光光電有限公司 江蘇 揚州 225009)

0 引 言

眾所周知，現實生活中的很多信息數據是高維的、非線性的，處理這些信息時預先維數簡約可以提高計算機處理數據的效率。流形學習就是一種行之有效的降維和保存特征的方法，即使對于高度彎曲和重疊的高維數據集合仍然能夠有效地提取數據的主要特征，進行高效的降維[1]。局部線性嵌入算法LLE[2]、等距離映射法Isomap[3]和局部切空間算法LTSA[4]等是經典的流形學習算法，其中，局部線性嵌入算法在實際中應用極為廣泛，它可以保持高維的數據拓撲結構在低維中仍然不變。但是LLE也存在很多問題[5-10]：1) 如果樣本點分布稀疏或者不均勻，則可能會引起不均勻的扭曲和折疊；2) 受離群點影響較大，可能導致低維坐標嵌入失敗；3) 缺乏對新樣本的處理能力；4) 算法的結果對鄰居數和正則化參數非常敏感；5) 傳統LLE使用的是歐幾里得距離，可能會導致短路。針對這些問題，很多學者在以下幾個方面對LLE作出了改進：1) 鄰域大小的自適應選擇[11]，例如根據流形的彎曲度、數據點之間的相關性大小和類內類間距離的比值動態地決定鄰域大小；2) 增強對樣本點的監督[12-13]，例如增加類標簽；3) 設計更合理的重構權重[14-16]，例如結合范數、凸輪距離或者是結構特征等設計權重系數；4) 增強對離群點的魯棒性[17]，比如通過增加結構信息或者根據數據分布的密度來減少離群點的影響。為了解決對降維過程中出現的短路、離群點影響大和結構信息缺乏的問題，本文對重構權重進行合理的改進，先通過將樣本點映射到高維以獲得對樣本點更好的分類效果從而計算得到近鄰點集，再結合基于Kernel Rank-order距離的重構權重系數和結構系數減少離群點的影響和增加數據間的結構信息，使得對有效樣本點的識別效果更好。

1 相關工作

權重代表著近鄰點在線性表示樣本點時貢獻的大小，通過重構權重，可以使與樣本點同屬于一類的近鄰點獲得更大的貢獻值，從而使樣本在降維后仍能保持較好的局部特征。在獲得更合理的重構權重方面，前人已經做了很多研究。2011年劉昶等[18]提出的加權判別局部多線性嵌入算法(Weighted Discriminative Locally Multi-linear Embedding，WDLME)，根據類邊界上樣本點距離越近，相互影響較大的原理，通過引入高斯核函數構建重構權重的加權函數：

Wij=e-‖xi-xj‖2/α

(1)

式中：xi為樣本點，xj為其鄰近點，α為一個實數。

為了加強LLE算法對曲率和離群點的魯棒性，劉方原等[19]提出改進重構權值的局部線性嵌入算法(IRWLLE)，他們重新定義了重構權重：

(2)

(3)

(4)

2 基于核函數距離局部鄰域選擇

若是數據點在原始空間難以被區分，則無法構造良好的鄰域。可以通過非線性特征映射將輸入空間提升到更高維的特征空間，數據在高維空間中變得線性可分。眾所周知，只要問題公式僅涉及數據點之間的內積運算而不涉及數據點本身，核函數就允許這種非線性擴展而無需明確形式。 定義以下映射：

k(x,y)=φ(x)·φ(y)φ:x∈RD→RN(D≤N)

(5)

式中：RD為D維空間，RN為N維空間。根據統計學和泛函的有關理論，一種核函數k(x,y)對應某一特征空間的內積，需要滿足Mercer條件。

?k(x,x′)φ(x)φ(x′)dxdx>0

(6)

其中多項式核函數和高斯核函數應用最為廣泛。

多項式核函數：

k(x,y)=(a(x·y)+b)d

(7)

式中：a>0，b≥0，d為正整數。

高斯徑向基函數：

(8)

式中：σ∈R。

將原空間中的樣本點映射到高維，使得原本不能有效分類的數據點變得更加線性可分。根據核函數，可以構建核距離dk(x,y)：

dk(x,y)=‖φ(x)-φ(y)‖=

(9)

由式(9)得到樣本點xi與其他點的距離值，將其他點按其與xi距離值從小到大排列組成xi的近鄰點集合Ni。

3 重構權重系數

權重代表著近鄰點在線性表示樣本點時貢獻的大小，所以能否較好地重構權重直接決定與樣本點相關性大的近鄰點能否獲得最大比重和降維后的數據可否最大限度地保留樣本特征。重構權重可以通過重新定義新的權重或者增添權重系數得到。本文采用增添權重系數的方法，先結合Rank-order距離和核函數得到基于Kernel Rank-order距離的重構權重系數，再利用樣本點和近鄰點間的歐氏距離和測地線距離得到結構權重系數。

3.1 Kernel Rank-order距離

在低維空間中，對于曲率過大或者有數據點分布偏離總體模式的流形，傳統歐氏距離只能反映數據點間的線性關系，不能選擇出對降維真正有效的近鄰點。Kernel Rank-order距離結合了核映射和Rank-order距離。核映射是將低維空間的數據點映射到高維，使在低維空間不可分的數據變得線性可分，獲得更好的特征提取效果，在此基礎上再利用Rank-order距離進行度量。Rank-order距離的大小反映了數據點間的相關性的大小，而離群點與數據點間的相似性較小，故可以有效地減少離群點對降維的影響。

第一步計算樣本點xi與其近鄰點xj(xj∈Ni)之間的Rank-order距離，公式如下：

(10)

式中：fxi(a)表示xi中第a個樣本點，Oxi(xj)表示xj在xi近鄰點列表中的位置，xj為xi的第j個近鄰點。同理Oxj(fxi(a))表示fxi(a)在xj近鄰點列表中的位置。D(xi,xj)越小說明它們共享的近鄰點越多，相似性越高。Rank-order 距離示意圖如圖1所示。

圖1 Rank-order距離

Oxj(xn)+Oxj(xj)=5+2+4+0=11

第二步將得到的距離進行對稱化和歸一化得到Kernel Rank-order距離(KRD)如下:

(11)

3.2 基于Kernel Rank-order距離的重構權重系數

Kernel Rank-order距離代表了兩個點之間的相關性，距離越小，說明兩點之間的相關性越高，由此定義基于Kernel Rank-order距離的樣本點xi的近鄰點xj的重構權重系數δij:

(12)

式中：dim為xi與其所有近鄰點xj的KRD(xi,xj)距離的中值，δij越大，說明xj與xi的相關性越高，xj對xi的貢獻率越高。

因為離群點的Kernel Rank-order距離很大，則離群點的δij很小，說明離群點對xi的貢獻很小，對降維結果的影響很小。

3.3 結構權重系數

針對局部線性嵌入算法(LLE)不能充分使用結構信息的不足，本文提出一種包含結構信息的重構權重的結構系數ζij，近鄰點xj的結構系數ζij的計算公式如下：

(13)

式中：DG和DE分別表示樣本點xi與其近鄰點xj之間的測地線距離和歐氏距離。ζij越小說明近鄰點xj偏離線性平面的程度越大，對xi的重構貢獻越小。

離群點過于偏離流形，所以其結構權重系數很小，不影響降維的結果。因此KRLLE對離群點有較好的魯棒性。

4 算法設計

1) 選擇局部鄰域。利用式(5)將樣本點xi(i=1,2,…,N)映射到高維，由式(9)得到樣本點xi與其他點的核距離，按升序排列，選擇前k個點組成xi的近鄰點集Ni={xi1,xi2,…,xik}。

2) 計算權重向量wi。最小化誤差函數并對權重系數wij做歸一化限制：

(14)

計算得到權重向量：wi=[wi1,wi2,…,wik]T(i=1,2,…,N)。

(15)

(16)

4) 固定權重矩陣W。計算xi的低維嵌入坐標yi與yi的近鄰點yij，在限制條件最小化誤差函數得到低維輸出集Y：

(17)

式(17)可化為:

J(Y)=tr(Y(I-W)(I-W)TYT)

(18)

令M=(I-W)(I-W)T，求出M的最小前d+1個特征值對應的特征向量，因為第一個特征值接近于0，其特征向量全1，所以剔除第一個特征值，取前2到d個特征值，所對應的特征向量即為所求的低維嵌入坐標。算法流程如圖2所示。

圖2 算法流程圖

5 實 驗

為了測試KRLLE算法的有效性，在ORL人臉庫、Yale人臉庫和MNIST手寫體數據庫上將KRLLE算法與WDLME、IRWLLE算法做比較，并對ORL人臉庫、Yale人臉庫和MNIST手寫體數據庫進行加噪，進而驗證KRLLE算法對離群點的魯棒性。

5.1 實驗數據庫介紹

ORL：由劍橋大學AT&T實驗室創建,一共包含40名志愿者，每人各10幅照片，共400幅面部圖像,部分志愿者的圖像包括了姿態、表情和面部飾物的變化，每幅圖像的尺寸均為112×92像素。圖3展示了ORL人臉庫中其中一位志愿者的一組照片。

圖3 ORL人臉

Yale：每個志愿者的10幅臉部照片，相比于ORL人臉數據庫，Yale庫中每個對象采集的樣本包含更明顯的光照、表情和姿態以及遮擋變化。圖4為Yale人臉庫中其中一位志愿者的照片。

圖4 Yale人臉庫

MNIST手寫體庫：由Google實驗室的Corinna Cortes和紐約大學柯朗研究所的Yann LeCun建立的一個手寫數字數據庫，訓練庫有60 000幅手寫數字圖像，測試庫有10 000幅。每幅圖片的尺寸均為28×28，圖5展示了數字3的10幅手寫體照片。

圖5 MNIST手寫體庫

5.2 原始實驗數據實驗結果

固定近鄰數K,觀察不同維數下本文KRLLE、WDLME[18]和IRWLLE[19]算法在ORL人臉庫、Yale人臉庫和MNIST手寫體數據庫上的識別率，分別如圖6-圖8所示。

圖6 不同維數下KRLLE、WDLME和IRWLLE算法在ORL人臉庫上的識別率

圖7 不同維數下KRLLE、WDLME和IRWLLE算法在Yale人臉庫上的識別率

圖8 不同維數下KRLLE、WDLME和IRWLLE算法在MNIST手寫體庫上的識別率

可以看出，在不同的維數下，KRLLE算法的識別率大部分高于其他兩種算法。為了減少實驗的偶然性，在ORL人臉庫、Yale人臉庫和MNIST手寫體數據庫上進行了多次實驗，表1-表3列出了其中7次實驗的識別率及平均識別率。可以看出，不管在人臉庫還是在MNIST手寫體數據庫上，KRLLE算法的識別率都高于WDLME和IRWLLE算法。

表1 KRLLE、WDLME和IRWLLE

表2 KRLLE、WDLME和IRWLLE

表3 KRLLE、WDLME和IRWLLE算法

5.3 加噪實驗數據實驗結果

離群點是偏移同類模式總體分布的數據點，位于總體分布邊緣區域。為了驗證算法對離群點是否具有較好的魯棒性，給ORL人臉庫、Yale人臉庫和MNIST手寫體數據集上增加噪聲點并進行實驗，圖9-圖11分別為ORL人臉庫、Yale人臉庫和MNIST手寫體數據庫中一組加了噪聲點的照片。

圖9 加噪聲點的ORL人臉庫

圖10 加噪聲點的Yale人臉庫

圖11 加噪聲點的MNIST手寫體庫

KRLLE、WDLME和IRWLLE算法在加噪聲點的ORL人臉庫、Yale人臉庫和MNIST手寫體數據庫上的識別率，分別如圖12-圖14所示。表4-表6分別列出了在加噪聲點的ORL人臉庫、Yale人臉庫和MNIST手寫體數據庫上的隨機抽取的7次實驗的平均識別率。

圖12 不同維數下KRLLE、WDLME和IRWLLE算法在加噪聲點的ORL人臉庫上的識別率

圖13 不同維數下KRLLE、WDLME和IRWLLE算法在加噪聲點的Yale人臉庫上的識別率

圖14 不同維數下KRLLE、WDLME和IRWLLE算法在加噪聲點的MNIST手寫體庫上的識別率

表4 KRLLE、WDLME和IRWLLE算法

表5 KRLLE、WDLME和IRWLLE算法

表6 KRLLE、WDLME和IRWLLE算法

續表6

由圖12-圖14可以看出，在加了噪聲點的數據庫上KRLLE的識別率仍然比IRWLLE和WDLME高。此外，比對表1和表4、表2和表5、表3和表7發現，KRLLE的識別率分別由0.94、0.92和0.93變為0.91、0.90和0.89，只略微下降。這是因為IRWLLE在選取近鄰點時利用核函數將數據點映射到高維增加了數據點的可分性，獲得了更好的特征提取效果，另外基于Kernel Rank-order距離的重構權重系數和結構系數將過于偏離流形的噪聲數據點的權重值減小了，所以對于加噪數據，KRLLE仍能最大限度地不受噪聲點的影響，準確地找到優質的近鄰點，具有較強的魯棒性。與KRLLE相比，IRWLLE的識別率從0.92、0.83和0.82下降為0.82、0.76和0.73，WDLME的識別率從0.89、0.81和0.82下降為0.78、0.69和0.72 。由此可見，IRWLLE和WDLME的識別率下降幅度明顯，對噪聲點的魯棒性較差。

6 結 語

本文提出基于Kernel Rank-order距離的重構權重局部線性嵌入算法KRLLE對LLE算法進行改進。(1) 利用核函數距離度量得到數據點集的優質近鄰點集，核函數的利用可以獲得更好的特征提取效果。(2) 計算重構權重系數，主要分計算基于Kernel Rank-order距離的重構權重系數和結構權重系數兩步，基于Kernel Rank-order距離的重構權重系數是核映射和Rank-order距離的綜合應用，其大小跟數據點間的相關性大小成反比，因為離群點是偏離同類模式總體的點，所以它與樣本點的相關性小，基于Kernel Rank-order距離的重構權重系數小，減小了離群點的權重值，離群點偏離了總體流形，它的結構系數也減少了它的權重值。因此KRLLE增強了對離群點的魯棒性。(3) 計算加權重構權重。(4) 根據加權重構權重得到低維嵌入坐標。在ORL人臉庫、Yale人臉庫和MNIST上的實驗數據表明，KRLLE具有更高的識別率，不僅增加了結構信息，還提高了LLE算法對離群點的魯棒性。未來將對區分病態矩陣、離群點和樣本點進行研究。