余莉 甘淑 袁希平 李佳田

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

關(guān)鍵詞：空間聚類(lèi)；Voronoi圖；空間鄰近；橋鏈接

中圖分類(lèi)號(hào)：TP181 文獻(xiàn)標(biāo)志碼：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 引言

點(diǎn)目標(biāo)是二維矢量空間中以坐標(biāo)形式精確表達(dá)一系列事件或現(xiàn)象位置分布的幾何要素，其聚類(lèi)分析采用指定的相似性測(cè)度計(jì)算目標(biāo)間位置的接近程度，進(jìn)而以數(shù)學(xué)建模發(fā)現(xiàn)空間事物聚集分布的感興趣模式，廣泛應(yīng)用于圖形圖像學(xué)、地圖學(xué)、氣象學(xué)、環(huán)境控制、公共衛(wèi)生與服務(wù)等自然、社會(huì)及經(jīng)濟(jì)領(lǐng)域。

現(xiàn)有的六類(lèi)點(diǎn)目標(biāo)聚類(lèi)研究[1]主要以距離和密度判斷目標(biāo)位置的聚集性：

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

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

為了在用戶(hù)輸入領(lǐng)域知識(shí)最小化的基礎(chǔ)上識(shí)別密度不均和任意形態(tài)的點(diǎn)簇，本文提出了基于空間鄰近的點(diǎn)目標(biāo)聚類(lèi)方法——PCVD（Points Clustering using Voronoi Diagram），鑒于Voronoi結(jié)構(gòu)在捕捉空間離散點(diǎn)間鄰近關(guān)系的優(yōu)勢(shì)[32]，本文以點(diǎn)目標(biāo)Voronoi圖的一階鄰近特性及勢(shì)力范圍面積共同定義點(diǎn)目標(biāo)及其鄰近目標(biāo)的聚集性強(qiáng)度的判斷準(zhǔn)則，并選擇平均統(tǒng)計(jì)量自動(dòng)計(jì)算強(qiáng)度閾值，構(gòu)建樹(shù)結(jié)構(gòu)實(shí)現(xiàn)類(lèi)內(nèi)目標(biāo)、類(lèi)邊界目標(biāo)、離群目標(biāo)的劃分。實(shí)驗(yàn)部分采用模擬數(shù)據(jù)集對(duì)PCVD、Kmeans和具有噪聲的基于密度的聚類(lèi)（DensityBased Spatial Clustering of Applications with Noise， DBSCAN）算法進(jìn)行對(duì)比分析，并于結(jié)論中對(duì)PCVD算法的適用性和伸縮性進(jìn)行論述。

1 聚集性判斷條件

點(diǎn)目標(biāo)聚集模式的形成是空間異質(zhì)性特征的表現(xiàn)，當(dāng)點(diǎn)目標(biāo)之間存在相互吸引或相互關(guān)聯(lián)的空間相互作用時(shí)，目標(biāo)的空間位置分布才會(huì)出現(xiàn)有意義的簇[32]?？臻g目標(biāo)位置分布的聚集性判斷條件可分為兩方面：1）準(zhǔn)確判斷目標(biāo)間的拓?fù)溧徑P(guān)系，以確認(rèn)目標(biāo)間不存在其他任意阻礙二者可視性或連通性的目標(biāo)；2）能夠精確評(píng)估鄰近目標(biāo)間的真實(shí)距離。

1.1 一階鄰近關(guān)系

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

1.2 真實(shí)距離測(cè)算

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

但從圖1所含兩個(gè)聚集性點(diǎn)群及其Voronoi圖細(xì)節(jié)顯示，每個(gè)簇的類(lèi)內(nèi)目標(biāo)的Voronoi圖面積是隨聚集性的增強(qiáng)而減小，可通過(guò)判斷Voronoi面積值來(lái)識(shí)別類(lèi)內(nèi)目標(biāo)；而類(lèi)邊界目標(biāo)的Voronoi面積卻是相對(duì)較大的，且根據(jù)邊界點(diǎn)的分布差異，其Voronoi面積值呈隨機(jī)分布，無(wú)法直接識(shí)別。據(jù)觀察，類(lèi)邊界目標(biāo)的一階鄰近目標(biāo)中至少包含一個(gè)類(lèi)內(nèi)目標(biāo)，且類(lèi)邊界目標(biāo)與該類(lèi)內(nèi)目標(biāo)存在高度聚集性，可識(shí)別為同類(lèi)，因此，在相似度判別時(shí)可根據(jù)這一規(guī)律選擇與邊界目標(biāo)最近的類(lèi)內(nèi)目標(biāo)來(lái)識(shí)別類(lèi)邊界目標(biāo)。

