余 莉,甘 淑,袁希平,楊明龍

昆明理工大學國土資源工程學院,云南昆明 650093

綜合線面特征分布的點目標多尺度聚類方法

余 莉,甘 淑,袁希平,楊明龍

昆明理工大學國土資源工程學院,云南昆明 650093

考慮空間數(shù)據(jù)分布的復雜性與不連續(xù)性,提出了一種點目標聚類方法。算法利用全要素Voronoi圖準確識別與表達點目標與線面實體的空間相關性；根據(jù)點目標位置分布特征計算面積閾值來控制聚類的粒度,同時以空間尺度變化下面積閾值的恒定作為判斷尺度收斂的條件,實現(xiàn)點目標的多尺度劃分,時間復雜度為O(n log n)。經試驗驗證,聚類尺度隨點目標分布特征自適應收斂,算法無須自定義參數(shù),能夠有效地發(fā)現(xiàn)受線面目標約束的任意形態(tài)點目標集群,對異常值處理穩(wěn)健。

空間聚類；多尺度；全要素Voronoi圖；約束

1 引 言

點目標多尺度聚類是空間數(shù)據(jù)知識發(fā)現(xiàn)的重要技術之一[1],其采用準確的相似性測度計算點目標間的鄰近程度,進而自適應地解譯與評估不同空間尺度下目標的分布特征與模式。然而,空間多尺度聚類有兩方面特殊性:①線面目標的存在易造成點目標間的不通視或不通達現(xiàn)象[2],直接以歐氏距離判斷點目標遠近易發(fā)生聚類模式混交;②點目標聚散性具有顯著的多尺度特征,不同的空間幅度范圍內發(fā)現(xiàn)不同聚類粒度所遵循的規(guī)律與體現(xiàn)的特征不盡相同,單一相似度閾值難以隨空間尺度變化準確地劃分點目標[3]。

針對前者,已有研究將線面目標視為障礙,增加了障礙約束下點目標真實距離的判別和計算,典型算法有:①直接距離法,根據(jù)點與線面特征點的連線計算繞行障礙的最小距離,COD-CLARANS[4]、DBCluC[5]、OETTC-MEANS-CLASA[6]、DBCOD[7]、OBS-UK-means[8]等,不規(guī)則線面目標的約減易造成幾何特征丟失且計算復雜;②柵格距離法,二值化矢量數(shù)據(jù),并運用數(shù)學形態(tài)學算子進行二值圖像的降噪和融合聚類[9-10],但限于矢柵轉換時的精度損失;③鄰近判斷法,采用簡單、規(guī)律且平鋪的幾何結構剖分空間并獲取目標的鄰近關系和幾何特征來實現(xiàn)聚類,基于Delaunay三角網(wǎng)的AUTOCLUST＋及其改進算法[11-13]、基于Voronoi圖的聚類算法[14-15],但從符合人類空間認知的角度而言,Voronoi剖分比Delaunay剖分更為清晰。而對于后者,聚類尺度特殊性的識別需要構建類融合的多尺度模型來實現(xiàn),常見算法有基于尺度空間理論的聚類[3,16-17]、以鄰近關系判別的AMOEBA層次聚類[18]、多尺度譜聚類[19]、基于徑向基函數(shù)網(wǎng)絡的多核劃分[20]等,但以上算法皆需預定義多尺度閾值,難以實現(xiàn)聚類尺度的自適應收斂。

縱觀現(xiàn)有算法的優(yōu)缺點,本文提出了考慮線面分布的點目標多尺度聚類方法(multi-scale spatial clustering,MSSC),鑒于Voronoi圖對點目標鄰近關系的準確表達及剖分的直觀完整[21],通過生成點線面目標的全要素Voronoi圖,提取點線面的鄰近關系及計算Voronoi勢力范圍;進而計算點集的類內平均面積作為面積閾值,將互為自然鄰居且其Voronoi圖面積小于閾值的點進行融合實現(xiàn)聚類;同時,在不同空間尺度下算法自適應地計算各子類的面積閾值,使得聚類粒度由粗到細劃分,并于尺度穩(wěn)定時收斂。MSSC算法無須自定義參數(shù),可識別異常值并發(fā)現(xiàn)任意形態(tài)的類。

