摘  要: 介紹了局部線性嵌套和等距映射兩種最基本的非線性降維方法,對(duì)比測試了兩種降維方法在不同參數(shù)下的執(zhí)行效果與效率，總結(jié)了兩種降維方法所適合的數(shù)據(jù)特點(diǎn)，并應(yīng)用于圖像識(shí)別中，比較了兩者在圖像識(shí)別中的識(shí)別率。
關(guān)鍵詞： 非線性降維;流形學(xué)習(xí); 局部線性嵌套; 等距映射; 人臉識(shí)別

    流形的概念最早是由德國數(shù)學(xué)家黎曼在1854年提出的，它是微分幾何學(xué)的基礎(chǔ)[1]。流形本質(zhì)上是局部可坐標(biāo)化的拓?fù)淇臻g,可以看作是歐式空間的非線性推廣。
1 局部線性嵌入算法
    局部線性嵌入算法LLE(Locally Linear Embedding)是ROWEIS S T和SAUL L K于2000年提出的一種非線性降維方法[2]，該方法主要認(rèn)為在局部意義下，數(shù)據(jù)結(jié)構(gòu)是線性的，或者說局部意義下的點(diǎn)是在一個(gè)超平面上，故可以使用任意一點(diǎn)的鄰近點(diǎn)的線性組合來表示該點(diǎn)。對(duì)于一組具有嵌套流形的數(shù)據(jù)集，在嵌套空間與內(nèi)在低維空間局部鄰域間的點(diǎn)的關(guān)系應(yīng)該保持不變。即在嵌套空間，每個(gè)采樣點(diǎn)可以用它的近鄰點(diǎn)線性表示，在低維空間中保持每個(gè)鄰域中的權(quán)值不變，重構(gòu)原數(shù)據(jù)使重構(gòu)誤差最小。
    通過最小化這種線性表示的誤差，可以建立如下數(shù)學(xué)模型：
  

    該算法有兩個(gè)待定的參數(shù)k和d，由于重構(gòu)成本函數(shù)同時(shí)最小化得到的最優(yōu)權(quán)值應(yīng)該遵循對(duì)稱性，因此每個(gè)點(diǎn)的鄰近權(quán)值在進(jìn)行平移、伸縮和旋轉(zhuǎn)變換時(shí)保持不變[3]。
2 等距映射
    等距映射算法是由TENENBAUM J B等人于2000年提出的一種非線性降維方法[4]。該方法試圖保持?jǐn)?shù)據(jù)內(nèi)部幾何特征，從而獲得流形上數(shù)據(jù)之間的測地距離。與傳統(tǒng)的非線性降維方法所不同的是，利用等距映射方法可以求得高維數(shù)據(jù)的本征維數(shù)，將本征維數(shù)較低的高維數(shù)據(jù)投影到低維空間中去[5]，使得高維數(shù)據(jù)可以直接觀察。等距映射有兩個(gè)假設(shè)：(1)高維數(shù)據(jù)所在的低維流形與歐式空間的一個(gè)子集是整體等距的； (2)與數(shù)據(jù)所在的流形等距的歐式空間的子集是一個(gè)凸集。

   

    實(shí)驗(yàn)3
    使用MATLAB軟件用siomap方法對(duì)scurve數(shù)據(jù)集進(jìn)行數(shù)據(jù)降維,分別選擇數(shù)據(jù)點(diǎn)個(gè)數(shù)為800、1 200，降維以后的維數(shù)為2，在構(gòu)造鄰域圖時(shí)選取k=2、6、12。降低維數(shù)后的仿真結(jié)果如圖3所示， 數(shù)據(jù)降維用時(shí)對(duì)比如表3所示。　　　
    實(shí)驗(yàn)4
    使用MATLAB軟件用LLE方法對(duì)scurve數(shù)據(jù)集進(jìn)行降維,分別選擇數(shù)據(jù)點(diǎn)個(gè)數(shù)為800、1 200，降維后的維數(shù)為2，在構(gòu)造鄰域圖時(shí)選取k=6、8、12。降低維數(shù)后的仿真結(jié)果如圖4所示，數(shù)據(jù)降維用時(shí)對(duì)比如表4所示。
4 結(jié)果分析
    實(shí)驗(yàn)1中，從圖1可以看出樣本點(diǎn)的分布及其鄰域點(diǎn)的取值對(duì)isomap的降維結(jié)果會(huì)產(chǎn)生比較大的影響[7]。實(shí)驗(yàn)2中，隨著鄰域點(diǎn)k取值的增加，圖2有著明顯的變化，說明隨著鄰域k的增加,LLE所得的結(jié)果明顯增強(qiáng)。在樣本點(diǎn)稀疏的情況下，鄰域k的取值對(duì)于LLE降維效果有比較明顯的影響，因而選取合適的鄰域取值對(duì)于LLE降維有非常重要的作用。對(duì)比實(shí)驗(yàn)2和實(shí)驗(yàn)4可知，鄰域k的選擇對(duì)于不同數(shù)據(jù)集的選取是不同的。LLE算法中的待定參數(shù)很少(k和d)，從圖3可以看出，隨著樣本鄰域選取的增加，會(huì)把其他較遠(yuǎn)點(diǎn)一起納入，從而造成結(jié)果的誤差，說明鄰域的選取對(duì)于實(shí)驗(yàn)有著直接的影響。

    通過對(duì)比實(shí)驗(yàn)運(yùn)行的時(shí)間會(huì)發(fā)現(xiàn)，isomap所用時(shí)間遠(yuǎn)遠(yuǎn)大于LLE。其中主要原因是計(jì)算歐式距離矩陣花費(fèi)時(shí)間比較長，計(jì)算賦權(quán)無向圖運(yùn)算量比較龐大，用多維尺度方法（MDS）時(shí)會(huì)用到大量的矩陣運(yùn)算，對(duì)于每一個(gè)不同的數(shù)據(jù)集，需要重新計(jì)算距離矩陣等，算法復(fù)雜度比較高，而LLE運(yùn)算量相對(duì)較少。
    isomap算法計(jì)算圖上兩點(diǎn)間的最短距離, 執(zhí)行起來比較慢，該方法適用于學(xué)習(xí)內(nèi)部平坦的低維流形, 不適于學(xué)習(xí)有較大內(nèi)在曲率的流形。LLE算法可以學(xué)習(xí)任意維數(shù)的低維流形，每個(gè)點(diǎn)的近鄰權(quán)值在平移、旋轉(zhuǎn)和伸縮變換下是保持不變的。在計(jì)算耗時(shí)上，isomap遠(yuǎn)遠(yuǎn)大于LLE。
參考文獻(xiàn)
[1] 王澤杰.兩類非線性降維流形學(xué)習(xí)算法的比較分析[J].上海工程技術(shù)大學(xué)學(xué)報(bào)，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] 趙連偉，羅四維，趙艷敞.高維數(shù)據(jù)的低維嵌入及嵌入維數(shù)研究[J].軟件學(xué)報(bào)，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] 王靖.流形學(xué)習(xí)的理論與方法研究[D].杭州：浙江大學(xué), 2006.
[6] 孫明明.流形學(xué)習(xí)理論與算法研究[D].南京：南京理工大學(xué), 2007.
[7] 劉小明.數(shù)據(jù)降維及分類中的流形學(xué)習(xí)研究[D].杭州：浙江大學(xué),2007.