李燕燕 肖 丹 魏曉峰 王海東

(河北建筑工程學(xué)院，河北 張家口 075024)

0 引 言

隨著信息時代的到來，高維數(shù)據(jù)以更加豐富的形式來描寫著現(xiàn)實世界，并且已深入到各個領(lǐng)域.然而，高維數(shù)據(jù)中包含了大量的冗余信息，并且不容易被人們表示和處理，更無法感知數(shù)據(jù)內(nèi)在的本質(zhì)規(guī)律，所以要在保持原始高維數(shù)據(jù)的本質(zhì)信息的前提下得到高維數(shù)據(jù)的低維表示.在這種背景下，數(shù)據(jù)降維技術(shù)應(yīng)運而生，其實質(zhì)是揭示高維數(shù)據(jù)內(nèi)在的本質(zhì)信息，挖掘出隱藏在高維空間中數(shù)據(jù)的低維本征表示.

在降維的發(fā)展歷程中，首先被提出來的是線性降維方法，線性降維方法是數(shù)據(jù)集在線性結(jié)構(gòu)的假設(shè)下提出的，目的是使得原高維數(shù)據(jù)之間的線性關(guān)系在低維空間中也是保持不變的.現(xiàn)有的線性降維方法有：主成分分析(principal component analysis，簡稱PCA[1])、多維尺度變換(Multidimensional Scaling，簡稱MDS[2]).這些線性降維方法運算簡便、復(fù)雜度低、有利于線性結(jié)構(gòu)的數(shù)據(jù)降維.然而，各個領(lǐng)域中高維數(shù)據(jù)多表現(xiàn)為非線性的，從而又興起了解決高維非線性數(shù)據(jù)的降維方法，流形學(xué)習(xí)作為非線性降維的一種技術(shù)廣泛應(yīng)用于模式識別的各個領(lǐng)域.著名的流形學(xué)習(xí)算法有等規(guī)度映射ISOMAP[3](Isometric Mapping)、局部線性嵌入(Locally linear embedding，LLE[4])等.ISOMAP把任意兩點之間的測地線距離作為流形的幾何描述，能有效地避免短路問題，但是拓?fù)浞€(wěn)定性差，且容易受到流形稀疏的影響.LLE是一種局部優(yōu)化算法，以局部線性信息的重疊來達(dá)到學(xué)習(xí)全局非線性信息的目的.

然而，Isomap在處理稀疏數(shù)據(jù)時，近鄰點的選取很有可能造成“短路”現(xiàn)象，因此，本文通過鄰域選取算法自適應(yīng)的動態(tài)選擇每一個樣本點的鄰域大小，再使用聚類信息來匯聚相似的樣本點，保證了降維后的數(shù)據(jù)具有很好的可分性.實驗結(jié)果表明，將該算法能成功應(yīng)用于手工流形的降維，取得了很好的效果.

1 Isomap算法

1.1 Isomap算法的思想

Isomap的理論框架是MDS，不同之處是對數(shù)據(jù)之間相似性的衡量由原始?xì)W式距離換成了測地線距離，通過這種整體幾何特征的重構(gòu)來最大程度的保持?jǐn)?shù)據(jù)降維前后的整體拓?fù)浣Y(jié)構(gòu).

算法的關(guān)鍵是正確的描述高維非線性空間中樣本點間的距離，它認(rèn)為傳統(tǒng)的歐式距離不能代表樣本點間的實際距離，而沿著數(shù)據(jù)流形區(qū)域分布的測地線距離能夠更好的描述樣本點間的內(nèi)在關(guān)系.由于測地距離一般能夠內(nèi)在地反映流形的本質(zhì)幾何機構(gòu)，所以Isomap通常能有很好的降維效果.Isomap的主要步驟如下：

Step1：構(gòu)建近鄰圖G.主要用k近鄰的方法確定xi鄰域點xj.

Step2：計算近鄰圖G上成對的測地線距離.當(dāng)圖G有邊xixj，設(shè)最短路徑dG(xixj)=d(xi,xj)；否則設(shè)dG(xixj)=∞.則測地距離定義如下：

Step3：用多維尺度變換MDS求解流形的低維表示Y.

1.2 Isomap對稀疏數(shù)據(jù)失效的原因

對Isomap算法的分析可知，Isomap通過近鄰算法構(gòu)建近鄰圖，在數(shù)據(jù)稀疏的情況下，流形上樣本點數(shù)目分布相對分散，k近鄰算法的搜索范圍相對擴大，可能將本不屬于同一流形區(qū)域的點包含在同一近鄰圖中，從而導(dǎo)致短路現(xiàn)象，即流形上本不相鄰的兩個數(shù)據(jù)點成為近鄰點.短路的出現(xiàn)可能使得擬合出的測地線距離嚴(yán)重偏離數(shù)據(jù)流形區(qū)域，難以正確反映高維數(shù)據(jù)的整體拓?fù)浣Y(jié)構(gòu).

2 A-Isomap算法

2.1 算法思想

