基于空間鄰近的點目標聚類方法

余莉 甘淑 袁希平 李佳田

摘要：空間聚類是空間數據挖掘和知識發現領域的主要研究方向之一，但點目標空間分布密度的不均勻、分布形狀的多樣化，以及“多橋”鏈接問題的存在，使得基于距離和密度的聚類算法不能高效且有效地識別聚集性高的點目標。提出了基于空間鄰近的點目標聚類方法，通過Voronoi建模識別點目標間的空間鄰近關系，并以Voronoi勢力范圍來定義相似度準則，最終構建樹結構以實現點目標的聚集模式識別。實驗將所提算法與Kmeans、具有噪聲的基于密度的聚類（DBSCAN）算法進行比較分析，結果表明算法能夠發現密度不均且任意形狀分布的點目標集群，同時準確劃分“橋”鏈接的簇，適用于空間點目標異質分布下的聚集模式識別。

關鍵詞：空間聚類；Voronoi圖；空間鄰近；橋鏈接

中圖分類號：TP181 文獻標志碼：A

Abstract： Spatial clustering is one of the vital research directions in spatial data mining and knowledge discovery. However， constrained by the complex distribution of uneven density， various shapes and multibridge connection of points， most clustering algorithms based on distance or density cannot identify high aggregative point sets efficiently and effectively. A point clustering method based on spatial proximity was proposed. According to the structure of point Voronoi diagram， adjacent relationships among points were recognized.

The similarity criteria was defined by region of Voronoi， a tree structure was built to recognize pointtarget clusters. The comparison experiments were conducted on the proposed algorithm， Kmeans algorithm and DensityBased Spatial Clustering of Applications with Noise （DBSCAN） algorithm. Results show that the proposed algorithm is capable for identifying clusters in arbitrary shapes， with different densities and connected only at bridges or chains， meanwhile also suitable for aggregative pattern recognition in heterogeneous space.

Key words：spatial clustering； Voronoi diagram； spatial proximity； bridge connection

0 引言

點目標是二維矢量空間中以坐標形式精確表達一系列事件或現象位置分布的幾何要素，其聚類分析采用指定的相似性測度計算目標間位置的接近程度，進而以數學建模發現空間事物聚集分布的感興趣模式，廣泛應用于圖形圖像學、地圖學、氣象學、環境控制、公共衛生與服務等自然、社會及經濟領域。

現有的六類點目標聚類研究[1]主要以距離和密度判斷目標位置的聚集性：

1）距離。以歐氏距離計算點間距離，常用于劃分、層次、模型、圖論聚類。劃分聚類通過定義和迭代優化距離準則函數來實現目標的劃分[2-5]。層次聚類根據點間距離排序，分別采用“從下至上”和“從上之下”兩種策略對點目標進行融合或劃分[6-9]。模型聚類中，模擬昆蟲社交行為和能力的群聚類算法[10-14]采用隨機搜索距離增量優化聚類結果，直至滿足終止條件；模擬神經元對信息的吸收、處理、反饋等能力的自適應共振網絡（Adaptive Resonance Theory 2， ART2）[15]、自組織映射網絡（SelfOrganizing Maps， SOM）[16]及改進算法TreeART2[17]、動態增長自組織映射模型GSOM（Growing SelfOrganizing Map）[18]和TGSOM（Treestructured Growing SelfOrganizing Map）[19]以距離計算輸入模式向量的相似性，并設置相似度閾值判斷獲勝神經元；模擬空間數據場間凝聚力相互作用的場聚類[20-23]以距離構建場強函數計算目標間凝聚力。圖論聚類的典型算法是采用Delaunay三角網剖分點，并以距離計算三角網邊長，進而定義邊長約束逐層刪除無效三角形邊來發現簇類[24-26]。然而，距離相似度僅表征點對點的相似信息，缺乏多點或局部區域目標的聚集特征的判斷，算法需要設置收斂條件并對聚類結果進行迭代優化，不僅計算量大，且收斂條件難以自動定義，同時聚類質量受簇的形狀和異常值影響較大[3]，圖論聚類中三角網以短邊表達“橋”鏈接的點目標，與集群目標間連接的三角形短邊難以區分[24]。