2 Voronoi剖分下的點目標聚散特征表達

空間實體以點線面的形式存儲于空間數(shù)據(jù)庫中,當考慮線面目標約束下的點目標聚類時,必須準確識別3種要素間的空間關系。Voronoi圖是一種基于場(field-based)的空間數(shù)據(jù)模型,是對二維空間的不重疊鋪蓋,本文通過提取線面要素邊界的幾何特征點與點目標合并生成Voronoi圖,并將同一要素的特征點Voronoi圖進行合并,得到全要素Voronoi圖,進而以“鄰近關系”與“勢力范圍”兩項衡量標準來識別線面目標阻隔下的點目標聚集分布特征。

2.1 鄰近關系

線面的阻隔使得點目標的聚集不僅是直線距離的靠近,還必須考慮位置是否鄰近。如圖1(a)所示,點目標A與B被線要素阻隔,二者的實際距離需要繞線而測,較為遙遠,常規(guī)的以直線距離計算遠近的方法不能正確判斷點目標的接近程度,與空間認知相悖。MSSC算法以Voronoi圖判斷目標間鄰近關系,根據(jù)文獻[22]提出了Voronoi鄰近關系的定義,若兩個空間目標具有相同的Voronoi邊,則它們構成鄰近關系,互為自然鄰居(natural neighbors)。

圖1 空間目標分布的鄰近程度測算Fig.1 Calculate adjacency of spatial objects distribution

由定義可得,圖1(b)中Ⅰ與Ⅱ是自然鄰居,表達為natural neighbors〈Ⅰ,Ⅱ〉,而A與B、Ⅱ與Ⅲ無公共邊,非鄰近關系,可見Voronoi圖的鄰近關系能較好地識別空間障礙的存在。

2.2 勢力范圍

由Voronoi圖幾何特性可知,點目標生成的Voronoi圖所覆蓋的二維平面范圍稱為勢力范圍(influence region,IR)[21],隨著生長源(點目標)的不均勻分布,Voronoi圖的勢力范圍亦發(fā)生變化,具體表現(xiàn)在生長源分布密集的區(qū)域,生成的Voronoi勢力范圍相對較小,反之,分布稀疏的區(qū)域,生成的Voronoi勢力范圍相對較大(見圖2),由此可得,Voronoi勢力范圍是表征其生長源聚集程度的標準之一。

綜合以上兩項標準,MSSC算法以點目標Voronoi圖的鄰近特性和勢力范圍共同判別點目標間的聚散特性,其中,Voronoi勢力范圍以Voronoi多邊形面積進行量化,并通過定義面積標度值來判斷Voronoi多邊形的生長源是否聚集,則記該面積標度值為面積閾值σ,即:當兩個相鄰Voronoi多邊形面積均小于面積閾值σ時,其生長源具有聚集性。

圖2 Voronoi圖表征的生長源分布特征Fig.2 Distribution characteristics of generators are expressed by Voronoi diagram

3 單一尺度的點目標聚類

MSSC算法中,σ值的選取決定了聚類的尺度,記:Smax、Smin分別是集合P的Voronoi多邊形面積的最大值和最小值,則σ的取值情況為:當σ≤Smin,所有點目標各自成類;當σ≥Smax,所有點目標合為一類;當Smin＜σ＜Smax,點目標隨σ值的變化實現(xiàn)多尺度的聚類,σ值越小,聚類粒度越細,類內歸屬信息越精確,但類間相似性越強; σ值越大,聚類粒度越粗,類間差異性越強,類內的相似性越低。

單一尺度下的點目標聚類選取固定的σ值,并根據(jù)準則1進行聚散性判斷。輸入全要素Voronoi圖層Voronoi Layer,包含_Shape(目標幾何信息)、_geo Lyr Name(特征點所屬線面目標的圖層名)、_geo Lyr Type(特征點所屬目標的幾何類型——點線面)、_geoFID(特征點所屬線面目標的標識碼),以及_geo Area(Voronoi面積)字段;輸出圖層Clusters Layer在VoronoiLayer基礎上新增了_clusterID(類ID);_isCluster(記錄點目標是否被分類)字段,具體算法如下。

