王曦楊，程春玲，陳興國

南京郵電大學 計算機學院，南京 210003

面向可視化的全局自適應等距映射算法*

王曦楊，程春玲+，陳興國

南京郵電大學 計算機學院，南京 210003

+Corresponding author:E-mail:chengcl@njupt.edu.cn

WANG Xiyang,CHENG Chunling,CHEN Xingguo.Globaladaptive isometricmapping algorithm for visualization.Journalof Frontiersof Computer Scienceand Technology,2017,11(7)：1092-1101.

等距映射；數(shù)據(jù)可視化；拓撲穩(wěn)定；數(shù)據(jù)流形

1 引言

在數(shù)據(jù)的可視查詢與分析過程中，不可避免地會遇到大量高維的數(shù)據(jù)，如全球氣候數(shù)據(jù)、基因分布數(shù)據(jù)、金融交易數(shù)據(jù)等，若直接對原始數(shù)據(jù)進行處理，很難保證數(shù)據(jù)可視化的質量以及響應速度[1]，迫切需要合適的數(shù)據(jù)約簡技術，提取有效而又合理的特征數(shù)據(jù)并用于可視化應用中。近幾年，美國俄亥俄大學以及斯坦福和華盛頓大學成立的交互式數(shù)據(jù)實驗室（Interactive Data Lab）在這方面的研究取得了較大進展，其面向數(shù)據(jù)可視化的約簡技術包括過濾采樣[1]（filtering&sampling）、數(shù)據(jù)聚合[2]（data aggregation）和混合約簡[3]（hybrid reduction）3種方式。然而這些方法針對特定數(shù)據(jù)和實際系統(tǒng)需求而設計，雖對特定數(shù)據(jù)有很好的處理效果，但通用性并不理想。相比之下，數(shù)據(jù)的降維映射作為一種傳統(tǒng)的底層的數(shù)據(jù)約簡策略，具有較高的普適性，可為數(shù)據(jù)可視化提供很好的技術支持，非常具有研究意義。

降維映射的目標就是將對象數(shù)據(jù)映射到一個二維或者三維空間，并且保留盡可能多的數(shù)據(jù)間的本質結構[4]。代表方法有保留局部特征的局部線性嵌入（locally linearembedding，LLE）[5]、拉普拉斯特征映射[6]（Laplacian eigenmaps，LE）和局部切空間排列[6]（local tangentspace alignment，LTSA）；保留全局特征的多維尺度變換[4]（multidimensionalscaling，MDS）和等距映射[7]（isometricmapping，Isomap）。僅保留局部特征的方法具有更快的運算速度，但映射后難以保證數(shù)據(jù)對象之間的測度，從而對數(shù)據(jù)結構及其內在規(guī)律的分析造成負面影響。MDS在數(shù)據(jù)可視化方面已有廣泛的應用，但它并不能對非線性分布的數(shù)據(jù)進行降維。作為MDS的有效擴展，基于數(shù)據(jù)流形的Isomap算法[5]采用能有效表征數(shù)據(jù)全局幾何結構的近鄰圖和測地距離對數(shù)據(jù)進行降維可視化處理，考慮到了較大規(guī)模、非線性數(shù)據(jù)結構的整體性。然而，Isomap算法極大依賴于難以有效選取的鄰域大小，極易造成數(shù)據(jù)拓撲不穩(wěn)定的情況[6]；另外，Isomap算法的復雜度非常高，實際計算量很大[6]。在高度交互式的可視化實際應用背景下，很難滿足交互實時性和可視化準確性的需求，極大限制了該類算法的實際應用。

針對以上兩個問題，本文總結了現(xiàn)有改進方法的優(yōu)劣，基于Isomap的核心思想，提出了具有全局自適應性的GA-Isomap（globaladaptive-Isomap）算法。主要工作在于：（1）引入數(shù)據(jù)區(qū)域密度作為唯一評估指標，提出數(shù)據(jù)區(qū)域密度的衡量方式和區(qū)域劃分方式；（2）基于區(qū)域密度和數(shù)據(jù)點連通性，提出漸進式的鄰域構建方法和基于區(qū)域的地標選取方法；（3）提出基于雙層圖的降維映射策略，利用鄰域圖和僅由地標構造出的框架圖提高映射準確性；（4）通過實驗將本文算法與現(xiàn)有算法進行比較分析。

2 相關工作