2）密度。通過計算指定范圍內點目標的分布密度判斷聚集程度，常用于密度和網格聚類。密度聚類通過定義搜索區域或區域半徑以及區域內包含目標的最小數量來判斷密度連通性以融合點簇[27-29]。網格聚類采用規則格網劃分點目標，以格網的4鄰域或8鄰域判斷目標鄰近關系，并設置格網內目標密度閾值以合并包含了高密度目標的格網[30-31]。密度是區域內點目標聚集性的整體表征，此類算法能夠識別變密度和不規則形狀的簇，但是密度的計算依賴于用戶對區域半徑、密度閾值、格網尺度等核心參數的設置，聚類質量對先驗知識的高需求限制了算法在大空間數據集的應用。

為了在用戶輸入領域知識最小化的基礎上識別密度不均和任意形態的點簇，本文提出了基于空間鄰近的點目標聚類方法——PCVD（Points Clustering using Voronoi Diagram），鑒于Voronoi結構在捕捉空間離散點間鄰近關系的優勢[32]，本文以點目標Voronoi圖的一階鄰近特性及勢力范圍面積共同定義點目標及其鄰近目標的聚集性強度的判斷準則，并選擇平均統計量自動計算強度閾值，構建樹結構實現類內目標、類邊界目標、離群目標的劃分。實驗部分采用模擬數據集對PCVD、Kmeans和具有噪聲的基于密度的聚類（DensityBased Spatial Clustering of Applications with Noise， DBSCAN）算法進行對比分析，并于結論中對PCVD算法的適用性和伸縮性進行論述。

1 聚集性判斷條件

點目標聚集模式的形成是空間異質性特征的表現，當點目標之間存在相互吸引或相互關聯的空間相互作用時，目標的空間位置分布才會出現有意義的簇[32]。空間目標位置分布的聚集性判斷條件可分為兩方面：1）準確判斷目標間的拓撲鄰近關系，以確認目標間不存在其他任意阻礙二者可視性或連通性的目標；2）能夠精確評估鄰近目標間的真實距離。

1.1 一階鄰近關系

二維空間內的Voronoi圖互不重合且連續鋪蓋，將所有空間目標聯系在一起，隱含地表達力了目標的側向鄰近信息（lateral adjacency information）[33]。陳軍等提出V9I（Voronoiregion based 9 Intersection）模型，定義了兩個空間目標的Voronoi勢力范圍（Influence Region， IR）[33]共邊時屬于空間鄰近關系。

1.2 真實距離測算

由點目標Voronoi圖幾何特性可知，隨著點目標的不均勻分布，其Voronoi圖的勢力范圍亦發生變化，以Voronoi面積定量化，則具體表現為：點目標生長元分布密集的區域，生成的Voronoi面積相對較小；反之，分布稀疏的區域，生成的Voronoi面積相對較大。圖1的近圓形簇采用從內向外，從密集到疏松分布的點目標作為生長元生成點目標Voronoi圖，當空間點目標分布密集時，得到的Voronoi圖面積相對較小，反之，當空間點目標分布稀疏時，得到的Voronoi圖面積相對較大。由此可得，點目標Voronoi面積是表征點目標聚集程度的指標之一。

但從圖1所含兩個聚集性點群及其Voronoi圖細節顯示，每個簇的類內目標的Voronoi圖面積是隨聚集性的增強而減小，可通過判斷Voronoi面積值來識別類內目標；而類邊界目標的Voronoi面積卻是相對較大的，且根據邊界點的分布差異，其Voronoi面積值呈隨機分布，無法直接識別。據觀察，類邊界目標的一階鄰近目標中至少包含一個類內目標，且類邊界目標與該類內目標存在高度聚集性，可識別為同類，因此，在相似度判別時可根據這一規律選擇與邊界目標最近的類內目標來識別類邊界目標。

