克服雙重約束的面目標位置聚類方法

余 莉，甘 淑，袁希平，李佳田

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

?

克服雙重約束的面目標位置聚類方法

余 莉，甘 淑，袁希平，李佳田

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

面目標的聚集模式識別是空間聚類研究的重要方向之一，但因多邊形幾何信息和空間障礙阻隔的雙重約束，目標的位置相似性難以快速而準確地計算。擴展點目標多尺度聚類方法，通過構建面目標的強度函數計算目標與鄰近目標的位置聚集程度，提出了有效作用于雙重約束下的面目標位置聚類法，并以判斷相鄰尺度下同一面目標類的強度函數閾值相等作為算法的收斂條件。經試驗分析與比較發(fā)現，算法無須自定義參數，能夠識別密度不均、任意形狀分布，以及“橋”鏈接的面目標集群，同時能夠準確判斷障礙約束對面目標簇的阻隔和劃分。

面目標；位置聚類；Voronoi圖；空間障礙；評價指數

面目標空間聚類旨在通過計算面目標間的相似性來識別具有近似特征或聚集分布模式的面目標集合，進而有效地發(fā)現地理實體的空間分異規(guī)律，廣泛運用于城市功能區(qū)劃[1-2]、面狀地物的制圖綜合[3-5]、聚落或城鎮(zhèn)結構擴張分析[6]等領域。面目標間的相似性分為空間信息相似性和非空間信息相似性，前者根據空間認知原理與格式塔完形原則，主要涉及面目標的方向、尺寸、形狀、位置鄰近等幾何信息的相似性[7-8]；后者則針對面目標功能、性質、狀態(tài)等的類似程度進行定性描述。不同的信息相似性需根據不同的應用導向進行選取和計算，非空間信息相似性常用于目標的類型識別與分類領域，一般采用傳統(tǒng)聚類分析中的角度系數、相關系數、指數相似系數、匹配測度等進行測算[9]。而空間信息主要用于目標形狀與分布的一致性或聚集性識別，其中，方向相似性或以面目標頂點計算標準差橢圓，或以最長邊法、加權平分線法、最小外接矩形法等計算建筑物的墻的方向來計算[10]；尺寸相似性采用面目標的周長、面積或最小外接矩形的寬長比等方式計算；形狀相似性可通過面目標邊數、角度、維數等進行衡量；位置相似性則是點目標位置距離測算的擴展，在克服面目標因不規(guī)則形狀導致的距離不確定性的基礎上，準確計算目標的位置接近程度。

面目標的聚集性識別中，位置相似性的準確判斷是空間聚類的核心問題，研究以準確發(fā)現面目標位置分布的聚集模式為切入點，通過分析現有的目標位置相似性測算方法，構建不受面目標形狀、尺寸限制，且在空間障礙實體約束條件下，能準確識別并測算面目標位置接近程度的相似性準則。

1 面目標的位置相似性研究進展

空間事物或現象的屬性、功能、關系等相互牽引與驅動，使其位置分布具有顯著的空間異質性，以面狀目標表示則呈現聚集分布且有意義的面目標簇，如聚落、建筑群、石漠化區(qū)等。面目標的位置相似性是對面目標聚集程度進行有效衡量的重要指標，縱觀已有的面目標空間聚類研究，主要從距離與拓撲關系兩方面判斷面目標的位置相似性。

1.1 距離測算

距離測算是通過計算面目標間的局部距離和邊界距離等來定義位置相似性。

局部距離是通過計算面目標的質心、最近點[11-12]或最遠點間的歐氏距離來判斷其位置遠近，但方法忽略了面目標面積的限制。以質心距離為例(圖1)，面目標A1、A2、A3，對應質心為P1、P2、P3，經目視判讀可得，相較于A1到A2的距離，A1與A3更為靠近，但以質心距離計算得到P1與P3間的距離大于P1與P2間的距離，與空間認知不符，因而質心距離對面目標位置相似性的判斷具有局限性。同理，最值距離也受到目標尺寸的影響。

邊界距離是通過提取面目標邊界的特征點對，采用Hausdorff距離[13-14]、改進Hausdorff距離[15-17]、平均距離[18]以及柵格距離[19]等計算目標間的位置相似性，但面目標的不規(guī)則幾何形狀導致難以準確找到距離為最值處的幾何點對，且?guī)缀吸c對的數量隨面目標數量的增加呈倍數增長，當空間數據量大且聚類算法迭代次數多時，會導致距離計算的時間復雜度大大增加。為提升算法效率，也有部分算法以最小外包矩形簡化面目標邊界[20]，但易造成圖形信息的損失，甚至產生拓撲關系的錯誤。同時，平均距離采用Delaunay三角網剖分目標，并計算目標間公共三角網邊的平均長度[7]，所得距離精度與邊界點的內插步長相關，計算準確度與效率難以有效平衡；而柵格距離在將矢量數據二值圖像化處理過程中，也存在信息和精度損失。