算法1:Clustering{

(1)初始化類編號cluster Num←1,isBoundaryFirst←True表示類的邊界點首次被遍歷,新建臨時棧pStack←Null。

(2)遍歷VoronoiLayer圖層中的Voronoi多邊形,以k次遍歷為例,若vk._geo Lyr Type＝Point,說明該Voronoi區(qū)域是點目標生成,將其壓入棧中,pStack←vk。

1)若vj._geoLyr Type＝Point&&vj._geoArea≤σ,根據(jù)定義1,找到vj的自然鄰居集合,并將該集合中_isCluster屬性為False的Voronoi多邊形壓入棧pStack,vj._clusterID←cluster Num,vj._ isCluster←True,isBoundaryFirst←False;

2)若vj._geo Lyr Type≠Point&&vj._ geo Area≤σ,根據(jù)定義1,找到vj的自然鄰居集合,并將該集合中_isCluster屬性為False的Voronoi多邊形壓入棧pStack,vj._isCluster←True,isBoundary First←False;

3)若vj._geo Lyr Type＝Point&&vj._ geo Area＞&&isBoundary First＝False,則vj._ clusterID←cluster Num,vj._isCluster←True;

4)若以上條件皆不滿足,Continue。

(4)cluster Num＋＋,轉至[2],第k次遍歷結束。

(5)直至遍歷VoronoiLayer圖層中所有對象,算法結束。}

ClustersLayer圖層_cluster ID字段值表示聚類的結果,同一_clusterID值的Voronoi多邊形為同類,代表其生長源亦屬同類。

4 多尺度點目標聚類

空間數(shù)據(jù)的分布具有相對尺度特征,在不同尺度上體現(xiàn)不同的數(shù)量級,尺度的大小亦與空間覆蓋范圍成正比,即感興趣點的范圍越小,相應的空間尺度越小,劃分粒度越細,最小尺度下,每個點目標各自成類;反之亦然[20]。

4.1 多尺度下的Voronoi聚類

不同空間尺度下的Voronoi剖分對類(cluster)的判別標準不一致,如圖3所示,圖(a)中空間尺度較大,Voronoi剖分的粒度較粗;隨著空間尺度減小,圖(b)在圖(a)尺度聚類的基礎上進行再聚類,細分圖(a)中的每個子類(sub-clusters);同樣,更小空間尺度的圖(c)繼續(xù)對圖(b)中的子類再聚類,得到細粒度的聚類。由此可見,尺度變化實現(xiàn)了聚類粒度的逐層細分,并以Voronoi多邊形邊界劃分類,揭示了更為全面的空間聚集規(guī)律。

圖3 不同尺度下點目標粒度的Voronoi劃分Fig.3 Points granularity is divided by Voronoi in different scales

4.2 面積閾值σ的計算

假設理想狀況下,空間點目標集合P均勻分布,則以P為生長源構建的Voronoi圖中所有Voronoi多邊形的面積均相等,反之,當點目標位置分布存在空間異質性時,根據(jù)勢力范圍特性,其構建的Voronoi多邊形面積大小隨點目標的聚散特征呈規(guī)律變化。MSSC算法逐一計算不同類內點目標均勻分布時的面積閾值σ作為參考,并與其真實情況下非勻質分布時生成的Voronoi多邊形面積進行比較,以判斷點目標的聚散性。

面積閾值σ的計算根據(jù)初聚類與再聚類分為以下兩種:

設點目標集合P＝{p1,p2,…,pn}?R2,由集合P為生長源的Voronoi圖集合V(P)＝{v1(p1),v2(p2),…,vn(pn)}?R2的面積為S(V)＝{s1(v1),s2(v2),…,sn(vn)},線面障礙集合O＝{o1,o2,…,om}?R2,由集合O為生長源的Voronoi圖集合V′(O)＝{v′1(o1),v′2(o2),…,v′m(om)}?R2的面積為S′(V)＝{s′1(v′1), s′2(v′2),…,s′m(v′m)}。