與常規(guī)計(jì)算點(diǎn)間距離不同，本文利用點(diǎn)目標(biāo)生成的Voronoi圖面積來(lái)評(píng)估單個(gè)點(diǎn)目標(biāo)與其周?chē)繕?biāo)聚集性的強(qiáng)弱，定義如下：

3 樹(shù)結(jié)構(gòu)聚類(lèi)

根據(jù)聚類(lèi)準(zhǔn)則，PCVD算法搜索同類(lèi)點(diǎn)目標(biāo)作為樹(shù)節(jié)點(diǎn)以構(gòu)建樹(shù)結(jié)構(gòu)，具體表現(xiàn)為：

1）遍歷搜索所有空間點(diǎn)目標(biāo)，若Q（pi）的值大于Σ，則選取點(diǎn)目標(biāo)pi作為樹(shù)結(jié)構(gòu)的根節(jié)點(diǎn)；搜索目標(biāo)pi的一階Voronoi鄰域內(nèi)的其他目標(biāo)，若搜索到的點(diǎn)目標(biāo)pj滿(mǎn)足準(zhǔn)則1，則將目標(biāo)pj作為pi節(jié)點(diǎn)的下一級(jí)子節(jié)點(diǎn)，但若搜索到的目標(biāo)pj滿(mǎn)足準(zhǔn)則2，則將目標(biāo)pj作為pi節(jié)點(diǎn)的下一級(jí)葉子節(jié)點(diǎn)；再根據(jù)準(zhǔn)則1～3，依次對(duì)每個(gè)子節(jié)點(diǎn)的一階Voronoi鄰域內(nèi)的其他目標(biāo)進(jìn)行逐層搜索判斷，直至葉子節(jié)點(diǎn)為止；將該棵樹(shù)結(jié)構(gòu)中的所有節(jié)點(diǎn)進(jìn)行標(biāo)記，單樹(shù)構(gòu)建完成。

2）繼續(xù)遍歷空間目標(biāo)，按照1）中的過(guò)程，從余下未被標(biāo)記的空間點(diǎn)目標(biāo)中選取根節(jié)點(diǎn)，并逐層搜索至單樹(shù)中再無(wú)子節(jié)點(diǎn)產(chǎn)生。

3）直至遍歷完所有空間點(diǎn)目標(biāo)，則樹(shù)結(jié)構(gòu)構(gòu)建結(jié)束。

樹(shù)的數(shù)量即為聚類(lèi)的個(gè)數(shù)，每棵樹(shù)的根節(jié)點(diǎn)和子節(jié)點(diǎn)表示類(lèi)內(nèi)目標(biāo)，葉子節(jié)點(diǎn)代表類(lèi)邊界目標(biāo)，而未被標(biāo)記的目標(biāo)則屬于離群目標(biāo)。

在樹(shù)結(jié)構(gòu)的構(gòu)建過(guò)程中，對(duì)于葉子節(jié)點(diǎn)的判斷有“先到先得”的優(yōu)勢(shì)，即：當(dāng)兩個(gè)類(lèi)C1和C2距離相對(duì)較接近時(shí)，依據(jù)準(zhǔn)則2的判斷，部分邊界目標(biāo)即是類(lèi)C1的邊界，又是類(lèi)C2的邊界，其歸屬取決于構(gòu)建C1和C2的樹(shù)結(jié)構(gòu)的順序，使得邊界目標(biāo)不一定分布在距離其較近的類(lèi)中，而發(fā)生誤判。PCVD算法在樹(shù)結(jié)構(gòu)構(gòu)建完成后，對(duì)葉子節(jié)點(diǎn)的歸屬進(jìn)行驗(yàn)證：