Isomap算法采用圖模型思想，通過捕捉原始數(shù)據(jù)集的內在流形結構，獲得觀測數(shù)據(jù)集在低維空間的相應描述[7]。目前對Isomap的研究主要包括鄰域圖構建方法、路徑計算方法和快速降維映射三方面，可從拓撲穩(wěn)定性和算法效率兩方面展開。

為提高Isomap方法的拓撲穩(wěn)定性，主要采用基于映射質量反饋的方法、刪除短路邊的方法以及動態(tài)鄰域構建方法。

基于結果反饋的方法就是對運行結果進行評估，從而進行相應優(yōu)化策略。典型的有基于“殘差”的評估優(yōu)化方法[8]，利用目標殘差和實際殘差的差值來遞增或遞減地調整近鄰值；還有Agarwal等人提出的PLACECENTER[9]以及Choi等人提出的ParallelGTM（generative topographicmapping）[10]優(yōu)化框架，根據(jù)映射結果的誤差來調整矩陣的分解方式。這類方法為了將誤差值控制在一個較小閾值當中，需不斷迭代處理先前的結果，很難控制運行時間。

刪除“短路”邊的方法可避免數(shù)據(jù)流形上本不相鄰的兩數(shù)據(jù)點相連，因而可有效保證鄰域圖的準確性和拓撲穩(wěn)定性。孟德宇等人提出流形重構法[11]，利用流形空間與低維表示空間之間的顯式映射關系矩陣，將原有點對點的映射擴展至局部空間到空間的快速映射。邵超等人提出的P-Isomap算法[12]，通過分配權重值抑制由鄰域大小不合適而產生的“短路”邊對距離保持的影響。Gao等人提出judgeShortCircuits算法[13]，根據(jù)“短路”邊途經低密度區(qū)域的特點，利用基于高斯核函數(shù)的核密度估計法，取一條邊上的3個四分位點的平均局部密度來近似區(qū)域密度，以此鑒別并刪除鄰域圖中可能的“短路”邊。然而，這類方法只是在原有算法的基礎上簡單增加了判斷和刪除的步驟，不可避免地增加了計算量，且依舊受靜態(tài)參數(shù)的影響。

動態(tài)鄰域構建方法使得近鄰圖的構建擺脫了靜態(tài)參數(shù)的限制，降低了算法敏感度。Zhan等人提出Isomap w ith dynam ic neighbor[14]，基于切空間向量評估數(shù)據(jù)點分布情況和距離遠近，動態(tài)選取近鄰。此外，Mekuz[15]、Gao[16]等人也提出類似方法，只是數(shù)據(jù)點向切空間的投影方式以及評估指標稍有不同。Yang提出利用最小代價生成樹和貪心算法的思想來構建鄰域圖[17]，可保證鄰域圖的準確性和連通性。?nkaya等人提出了Isomap w ith NC算法[18]，使用加布里埃爾圖（Gabriel graph）來計算數(shù)據(jù)點的區(qū)域連通性和近似關系，從而為每個數(shù)據(jù)點分配特定的近鄰。然而，基于切空間的評估法對數(shù)據(jù)有較高要求，其內部參數(shù)必須在有足夠的采樣數(shù)據(jù)、相對恒定的曲率和相對均勻的分布密度前提下才可計算得到。利用最小代價生成樹和使用加布里埃爾圖的方法，其中臨界節(jié)點的判斷邏輯增加了算法復雜度。為提高算法運算速度，目前主要是設計快速映射方法，主要措施有基于地標的映射方法和基于約簡距離矩陣的映射方法。地標的概念以及經典的L-Isomap算法[19]由Isomap創(chuàng)始人Tenenbaum提出，通過固定地標，僅計算每個數(shù)據(jù)點與地標點的距離，從而減少距離矩陣的計算量，但仍面臨拓撲穩(wěn)定性的問題。為此，Orsenigo提出L-IsomapSC算法[20]，引入“親密度”和“類同性質”兩個新指標來確定地標點集的權重，最終找出能夠覆蓋所有數(shù)據(jù)點的地標點集合。其結果雖然提高了數(shù)據(jù)拓撲穩(wěn)定性，但尋找最大權重點集增加了較大的時間開銷，且其地標所占比仍需人為控制。

