局部線性嵌入算法及其穩(wěn)定性實現(xiàn)

夏潔云

（廣東工程職業(yè)技術(shù)學(xué)院）

0 引言

局部線性嵌入（locally linear embedding，LLE）算法[1-2]基于簡單的幾何直覺，由于計算簡單，性能良好，被廣泛應(yīng)用[3-5]。近些年來對LLE算法的改進(jìn)有很多，如改進(jìn)距離測度的有：加權(quán)距離[6]、核相關(guān)變換[7]；改進(jìn)權(quán)重計算的有：局部線性變換[8-9]、多權(quán)重組合方法[10-11]；改進(jìn)嵌入計算的有：減少孤立子影響算法[12-13]、展開流形算法[14]等。雖然這些改進(jìn)算法對LLE算法的性能有很大的提升，但對于LLE算法關(guān)鍵步驟的理論實現(xiàn)卻相對較少，并且對 LLE算法在非均勻采樣條件下，對鄰域點數(shù)以及數(shù)據(jù)采樣點數(shù)的穩(wěn)定性實現(xiàn)也很少。本文對 LLE算法的關(guān)鍵步驟進(jìn)行理論實現(xiàn)，同時在各種經(jīng)典流形上對 LLE算法的實際降維效果進(jìn)行驗證分析，并在非均勻采樣條件下，驗證并討論 LLE算法對鄰域點數(shù)和采樣點數(shù)的穩(wěn)定性。

1 LLE算法

給 定 一 個 數(shù) 據(jù) 點 集 XN×M， 這 里表示一個N×M的矩陣，其中 XN×M的每一行表示某個數(shù)據(jù)點的各個坐標(biāo)。假定這些數(shù)據(jù)點是采樣自一個潛在的流形。如果這些數(shù)據(jù)是充足的（即對流形是一個充分的采樣），即使不知道這個潛在的流形是什么樣，但可以認(rèn)為，對于每一個數(shù)據(jù)點，它與其鄰點所形成的局部區(qū)域（通常稱為一個 patch）是線性的?？捎靡粋€數(shù)據(jù)點的鄰點線性組合來逼近它（重構(gòu)這個數(shù)據(jù)點）。

重構(gòu)誤差使用式(1)度量：

其中，權(quán)重 wij反映了第j個數(shù)據(jù)點對重構(gòu)第i個數(shù)據(jù)點的貢獻(xiàn)。

重構(gòu)權(quán)重W反映了數(shù)據(jù)的內(nèi)在屬性，且對于旋轉(zhuǎn)、尺度、平移等變換具有不變性。據(jù)此，對數(shù)據(jù)在原高維空間的局部幾何關(guān)系的刻畫同樣適用于→流形上的patch。即在M 維空間里用→于重構(gòu)數(shù)據(jù)點的權(quán)重 wij與在m維空間里重構(gòu)權(quán)重一樣。LLE基于上述思想，構(gòu)造一個能夠保持鄰居關(guān)系的→映射。算法的最后結(jié)果是，每一個高維的觀測數(shù)據(jù)都被映射到一個低維表示。數(shù)據(jù)的低維表示通過式(2)求得：

式(2)與式(1)一樣，都→是基于重構(gòu)誤差。不同的是，這里是固定W而求得的坐標(biāo)的最優(yōu)解。Y表示一個N×m的矩陣，其中Y的每一行表示某個數(shù)據(jù)點在低維空間的坐標(biāo)。

2 算法關(guān)鍵步驟

對 LLE算法兩個關(guān)鍵步驟的理論基礎(chǔ)進(jìn)行分析和推導(dǎo)，從理論層面實現(xiàn)LLE算法的具體過程。

2.1 權(quán)重構(gòu)建

通過正則化可得：

一階微分可得：

2.2 嵌入向量

3 LLE算法實驗

