LLE(局部線性嵌入)

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

2、是線性的，也就是說一個(gè)數(shù)據(jù)可以由它鄰域的幾個(gè)樣本來線性表示。 假設(shè)有樣本 ，我們?cè)谠摌颖镜脑监徲蛑杏肒近鄰的思想找到其中的K個(gè)樣本 ，假設(shè) 可以由 線性表示，即： 其中， 為權(quán)重系數(shù)，我們通過LLE降維后，希望 在低維空間對(duì)應(yīng)的投影 和 對(duì)應(yīng)的投影 也盡量保持同樣的線性關(guān)系，即： 從上面看出，線性關(guān)系只在樣本附近起作用，離樣本遠(yuǎn)的樣本對(duì)局部樣本的線性關(guān)系沒有影響，大大降低了降維的難度。1x132,.,xkxx1x132,.,xkxx1113132121.xkkxwxwxw111312,.,wkww1x1x132,.,xkxx121x,.,x,xk1113132121xw.xwxwxkk LL

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

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

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

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

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