基于約簡距離矩陣的映射是相對新穎的優(yōu)化方法，代表性的有Dzw inel等人提出的快速nr-MDS算法[21]，對距離矩陣進行奇異值分解，利用約簡的相異矩陣進行運算，使得映射過程的空間復雜度僅為線性。還有Yang等人提出的MMD-Isomap（multi-manifold discrim inant Isomap）算法[22]，基于不同的數(shù)據(jù)流形區(qū)域，對原始數(shù)據(jù)的距離矩陣進行分割，再分別對每個矩陣進行降維映射計算。該類方法雖降低了計算復雜度，但其映射結果并不穩(wěn)定，會出現(xiàn)數(shù)據(jù)“擁擠”現(xiàn)象，即多個數(shù)據(jù)點重疊。

3 GA-Isomap算法設計

理想的等距映射方法應擺脫鄰域半徑、近鄰值、地標所占比等靜態(tài)參數(shù)影響，提高拓撲穩(wěn)定性的同時盡量減少時間開銷。若算法能主動適應原始數(shù)據(jù)的分布特征，則可以擺脫靜態(tài)參數(shù)的人為設置，更加準確有效地抓取原始數(shù)據(jù)流形，進而確定每個數(shù)據(jù)點的近鄰，構建鄰域圖。此時，如果可以采用一個簡單且實用的評估指標，統(tǒng)籌考慮近鄰和地標的選擇，將大大簡化處理流程。數(shù)據(jù)密度作為一個典型特征，可直觀反映原始數(shù)據(jù)之間的關系，因此本文將原始數(shù)據(jù)區(qū)域密度作為唯一指標，以此判斷出每個數(shù)據(jù)點的近鄰，劃分其所處區(qū)域，完成鄰域圖的構建，并根據(jù)區(qū)域選擇出地標。在最終映射計算時，由于這里的地標是根據(jù)區(qū)域選取的，可利用地標點之間構成的完全連通圖作為后續(xù)數(shù)據(jù)點的映射框架，設計基于雙層圖的映射，盡量確保數(shù)據(jù)點之間的相對位置關系，也遵循等距映射方式最基本的目標。

3.1 原始數(shù)據(jù)區(qū)域劃分

通過數(shù)據(jù)的分布密度可以直觀量化出原始數(shù)據(jù)的分布情況，從而為每個數(shù)據(jù)點的近鄰選擇和區(qū)域地標點選擇提供參考依據(jù)。但由于高維空間的區(qū)域大小不易確定，且這里只需對數(shù)據(jù)分布區(qū)域進行區(qū)分，根據(jù)數(shù)據(jù)流形中的局部線性特征[5]，可統(tǒng)一用線密度作為一個衡量指標。為簡化計算，本文引入核心近鄰和密度近鄰的概念。文獻[17]同樣提到這樣的概念，但只是通過連接距離的遠近進行簡單區(qū)分，對其定義并不明確，為使得后續(xù)鄰域圖盡量只包含短邊以便遵循數(shù)據(jù)流形，這里對其進行重新定義。

定義1（核心近鄰）原始數(shù)據(jù)構成的連通圖中，與數(shù)據(jù)點xi直接相連的點即為點xi的核心近鄰。

定義2（密度近鄰）原始空間中，與數(shù)據(jù)點xi處于同一密度區(qū)域的數(shù)據(jù)點即為點xi的密度近鄰。

定義3（區(qū)域密度）數(shù)據(jù)點xi所處區(qū)域的密度值為其對應密度近鄰集合中數(shù)據(jù)點個數(shù)與相距最遠的兩點間距離的比值。

數(shù)據(jù)點xi的核心近鄰構成核心近鄰集合CNi，其密度近鄰構成密度近鄰集合DNi，通過構建密度近鄰集合即可實現(xiàn)不同密度區(qū)域的劃分。基于最小連通圖，將未與點xi直接相連的點按歐式距離的非遞減順序排序，構成有序點集Pi；依次考慮Pi中的數(shù)據(jù)點Pi[j]，加入DNi集合計算區(qū)域密度，即DNi={Pi[j]}?{xi}?CNi。令density()為數(shù)據(jù)集合的密度計算函數(shù)，任意兩點 xm,xn∈DNi的歐式距離為 δmn，則密度計算公式可寫為：

確定密度近鄰的過程為：若密度值保持不變或是增加，則將該點看作數(shù)據(jù)點xi的近鄰；若DNi的密度下降，則預示著一個不同密度區(qū)域的開始，將該點稱為離點xi最近的區(qū)域斷點，并從DNi中刪除。

3.2 鄰域圖構建