圖1 質心距離的計算Fig.1 The calculation of centroid distance between polygons

1.2 拓撲關系測算

拓撲關系測算是以面目標間的拓撲關系判斷位置相似性，GDBSCAN(generalizing density-based spatial clustering of applications with noise)算法[21]采用相交或相遇的空間關系判斷面目標的鄰近關系，但缺乏對相離空間目標的處理；DBCANESO(density-based clustering algorithm with noise for extended spatial objects)算法[22]以目標緩沖區(qū)內包含目標的面積與目標緩沖區(qū)面積的比值計算密度值作為相似性，存在緩沖區(qū)半徑設置缺乏依據且主觀性強的問題；SCGML_IR(spatial clustering in geography markup language data based on inclusion relations)和SCGML_IR*算法[23]根據GML(geography markup language)文檔判斷點/線/面目標之間的包含關系作為相似性度量準則，但算法以特定數據源和單一拓撲關系作為判斷準則，應用較為局限。

綜上所述，面目標的位置相似性計算既需要克服自身尺寸和形狀的影響，又需盡可能準確并高效地測算目標間位置的接近程度。同時考慮到空間障礙阻隔了面目標聚集分布的連續(xù)性，相似性的判斷也需要對障礙進行識別與區(qū)分。在目標幾何信息和空間障礙的雙重約束下，研究選擇擴展點目標多尺度聚類方法(multi-scale spatial clustering，MSSC)[24]進行面目標的聚類分析，原因有以下幾點：Voronoi圖在無需簡化不規(guī)則多邊形邊界的情況下，能夠對面目標進行整體剖分，符合格式塔原理的連續(xù)性和閉合性定律[25]，既不會造成圖形信息損失，又能準確提取目標的鄰近關系；Voronoi圖在“頸”和“鏈”目標處的勢力范圍遠大于聚集目標，易于識別“頸”和“鏈”目標；MSSC方法在無須用戶自定義參數的基礎上實現目標的多尺度聚類，具有較好的自適應性。鑒于此，研究以Voronoi鄰近關系判斷面目標間、面目標與障礙間的通達性；通過對比分析面目標的幾何特征對其位置聚集性的影響，構建了強度函數以計算面目標與其鄰近目標的聚集性強弱來表征位置相似性；最后采用評價指數對聚類質量進行評估。

2 強度函數的構建

根據地理學第一定律[26]闡述，目標距離越近，關聯程度越強，本文通過對比分析，構建適宜的強度函數以識別空間障礙約束下位置關聯性強、聚集程度高的不規(guī)則面目標集合。

2.1 指標的對比分析

MSSC方法驗證了點目標位置分布與其Voronoi圖空間格局之間的密切相關，當點目標的位置分布越密集時，生成的Voronoi勢力范圍越小，由此可得，以空間目標為生長元所得到的Voronoi多邊形的面積是判斷目標分布特征的重要指標之一。但與零維點目標不同，面目標屬于二維對象，其Voronoi圖的剖分格局除了受生長元位置影響外，還依賴于目標自身不規(guī)則形狀與尺寸的約束。本文采用Voronoi圖對面目標的勢力范圍進行剖分，在完整包含面目標的同時，Voronoi圖不僅充分表達了目標的不規(guī)則幾何形狀特征，而且能夠通過Voronoi圖的一階鄰近特性判斷面目標在空間障礙約束下的通視情況；進而，結合目標尺寸約束下Voronoi面積變化的分析，以確定目標位置的接近程度。

研究選擇“面目標Voronoi面積”“面積差”和“比率”3項指標進行對比分析，旨在尋求不同離散程度、不同目標尺寸大小下，能穩(wěn)定判斷面目標聚集特征的計算方法。其中，“面積差”表示面目標的Voronoi面積與自身面積的差值；“比率”表示面積差與面目標周長的比值，為清晰顯示指標對比結果，當存在右坐標軸時，“比率”指標值由右坐標軸顯示。

(1) 相同目標尺寸，不同離散程度分布的指標變化。圖2(a)中存在21個尺寸一致的面目標，細線表示Voronoi邊，經目視判讀，面目標1—9屬于聚集分布，10—21的分布相對分散。對應于“面目標Voronoi面積”“面積差”和“比率”3項指標的變化趨勢如圖2(b)所示，皆表現為目標在不同聚集程度分布下，指標值隨聚集程度的減弱而數值增大，同一聚集程度分布下，指標值會因邊界和轉角的分布而略有增加，但指標值仍遠小于離散分布的目標。

