基于聚類的海量空間數(shù)據(jù)可視化研究與應(yīng)用?

楊 璇 劉 宇

（1.南京烽火軟件科技有限公司 南京 210019）（2.武漢郵電科學(xué)研究院 武漢 430074）

1 引言

隨著空間信息處理技術(shù)的快速發(fā)展以及人們對空間信息需求的日益增長，空間數(shù)據(jù)可視化已成為處理此類信息的一個關(guān)鍵途徑及一項主要技術(shù)。可視化技術(shù)充分利用了人們對空間和色彩的感知度，將人機一體化有機地結(jié)合起來，它在空間信息的展示及挖掘期間起著重要作用［1］。

空間數(shù)據(jù)的特性主要表現(xiàn)在對地理位置（如經(jīng)度和維度等）的依賴性，空間數(shù)據(jù)可視化目前較為常用的方法的是基于地理信息系統(tǒng)（GIS）［2］。但是，隨著空間數(shù)據(jù)的數(shù)據(jù)量和數(shù)據(jù)復(fù)雜度的不斷提升，僅僅依靠GIS實現(xiàn)空間數(shù)據(jù)的可視化存在明顯的缺陷，因此怎樣對海量空間數(shù)據(jù)進行分析和挖掘面臨著很多問題。

海量空間數(shù)據(jù)分析面對的關(guān)鍵問題在于此類數(shù)據(jù)自身的復(fù)雜性:由于其包含了空間實體的方位、尺寸、位置等多方面的信息，因此其數(shù)據(jù)結(jié)構(gòu)比普通的結(jié)構(gòu)化數(shù)據(jù)更為復(fù)雜，其復(fù)雜性主要涵蓋了數(shù)據(jù)表現(xiàn)為多維度、空間屬性間存在非線性關(guān)聯(lián)等方面，因此進一步增加了空間數(shù)據(jù)分析的難度。如何利用可視化方法，提高可視化效率和可信度，讓數(shù)據(jù)分析變得更簡單，是一個值得研究的課題［3］。

針對空間數(shù)據(jù)分析方法與空間數(shù)據(jù)可視化技術(shù)在實際應(yīng)用中面臨的問題，本文提出了一種基于聚類的空間數(shù)據(jù)可視化方法。通過對空間數(shù)據(jù)進行聚類分析，對數(shù)據(jù)進行合理組織和有效劃分，設(shè)計了一種展示直觀、便于分析、交互性好的可視化方法，來對此類數(shù)據(jù)進行展示和分析，進而使分析的成效有所提升，分析的結(jié)果具有更高的精準度。

2 相關(guān)工作

2.1 空間聚類算法

空間聚類作為聚類分析的一個重要探究方向，主要是按照聚類結(jié)束條件來不斷對數(shù)據(jù)劃分過程進行優(yōu)化，從而獲取最佳劃分結(jié)果的流程［4］?，F(xiàn)階段，國內(nèi)外學(xué)者在此領(lǐng)域的探究已經(jīng)獲取了不少成果，現(xiàn)有的文獻也展現(xiàn)出了許多不同的空間聚類算法。根據(jù)操作方法的差別，通常主要分成如下幾種:基于劃分的聚類算法、基于層次的聚類算法、基于密度的聚類算法、基于網(wǎng)格的聚類算法和基于模型的聚類算法［5］。

基于劃分的聚類算法提出時間最久遠，使用最頻繁，由于這類算法便于領(lǐng)會和理解并且在實際應(yīng)用中易于掌控和實現(xiàn)，因此被普遍適用于空間聚類分析之中。基于層次的聚類算法由于在靈活性方面較為遜色，因此通常與其他的算法一起使用，共同完成聚類［6］?；诿芏鹊木垲愃惴ㄏ噍^于其他方法而言，此算法在發(fā)掘各種形狀的聚類方面更具顯著優(yōu)勢［7］?；诰W(wǎng)格的聚類算法，其處理速率和效率要比以單個數(shù)據(jù)為處理對象的高的多，它能夠有效處理高維度的數(shù)據(jù)集，但是聚類結(jié)果的精度可能會降低［8］。而基于模型的聚類算法其主要思想是:為每個聚類都設(shè)定一個數(shù)學(xué)模型，然后借助相應(yīng)模型來劃分聚類。

