鞠 玲 王正群 徐春林 楊 洋

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

0 引 言

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

1 相關(guān)工作

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

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

(1)

式中：xi為樣本點(diǎn)，xj為其鄰近點(diǎn)，α為一個(gè)實(shí)數(shù)。

為了加強(qiáng)LLE算法對(duì)曲率和離群點(diǎn)的魯棒性，劉方原等[19]提出改進(jìn)重構(gòu)權(quán)值的局部線性嵌入算法(IRWLLE)，他們重新定義了重構(gòu)權(quán)重：

(2)

(3)

(4)

2 基于核函數(shù)距離局部鄰域選擇

若是數(shù)據(jù)點(diǎn)在原始空間難以被區(qū)分，則無(wú)法構(gòu)造良好的鄰域?？梢酝ㄟ^(guò)非線性特征映射將輸入空間提升到更高維的特征空間，數(shù)據(jù)在高維空間中變得線性可分。眾所周知，只要問(wèn)題公式僅涉及數(shù)據(jù)點(diǎn)之間的內(nèi)積運(yùn)算而不涉及數(shù)據(jù)點(diǎn)本身，核函數(shù)就允許這種非線性擴(kuò)展而無(wú)需明確形式。 定義以下映射：

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

(5)

式中：RD為D維空間，RN為N維空間。根據(jù)統(tǒng)計(jì)學(xué)和泛函的有關(guān)理論，一種核函數(shù)k(x,y)對(duì)應(yīng)某一特征空間的內(nèi)積，需要滿(mǎn)足Mercer條件。

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

(6)

其中多項(xiàng)式核函數(shù)和高斯核函數(shù)應(yīng)用最為廣泛。

多項(xiàng)式核函數(shù)：

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

(7)

式中：a>0，b≥0，d為正整數(shù)。

高斯徑向基函數(shù)：

(8)

式中：σ∈R。

將原空間中的樣本點(diǎn)映射到高維，使得原本不能有效分類(lèi)的數(shù)據(jù)點(diǎn)變得更加線性可分。根據(jù)核函數(shù)，可以構(gòu)建核距離dk(x,y)：

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

(9)

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

3 重構(gòu)權(quán)重系數(shù)

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

3.1 Kernel Rank-order距離

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

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

(10)

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

圖1 Rank-order距離

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

第二步將得到的距離進(jìn)行對(duì)稱(chēng)化和歸一化得到Kernel Rank-order距離(KRD)如下:

(11)

3.2 基于Kernel Rank-order距離的重構(gòu)權(quán)重系數(shù)

Kernel Rank-order距離代表了兩個(gè)點(diǎn)之間的相關(guān)性，距離越小，說(shuō)明兩點(diǎn)之間的相關(guān)性越高，由此定義基于Kernel Rank-order距離的樣本點(diǎn)xi的近鄰點(diǎn)xj的重構(gòu)權(quán)重系數(shù)δij:

(12)

式中：dim為xi與其所有近鄰點(diǎn)xj的KRD(xi,xj)距離的中值，δij越大，說(shuō)明xj與xi的相關(guān)性越高，xj對(duì)xi的貢獻(xiàn)率越高。

因?yàn)殡x群點(diǎn)的Kernel Rank-order距離很大，則離群點(diǎn)的δij很小，說(shuō)明離群點(diǎn)對(duì)xi的貢獻(xiàn)很小，對(duì)降維結(jié)果的影響很小。

3.3 結(jié)構(gòu)權(quán)重系數(shù)

針對(duì)局部線性嵌入算法(LLE)不能充分使用結(jié)構(gòu)信息的不足，本文提出一種包含結(jié)構(gòu)信息的重構(gòu)權(quán)重的結(jié)構(gòu)系數(shù)ζij，近鄰點(diǎn)xj的結(jié)構(gòu)系數(shù)ζij的計(jì)算公式如下：

(13)

式中：DG和DE分別表示樣本點(diǎn)xi與其近鄰點(diǎn)xj之間的測(cè)地線距離和歐氏距離。ζij越小說(shuō)明近鄰點(diǎn)xj偏離線性平面的程度越大，對(duì)xi的重構(gòu)貢獻(xiàn)越小。

離群點(diǎn)過(guò)于偏離流形，所以其結(jié)構(gòu)權(quán)重系數(shù)很小，不影響降維的結(jié)果。因此KRLLE對(duì)離群點(diǎn)有較好的魯棒性。

4 算法設(shè)計(jì)

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

2) 計(jì)算權(quán)重向量wi。最小化誤差函數(shù)并對(duì)權(quán)重系數(shù)wij做歸一化限制：

(14)

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

(15)

(16)

4) 固定權(quán)重矩陣W。計(jì)算xi的低維嵌入坐標(biāo)yi與yi的近鄰點(diǎn)yij，在限制條件最小化誤差函數(shù)得到低維輸出集Y：

(17)

式(17)可化為:

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

(18)

令M=(I-W)(I-W)T，求出M的最小前d+1個(gè)特征值對(duì)應(yīng)的特征向量，因?yàn)榈谝粋€(gè)特征值接近于0，其特征向量全1，所以剔除第一個(gè)特征值，取前2到d個(gè)特征值，所對(duì)應(yīng)的特征向量即為所求的低維嵌入坐標(biāo)。算法流程如圖2所示。

