基于LLE的數(shù)據(jù)降維方法研究

楊志偉 黃秀云

摘要：隨著當今社會科學技術的飛速發(fā)展，數(shù)據(jù)信息日益向高維化過渡，所以，想要從它們之間提取出我們所需要的信息越來越難，也給我們帶來了前所未有的挑戰(zhàn)。因此，對把高維數(shù)據(jù)通過降維的方法投影到一個相對低維的空間，進而找到隱藏在其間對我們有用的低維結構的研究就成為當前工作中的重中之重。鑒于此，本文主要進行了以下的工作：

①簡述了當前國內外關于降維方法的研究情況以及當前一些比較流行的降維方法。

②重點分析了非線性降維方法——局部線性嵌入，局部線性嵌入算法（locally linear embedding，LLE）是解決降維的方法，并通過實驗結果對比PCA與LLE算法。

③結合已有的一些結論對該算法中參數(shù)的選擇方法做了改進。

關鍵詞：局部線性嵌入LLE 數(shù)據(jù)降維 主成分分析PCA

1 緒論

1.1 目的和意義

1.1.1 圖像處理及其目的和意義

所謂圖像處理（image processing），又叫數(shù)字圖像處理，就是用計算機對已有的圖形信息進行分析、修改、加工或其他方式的處理，以達到應用者或觀賞者在視覺或心理上所需要的要求。其本質是一段能被計算機還原顯示、并修改和導出一幅圖形的數(shù)字碼。很多情況下，外界的圖形信息對于人的肉眼來說是無法準確捕捉甚至是不可見的，通過數(shù)字圖像處理中的模式識別技術，可以把人類肉眼無法識別的圖形進行分類處理，快速、準確的查找、匹配和識別出需要的信息。

1.1.2 降維的目的及意義

隨著科技的飛速發(fā)展，人們在行為過程中所接觸和處理的數(shù)據(jù)已經不再是局限的小數(shù)據(jù)，而是蘊含信息量很多的超大型數(shù)據(jù)，也就是本文的處理對象——高維數(shù)據(jù)。這些數(shù)據(jù)晦澀難懂，難以發(fā)掘，卻蘊含著各個方面我們需要獲取和應用的信息，利用這些信息可以大大提高我們的科技水平和生活水平。要從這些超大型數(shù)據(jù)中搜尋出我們所需要了解的信息，總結出隱藏在數(shù)據(jù)中的本質特征并加以運用，是一個很有難度的工程。也就是所謂的“維數(shù)災難”。

為了克服“維數(shù)災難”這個難題，人們總結和研究出一些降維方法，即通過線性或非線性方法使高維空間輸入進來的數(shù)據(jù)樣本在保存其高維空間中的本質結構特征的情況下被映射到一個滿足要求的低維空間，這就是降維的基本思想。其目的是提取和顯示出隱藏在高維樣本觀測數(shù)據(jù)中無法直接獲取但卻具有研究價值的信息并在低維空間顯示，使其能夠得以應用。

1.2 國內外研究概況

解決降維問題的方法主要可以分為兩大類：線性降維方法與非線性降維方法。國外較早的意識到了研究降維方法的重要性，目前已逐漸建立形成較為系統(tǒng)的理論方法體系并在各個領域中得到了較為廣泛的運用；而在國內的發(fā)展則相對緩慢，但近年來也在降維方法的研究上取得了很大的進步。

最早開始研究并得到應用的是線性降維方法，其中以二十世紀早期提出的主成分分析法（PCA）應用最廣，至今仍然在各個領域的降維問題中占有很大的比重甚至是主要地位。它是可以在方差最大化的映射方向上，以丟失很少的數(shù)據(jù)的代價把許多冗雜的指標轉化成數(shù)量不多的幾個綜合指標的方法。之后又提出了線性判別法（LDA），這種方法先找出原始樣本觀測數(shù)據(jù)的特征向量，并將數(shù)據(jù)映射到一個合適的低維方向上，映射成功后能做到不同集合的數(shù)據(jù)盡量分開，而同一集合內的樣本數(shù)據(jù)就相對靠攏，最后在低維空間中再一次對映射過后的樣本數(shù)據(jù)進行更加詳細的分類。[2]

1.3 降維問題的分類

根據(jù)降維結果的要求和降維目的不同，把降維要處理的問題大致歸為三類：

1.3.1 硬降維問題

這是最基本的一種降維問題，目的就是前文所敘述的，把高維原始樣本觀測數(shù)據(jù)映射到低維空間上以便尋找數(shù)據(jù)結構上的基本特征。它的處理對象維數(shù)高達幾十萬，所以必須對數(shù)據(jù)集進行非常徹底的降維，以使數(shù)據(jù)能夠進行處理。

1.3.2 軟降維問題