在數(shù)據(jù)稀疏的情況下，近鄰圖中短路邊的出現(xiàn)是導(dǎo)致算法失效的重要原因，算法CN-Isomap通過對“流形鄰居”的設(shè)定來鑒別和刪除近鄰圖中短路邊[5]，極大地削弱Isomap對鄰域大小的依賴程度，并使其更具拓?fù)浞€(wěn)定性.本文在CN-Isomap算法的基礎(chǔ)上，在近鄰區(qū)內(nèi)進(jìn)行聚類分析，使相似的樣本點匯聚在一起，保證了降維后數(shù)據(jù)具有很好的可分性.

聚類算法：利用k均值聚類后的各類中心以及總體樣本中心信息來構(gòu)建樣本的數(shù)據(jù)可分系數(shù)，來約束測地距離.設(shè)樣本點聚類分類的類別個數(shù)為C，mj為第j類樣本的中心，n(j)為第j類樣本的個數(shù).則第j類樣本點的類內(nèi)平均距離為

(1)

第j類樣本與總體樣本中心的距離為

(2)

m為總體樣本的中心.根據(jù)式(1)和(2)，我們定義樣本點重構(gòu)誤差的近似重構(gòu)系數(shù)為

(3)

2.2 算法的主要步驟

Step1：利用k鄰域法找到樣本點的近鄰點集合.

Step2：構(gòu)建k個樣本點的近鄰圖，并利用“流形鄰居”算法，刪除短路邊.

Step3：在近鄰區(qū)內(nèi)進(jìn)行聚類分析，利用數(shù)據(jù)可分系數(shù)將不同類別的流形分開.

Step4：應(yīng)用最短路徑算法得到任意兩樣本點間的最短路徑距離，用這個距離來估計樣本點間的測地線距離，完成對任意兩點測地線的擬合.

Step5：將這些最短路徑長度作為輸入運行古典MDS算法，完成降維.

3 實驗結(jié)果分析

3.1 手工流形實驗

本實驗采用的是經(jīng)典的Swiss roll手工流形數(shù)據(jù)集，近鄰點k=6，利用相同顏色的點標(biāo)識近鄰狀態(tài).下面兩圖呈現(xiàn)了采樣數(shù)據(jù)點個數(shù)均為1000點和300點時各種算法的2維嵌入結(jié)果.

圖1 采樣點個數(shù)1000時的二維嵌入效果

圖2 采樣點個數(shù)300時的二維嵌入效果

在數(shù)據(jù)集稠密的情況下，A-Isomap的降維效果優(yōu)于Isomap和CN-Isomap，特別在數(shù)據(jù)稀疏時，Isomap和CN-Isomap算法很難保持?jǐn)?shù)據(jù)間潛在的低維結(jié)構(gòu)，降維后的二維數(shù)據(jù)呈現(xiàn)出了扭曲變形.而本文新算法A-Isomap卻能在原數(shù)據(jù)空間數(shù)據(jù)信息量少的條件下，可以較好的保持?jǐn)?shù)據(jù)間的相互關(guān)系.

3.2 算法效率分析

在Isomap算法中.影響時間復(fù)雜度的因素主要有3個：選取近鄰所用的時間、計算最短路徑所用的時間、計算特征向量所用的時間，這三者的時間復(fù)雜度分別是O(mN2)、O(kN2logN)、O(N3).CN-Isomap雖然增加了對流形鄰居甄別、刪除的時間，但是卻減少了最短路徑計算的時間.對比之下，增加的時間復(fù)雜度對算法的影響很小.本文算法A-Isomap在CN-Isomap的基礎(chǔ)上，對鄰域區(qū)內(nèi)的點進(jìn)行了聚類分析，其時間復(fù)雜度是O(kNt)，其復(fù)雜度是遠(yuǎn)遠(yuǎn)小于O(N3).其中，N維樣本點的個數(shù)，m維輸入空間的維數(shù)，k為近鄰點的個數(shù)，t為迭代次數(shù).通過表1各算法的平均時間比較可以看出，本文新算法A-Isomap的平均計算時間并沒有顯著的增加，而是和前兩種算法相差無幾.

表1 平均計算時間比較(單位/秒)

4 小 結(jié)

A-Isomap算法針對稀疏數(shù)據(jù)局部信息量不足的問題，通過鄰域選取算法自適應(yīng)的動態(tài)選擇每一個樣本點的鄰域大小.同時，使用聚類信息來匯聚相似的樣本點，保證了降維后的數(shù)據(jù)具有很好的可分性，加強了局部結(jié)構(gòu)的刻畫，通過實驗結(jié)果展示出A-Isomap能夠更好地保持稀疏數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，更具魯棒性.

參 考 文 獻(xiàn)

[1]Jolliffe I.Principal component analysis[M].John Wiley & Sons,Ltd,2005

[2]Cox T,Cox M.Multidimensional Scaling.1994[J].Chapman&Hall,London,UK

[3]J.B,TENENBAUM,V.DE SILVA,J.C.LAGFORD.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319～2323

[4]S.T.ROWEIS,L.K.SAUL.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323～2326

[5]武森，全喜偉，陳學(xué)昌.稀疏數(shù)據(jù)非線性降維的CN-Isomap算法[J].數(shù)學(xué)的實踐與認(rèn)識，2010,40(17):182～188