與常規計算點間距離不同，本文利用點目標生成的Voronoi圖面積來評估單個點目標與其周圍目標聚集性的強弱，定義如下：

3 樹結構聚類

根據聚類準則，PCVD算法搜索同類點目標作為樹節點以構建樹結構，具體表現為：

1）遍歷搜索所有空間點目標，若Q（pi）的值大于Σ，則選取點目標pi作為樹結構的根節點；搜索目標pi的一階Voronoi鄰域內的其他目標，若搜索到的點目標pj滿足準則1，則將目標pj作為pi節點的下一級子節點，但若搜索到的目標pj滿足準則2，則將目標pj作為pi節點的下一級葉子節點；再根據準則1～3，依次對每個子節點的一階Voronoi鄰域內的其他目標進行逐層搜索判斷，直至葉子節點為止；將該棵樹結構中的所有節點進行標記，單樹構建完成。

2）繼續遍歷空間目標，按照1）中的過程，從余下未被標記的空間點目標中選取根節點，并逐層搜索至單樹中再無子節點產生。

3）直至遍歷完所有空間點目標，則樹結構構建結束。

樹的數量即為聚類的個數，每棵樹的根節點和子節點表示類內目標，葉子節點代表類邊界目標，而未被標記的目標則屬于離群目標。

在樹結構的構建過程中，對于葉子節點的判斷有“先到先得”的優勢，即：當兩個類C1和C2距離相對較接近時，依據準則2的判斷，部分邊界目標即是類C1的邊界，又是類C2的邊界，其歸屬取決于構建C1和C2的樹結構的順序，使得邊界目標不一定分布在距離其較近的類中，而發生誤判。PCVD算法在樹結構構建完成后，對葉子節點的歸屬進行驗證：

1）遍歷樹結構中的所有葉子節點；

2）對于單個葉子節點pi，搜索pi的一階Voronoi鄰近目標，比較每個鄰近目標的與葉子節點pi的聚集性強弱，根據準則4，點目標pi與聚集性強度Q最大的目標屬于同類。

葉子節點歸屬的檢驗是對類邊界的修正，可提升聚類結果的準確性。

4 PCVD算法描述

5 實驗與討論

實驗模擬了不同空間分布的點目標集合， 分別以距離計算相似度的Kmeans算法[2]、以密度計算相似度的DBSCAN算法[27]和以Voronoi結構計算聚集性強度的PCVD算法進行對比聚類，旨在對PCVD算法的有效性和穩定性進行驗證。

5.1 模擬數據實驗

1）密度分布不均的點目標。

圖2（a）中以848個點模擬了密度分布不均，且高密度點集被稀疏點集包圍的空間點目標分布。對比實驗結果顯示：圖2（b）為聚類數目k=2的Kmeans算法結果；圖2（c）為鄰域包含最小目標數MinPts=5，鄰域半徑Eps=13時，DBSCAN算法的聚類結果；圖2（d）為縮放因子C=6的PCVD算法結果，可以看出，Kmeans算法雖將點目標分為兩類，但無法識別密度較為稀疏的離群目標，DBSCAN和PCVD算法能夠識別變密度簇中的高密度目標，并準確分為兩類，聚集目標的識別不因離群目標的存在而發生誤判。

2）任意形狀分布的點目標。

圖3（a）中以2947個點模擬了任意形狀分布的空間點目標簇，包含圓環、帶狀、不規則簇。對比實驗結果顯示：圖3（b）為聚類數目k=3的Kmeans算法結果；圖3（c）為MinPts=5， Eps=33時，DBSCAN算法的聚類結果；圖3（d）為C=1的PCVD算法結果，可以看出，Kmeans算法受簇形狀限制，不能準確劃分點目標，DBSCAN和PCVD算法將點目標劃分為三類，聚類結果不受簇形狀的影響。

3）“橋”鏈接的點目標。