圖2 相同目標尺寸下的指標變化Fig.2 Changes of indicators under given object size

(2) 相同離散程度分布，不同目標尺寸的指標變化。圖3(a)中存在13個尺寸不同但等距離分布的面目標，細線表示Voronoi邊，經目視判讀，所有面目標均勻分布，應具有相同的位置相似性，即指標值應近似相等。對應于“面目標Voronoi面積”“面積差”和“比率”3項指標值的變化趨勢(圖3(b))，表現為：“面目標Voronoi面積”和“面積差”隨面目標尺寸的增大而指標值增加，相較而言，“面積差”的增加幅度較弱，但兩者在判斷目標位置相似性時，易受到目標自身尺寸大小的影響，準確度低。而“比率”指標加入了對目標面積和周長的約束，指標值近似相等，在不受面目標尺寸影響的情況下，能準確反映目標的分布特性，較為穩(wěn)定。

圖3 相同離散程度下的指標變化Fig.3 Changes of indicators under the uniform distribution of objects

(3) 不同目標尺寸、不同離散程度且?guī)Э臻g障礙約束下的指標變化。圖4(a)中存在不均勻分布的面目標1—39和線狀障礙40，經目視判讀，面目標1—35屬于聚集分布，36—39屬于離群分布，也稱離群目標。對應于“面目標Voronoi面積”“面積差”和“比率”3項指標值的變化趨勢如圖4(b)，針對離群目標36—39和空間障礙40而言，因目標的Voronoi面積較大，導致3項指標的值遠遠大于聚集分布的目標，易于區(qū)分和提取。但對于聚集分布的目標1—35而言，研究將位于面簇內部，即其Voronoi一階鄰近目標皆為同類目標的面目標稱作類內目標，如目標1—17；將位于面簇邊界，即其Voronoi一階鄰近目標中至少包含一個非類內目標(空間障礙、離群目標或其他類目標)的面目標稱作類邊界目標，如目標18—35。類內目標中，“面目標Voronoi面積”和“面積差”指標的值隨面目標面積或延展性的增加而增大，存在波動，如目標3、4、11、14等，而“比率”指標不受面目標尺寸影響，一直保持相對較小且近于穩(wěn)定的值，能較好地識別類內目標。類邊界目標的3個指標變化皆受到類邊界目標與非類內目標分布趨勢的影響，指標值極不穩(wěn)定，如目標26和29的指標值相差較大，難以直接通過指標值的大小判斷。但值得注意的是，類邊界目標的Voronoi一階鄰近目標中至少包含一個類內目標，且與“比率”指標值較小的類內目標存在高度聚集性，可識別為同類，因此，當依據“比率”指標值識別得到類內目標后，可將類邊界目標與其Voronoi一階鄰近目標中“比率”指標值最小的類內目標劃為同類。

圖4 障礙約束下的指標變化Fig.4 Changes of indicators with obstacles

2.2 強度函數的定義和值域分析

根據以上3項指標的對比分析，“比率”指標對面目標位置聚集程度的判斷準確且穩(wěn)定，顧以其作為面目標位置相似性計算的方式，稱作強度函數。

(1)

面目標的強度函數值越小，表示面目標與周圍面目標的聚集性越強；反之，面目標強度函數值越大，表示面目標與周圍的面目標越分散。

面目標位置聚類時，常受到空間障礙的阻隔，因而也需要對其與面目標的位置相似性進行計算。空間障礙約束是指以線、面要素表達，且因長度延伸較長、面積覆蓋較廣而阻礙待聚類目標聚集性的空間目標，如無間斷的河流、高速公路等。聚類分析時，空間障礙因具有較大的Voronoi面積，使得其強度函數值遠大于聚集目標的強度函數值，易于阻隔并劃分面類。就面狀障礙而言，可根據公式(1)進行計算，而線狀障礙因無面積值，其強度函數可進行簡化。

(2)

強度函數的數值表達了面目標與其鄰近目標聚集性的強弱，可作為鄰近目標間距離遠近的判斷標準，隨著目標分布的聚集至松散，強度函數的值呈單調遞增的趨勢，研究設置強度函數閾值Σ提取聚集目標，Σ的取值決定了面目標聚類的粒度，記max(f(A))、min(f(A))分別是面目標集合A中強度函數的最大值和最小值，則Σ的取值范圍為[min(f(A))，max(f(A))]，Σ值越小，聚類粒度越細，聚類個數越多，類內聚集性越強；反之，亦成立。

3 面目標的多尺度位置聚類方法

