改進(jìn)的局部線性嵌入算法及其應(yīng)用

邱建榮，羅 漢

湖南大學(xué) 數(shù)學(xué)與計(jì)量經(jīng)濟(jì)學(xué)院，長(zhǎng)沙410082

1 引言

隨著社會(huì)的不斷進(jìn)步與發(fā)展，數(shù)據(jù)采集越來(lái)越容易，海量的數(shù)據(jù)迅速產(chǎn)生，人們遇到的數(shù)據(jù)不再是局限于一個(gè)小范圍的幾筆小數(shù)據(jù)，取而代之的是正以指數(shù)形式增長(zhǎng)的大型數(shù)據(jù)，即現(xiàn)在常說(shuō)的高維數(shù)據(jù)，維數(shù)過(guò)高導(dǎo)致維數(shù)災(zāi)難，為解決“維災(zāi)”問(wèn)題，降維方法呼之而出，降維算法分為線性算法與非線性算法，線性算法中具有代表性的有：主成分分析（Principal Component Analysis，PCA）[1]、線性判別分析（Linear Discriminant Analysis，LDA）[2]、多維尺度變換（Multidimensional Scaling，MDS）[3]等，2DPCA算法[4]是一種圖像特征提取方法，該方法被廣泛地應(yīng)用在人臉等圖像識(shí)別領(lǐng)域。對(duì)于本質(zhì)結(jié)構(gòu)為非線性低維流形的高維數(shù)據(jù)線性降維效果不好。而核方式和流形學(xué)習(xí)方法作為非線性降維算法對(duì)本質(zhì)非線性分布的數(shù)據(jù)降維效果良好。核方式是指非線性結(jié)構(gòu)數(shù)據(jù)通過(guò)一種核映射到更高維的空間，使其數(shù)據(jù)結(jié)構(gòu)在該空間呈現(xiàn)線性結(jié)構(gòu)，再通過(guò)經(jīng)典的線性降維方法進(jìn)行降維，具有代表性的方法如核主成分分析方法（Kernel Principal Component Analysis，KPCA）[5]。流形學(xué)習(xí)方法分為全局算法與局部算法，等距映射（Isometric Feature Mapping，ISOMAP）[6]是經(jīng)典的全局算法，而局部線性嵌入（Locally Linear Embedding，LLE）[7]、拉普拉斯特征映射（Laplacian Eigenmap，LE）[8]、局部切空間排列（Local Tangent Space Alignment，LTSA）[9]等算法都是經(jīng)典的局部算法。

LLE算法作為一種經(jīng)典的流形學(xué)習(xí)算法，在人臉圖像識(shí)別、數(shù)據(jù)挖掘以及機(jī)器學(xué)習(xí)等領(lǐng)域得到了成功應(yīng)用。但原始的LLE算法存在著一些問(wèn)題，最突出的問(wèn)題是其用歐氏距離查找近鄰點(diǎn)不能有效應(yīng)用于高維數(shù)據(jù)結(jié)構(gòu)中。近年來(lái)提出了許多針對(duì)查找近鄰點(diǎn)方式的改進(jìn)算法：其中ISOLLE（LLE with geodesic distance）[10]是利用測(cè)地線距離來(lái)尋找近鄰點(diǎn)，實(shí)驗(yàn)結(jié)果顯示測(cè)地線距離能夠比歐氏距離更能準(zhǔn)確地解決非線性曲面問(wèn)題；張強(qiáng)[11]針對(duì)偏離樣本整體分布的樣本點(diǎn)在低維重構(gòu)過(guò)程中可能映射在其他平面的不足，同時(shí)結(jié)合Kmeans++算法的優(yōu)點(diǎn)，提出了基于聚類(lèi)的Cluster-SLLE算法；RLLE（Locally Linear Embedding based on Rank-order Distance）[12]采用的是另外一種新提出的距離度量方法叫Rank-order距離，它能夠比歐氏距離更準(zhǔn)確地查找高維空間中數(shù)據(jù)點(diǎn)的近鄰信息；劉方原等[13]提出一種改進(jìn)重構(gòu)權(quán)值的局部線性嵌入算法（IRWLLE），更好地保持了流形的近鄰關(guān)系，對(duì)流形的展開(kāi)更加完好。當(dāng)數(shù)據(jù)的分布呈現(xiàn)曲率較大的流形時(shí)，傳統(tǒng)的歐氏距離只能反映數(shù)據(jù)間的線性關(guān)系，會(huì)造成在流形實(shí)際分布較遠(yuǎn)的兩點(diǎn)在低維空間中近鄰的偏差，無(wú)法有效體現(xiàn)數(shù)據(jù)間的空間結(jié)構(gòu)關(guān)系。如圖1所示，用直線距離并不能衡量流形上A與B兩點(diǎn)間的相對(duì)位置關(guān)系，而用沿曲面上的測(cè)地線距離來(lái)表示A與B兩點(diǎn)間的距離更有實(shí)際意義。本文提出基于Geodesic Rank-order距離度量的局部線性嵌入算法，該算法先應(yīng)用最短路徑算法（Dijkstra算法）[14-15]找到的最短路徑長(zhǎng)度來(lái)近似兩個(gè)樣本點(diǎn)之間的測(cè)地線距離，然后計(jì)算Rank-order距離用于LLE算法的相似性度量，在ORL以及Yale人臉數(shù)據(jù)集上取得較好實(shí)驗(yàn)效果。

