LLE算法及其改進(jìn)算法介紹

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

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

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

4、：（1）尋找每個(gè)樣本點(diǎn)的k個(gè)近鄰點(diǎn)；（2）由每個(gè) 樣本點(diǎn)的近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的局部重建權(quán)值矩陣；（3）由該樣本點(diǎn)的局部重建權(quán)值矩陣和其近鄰點(diǎn)計(jì)算出該樣本點(diǎn)的輸出值。具體的算法流程如圖 2所 7示01, Compute the neiglibois of each data poi】it,焉LLE AUgdklTSI口V2. C ompute the weights 號(hào)方 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個(gè)近鄰點(diǎn)。把相對(duì)于所求樣本點(diǎn)距離個(gè)近鄰點(diǎn)。k是一

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

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

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

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

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

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

12、(2)求可中與其k個(gè)近鄰點(diǎn)間的權(quán)值系數(shù)，且滿足以下條件:2 .J-1且Pw佇J-1其中=是1的k個(gè)近鄰點(diǎn)，叩7"是與其近鄰點(diǎn)lt之間的權(quán)值。(3)計(jì)算心+1的輸出向量丹5：jt加1 = Y和7"畑】J其中丿押+叮為盂N+U的輸出向量。參考文獻(xiàn):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