1）遍歷樹(shù)結(jié)構(gòu)中的所有葉子節(jié)點(diǎn)；

2）對(duì)于單個(gè)葉子節(jié)點(diǎn)pi，搜索pi的一階Voronoi鄰近目標(biāo)，比較每個(gè)鄰近目標(biāo)的與葉子節(jié)點(diǎn)pi的聚集性強(qiáng)弱，根據(jù)準(zhǔn)則4，點(diǎn)目標(biāo)pi與聚集性強(qiáng)度Q最大的目標(biāo)屬于同類(lèi)。

葉子節(jié)點(diǎn)歸屬的檢驗(yàn)是對(duì)類(lèi)邊界的修正，可提升聚類(lèi)結(jié)果的準(zhǔn)確性。

4 PCVD算法描述

5 實(shí)驗(yàn)與討論

實(shí)驗(yàn)?zāi)M了不同空間分布的點(diǎn)目標(biāo)集合， 分別以距離計(jì)算相似度的Kmeans算法[2]、以密度計(jì)算相似度的DBSCAN算法[27]和以Voronoi結(jié)構(gòu)計(jì)算聚集性強(qiáng)度的PCVD算法進(jìn)行對(duì)比聚類(lèi)，旨在對(duì)PCVD算法的有效性和穩(wěn)定性進(jìn)行驗(yàn)證。

5.1 模擬數(shù)據(jù)實(shí)驗(yàn)

1）密度分布不均的點(diǎn)目標(biāo)。

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

2）任意形狀分布的點(diǎn)目標(biāo)。

圖3（a）中以2947個(gè)點(diǎn)模擬了任意形狀分布的空間點(diǎn)目標(biāo)簇，包含圓環(huán)、帶狀、不規(guī)則簇。對(duì)比實(shí)驗(yàn)結(jié)果顯示：圖3（b）為聚類(lèi)數(shù)目k=3的Kmeans算法結(jié)果；圖3（c）為MinPts=5， Eps=33時(shí)，DBSCAN算法的聚類(lèi)結(jié)果；圖3（d）為C=1的PCVD算法結(jié)果，可以看出，Kmeans算法受簇形狀限制，不能準(zhǔn)確劃分點(diǎn)目標(biāo)，DBSCAN和PCVD算法將點(diǎn)目標(biāo)劃分為三類(lèi)，聚類(lèi)結(jié)果不受簇形狀的影響。

3）“橋”鏈接的點(diǎn)目標(biāo)。

圖4（a）中以1460個(gè)點(diǎn)模擬了存在多“橋”鏈接分布的空間點(diǎn)目標(biāo)簇。對(duì)比實(shí)驗(yàn)結(jié)果顯示：圖4（b）為聚類(lèi)數(shù)目k=2的Kmeans算法結(jié)果；圖4（c）為MinPts=5， Eps=28時(shí)，DBSCAN算法的聚類(lèi)結(jié)果；圖4（d）為C=7的PCVD算法結(jié)果，可以看出，DBSCAN算法不能劃分被“橋”鏈接的類(lèi)，Kmeans和PCVD算法能夠區(qū)分“橋”鏈接的簇。

綜合對(duì)比實(shí)驗(yàn)，以距離計(jì)算點(diǎn)間相似度的方法適于識(shí)別圓形和近圓形簇，對(duì)離群點(diǎn)目標(biāo)敏感，難以準(zhǔn)確提取聚集度高的點(diǎn)集；以密度搜索聚類(lèi)的方法能夠識(shí)別密度不均和不規(guī)則形態(tài)的簇，但難以識(shí)別“橋”鏈接的簇，PCVD算法利用Voronoi圖的鄰近關(guān)系和面積共同判斷目標(biāo)聚集性，點(diǎn)目標(biāo)Voronoi面積越小，聚集性越強(qiáng)，且“橋”目標(biāo)的Voronoi圖面積一般大于集群目標(biāo)的Voronoi圖面積，因此能準(zhǔn)確識(shí)別模擬數(shù)據(jù)集中的簇，同時(shí)算法對(duì)離群點(diǎn)的處理較為穩(wěn)健。