基于面目標強度函數的構建，本文擴展MSSC方法，提出了面目標的多尺度位置聚類方法(MSSC for polygon，MSSCP)，采用Voronoi圖剖分空間目標和障礙后，按公式(1)和(2)分別計算面目標和障礙的強度函數值，最終以強度函數閾值的收斂實現面目標聚類。

3.1 聚類預處理

MSSCP方法借鑒特征點逼近生成線/面Voronoi圖的思想[27-28]，以空間目標間最小距離的1/2為間隔，將空間線、面目標邊界離散化為特征點，并以特征點為生長元生成Voronoi圖，最后合并相同目標的特征點Voronoi圖，以生成混合線、面目標的Voronoi圖。然而，根據Voronoi圖的生成原理可知，Voronoi邊界是生長元之間歐氏距離的二等分線，當兩個空間目標相交時，平面內的點到交點的距離皆相等，Voronoi邊界難以劃分，因此，當空間目標存在相交的拓撲關系時，需根據目標在聚類過程中的作用分別處理。具體操作為：當相交目標為待聚類目標時，聚類中屬于獨立的個體，應在交點或重合邊界處稍微收縮線段，使得相交的目標分離后再生成單一目標的Voronoi圖；當相交的目標為空間障礙時，對周圍面目標具有整體阻隔作用，應將相交障礙的Voronoi圖合并成一個完整的Voronoi多邊形，改變被阻隔目標的鄰近關系。

3.2 面目標的多尺度位置聚類

根據MSSC方法思想，如圖3中分析可得，當空間面目標均勻分布時，單一面目標的強度函數值近似等于所有面目標強度函數值的平均值，因此，MSSCP方法以類內面目標強度函數值的平均值作為強度函數閾值，以判斷單一尺度下面目標的位置相似性，在初始聚類時，先將所有面目標視為一類，隨著尺度的遞增，逐層實現面目標聚類的粒度下鉆。

(3)

相較于MSSC方法，MSSCP方法采用強度函數取代目標的Voronoi面積進行目標位置的相似性計算，并以相鄰尺度下，同一面目標類的強度函數閾值相等作為算法的收斂條件，算法流程見圖5。

MSSCP方法在生成空間面目標和障礙的Voronoi圖后，根據公式(1)和(2)計算所有目標與障礙的強度函數值，再以公式(3)計算當前聚類尺度下的強度函數閾值，進而通過相鄰尺度下的強度函數閾值是否相等，來判斷聚類粒度的下鉆。單一尺度聚類后，需遍歷樹結構中的所有非空間障礙的葉子節(jié)點進行檢查，搜索任一葉子節(jié)點及與其屬于Voronoi一階鄰近關系的目標集合，將該葉子節(jié)點與鄰近目標集合中強度函數值最小的目標劃為同類。

圖5 MSSCP算法流程圖Fig.5 The flow chart of MSSCP algorithm

聚類結束后，每棵完整的樹代表了一個面目標類，樹的數量即為聚類的個數，樹中非空間障礙節(jié)點的數量即為該類包含的面目標數量，每棵樹的根節(jié)點和子節(jié)點表示類內目標，非空間障礙的葉子節(jié)點代表類邊界目標，而未被標記的目標則屬于離群目標。

4 聚類結果的有效性評價

聚類結果的有效性評價是通過構建有效性指數，對空間簇內部的緊密性和外部的分離性進行量化評估的方法[29]。研究基于相對評價法的思想[9]，提出適用于評價MSSCP方法聚類質量的指數AIM(assessmentindexofMSSCP)。

根據MSSCP方法的聚類結果可知，樹的根節(jié)點和子節(jié)點代表了類內目標，當類內目標的強度函數值與閾值越接近時，表示類內目標分布越均勻；而非空間障礙的葉子節(jié)點代表了類邊界目標，當類邊界目標的強度函數值與閾值相差越大時，表示各面簇間的分離程度越強。根據這一特性，研究采用目標強度函數的方差，分別定義了簇內緊密度指數CI(compactnessindex)和簇間離散度指數DI(dispersionindex)。

設經聚類得到m個面目標類的集合C={c1，c2，…，cm}，cj∈C，對應的強度函數閾值集合Σ={σ1，σ2，…，σm}，類cj包含類內目標集合AI= {ai1，ai2，…，aip} ?R2，對應類內目標AI的強度函數F(AI)={f(ai1)，f(ai2)，…，f(aip)}，另包含類邊界目標集合AO={ao1，ao2，…，aoq} ?R2，對應類邊界目標AO的強度函數F(AO)={f(ao1)，f(ao2)，…，f(aoq)}，則：