LLE算法的降維效果在3個比較經(jīng)典的人工流形數(shù)據(jù)集Swiss roll、Two peaks和Punched sphere上進(jìn)行驗證，其中Punched sphere為非均勻采樣數(shù)據(jù)集。另外，在Punched sphere上又分別驗證LLE算法在非均勻數(shù)據(jù)集上對于鄰域點選擇和數(shù)據(jù)點采樣的穩(wěn)定性。

3.1 LLE算法的實際降維效果

圖 1～圖 3分別為 LLE算法在 Swiss roll、Two peaks和Punched sphere上的數(shù)據(jù)降維效果。數(shù)據(jù)集統(tǒng)一采樣1000個數(shù)據(jù)點，采樣8個點的數(shù)據(jù)鄰域。

由圖1～圖3 可以看出，LLE算法具有很好的非線性數(shù)據(jù)降維效果。在有效降低高維數(shù)據(jù)的同時還能夠有效保持?jǐn)?shù)據(jù)點之間的鄰域關(guān)系不變。從圖像上數(shù)據(jù)點的分布情況可以看到，降維之前相對較近的數(shù)據(jù)點，降維之后依然保持近鄰關(guān)系。圖1(a)為三維的卷曲瑞士卷曲面，圖1(b)為LLE算法的降維效果圖，雖然不能將瑞士卷完全展開成平面，但已經(jīng)降維為二維圖形；圖2 (a)為三維空間的雙極曲面，圖2 (b)為LLE算法的降維效果圖，從圖形上可以看到 LLE算法完全將雙極曲面展開，這表明了 LLE算法的良好數(shù)據(jù)降維效果；圖3 (a)為非均勻采樣的三維半球面，圖3 (b)為LLE算法的降維效果。結(jié)果表明：LLE算法不僅能夠有效對高維數(shù)據(jù)進(jìn)行降維，還能完整地保存高維數(shù)據(jù)點之間的鄰域關(guān)系。

圖1 LLE算法在Swiss roll上的降維效果

圖2 LLE算法在Two peaks上的降維效果

圖3 LLE算法在Punched sphere上的降維效果

3.2 LLE算法對于鄰域點個數(shù)以及數(shù)據(jù)采樣點數(shù)的穩(wěn)定性

本節(jié)實驗驗證 LLE算法對于鄰域點個數(shù)和采樣點數(shù)的穩(wěn)定性。

圖 4(a)、(b)、(c)分別為 LLE 算法在Punched sphere上采樣5、10、15個鄰域點，1000個數(shù)據(jù)點的降維效果。實驗結(jié)果可以看出，當(dāng)鄰域點個數(shù)從5變化到15時，LLE算法對于非均勻采樣數(shù)據(jù)集的降維效果一直優(yōu)良，鄰域點的個數(shù)對于 LLE算法的降維效果沒有太大的影響。因此，在適當(dāng)?shù)泥徲虼笮》秶鷥?nèi)，LLE算法都可以保持較好的數(shù)據(jù)降維效果。這表明：LLE算法在一定程度上具有對于數(shù)據(jù)點鄰域選擇的穩(wěn)定性。

圖 5(a)、(b)、(c)為 LLE 算法在 Punched sphere上分別采樣200、1000、2000個點，10個鄰域點的降維效果。

圖5 (a) 采樣點為200時的降維效果

圖5 LLE算法在Punched sphere上的降維效果

實驗結(jié)果可以看出，當(dāng)采樣點數(shù)從 200變化到2000時，LLE算法對于非均勻采樣數(shù)據(jù)集始終保持良好的數(shù)據(jù)降維效果，數(shù)據(jù)點采樣的個數(shù)對于 LLE算法的降維效果沒有太大影響。因此，對于非均勻數(shù)據(jù)集，無論是稀疏采樣還是密集采樣，LLE算法都具有良好的數(shù)據(jù)降維效果。這表明：LLE算法對于數(shù)據(jù)點的采樣個數(shù)有很好的穩(wěn)定性。