圖4（a）中以1460個點模擬了存在多“橋”鏈接分布的空間點目標簇。對比實驗結果顯示：圖4（b）為聚類數目k=2的Kmeans算法結果；圖4（c）為MinPts=5， Eps=28時，DBSCAN算法的聚類結果；圖4（d）為C=7的PCVD算法結果，可以看出，DBSCAN算法不能劃分被“橋”鏈接的類，Kmeans和PCVD算法能夠區分“橋”鏈接的簇。

綜合對比實驗，以距離計算點間相似度的方法適于識別圓形和近圓形簇，對離群點目標敏感，難以準確提取聚集度高的點集；以密度搜索聚類的方法能夠識別密度不均和不規則形態的簇，但難以識別“橋”鏈接的簇，PCVD算法利用Voronoi圖的鄰近關系和面積共同判斷目標聚集性，點目標Voronoi面積越小，聚集性越強，且“橋”目標的Voronoi圖面積一般大于集群目標的Voronoi圖面積，因此能準確識別模擬數據集中的簇，同時算法對離群點的處理較為穩健。

5.2 算法性能分析

1）PCVD算法的時間復雜度。

縱觀PCVD算法聚類過程，若空間待聚類點目標數目為n，聚集性強度值的計算量與目標數量呈線性增加，該階段算法的時間復雜度為O（n）；單一樹結構構建的過程類似于二叉樹構建的過程，建樹階段算法的時間復雜度為O（n log n）；類邊界目標的檢驗亦與葉子節點的數量呈線性增加，最壞情況是所有點目標皆為葉子節點，則該階段算法的時間復雜度為O（n），綜合可得PCVD算法的時間復雜度為O（n log n）。

2）強度閾值的計算。

PCVD算法以平均值計算強度閾值，并以常數C的取值調節識別目標聚集性的強弱，C值越小，發現目標的聚集性越弱，類內包含的離群目標使得類內所有點目標的Voronoi面積平均值越大；反之，C值越大，發現目標的聚集性越強，使得類內所有點目標的Voronoi面積平均值越小。采用5.1節中模擬的三個數據集并順序編號，將常數C取值從1至10，分別計算每個數據集中類1包含的所有點目標的Voronoi面積平均值，繪制類內目標對應的Voronoi面積平均值隨不同常數C取值而變化的折線圖，如圖5所示。

由圖可知，當空間目標簇之間的分布密度近似時，如數據集2，常數C的改變對類內目標的Voronoi面積平均值影響微弱，PCVD算法以聚集性強度的均值（C=1）作為閾值，能夠滿足點目標聚集模式的識別，算法無需自定義參數，如圖3（d）；而當空間目標簇之間的分布密度差異較大或存在空間離群點時，如數據集1和數據集3，稀疏分布目標的聚集性強度值遠遠小于聚集性高的目標的聚集性強度，強度閾值（平均值）因受到離群目標聚集性強度值的影響而偏小，聚類時，需要適當地調整常數C以增加強度閾值，才能夠發現聚集性高的目標。圖5中，數據集1在C=6后，C值的取值對類內目標的Voronoi面積平均值變化影響不大，算法在該處得到合適的聚類結果，同樣，數據集3在C=7后亦使類內目標的Voronoi面積平均值趨于穩定。因此，當常數C由小到大變化過程中，當類內目標的Voronoi面積平均值趨于穩定時，算法能夠發現聚集程度高的點目標簇。

6 結語

PCVD聚類算法的構建有利于點目標位置分布的結構、相互關系、隱含特征等感興趣模式的識別，基于Voronoi圖無縫的空間鄰近關系表達來判斷離散點目標間的可視性，并以聚集性強度來定量計算點目標與周圍目標的聚集性，最終構建樹結構搜索集群目標聚類，并對類邊界目標進行優化。模擬數據實驗證明，PCVD算法能夠識別密度不均、簇形狀任意分布和“橋”鏈接的聚類，對離群點的處理穩健，聚類結果無模式混交現象。同時，算法具有良好的伸縮性，其聚類思想不僅適用于點目標，以可擴展至線、面目標的聚集模式識別，依賴于線、面Voronoi圖的生成，根據目標形狀特征構建聚集性強度測算方法以實現聚類。