定義2：全局平均面積(global mean area, GMA):假設理想狀況下,所有點目標P均勻分布,則點目標勢力范圍的平均值稱為全局平均面積GMA,其等于P的最小外包矩形MBR(P)減去O的Voronoi面積S′(V)之差,再除以點的個數(shù)

定義3：局部平均面積(partial mean area, PMA):設SP為P中一子類集合,SP＝{sp1, sp2,…,spk}?R2,假設子類中點均勻分布,則子類中點的勢力范圍的平均值稱為局部平均面積PMA,其等于子類中點的Voronoi面積與子類中線面障礙的面積之差,再除以子類中點的數(shù)量

值得注意的是,σ取值主要是用于控制聚類的粒度,σ取值偏大時,不屬于同類的點目標會被劃分為一類;而σ取值偏小時,本屬于同類的點目標會被劃分開;σ分別取最大值、最小值時,點目標會全部融合成一類,或每個點目標獨立成一類,顯然是與聚類算法發(fā)現(xiàn)點目標典型聚集模式的初衷相悖,這就要求σ在合適的尺度收斂。此外,同一尺度下σ取值應根據(jù)不同子類的聚集模式自適應計算,非唯一值。針對以上兩點需求,MSSC算法通過對σ值的處理實現(xiàn)多尺度聚類。

4.3 多尺度聚類的收斂條件

MSSC算法以面積閾值σ控制聚類的粒度,以σ值的變化趨勢判斷空間多尺度的收斂條件。主要表現(xiàn)為:σ的計算取決于類內點目標生成的Voronoi圖的平均面積,即σ＝PMA。根據(jù)點目標的Voronoi分布特征,當類內點目標非均勻分布時,聚集程度高的點目標生成的Voronoi圖面積小于σ,即將該子目標劃分為新的子類,在下一尺度計算新子類的PMA,繼續(xù)聚類;當類內點目標均勻分布,無聚集趨勢時,每個點目標生成的Voronoi圖面積均大于或等于σ,保持原有分類,下一尺度計算該類的PMA時,值保持不變。由此可以判斷:兩個相鄰尺度下σ值保持不變時,聚類停止,算法尺度收斂。

記空間尺度Λ＝{λ1,λ2,…,λm,…},可看作聚類的層數(shù),不同尺度下,面積閾值集合∑＝{σ1[], σ2[],…,σm[],…},子類集合SubCluster＝{SC[1][],SC[2][],…,SC[m][],…},對應的子類個數(shù)K＝{k1,k2,…,km,…},ki為大于等于1的任意整數(shù),當相鄰兩個尺度下,若任一類的面積閾值保持不變,表示類內點目標已均勻分布,即不再產生子類,則聚類終止,MSSC算法的收斂條件為

文中字母黑體加粗與“[]”皆表示集合,尺度收斂過程如下:

(1)初聚類時,λ1＝1,σ1為點目標P的全局平均面積GMA(P),取唯一值,根據(jù)算法1進行聚類,得到子類集合SC[1][]＝{SC[1][1],…,SC[1][k1]};

(2)再聚類時,λ2＝2,先計算子類SC[1][]集合中每個子類的局部平均面積,即σ2[]＝{PMA(SC[1][1]),…,PMA(SC[1][k1])},若σ1≠σ2[],根據(jù)算法1分別進行SC[1][]子類集合中各子類的再聚類,得到子類集合SC[2][]＝{SC[2][1],…,SC[2][k2]};

(3)繼續(xù)再聚類至m尺度,λm＝m,計算子類SC[m－1][]集合中每個子類的局部平均面積,即σm[]＝{PMA(SC[m－1][1]),…, PMA(SC[m－1][km－1])},若σm[]≠σm－1[],根據(jù)算法1分別進行SC[m－1][]子類集合中各子類的再聚類,得到子類集合SC[m][]＝{SC[m][1],…,SC[m][km]},重復過程(3);若σm[]＝σm－1[],算法結束,λm－1為點集P聚類的最小尺度。