上述聚類方法各有優(yōu)缺點，因此在實際應(yīng)用中，如何尋找一種合適的聚類算法，從而快速準確地獲得聚類結(jié)果，成為了實現(xiàn)海量空間數(shù)據(jù)可視化的關(guān)鍵問題。

2.2 空間數(shù)據(jù)可視化

目前空間數(shù)據(jù)可視化的主要方法包括了基于熱力圖、基于圓點坐標、基于統(tǒng)計圖、基于密度圖等。

上述的各個空間數(shù)據(jù)可視化方法都具有自己的優(yōu)勢，但同時也存在一定的不足。其中，前兩種方法在數(shù)據(jù)數(shù)量較大的情況下，可能會出現(xiàn)數(shù)據(jù)顯示堆疊的情況，并且還會增加渲染的成本；而后兩種方法，雖然先通過對最初始的空間數(shù)據(jù)加以預(yù)處理，可以從某種角度上使得大數(shù)據(jù)情況下的可視化要求得到了滿足，然而二者都側(cè)重于空間實體在專題維度的統(tǒng)計信息，對實體本身在區(qū)域內(nèi)的分布信息缺乏表達［9］。

因此，本文提出了一種基于聚類的空間數(shù)據(jù)可視化設(shè)計，先利用聚類算法對空間數(shù)據(jù)展開聚類分析，然后將得到的具體結(jié)果通過基于熱力圖的方法進行可視化，從而解決原有可視化方法帶來的一些問題，譬如數(shù)據(jù)擁堵、重復(fù)疊加等。

3 可視化系統(tǒng)設(shè)計

3.1 聚類算法的選擇

由于空間數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)復(fù)雜且具有很大的不確定性，所以，怎樣選取較為適宜的聚類算法進行數(shù)據(jù)分析變得尤為重要。

經(jīng)典的K-means算法是基于劃分的聚類算法的代表性算法且使用十分廣泛的算法，其主要實現(xiàn)過程是:首先指定一個聚類中心，然后借助迭代的方法此中心加以更新［10］，但由于每一個點都被劃分至與其間距最小的聚類中心，因此該算法不能檢測非球面類型的數(shù)據(jù)分布。而基于密度的聚類算法例如DBSCAN算法雖然可以對所有分布種類的數(shù)據(jù)集加以聚類，但是必須指定一個密度閾值，但同時聚類結(jié)果對于密度閾值又非常敏感［11］，這事實上是把參數(shù)的選取權(quán)交付給了使用者，然而在現(xiàn)實里，使用者較難對參數(shù)值作出精準明確，從而導(dǎo)致了不同聚類間密度差別大，這往往使得聚類結(jié)果存在一定的誤差，鄰域范圍難以明確。最近，Alex Rodriguez和Alessandro Laio在《science》上發(fā)表了題目為“Clustering by fast search and find of density peaks”［12］的文章，其中提出了一種全新的聚類算法“Clustering by fast search and find of density peaks”（CFSFDP），該算法克服了以前的聚類算法存在的一些問題，既可以很好地描述數(shù)據(jù)分布，還可以檢測非球面類型的數(shù)據(jù)分布，得到非球形的聚類結(jié)果［13］。因此，本文嘗試采用CFSFDP聚類算法對海量空間進行可視化分析。

3.2 可視化算法設(shè)計

CFSFDP算法的實現(xiàn)基于兩個重要的假設(shè):首先，類簇的中心位于一些密度較低的點內(nèi)；其次，類簇的中心距離其他密度更高的點的距離較大［14］。

結(jié)合空間數(shù)據(jù)的自身的特征與其可視化在實際中實現(xiàn)的要求，對CFSFDP算法在空間數(shù)據(jù)可視化應(yīng)用中的實現(xiàn)過程作如下分析。

算法首先定義了兩個值:樣本點的局部密度密度ρi與該點到局部密度密度更高的點的距離δi。

樣本點i局部密度:

式（1）中的dc為截斷距離。當x＜0時，χ(x)=1；其它情況下，x=0。

樣本點i到局部密度更高的點的距離公式為

由式（2）可知，當點i具有最大局部密度時，δi表示樣本點i到距離點i距離最大的點之間的距離，否則δi表示在所有局部密度高于點i的點中，點i到距離點i距離最短的點之間的距離。從定義能夠獲悉，局部密度最高的點一定為一個聚類中心。