定義4：簇內緊密度指數(CI)指簇內目標分布的均勻程度，等于所有面簇各自包含的類內目標的強度函數值與該類強度函數閾值的方差之和的平均值

(4)

定義5：簇間離散度指數(DI)指簇間目標分布的分離程度，等于所有面簇各自包含的類邊界目標的強度函數值與該類強度函數閾值的方差之和的平均值

(5)

簇內緊密度指數CI的數值越小，表示類內目標的強度函數值與該簇的強度函數閾值越接近，即類內目標越趨于均勻而緊密；簇間離散度指數DI的數值越大，則表示類邊界目標的強度函數值與該簇的強度函數閾值相差越大，即面簇間的位置越遠，因此，可組合CI和DI指數，共同計算AIM指數。

定義6：MSSCP評價指數(AIM)是簇內緊密度指數與簇間離散度指數的綜合評價指數

(6)

AIM指數的數值越小，表示聚類結果的類內緊密度越低，或簇間離散度越高，整體聚類質量越好。

5 試驗與討論

5.1 模擬數據試驗

為驗證MSSCP算法對面目標位置聚類的有效性，試驗選取了不同凹凸多邊形模擬了5組具有典型位置分布特征的面目標數據集：等密度分離、變密度分離、任意形狀分布、橋鏈接，以及帶空間障礙約束的面目標數據集進行聚類，聚類結果在表1中以虛線框圈出。

試驗結果顯示，MSSCP方法以強度函數代替Voronoi圖面積，并對MSSC方法進行擴展，能夠識別不同密度且任意形狀的目標簇。同時，通過與現有的面目標位置相似性判斷或計算方法進行對比分析，MSSCP方法對面目標位置聚類的有效性，具體表現如下：①相較于以點代面或多邊形化簡后再計算距離相似度的方法，MSSCP方法充分顧及面目標幾何形狀信息的約束，在Voronoi圖完整剖分目標的前提下，能夠準確提取目標間的鄰近關系，以判斷目標間是否通視或連續(xù)；②相較于提取特征點并迭代計算目標間最近距離或平均距離表征目標相似性的計算方法，MSSCP方法既無需考慮特征點選取的不確定性，又通過構建強度函數以直接計算目標與鄰近目標聚集程度的強弱，降低了計算的時間復雜度；③MSSCP方法針對“頸”和“鏈”目標計算的強度函數值遠遠大于聚集目標，能夠準確區(qū)分橋鏈接的面簇。此外，同為識別環(huán)狀分布的面目標，MSSCP方法能夠識別障礙對目標連續(xù)性的阻隔作用，將無障礙約束的環(huán)狀面目標識別為同類，而對空間障礙約束的環(huán)狀目標簇進行準確劃分為4類。

5.2 真實數據試驗

試驗采用MSSC和MSSCP方法對真實的聚落圖斑數據進行聚類并對比分析，旨在驗證MSSCP算法在面目標幾何信息約束和空間障礙約束下的可行性，選取了云南山區(qū)部分聚落聚集分布區(qū)域作為研究區(qū)(圖6(a))，提取研究區(qū)內267個面狀聚落圖斑和7條河流數據進行聚落位置相似性的識別，進而提取聚集分布的聚落群。試驗以MSSC和MSSCP方法分別對聚落圖斑的質心(點目標)、聚落圖斑(面目標)、考慮了河流(線障礙)約束的聚落圖斑(面目標)3種形式進行聚落的位置聚類，并以不同符號或顏色區(qū)分顯示聚類結果，以灰黑色面表示離群目標，如圖6(b)—(d)所示。

表1 模擬數據的聚類結果

圖6 聚落的位置聚類結果Fig.6 The result of position clustering of settlement

試驗結果分析如下：

(1) 幾何信息約束的對比。試驗采用MSSC算法對聚落質心進行聚類，在未考慮聚落形狀的情況下聚類得到4個點目標類(圖6(b))，而采用MSSCP算法對完整的聚落圖斑進行聚類，得到9個面目標類(圖6(c))。聚類結果差異原因在于：部分面積較大的圖斑被單點代替，改變了聚落的聚集趨勢，易將距離較遠的圖斑識別為同類(如虛線橢圓圈劃處)，或將距離較近的圖斑分為多類(如虛線方框圈劃處)，存在較大的偏差，特別是在處理覆蓋范圍較廣且形狀狹長時，僅以圖形質心難以準確判別地物的鄰近關系和實際位置的接近程度。

(2) 空間障礙約束的對比。空間障礙對面目標的聚集模式存在阻隔作用，對比圖6(c)和(d)可知，試驗加入河流障礙后，MSSCP方法識別得到22個面目標類，將位于河流障礙兩側的面目標進行區(qū)分識別，聚類結果與空間認知相符。