現(xiàn)有的動態(tài)近鄰構建法提供了很好的思路，但其構建完整圖再刪除邊的做法造成了很多計算浪費。為提高構建的準確性和速度，本文的鄰域圖構建將基于區(qū)域劃分的結果，采用逐步增加邊的方法完成鄰域圖的構建，稱之為漸進式構建法?？梢哉f，近鄰圖的構建和區(qū)域的劃分是同時進行的。

鄰域圖的構建將從最小連通圖開始。最小連通圖既能有效地避免“短路”邊，也能較好地反映原始數(shù)據(jù)內在的流形結構，這也是該類算法能夠成功運用的必要前提。只需利用k-nn方法從k=1開始遞增式構建k近鄰圖，通過深度優(yōu)先遍歷判斷圖的連通性，即可得出最小連通鄰域圖G。

在構建過程中，每當確定一個數(shù)據(jù)點xi與其相應的密度近鄰集合DNi后，增加邊使得點xi與DNi中所有點直接相連，更新圖G。如此構建將使得后續(xù)數(shù)據(jù)點判斷密度近鄰的計算量越來越少，因為對后續(xù)點，與其直接相連的數(shù)據(jù)點只會增多，即其初始集合CNi中的點數(shù)逐漸變多，由此可避免近鄰點之間的重復判斷。

3.3 地標點選取

隨機選取地標點雖是最快的方法，但易造成數(shù)據(jù)點的丟失，難以保證完整的數(shù)據(jù)拓撲。為此，文獻[21]提出當?shù)貥四軌蚋采w所有數(shù)據(jù)點時，可保證結果的準確性。這提供了一個很好的思路。由于本文方法在劃分區(qū)域時充分考慮到了周圍點的疏密分布，可以說一個密度區(qū)域中的點是相對緊湊的，因而選擇該區(qū)域的中心點作為該區(qū)域的地標將非常具有代表性。相比于文獻[21]所提出的基于類同性質和親密度的權重覆蓋判斷方式，更容易理解和實現(xiàn)。

定義4（地標點）在密度近鄰集合中，到其余所有點的平均距離最小的點，即是該密度區(qū)域的地標點。

令DNi集合中任意一點與其余點之間的平均距離函數(shù)為ad()，對任意點xj∈DNi，則該點到其余點的平均距離為：

那么該集合的地標點的選取公式可寫為：

從DNi集合中求出集合中心點作為后續(xù)降維映射的地標，這意味著該地標點可代表鄰域內的所有點，為避免不必要的選擇沖突和數(shù)據(jù)點的重復判斷，必須規(guī)定一個密度區(qū)域只允許出現(xiàn)一個地標點，其余點將不可能成為地標點。

3.4 基于雙層圖的降維映射

現(xiàn)有的方法往往只將地標作為一種減少計算量的手段，因而通常在降維映射后發(fā)生數(shù)據(jù)結構遭到破壞的情況，尤其在基于散點圖的可視化應用中非常明顯。若是利用地標點構成地標框架圖GL，依此計算出地標測地距離矩陣DXGL，并將其映射結果作為數(shù)據(jù)點相對位置的參考，可使得后續(xù)數(shù)據(jù)點的映射更加準確。

此時，采用構建完全連通圖的方式構建地標框圖GL可極大提高地標測地距離矩陣DXGL的準確性。為盡量保證地標點之間的距離測度，最終基于MDS的映射目標函數(shù)可改進為：

其中，dXL(lmi,lmj)表示原始維度空間內地標lmi與lmj兩點的測地距離，其值可通過矩陣DXGL獲得；dYL(lmi′,lmj′)表示映射目標空間內與其對應的 lmi′與 lmj′兩點的歐式距離，由此得出地標點在目標空間的映射坐標點集YL。

在地標映射完成后，只需通過鄰域圖G計算獲得其余點與所有地標點的測地距離矩陣DXG，利用L-MDS[20]算法即可獲得其余數(shù)據(jù)點的低維映射結果。

3.5 算法描述及復雜度分析

基于以上的設計方案和傳統(tǒng)Isomap算法框架，可構造一個能夠自適應構建鄰域和地標的降維映射算法，稱之為GA-Isomap算法。

算法GA-Isomap

輸入：原始數(shù)據(jù)點集X={x1,x2,…,xn}

輸出：目標空間對應點集Y={y1,y2,…,yn}

步驟1劃分區(qū)域，構建鄰域圖

步驟2選取地標，構造地標完全圖

步驟3基于雙層圖的降維映射

表1比較了GA-Isomap算法與傳統(tǒng)Isomap[7]、LIsomap[20]、L-IsomapSC[21]和 Isomap w ith NC[18]算法的時間復雜度。