算法2:Multi-Scale Spatial Clustering{

(1)初始化變量isFirstClustering←True,表示為初聚類。

1)若isFirstClustering＝True,σ值為所有點目標的全局平均面積,σ1＝GMA(P),執(zhí)行算法1,isFirstClustering←False。

2)若isFirstClustering＝False,以尺度λm為例,σm[]為λm－1尺度下得到的各個子類局部平均面積的集合,若σm[]≠σm－1[],對每個子類執(zhí)行算法1;若σm[]＝σm－1[],說明σ已收斂,算法結束,點集P聚類的最小尺度為m－1。}

4.4 MSSC算法的時間復雜度

縱觀MSSC算法結構,構建全要素Voronoi的時間復雜度為O(n log n),n為特征點的個數(shù);算法1的時間復雜度為O(n);算法2中多尺度聚類的是對類的逐層細分,其結構類似于二叉樹,當聚類最小尺度為m時,時間復雜度為O(m log m)。綜合考慮MSSC算法的時間復雜度為O(n log n)＋O(n)＋O(m log m),但一般情況下,m遠遠小于n,則MSSC算法的時間復雜度為O(n log n)。

5 試驗與討論

試驗采用真實數(shù)據(jù)與模擬數(shù)據(jù)對MSSC算法的可行性、穩(wěn)定性進行驗證與討論。

5.1 MSSC算法的可行性

選取典型高原湖泊星云湖上游支流區(qū)域作為研究區(qū),空間數(shù)據(jù)集為Gauss-Kruger投影,西安80參心坐標系,1∶10 000比例尺。在研究區(qū)范圍內,提取河流、湖泊分別作為線、面目標約束,并按50 m間隔對等高線抽樣生成點目標數(shù)據(jù)(見圖4),從單一尺度綜合線面目標聚類與多尺度聚類的自適應收斂考慮,并對比已有聚類算法進行驗證。

圖4 研究區(qū)空間數(shù)據(jù)Fig.4 Spatial data of research region

單一尺度綜合線面目標聚類。試驗選取點目標的最粗聚類粒度作為衡量標準,采用聚類算法k-means[23]、k-medoids[24]、CLARANS[1]以及BIRCH[25]對高程點目標聚類,當預設最終聚類數(shù)目k＝1(最小值),所有點目標被劃分為一類,難以顧及線面目標對空間點集的約束。而客觀世界中高程點被河流與湖泊劃分,MSSC算法通過構建全要素Voronoi圖判斷點線面目標間的鄰近關系(見圖5),取點目標Voronoi面積的最大值作為面積閾值(σ＝80 181.24 m2)進行聚類,將點目標自動劃分為4類(見圖6),以不同形狀和顏色的點集表征不同的類別,準確識別了線面目標對點目標聚類的劃分。

圖5 全要素Voronoi圖Fig.5 Voronoi diagram with all features

圖6 綜合線面特征聚類Fig.6 Clustering with lines and polygons

多尺度聚類的自適應收斂?，F(xiàn)有多尺度聚類算法對尺度的控制范圍過大,尺度變化從每個點目標單獨成類至所有點目標合為一類,難以準確預定義能夠識別點目標典型聚集模式的適合尺度,主觀性強。試驗采用MSSC算法對研究區(qū)點目標聚類,算法在λ＝9時收斂,發(fā)現(xiàn)79類有聚集趨勢的點目標集群,但為說明尺度收斂過程,選取11個空間尺度、4個典型聚類進行分析。圖7中4條折線分別表示4個典型類在11個空間尺度下的面積閾值變化情況,圖8為4個典型類在λ＝1,5,9時的聚類情況。

圖7 面積閾值與空間尺度的關系Fig.7 The relationship between area threshold and spatial scale

就整體而言,λ＝1時,σ取全局平均面積GMA(3 142.232 3 m2),λ＝2,3,…,11時,σ根據(jù)子類中點目標的不同分布計算不同子類的局部平均面積,σ＝PMA,σ值隨空間尺度的減小而逐漸減小,并在特定的空間尺度之后保持不變。具體而言,Cluster 1、Cluster 2、Cluster 3、Cluster 4的σ值分別在λ＝9、λ＝7、λ＝6、λ＝6之后恒定,σ值不變表示聚類粒度不再改變,類的數(shù)量不再增加,聚類結束,即驗證了算法在兩個相鄰空間尺度下σ值不變時達到收斂。

