邱建榮，羅 漢

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

1 引言

隨著社會的不斷進步與發(fā)展，數(shù)據(jù)采集越來越容易，海量的數(shù)據(jù)迅速產(chǎn)生，人們遇到的數(shù)據(jù)不再是局限于一個小范圍的幾筆小數(shù)據(jù)，取而代之的是正以指數(shù)形式增長的大型數(shù)據(jù)，即現(xiàn)在常說的高維數(shù)據(jù)，維數(shù)過高導(dǎo)致維數(shù)災(zāi)難，為解決“維災(zāi)”問題，降維方法呼之而出，降維算法分為線性算法與非線性算法，線性算法中具有代表性的有：主成分分析（Principal Component Analysis，PCA）[1]、線性判別分析（Linear Discriminant Analysis，LDA）[2]、多維尺度變換（Multidimensional Scaling，MDS）[3]等，2DPCA算法[4]是一種圖像特征提取方法，該方法被廣泛地應(yīng)用在人臉等圖像識別領(lǐng)域。對于本質(zhì)結(jié)構(gòu)為非線性低維流形的高維數(shù)據(jù)線性降維效果不好。而核方式和流形學(xué)習方法作為非線性降維算法對本質(zhì)非線性分布的數(shù)據(jù)降維效果良好。核方式是指非線性結(jié)構(gòu)數(shù)據(jù)通過一種核映射到更高維的空間，使其數(shù)據(jù)結(jié)構(gòu)在該空間呈現(xiàn)線性結(jié)構(gòu)，再通過經(jīng)典的線性降維方法進行降維，具有代表性的方法如核主成分分析方法（Kernel Principal Component Analysis，KPCA）[5]。流形學(xué)習方法分為全局算法與局部算法，等距映射（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é)習算法，在人臉圖像識別、數(shù)據(jù)挖掘以及機器學(xué)習等領(lǐng)域得到了成功應(yīng)用。但原始的LLE算法存在著一些問題，最突出的問題是其用歐氏距離查找近鄰點不能有效應(yīng)用于高維數(shù)據(jù)結(jié)構(gòu)中。近年來提出了許多針對查找近鄰點方式的改進算法：其中ISOLLE（LLE with geodesic distance）[10]是利用測地線距離來尋找近鄰點，實驗結(jié)果顯示測地線距離能夠比歐氏距離更能準確地解決非線性曲面問題；張強[11]針對偏離樣本整體分布的樣本點在低維重構(gòu)過程中可能映射在其他平面的不足，同時結(jié)合Kmeans++算法的優(yōu)點，提出了基于聚類的Cluster-SLLE算法；RLLE（Locally Linear Embedding based on Rank-order Distance）[12]采用的是另外一種新提出的距離度量方法叫Rank-order距離，它能夠比歐氏距離更準確地查找高維空間中數(shù)據(jù)點的近鄰信息；劉方原等[13]提出一種改進重構(gòu)權(quán)值的局部線性嵌入算法（IRWLLE），更好地保持了流形的近鄰關(guān)系，對流形的展開更加完好。當數(shù)據(jù)的分布呈現(xiàn)曲率較大的流形時，傳統(tǒng)的歐氏距離只能反映數(shù)據(jù)間的線性關(guān)系，會造成在流形實際分布較遠的兩點在低維空間中近鄰的偏差，無法有效體現(xiàn)數(shù)據(jù)間的空間結(jié)構(gòu)關(guān)系。如圖1所示，用直線距離并不能衡量流形上A與B兩點間的相對位置關(guān)系，而用沿曲面上的測地線距離來表示A與B兩點間的距離更有實際意義。本文提出基于Geodesic Rank-order距離度量的局部線性嵌入算法，該算法先應(yīng)用最短路徑算法（Dijkstra算法）[14-15]找到的最短路徑長度來近似兩個樣本點之間的測地線距離，然后計算Rank-order距離用于LLE算法的相似性度量，在ORL以及Yale人臉數(shù)據(jù)集上取得較好實驗效果。

圖1 歐氏距離與測地線距離對比圖

2 局部線性嵌入方法

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

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上的一個低維嵌入。

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

利用歐幾里德距離公式：

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

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

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

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

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

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

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

綜上所述，事實上LLE的整個過程就是：

3 Geodesic Rank-order距離

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

步驟1用Dijkstra算法計算每個樣本點xi與其他樣本之間的測地線距離，并按距離的升序排列。

步驟2計算每兩個點xi和xj之間的非對稱的Rankorder距離D(xi,xj)，計算公式為：

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

圖2 點與點之間的共享近鄰信息

點xi與xj的非對稱性距離：

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

4 改進的局部線性嵌入

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

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

輸出：d維的向量Y。

步驟1運用Dijkstra算法計算每個樣本點xi與其他樣本之間的測地線距離，并按距離的升序排列。

步驟2 for i=1 to N

end

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

步驟4用

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

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

5 實驗驗證

5.1 實驗平臺及實驗數(shù)據(jù)

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

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

圖3 ORL人臉圖像樣本對比圖

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

圖4 Yale人臉圖像樣本對比圖

表1 實驗數(shù)據(jù)集描述

5.2 參數(shù)選擇

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

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

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

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

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

5.3 實驗結(jié)果

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

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

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

6 結(jié)束語

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

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