Table1 Complexity comparison of5 algorithms表1 5種算法的時間復雜度比較

不難發(fā)現(xiàn)，GA-Isomap在鄰域圖構建、地標選取和映射計算均達到目前較低的復雜度，且不受靜態(tài)近鄰值k和地標占比的影響。密度區(qū)域的劃分大大簡化了鄰域構建和地標選取的過程，選取區(qū)域中心作為地標的方式使得新算法既具有傳統(tǒng)L-Isomap的線性復雜度，也達到了L-IsomapSC所追求的地標全覆蓋的目標。在路徑計算方面，因為GA-Isomap為提高映射準確率，單獨構建了完全圖計算地標與地標的相對位置關系，不可避免地增加了計算復雜度。但在實際運行時，算法中的nL＜＜n，這將有效控制地標距離矩陣的規(guī)模和基于地標的映射計算量，實驗結果也說明了本文方法的可行性。

4 實驗結果與分析

本文采用函數(shù)生成無噪聲干擾的sw iss roll標準測試數(shù)據(jù)集[6]，其三維空間分布如圖1（a）所示，數(shù)據(jù)呈卷狀分布，其結果可反映出不同算法的流形捕捉性能。這里為更好地測試不同算法的拓撲穩(wěn)定性，還采用changing-sw iss roll數(shù)據(jù)[23]進行測試，其三維空間分布如圖1（b）所示。本文通過隨機數(shù)生成器規(guī)定changing-sw iss roll局部子空間內的數(shù)據(jù)點個數(shù)，其整體依舊呈卷狀分布，但該數(shù)據(jù)產生明顯的疏密分布變化，其中對于數(shù)據(jù)點分布相對稀疏的局部子空間的映射結果更能切實反映出不同算法的拓撲穩(wěn)定性。仿真環(huán)境為Matlab 2012b，硬件配置為Intel i5-3337u 1.8GHz CPU，8GB內存，操作系統(tǒng)為Windows7。部分測試代碼來源于http://isomap.stanford.edu/。

Fig.1 Three-dimensionaldistribution of testdata圖1 測試數(shù)據(jù)三維分布效果圖

該實驗首先使用2 000個數(shù)據(jù)點的sw iss roll和changing-sw iss roll數(shù)據(jù)測試各算法，通過直觀的降維映射效果圖反映各算法的拓撲穩(wěn)定性；然后分別使用不同規(guī)模的測試數(shù)據(jù)，測試并比較各算法的運行時間。對比算法分別為 Isomap[6]、L-Isomap[20]、Isomap w ith dynam ic neighbor[14]和 Isomap w ith NC[18]。 由 于Isomap和L-Isomap的映射質量受靜態(tài)參數(shù)影響，為選取較優(yōu)結果進行比較，其近鄰值k取常用的6、8，并將地標所占比設為文獻[21]中的建議值0.5。Isomap w ith dynam ic neighbor和Isomap w ith NC算法均按照原文獻進行初始參數(shù)設置，前者的最小近鄰值設為4，后者的最小區(qū)域直徑初始化為任意兩點的最小距離。對于GA-Isomap算法，需將最小連通圖構建部分中k-nn算法的k設為初始值1；將密度區(qū)域點集DNi最小長度設為2，避免產生空區(qū)域或單個孤立的數(shù)據(jù)點。

4.1 可視化映射效果

首先分別利用5種算法處理測試2 000點的sw iss roll和changing-sw iss roll數(shù)據(jù)，將其映射至二維平面內，繪制二維散點圖。通過簡單的顏色編碼直觀展示各算法對原始數(shù)據(jù)的鄰域結構和整體拓撲結構的保留程度，處理結果如圖2和圖3所示，X軸表示水平方位，Y軸表示縱向方位。

從圖 2（a）、（b）、（c）、（d）和圖 3（a）、（b）、（c）、（d）可以看出，Isomap和L-Isomap的處理結果并不理想，數(shù)據(jù)內部和邊緣都存在明顯的畸變，對于changingsw iss roll則尤為明顯，即使調整鄰域參數(shù)k值也很難保證拓撲穩(wěn)定，映射準確。如圖2（c）、（d）紅圈部分所示，部分區(qū)域出現(xiàn)嚴重空缺，固定近鄰數(shù)、地標占比的方法導致映射結果具有很強的隨機性。其余3個算法對于傳統(tǒng)的測試數(shù)據(jù)均有非常好的映射效果，主要是因為傳統(tǒng)sw iss roll的數(shù)據(jù)分布是相對均勻的。但是對于changing-sw iss roll測試數(shù)據(jù)，Isomap w ith dynam ic neighbor和Isomap w ith NC這兩個算法在數(shù)據(jù)極為稀疏的區(qū)域都產生了嚴重的畸變，如圖3（e）、（f）中紅圈所示區(qū)域，并不能準確抓取離散區(qū)域的數(shù)據(jù)流形。