綜合以上驗證,算法針對真實數(shù)據(jù)的處理是有效且可行的。另從線面約束形態(tài)上看,MSSC算法能精確識別不規(guī)則形態(tài)的線面目標,不受多邊形凹凸的限制,優(yōu)于通過簡化線面目標進而測算點目標繞行障礙物距離來判斷點目標聚類的COD-CLARANS[4]、DBCluC[5]等算法;從聚類形態(tài)而言,MSSC算法聚類粒度隨空間尺度的減小而細化,可以識別分布相對密集且任意形態(tài)的點目標集群(見圖8)。

圖8 不同空間尺度下的MSSC算法聚類結果Fig.8 Clustering result of MSSC algorithm in different spatial scales

5.2 MSSC算法的穩(wěn)定性

聚類算法的穩(wěn)定性要求算法對空間異常值(噪聲)的存在不敏感。二維空間數(shù)據(jù)聚類中的異常值主要表征為受聚類中心影響較小,不具有聚集趨勢的空間點目標[18],而穩(wěn)定的聚類算法需要能夠識別異常值且聚類結果不受異常值影響。

試驗在真實高程點數(shù)據(jù)集外圍8個方向加入不具有聚集趨勢的8個異常數(shù)據(jù)點,采用MSSC算法在σ＝80 181.24 m2時進行聚類(見圖9),結果顯示:8個異常點因遠離高程點,使得其生成的Voronoi圖面積遠遠大于具有聚集趨勢的高程點生成的Voronoi圖面積,且當異常點數(shù)目遠小于高程點數(shù)目時,異常點的Voronoi圖面積遠大于高程點集的Voronoi圖面積的平均值,MSSC算法將Voronoi面積小于σ的點目標進行聚類,大于σ被單獨識別,判斷為異常值,對比圖6,異常值對高程點目標的聚類不產生影響。

圖9 異常值的識別Fig.9 Distinguish outliers from points

6 結 論

MSSC算法利用全要素Voronoi剖分準確地識別了空間點線面目標的鄰近關系,對河流、湖泊、建筑物等具有阻礙點目標空間連續(xù)性的障礙物的處理符合人類的空間認知習慣;根據(jù)點目標分布特征自適應地計算σ值,以其數(shù)值控制聚類的粒度,以其變化規(guī)律控制尺度的收斂,能夠發(fā)現(xiàn)空間點目標的典型聚集模式;聚類過程中對異常值處理穩(wěn)健,無須自定義參數(shù)。

MSSC算法適用于發(fā)現(xiàn)客觀世界中表征地形、氣候、經濟、人口等位置分布的離散數(shù)據(jù)點聚集模式,進而解譯隱含規(guī)律。結合試驗對高程點的聚散特征分析,被聚類的高程點表征了地形起伏較大的區(qū)域,尺度收斂的速率亦體現(xiàn)了空間數(shù)據(jù)分布異質性的強弱,相關問題亟待進行下一步實證分析研究。

[1] NG R T,HAN J W.Efficient and Effective Clustering Methods for Spatial Data Mining[C]∥Proceedings of the 20thVLDB Conference.Santiago,Chile:[s.n.],1994:144-155.

[2] ESTIVILL-CASTROV,LEEI.AUTOCLUST＋:Automatic Clustering of Point-data Sets in the Presence of Obstacles [C]∥Proceedings of the 1st International Workshop on Temporal,Spatial and Spatio-temporal Data Mining.Berlin:Springer-Verlag,2001:133-146.