圖1 歐氏距離與測(cè)地線距離對(duì)比圖

2 局部線性嵌入方法

LLE算法的主要思想：采集的高維數(shù)據(jù)樣本點(diǎn)都可以利用局部鄰域的點(diǎn)來(lái)線性表示，并保持局部鄰域權(quán)值不變，在低維空間中重新構(gòu)造原來(lái)的數(shù)據(jù)點(diǎn)，使得重構(gòu)誤差達(dá)到最小。

LLE算法的具體步驟：設(shè)X={ x1,x2,…,xN}∈RD×N是高維歐氏空間RD中的數(shù)據(jù)集。數(shù)據(jù)集處于本征維數(shù)為d（d＜D，一般情況下d＜＜D）的低維空間，因此，設(shè)Y={ y1,y2,…,yN}∈Rd×N是嵌入空間Rd上的一個(gè)低維嵌入。

步驟1局部鄰域選取，假設(shè)對(duì)于一個(gè)給定的高維數(shù)據(jù)集：

利用歐幾里德距離公式：

找到每個(gè)樣本點(diǎn)xi鄰域的k(k＜N)個(gè)近鄰點(diǎn)記為N(xi)。

步驟2計(jì)算樣本點(diǎn)鄰域的重構(gòu)權(quán)重，該權(quán)重使得xi的局部重構(gòu)誤差平方最小化：

其中，wij為xi和xj之間的權(quán)值，xj?N(xi)時(shí)wij=0且wii=0。

步驟3通過(guò)得到的權(quán)值矩陣W，找到每個(gè)樣本點(diǎn)的低維嵌入yi∈Rd，使重構(gòu)誤差平方和函數(shù)最小化：

為了求解的唯一性，對(duì)yi加以限制：

其中，Id×d表示單位矩陣。那么，優(yōu)化問(wèn)題則轉(zhuǎn)化為下面的約束優(yōu)化問(wèn)題：

利用Lagrange乘子法可知上述優(yōu)化問(wèn)題等價(jià)于求一個(gè)對(duì)稱、半正定、稀疏的矩陣M=(I-W)T(I-W)的最小的d個(gè)非零特征值特征向量。

綜上所述，事實(shí)上LLE的整個(gè)過(guò)程就是：

3 Geodesic Rank-order距離

在高維空間中用歐氏距離作為兩個(gè)樣本點(diǎn)的相似性度量并不可靠，尋找的局部鄰域信息不一定準(zhǔn)確。本文提出一種新的距離——Geodesic Rank-order距離，該距離首先應(yīng)用最短路徑算法（Dijkstra算法）找到的最短路徑長(zhǎng)度來(lái)近似兩個(gè)樣本點(diǎn)之間的測(cè)地線距離，然后計(jì)算Rank-order距離。Geodesic Rank-order距離是在測(cè)地線距離基礎(chǔ)上利用兩個(gè)樣本點(diǎn)共享的近鄰點(diǎn)信息來(lái)計(jì)算兩個(gè)樣本之間的距離。加入近鄰點(diǎn)的共享信息會(huì)提高距離度量的可靠程度。具體計(jì)算步驟如下：