相比之下，GA-Isomap對不同分布狀態(tài)的數(shù)據(jù)均有非常好的處理效果。因為該算法中的鄰域構建充分考慮到了數(shù)據(jù)的區(qū)域特性，區(qū)域內的點彼此連通，使得測地距離的計算更加準確。另外，由于達到了地標全覆蓋的目標，任意非地標的數(shù)據(jù)點都可以找到自己所在區(qū)域的地標，即使在數(shù)據(jù)極為稀疏的部分也能準確捕捉數(shù)據(jù)流形，并通過基于雙層圖的映射有效反映出原始數(shù)據(jù)的分布情況。

4.2 運行時間

對于兩種數(shù)據(jù)的測試，每個算法均進行10次運算處理，取時間均值進行比較。時間開銷的比較結果分別如圖4、圖5所示。

在測試數(shù)據(jù)規(guī)模較?。╪≤1 500）時，各算法的運行時間差距并不大，但數(shù)據(jù)規(guī)模較大時，Isomap w ith dynam ic neighbor由于采用切空間的映射和評估來構建鄰域圖，過多的投影計算使其運行時間快速增長，時間開銷相比原始Isomap并沒有改善。Isomap w ith NC和L-Isomap對于算法運行時長的改善顯著，但Isomap w ith NC需要重復判斷并更新擴展近鄰[18]、臨界近鄰[18]和最終近鄰[18]；L-Isomap 中固定地標百分比導致地標數(shù)呈線性增長，其計算時長增加也比較明顯。另外，隨機地標的策略導致其并不適合對小規(guī)模、稀疏分布的測試數(shù)據(jù)進行處理，會發(fā)生鄰域圖無法構建的情況，導致L-Isomap算法無法運行。因此對于changing-sw iss roll，本文未做1 500點以下的時間開銷比較。

Fig.4 Time comparison by dealingw ith sw iss roll圖4 傳統(tǒng)sw iss roll數(shù)據(jù)時間比較

Fig.5 Timecomparison by dealingwith changing-swiss roll圖5 changing-sw iss roll數(shù)據(jù)時間比較

相比之下，GA-Isomap處理兩種測試數(shù)據(jù)時運行時間增量很小，反映出該算法所采用的近鄰、地標選取方式和映射計算方式其整體擁有較小的時間開銷，也更適合于較大數(shù)據(jù)量的處理。密度區(qū)域內數(shù)據(jù)點的增多并不會導致地標個數(shù)的增加，這可以有效控制地標數(shù)量。在數(shù)據(jù)邊界確定時，數(shù)據(jù)量越大，分布越密集，地標個數(shù)越趨于穩(wěn)定，從而控制了相對地標的映射計算量。即使增加了對地標的測地距離計算和映射處理，對于算法整體的運行效率并沒有太大影響。

5 總結與展望

針對數(shù)據(jù)可視分析應用中視圖準確性和結果反饋即時性的需求，本文遵循等距映射的核心思想提出了新的降維映射算法GA-Isomap。本文算法無需任何先驗知識和靜態(tài)參數(shù)設置，主動適應數(shù)據(jù)分布特征，為鄰域圖構建和地標點選取提出了一個新思路。在進行數(shù)據(jù)降維可視化時，本文算法兼顧了拓撲穩(wěn)定性和算法效率，從而能夠更準確、迅速地對數(shù)據(jù)進行可視化。

然而，GA-Isomap為提高計算效率，在劃分區(qū)域、選取近鄰和地標時，需設定額外矩陣或數(shù)組記錄中間結果，雖避免了后續(xù)的重復判斷，但導致較大的內存占用。另外，如何有效處理含有噪聲的數(shù)據(jù)也是一個關鍵問題，因此下一步的工作是研究更加高效的距離測算方式，以及距離矩陣的分解和存儲方式，并將所設計的算法用于數(shù)據(jù)可視化系統(tǒng)開發(fā)當中，實際檢驗本文算法的有效性，并嘗試將本文算法用于大數(shù)據(jù)環(huán)境下的可視查詢與分析中。

