自適應鄰域選擇的I somap算法

李燕燕 肖 丹 魏曉峰 王海東

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

0 引 言

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

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

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

1 Isomap算法

1.1 Isomap算法的思想

Isomap的理論框架是MDS，不同之處是對數(shù)據(jù)之間相似性的衡量由原始歐式距離換成了測地線距離，通過這種整體幾何特征的重構來最大程度的保持數(shù)據(jù)降維前后的整體拓撲結構.

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

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

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

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

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

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

2 A-Isomap算法

2.1 算法思想

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

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

(1)

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

(2)

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

(3)

2.2 算法的主要步驟

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

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

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

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

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

3 實驗結果分析

3.1 手工流形實驗

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

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

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

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

3.2 算法效率分析

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

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

4 小 結

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

參 考 文 獻

[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]武森，全喜偉，陳學昌.稀疏數(shù)據(jù)非線性降維的CN-Isomap算法[J].數(shù)學的實踐與認識，2010,40(17):182～188