通過運算全部樣本點的局部密度及樣本點至局部密度大的點的間距，能夠獲取到一個決策圖。從此圖中選取出存在較高ρi和較高δi的樣本點，并且將其視作聚類中心。而后，其它樣本點按照局部密度自大至小的次序明確其所從屬的具體的類，每個非核心樣本點的類為周邊范圍里最近的大于該樣本點的點所從屬的聚類。圖例如圖1所示。

圖1 聚類過程說明

以圖1的圖（a）為例，所有點的密度值按照由高到低排列，點1表示密度最高的點。圖1的圖（b），為每個點局部密度ρi及該點到局部密度高的點的間距δi的函數(shù)關(guān)系。利用圖（b）決策圖，可選取具有較高ρi和較高δi的點1和點10，并將其視作聚類中心，其余點依據(jù)密度自大至小的順序賦予所從屬的類簇編號。圖中的三個點26，27，28的δi比較高，然而ρi卻比較低，因而，此三個點屬于不正常點，不可作為類簇中心。在對每一個點指派所屬類別之后，該算法中沒有直接用噪音信號截斷的方法去除噪音點，而是先找出類別間的邊界，然后找出邊界中密度值最高的點，將其密度作為閾值，最后僅僅留下類別中等于或者大于該閾值的點。

從圖2可以看出，在一個非球形類分布圖中，同時加入噪音點后，圖（a）是產(chǎn)生數(shù)據(jù)的概率分布，圖（b）、（c）為從該概率分布中分別產(chǎn)生了4000個和1000個樣本點，圖（d）、（e）依次為圖（b）、（c）兩組數(shù)據(jù)的決策圖，從圖（d）、（e）中可以明顯看出聚類的中心點和個數(shù)。由圖（f）可看出隨著樣本點的增加，錯誤指派點的比率減?。?5］。從圖能夠獲悉，當樣本數(shù)量在1000～10000之間時，聚類結(jié)果的正確率都在99%以上，因此說明該算法具有一定的健壯性。

CFSFDP算法的過程可以概括為，先把局部密度最高且不為異常點的點視作聚類核心，而后把類簇編號自高密度點依次傳到低密度點［16］。該算法可以得到非球形的聚類結(jié)果，并且能夠合理地展示數(shù)據(jù)分布，在復(fù)雜度上也比常用的K-means算法更具優(yōu)勢。同時，該算法只考慮點與點之間的距離，不需要將點映射到向量空間中。

圖2 聚類效果展示

3.3 可視化交互與動畫設(shè)計

可視化系統(tǒng)除了給用戶帶來流暢的視覺展示效果外，另一個重要部分是系統(tǒng)能給用戶帶來良好的交互體驗。交互是用戶通過和系統(tǒng)之間的對話和互動來操作和理解數(shù)據(jù)的過程。本文在熱力圖的基礎(chǔ)上，插入了時間軸，使用戶通過操作時間軸來進行與系統(tǒng)的交互功能，從而展示空間數(shù)據(jù)的時序性。

時間軸是一種較為常見的交互形式，其能夠?qū)?shù)據(jù)時序性展現(xiàn)出來，目前在許多常用的可視化工具中均會用到。時間軸可與不同形式的圖表搭配使用，一方面可以顯示數(shù)據(jù)的時序性，另一方面，可擴大數(shù)據(jù)在有限屏幕空間顯示的范圍。本文將時間軸與熱力圖相搭配，從而表現(xiàn)空間數(shù)據(jù)的時序性［17］。

按照應(yīng)用方法的區(qū)別，可將時間軸分成單點與雙點兩類。單點時間軸只有一個可以拖動或自動移動的浮標，通過改變浮標的位置來展示不同時刻的數(shù)據(jù)分析結(jié)果。雙點時間軸有兩個可以移動的浮標，兩個浮標的位置分別對應(yīng)一個時刻，從而表示一個時間段，通過改變這兩個浮標的位置就可以展示某個時間范圍內(nèi)的數(shù)據(jù)分析結(jié)果。本文選擇采用單點時間軸來實現(xiàn)用戶與系統(tǒng)的交互，通過改變時間軸的位置，展現(xiàn)某一時刻空間數(shù)據(jù)的分布情況，從而展示數(shù)據(jù)的時序性。

4 實證分析

4.1 可視化系統(tǒng)實驗設(shè)計

實驗設(shè)計部分分為三塊:1）直接將圓點坐標投影到地圖上；2）采用K-means算法實現(xiàn)可視化；3）采用CFSFDP算法實現(xiàn)可視化。