[1]Jiang Lilong,NandiA.SnapToQuery:providing interactive feedback during exploratory query specification[J].Proceedingsof the VLDBEndowment,2015,8(11):1250-1261.

[2]Liu Zhicheng,Jiang Biye,Heer J.imMens:real-time visual querying of big data[C]//Proceedingsof the 15th Eurographics Conference on Visualization,Leipzig,Germany,Jun 17-21,2013.Chichester,UK:The Eurographs Association&John Wiley&Sons,Ltd,2013,32:421-430.

[3]Agarwal S,MozafariB,Panda A,etal.BlinkDB:queriesw ith bounded errors and bounded response times on very large data[C]//Proceedings of the 8th European Conference on Computer Systems,Prague,Apr 15-17,2013.New York:ACM,2013:29-42.

[4]Brehmer M,Sedlmair M,Ingram S,etal.Visualizing dimensionally-reduced data:interviewsw ith analystsand a characterization of task sequences[C]//Proceedings of the 5th Workshop on Beyond Time and Errors:Novel Evaluation Methods for Visualization,Paris,Nov 10,2014.New York:ACM,2014:1-8.

[5]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[6]Balasubramanian M,Schwartz E L.The Isomap algorithm and topologicalstability[J].Science,2002,295(5552):7-9.

[7]Tenenbaum JB,De Silva V,Langford JC.A globalgeometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[8]Samko O,Marshall A D,Rosin PL.Selection of the optimal parameter value for the Isomap algorithm[J].Pattern Recognition Letters,2006,27(9):968-979.

[9]Agarwal A,Phillips JM,Venkatasubramanian S.Universal multi-dimensional scaling[C]//Proceedings of the 16th International Conference on Know ledge Discovery and Data M ining,Washington,Jul25-28,2010.New York:ACM,2010:1149-1158.

[10]Choi JY,Bae SH,Qiu Xiaohong,etal.High performance dimension reduction and visualization for large high-dimensional data analysis[C]//Proceedings of the 10th International Conference on Cluster,Cloud and Grid Computing,Melbourne,Australia,May 17-20,2010.New York:ACM,2010:331-340.

[11]Meng Deyu,Xu Chen,Xu Zongben.A new manifold reconstruction method based on Isomap[J].Chinese Journal of Computers,2010,33(3):545-555.

[12]Shao Chao,Huang Houkuan,Zhao Lianwei.A more topologically stable ISOMAPalgorithm[J].Journal of Software,2007,18(4):869-877.

[13]Gao Xiaofang,Liang Jiye.An improved incrementalnonlinear dimensionality reduction for isometric data embedding[J].Information Processing Letters,2015,115(4):492-501.

[14]Zhan Yubin,Yin Jianping,Long Jun.Dynamic neighborhood selection for nonlinear dimensionality reduction[C]//LNCS 5861:Proceedings of the 6th International Conference on Modeling Decisions for Artificial Intelligence,Awaji Island,Japan,Nov 30-Dec 2,2009.Berlin,Heidelberg:Springer,2009:327-337.

[15]Mekuz N,Tsotsos JK.Parameterless Isomap w ith adaptive neighborhood selection[C]//LNCS 4174:Proceedings of the 28th Symposium of the German Association for Pattern Recognition,Berlin,Sep 12-14,2006.Berlin,Heidelberg:Springer,2006:364-373.

[16]Gao Xiaofang,Liang Jiye.The dynam ical neighborhood selection based on the sampling density and manifold curvature for isometric data embedding[J].Pattern Recognition Letters,2011,32(2):202-209.

[17]Yang Li.Building connected neighborhood graphs for isometric data embedding[C]//Proceedings of the 11th ACM SIGKDD International Conference on Know ledge Discovery in Data M ining,Chicago,USA,Aug 21-24,2005.New York:ACM,2005:722-728.

[18] ?nkaya T,Kayal?gil S,?zdemirel N E.An adaptive neighbourhood construction algorithm based on density and connectivity[J].Pattern Recognition Letters,2015,52:17-24.

[19]Silva V D,Tenenbaum JB.Global versus localmethods in nonlinear dimensionality reduction[J].Advances in Neural Information Processing Systems,2002,15:1959-1966.

[20]Orsenigo C.An improved set covering problem for Isomap supervised landmark selection[J].Pattern Recognition Letters,2014,49:131-137.

[21]Dzw inelW,W cis?o R.Very fast interactive visualization of large sets of high-dimensional data[J].Procedia Computer Science,2015,51:572-581.