步驟1用Dijkstra算法計(jì)算每個(gè)樣本點(diǎn)xi與其他樣本之間的測(cè)地線距離，并按距離的升序排列。

步驟2計(jì)算每?jī)蓚€(gè)點(diǎn)xi和xj之間的非對(duì)稱的Rankorder距離D(xi,xj)，計(jì)算公式為：

其中，fxi(k)代表xi的第k個(gè)近鄰點(diǎn)；Oxi(xj)是指xj在xi的近鄰點(diǎn)列表中的位置，即xj是xi的第幾個(gè)最近鄰點(diǎn)。xi與xj的非對(duì)稱Rank-order距離越小則意味著它們的最近鄰點(diǎn)結(jié)構(gòu)越相似，xi與xj在空間中的真實(shí)距離越近。如圖2所示。

圖2 點(diǎn)與點(diǎn)之間的共享近鄰信息

點(diǎn)xi與xj的非對(duì)稱性距離：

步驟3計(jì)算得到對(duì)稱且歸一化的Geodesic Rankorder距離，簡(jiǎn)稱GRD(xi,xj)：

4 改進(jìn)的局部線性嵌入

LLE方法的第一步是計(jì)算樣本點(diǎn)之間的歐氏距離來(lái)查找k個(gè)近鄰點(diǎn)，但是在結(jié)構(gòu)復(fù)雜的高維數(shù)據(jù)用歐氏距離找到的近鄰點(diǎn)并不可靠。所以，本文在給出了Geodesic Rank-order距離的具體定義及步驟之后，以Geodesic Rank-order距離替換LLE算法中的歐氏距離，其他步驟與LLE算法步驟一致，該方法稱為GRDLLE算法，其偽代碼描述如下：

輸入：原始數(shù)據(jù)集X=(x1,x2,…,xN)∈RD×N；d為低維空間的維度；k為選取近鄰點(diǎn)的個(gè)數(shù)。

輸出：d維的向量Y。

步驟1運(yùn)用Dijkstra算法計(jì)算每個(gè)樣本點(diǎn)xi與其他樣本之間的測(cè)地線距離，并按距離的升序排列。

步驟2 for i=1 to N

end

步驟3用GRD(xi,xj)尋找每個(gè)樣本點(diǎn)的k近鄰點(diǎn)。

步驟4用

步驟5計(jì)算半正定M=(I-W)T(I-W)矩陣。

步驟6 Y等于M=(I-W)T(I-W)矩陣的第2至第d+1個(gè)最小的特征值對(duì)應(yīng)的特征向量。

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

5.1 實(shí)驗(yàn)平臺(tái)及實(shí)驗(yàn)數(shù)據(jù)

本文將應(yīng)用LLE、ISOLLE、RLLE、2DPCA以及GRDLLE算法在ORL以及Yale人臉數(shù)據(jù)集上作對(duì)比實(shí)驗(yàn)，所有的程序均用Matlab語(yǔ)言編程，在Matlab 2015a軟件平臺(tái)實(shí)現(xiàn)，計(jì)算機(jī)配置為：Intel?CoreTMi5-6200u CPU@2.30 GHz 2.40 GHz處理器，4.00 GB內(nèi)存與Windows 10操作系統(tǒng)。

為了驗(yàn)證GRDLLE算法的有效性，對(duì)ORL人臉圖像及Yale人臉數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)，并與LLE、ISOLLE、RLLE、2DPCA算法進(jìn)行比較。ORL人臉數(shù)據(jù)庫(kù)由劍橋大學(xué)AT&T實(shí)驗(yàn)室采集和整理，總共40個(gè)人，每人有10幅不同圖像，每幅圖像為112×92像素，圖像呈現(xiàn)出不同時(shí)間、光照、人臉表情、面部飾品的變化，Yale人臉數(shù)據(jù)庫(kù)包含165個(gè)灰度圖像，總共15個(gè)人。每人有11張圖片，每幅圖像為243×320像素，圖像包括不同的面部表情或配置：中光，眼鏡，快樂(lè)；左光，不戴眼鏡，正常；右光，悲傷，困倦，驚訝和眨眼；部分人的人臉圖像樣本；如圖3、4所示。

圖3 ORL人臉圖像樣本對(duì)比圖

將圖像分為訓(xùn)練集和測(cè)試集2組，每人50%～60%的圖像作為訓(xùn)練集，其他圖像作為測(cè)試集，實(shí)驗(yàn)數(shù)據(jù)集描述如表1所列。