本質上是維數(shù)不高的低維數(shù)據(jù)，但在形式上表現(xiàn)為高維空間的流形，我們的目的就是將其進行變換，使其可以用低維的方式進行表示。

1.3.3 可視化問題

這種待處理數(shù)據(jù)一般本身維數(shù)并不高，但是為了提高數(shù)據(jù)的視覺效果，必須繼續(xù)對其進行降維，一般取2或3。[2]

1.4 降維方法概述

1.4.1 線性降維方法

線性降維方法本質是建立最佳線性模型，只不過不同的方法對降維結果的要求不同，所以建立的線性模型也都不相同，都有自己的側重點。它因為直接，所以具有一些很好的性質，如：計算量小、可解釋性較強等。

線性方法主要有：主成分分析（PCA）、線性判別法（LDA）、投影尋蹤（PP）。

1.4.2 非線性降維方法

在現(xiàn)實生活中我們所需要研究的數(shù)據(jù)集合絕大多數(shù)時候表現(xiàn)為非線性的結構，這時線性方法就不能達到很好的處理效果，非線性降維方法成為了研究的重點。

非線性降維方法建立的模型可以處理非常復雜的非線性結構的數(shù)據(jù)，但作為代價的是計算相對復雜，計算量大，并且可解釋性較差。

非線性方法主要有：局部線性嵌入法（LLE）、多維尺度法（MDS）、等距映射法（ISOMAP）、拉普拉斯特征映射（LE）、核-主成分分析（K-PCA）、局部切空間法（LTSA）。

2 局部線性嵌入降維法

局部線性嵌入算法（locally linear embedding，LLE）是一種應用很廣，并且是針對非線性數(shù)據(jù)降維的方法，它的特點是可以使處理后的低維數(shù)據(jù)保持和高維原始觀測樣本數(shù)據(jù)相同的拓撲關系。

2.1 LLE-局部線性嵌入算法

LLE算法可以由圖1所示的一個例子來形象地描述。在圖1所示中，LLE能很好地將三維非線性數(shù)據(jù)映射到二維空間中。如果把圖1（B）中的數(shù)據(jù)分別看成是分布在三維空間中的兩類數(shù)據(jù)，通過LLE算法降維后，則數(shù)據(jù)在二維空間中仍能保持相對獨立的兩類。在圖1（B）中的黑色小圈中可以看出，如果將黑色小圈中的數(shù)據(jù)映射到二維空間中，如圖1（C）中的黑色小圈所示，映射后的數(shù)據(jù)仍能保持原有的數(shù)據(jù)流形，這說明LLE算法確實能保持流形的領域不變性。

■

圖1 LLE降維示例

由此可以看出LLE算法可以應用于樣本的聚類。而線性方法，如PCA，是無法與它比擬的。LLE算法不僅操作簡單，而且算法的優(yōu)化不涉及到局部最小化。不過雖然該算法能解決非線性映射，但當處理數(shù)據(jù)的維數(shù)過大或數(shù)量過多，涉及到的稀疏矩陣過于龐大，就不易于處理了。在圖1所示的球形面中，當缺少北極面時，LLE算法能很好的將其映射到二維空間中，如圖1中的（C）所示。但倘若數(shù)據(jù)分布在整個封閉的球面上，LLE就不能很好的將它映射到二維空間了，并且無法保持原有的數(shù)據(jù)流形。所以在處理數(shù)據(jù)中，為了便于處理，我們首先假設數(shù)據(jù)不是分布在閉合的球面或者橢球面上的。

圖1為非線性降維的一個實例：（B）是從A中提取的樣本點（位于三維空間），通過非線性降維算法（LLE），將數(shù)據(jù)映射到二維空間中如（C）。從（C）圖中的顏色可以看出通過LLE算法處理后的數(shù)據(jù)，能很好的保持原有數(shù)據(jù)的鄰域特性。

2.2 LLE-LLE及其參數(shù)的確定

2.2.1 LLE-LLE算法簡介

局部線性嵌入的核心思想是對一組在高維空間上的數(shù)據(jù)項，要求使原嵌套空間與內在低維空間局部鄰域關系相同，即在原嵌套空間中每個樣本點可以用它的近鄰點線性表示，在低維空間中保持每個鄰域中的權重值不變，重構原數(shù)據(jù)點，使重構誤差最小。

LLE算法大致可以歸納為三個步驟：

①尋找每個樣本點的k個近鄰點。

②由每個樣本點的近鄰點計算出該樣本點的局部重建權值矩陣。

③由該樣本點的局部重建權值矩陣和其近鄰點計算出該樣本點在低維空間上投影的輸出值。

具體的算法流程如圖2所示。

■

圖2 LLE算法的三個步驟

2.2.2 局部線性嵌入法（LLE）的原理分析

