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

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

綜合線面特征分布的點(diǎn)目標(biāo)多尺度聚類方法

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

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

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

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

1 引 言

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

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

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

2 Voronoi剖分下的點(diǎn)目標(biāo)聚散特征表達(dá)

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

2.1 鄰近關(guān)系

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

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

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

2.2 勢力范圍

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

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

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

3 單一尺度的點(diǎn)目標(biāo)聚類

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

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

算法1:Clustering{

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

(2)遍歷VoronoiLayer圖層中的Voronoi多邊形,以k次遍歷為例,若vk._geo Lyr Type＝Point,說明該Voronoi區(qū)域是點(diǎn)目標(biāo)生成,將其壓入棧中,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＋＋,轉(zhuǎn)至[2],第k次遍歷結(jié)束。

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

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

4 多尺度點(diǎn)目標(biāo)聚類

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

4.1 多尺度下的Voronoi聚類

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

圖3 不同尺度下點(diǎn)目標(biāo)粒度的Voronoi劃分Fig.3 Points granularity is divided by Voronoi in different scales

4.2 面積閾值σ的計(jì)算

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

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

設(shè)點(diǎn)目標(biāo)集合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):假設(shè)理想狀況下,所有點(diǎn)目標(biāo)P均勻分布,則點(diǎn)目標(biāo)勢力范圍的平均值稱為全局平均面積GMA,其等于P的最小外包矩形MBR(P)減去O的Voronoi面積S′(V)之差,再除以點(diǎn)的個數(shù)

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

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

4.3 多尺度聚類的收斂條件

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

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

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

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

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

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

算法2:Multi-Scale Spatial Clustering{

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

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

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

4.4 MSSC算法的時間復(fù)雜度

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

5 試驗(yàn)與討論

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

5.1 MSSC算法的可行性

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié) 論

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

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

[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].計(jì)算機(jī)應(yīng)用,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].計(jì)算機(jī)科學(xué)與探索,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ù)學(xué)形態(tài)學(xué)算子的尺度空間聚類方法[J].遙感學(xué)報, 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ù)學(xué)形態(tài)學(xué)的帶障礙約束的空間聚類算法研究[J].電腦知識與技術(shù),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].武漢大學(xué)學(xué)報:信息科學(xué)版, 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].計(jì)算機(jī)科學(xué),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.(駱劍承,梁怡,周成虎.基于尺度空間的分層聚類方法及其在遙感影像分類中的應(yīng)用[J].測繪學(xué)報,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.(陳小瑜.基于多尺度空間聚類的經(jīng)濟(jì)區(qū)域劃分研究[J].重慶師范大學(xué)學(xué)報:自然科學(xué)版,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].計(jì)算機(jī)工程與應(yīng)用,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)絡(luò)[J].華中科技大學(xué)學(xué)報:自然科學(xué)版,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ù)挖掘:概念與技術(shù)[M].北京:機(jī)械工業(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.

(責(zé)任編輯:宋啟凡)

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

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

2015-03-13

余莉(1987—),女,博士生,主要研究方向?yàn)榭臻g數(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.(余莉,甘淑,袁希平,等.綜合線面特征分布的點(diǎn)目標(biāo)多尺度聚類方法[J].測繪學(xué)報,2015,44(10):1152-1159.)

10.11947/j.AGCS.2015.20150136

修回日期:2015-07-07