张登荣, 杜 要, 寻丹丹, 刘 婷

(1. 杭州师范大学遥感与地球科学研究院,浙江 杭州 311121; 2. 浙江省城市湿地与区域变化研究重点实验室,浙江 杭州 311121)

Kernel-Kmeans：一种基于核密度估计的空间聚类算法

张登荣1,2, 杜 要1,2, 寻丹丹1,2, 刘 婷1,2

(1. 杭州师范大学遥感与地球科学研究院,浙江 杭州 311121; 2. 浙江省城市湿地与区域变化研究重点实验室,浙江 杭州 311121)

利用核密度估计的非参数检验特性,提出了一种基于核密度估计的Kmeans改进算法Kernel-Kmeans.该算法综合了基于划分的聚类思想以及基于密度的聚类思想,首先由核密度估计算法计算样本点的密度分布,然后对密度分布栅格进行窗口计算并取极大值来初步确定聚类中心以及聚类数量,最后将聚类中心和聚类数量作为参数输入Kmeans算法得到聚类结果.以OpenStreetMap发布的京津冀城市群点数据开展实验研究,采用算法运算时间与轮廓系数为验证指标,与Kmeans算法、极大极小改进Kmeans算法进行了对比验证，结果表明Kernel-Kmeans算法的精度高于后两者.

核密度估计；Kmeans算法；轮廓系数

0 引言

聚类是数据挖掘中的重要研究内容,它将数据划分为若干个簇,使每个簇内具有较高的相似性,簇间的相似性则较小[1].聚类分析是探索性的分析,没有统一的标准,聚类之后的结果也是不可预知的.聚类的整个过程是无监督学习的过程.目前根据聚类算法的思想可以将算法分为以下几类：基于划分的聚类方法,主要代表为Kmeans算法；基于层次的聚类算法,包括CURE、BIRCH和ROCK等；基于密度的聚类算法,主要有DBSCAN、GDBSCAN等；基于网格的聚类算法,主要包括WaveCluster、STING等；基于神经网络的算法、基于统计学的聚类算法等[2].

Kmeans算法是较经典的聚类算法之一,凭借其简单、效率高的优点而得到广泛应用.但是Kmeans算法也有其局限性,比如算法需要预先设定参数分类数量K值,但是聚类为无监督学习过程,用户对数据了解不够的情况下很难给出合适的值[3-4].Kmeans算法的另一个局限性体现在算法随机设置初始聚类中心,聚类结果容易陷入局部最优解,并且聚类的结果不稳定.

针对Kmeans的缺陷,许多研究人员提出了一系列的改进措施.翟东海等[5]根据距离越远的点被分到一个簇内的可能性越低,提出极大极小方法：计算样本两两之间的距离,将距离最大的两个样本作为聚类中心,将与前面两个聚类中心距离的乘积值最大的样本作为第三个聚类中心,以此类推直到选出第k个聚类中心.该方法避免了随机确定初始聚类中心引起的局部最优解,但容易受孤立点以及噪声数据的影响.Kmeans算法中高密度区域的点会被低密度区域的点分割,而噪声点往往处于低密度区域,何佳知等[6]将数据集分为高密度区与低密度区两部分,将密度值最大的点作为第一个聚类中心,然后在高密度区域的点集中选取距离第一个初始聚类中心一定距离阈值外的点作为第二个初始聚类中心,以此类推选择k个聚类中心.该方法通过划分高密度及低密度区域避免了孤立点的影响,利用距离阈值避免了局部最优解.Al-Daoud[7]首先找到样本数据集各数据方差最大的属性,将数据集按照该属性进行排序,然后将排序后的数据集分为k组,每组数据的中位数就是初始聚类中心.该方法的局限性是在属性的选择上,适合某一属性权重较大的情况.

本文将密度的思想引入到Kmeans算法中,提出一种基于密度的Kernel-Kmeans算法：首先通过核密度分析将数据集分为高密度区及低密度区,然后在高密度区域利用空间分析的焦点统计等方法确定一定区域内的最大密度点,形成极大密度点集.最后将极大密度点集作为初始聚类中心输入Kmeans算法.该算法避免了Kmeans算法随机确定初始聚类中心引起的局部最优解以及孤立点的影响.同时极大密度点集的个数可以作为算法的参数K值,用户将得到适合聚类数据的K值推荐.

