空間知識挖掘的自然面群聚集度聚類方法

劉呈熠，武 芳，鞏現勇，行瑞星，杜佳威

信息工程大學地理空間信息學院，河南 鄭州 450001

以湖泊、島嶼為代表的自然面群是地圖的重要組成部分，其形狀、尺寸、方向等幾何特征存在較大差異，而且具有整體分散、局部聚集、聚集程度不一的分布特征。自然面群的空間分布特征是影響地圖綜合的重要因素[1-2]，識別、挖掘空間聚集特征是研究的難點之一[3]。當前，面群的空間聚類方法已有不少成果[4]，根據算法類型主要可分為：①劃分聚類算法。通過不斷優化目標函數來達到預設聚類要求，如k-means算法[5]、SOM算法[6]等。這類算法通過多次迭代得到最優的聚類結果，但易陷入局部最優問題，且受預設值制約。②層次聚類算法。在面群鄰近關系的基礎上，采用分割或聚合的策略獲得聚類結果，如最小生成樹法[7]、Delaunay三角網法[8-12]、圖卷積神經網絡算法[13]、MSSCP算法[14]、緩沖區法[15]等。這類算法多適用于相似度高、分布規則的面群聚類問題，但對于幾何特征差異大、分布特征復雜的自然面群聚類不適用。③密度聚類算法。以密度為核心參數，不斷聚合鄰域范圍內滿足預設規則的對象來獲得聚類結果，如DBSCAN算法[16]、似最小生成樹法[17]、密度峰值算法[18-19]等。這類算法能夠識別異形簇，但多用于點簇聚類。

分布密度作為描述地物聚集程度的一項重要指標，其背后往往隱含某種地理意義，如湖泊群密度反映區域降水量，島嶼群密度反映地質構造[20]等。根據Gestalt原理的鄰近性和相似性原則[21-22]，圍繞自然面要素的鄰近距離和分布密度，本文提出一種基于聚集度和邊界最短距離的自然面群聚類方法(natural polygon features clustering,NPFC)，并進行如下工作：①為克服分布密度定義不適用的問題，定義一種新的面要素分布密度度量參數——聚集度，分析不同條件下聚集度的變化特點，驗證其有效性；②為解決離散面聚合問題，根據聚集度向量識別聚類中心，并提出一種基于聚類中心的群組生長模型；③為消除過度劃分問題，設計邊緣檢測和群組合并策略，獲得更優的聚類結果。

1 面要素聚集度

1.1 聚集度的定義

地物的分布密度通常指單位面積內地物對象的數量[23]，數量越多，該地物的分布密度就越高。然而，面要素具有一定尺寸，計數區域難以統一劃定；同時采用計數方式忽視了面要素的尺寸差異，無法正確反映地物的分布密度。面要素的分布密度受到尺寸、鄰域大小和鄰近面數量共同影響。面要素尺寸一般采用面積來描述，本文采用面積與對應Voronoi圖面積的比值描述其聚集程度；考慮到面要素的一階鄰域是其最鄰近、影響最直接的區域，將該區域作為計算分布密度的鄰域范圍，并根據文獻[18]選用高斯核函數控制鄰近距離對中心面要素分布密度的影響程度；鄰近面數量為其一階鄰域范圍內包含的所有面要素數量。據此本文提出面要素“聚集度”的概念，記為δ(i)，其計算公式如下

(1)

式中，φ(i)為面要素i的一階鄰近面要素及其本身；S(j)為面要素j的面積；Svor(j)為面要素j的Voronoi圖面積；d(i,j)為面要素i與j的邊界最短距離；dc表示截斷距離，當d(i,j)

(2)

圖1 聚集度的計算Fig.1 Calculation of aggregation index

1.2 指標對比分析

為驗證“聚集度”的有效性，利用3種不同分布的面群數據進行測試，并引入2個描述面要素聚集程度的代表性參數，即“面積比”“強度函數”[14]，對比分析不同參數對面群分布密度的度量能力，相關參數計算方法見表1。為區分三者結果差異，采用折線圖進行比較，“面積比”和“強度函數”數值采用左坐標軸，“聚集度”數值采用右坐標軸。

表1 對比參數計算方法