(3) 面目標多尺度聚類的結果評價。MSSCP方法將聚落圖斑進行多尺度的空間聚類，在空間尺度λ=5時算法收斂，聚類結果如圖6(c)所示，5個空間尺度下分別聚類得到面目標類的數目為：2、3、4、5、9。試驗采用CI、DI、AIM 3個指數對不同空間尺度下的面目標聚類結果進行量化分析(表2)，結果顯示：隨著空間尺度的增加，聚類粒度的下鉆，簇內緊密度指數CI下降，表示類內目標越趨于均勻和緊湊；而簇間離散度指數DI的變化雖存在波動，但整體呈下降趨勢，原因是聚類粒度的下鉆使得部分較為離散的邊界目標的聚集性相對減弱，被劃分為離群目標；AIM指數呈遞減的趨勢，表示聚類結果的質量隨尺度的增加逐漸優(yōu)化。

表2 不同空間尺度下的評價指數值

6 結 論

本文基于MSSC方法進行擴展，在充分考慮面目標幾何信息復雜性和空間障礙阻隔雙重約束的基礎上，提出了MSSCP方法，采用混合線、面目標的Voronoi圖提取目標直接或間接的Voronoi鄰近關系，并選擇不同面目標聚散分布和不同面目標尺寸下，“面目標Voronoi面積”“面積差”和“比率”3項指標變化進行對比分析，構建能夠表征面目標位置聚散性的強度函數以定量計算目標間的位置相似性。模擬試驗證明，MSSCP方法能夠識別不同密度分離、任意形狀分布、橋鏈接以及帶障礙約束的面目標類。真實數據試驗表明MSSCP方法避免了局部歐氏距離計算所帶來的位置相似性的不確定性；適用于空間障礙實體約束下，不規(guī)則面目標的位置聚集模式提取；評價指數的分析提現了隨空間尺度的下鉆，聚類質量逐層優(yōu)化，面簇的簇內緊密度逐層增加。

MSSCP方法針對面目標的位置進行聚類，適用于空間事物和現象的位置聚集趨勢分析，如典型石漠化區(qū)的劃分、聚落結構擴張變化分析中中心聚落的提取與劃分等。后續(xù)研究中有兩方面問題亟待討論和解決：考慮到面目標具有的非空間信息和方向、尺寸、形狀等空間信息皆具有獨立的非連續(xù)性、非均勻性與趨勢性[30]，若將所有信息歸一化后進行加權融合，不僅權值難以確定，且易發(fā)生信息的互斥，后續(xù)研究將于實現面目標的位置相似性識別后，再選擇性加入其他信息作為約束，來進行類粒度的細化，以擴展MSSCP方法的應用范疇。該研究主要針對面目標的位置相似性進行聚類，亦可參考式(2)擴展實現線目標的位置相似性聚類。

[1] 辜寄蓉,陳先偉,楊海龍.城市功能區(qū)劃分空間聚類算法研究[J].測繪科學,2011,36(5): 65-67.

GU Jirong,CHEN Xianwei,YANG Hailong.Spatial Clustering Algorithm on Urban Function Oriented Zone[J].Science of Surveying and Mapping,2011,36(5): 65-67.

[2] CAO Zechun,WANG Sujing,FORESTIER G,et al.Analyzing the Composition of Cities Using Spatial Clustering[C]∥Proceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing.New York: ACM,2013: 14.

[3] STEINHAUER J H,WIESE T,FREKSA C,et al.Recognition of Abstract Regions in Cartographic Maps[M]∥MONTELLO D R.Spatial Information Theory.Berlin Heidelberg: Springer,2001: 306-321.

[4] YAN Haowen,WEIBEL R,YANG Bisheng.A Multi-Parameter Approach to Automated Building Grouping and Generalization[J].Geoinformatica,2008,12(1): 73-89.

[5] 鄧敏,孫前虎,文小岳,等.建筑物層次空間聚類方法研究[J].計算機工程與應用,2011,47(28): 120-123.DENG Min,SUN Qianhu,WEN Xiaoyue,et al.Hierarchical Spatial Clustering of Buildings[J].Computer Engineering and Applications,2011,47(28): 120-123.

[6] 馬利邦,郭曉東,張啟媛.甘谷縣鄉(xiāng)村聚落時空布局特征及格局優(yōu)化[J].農業(yè)工程學報,2012,28(13): 217-225.

MA Libang,GUO Xiaodong,ZHANG Qiyuan.Spatio-Temporal Distribution and Optimization of Rural Settlements in Gangu County of Loess Hilly Area[J].Transactions of the Chinese Society of Agricultural Engineering,2012,28(13): 217-225.