1 理论与方法

1.1 核密度估计原理

空间分析[8]是为了解决地理空间问题而进行的数据分析与数据挖掘,从GIS目标之间的空间关系中获取派生的信息和新的知识,是从一个或多个空间数据图层中获取信息的过程.本文采取的空间分析方法主要包括核密度分析、焦点统计等.

核密度[9]是概率论中用来估计未知的密度函数,属于非参数检验方法之一.概念上每个点上方覆盖着一个平滑的曲面,在点所在位置表面值最高,随着距离的增加表面值减小,直到距离等于搜索半径时值为零.输出栅格的每个像元值为所有叠加在改像元上的表面值之和.由此,核密度估计法将一个点集转化为表现出连续密度变化的表面.

核密度估计的实现方法是：选择适当的核函数K,计算输出栅格的每个像元的核密度估计值f(x).公式如下：

(1)

其中,K是二维空间的核函数,h是带宽,n是带宽范围内观测点的数量,i=1,…,n.通过式(1),可以将离散的点集转化成平滑的密度变化图,从而显示出其空间分布模式.密度值越高,则表明该点的聚集程度越高.

本文采用的核平滑函数是基于Silverman[10]提出的二次核函数,公式如下：

(2)

1.2 Kernel-Kmeans算法

图1 Kernel-Kmeans算法流程图Fig. 1 Kmeans-Kernel algorithm flow chart

针对Kmeans算法K值以及聚类中心的不确定性，本文提出结合密度概念的Kmeans聚类算法(图1).该方法中的密度概念主要通过核密度估计算法实现.首先将数据样本利用它们的位置属性进行核密度估计,获取一幅可以表现出连续密度变化的栅格影像.影像的像素值代表着数据样本中该位置的密度,即像素值越高密度越大.设定一阈值,将影像分为高密度区域以及低密度区域,然后在高密度区域通过一系列的空间分析步骤(焦点统计,栅格计算等)提取出一定区域内密度值最高的点,形成极大密度点集.将极大密度点集作为聚类中心,极大密度点集的个数作为K值.算法中将影像设置为低密度区域以及高密度区域,低密度区域也会得到一定区域内最大密度点,但是用低密度区域内的点聚类效果不好,所以只在高密度区域进行极大密度点集的获取.

本文算法描述如下：

Step 1 将样本数据集进行核密度估计算法,获得一张带有连续密度值的栅格影像,记作影像A；

Step 2 根据影像,设定阈值,将影像划分为低密度区域以及高密度区域；

Step 3 在高密度区域利用焦点统计工具处理,得到极大密度点集(即密度值最大)；

Step 4 通过重分类等空间分析工具提取极大密度点集；

Step 5 将极大密度点集作为参数输入Kmeans算法,极大密度点集在算法中的作用是聚类中心,K值为极大密度点集的个数；

Step 6 对样本数据集中的每个样本,计算与极大密度点集中每个点的距离,将其归纳到与样本距离最近的点所代表的簇中；

Step 7 迭代,直到满足结束条件,得到聚类分析的结果.

2 案例研究

2.1 数据源

OpenStreetMap[11]是一个网上地图协作计划,目标是创造一个内容自由且能让所有人编辑的世界地图.OpenStreetMap强调使用本地知识，贡献者们使用航空图像、GPS 设备与传统的地区地图来确保其精确性和时效性.

