LLE算法及其改進算法介紹

1、LLE及其改進算法介紹Locally linear embedding (LLE) (Sam T.Roweis and Lawrence K.Saul, 2000)以及 Supervised locally linear embedding (SLLE) (Dick and Robert, 2002) 是最近提出的非線性降維方法，它能夠使降維后的數(shù)據(jù)保持原有拓撲結(jié) 構(gòu)。LLE算法可以有圖1所示的一個例子來描述。在圖1所示中，LLE能成功地 將三維非線性數(shù)據(jù)映射到二維空間中。如果把圖 1（ B）中紅顏色和藍顏色的數(shù) 據(jù)分別看成是分布在三維空間中的兩類數(shù)據(jù)，通過LLE算法降維后，則數(shù)據(jù)在二維空間中

2、仍能保持相對獨立的兩類。在圖 1（ B）中的黑色小圈中可以看出，女口 果將黑色小圈中的數(shù)據(jù)映射到二維空間中，如圖 1 （C）中的黑色小圈所示，映 射后的數(shù)據(jù)任能保持原有的數(shù)據(jù)流形，這說明LLE算法確實能保持流形的領(lǐng)域不 變性。由此LLE算法可以應(yīng)用于樣本的聚類。而線性方法，如 PCA和MDS都不 能與它比擬的。LLE算法操作簡單，且算法中的優(yōu)化不涉及到局部最小化。該算 法能解決非線性映射，但是，當處理數(shù)據(jù)的維數(shù)過大，數(shù)量過多，涉及到的稀疏 矩陣過大，不易于處理。在圖1中的球形面中，當缺少北極面時，應(yīng)用 LLE算法 則能很好的將其映射到二維空間中，如圖1中的C所示。如果數(shù)據(jù)分布在整個封 閉的球面

3、上，LLE則不能將它映射到二維空間，且不能保持原有的數(shù)據(jù)流形。那 么我們在處理數(shù)據(jù)中，首先假設(shè)數(shù)據(jù)不是分布在閉合的球面或者橢球面上。(B)a(C)IIIbl"3B是從A中提取的樣本點（三維），通過非線性降維11圖1非線性降維實例：算法（LLE），將數(shù)據(jù)映射到二維空間中（C）。從C圖中的顏色可以看岀通過LLE算法處理后的數(shù)據(jù)，能很好的保持原有數(shù)據(jù)的鄰域特性LLE算法是最近提出的針對非線性數(shù)據(jù)的一種新的降維方法， 處理后的低維 數(shù)據(jù)均能夠保持原有的拓撲關(guān)系。它已經(jīng)廣泛應(yīng)用于圖像數(shù)據(jù)的分類與聚類、文 字識別、多維數(shù)據(jù)的可視化、以及生物信息學(xué)等領(lǐng)域中。1 LLE算法LLE 算法可以歸結(jié)為三步

4、：（1）尋找每個樣本點的k個近鄰點；（2）由每個 樣本點的近鄰點計算出該樣本點的局部重建權(quán)值矩陣；（3）由該樣本點的局部重建權(quán)值矩陣和其近鄰點計算出該樣本點的輸出值。具體的算法流程如圖 2所 7示01, Compute the neiglibois of each data poi】it,焉LLE AUgdklTSI口V2. C ompute the weights 號方 that best leconstiucT each poinf； from its ueigti- bor頭 ininimizitig The cost in Equntion (1) by coustrniiied li

5、near fits.Reconstruct with linear weights.°Q1 4 o43. Compwte the vectors 丹 best lecoiistiucted bv the weights "勺， minimizing The quadratic form iti EquntlQii (2) by its bottom nouzei'o eigeiivectoi s*o°。O nOO二OQ Map to embedded coordinates.圖 2 LLE算法流程O Xi.k個近鄰點。把相對于所求樣本點距離個近鄰點。k是一

6、個預(yù)先給定值。Sam沖min鞏屛）二丫召-一J-l算法的第一步是計算出每個樣本點的 最近的k個樣本點規(guī)定為所求樣本點的T.Roweis和Lawrenee K.Saul算法采用的是歐氏距離，則減輕復(fù)雜的計算。然 而本文是假定高維空間中的數(shù)據(jù)是非線性分布的，采用了diijstra 距離。Dijkstra 距離是一種測地距離，它能夠保持樣本點之間的曲面特性，在ISOMA P算法中有廣泛的應(yīng)用。針對樣本點多的情況，普通的dijkstra 算法不能滿足LLE 算法的要求。LLE算法的第二步是計算出樣本點的局部重建權(quán)值矩陣。這里定義一個誤差 函數(shù)，如下所示：其中奇上）為勺的k個近鄰點，吋是無與忑&

7、之間的權(quán)值，且要滿 足條件：一：1呵亠1。這里求取W矩陣，需要構(gòu)造一個局部協(xié)方差矩陣Jt將上式與-兒】w; = 1相結(jié)合，并采用拉格朗日乘子法，即可求出局部最優(yōu)化 重建權(quán)值矩陣：kK-1Wj = nrnEjt !在實際運算中，©可能是一個奇異矩陣，此時必須正則化如下所示:其中r是正則化參數(shù)，I是一個kxk的單位矩陣。LLE算法的最后一步是將所有的樣本點映射到低維空間中。映射條件滿足如下所示：min £（） =二其中，鞏F）為損失函數(shù)值，戸是召的輸出向量，片° =12悶是戸的k個近鄰 點，且要滿足兩個條件，即：M fl 1T JZL-iX = °，石xA/

