一种融合K-means和快速密度峰值搜索算法的聚类方法

盛　华　张桂珠

1(江南大学物联网工程学院　江苏 无锡 214122)2(江南大学轻工过程先进控制教育部重点实验室　江苏 无锡 214122)



一种融合K-means和快速密度峰值搜索算法的聚类方法

盛华1张桂珠2

1(江南大学物联网工程学院江苏 无锡 214122)2(江南大学轻工过程先进控制教育部重点实验室江苏 无锡 214122)

K-means算法的初始聚类中心是随机选取的，不同的初始中心输入会得出不同的聚类结果。针对K-means算法存在的问题，提出一种融合K-means算法与聚类的快速搜索和发现密度峰算法的聚类算法(K-CBFSAFODP)。该算法是这样考虑的：类簇中心被具有较低局部密度的邻居点包围，且与具有更高密度的任何点都有相对较大的距离，以此来刻画聚类中心；再运用K-means算法进行迭代聚类，弥补了K-means聚类中心随机选取导致容易陷入局部最优的缺点；并且引入了熵值法用来计算距离，从而实现优化聚类。在UCI数据集和人工模拟数据集上的实验表明，融合算法不仅能得到较好的聚类结果，而且聚类很稳定，同时也有较快的收敛速度，证实了该融合算法的可行性。

聚类K-means算法CBFSAFODP算法初始聚类中心密度信息熵

0　引　言

聚类分析是一种无监督的机器学习方法，是数据挖掘中的重要研究方向之一[1]。它基于“物以类聚”原理，即在同一个簇中的数据对象之间具有较高的相似度，而在不同簇数据对象间具有较低的相似度。目前聚类分析已经广泛地应用到许多领域，如模式识别、数据分析、图像处理、市场分析、客户关系管理等[2]。聚类分析的常用方法可大致划分为五类：基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法[3]。

在数据挖掘下的聚类分析方法中，K-means算法是运用最广泛的基于划分的算法。它理论证实可靠、算法简单可行、收敛速度很快，对大数据集的处理很有效果。但K-means算法也存在一些缺陷：对K值的选择没有准确依据、聚类结果的好坏严重依赖初始聚类中心的设定、容易陷入局部最优解、只能处理数值属性的数据以及无法检测到的非球形簇[4]。

CBFSAFODP算法(Alex Rodriguez 和 Alessandro Laio 在 Science 上发表了一篇名为《Clustering by fast search and find of density peaks》的文章，本文姑且称这篇文章中的算法为CBFSAFODP)是属于数据挖掘下聚类分析方法中一种应用广泛的基于密度的算法。该算法简单新颖、对初始值不敏感、灵活性好、能检测非球形簇以及能有效地处理大数据集，在解决聚类初始中心[5]选取方面很有针对性，目前已被应用到数据挖掘。然而一些单一的聚类方法往往得不到最佳的聚类效果。

为了克服CBFSAFODP算法在聚类效果上的不足，本文提出一种融合K-means算法与聚类的快速搜索和发现密度峰算法的聚类算法。K-CBFSAFODP是把K-means算法融入到CBFSAFODP中去，在执行CBFSAFODP算法选取好聚类中心后，再运用K-means算法进行迭代聚类，弥补了K-means聚类中心随机选取导致容易陷入局部最优的缺点。该算法为聚类算法选择初始聚类中心提供了一种新的思路，能够更加合理地选取聚类数K以及初始聚类中心，极大程度上减少K-means算法因初始聚类中心的不合理选取导致聚类结果的不稳定性[6]，以及过多依赖参数选择问题。实验结果表明，K-CBFSAFODP比单独的K-means、CBFSAFODP具有更好的聚类效果。

1　聚类的快速搜索和发现密度峰算法

1.1算法思想

CBFSAFODP算法[7]基于这样的设想：类簇中心被具有较低局部密度的邻居点包围，且与具有更高密度的任何点都有相对较大的距离。对于每一个数据点需要计算两个量(ρi和δi)：一是局部密度；二是与高于该点的所有局部密度中与该点距离[8]的最小值，来刻画聚类中心。然后对每个cluster确定其边界区域[9]，再将其中的数据点进一步分为cluster core和cluster halo，从而实现聚类的方法。