5.2 算法性能分析

1）PCVD算法的時(shí)間復(fù)雜度。

縱觀PCVD算法聚類(lèi)過(guò)程，若空間待聚類(lèi)點(diǎn)目標(biāo)數(shù)目為n，聚集性強(qiáng)度值的計(jì)算量與目標(biāo)數(shù)量呈線(xiàn)性增加，該階段算法的時(shí)間復(fù)雜度為O（n）；單一樹(shù)結(jié)構(gòu)構(gòu)建的過(guò)程類(lèi)似于二叉樹(shù)構(gòu)建的過(guò)程，建樹(shù)階段算法的時(shí)間復(fù)雜度為O（n log n）；類(lèi)邊界目標(biāo)的檢驗(yàn)亦與葉子節(jié)點(diǎn)的數(shù)量呈線(xiàn)性增加，最壞情況是所有點(diǎn)目標(biāo)皆為葉子節(jié)點(diǎn)，則該階段算法的時(shí)間復(fù)雜度為O（n），綜合可得PCVD算法的時(shí)間復(fù)雜度為O（n log n）。

2）強(qiáng)度閾值的計(jì)算。

PCVD算法以平均值計(jì)算強(qiáng)度閾值，并以常數(shù)C的取值調(diào)節(jié)識(shí)別目標(biāo)聚集性的強(qiáng)弱，C值越小，發(fā)現(xiàn)目標(biāo)的聚集性越弱，類(lèi)內(nèi)包含的離群目標(biāo)使得類(lèi)內(nèi)所有點(diǎn)目標(biāo)的Voronoi面積平均值越大；反之，C值越大，發(fā)現(xiàn)目標(biāo)的聚集性越強(qiáng)，使得類(lèi)內(nèi)所有點(diǎn)目標(biāo)的Voronoi面積平均值越小。采用5.1節(jié)中模擬的三個(gè)數(shù)據(jù)集并順序編號(hào)，將常數(shù)C取值從1至10，分別計(jì)算每個(gè)數(shù)據(jù)集中類(lèi)1包含的所有點(diǎn)目標(biāo)的Voronoi面積平均值，繪制類(lèi)內(nèi)目標(biāo)對(duì)應(yīng)的Voronoi面積平均值隨不同常數(shù)C取值而變化的折線(xiàn)圖，如圖5所示。

