摘 要: 介紹了局部線性嵌套和等距映射兩種最基本的非線性降維方法,對比測試了兩種降維方法在不同參數下的執行效果與效率，總結了兩種降維方法所適合的數據特點，并應用于圖像識別中，比較了兩者在圖像識別中的識別率。
關鍵詞： 非線性降維;流形學習; 局部線性嵌套; 等距映射; 人臉識別
流形的概念最早是由德國數學家黎曼在1854年提出的，它是微分幾何學的基礎[1]。流形本質上是局部可坐標化的拓撲空間,可以看作是歐式空間的非線性推廣。
1 局部線性嵌入算法
局部線性嵌入算法LLE(Locally Linear Embedding)是ROWEIS S T和SAUL L K于2000年提出的一種非線性降維方法[2]，該方法主要認為在局部意義下，數據結構是線性的，或者說局部意義下的點是在一個超平面上，故可以使用任意一點的鄰近點的線性組合來表示該點。對于一組具有嵌套流形的數據集，在嵌套空間與內在低維空間局部鄰域間的點的關系應該保持不變。即在嵌套空間，每個采樣點可以用它的近鄰點線性表示，在低維空間中保持每個鄰域中的權值不變，重構原數據使重構誤差最小。
通過最小化這種線性表示的誤差，可以建立如下數學模型：
該算法有兩個待定的參數k和d，由于重構成本函數同時最小化得到的最優權值應該遵循對稱性，因此每個點的鄰近權值在進行平移、伸縮和旋轉變換時保持不變[3]。
2 等距映射
等距映射算法是由TENENBAUM J B等人于2000年提出的一種非線性降維方法[4]。該方法試圖保持數據內部幾何特征，從而獲得流形上數據之間的測地距離。與傳統的非線性降維方法所不同的是，利用等距映射方法可以求得高維數據的本征維數，將本征維數較低的高維數據投影到低維空間中去[5]，使得高維數據可以直接觀察。等距映射有兩個假設：(1)高維數據所在的低維流形與歐式空間的一個子集是整體等距的； (2)與數據所在的流形等距的歐式空間的子集是一個凸集。
實驗3
使用MATLAB軟件用siomap方法對scurve數據集進行數據降維,分別選擇數據點個數為800、1 200，降維以后的維數為2，在構造鄰域圖時選取k=2、6、12。降低維數后的仿真結果如圖3所示， 數據降維用時對比如表3所示。
實驗4
使用MATLAB軟件用LLE方法對scurve數據集進行降維,分別選擇數據點個數為800、1 200，降維后的維數為2，在構造鄰域圖時選取k=6、8、12。降低維數后的仿真結果如圖4所示，數據降維用時對比如表4所示。
4 結果分析
實驗1中，從圖1可以看出樣本點的分布及其鄰域點的取值對isomap的降維結果會產生比較大的影響[7]。實驗2中，隨著鄰域點k取值的增加，圖2有著明顯的變化，說明隨著鄰域k的增加,LLE所得的結果明顯增強。在樣本點稀疏的情況下，鄰域k的取值對于LLE降維效果有比較明顯的影響，因而選取合適的鄰域取值對于LLE降維有非常重要的作用。對比實驗2和實驗4可知，鄰域k的選擇對于不同數據集的選取是不同的。LLE算法中的待定參數很少(k和d)，從圖3可以看出，隨著樣本鄰域選取的增加，會把其他較遠點一起納入，從而造成結果的誤差，說明鄰域的選取對于實驗有著直接的影響。
通過對比實驗運行的時間會發現，isomap所用時間遠遠大于LLE。其中主要原因是計算歐式距離矩陣花費時間比較長，計算賦權無向圖運算量比較龐大，用多維尺度方法（MDS）時會用到大量的矩陣運算，對于每一個不同的數據集，需要重新計算距離矩陣等，算法復雜度比較高，而LLE運算量相對較少。
isomap算法計算圖上兩點間的最短距離, 執行起來比較慢，該方法適用于學習內部平坦的低維流形, 不適于學習有較大內在曲率的流形。LLE算法可以學習任意維數的低維流形，每個點的近鄰權值在平移、旋轉和伸縮變換下是保持不變的。在計算耗時上，isomap遠遠大于LLE。
參考文獻
[1] 王澤杰.兩類非線性降維流形學習算法的比較分析[J].上海工程技術大學學報，2008,22(1)：54-59.
[2] ROWEIS S T, SAUL L K. Nonlinear dimensionality reducation by locally linear embedding[J]. Science，2000,26(8): 2323-2326.
[3] 趙連偉，羅四維，趙艷敞.高維數據的低維嵌入及嵌入維數研究[J].軟件學報，2005,12(8)：1423-1430.
[4] REINHARD K,NIRANJAN M. Subspace models for speech transitions using principal curves[J].Proceedings of Institute of Acoustics,1998:53-60
[5] 王靖.流形學習的理論與方法研究[D].杭州：浙江大學, 2006.
[6] 孫明明.流形學習理論與算法研究[D].南京：南京理工大學, 2007.
[7] 劉小明.數據降維及分類中的流形學習研究[D].杭州：浙江大學,2007.