1.2算法聚类中心的选取

S={xi|xi∈Rn,i=1,2,…,n},IS={1,2,…,n}。设ρi包含Cj(j=1,2,…,k)个簇，Cj(j=1,2,…,k)表示初始的聚类中心，dij=dist(xi,xj)表示数据点xi与xj之间的(某种)距离。

(1) 样本xi与xj之间的欧氏距离：

(1)

(2) xi局部密度ρi：包括Cut-off kernel 和 Gaussian kernel两种计算方式。

Cut-off kernel:

(2)

其中，如果x<0，那么χ(x)=1，否则χ(x)=0;dc是一个截断距离。其实就是与点xi的距离小于dc的点的个数(不包括自己)，这意味着对于大数据集，分析结果对于dc的选择具有很好的鲁棒性。根据大量实验表明，dc一般取聚类中所有数据点之间相互距离按升序排列的2%位置的距离数值定义为dc。

Gaussian kernel:

(3)

对比定义可知，cut-off kernel为离散值，Gaussian kernel为连续值。相对而言，后者产生冲突的概率较小，即不同数据点具有相同局部密度之概率更小。

(3) 数据点xi的δi是点到任何比其密度大的点的距离的最小值。

则可定义如下：

(4)

图1　数据点按照密度降序排列　　图2　图1中数据的决策图

由图2不难发现，第1号和第10号数据点由于同时具有较大的ρ值和δ值，于是从数据集中脱颖而出，而这两个数据点恰好是图1所示数据集中的两个聚类中心。此外，编号为26、27、28的三个数据点在原始数据集中是“离群点”，它们在图2中也有特点：其δ值很大，但ρ值很小。

(5) 由于图2对确定聚类中心起到决定作用，因此也将这种由(ρi,δi)对应的图称为决策图。然后，需要注意的是，在确定聚类中心时，采用的是定性分析而不是定量分析，且包含了主观因素，如图3所示。不同的人可能得出不同的结果，聚类中心就很难分辨了。

图3　决策图中聚类中心难以确定例子

对于这些在决策图中无法用肉眼判断出聚类中心的情形(CBFSAFODP算法聚类中心个数的确定用“automatically”确实不太合适)，给出一种确定聚类中心个数的方法，即计算一个将ρ值和δ值综合考虑的量：

γi=ρiδii∈IS

(6) 然而“若干个”到底是取多少个？本文算法首先把降序排列好的γ在坐标平面上画出来，以下标为横轴，γ为纵轴，如图4所示。非聚类中心的γ值比较平滑，而从非聚类中心过渡到聚类中心时γ值有一个明显的跳跃，这个跳跃用肉眼或数值检测都可以判断出来。

图4　降序排列γ值示意图

1.3CBFSAFODP算法步骤

Step1初始化及预处理：

Step1.1给定用于确定截断距离dc的参数t∈(0,1)；

Step1.2计算距离dij，并令dij=dji,i

Step1.3确定截断距离dc；

ni=0,i∈IS;

for i=1,2,…,N

{δqi=dmax;

for j=1,2,…,i-1

{

if(dist(xqi,xqi)<δqi)

{

δqi=dist(xqi,xqj);

nqi=qj;

}

}

}

Step3对非聚类中心数据点进行归类：

for i=1,2,…,N

if(cqi=-1)cqi=cnqi

Step4若nc>1，则将每个cluster中的数据点进一步分为cluster core和cluster halo：

Step4.1初始化标记hi=0,i∈IS；

for i=1,2,…,N-1