(1) 面要素尺寸相同、鄰近距離不同條件下的參數對比。如圖2(a)所示，共有17個尺寸形狀相同的正方形組成，其中1—9號分布集中、10—17號分布稀疏。如圖2(b)所示，根據參數變化區間分為1—9號、10—17號兩組。1—9號正方形“面積比”“強度函數”變化幅度小，未反映鄰近面數量、鄰近距離對分布密度的影響；“聚集度”變化幅度大，其中5號鄰近面數量最多，邊界最短距離均較小，“聚集度”最大；2、4、6、8號“聚集度”次之；1、3、7、9號鄰近面數量少，邊界最短距離最遠，“聚集度”最小。10—17號正方形“面積比”相較于前組略有下降，未能體現分布密度變化；“強度函數”和“聚集度”均能清晰反映分布密度變化情況，面要素分布越稀疏，“強度函數”越大，“聚集度”越低。可見，在尺寸固定，鄰近距離變化時，“強度函數”和“聚集度”均能反映面要素分布的疏密程度。特別的，尺寸與鄰近距離均相同時，鄰近面數量越多，本文“聚集度”區分性更強，有利于本文方法中聚類中心的識別，如圖2(b)中的5號聚集度明顯突出。

圖2 尺寸相同條件下參數對比Fig.2 Parameters comparison under the same size condition

(2) 面要素尺寸不同，鄰近距離相同條件下的參數對比。如圖3(a)所示，共有13個不同尺寸的正方形，相鄰正方形鄰近距離相同，1—13號尺寸逐漸增大。“面積比”隨著面要素尺寸增大緩慢上升；“強度函數”基本保持不變；聚集度變化較大，6號聚集度全局最高，相較于3號，兩者面要素數量相同，但6號鄰域內面要素尺寸均大于3號，聚集度更大，8—13號“聚集度”波動下降，反映了邊緣面分布密度整體下降的趨勢。可見，“面積比”和“強度函數”描述面要素分布密度的能力較弱，且存在多個相同值，難以區分面要素分布密度差異。在鄰近距離相同時，面要素尺寸越大、鄰近面數量越多、鄰近面尺寸越大，“聚集度”就越大，準確反映面要素分布密度差異，有利于聚類中心的識別及聚集度向量的構建。

圖3 鄰近距離相同條件下參數對比Fig.3 Parameters comparison under the same distance condition

(3) 面要素尺寸與鄰近距離均不同條件下的參數對比。如圖4(a)所示，共有20個形狀尺寸、鄰近距離均不同的面要素，1—10號分布集中，11—20號分布松散。在第1組(1—9號)中，2、4號“面積比”較高，“強度函數”較低，“聚集度”較高，3個參數均能反映2、4號分布密度高的特點。在第2組(10—17號)中，“面積比”波動小，與第1組差異較小，不利于不同分布密度群組的分離；“強度函數”波動幅度大，但兩組邊緣面要素數值相近，例如6號與17號，不利于確定群組邊緣面要素的歸屬；相較于第1組，第2組“聚集度”大幅降低，邊緣面要素聚集度差異明顯，有利于確定群組邊界，同時16號“聚集度”局部最高，表明在面群松散時依然能夠識別聚類中心。可見，在尺寸、鄰近距離均不同的情況下，“聚集度”在反映面要素的分布密度方面更有優勢，有利于實現不同分布密度面群的聚類。

圖4 多差異條件下的參數對比Fig.4 Parameters comparison under the condition of multiple differences

綜上所述，本文提出的“聚集度”能夠準確描述面要素的分布密度，即面要素尺寸越大、鄰近距離越小、鄰近面數量越多、鄰近面尺寸越大，面要素分布越密集，“聚集度”就越大，為本文聚類方法中描述自然面群的分布密度提供重要的參數依據。

2 面向自然面群的聚類方法

根據自然面群的鄰近性和密度相似性，本文圍繞面要素聚集度和邊界最短距離，提出了一種面向自然面群的聚類方法，主要包含以下3個環節：①聚類中心的識別；②基于聚集度向量的初聚類；③邊緣檢測與群組合并。

2.1 聚類中心的識別

