LLE(局部線性嵌入)

1、LLE楊浩LLE的背景意義 傳統(tǒng)的降維方法主要有PCA、LDA。PCA的基本思想是通過線性變換尋找一組最優(yōu)的基，來重構(gòu)原始數(shù)據(jù)樣本，以使重構(gòu)后的樣本與原始樣本誤差最小。LDA是以樣本的可區(qū)分性為主要目標，通過線性變換以達到類內(nèi)的散度最小，類間的散度最大的目的。但是當數(shù)據(jù)集在高維空間呈現(xiàn)高度扭曲時，它們很難發(fā)現(xiàn)嵌入在數(shù)據(jù)集中的非線性結(jié)構(gòu)和恢復內(nèi)在結(jié)構(gòu)。 LLE算法 LLE算法是是流形學習的一種。流形學習方法提供了一種新的研究途徑，它能夠?qū)?shù)據(jù)集中高維數(shù)據(jù)空間進行非線性降維，揭示其中的流形分布。LLE是屬于流形學習的一種。 一個流形降維的過程如下圖：LLE的算法思想 LLE首先假設數(shù)據(jù)在較小的局部

2、是線性的，也就是說一個數(shù)據(jù)可以由它鄰域的幾個樣本來線性表示。 假設有樣本 ，我們在該樣本的原始鄰域中用K近鄰的思想找到其中的K個樣本 ，假設 可以由 線性表示，即： 其中， 為權重系數(shù)，我們通過LLE降維后，希望 在低維空間對應的投影 和 對應的投影 也盡量保持同樣的線性關系，即： 從上面看出，線性關系只在樣本附近起作用，離樣本遠的樣本對局部樣本的線性關系沒有影響，大大降低了降維的難度。1x132,.,xkxx1x132,.,xkxx1113132121.xkkxwxwxw111312,.,wkww1x1x132,.,xkxx121x,.,x,xk1113132121xw.xwxwxkk LL

3、E的推導 對于LLE，首先需要確定鄰域的大小，即需要多少的鄰域樣本來線性表示某個樣本。假設這個值為K,我們可以通過歐式距離來選擇樣本點的K個鄰居。 找到K個鄰近樣本后，需要找到 與K個樣本點的線性關系，也就是找到線性關系中的權重系數(shù)。因此我們可以通過回歸來求權重系數(shù)。假設我們有N個D維樣本 我們用均方差來定義損失函數(shù)：為了后面計算方便，先對系數(shù)進行歸一化限制，即有ix211)(NiKjjijixwxwJx,.x,xN21Kjijw11 LLE算法推導iTjiNiTjiTiNiijiNiKjjijKjiijNiKjjijiNiKjjijiWxxxxWWxxxwxwxwxxwxwJ)()()()(

4、1212111211211ijiiKiiKiiiKjjiijKjjijKjiijWxxwwwxxxxxxxxwxwxw)(.)(2121111ijiNiTjiTiiKiiKiiiKiiiNiiKiiiKiiKiiiiKiiNiKiiiNiijiWxxxxWwwwxxxxxxxxxxxxwwwwwwxxxxxxwwwxxxxxxWxx)()(.)(121212112121212112121 令 則 為 的局部協(xié)方差矩陣 ， 為 的局部重建權值)()(jiTjiixxxxZiiNiTiNiKjjijiWZWxwxwJ1211)(iZixiWixLLE的算法推導 因此，我們最終的目的是使得 取得最小

5、值情況下 的值。 又因為： 可以化簡為根據(jù)約束條件，可以用拉格朗日乘子法：iiNiTiWZWWJ1)(iW11.11.121KiKiiKTiwwwW11Kjjw11)(1KTiiiNiTiWWZWWJ) 11()(L1KTiiiNiTiWWZWW LLE算法推導 對W求導并令其值為0 ,求得 ： （1） 前面已知 ，則 連立（1）式得解得：因為 ，因此可以根據(jù)上述公式，迭代K個近鄰數(shù)據(jù)點，依次可以求得 ，然后在迭代所有的數(shù)據(jù)點，求得W的權重矩陣。01Z2iKiW11 KTiWTiKiWKT1111WKiTKKiiZZW11111)()(jiTjiixxxxZ,.,21iKiiiwwwWLLE算

6、法推導 得到權重矩陣后，將原始的數(shù)據(jù)映射到低維空間中。映射的條件滿足： 此時，權重系數(shù)我們上一步已經(jīng)求得，要求得滿足最小損失函數(shù)條件下的數(shù)據(jù) ,而且滿足以下條件： （1） 其中， 是單位矩陣211)(minNiKjjijiywyYJy,.,y,YyN21Niiy10I1TiNiiyyILLE算法推導T1212)()()(minYWIWIYWIYYWYIYJTNiiiNiii令結(jié)合上述約束條件： TWIWIM)(I0)(min11TiNiiNiiTyyyYMYYJ 根據(jù)拉格朗日乘子法有：對Y進行求導令其為0，得： 根據(jù)矩陣特征值得定義： 設A為n階矩陣，若存在常數(shù) 和n維 非零向量， 使得則 為

7、A的一個特征值， 為 對應的特征向量。 因此， 為M矩陣的特征向量組成的矩陣。)N-()(IYYYMYYLTT-M02M2TTTTTTYMYYYYYxxAxTY 將 帶入到 得: 即：若要求 最小，則 最小，即取M的最小特征值。 TTYY-M)N-()(IYYYMYYLTTNIYL)( -NIYL)()(YLnnnnnnnndnnnnnnnyyymmmmmmmmmmkkkmmmmmmmmmm.,.,.213212222111211213212222111211 SLLE 傳統(tǒng)的LLE在第一步時根據(jù)樣本點間歐式距離來尋找k個近鄰點，而SLLE在處理這一步增加了樣本的類別的信息，SLLE算法的其余步驟與LLE相同。 SLLE在計算點與點之間的距離采用以下兩種方法： 1.第一種是采用以下公式來修正點與點之間的距離公式： 是直接采用歐式距離計算出的距離， 表示類與類之間的最大距離； 取0或者1，當兩個點屬于同一類時 否則 是控制點集之間的距離參數(shù)， ，是一個經(jīng)驗參數(shù)。)max(DDDD)ma