[7] 艾廷華,郭仁忠.基于格式塔識別原則挖掘空間分布模式[J].測繪學報,2007,36(3): 302-308.DOI: 10.3321/j.issn:1001-1595.2007.03.011.

AI Tinghua,GUO Renzhong.Polygon Cluster Pattern Mining based on Gestalt Principles[J].Acta Geodaetica et Cartographica Sinica,2007,36(3): 302-308.DOI: 10.3321/j.issn:1001-1595.2007.03.011.

[8] 閆浩文,應申,李霖.多因子影響的地圖居民地自動聚群與綜合研究[J].武漢大學學報(信息科學版),2008,33(1): 51-54.YAN Haowen,YING Shen,LI Lin.An Approach for Automated Building Grouping and Generalization Considering Multiple Parameters[J].Geomatics and Information Science of Wuhan University,2008,33(1): 51-54.

[9] 鄧敏,劉啟亮,李光強,等.空間聚類分析及應用[M].北京: 科學出版社,2011.

DENG Min,LIU Qiliang,LI Guangqiang,et al.Analysis and Application of Spatial Clustering[M].Beijing: Science Press,2011.

[10] BARRAULT M,REGNAULD N,DUCHENE C,et al.Integrating Multi-agent,Object-oriented,and Algorithmic Techniques for Improved Automated Map Generalization[C]∥Proceedings of 20th International Cartographic Conference.Beijing: Publishing House of Surveying and Mapping,2001: 2110-2116.

[11] 楊春成,何列松,謝鵬,等.顧及距離與形狀相似性的面狀地理實體聚類[J].武漢大學學報(信息科學版),2009,34(3): 335-338.YANG Chuncheng,HE Liesong,XIE Peng,et al.Clustering Analysis of Geographical Area Entities Considering Distance and Shape Similarity[J].Geomatics and Information Science of Wuhan University,2009,34(3): 335-338.

[12] ZHANG Xiang,AI Tinghua,STOTER J S,et al.Building Pattern Recognition in Topographic Data: Examples on Collinear and Curvilinear Alignments[J].Geoinformatica,2013,17(1): 1-33.

[13] ALT H,BEHRENDS B,BL?MER J.Approximate Matching of Polygonal Shapes[J].Annals of Mathematics and Artificial Intelligence,1995,13(3-4): 251-265.

[14] WANG Sujing,CHEN Chunsheng,RINSURONGKAWONG V,et al.A Polygon-based Methodology for Mining Related Spatial Datasets[C]∥Proceedings of the 1st ACM SIGSPATIAL International Workshop on Data Mining for Geoinformatics.New York: ACM,2010: 1-8.

[15] DAVIS E.Representations of Commonsense Knowledge[M].San Mateo: Morgan Kaufmann,1990.

[16] DENG Min,LI Zhilin,CHEN Xiaoyong.Extended Hausdorff Distance for Spatial Objects in GIS[J].International Journal of Geographical Information Science,2007,21(4): 459-475.

[17] JOSHI D,SAMAL A K,SOH L K.Density-based Clustering of Polygons[C]∥Proceedings of the CIDM’09 IEEE Symposium on Computational Intelligence and Data Mining.Nashville,TN: IEEE,2009: 171-178.

[18] HUH Y,KIM J,LEE J,et al.Identification of Multi-Scale Corresponding Object-Set Pairs between Two Polygon Datasets with Hierarchical Co-Clustering[J].ISPRS Journal of Photogrammetry and Remote Sensing,2014,88: 60-68.

[19] 耿協鵬,杜曉初,胡鵬.基于柵格距離變換的擴展對象空間聚類方法[J].測繪學報,2009,38(2): 162-167,174.DOI: 10.3321/j.issn:1001-1595.2009.02.012.

GENG Xiepeng,DU Xiaochu,HU Peng.Spatial Clustering Method Based on Raster Distance Transform for Extended Objects[J].Acta Geodaetica et Cartographica Sinica,2009,38(2): 162-167,174.DOI: 10.3321/j.issn:1001-1595.2009.02.012.

[20] HALKIDI M,VAZIRGIANNIS M.NPClu: An Approach for Clustering Spatially Extended Objects[J].Intelligent Data Analysis,2008,12(6): 587-606.

[21] SANDER J,ESTER M,KRIRGEL H P,et al.Density-based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications[J].Data Mining and Knowledge Discovery,1998,2(2): 169-194.

[22] 黎韶光,周巨鎖,謝玉波,等.一種面向擴展空間對象的密度聚類算法[J].計算機工程與應用,2011,47(13): 166-168.