[3] LEUNG Y,ZHANGJ S,XUZ B.Clustering by Scale-space Filtering[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(12):1396-1410.

[4] TUNG A K H,HOU J,Han J W.Spatial Clustering in the Presence of Obstacles[C]∥Proceedings of the 17thInternational Conference on Data Engineering.Heidelberg: IEEE,2001:359-367.

[5] ZAIANE O R,LEE C H.Clustering Spatial Data when Facing Physical Constraints[C]∥Proceedings of the 2002 IEEE International Conference on Data Mining.Maebashi City,Japan:IEEE,2002:737-740.

[6] FAN B.A Hybrid Spatial Data Clustering Method for Site Selection:The Data Driven Approach of GIS Mining[J].Expert Systems with Applications,2009,36(2): 3923-3936.

[7] YANG Yang,SUN Zhiwei,ZHAO Zheng.Density-based Spatial Clustering Method with Obstacle Constraints[J].Computer Applications,2007,27(7):1688-1691.(楊楊,孫志偉,趙政.一種處理障礙約束的基于密度的空間聚類算法[J].計算機應用,2007,27(7):1688-1691.)

[8] CAO Keyan,WANG Guoren,H AN Donghong,et al.Clustering Algorithm of Uncertain Data in Obstacle Space [J].Journal of Frontiers of Computer Science and Technology,2012,6(12):1087-1097.(曹科研,王國仁,韓東紅,等.障礙空間中不確定數(shù)據(jù)聚類算法[J].計算機科學與探索,2012,6(12):1087-1097.)

[9] WANG Min,ZHOU Chenghu,PEI Tao,et al.MSCMO:A Scale Space Clustering Algorithm Based on Mathematical Morphology Operators[J].Journal of Remote Sensing, 2004,8(1):45-50.(汪閩,周成虎,裴韜,等.MSCMO:基于數(shù)學形態(tài)學算子的尺度空間聚類方法[J].遙感學報, 2004,8(1):45-50.)

[10] KONG Juan,XU Futian,XUE Qingfeng.Clustering Algorithm Based on Mathematical Morphology in the Presence of Obstacles[J].Computer Knowledge and Technology, 2008,4(9):2923-2925.(孔娟,徐夫田,薛慶峰.基于數(shù)學形態(tài)學的帶障礙約束的空間聚類算法研究[J].電腦知識與技術,2008,4(9):2923-2925.)

[11] ESTIVILL-CASTROV,LEEI.Clustering with Obstacles for Geographical Data Mining[J].ISPRSJournal of Photogrammetry and Remote Sensing,2004,59(1-2):21-34.

[12] SHI Yan,LIU Qiliang,DENG Min,et al.A Novel Spatial Clustering Method with Spatial Obstacles[J].Geomatics and Information Science of Wuhan University,2012,37 (1):96-100.(石巖,劉啟亮,鄧敏,等.一種顧及障礙約束的空間聚類方法[J].武漢大學學報:信息科學版, 2012,37(1):96-100.)

[13] LIUD Q,NOSOVSKIYG V,SOURINAO.Effective Clustering and Boundary Detection Algorithm Based on Delaunay Triangulation[J].Pattern Recognition Letters,2008,29 (9):1261-1273.

[14] EDLA D R,JANA P K.A Novel Clustering Algorithm Using Voronoi Diagram[C]∥Proceedings of the 7thInternational Conference on Digital Information Management.Macau:IEEE,2012:35-40.

[15] XUE Lixia,WANG Linlin,WANG Zuocheng,et al.Spatial Clustering in the Presence of Obstacles Based on Voronoi Diagram[J].Computer Science,2007,34(2):189-191.(薛麗霞,汪林林,王佐成,等.基于Voronoi圖的有障礙物空間聚類[J].計算機科學,2007,34(2):189-191.)

[16] LUO Jiancheng,YEE Leung,ZHOU Chenghu.Scale Space Based Hierarchical Clustering Method and Its Application to Remotely Sensed Data Classification[J].Acta Geodaetica et Cartographica Sinica,1999,28(4):319-324.(駱劍承,梁怡,周成虎.基于尺度空間的分層聚類方法及其在遙感影像分類中的應用[J].測繪學報,1999, 28(4):319-324.)

[17] CHEN Xiaoyu.A Study of Economic Regionalization Based on Multiscale Spatial Clustering[J].Journal of Chongqing Normal University:Natural Science,2011,28(5):81-84, 92.(陳小瑜.基于多尺度空間聚類的經濟區(qū)域劃分研究[J].重慶師范大學學報:自然科學版,2011,28(5):81-84,92.)

[18] ESTIVILL-CASTROV,LEEI.Amoeba:Hierarchical Clustering Based on Spatial Proximity Using Delaunay Diagram [C]∥Proceedings of the 9thInternational Symposium on Spatial Data Handling.[S.l.]:IGU Study Group on Geographical Information Science,2000:1-16.

[19] SHI Peibei,GUO Yutang,HU Yujuan,et al.Multiscale Spectral Clustering Algorithm[J].Computer Engineering and Applications,2011,47(8):128-130.(施培蓓,郭玉堂,胡玉娟,等.多尺度的譜聚類算法[J].計算機工程與應用,2011,47(8):128-130.)

[20] FU Lihua,LI Hongwei,ZHANG Meng,et al.Multi-scale Radial Basis Function Networks with Multiple Kernels[J].Journal of Huazhong University of Science&Technology: Nature Science Edition,2010,38(1):39-42.(付麗華,李宏偉,張猛,等.帶多個核函數(shù)的多尺度徑向基函數(shù)網(wǎng)絡[J].華中科技大學學報:自然科學版,2010,38(1): 39-42.)

[21] CHEN Jun.Voronoi Dynamic Spatial Data Model[M].Beijing:Surveying and Mapping Press,2002.(陳軍.Voronoi動態(tài)空間數(shù)據(jù)模型[M].北京:測繪出版社,2002.)

[22] GOLD C M.Dynamic Spatial Data Structures:The Voronoi Approach[C]∥Proceedings of the 1992 Canadian Conference on GIS.Ottawa:CIG,1992:245-255.

[23] MACQUEEN J.Some Methods for Classification and Analysis of Multivariate Observations[C]∥Proceedings of the 5thBerkeley Symposium on Mathematical Statistics and Probability.Berkley:[s.n.],1967:281-297.

[24] HAN J W,KAMBER M.Data Mining:Concepts and Techniques[M].Beijing:China Machine Press,2001.(HAN J W,KAMBER M.數(shù)據(jù)挖掘:概念與技術[M].北京:機械工業(yè)出版社,2001.)

[25] ZH ANGT,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.

(責任編輯:宋啟凡)

Multi-scale Clustering of Points Synthetically Considering Lines and Polygons Distribution

YU Li,GAN Shu,YUAN Xiping,YANG Minglong

Faculty of Land Resource Engineering,Kunming University of Science and Technology,Kunming 650093,China

Considering the complexity and discontinuity of spatial data distribution,a clustering algorithm of points was proposed.To accurately identify and express the spatial correlation among points,lines and polygons,a Voronoi diagram that is generated by all spatial features is introduced.According to the distribution characteristics of point’s position,an area threshold used to control clustering granularity was calculated.Meanwhile,judging scale convergence by constant area threshold,the algorithm classifies spatial features based on multi-scale,with an O(n log n)running time.Results indicate that spatial scale converges self-adaptively according with distribution of points.Without the custom parameters,the algorithm capable to discover arbitrary shape clusters which be bound by lines and polygons,and is robust for outliers.

spatial clustering;multi-scale;Voronoi diagram of all features;constraints

The National Science Foundation of China(Nos.41261092;71163023;41161061)

YU Li(1987—),female,PhD c andidate, majors in spatial data mining,modeling and analysis.E-mail:woshiyuli＠126.com

P208

A

1001-1595(2015)10-1152-08

國家自然科學基金(41261092；71163023；41161061)

2015-03-13

余莉(1987—),女,博士生,主要研究方向為空間數(shù)據(jù)挖掘、建模與分析。

YU Li,GAN Shu,YUAN Xiping,et al.Multi-scale Clustering of Points Synthetically Considering Lines and Polygons Distribution[J].Acta Geodaetica et Cartographica Sinica,2015,44(10):1152-1159.(余莉,甘淑,袁希平,等.綜合線面特征分布的點目標多尺度聚類方法[J].測繪學報,2015,44(10):1152-1159.)

10.11947/j.AGCS.2015.20150136

修回日期:2015-07-07