理想情況下，群組內分布集中、聚集度相近，且越接近群組中心，聚集度就越高，聚類中心就是群組內聚集度最大的面要素。然而實際情況下，一個視覺認知群組內往往存在多個聚集度為局部極大值的面要素，鄰近面以其為中心聚集分布，形成面簇。通過識別這類面要素，就能將鄰近面聚合成簇，達到初聚類目的。本文以一階鄰域作為識別范圍，若面要素的聚集度均高于鄰近面的聚集度，則該面要素被視為聚類中心。例如，圖5共有28個形狀尺寸各異，分布不均勻的面要素組成。根據式(1)計算聚集度構建分布圖，得到處于“峰頂”的局部高點，即為聚類中心，如圖5(b)所示。最終識別的聚類中心為4、16、29號。

圖5 聚類中心的識別Fig.5 The identification of cluster center

2.2 基于聚集度向量的初聚類

定義1：聚集度向量。聚集度向量是面要素pi指向其一階鄰域內聚集度高于pi，且邊界最短距離最小的面要素pj的組合，記為pi→pj，本文稱之為pi從屬于pj。

定義2：Grow算法。以群組{pi}中面要素pi為起點，獲得其從屬面集合{qj}，按照邊界最短距離由小至大讀取。設置距離規則：①d(pi,qj)

除聚類中心外，每個面要素均能作為聚集度向量起點，指向高于自身聚集度的最近面要素，構成從屬關系，如圖6(a)所示，顏色越紅則聚集度越大，越綠則聚集度越小，箭頭為聚集度向量，起點為低聚集度面，終點為最近的高聚集度面，低聚集度面從屬于高聚集度面，例如“1→3”為1號從屬于3號，“1→3→4”為1號、3號均從屬于4號。

根據聚集度向量，每個面要素均指向聚類中心，即局部區域的面要素均從屬于該區域的聚類中心。那么，從聚類中心出發，沿著聚集度向量逆向搜索，局部區域內的所有面要素均可達。因此，將聚類中心作為群組的第1個對象，按序對每個加入群組的面要素執行Grow算法，構建初始群組。其中，距離規則①控制組內鄰近面邊界最短距離的上限，保證群組邊界收斂；距離規則②控制組內鄰近面邊界距離的增長速度，防止距離突變導致離散面加入群組。如圖6(b)所示，雖然存在“31→14”從屬關系，但不滿足距離規則①，31無法加入黃色群組；存在“33→18”從屬關系，但不滿足距離規則②，33無法加入黃色群組。

通過執行Grow算法，面要素圍繞聚類中心構成面簇，但仍存在部分離散面要素，例如30—33。根據聚集度向量識別離散面要素的中心，作為“次聚類中心”，如圖6(a)所示，30、32、33的次聚類中心為33。以次聚類中心為起點，執行Grow算法，直至無法形成新的聚類群組，則初聚類結束，初聚類結果如圖6(b)所示。

圖6 基于聚集度向量的初聚類Fig.6 Initial clustering based on aggregation index vector

2.3 邊緣檢測與群組合并

初聚類根據聚集度向量將離散面要素聚合成簇，保證群組內分布緊密。然而，當面群分布密度不均勻時，一個視覺認知群組內易存在多個聚類中心，導致初聚類過度劃分，不符合人類認知，如圖6(b)中人工判讀時，藍色組、黃色組和紫色組應為一組，但由于存在多個聚集度中心，該組在初聚類中被劃分為多個群組。為消除過度劃分問題，本文設計鄰近群組的邊緣檢測和合并策略，分為以下環節：

(1) 邊緣檢測。根據面要素鄰近關系，若存在pm屬于群組Gi，pn屬于Gj，且pm與pn相鄰，則pm為Gi的邊緣面，pn為Gj的邊緣面，Gi與Gj相鄰，如圖7(a)所示，5與20相鄰，則藍色組與黃色組為相鄰群組，紅色虛線框內面要素為藍色組和黃色組的邊緣面。

圖7 邊緣檢測與群組合并Fig.7 Edge detection and group merging

表2 邊緣檢測參數

(3) 群組合并。若鄰近群組邊緣面數量均大于1，且滿足合并規則①②③，群組被合并；若存在鄰近群組邊緣面數量等于1，且滿足合并規則②③，群組可被合并；否則鄰近群組不合并。

