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

LLE及其改良算法介紹Locallylinearembedding(LLE)(SamT.RoweisandLawrenceK.Saul,2000)以及Supervisedlocallylinearembedding(SLLE)(DickandRobert,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ù)在二維空間中仍能保持相對(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è)封閉的球面上，LLE那么不能將它映射到二維空間，且不能保持原有的數(shù)據(jù)流形。那么我們?cè)谔幚頂?shù)據(jù)中，首先假設(shè)數(shù)據(jù)不是分布在閉合的球面或者橢球面上。圖1非線性降維實(shí)例：B是從A中提取的樣本點(diǎn)〔三維〕，通過(guò)非線性降維

算法〔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)域中。1LLE算法

LLE算法可以歸結(jié)為三步:(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所示。圖2LLE算法流程算法的第一步是計(jì)算出每個(gè)樣本點(diǎn)的k個(gè)近鄰點(diǎn)。把相對(duì)于所求樣本點(diǎn)距離最近的k個(gè)樣本點(diǎn)規(guī)定為所求樣本點(diǎn)的個(gè)近鄰點(diǎn)。k是一個(gè)預(yù)先給定值。SamT.Roweis和LawrenceK.Saul算法采用的是歐氏距離，那么減輕復(fù)雜的計(jì)算。然而本文是假定高維空間中的數(shù)據(jù)是非線性分布的，采用了diijstra距離。Dijkstra距離是一種測(cè)地距離，它能夠保持樣本點(diǎn)之間的曲面特性，在ISOMAP算法中有廣泛的應(yīng)用。針對(duì)樣本點(diǎn)多的情況，普通的dijkstra算法不能滿足LLE算法的要求。LLE算法的第二步是計(jì)算出樣本點(diǎn)的局部重建權(quán)值矩陣。這里定義一個(gè)誤差函數(shù)，如下所示：其中為的k個(gè)近鄰點(diǎn)，是與之間的權(quán)值，且要滿足條件：。這里求取W矩陣，需要構(gòu)造一個(gè)局部協(xié)方差矩陣。

將上式與相結(jié)合，并采用拉格朗日乘子法，即可求出局部最優(yōu)化重建權(quán)值矩陣：

在實(shí)際運(yùn)算中，可能是一個(gè)奇異矩陣，此時(shí)必須正那么化，如下所示：其中r是正那么化參數(shù)，I是一個(gè)kxk的單位矩陣。LLE算法的最后一步是將所有的樣本點(diǎn)映射到低維空間中。映射條件滿足如下所示：其中，為損失函數(shù)值，是的輸出向量，是的k個(gè)近鄰點(diǎn)，且要滿足兩個(gè)條件，即：其中I是的單位矩陣。這里的可以存儲(chǔ)在的稀疏矩陣W中，當(dāng)是的近鄰點(diǎn)時(shí)，，否那么，。那么損失函數(shù)可重寫為：其中M是一個(gè)的對(duì)稱矩陣,其表達(dá)式為:要使損失函數(shù)值到達(dá)最小,那么取Y為M的最小m個(gè)非零特征值所對(duì)應(yīng)的特征向量。在處理過(guò)程中，將M的特征值從小到大排列，第一個(gè)特征值幾乎接近于零，那么舍去第一個(gè)特征值。通常取第間的特征值所對(duì)應(yīng)的特征向量作為輸出結(jié)果。2SLLE算法Dick和Robert提出一種針對(duì)有監(jiān)督的LLE算法，即SLLE。傳統(tǒng)的LLE算法在第一步時(shí)是根據(jù)樣本點(diǎn)間的歐氏距離來(lái)尋找個(gè)近鄰點(diǎn)。而SLLE在處理這一步時(shí)，增加了樣本點(diǎn)的類別信息。SLLE的其余步驟同LLE算法是一致的。SLLE算法在計(jì)算點(diǎn)與點(diǎn)之間的距離時(shí)，采用如下公式：其中是計(jì)算后的距離；在本文中是定義為dijkstra距離；是表示類與類之間的最大dijkstra距離；取0或者1，當(dāng)兩點(diǎn)屬于同類時(shí)，取為0，否那么取1；是控制點(diǎn)集之間的距離參數(shù)，是一個(gè)經(jīng)驗(yàn)參數(shù)。當(dāng)取為零時(shí)，此時(shí)的SLLE和LLE算法相同。3SLLE參數(shù)設(shè)置SLLE算法中有4個(gè)參數(shù)需要設(shè)置，即近鄰點(diǎn)的個(gè)數(shù)k、輸出維數(shù)m、正那么化參數(shù)r和距離參數(shù)。k的選取在算法中起到關(guān)鍵因素，如果k取值太大，LLE不能表達(dá)局部特性，使得LLE算法趨向于PCA算法；反之取得太小，LLE便不能保持樣本點(diǎn)在低維空間中的拓?fù)浣Y(jié)構(gòu)。本文中k沒(méi)有作出進(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)整的方法得到。當(dāng)采取自適應(yīng)調(diào)整的方法來(lái)選定r的值。對(duì)于每個(gè)樣本點(diǎn)，都要校正矩陣，此時(shí)正那么化參數(shù)采取如下式子：其中為的最小的個(gè)特征值。

距離參數(shù)是一個(gè)經(jīng)驗(yàn)參數(shù)。在求取點(diǎn)間的距離時(shí)，可以增加不同類點(diǎn)之間的距離，從而增加類類之間的距離。4SLLE的測(cè)數(shù)數(shù)據(jù)處理設(shè)訓(xùn)練樣本為，訓(xùn)練樣本的輸出為，為訓(xùn)練樣本的維數(shù)，m為訓(xùn)練樣本的輸出維數(shù)，N為訓(xùn)練樣本的個(gè)數(shù)。設(shè)為測(cè)試樣本的集合。主要算法分為三步：〔1〕選取一個(gè)，將x參加X(jué)矩陣中，那么X變?yōu)榈木仃?。在?xùn)練樣本中尋找的k個(gè)近鄰點(diǎn)，此時(shí)還時(shí)采用dijkstra距離，但是不能像SLLE算法那樣加上樣本點(diǎn)的類別信息。〔2〕求與其k個(gè)近鄰點(diǎn)間的權(quán)值系數(shù)，且滿足以下條件：其中是的k個(gè)近鄰點(diǎn)，是與其近鄰點(diǎn)之間的權(quán)值?！?〕計(jì)算的輸出向量：其中為的輸出向量。參考文獻(xiàn)：[1]SamT.RoweisandLawrenceK.Saul.NonlinearDimensionalityReductionbyLocallyLinearEmbedding,Science,Dec222000:2323-2326[2]LawrenceK.Saul,SamT.Roweis.AnIntroductiontoLocallyLinearEmbedding.:///~roweis/lle/,2001[3]LawrenceK.Saul,SamT.Roweis.ThinkGlobally,FitLocally:UnsupervisedLearningofLowDimensionalManifolds.JournalofMachineLearningResearch4(2003)119-155[4]DickdeRidder,OlgaKouropteva,OlegOkun,etal.Supervisedlocallylinearembedding.ArtificialNeuralNetworksandNeuralInformationProcessing,ICANN/ICONIP2003Proceedings,LectureNotesinComputerScience2714,Springer,333-341[5]KouroptevaO,OkunO&Pietik?inenM.Classificationofhandwrittendigitsusingsupervisedlocallylinearembeddingalgorithmandsupportvectormachine.Proc.ofthe11thEuropeanSymposiumonArtificialN