局部線性嵌入算法及其穩定性實現

夏潔云

（廣東工程職業技術學院）

0 引言

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

1 LLE算法

給 定 一 個 數 據 點 集 XN×M， 這 里表示一個N×M的矩陣，其中 XN×M的每一行表示某個數據點的各個坐標。假定這些數據點是采樣自一個潛在的流形。如果這些數據是充足的（即對流形是一個充分的采樣），即使不知道這個潛在的流形是什么樣，但可以認為，對于每一個數據點，它與其鄰點所形成的局部區域（通常稱為一個 patch）是線性的。可用一個數據點的鄰點線性組合來逼近它（重構這個數據點）。

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

其中，權重 wij反映了第j個數據點對重構第i個數據點的貢獻。

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

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

2 算法關鍵步驟

對 LLE算法兩個關鍵步驟的理論基礎進行分析和推導，從理論層面實現LLE算法的具體過程。

2.1 權重構建

通過正則化可得：

一階微分可得：

2.2 嵌入向量

3 LLE算法實驗

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

3.1 LLE算法的實際降維效果

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

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

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

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

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

3.2 LLE算法對于鄰域點個數以及數據采樣點數的穩定性

本節實驗驗證 LLE算法對于鄰域點個數和采樣點數的穩定性。

圖 4(a)、(b)、(c)分別為 LLE 算法在Punched sphere上采樣5、10、15個鄰域點，1000個數據點的降維效果。實驗結果可以看出，當鄰域點個數從5變化到15時，LLE算法對于非均勻采樣數據集的降維效果一直優良，鄰域點的個數對于 LLE算法的降維效果沒有太大的影響。因此，在適當的鄰域大小范圍內，LLE算法都可以保持較好的數據降維效果。這表明：LLE算法在一定程度上具有對于數據點鄰域選擇的穩定性。

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

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

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

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

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

4 結論

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

[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.