為避免出現合并不充分問題，需對新合并群組再次進行邊緣檢測和群組合并，直至不存在需合并的鄰近組，則聚類完成。如圖7(b)所示，原藍色組、黃色組、紫色組通過檢測合并成一組，紅色組31號面要素未通過檢測不合并。

3 NPFC方法實現

根據NPFC方法原理，本文設計如下實現流程，如圖8所示。

(1) 拓撲關系獲取與參數計算。據文獻[24]方法，構建面要素的約束Delaunay三角網和Voronoi圖，獲取鄰近關系。逐個計算鄰近面的邊界最短距離d(i,j)，并得到截斷距離dc，依照式(1)得到聚集度δ(i)。

(2) 構建聚集度向量，識別聚類中心。遍歷所有面要素，以面要素pi為例，根據鄰近關系和距離集合{d(i,j)}將鄰近面要素由近至遠排序；逐一讀取鄰近面pj，若δ(pj)>δ(pi),則構建聚集度向量pi→pj；若所有鄰近面聚集度值均小于pi，則pi識別為聚類中心。

圖8 NPFC方法流程Fig.8 Flow chart of NPFC method

(3) 遍歷所有聚類中心，以pi為例，初始化dmax=dc，對pi執行Grow算法，若有面要素加入，則更新dmax，并對其余面執行Grow算法，直至群組內不再有新面加入，則該步驟結束。

(4) 剩余離散面的聚類。遍歷未加入群組的離散面，執行步驟(2)，獲取次聚類中心，并以次聚類中心為初始面執行步驟(3)。直至遍歷完成，則初聚類結束。

(5) 邊緣檢測。遍歷所有初聚類群組內面要素，根據面要素鄰近關系獲取群組鄰近關系，識別鄰近群組的邊緣面，執行步驟(6)。

(7) 合并群組。若存在鄰近組被標記為“合并”，則將所有標記的鄰近組合并，并執行步驟(5)；否則聚類結束，輸出聚類結果。

NPFC方法具有以下優勢：①設計的聚集度參數能夠準確反映面要素分布密度，有利于根據分布疏密對面群聚類，符合人類認知。②兼顧面要素特征和群組整體特征，按照“局部→整體”的順序實現聚類，有效克服了自然面群疏密程度不一導致聚類條件難以確定的問題。③采用鄰近距離和分布密度的雙重約束獲取聚類結果，滿足自然面群的制圖要求，有利于后續對分布特征的挖掘。

4 試驗與結果分析

4.1 試驗過程

為檢驗算法的有效性，本文選取自然面群的典型代表：島嶼群和自然湖泊群作為試驗數據，按照試錯法調整參數，得到聚類結果。

圖9 島嶼群聚類過程Fig.9 The process of islands clustering

圖10 湖泊群聚類過程Fig.10 The process of lakes clustering

試驗區域自然面群聚集程度不一，局部區域存在多個聚類中心，導致初聚類后群組數量較多。通過邊緣檢測與群組合并后，群組數量明顯減少，群組內面要素鄰近距離變化和分布密度差異均處于視知覺的可接受范圍內，符合人類認知。

4.2 結果對比

為體現本文方法在處理自然面群聚類上的優勢，選用MSSCP聚類方法[14]和基于邊界最短距離的MST聚類方法進行對比試驗。試驗環境是Intel i7-1750 H，2.20 GHz處理器，Windows10操作系統。通過試錯法調整參數，分別得到最優聚類結果。將試驗結果與專業制圖員的聚類結果進行對比，并采用Jaccard系數、F值、熵值[25-26]以及算法耗時作為聚類結果評價參數進行定量化評價。

以人工聚類結果為參照，選取MSSCP方法、MST方法和本文方法的試驗結果進行對比，如圖11所示，人工聚類共有83個群組；MSSCP方法循環次數為3次，共有117個群組；MST方法距離閾值為800 m，共有219個群組；本文方法參數設置與4.1節一致，共有193個群組。在MSSCP聚類結果中，藍色虛線框內島嶼群未能按照分布輪廓進行聚類，這是由于兩個群組之間的“通道”存在少量島嶼，MSSCP方法無法將其分離；黑色虛線框內島嶼群分布密度差異大，MSSCP方法和MST方法均無法對其進行有效分離；而本文方法對上述區域島嶼群均能有效分離，更接近人工聚類結果。

