基于聚類的海量空間數據可視化研究與應用?

楊 璇 劉 宇

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

1 引言

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

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

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

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

2 相關工作

2.1 空間聚類算法

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

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

上述聚類方法各有優缺點，因此在實際應用中，如何尋找一種合適的聚類算法，從而快速準確地獲得聚類結果，成為了實現海量空間數據可視化的關鍵問題。

2.2 空間數據可視化

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

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

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

3 可視化系統設計

3.1 聚類算法的選擇

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

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

3.2 可視化算法設計

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

結合空間數據的自身的特征與其可視化在實際中實現的要求，對CFSFDP算法在空間數據可視化應用中的實現過程作如下分析。

算法首先定義了兩個值:樣本點的局部密度密度ρ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的函數關系。利用圖（b）決策圖，可選取具有較高ρi和較高δi的點1和點10，并將其視作聚類中心，其余點依據密度自大至小的順序賦予所從屬的類簇編號。圖中的三個點26，27，28的δi比較高，然而ρi卻比較低，因而，此三個點屬于不正常點，不可作為類簇中心。在對每一個點指派所屬類別之后，該算法中沒有直接用噪音信號截斷的方法去除噪音點，而是先找出類別間的邊界，然后找出邊界中密度值最高的點，將其密度作為閾值，最后僅僅留下類別中等于或者大于該閾值的點。

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

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

圖2 聚類效果展示

3.3 可視化交互與動畫設計

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

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

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

4 實證分析

4.1 可視化系統實驗設計

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

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

在獲得聚類結果之后，開始設計圖形化的表示方法，得到可視化展示結果。在得到的聚類結果決策圖的基礎上，創建了從聚類結果至可視化目標的映射，從而可將獲得的相應結果變成可更加直觀分析的可視化目標，映射關系如表1所示。

表1 聚類結果到可視化目標的映射

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

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

圖3 可視化結果示例

圖4 可視化結果示例

4.2 試驗結果對比分析

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

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

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

5 結語

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

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

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