PCVD算法的自適應性取決于聚集目標的空間分布：當聚集目標之間密度近似時，距離函數閾值取均值則可以自動識別目標簇； 但當聚集目標之間密度差異較大時，則需要主動定義常數C的取值以調節得到滿意的聚類粒度，這一過程降低了算法的自適應性。常數C取值的變化是聚類粒度在不同聚類層次之間的體現，如何讓算法能夠自動識別C的取值，實現多尺度的聚類是后續研究中亟待討論和解決的問題。

參考文獻：

[1]ESTIVILLCASTRO V， LEE I. Argument free clustering for large spatial pointdata sets via boundary extraction from Delaunay diagram[J]. Computers， Environment and Urban Systems， 2002， 26（4）： 315-334.

[2]MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]// Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Chicago： University of Chicago Press， 1967， 1： 281-297.

[3]KAUFMAN L， ROUSSEEUW P J. Finding Groups in Data： an Introduction to Cluster Analysis[M]. New York： John Wiley & Sons， 1990：38-42.

[4]RAYMOND T N， HAN J W. Efficient and effective clustering methods for spatial data mining[C]// Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco， CA： Morgan Kaufmann Publishers， 1994： 144-155.

[5]ESTER M， KRIEGEL H P， XU X. Knowledge discovery in large spatial databases： Focusing techniques for efficient class identification [C]// Proceedings of the 4th International Symposium on Large Spatial Databases. Berlin： SpringerVerlag， 1995： 67-82.

[6]ZHANG T， RAMAKRISHNAN R， LIVNY M. BIRCH： an efficient data clustering method for very large databases[C]// Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. New York： ACM， 1996： 103-114.

[7]GUHA S， RASTOGI R， SHIM K. CURE： an efficient clustering algorithm for large databases[C]// Proceedings of the 1998 ACMSIGMOD International Conference on Management of Data. New York： ACM， 1998： 73-84.

[8]GUHA S， RASTOGI R， SHIM K. ROCK： A robust clustering algorithm for categorical attributes[C]// Proceedings of the 15th International Conference on Data Engineering. Washington， DC： IEEE Computer Society， 1999： 512-521.

[9]DASH M， LIU H， SCHEUERMANN P， et al. Fast hierarchical clustering and its validation[J]. Data & Knowledge Engineering， 2003， 44（1）： 109-138.

[10]HANDL J， KNOWLES J， DORIGO M. Antbased clustering and topographic mapping[J]. Artificial Life， 2006， 12（1）： 35-61.

[11]LUMER E D， FAIETA B. Diversity and adaptation in populations of clustering ants[C]// Proceedings of the 3rd International Conference on Simulation of Adaptive Behavior： from Animals to Animats 3. Cambridge： MIT Press， 1994， 1：501-508.

[12]MONMARCH N， SLIMANE M， VENTURINI G. On improving Clustering in Numerical Databases with Artificial Ants[M]. Berlin： Springer， 1999： 626-635.

[13]YANG Y， KAMEL M S. An aggregated clustering approach using multiant colonies algorithms [J]. Pattern Recognition， 2006， 39（7）：1278-1289.

[14]TAN S C， TING K M， TENG S W. A general stochastic clustering method for automatic cluster discovery[J]. Pattern Recognition， 2011， 44（10）： 2786-2799.

[15]CARPENTER G A， and GROSSBERG S. ART2： selforganization of stable category recognition codes for analog input patterns [J]. Applied Optics， 1987， 26（23）： 4919-4930.

[16]KOHONEN T. SelfOrganization and Associative Memory [M]. Berlin： SpringerVerlag， 1989： 119-157.

[17]余莉， 李佳田， 李佳，等. 二維空間聚類的樹ART2模型[J]. 計算機應用， 2011， 31（5）： 1328-1330. （YU L， LI J T， LI J， et al. TreeART2 model for clustering spatial data in twodimensional space[J]. Journal of Computer Applications， 2011， 31（5）： 1328-1330.）

