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

劉呈熠，武 芳，鞏現(xiàn)勇，行瑞星，杜佳威

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

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

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

1 面要素聚集度

1.1 聚集度的定義

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

(1)

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

(2)

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

1.2 指標(biāo)對比分析

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

表1 對比參數(shù)計算方法

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

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

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

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

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

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

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

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

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

2.1 聚類中心的識別

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

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

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

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

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

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

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

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

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

2.3 邊緣檢測與群組合并

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

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

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

表2 邊緣檢測參數(shù)

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

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

3 NPFC方法實現(xiàn)

根據(jù)NPFC方法原理，本文設(shè)計如下實現(xiàn)流程，如圖8所示。

(1) 拓?fù)潢P(guān)系獲取與參數(shù)計算。據(jù)文獻(xiàn)[24]方法，構(gòu)建面要素的約束Delaunay三角網(wǎng)和Voronoi圖，獲取鄰近關(guān)系。逐個計算鄰近面的邊界最短距離d(i,j)，并得到截斷距離dc，依照式(1)得到聚集度δ(i)。

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

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

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

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

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

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

NPFC方法具有以下優(yōu)勢：①設(shè)計的聚集度參數(shù)能夠準(zhǔn)確反映面要素分布密度，有利于根據(jù)分布疏密對面群聚類，符合人類認(rèn)知。②兼顧面要素特征和群組整體特征，按照“局部→整體”的順序?qū)崿F(xiàn)聚類，有效克服了自然面群疏密程度不一導(dǎo)致聚類條件難以確定的問題。③采用鄰近距離和分布密度的雙重約束獲取聚類結(jié)果，滿足自然面群的制圖要求，有利于后續(xù)對分布特征的挖掘。

4 試驗與結(jié)果分析

4.1 試驗過程

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

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

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

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

4.2 結(jié)果對比

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

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

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

參照人工聚類結(jié)果，分別計算上述3種聚類結(jié)果的定量評價指標(biāo)見表3。在Jaccard系數(shù)、F值方面，值越大，說明與參照結(jié)果越相似；在熵方面，值越小，類歸屬的不確定性越低，與參照結(jié)果越相似?？梢姡疚姆椒ㄔ趰u嶼群聚類效果方面更具優(yōu)勢；在耗時方面，MST算法略快于MSSCP算法和本文算法。

表3 島嶼群聚類結(jié)果定量化評價

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

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

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

表4 湖泊群聚類結(jié)果定量化評價

4.3 參數(shù)分析

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

圖13 不同參數(shù)的初聚類結(jié)果Fig.13 Initial clustering results with different parameters

圖14 不同參數(shù)的NPFC方法聚類結(jié)果Fig.14 Island clustering results with different parameters by NPFC

5 結(jié) 論

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

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