基于CFSFDP聚類算法的可視化主要設(shè)計過程是，以某城區(qū)一天24h道路通行車輛數(shù)據(jù)可視化為例，首先，通過數(shù)據(jù)模擬平臺獲得關(guān)于車輛行駛的原始數(shù)據(jù)后，通過操作數(shù)據(jù)庫得到需要分析的相關(guān)字段，包括車輛所在位置的城市、區(qū)域、經(jīng)緯度、時刻等字段，利用統(tǒng)計計算的方法，獲得某個區(qū)域的車輛數(shù)量與位置［18］。然后，采用CFSFDP算法對車輛位置進行聚類分析。

在獲得聚類結(jié)果之后，開始設(shè)計圖形化的表示方法，得到可視化展示結(jié)果。在得到的聚類結(jié)果決策圖的基礎(chǔ)上，創(chuàng)建了從聚類結(jié)果至可視化目標的映射，從而可將獲得的相應(yīng)結(jié)果變成可更加直觀分析的可視化目標，映射關(guān)系如表1所示。

表1 聚類結(jié)果到可視化目標的映射

最后，我們還要為用戶提供必要的交互操作，主要是用戶可根據(jù)時間軸查看不同24h內(nèi)車輛變化情況等。根據(jù)模擬平臺得到的原始數(shù)據(jù)，最終經(jīng)過聚類分析和可視化結(jié)果展示之后，得到了某區(qū)域內(nèi)車輛數(shù)據(jù)可視化效果圖。

根據(jù)實驗設(shè)計分類，最終得到了三類可視化效果圖，效果圖如圖3和圖4所示。漸變色彩的取值反映了該區(qū)域的車輛數(shù)量，且用戶可根據(jù)時間軸查看24h內(nèi)該區(qū)域的車輛數(shù)量變化情況。

圖3 可視化結(jié)果示例

圖4 可視化結(jié)果示例

4.2 試驗結(jié)果對比分析

圖3 （a）是直接將圓點坐標投影到地圖上，由圖可看出，當數(shù)據(jù)量大、且地圖范圍有限的情況下，圓點圖標會發(fā)生擁擠、重合的現(xiàn)象，因此在大數(shù)據(jù)時代已很少采用這種可視化方法。

圖3（b）是采用K-means算法實現(xiàn)可視化，K-means算法首先需要根據(jù)初始聚類中心來確定一個初始劃分，因此初始聚類中心的選擇對聚類結(jié)果有較大的影響，一旦初始值選擇不準確，可能無法得到有效的聚類結(jié)果；而且在K-means算法中，由于K-means算法中的K值是預(yù)先給定的，而選擇合適的K值難以確定。由圖也可看出，雖然得到的聚類可視化結(jié)果可以大致反應(yīng)某區(qū)域的車輛數(shù)量，但結(jié)果卻并沒有準確地反映當前車輛的位置的實際分布情況。

圖4是采用CFSFDP算法實現(xiàn)可視化。對比基于圓點圖標的方法即圖3（a），可看出采用CFSFDP算法得出的聚類可視化結(jié)果最接近實際情況。

5 結(jié)語

本文主要研究了海量空間數(shù)據(jù)的可視化方法，先對現(xiàn)有方法的優(yōu)缺點展開了剖析，并以此為根基，提出了一種基于空間聚類的可視化方法，對相應(yīng)數(shù)據(jù)進行剖析及展示。根據(jù)可視化結(jié)果，用戶可以了解所在區(qū)域交通情況，從而選擇合適的出行路線，從而在一定程度上解決城市交通擁堵的情況。但是該方法在下述方面仍需要加大研究深度:

1）算法優(yōu)化。由于CFSFDP算法需要事先計算好全部數(shù)據(jù)點之間的距離。當樣本特別大時，則整個距離矩陣的內(nèi)存開銷也會很大，因此如何避免直接加載距離矩陣，從而減小內(nèi)存開銷，是該算法需要改進的問題。

2）海量空間數(shù)據(jù)聚類的速度提升。對海量數(shù)據(jù)而言，處理速度是我們始終需要不斷改進的問題，隨著數(shù)據(jù)量越來越大，對于處理速度的要求也會越來越高，所以更快的數(shù)據(jù)處理速度是我們在探索大數(shù)據(jù)問題上不斷追求的目標。