局部線性嵌入算法的第一個步驟是計算出高維空間中每個樣本點xi（i=1，2，…，n）的k個近鄰點，把距離所求樣本點最近的k個其他樣本點定義為所求樣本點的k個近鄰點。k是一個根據(jù)計算要求預先的給定值。

局部線性嵌入算法的第二個步驟是計算出樣本點的局部重建權值矩陣。這里需要定義一個成本函數(shù)（cost function），如式（1）所示，用來測量重建誤差：

即所有樣本點與它們的重建之間的距離的平方和。令w■■是第j個近鄰點到第i個樣本點之間的權重。為了計算權重w■■，我們提出兩個限制條件來作為成本函數(shù)取最小值的標準：首先，每個樣本點xi僅從它的近鄰點那里被重建，如果xj不屬于xi的近鄰點的集合，則令w■■=0；其次，矩陣中每行的權重總和為1，即：■w■■=1。

為了讓重建的誤差最小，權重w■■必須服從一種重要的對稱性，即對所有特定樣本點來說，它們與自己的近鄰點之間經過旋轉、重新排列、轉換等各種變換后，彼此之間的拓撲結構必須保持不變，以達到讓重建權重準確描述每個近鄰的基本幾何特性的要求。所以可以認為高維原始空間內的數(shù)據(jù)局部幾何特征和在映射過后的低維流形上的局部拓撲結構是完全等效的。

局部線性嵌入算法的最后一個步驟是把所有高維原始空間上的觀測樣本點集xi映射到內部全局坐標的低維向量yi上并輸出。w■■代表著高維空間上xi周圍的局部信息，又由于映射結果需要在低維空間中最大化地保持原始空間中的局部線性結構，映射條件必須滿足式（2）所示的成本函數(shù)：

其中， 為成本函數(shù)值，yi是xi在低維空間上的輸出向量，yj是xi的第j個近鄰點在低維空間上的輸出向量，并且要滿足以下兩個條件：

式（4）中的1指的是m*m單位矩陣。

為了使成本函數(shù)值取到最小值，取yj為M的最小m個非零特征值所對應的單位坐標特征向量。我們需要將M的特征值按照遞增的順序進行排列，通常第一個特征值很小，所以舍去。一般取第2到第m+1之間的特征值所對應的單位坐標特征向量作為輸出結果。

3 LLE的一些改進算法的簡述

3.1 自適應LLE算法（ALLE算法）

所謂自適應，即算法程序自行根據(jù)將要處理的對象的樣本點分布狀況，自動選擇近鄰點個數(shù)k。

前面已經提到過，LLE算法的第一步中選取k值在大部分情況下是根據(jù)經驗選擇的一個活動性很大的值，需要嘗試且不方便控制：

①k取的過大就可能會影響整個流形的平滑性，甚至丟失流形的一些小規(guī)模的結構，而k取的過小則又可能會把連續(xù)的流形誤劃分成脫節(jié)的子流形。

②且如果對所有樣本集區(qū)域內的樣本點選取相同的近鄰點個數(shù)，對于所含結構信息很重要的樣本集區(qū)域，也許就會丟失許多我們所需要和尋找的內容，相反，對于所含結構信息不重要的樣本集區(qū)域，就會額外加大許多不必要的計算量，浪費了計算機的效率和時間，甚至可能會因為多選取了一些錯誤的近鄰點，破壞了其真實的局部結構特征，使最后的低維流形與實際不符，從而誤導我們的分析，也就是所謂的噪聲干擾和冗余數(shù)據(jù)的影響。

③對于彎曲弧度非常大的不光滑流形，基本LLE算法所采用的一致的值也會使高維數(shù)據(jù)流形在低維空間映射的結果與數(shù)據(jù)集本身的實際不符。

綜上所述，k值的自適應選取是改進LLE算法性能的關鍵。

ALLE算法采用APC對高維的數(shù)據(jù)進行聚類（APC（affinity propagation clustering），仿射傳播聚類，有效率高、不依靠起始點選取等多種優(yōu)秀性質，它將全體樣本點都作為候選的類代表點），將聚類以后的高維數(shù)據(jù)結果作為LLE算法的輸入。

ALLE的第一個步驟就是計算樣本點所在區(qū)域內的N個點之間的相似度，并得出相似度矩陣S，矩陣的元素為

（5）

■

圖3 ALLE算法流程