圖11 不同方法的島嶼群聚類結果Fig.11 Island clustering results with different methods

參照人工聚類結果，分別計算上述3種聚類結果的定量評價指標見表3。在Jaccard系數、F值方面，值越大，說明與參照結果越相似；在熵方面，值越小，類歸屬的不確定性越低，與參照結果越相似。可見，本文方法在島嶼群聚類效果方面更具優勢；在耗時方面，MST算法略快于MSSCP算法和本文算法。

表3 島嶼群聚類結果定量化評價

在對自然湖泊群進行聚類試驗時，參照人工聚類結果，選取MSSCP方法、MST方法和本文方法的最優聚類結果，如圖12所示。人工聚類共有30個群組，MSSCP方法循環次數為1次，聚類結果共有17個群組；MST方法距離閾值為500 m，聚類結果共有54個群組；本文方法參數設置與4.1節一致，聚類結果共有52個群組。對比人工聚類結果可以發現，在紅框區域內，MSSCP聚類結果對群組的邊緣面要素歸屬存在錯誤，如圖12(g)所示，MST方法和本文方法結果與人工聚類結果接近；在黑框區域內，由于MSSCP方法對局部分布密度變化不敏感，MST方法無法感知局部分布密度差異，兩者的聚類結果與人工聚類結果存在較大差異，如圖12(h)、圖12(j)所示，本文方法對局部距離和分布密度變化較為敏感，能夠識別局部特征差異，與人工聚類結果更為接近。

圖12 不同方法的自然湖泊群Fig.12 Lake clustering results with different methods

參照人工聚類結果，在Jaccard系數、F值方面，本文方法略高于其他方法；在熵方面，本文方法遠低于MSSCP方法和MST方法，說明本文方法在自然湖泊群聚類方面存在優勢；在耗時方面，本文方法略快于MSSCP方法和MST方法，見表4。

表4 湖泊群聚類結果定量化評價

4.3 參數分析

為提高NPFC方法調節參數效率，以島嶼群局部區域為例，分析不同參數閾值對聚類結果的影響。在識別聚類中心的基礎上，調整距離增長閾值σdis，得到不同聚類結果，如圖13所示。σdis越小，群組數量越多，群組劃分越細致；隨著σdis增大，聚類的群組數量逐漸增大，但增長幅度放緩，并接近于聚類中心數量，如圖13(d)、圖13(e)初聚類結果基本一致。值得注意的是，σdis并非越小越好，需根據不同目標比例尺下最小感知閾值進行確定，在此給出參數調整的建議，即目標比例尺越大，聚類結果應越細致，σdis應減小；反之應增大。

圖13 不同參數的初聚類結果Fig.13 Initial clustering results with different parameters

圖14 不同參數的NPFC方法聚類結果Fig.14 Island clustering results with different parameters by NPFC

5 結 論

空間聚類能夠挖掘自然面群的空間分布知識，是自然面群制圖綜合的重要步驟。針對自然面群幾何差異大、分布整體分散、局部集中，且集中程度不一的特點，本文提出了一種自然面群的聚類方法。首先，定義一種面要素分布密度度量參數——聚集度，能較好顧及面要素自身尺寸、鄰近距離、鄰近面數量和鄰近面尺寸對分布密度的影響；圍繞聚集度和鄰近距離設計了一種群組生長模型，能夠以局部聚集度極大值面要素作為聚類中心，聚合鄰近面；顧及群組鄰近性和密度相似性，基于邊緣聚集度和群組鄰近距離提出了鄰近群組的邊緣檢測和群組合并策略，有效解決了過度劃分的問題。對比試驗結果證明，聚集度能夠準確地描述面要素分布密度差異；同時NPFC方法的自然面群聚類效果更好。

今后工作中需要進一步解決以下3方面的問題：①自然面群的制圖綜合，利用聚類結果提取的群組分布范圍、密度差異等空間分布約束，更好地服務于自然面群的制圖綜合；②參數閾值設置的問題，研究參數閾值與比例尺的定量關系，得到目標比例尺下，人類視知覺對自然面群分布密度差異的最小識別閾值，并據此實現參數閾值的自適應調整；③本文方法對其他面群聚類問題的適用性。