由圖可知，當(dāng)空間目標(biāo)簇之間的分布密度近似時(shí)，如數(shù)據(jù)集2，常數(shù)C的改變對(duì)類(lèi)內(nèi)目標(biāo)的Voronoi面積平均值影響微弱，PCVD算法以聚集性強(qiáng)度的均值（C=1）作為閾值，能夠滿(mǎn)足點(diǎn)目標(biāo)聚集模式的識(shí)別，算法無(wú)需自定義參數(shù)，如圖3（d）；而當(dāng)空間目標(biāo)簇之間的分布密度差異較大或存在空間離群點(diǎn)時(shí)，如數(shù)據(jù)集1和數(shù)據(jù)集3，稀疏分布目標(biāo)的聚集性強(qiáng)度值遠(yuǎn)遠(yuǎn)小于聚集性高的目標(biāo)的聚集性強(qiáng)度，強(qiáng)度閾值（平均值）因受到離群目標(biāo)聚集性強(qiáng)度值的影響而偏小，聚類(lèi)時(shí)，需要適當(dāng)?shù)卣{(diào)整常數(shù)C以增加強(qiáng)度閾值，才能夠發(fā)現(xiàn)聚集性高的目標(biāo)。圖5中，數(shù)據(jù)集1在C=6后，C值的取值對(duì)類(lèi)內(nèi)目標(biāo)的Voronoi面積平均值變化影響不大，算法在該處得到合適的聚類(lèi)結(jié)果，同樣，數(shù)據(jù)集3在C=7后亦使類(lèi)內(nèi)目標(biāo)的Voronoi面積平均值趨于穩(wěn)定。因此，當(dāng)常數(shù)C由小到大變化過(guò)程中，當(dāng)類(lèi)內(nèi)目標(biāo)的Voronoi面積平均值趨于穩(wěn)定時(shí)，算法能夠發(fā)現(xiàn)聚集程度高的點(diǎn)目標(biāo)簇。

6 結(jié)語(yǔ)

PCVD聚類(lèi)算法的構(gòu)建有利于點(diǎn)目標(biāo)位置分布的結(jié)構(gòu)、相互關(guān)系、隱含特征等感興趣模式的識(shí)別，基于Voronoi圖無(wú)縫的空間鄰近關(guān)系表達(dá)來(lái)判斷離散點(diǎn)目標(biāo)間的可視性，并以聚集性強(qiáng)度來(lái)定量計(jì)算點(diǎn)目標(biāo)與周?chē)繕?biāo)的聚集性，最終構(gòu)建樹(shù)結(jié)構(gòu)搜索集群目標(biāo)聚類(lèi)，并對(duì)類(lèi)邊界目標(biāo)進(jìn)行優(yōu)化。模擬數(shù)據(jù)實(shí)驗(yàn)證明，PCVD算法能夠識(shí)別密度不均、簇形狀任意分布和“橋”鏈接的聚類(lèi)，對(duì)離群點(diǎn)的處理穩(wěn)健，聚類(lèi)結(jié)果無(wú)模式混交現(xiàn)象。同時(shí)，算法具有良好的伸縮性，其聚類(lèi)思想不僅適用于點(diǎn)目標(biāo)，以可擴(kuò)展至線(xiàn)、面目標(biāo)的聚集模式識(shí)別，依賴(lài)于線(xiàn)、面Voronoi圖的生成，根據(jù)目標(biāo)形狀特征構(gòu)建聚集性強(qiáng)度測(cè)算方法以實(shí)現(xiàn)聚類(lèi)。

PCVD算法的自適應(yīng)性取決于聚集目標(biāo)的空間分布：當(dāng)聚集目標(biāo)之間密度近似時(shí)，距離函數(shù)閾值取均值則可以自動(dòng)識(shí)別目標(biāo)簇； 但當(dāng)聚集目標(biāo)之間密度差異較大時(shí)，則需要主動(dòng)定義常數(shù)C的取值以調(diào)節(jié)得到滿(mǎn)意的聚類(lèi)粒度，這一過(guò)程降低了算法的自適應(yīng)性。常數(shù)C取值的變化是聚類(lèi)粒度在不同聚類(lèi)層次之間的體現(xiàn)，如何讓算法能夠自動(dòng)識(shí)別C的取值，實(shí)現(xiàn)多尺度的聚類(lèi)是后續(xù)研究中亟待討論和解決的問(wèn)題。

參考文獻(xiàn)：

[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]余莉， 李佳田， 李佳，等. 二維空間聚類(lèi)的樹(shù)ART2模型[J]. 計(jì)算機(jī)應(yīng)用， 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：一種用于數(shù)據(jù)聚類(lèi)的動(dòng)態(tài)自組織映射神經(jīng)網(wǎng)絡(luò)[J]. 電子與信息學(xué)報(bào)， 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]淦文燕， 李德毅， 王建民. 一種基于數(shù)據(jù)場(chǎng)的層次聚類(lèi)方法[J]. 電子學(xué)報(bào)， 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]鄧敏， 彭東亮， 劉啟亮，等. 一種基于場(chǎng)論的層次空間聚類(lèi)算法[J]. 武漢大學(xué)學(xué)報(bào)（信息科學(xué)版）， 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]武佳薇， 李雄飛， 孫濤，等. 鄰域平衡密度聚類(lèi)算法[J]. 計(jì)算機(jī)研究與發(fā)展， 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動(dòng)態(tài)空間數(shù)據(jù)模型[M]. 北京： 測(cè)繪出版社， 2002： 24-47. （CHEN J， ZHAO R L. Voronoi Dynamic Spatial Data Model[M]. Beijing： Surveying and Mapping Press， 2002： 24-47.）