圖2 算法流程圖

5 實(shí) 驗(yàn)

為了測(cè)試KRLLE算法的有效性，在ORL人臉庫(kù)、Yale人臉庫(kù)和MNIST手寫(xiě)體數(shù)據(jù)庫(kù)上將KRLLE算法與WDLME、IRWLLE算法做比較，并對(duì)ORL人臉庫(kù)、Yale人臉庫(kù)和MNIST手寫(xiě)體數(shù)據(jù)庫(kù)進(jìn)行加噪，進(jìn)而驗(yàn)證KRLLE算法對(duì)離群點(diǎn)的魯棒性。

5.1 實(shí)驗(yàn)數(shù)據(jù)庫(kù)介紹

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

圖3 ORL人臉

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

圖4 Yale人臉庫(kù)

MNIST手寫(xiě)體庫(kù)：由Google實(shí)驗(yàn)室的Corinna Cortes和紐約大學(xué)柯朗研究所的Yann LeCun建立的一個(gè)手寫(xiě)數(shù)字?jǐn)?shù)據(jù)庫(kù)，訓(xùn)練庫(kù)有60 000幅手寫(xiě)數(shù)字圖像，測(cè)試庫(kù)有10 000幅。每幅圖片的尺寸均為28×28，圖5展示了數(shù)字3的10幅手寫(xiě)體照片。

圖5 MNIST手寫(xiě)體庫(kù)

5.2 原始實(shí)驗(yàn)數(shù)據(jù)實(shí)驗(yàn)結(jié)果

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

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

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

圖8 不同維數(shù)下KRLLE、WDLME和IRWLLE算法在MNIST手寫(xiě)體庫(kù)上的識(shí)別率

可以看出，在不同的維數(shù)下，KRLLE算法的識(shí)別率大部分高于其他兩種算法。為了減少實(shí)驗(yàn)的偶然性，在ORL人臉庫(kù)、Yale人臉庫(kù)和MNIST手寫(xiě)體數(shù)據(jù)庫(kù)上進(jìn)行了多次實(shí)驗(yàn)，表1-表3列出了其中7次實(shí)驗(yàn)的識(shí)別率及平均識(shí)別率?？梢钥闯?，不管在人臉庫(kù)還是在MNIST手寫(xiě)體數(shù)據(jù)庫(kù)上，KRLLE算法的識(shí)別率都高于WDLME和IRWLLE算法。

表1 KRLLE、WDLME和IRWLLE

表2 KRLLE、WDLME和IRWLLE

表3 KRLLE、WDLME和IRWLLE算法

5.3 加噪實(shí)驗(yàn)數(shù)據(jù)實(shí)驗(yàn)結(jié)果

離群點(diǎn)是偏移同類(lèi)模式總體分布的數(shù)據(jù)點(diǎn)，位于總體分布邊緣區(qū)域。為了驗(yàn)證算法對(duì)離群點(diǎn)是否具有較好的魯棒性，給ORL人臉庫(kù)、Yale人臉庫(kù)和MNIST手寫(xiě)體數(shù)據(jù)集上增加噪聲點(diǎn)并進(jìn)行實(shí)驗(yàn)，圖9-圖11分別為ORL人臉庫(kù)、Yale人臉庫(kù)和MNIST手寫(xiě)體數(shù)據(jù)庫(kù)中一組加了噪聲點(diǎn)的照片。

圖9 加噪聲點(diǎn)的ORL人臉庫(kù)

圖10 加噪聲點(diǎn)的Yale人臉庫(kù)

圖11 加噪聲點(diǎn)的MNIST手寫(xiě)體庫(kù)

KRLLE、WDLME和IRWLLE算法在加噪聲點(diǎn)的ORL人臉庫(kù)、Yale人臉庫(kù)和MNIST手寫(xiě)體數(shù)據(jù)庫(kù)上的識(shí)別率，分別如圖12-圖14所示。表4-表6分別列出了在加噪聲點(diǎn)的ORL人臉庫(kù)、Yale人臉庫(kù)和MNIST手寫(xiě)體數(shù)據(jù)庫(kù)上的隨機(jī)抽取的7次實(shí)驗(yàn)的平均識(shí)別率。

圖12 不同維數(shù)下KRLLE、WDLME和IRWLLE算法在加噪聲點(diǎn)的ORL人臉庫(kù)上的識(shí)別率

圖13 不同維數(shù)下KRLLE、WDLME和IRWLLE算法在加噪聲點(diǎn)的Yale人臉庫(kù)上的識(shí)別率

圖14 不同維數(shù)下KRLLE、WDLME和IRWLLE算法在加噪聲點(diǎn)的MNIST手寫(xiě)體庫(kù)上的識(shí)別率

表4 KRLLE、WDLME和IRWLLE算法

表5 KRLLE、WDLME和IRWLLE算法

表6 KRLLE、WDLME和IRWLLE算法

續(xù)表6

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

6 結(jié) 語(yǔ)

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