本文采用OpenStreetMap发布的京津冀城市群的点数据，从OpenStreetMap官网(http://www.openstreetmap.org)获取，主要是关于咖啡馆、地铁站点等特殊地点的位置信息.数据源中有14 083条记录,如图2所示.

图2 数据源Fig. 2 Data source

图3 核密度图Fig. 3 Kernel density result

2.2 案例结果

Kernel-Kmeans算法操作分为两步,第一步为极大密度点集的获取,第二步将极大密度点集作为Kmeans算法的聚类中心,进行Kmeans算法聚类操作.详细步骤如下：

首先对数据源进行核密度分析.图3清楚地展示数据源的密度变化,红色越深的地方密度值越高,点的聚集程度也就越高.其次，因为极大密度点集的获取需在高密度区域进行,故将图像按照一定阈值分为低密度区域以及高密度区域.忽略低密度区域,在高密度区域进行焦点统计,统计结果与核密度图进行栅格相减,结果为零的像素就是一定区域内像素值最大的点.通过空间分析的重分类、栅格转矢量等操作提取全部结果为零的点,形成极大密度点集,如图4所示.最后,将极大密度点集作为Kmeans算法的初始聚类中心,多次迭代后得到聚类结果,如图5所示.

图4 初始聚类中心Fig. 4 Initial cluster center

图5 聚类结果图Fig. 5 Clustering result

2.3 算法验证

2.3.1 时间验证

图6 算法时间比较Fig. 6 Time comparison of two algorithms

本实验通过聚类时间以及聚类精度来评价聚类的结果,聚类精度用轮廓系数来衡量.原始的Kmeans算法随机选择初始聚类中心后通过迭代不断修改聚类中心,直到聚类中心的变化很小,过程中迭代浪费了大量时间.本文算法利用核密度估计算法等得到极大密度点集,将极大密度点集作为初始聚类中心,减少迭代次数.图6为两种算法的时间比较.

由图6可以看出,Kmeans算法所用时间随数据量的增加而增加,但是每次增加时间不固定,甚至有数据量增加而所用时间减少的情况，考虑是因为初始聚类中心的随机性导致迭代次数的不稳定所造成.本文算法所用时间同样随数据量的增加而增加.比较两种算法,Kmeans算法增加较为明显,在数据量较小时,Kmeans算法迭代较少,时间效率优于本文算法；但是随着数据量的增加,Kmeans算法迭代次数增加,本文算法效率逐渐超过Kmeans算法.

2.3.2 效果验证

对于聚类结果一般基于簇内以及簇间两个方面来评价.一个较好的聚类结果通常拥有较高簇内距离以及较大的簇间距离,即拥有较小的簇内凝聚度以及较大的簇间分离度.轮廓系数则较好地结合了凝聚度与分离度[12].样本i的轮廓系数的计算公式为：

(3)

假设样本i被分到x簇,式中a(i)为样本i到x簇中所有其他样本的平均值,b(i)为i到所有非x簇样本的平均距离的最小值.所有点的轮廓系数的平均值就是该聚类结果的轮廓系数.由式(3)可以看出轮廓系数的取值为[-1,1].若轮廓系数为负数,则说明到簇内距离大于簇间距离,聚类结果很糟糕.同时,轮廓系数越趋近于1,则说明类内距离越小,聚类效果越好[13].

为说明Kernel-Kmeans的有效性,实验比较了Kmeans算法、极大极小方法[5]以及本文提出的Kernel-Kmeans算法的精度.结果如表1所示.

表1 3种算法精度比较(轮廓系数)Tab. 1 Accuracy comparison of three algorithms (contour coefficient)

可见，对同一组实验数据,Kmeans算法由于初始聚类中心的随机性而导致多次试验有不同的结果,表1中的结果为多次的平均数.极大极小方法与Kernel-Kmeans算法都只有一种结果,比较稳定.因此,极大极小方法和Kernel-Kmeans算法都改进了Kmeans算法这一缺陷.就精度而言,Kmeans算法轮廓系数的平均值为0.562,极大极小方法为0.66,Kernel-Kmeans算法为0.690.可以看出,两种算法都对Kmeans算法精度有所改进,Kernel-Kmeans算法略高于极大极小方法.

3 结论

本文提出Kernel-Kmeans算法,将核密度估计方法结合到Kmeans算法中,改进了Kmeans算法聚类数量以及初始聚类中心的不确定性.该算法首先由核密度估计算法得到密度连续变化的栅格图,然后利用焦点统计获得极大密度点集,通过一系列的空间分析步骤将点集提取出来,利用极大密度点集确定聚类中心以及聚类数量K,然后将每个样本分配到与它距离最近的聚类中心所代表的簇中,重新计算聚类中心,至前后聚类中心变化较小.因Kernel-Kmeans算法给出较为准确的聚类中心,因此能减少迭代次数,有较好的聚类效果.

对本文算法的时间验证结果说明，Kmeans算法随着数据量的增加耗时也逐渐增加.尽管由于初始聚类中心的随机性,导致迭代次数也具有随机性,算法所用时间不固定,但是总体趋势仍表现为随着数据量的增加,算法耗时增加.Kernel-Kmeans算法经过核密度估计算法和一系列的空间分析提取极大密度点集,将极大密度点集作为初始聚类中心可以减少迭代次数.因此本文算法在数据量较少时,效率低于Kmeans算法,主要原因在于数据量少时Kmeans算法迭代次数本来就少,而本文算法提取极大密度点集耗时较多.数据量较多时Kmeans算法迭代次数增加,效率逐渐低于本文算法.

采用轮廓系数比较了Kmeans算法、极大极小方法以及Kernel-Kmeans算法的精度,结果表明Kernel-Kmeans算法的精度高于Kmeans算法以及极大极小方法.由此，时间验证和精度验证均证明了Kernel-Kmeans算法的有效性.

[1] JAIN A K, DUBES R C. Algorithms for clustering data[J]. Englewood Cliffs Prentice Hall,1988,32(32):227-229.

[2] 戴涛.聚类分析算法研究[D].北京：清华大学,2005.

[3] 王玲,薄列峰,焦李成.密度敏感的半监督谱聚类[J].软件学报,2007,18(10)：2412-2422.

[4] CELEBI M E, KINGRAVI H A, VELA P A. A comparative study of efficient initialization methods for the K-means clustering algorithm[J]. Expert Systems with Applications,2013,40(1):200-210.

[5] 翟东海,鱼江,高飞,等.最大距离法选取初始簇中心的K-means文本聚类算法的研究[J].计算机应用研究,2014,31(3)：713-715.

[6] 何佳知,谢颖华.基于密度的优化初始聚类中心K-means算法研究[J].微型机与应用,2015(19)：17-19.

[7] AL-DAOUD M B. A new algorithm for cluster initialization[C]// World Enformatika Conference. Istanbul: [s.n.],2005:74-76.

[8] 郭仁忠.空间分析[M].北京：高等教育出版社,2001.

[9] 李存华,孙志挥,陈耿,等.核密度估计及其在聚类算法构造中的应用[J].计算机研究与发展,2004,41(10)：1712-1719.

[10] SILVERMAN B W. Density estimation for statistics and data analysis[M]. New York: Chapman and Hall,1986:296-297.

[11] HAKLAY M, WEBER P. OpenStreetMap: user-generated street maps[J]. IEEE Pervasive Computing,2008,7(4):12-18.

[12] 朱连江,马炳先,赵学泉.基于轮廓系数的聚类有效性分析[J].计算机应用,2010(S2)：139-141.

[13] 张靖,段富.优化初始聚类中心的改进K-means算法[J].计算机工程与设计,2013,34(5)：1691-1694.

Kernel-Kmeans: A Spatial Clustering Algorithm Based on Kernel Density Estimation

ZHANG Dengrong1,2, DU Yao1,2, XUN Dandan1,2, LIU Ting1,2

(1. Institute of Remote Sensing and Earth Sciences, Hangzhou Normal University, Hangzhou 311121, China; 2. Key Laboratory of Urban Wetland and Regional Change Research of Zhejiang Province, Hangzhou 311121, China)

Basing on the non parametric test of kernel density estimation, this paper proposes an improved Kmeans algorithm based on kernel density estimation, which is called Kernel-Kmeans. This algorithm combines the idea of partition on the basis of clustering and density on the basis of clustering. Firstly, the density distribution of the sample points is calculated by the kernel density estimation algorithm, then the density distribution grid is calculated and the maximum value is calculated to determine the cluster centers and the number of clusters, finally, the cluster center and cluster quantity are input onto the Kmeans algorithm to obtain cluster results. In this paper, the point data of the city group of Beijing, Tianjin and Hebei, which is released by OpenStreetMap, is studied, the operation time and silhouette coefficient are used to verify the index. Compared with the Kmeans algorithm, the minimax improved Kmeans algorithm, the results show that Kernel-Kmeans has higher precision than the latter two.

kernel density estimation; Kmeans algorithm; silhouette coefficient

10.3969/j.issn.1674-232X.2017.03.018

2016-09-12

国家“十二五”863计划重大专项课题(2013AA12A403).

刘 婷(1985—)，女，讲师，博士，主要从事空间数据挖掘分析与应用研究.E-mail：71173618@qq.com

TP301.6

A

1674-232X(2017)03-0324-06