LLE(局部線性嵌入)_第1頁
LLE(局部線性嵌入)_第2頁
LLE(局部線性嵌入)_第3頁
LLE(局部線性嵌入)_第4頁
LLE(局部線性嵌入)_第5頁
已閱讀5頁,還剩11頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論