本文在非均勻采樣數(shù)據(jù)集Punched sphere上分別驗證了 LLE算法對于鄰域點數(shù)以及數(shù)據(jù)采樣點數(shù)的雙重穩(wěn)定性。圖4、圖5的實驗結(jié)果完全驗證了LLE算法的穩(wěn)定特性。實驗表明：LLE算法是一種非常有效的非線性數(shù)據(jù)降維算法。該算法不僅對于均勻采樣數(shù)據(jù)集有良好的降維效果，同時對于非均勻采樣數(shù)據(jù)集也有著優(yōu)良的性能。

4 結(jié)論

LLE算法是一種非常有效的非線性數(shù)據(jù)降維方法，有廣泛的應(yīng)用。它主要是通過兩次局部最小化實現(xiàn)對高維數(shù)據(jù)的降維處理。本文實現(xiàn)了 LLE算法的兩個局部最小化的理論推導(dǎo)過程，完善了 LLE算法的理論基礎(chǔ)。同時，對 LLE算法的非線性降維效果進(jìn)行了實際驗證，分別在均勻采樣和非均勻采樣的數(shù)據(jù)流形上對 LLE算法進(jìn)行實際驗證。另外，在非均勻采樣數(shù)據(jù)集上，分別驗證了 LLE算法對于鄰域點選擇和數(shù)據(jù)點采樣的穩(wěn)定性。通過一系列的分析探討，證實 LLE算法確實是一種非常有效的非線性數(shù)據(jù)降維算法。

[1]S T Roweis,L K Saul. Nonlinear dimensionality reduction by locally linear embedding[J]. Science,2000,290: 2323-2326.

[2]L K Saul,S T Rowels. Think globally,fit locally: Unsupervised learning of low dimensional manifolds[J]. Journal of Machine Learning Research,2003,4: 119-155.

[3]Wang Y,Wu Y. Complete neighborhood preserving embedding for face recognition[J].Pattern Recognition,2010,43(3):1008-1015.

[4]Yan Y,Zhang Y .Discriminant projection embedding for face and palmprint recognition[J]. Neurocomputing,2008,71(16–18):3534-3543.

[5]Ying H P,Andrew Teoh B J,Wong E K. Neighbourhood discriminant embedding in face recognition[J]. IEICE Electron Express,2008,5(24):1036-1041.

[6]Pan Y,Ge S S,Al Mamun A. Weighted locally linear embedding for dimension reduction[J]. Pattern Recognitn,2009,42(5):798-811.

[7]Wen Guihua,Jiang Lijun,Wen Jun. Kernel relative transformation with applications to enhancing locally linear embedding[C]. International Joint Conference on Neural Networks,2008:3401-3406.

[8]Goldberg Y,Ritov Y. LDR-LLE: LLE with low-dimensional neighborhood representation[J]. ISVC,2008,1: 43-54.

[9]Hou C,Wang J,Wu Y,Yi D. Local linear transformation embedding[J]. Neurocomputing,2009,72(10-12):2368-2378.

[10]Wang J,Zhang Z. Nonlinear embedding preserving multiple local-linearities[J]. Pattern Recognition,2010,43(4):1257-1268.

[11]Zhang Zhenyue,Wang Jiang. Modified locally linear embedding using multiple weights[C]Advances in Neural Information Processing Systems,2007,19:1593-1600.

[12]Hong Chang,Dit-Yan Yeung. Robust locally linear embedding[J]. Pattern Recognit,2006,39(6):1053-1065.

[13]Zeng Xianhua,Luo Siwei. Generalized locally linear embedding based on local reconstruction similarity[C]. Fifth International Conference on Fuzzy Systems and Knowledge Discovery,2008:305-309.

[14]Hou Chenping,Zhang Changshui,Wu Yi,et al. Stable local dimensionality reduction approaches[J]. Pattern Recognit,2009,42(9): 2054-2066.