附加边界约束的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.