{

for j=i+1,i+2,…,N

{

if(ci≠cj且dist(xi,xj)

{

}

}

}

Step4.3标识cluster halo：

for i=1,2,…,N

2　K-means算法

2.1K-means算法的思想

K-means算法[10]是以k为参数，把n个数据对象分为k个簇，每个簇内的数据对象具有较高的相似度，而不同簇之间具有相对较低的相似度。相似度是通过计算一个簇内数据对象的平均值得来的，相似度的定义是划分关键，本文中是计算数据对象之间的赋权欧式距离[11]。K-means算法的基本思想是：首先在n个数据对象中随机地选择k个对象作为初始聚类中心;接着按最小距离原则来计算每个数据对象到聚类中心的距离，将其赋给最近的簇。然后，重新计算每个簇的平均值，计算收敛函数，直到各个聚类的中心不再变化，算法则终止。否则，重复上述过程。

2.2K-means算法的一般过程

输入：簇的数目k以及n个数据对象的数据集。

输出：E不变时满足目标函数值最小的k个簇。

Step1从给出的n个数据对象中随机选出k个对象作为初始聚类中心来执行；

Step2计算数据对象与各个簇的聚类中心的距离，将每个数据对象赋给与其距离最近的簇；

Step3重新计算每个新簇的均值，作为新的簇的聚类中心，nj表示第j个簇数据对象个数，Cj表示第j个簇；

(5)

(6)

Step5直到E不再发生明显的变化时，算法终止；否则转向Step2。

3　融合K-means算法与聚类的快速搜索和发现密度峰算法

3.1K-CBFSAFODP算法思想

针对K-means算法随机选取k个点作为初始聚类中心进行迭代操作而导致聚类结果的不稳定，本文提出了融合K-means算法与聚类的快速搜索和发现密度峰算法。该算法首先需要对每个数据计算两个量，即ρi和δi,通过这两个量来刻画聚类中心。 ρi和δi值越大，该点越是可能是聚类中心。再运用K-means算法进行迭代聚类，且引入信息熵计算赋权欧式距离来更准确地规范各对象的差异程度，从而更好地聚类。

3.2使用熵值法确定各数据对象间赋权欧氏距离

由于要对初始聚类中心以及k值做大量的预处理，来提高聚类的质量，本文引入了信息熵来度量各属性权重，计算各数据对象之间的权重系数。熵是体系混乱程度的度量。一个属性的变异程度越大，则整个系统越是有序的，且该对象属性的信息熵会越小，它提供的信息量就会越大，权重也就会变得越大；反之亦然。

(1) 设数据集有m个对象、n维属性：

本文引入信息熵，计算各数据对象的赋权欧氏距离，可以更加入微地分析各个对象的差异程度。

(2) 首先对数据对象属性进行标准化处理，使不同量纲的数据可以进行比较：

(7)

其中，Mij为数据对象xi的第j维属性值比重，xij为属性值。

(3) 分别计算第j维属性的熵值和权值：

熵值：

(8)

权值：

(9)

(4) 赋权欧氏距离的计算公式为：

(10)

在选择赋权欧氏距离作为相似性度量后，各个对象之间的差异程度能够准确地计算出来，从而可以提高聚类的准确度。

3.3K-CBFSAFODP算法描述

输入：待聚类的n个数据对象的数据集。

输出：满足目标函数最小的k个簇。

Step1使用熵值法计算数据对象赋权欧式距离dij,并令dij=dji,i

Step5令γi=ρiδi， i∈IS， γ值越大，越有可能是聚类中心；

Step7计算数据对象与各个簇的聚类中心的距离，将每个数据对象赋给与其距离最近的簇；

Step8根据式(5)重新计算每个新簇的均值，作为新的簇的聚类中心；

Step9根据式(6)计算E值；

Step10直到E不再发生明显的变化时，算法终止；否则转向Step7。

4　实验分析

为了验证融合算法的效果，本文对CBFSAFODP算法 、K-means算法以及K-CBFSAFODP算法进行了对比实验。实验采用了Matlab R2013a开发环境，Intel(R) Core(TM)2 Duo CPU 2.20 GHz,6 GB 内存，在Windows 7操作系统上运行。

实验使用了UCI机器学习数据库中的Iris、Wine和自定义人工数据集Dataset作为实验数据。对K-means算法、CBFSAFODP以及本文改进的算法K-CBFSAFODP在选取不同初始聚类中心运行100次后进行比较鉴定，发现融合的K-CBFSAFODP算法在聚类误差平方和、迭代次数、聚类时间和聚类的准确率等方面有极大的优化提升。实验的数据集概述情况如表1所示。

表1　实验数据集的构成描述

为了说明初始中心选取的有效性，本文选取UCI 上Iris数据进行验证。Iris数据集包含150条样本记录，分别取自3种不同的鸢尾花的花朵样本，每一类各50条记录，其中每一条记录都含有4个属性：sepal length、sepal width、petal width和petal length，共聚成3类。初始聚类中心选取对比如表2所示。

表2　初始聚类中心选取对比

由表2可以看出，本文算法的Iris数据集初始化聚类中心与实际数据中心非常接近，表明该算法对Iris数据比较有效，同理对于Wine和dataset数据集也有一样的效果。

由图5可得知，聚类的每条属性在聚类过程中作用是真实不同的，应加以区分对待。K-means算法恰恰忽略了数据对象属性对聚类作用的差异度，使得聚类结果与本来聚类结果之间存在很大差异。

图5　计算得到Iris数据集各属性对应的权值

如表3所示，可以看出本文算法在误差平方和以及迭代次数上明显优于K-means算法。

表3　比较两个算法在UCI数据集的误差平方和以及迭代次数

关于算法聚类结果的评价，除了常用的聚类误差平方和、聚类时间和聚类准确率评价方法之外，还可以采用F-measure指标、Rand指数和Jaccard系数对聚类结果进行比较分析。后三个评价指标都是在已知正确分类信息的前提下对聚类算法的聚类结果进行评价的有效指标。

F-measure采用信息检索的精确率和召回率思想。数据所属的类i可看作是集合Ni中等待查询的项；由算法产生的簇Ck可看作是集合Nk中检索到的项；Nik是簇Ck中类i的数量。类i和簇Ck的精确率和召回率分别是：

精确率:Precision(i,Ck)=Nik/Nk

召回率:Recall(i,Ck) = Nik/Ni

F-Measure是Precision和Recall的加权调和平均(α是参数):

当α=1时，就是最常见的F1，即：

F-measure可看成分类i的评判分值。对聚类结果来说，其总F-measure可由每个分类i的F-measure加权平均得到：

其中：|i|为分类i中所有对象的数目。

Rand指数和Jaccard系数评价指标的定义如下：设U和V分别是基于数据集的两种划分；其中U是已知正确划分，而V是通过聚类算法得到的划分，定义a、b、c、d四个参数。设a表示U和V都在同一类的样本对数目；b表示在U中为同一类，而在V中却不是同一类的样本对数目；c表示在V中为同一类，而在U中却不是同一类的样本对数目；d表示U和V都不在同一类的样本对数目。n(n-1)/2=a+b+c+d,其中，n为数据集中所有样本数。令M=a+b+c+d，则M表示所有的样本对。Rand指数和Jaccard系数的定义如下：

Rand指数：R=(a+d)/M

Jaccard系数：J=a/(a+b+c)

其中，R表示Rand指数；J表示Jaccard系数。

由上述定义可知，F-Measure是Precision和Recall的加权调和平均，最优划分期望其值尽可能大；Rand指数表示聚类结果与原始数据样本分布的一致性；Jaccard系数表示正确聚类的样本对越多，聚类效果越好。

由图6、图7和图8可知，F-measure、Rand指数和Jaccard系数的三个聚类有效性指标显示，K-CBFSAFODP算法优于K-means算法和CBFSAFODP算法。图9、图10和图11是对Iris、Wine和自定义数据集Dataset分别应用K-means、CBFSAFODP和K-CBFSAFODP聚类准确率对比图。从图中可以看出，K-CBFSAFODP算法的聚类准确率要明显优于K-means算法和CBFSAFODP算法。且融合算法K-CBFSAFODP首先进行了一个优化初始聚类中心的过程，因此比原有算法更加稳定，能得到更准确的聚类中心，快速地到达收敛。总之，实验结果表明，本文提出的K-CBFSAFODP具有稳定性强、准确率高、收敛速度快的优点。

图6　聚类结果的F-measure指标　　图7　聚类结果的Rand指数

图8　聚类结果的Jaccard系数　　图9　Iris数据集上的测试

图10　Wine数据集上的测试　　图11　dataset数据集上的测试

5　结　语

K-means算法初始聚类中心选取的随机性所带来的聚类结果的不稳定性，以及要求用户事先指定K值，限制了许多实际应用。本文引入了信息熵以及快速搜索和查找聚类的密度峰，用信息熵对数据对象属性进行赋权来计算对象间的距离，来规范数据的属性，提高聚类的准确率；然后利用数据点的局部密度以及高于该点的所有局部密度中与该点距离的最小值，对数据集的初始中心进行预处理，来刻画初始聚类中心。提出了融合CBFSAFODP算法和K-means算法的聚类算法K-CBFSAFODP。融合的算法给聚类中心以及聚类个数K值的选取提供了新的有效依据，从而摆脱了随机选取聚类中心导致的聚类结果的不稳定性和用户操作的难度，大大提高了聚类的质量和稳定性。

[1] Datta Souptik,Giannella Chris,Kargupta Hillol.Approximate Distributed K-Means Clustering over a Peer-to-Peer Network[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(10):1372-1388.

[2] Zhou Tao,Lu Huiling.Clustering algorithm research advances on data mining[J].Computer Engineering and Applications,2012,48(12):100-111.

[3] Wang Jun,Wang Shitong,Deng Zhaohong.Survey on challenges in clustering analysis research[J].Control and Decision,2012,27(3):321-328.

[4] 於跃成,刘彩生,生佳根.分布式约束一致高斯混合模型[J].南京理工大学学报,2013,37(6):799-806.[5] 黄敏,何中市,邢欣来,等.一种新的K-means聚类中心选取算法[J].计算机工程与应用,2011,47(35):132-134.

[6] Fahim A M,Salem A M,Torkey F A,et al.An efficient enhanced k-means clustering algorithm[J].Journal of Zhejiang University SCIENCE A,2006,7(10):1626-1633.

[7] Rodriguez A,Liao A.Machine Learning.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496.

[8] 陈磊磊.不同距离测度的K-Means文本聚类研究[J].软件,2015,36(1):56-61.

[9] Qiu Baozhi,Wang Bo.Cluster boundary detection technology for categorical data[J].Journal of Computer Applications,2012,32(6):1654-1656.

[10] 吴夙慧,成颖,郑彦宁,等.K-means算法研究综述[J].现代图书情报技术,2011(5):28-35.

[11] 高孝伟.熵权法在教学评优中的应用研究[J].中国地质教育,2008,17(4):100-104.

A CLUSTERING METHOD COMBINING K-MEANS AND FAST SEARCH ALGORITHM OF DENSITY PEAKS

Sheng Hua1Zhang Guizhu2

1(SchoolofIoTEngineering,JiangnanUniversity,Wuxi214122,Jiangsu,China)2(KeyLaboratoryofAdvancedProcessControlforLightIndustry(MinistryofEducation),JiangnanUniversity,Wuxi214122,Jiangsu,China)

The initial clustering centre of K-means algorithm is selected randomly, different initial centre inputs will get different clustering results. Aiming at this problem of K-means algorithm, we proposed a clustering algorithm which combines K-means algorithm and clustering with the fast density peaks search and finding algorithm (K-CBFSAFODP). This algorithm has the following considerations: the class cluster centre is surrounded by neighbour points with lower local density, and has relatively larger distance to any point with higher density, this is used to depict the cluster centre; then the K-means algorithm is employed for iterative clustering, this makes up the defect that to randomly select K-means clustering centre leads to falling into local optima easily. Moreover, the algorithm introduces entropy method to calculate the distance, thereby realises the optimisation of clustering. It is demonstrated by the experiments on UCI datasets and artificial simulation dataset that this combination algorithm can get better clustering results, and the clusters is very stable as well; meanwhile it also has fast convergence speed. These confirm the feasibility of the combination algorithm.

ClusteringK-means algorithmCBFSAFODP algorithmInitial clustering centresDensityInformation entropy

2015-07-01。江苏省自然科学基金项目(BK201401 65)。盛华，硕士生，主研领域：数据挖掘，大数据。张桂珠，副教授。

TP18

A

10.3969/j.issn.1000-386x.2016.10.058