[18]HSU A L， HALGAMUGE S K. Enhancement of topology preservation and hierarchical dynamic selforganising maps for data visualization [J]. International Journal of Approximate Reasoning， 2003， 32（2/3）：259-279.

[19]王莉， 王正歐. TGSOM：一種用于數據聚類的動態自組織映射神經網絡[J]. 電子與信息學報， 2003， 25（3）： 313-319. （WANG L， WANG Z O. TGSOM： a new dynamic selforganizing maps for data clustering[J]. Journal of Electronics and Information Technology， 2003， 25（3）： 313-319.）

[20]HINNEBURG A， KEIM D A. An efficient approach to clustering in large multimedia databases with noise[C]// Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining. Berlin： SpringerVerlag， 1998， 98： 58-65.

[21]淦文燕， 李德毅， 王建民. 一種基于數據場的層次聚類方法[J]. 電子學報， 2006， 34（2）： 258-262. （GAN W Y， LI D Y， WANG J M. A hierarchical clustering method based on data fields [J]. Acta Electronica Sinica， 2006， 34（2）： 258-262.）

[22]NOSOVSKIY G V， LIU D， SOURINA O. Automatic clustering and boundary detection algorithm based on adaptive influence function[J]. Pattern Recognition， 2008， 41（9）： 2757-2776.

[23]鄧敏， 彭東亮， 劉啟亮，等. 一種基于場論的層次空間聚類算法[J]. 武漢大學學報（信息科學版）， 2011， 36（7）： 847-852. （DENG M， PENG D L， LIU Q L， et al. A hierarchical spatial clustering algorithm based on field theory [J]. Geomatics and Information Science of Wuhan University， 2011， 36（7）： 847-852.）

[24]ESTIVILLCASTRO V， LEE I. AMOEBA： hierarchical clustering based on spatial proximity using Delaunay diagram[C]// Proceedings of the 9th International Symposium on Spatial Data Handling. Berlin： SpringerVerlag， 2000， 26-41.

[25]ESTIVILLCASTRO V， LEE I. Multilevel clustering and its visualization for exploratory data analysis[J]. GeoInformatica， 2002， 6（2）： 123-152.

[26]LIU D， NOSOVSKIY G V， SOURINA O. Effective clustering and boundary detection algorithm based on Delaunay triangulation[J]. Pattern Recognition Letters， 2008， 29（9）： 1261-1273.

[27]ESTER M， KRIEGEL H P， SANDER J， et al. A densitybased algorithm for discovering clusters in large spatial databases with noise[C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park， California： AAAI Press， 1996： 226-231.

[28]PARKER J K， DOWNS J A. Footprint generation using fuzzyneighborhood clustering[J]. GeoInformatica， 2013， 17（2）： 285-299.

[29]武佳薇， 李雄飛， 孫濤，等. 鄰域平衡密度聚類算法[J]. 計算機研究與發展， 2010， 47（6）： 1044-1052. （WU J W， LI X F， SUN T， et al. A densitybased clustering algorithm concerning neighborhood balance [J]. Journal of Computer Research and Development， 2010， 47（6）： 1044-1052.）

[30]WANG W， YANG J， MUNTZ R. STING： a statistical information grid approach to spatial data mining[C]// Proceedings of the 23rd International Conference on Very Large Databases. San Francisco， CA： Morgan Kaufmann Publishers Inc， 1997： 186-195.

[31]AGRAWAL R， GEHRKE J， GUNOPULOS D， et al. Automatic subspace clustering of high dimensional data[J]. Data Mining and Knowledge Discovery， 2005， 11（1）： 5-33.

[32]GOLD C M. Problems with handling spatial data— the Voronoi approach[J]. CISM Journal， 1991，45（1）： 65-80.

[33]陳軍， 趙仁亮. Voronoi動態空間數據模型[M]. 北京： 測繪出版社， 2002： 24-47. （CHEN J， ZHAO R L. Voronoi Dynamic Spatial Data Model[M]. Beijing： Surveying and Mapping Press， 2002： 24-47.）