圖4 Yale人臉圖像樣本對(duì)比圖

表1 實(shí)驗(yàn)數(shù)據(jù)集描述

5.2 參數(shù)選擇

對(duì)于LLE、ISOLLE、RLLE以及GRDLLE算法有兩個(gè)待定參數(shù)：近鄰點(diǎn)個(gè)數(shù)k和降維后維數(shù)d。

由于近鄰點(diǎn)個(gè)數(shù)過(guò)多可能會(huì)忽略掉一些小規(guī)模的結(jié)構(gòu)信息，而過(guò)少又會(huì)誤將連續(xù)的流形劃分為脫節(jié)的子流形。因此實(shí)驗(yàn)中近鄰點(diǎn)個(gè)數(shù)k取經(jīng)驗(yàn)值6～18。

k值選定后，對(duì)于參數(shù)d，采用判斷高維數(shù)據(jù)和低維數(shù)據(jù)距離矩陣的線性相關(guān)性來(lái)找出最佳的d，兩者相關(guān)性越大，則表示降維結(jié)果保存的信息越多。計(jì)算公式如下：

其中，ρ是指線性相關(guān)系數(shù)，DX和DY分別為X和Y的距離矩陣。

改變近鄰點(diǎn)個(gè)數(shù)k和計(jì)算最佳的低維空間維度d來(lái)尋找每種降維算法所能達(dá)到的最大識(shí)別率，而2DPCA算法選擇總體散布矩陣的最佳d個(gè)最大特征值對(duì)應(yīng)特征向量構(gòu)成投影矩陣得到最大識(shí)別率。

5.3 實(shí)驗(yàn)結(jié)果

分別采用LLE、ISOLLE、RLLE以及GRDLLE算法對(duì)整理好的ORL以及Yale圖像數(shù)據(jù)集進(jìn)行降維，用KNN分類(lèi)器進(jìn)行人臉識(shí)別。采用2DPCA算法對(duì)整理好的ORL以及Yale圖像數(shù)據(jù)集進(jìn)行特征提取，依據(jù)特征投影矩陣的最小距離判別法進(jìn)行圖像識(shí)別。識(shí)別率為識(shí)別正確的測(cè)試樣本數(shù)與總測(cè)試樣本數(shù)之比。

如表2，展示了五種算法在ORL以及Yale人臉圖像上最大識(shí)別率的比較，對(duì)比發(fā)現(xiàn)采用GRDLLE算法降維后的識(shí)別率比其他四種算法高，表明在這五種方法中GRDLLE算法用于人臉識(shí)別的正確識(shí)別率最高。

表2 ORL以及Yale數(shù)據(jù)集上的人臉識(shí)別率

6 結(jié)束語(yǔ)

LLE算法是一種經(jīng)典的非線性降維算法，其廣泛應(yīng)用于人臉識(shí)別、數(shù)據(jù)挖掘以及機(jī)器學(xué)習(xí)等領(lǐng)域中，針對(duì)LLE算法中近鄰點(diǎn)選取采用歐式距離并不能很好地應(yīng)用于結(jié)構(gòu)復(fù)雜的高維數(shù)據(jù)集中這個(gè)缺點(diǎn)，本文提出了一種改進(jìn)的局部線性嵌入算法GRDLLE結(jié)合測(cè)地線距離和Rand-order距離的各自特點(diǎn)，能更準(zhǔn)確地計(jì)算高維空間中樣本點(diǎn)之間的距離，查找的近鄰點(diǎn)更為準(zhǔn)確。通過(guò)對(duì)ORL以及Yale人臉數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)表明，GRDLLE算法降維后采用分類(lèi)器進(jìn)行人臉識(shí)別的識(shí)別率最高，表明GRDLLE算法具有很好的降維效果。

但GRDLLE算法也存在一些需要改進(jìn)的地方：一是在近鄰參數(shù)選取上，沒(méi)有提供標(biāo)準(zhǔn)的選取辦法，大多數(shù)是憑經(jīng)驗(yàn)選取；二是并未引進(jìn)樣本的類(lèi)別信息。如何獲得近鄰參數(shù)的最佳選取辦法以及如何引入類(lèi)別信息提供效果更佳的降維方法將是下一步的研究重點(diǎn)。