LI Shaoguang,ZHOU Jusuo,XIE Yubo,et al.Density-based Clustering Algorithm for Extended Spatial Objects[J].Computer Engineering and Applications,2011,47(13): 166-168.

[23] 張麗,吉根林.基于點面包含關系的GML空間聚類算法[J].小型微型計算機系統(tǒng),2010,31(4): 702-705.

ZHANG Li,JI Genlin.Algorithm for Spatial Clustering in GML Data Based on Point-Region Spatial Inclusion Relation[J].Journal of Chinese Computer Systems,2010,31(4): 702-705.

[24] 余莉,甘淑,袁希平,等.綜合線面特征分布的點目標多尺度聚類方法[J].測繪學報,2015,44(10): 1152-1159.DOI: 10.11947/j.AGCS.2015.20150136.

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.DOI: 10.11947/j.AGCS.2015.20150136.

[25] 王中輝,閆浩文.基于方向Voronoi圖模型的群組目標空間方向關系計算[J].小型微型計算機系統(tǒng),2013,38(5): 584-588.WANG Zhonghui,YAN Haowen.Computation of Direction Relations between Object Groups Based on Direction Voronoi Diagram Model[J].Geomatics and Information Science of Wuhan University,2013,38(5): 584-588.

[26] TOBLER W R.A Computer Movie Simulating Urban Growth in the Detroit Region[J].Economic Geography,1970,46(S1): 234-240.

[27] 王新生,劉紀遠,莊大方,等.基于GIS的任意發(fā)生元Voronoi圖逼近方法[J].地理科學進展,2004,23(4): 97-102.

WANG Xinsheng,LIU Jiyuan,ZHUANG Dafang,et al.GIS-based Approximation Algorithm for Constructing Voronoi Diagrams with General Generators[J].Progress in Geography,2004,23(4): 97-102.

[28] 李佳田,楊琪莉,羅富麗,等.線/面Voronoi圖的分解合并生成算法[J].武漢大學學報(信息科學版),2015,40(11): 1545-1550.LI Jiatian,YANG Qili,LUO Fuli,et al.A Decomposition and Combination Algorithm for Voronoi Diagrams of Polylines and Polygons[J].Geomatics and Information Science of Wuhan University,2015,40(11): 1545-1550.

[29] BERRY M J A,LINOFF G S.Data Mining Techniques: For Marketing,Sales,and Customer Support[M].New York: John Wiley &Sons,1997.

[30] 劉啟亮,鄧敏,石巖,等.一種基于多約束的空間聚類方法[J].測繪學報,2011,40(4): 509-516.

LIU Qiliang,DENG Min,SHI Yan,et al.A Novel Spatial Clustering Method Based on Multi-constraints[J].Acta Geodaetica et Cartographica Sinica,2011,40(4): 509-516.

(責任編輯：宋啟凡)

Position Clustering for Polygon Object under Dual-constrains

YU Li，GAN Shu，YUAN Xiping，LI Jiatian

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

It is a vital research direction for spatial clustering to recognize polygon cluster,but due to the dual-constrains by geometric information of polygons and obstacles,the position similarity of polygon is difficult to calculate accurately and quickly.A polygon clustering algorithm under dual-constrains is proposed by extending the algorithm of multi-scale spatial clustering,and constructing an intensity function to express position aggregation between object and its adjacent object.For further discuss,it takes the same thresholds of intensity function in adjacent scales as convergence condition.Simulated polygons and real data are chosen to perform clustering in experiments to verify the validity of our algorithm.Results show that without predefined parameters,this algorithm can identify variety polygon clusters with different densities,arbitrary shape,bridge and obstacle.

polygon；position clustering；Voronoi diagram；spatial obstacle；assessment index

The National Natural Science Foundation of China(Nos.41561083; 41261092; 41561082); The Natural Science Foundation of Yunnan Province(No.2015FA016)

YU Li(1987—),female,PhD candidate,majors in spatial data mining,modeling and analysis.

GAN Shu

余莉，甘淑，袁希平，等.克服雙重約束的面目標位置聚類方法[J].測繪學報，2016,45(10)：1250-1259.

10.11947/j.AGCS.2016.20150491.

YU Li，GAN Shu，YUAN Xiping，et al.Position Clustering for Polygon Object under Dual-constrains[J].Acta Geodaetica et Cartographica Sinica,2016,45(10):1250-1259.DOI:10.11947/j.AGCS.2016.20150491.

P208

A

1001-1595(2016)10-1250-10

國家自然科學基金(41561083；41261092；41561082)；云南省自然科學基金(2015FA016)

2015-09-23

修回日期：2016-07-08

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

E-mail：woshiyuli@126.com

甘淑

E-mail：n1480@qq.com