李燕燕 肖 丹 魏曉峰 王海東

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

0 引 言

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

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

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

1 Isomap算法

1.1 Isomap算法的思想

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

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

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

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

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

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

對(duì)Isomap算法的分析可知，Isomap通過(guò)近鄰算法構(gòu)建近鄰圖，在數(shù)據(jù)稀疏的情況下，流形上樣本點(diǎn)數(shù)目分布相對(duì)分散，k近鄰算法的搜索范圍相對(duì)擴(kuò)大，可能將本不屬于同一流形區(qū)域的點(diǎn)包含在同一近鄰圖中，從而導(dǎo)致短路現(xiàn)象，即流形上本不相鄰的兩個(gè)數(shù)據(jù)點(diǎn)成為近鄰點(diǎn).短路的出現(xiàn)可能使得擬合出的測(cè)地線距離嚴(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通過(guò)對(duì)“流形鄰居”的設(shè)定來(lái)鑒別和刪除近鄰圖中短路邊[5]，極大地削弱Isomap對(duì)鄰域大小的依賴程度，并使其更具拓?fù)浞€(wěn)定性.本文在CN-Isomap算法的基礎(chǔ)上，在近鄰區(qū)內(nèi)進(jìn)行聚類(lèi)分析，使相似的樣本點(diǎn)匯聚在一起，保證了降維后數(shù)據(jù)具有很好的可分性.

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

(1)

第j類(lèi)樣本與總體樣本中心的距離為

(2)

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

(3)

2.2 算法的主要步驟

Step1：利用k鄰域法找到樣本點(diǎn)的近鄰點(diǎn)集合.

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

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

Step4：應(yīng)用最短路徑算法得到任意兩樣本點(diǎn)間的最短路徑距離，用這個(gè)距離來(lái)估計(jì)樣本點(diǎn)間的測(cè)地線距離，完成對(duì)任意兩點(diǎn)測(cè)地線的擬合.

Step5：將這些最短路徑長(zhǎng)度作為輸入運(yùn)行古典MDS算法，完成降維.

3 實(shí)驗(yàn)結(jié)果分析

3.1 手工流形實(shí)驗(yàn)

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

圖1 采樣點(diǎn)個(gè)數(shù)1000時(shí)的二維嵌入效果

圖2 采樣點(diǎn)個(gè)數(shù)300時(shí)的二維嵌入效果

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

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

4 小 結(jié)

A-Isomap算法針對(duì)稀疏數(shù)據(jù)局部信息量不足的問(wèn)題，通過(guò)鄰域選取算法自適應(yīng)的動(dòng)態(tài)選擇每一個(gè)樣本點(diǎn)的鄰域大小.同時(shí)，使用聚類(lèi)信息來(lái)匯聚相似的樣本點(diǎn)，保證了降維后的數(shù)據(jù)具有很好的可分性，加強(qiáng)了局部結(jié)構(gòu)的刻畫(huà)，通過(guò)實(shí)驗(yàn)結(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é)的實(shí)踐與認(rèn)識(shí)，2010,40(17):182～188