改進的局部線性嵌入算法及其應用

邱建榮，羅 漢

湖南大學 數學與計量經濟學院，長沙410082

1 引言

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

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

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

2 局部線性嵌入方法

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

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

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

利用歐幾里德距離公式：

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

步驟2計算樣本點鄰域的重構權重，該權重使得xi的局部重構誤差平方最小化：

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

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

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

其中，Id×d表示單位矩陣。那么，優化問題則轉化為下面的約束優化問題：

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

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

3 Geodesic Rank-order距離

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

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

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

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

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

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

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

4 改進的局部線性嵌入

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

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

輸出：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個最小的特征值對應的特征向量。

5 實驗驗證

5.1 實驗平臺及實驗數據

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

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

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

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

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

表1 實驗數據集描述

5.2 參數選擇

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

由于近鄰點個數過多可能會忽略掉一些小規模的結構信息，而過少又會誤將連續的流形劃分為脫節的子流形。因此實驗中近鄰點個數k取經驗值6～18。

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

其中，ρ是指線性相關系數，DX和DY分別為X和Y的距離矩陣。

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

5.3 實驗結果

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

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

表2 ORL以及Yale數據集上的人臉識別率

6 結束語

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

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