這里的距離采用歐氏距離，選取矩陣的對角線元素p=s（j，j）為xi與其他樣本點的平均相似度。令r（i，j）和a（i，j）為零，其中r（i，j）是xj對xi的吸引度，表示xj相對于xi的類代表程度，a（i，j）是xi對xj的歸屬度，表示xi選擇xj作為自己的類代表點的合適程度。通過對這兩個量的迭代并求和，進行數(shù)據(jù)的收集和傳遞，調整p=s（j，j）使目標函數(shù)達到最優(yōu)，滿足一定的條件后停止，找到每個點各自的類代表點，每個點只在它們各自的類代表點集區(qū)域內建立最合適的局部重建矩陣，以達到所有樣本點能夠應根據(jù)自身所處的局部結構特征自適應地選擇近鄰點個數(shù)k的目的。最后，計算局部重建矩陣，最小化重構誤差（注：此時高維的誤差函數(shù)和低維的重構誤差函數(shù)都需要重新定義），計算低維空間的投影。[7]

3.2 加權局部線性嵌入算法（WLLE算法）

基本LLE對噪聲的干擾十分敏感，為了改進LLE的性能，提出了加權局部線性嵌入算法（WLLE）。

WLLE算法相對于基本LLE算法的主要區(qū)別在構建局部重構權值矩陣W，滿足重構誤差函數(shù)之后，這時需要計算每個樣本點xi對自身所處的樣本集的重要性Dii，公式（6）：

其中

然后計算高維空間X在低維空間的映射Y，滿足（8）約束條件：

（8）

使加權誤差函數(shù)

（9）

達到最小。

最后，對稀疏對稱矩陣

（10）

進行非稀疏對角化，得到其最小的（d+1）個特征值對應的特征向量。由于第一個特征值接近于零，故舍去，則高維空間的樣本集在X的低維空間上的映射Y通常取第2到第（d+1）個非零特征值對應的特征向量，d表示嵌入的維數(shù)。[6，7]

4 局部線性嵌入算法的相關實驗及其結果

4.1 LLE葉片數(shù)據(jù)集實驗及其結果

為了驗證局部線性嵌入算法在圖像處理降維方面的高效性和優(yōu)越性，需要利用植物葉片數(shù)據(jù)庫進行分類實驗。該數(shù)據(jù)庫包括220種植物的16846幅葉片圖像。本次試驗從68幅夾竹桃葉片圖像中隨機選取30幅作為正類樣本，再從其他219種植物葉片中隨機選取30幅作為負類樣本。部分圖像葉片如圖4所示。

■

（a）夾竹桃 （b）其他

圖4 正負類葉片圖像

因為源數(shù)據(jù)庫中圖片大小不一，為方便起見對所有圖像進行預處理：將其低采樣成64×64像素、256灰度級、白色背景的灰度圖像。每幅圖像構成1個矩陣。然后將每個矩陣以行為單位依次連接成1個一維向量（詳見附錄程序）。得到二維可視化結果如圖7所示。

在樣本集的量較大的時候，LLE算法相對于其他降維方式的優(yōu)越性會更大。

4.2 結論

實驗結果表明PCA方法對于樣本類別信息挖掘不夠，所以數(shù)據(jù)的聚類效果很差，而該算法因為更有效地利用了樣本的類別信息，樣本的聚類性能較好，因此利用最簡單的分類器也可以得到較優(yōu)的分類效果。

但是對于k值的選擇仍然是通過反復實驗確定的最優(yōu)值。顯然自適應性有所欠缺；同時對于測試樣本低維映射關系的確立也采用的是通用的近似的方法。

5 結束語

本文主要完成了以下的各項研究工作：

①簡述了數(shù)據(jù)降維的目的和意義。

②簡述了當前國內外關于降維方法的研究情況。

③重點分析了非線性降維方法——局部線性嵌入，局部線性嵌入算法（locally linear embedding，LLE） 是解決降維的方法。

④通過實驗驗證了LLE算法的效果和優(yōu)越性。

⑤簡述了目前幾種基于LLE算法的改進算法的原理及其針對問題的處理結果的優(yōu)越性。

參考文獻：

[1]余肖生，周寧.高維數(shù)據(jù)降維方法研究[J].情報科學，2007，8，25（8）：1248-1251.

[2]黃移軍.基于局部線性嵌入的高維數(shù)據(jù)降維研究[D].中南大學，2009.

[3]馬瑞，宋亦旭.基于局部線性嵌入（LLE）非線性降維的多流形學習[J].清華大學學報（自然科學版），2008，48（4）：583-586.

[4]張善文，黃德雙.一種魯棒的監(jiān)督流形學習算法及其在植物葉片分類中的應用[J].模式識別與人工智能，2010，23（6）：836-841.

[5]丁嬌，梁棟，閻慶.基于WLLE和SVM的植物葉片圖像識別方法[J].安徽大學學報（自然科學版），2013，7，37（4）：61-67.

[6]張善文，王獻峰.基于加權局部線性嵌入的植物葉片圖像識別方法[J].農業(yè)工程學報，2011，12，27（12）：141-145.

[7]李博，楊丹，雷明，葛永新.基于近鄰消息傳遞的自適應局部線性嵌入[J].光電子·激光，2010，21（5）：772-778.