8、i =1其中I是璃5的單位矩陣。這里的和;0 = 12#N）可以存儲在MxM的稀疏矩陣W/中，當是兀的近鄰點時，硏廣吋，否則，吧廣°。則損失函數(shù)可重寫為:Z Nj-l其中M是一個MxM的對稱矩陣，其表達式為:M=要使損失函數(shù)值達到最小，則取丫為M的最小m個非零特征值所對應(yīng)的特征向 量。在處理過程中，將M的特征值從小到大排列，第一個特征值幾乎接近于零， 那么舍去第一個特征值。通常取第2楙+ 1間的特征值所對應(yīng)的特征向量作為輸 出結(jié)果。2 SLLE算法Dick和Robert提出一種針對有監(jiān)督的LLE算法，即SLLE傳統(tǒng)的LLE算法 在第一步時是根據(jù)樣本點間的歐氏距離來尋找 個近鄰點。而S

9、LLE在處理這一步 時，增加了樣本點的類別信息。SLLE的其余步驟同LLE算法是一致的。SLLE算法在計算點與點之間的距離時，采用如下公式:其中£/是計算后的距離；D在本文中是定義為dijkstra 距離；m捉(D)是表示類 與類之間的最大dijkstra 距離；取0或者1,當兩點屬于同類時，菖取為0， 否則取1; 是控制點集之間的距離參數(shù)，是一個經(jīng)驗參數(shù)。當o取為零 時，此時的SLLE和LLE算法相同。3 SLLE參數(shù)設(shè)置SLLE算法中有4個參數(shù)需要設(shè)置，即近鄰點的個數(shù) k、輸出維數(shù)m、正則 化參數(shù)r和距離參數(shù)氐。k的選取在算法中起到關(guān)鍵因素，如果k取值太大，LLE 不能體現(xiàn)局部特

10、性，使得LLE算法趨向于PCA算法；反之取得太小，LLE便不能 保持樣本點在低維空間中的拓撲結(jié)構(gòu)。 本文中k沒有作出進一步的改進，相當于 一個經(jīng)驗參數(shù)，預(yù)先取值為12。本文的輸出維數(shù)m采用類似于PCA算法求取固有維數(shù)。SLLE算法在計算每 個樣本點的重建權(quán)值矩陣時，都要構(gòu)造一個局部協(xié)方差矩陣可以通過如下式 子求出該樣本點的輸出維數(shù)。其中忑為。'的特征值，且以從大到小排列。對于每個樣本點，都需要計算一次樣 本點的輸出維數(shù)。所有點輸出維數(shù)的平均值規(guī)定為樣本的輸出維數(shù)。正則化參數(shù)r可以取一個特別小的值，或者采用自適應(yīng)調(diào)整的方法得到。 采取自適應(yīng)調(diào)整的辦法來選定r的值。對于每個樣本點，都要校正

11、爐矩陣，此時 正則化參數(shù)采取如下式子：Jc fn J二Id其中4,為©的最小的上-個特征值。距離參數(shù)0是一個經(jīng)驗參數(shù)。在求取點間的距離時，可以增加不同類點之 間的距離，從而增加類類之間的距離。4 SLLE的測數(shù)數(shù)據(jù)處理設(shè)訓(xùn)練樣本為疋皿川，訓(xùn)練樣本的輸出為Fizi，&為訓(xùn)練樣本的維數(shù)，m為 訓(xùn)練樣本的輸出維數(shù)，N為訓(xùn)練樣本的個數(shù)。設(shè)*'為測試樣本的集合。主要算法 分為三步：(1)選取一個 g 宀* X，將x加入X矩陣中，則X變?yōu)樾腗 + 1)的矩陣。 在訓(xùn)練樣本中尋找可閑的k個近鄰點，此時還時采用dijkstra 距離，但是不能 像SLLE算法那樣加上樣本點的類別信息。

12、(2)求可中與其k個近鄰點間的權(quán)值系數(shù)，且滿足以下條件:2 .J-1且Pw佇J-1其中=是1的k個近鄰點，叩7"是與其近鄰點lt之間的權(quán)值。(3)計算心+1的輸出向量丹5：jt加1 = Y和7"畑】J其中丿押+叮為盂N+U的輸出向量。參考文獻:1 SamT. Roweis and Lawrenee K. Saul. Nonlinear Dimensionality Reduction by Locally Linear Embeddi ng, Scie nee, Dec 22 2000:2323-23262 Lawre nee K.Saul, Sam T.Roweis. A

13、n In troducti on to Locally LinearEmbedd ing. htt p: //roweis/lle/, 20013 Lawre nee K.Saul, Sam T.Roweis. Thi nk Globally, Fit Locally:Unsup ervised Lear ning of Low Dime nsional Mani folds. Journal of Mach ine Learni ng Research 4(2003) 119-1554 Dick de Ridder, Olga Kouropteva, Ol

14、eg Okun, et al. Supervised locally lin ear embedd ing. Artificial Neural Networks and Neural In formatio nProcess in g, ICANN/ICONIP 2003 P roceedi ngs, Lecture Notes in Compu ter Scie nee 2714, Sprin ger, 333-341 Kouro pteva O, Oku n O & Pietik? inen M. Classificatio n of han dwritte n digits using sup ervised locally lin ear embedd ing algorithm and support vector machine. Proc. of the 11th European Symposium