[22]Yang Bo,Xiang M ing,Zhang Yupei.Multi-manifold discrim inant Isomap for visualization and classification[J].Pattern Recognition,2016,55:215-230.

[23]He Jinrong,Ding Lixin,Jiang Lei,etal.Intrinsic dimensionality estimation based on manifold assumption[J].Journal of Visual Communication and Image Representation,2014,25(5):740-747.

附中文參考文獻：

[11]孟德宇,徐晨,徐宗本.基于Isomap的流形結構重建方法[J].計算機學報,2010,33(3):545-555.

[12]邵超,黃厚寬,趙連偉.一種更具拓撲穩(wěn)定性的ISOMAP算法[J].軟件學報,2007,18(4):869-877.

WANG Xiyangwasborn in 1992.He isan M.S.candidateatNanjing University of Postsand Telecommunications.His research interest is interactive data visualization and analysis.

王曦楊（1992—），男，江蘇南京人，南京郵電大學碩士研究生，主要研究領域為交互式數(shù)據(jù)可視化與分析。

程春玲（1972—），女，陜西西安人，1996年于南京理工大學獲得碩士學位，現(xiàn)為南京郵電大學教授，CCF會員，主要研究領域為數(shù)據(jù)管理，分布式資源管理和性能優(yōu)化。

CHEN Xingguo was born in 1984.He received the Ph.D.degree in computer science and technology from Nanjing University in 2014.Now he isa lectureratNanjing University of Posts and Telecommunications.His research interests includemachine learning and reinforcement learning.

陳興國（1984—），男，江蘇南通人，2014年于南京大學獲得博士學位，現(xiàn)為南京郵電大學講師，主要研究領域為機器學習，強化學習。

G lobalAdaptive Isometric M apping A lgorithm for Visualization*

WANG Xiyang,CHENG Chunling+,CHEN Xingguo
School of Computer,Nanjing University of Postsand Telecommunications,Nanjing 210003,China

The Isomap(isometricmapping)and its variant algorithm aremuch influenced by static parameters and thenearestneighbor judgment logic.Asa result,there are problems such as computationalwaste,numericalsensitivity or unstable data topology.In the practicalapplication of interactive data visualization,it is very difficult to fulfill the requirementof real-time interaction and accurate visualization.Therefore,this papermakes an improvementon the original computing framework of isometricmapping,and proposes a globaladaptive algorithm called GA-Isomap(global adaptive-Isomap).In the aspectof neighborhood construction,this paper proposes an incremental construction method and region selection method,by means of the new designed method of local density calculation and the region division.In the aspect of low-dimensional embedding,this paper proposes amapping calculation method based on two-layer graph,which takes the framework graph of landmarksand the relative position relationship into consideration.Compared w ith original Isomap,L-Isomap,Isomap with dynamic neighbor and Isomap w ith NC,simulation results show that the GA-Isomap algorithm can effectively balance the data topology stability and operationalefficiency in visualization.

isometricmapping;data visualization;topologicalstability;datamanifold

nling was born in 1972.She

the M.S.degree in computer application from Nanjing University of Science and Technology in 1996.Now she is a professor at Nanjing University of Posts and Telecommunications,and themember of CCF.Her research interests include datamanagement,distributed resourcemanagement and performanceoptimization.

A

：TP391

摘 要：等距映射（isometric mapping，Isomap）及其衍生的維度約簡算法受靜態(tài)近鄰值、地標比重值或近鄰判斷邏輯的影響，存在計算浪費、數(shù)值敏感或數(shù)據(jù)拓撲不穩(wěn)定的情況，在數(shù)據(jù)可視化分析的實際應用中很難滿足交互實時性和視圖準確性的需求。為此，對等距映射的原始計算框架進行改進，提出了具有全局自適應性的GA-Isomap（global adaptive-Isomap）算法。鄰域圖構建方面，設計了數(shù)據(jù)局部密度值計算和區(qū)域劃分方法，提出了漸進式的鄰域圖構造方法和區(qū)域地標點選取方法；降維映射方面，引入地標框架圖并利用相對位置關系，提出了基于雙層圖的映射計算方式。仿真結果表明，與Isomap、L-Isomap、Isomap w ith dynam ic neighbor和Isomap w ith NC算法相比，該算法在進行數(shù)據(jù)可視化映射時能有效兼顧數(shù)據(jù)拓撲穩(wěn)定性和運行效率。