附加邊界約束的k-means空間點聚類算法研究

蔡躍輝 王倩 朱偉

摘 要 針對常規K-means算法通常采用理想的歐氏空間距離作為評判點集之間空間相似度的唯一指標，未考慮邊界對點集之間的阻礙作用，提出了一種附加邊界約束的K-means空間點聚類算法。該算法綜合了K-means與線段在多邊形內部的判定算法，使得空間點數據在邊界存在的前提下，進一步利用點與各聚類中心的最短歐氏距離來表達點集之間的空間鄰近性。基于3個數據集的實驗結果表明：該算法對于多邊形凸處區域的孤立點群與常規K-means算法結果一致，但凹處的點會受到邊界的阻礙作用，不會歸并為同類，而且聚類后各簇中心必位于邊界內部。

關鍵詞 K-means;邊界;凹多邊形;約束;空間點;聚類

引言

K-means作為空間數據挖掘劃分聚類算法當中的一種出色算法，關于其研究主要集中在k值確定，受初始聚類中心的影響較大，容易產生局部最優解，算法時間開銷大4個方面。如張陽等通過一定的方法減少K-means算法迭代的次數[1]，從而提高K-means的運行效率。

目前顧及空間障礙對K-means聚類影響的研究還未引起學者足夠的重視，關于其研究成果較少，而空間障礙對聚類的影響卻日益引起人們的重視。如劉啟亮等針對現實空間對象之間存在障礙物與連通體的情況，于2013年在ASCDT算法[2]的基礎上提出了ASCDT+算法[3]，實現了顧及障礙物與連通體的空間點數據聚類。

凹多邊形邊界作為空間障礙的一種，影響點集之間的直通性，基于此種現狀，本文提出一種附加邊界約束的K-means聚類算法，取名為CBCK。

1 附加邊界約束的K-means空間點聚類算法

CBCK主要由改進的K-means與線段是否在多邊形內兩個算法融合而成。

1.1 線段是否在多邊形內

邊界為凸多邊形且點集位于多邊形內部，則任意兩條線段都位于多邊形內部，但當多邊形為凹多邊形時，則點集中待聚類點與聚類中心連接的線段就可能不在多邊形內部。如下圖1所示，線段PQ與多邊形<！--[if gte vml 1]> <！[endif]--><！--[if ！vml]--><！--[endif]-->中AF、AB邊內交，那么此線段肯定不位于多邊形之內。張宏等學者在《地理信息系統算法基礎》一書中給出了線段是否在多邊形內部的判定條件——“如果線段與多邊形相鄰兩交點的中點位于此多邊形內部，那么此相鄰兩交點之間的全部點都將位于多邊形的內部”，并采用反證法給出了證明[4]。判斷線段是否位于多邊形內部算法的偽代碼如下所述，此過程的時間開銷大約為o（M），M指代多邊形邊的數量。

<！--[if gte vml 1]> <！[endif]-->

1.2 改進的K-means算法

針對多邊形可能包含凹形頂點的情況，使得待聚類點與各個聚類中心連接的線段可能不在多邊形內部，首先計算點與k個聚類中心的歐氏距離。然后考慮邊界約束的影響，將點與聚類中心線段不在多邊形內部對應的距離設置為+∞，最后將當前點與k個聚類中心中最短直線距離的中心歸為一類。整個算法的時間復雜度大約為o（QNKM），其中Q代表整個算法迭代至滿足下式（1）的次數， N為待聚類點個數，K為待分類數，常規K-means時間開銷為o（QNK）。

<！--[if gte vml 1]> <！[endif]--><！--[if ！vml]--><！--[endif]-->

2 實驗結果與對比分析

1個模擬數據集（圖2）和1個實例數據集（圖4）將用來評估CBCK的聚類效果。

2.1 模擬數據

設圖中邊界為行政區劃邊界，點為居民地。實驗時，將K-means與CBCK算法的初始k值設置為2，初始聚類中心采用人為事先定義，均保持一致。

而K-means算法僅計算點與聚類中心之間最短的直線距離，因此將凹形邊界兩側歐氏距離較小的點歸為一類。不僅于此，由于凹處兩側的點基本呈現為對稱分布，而K-means的聚類中心通常采用簇的幾何中心，從而使得S1簇聚類中心——C1偏移到邊界線的外部。

<！--[if gte vml 1]> <！[endif]-->

上圖2、3中，設定K-means與CBCK聚類的k值為8，初始聚類中心人為設置成一致。對比圖2與圖3，可以發現原始數據都被分成8類。其中圖2與圖3中，S1、S4、S5、S8簇的點集劃分與聚類中心都是一致的。由此可見，位于多邊形凸形區域的孤立點群，CBCK與K-means聚類算法在同等條件下的結果是一致的。而圖2（S2、S3與S6、S7）與圖3中明顯存在差異。

2.2 實例數據

<！--[if gte vml 1]> <！[endif]-->

在這個實驗中，CBCK算法被應用到某地一個珍貴苗木分區管理當中，圖3中S1～S10的符號表示苗木所在地點，共有363棵苗木。該苗圃邊界較為復雜，具備多個凹形區域，四面環水。日前該苗圃欲加強對園區的日常管理，計劃建設10個苗木管理臨時分中心，并在每個臨時管理分中心配備一名專職管理人員。針對此種情況，應用CBCK算法，得到如下圖4的聚類結果。根據圖4所示，S1～S10為CBCK得到的10個分區結果，C1～C10（五角星的位置）為10個分區管理中心的建設位置。這樣的聚類結果，使得分區既考慮到實際情況（河流不可直接通過，因此河流兩側的樹木未歸為一類），又使得管理分中心都位于邊界線的范圍之內（管理分中心不可建設于河流當中），同時讓各簇的珍貴苗木到其分管理中心的距離之和最少，使得管理人員的通行時間最短，從而提高了管理效率。

3 結束語

本文提出了一種附加邊界約束的K-means空間點聚類算法，通過1個模擬和1個實例數據集，可以發現：在空間點數據聚類時，CBCK算法不僅考慮點與各聚類中心之間的最短歐氏距離，同時考慮點與各聚類中心之間是否存在邊界的限制，使得位于多邊形凹形區域兩側的點不會因為歐氏距離較短而被歸并為一類，從而使得聚類結果更加貼近實際需要。同時CBCK算法使得各簇的聚類中心必不會超越邊界的限制，從而可以確保在一些特殊情況下聚類中心的合理性，如國界線附近點集的聚類（聚類中心不能超越國家邊界線的范圍），如上圖4應用中的聚類中心——臨時分中心不應建設在河流當中。

同時應該指出，CBCK作為K-means均值聚類算法的一個改進，也存在K-means算法的諸多缺陷，如初始聚類中心的選擇，需提前確定K值，數據量大聚類時間開銷大等，特別是初始聚類中心的自適應選取方法，這也是本文作者后續文章當中欲加突破的研究方向。

參考文獻

[1] 張陽，何麗，朱顥東.一種改進的k-means動態聚類算法[J].重慶師范大學學報（自然科學版），2016，33（1）：97-100.

[2] Deng M，Liu Q，Cheng T，et al. An adaptive spatial clustering algorithm based on delaunay triangulation[J]. Computers，environment and urban systems，2011，35（4）：320-332.

[3] Liu Q，Deng M，Shi Y. Adaptive spatial clustering in the presence of obstacles and facilitators[J]. Computers & geosciences，2013（56）：104-118.

[4] 張宏，溫永寧，劉愛利，等.地理信息系統算法基礎[M].北京：科學出版社，2006：31-32.