基于密度和聚类指数改进的K－means 算法

毛 秀，冒纯丽，丁岳伟

(上海理工大学 光电信息与计算机工程学院，上海 200093)

数据挖掘就是对庞大的数据集进行分析，从而发现隐藏其中未知的关系，并以数据拥有者可理解的方式对其有价值数据总结［1］。聚类分析是将数据库中的数据按照某种规则分组或分成成若干类，使得同一类内的数据之间相似度较高，而不同类内的数据之间相似度较低［2］。各种聚类方法也被不断提出和改进，每种算法都有其自身的短处和长处，因此研究和改进各种聚类算法具有一定意义。

至今已经有多种聚类算法发展成熟，主要有基于层次的算法、基于划分的算法、基于密度的算法、基于网格的算法，模糊聚类也是当下比较流行的聚类分支。现实中人们经常使用K－means 聚类算法，相比于其他聚类算法，该算法在处理大数据方面性能明显较优［3］。目前，基于K－means 算法的聚类算法研究更是层出不穷，结合了如孤立点去除、并行化处理、密度、遗传算法、生成树、距离代价函数、加权等因素用于改进。K－means 算法的原理简单、易实现，但抗噪声能力差扰，聚类结果因不同中心点会大相径庭，人为给算法输入的k 值或偏大或偏小均会导致结果不理想。针对这些缺点，文献［2］提出了基于密度优化初始中心点的方法，文献［4］等为了获取k 值提出了新的聚类指数，文献［5］结合密度和最大最小距离法优化了中心点的选择，文献［6］提出的ADK－keans 算法对孤立点进行特别处理，提高稳定性的同时收敛速度快，聚类精度高，文献［7］先通过密度优化初始聚类中心，针对不同的k 值聚类并计算对应的聚类有效性指标本，从而确定最佳聚类数，本文将其算法简称为ASK－means算法。本文在上述工作基础上，将密度、最大距离积法和聚类指数3 方面的优势进行集成提出了改进的Kmeans 算法，简称AIK－means 算法。

1 传统K－means 聚类算法

K－means 聚类算法是把数据集X 中的样本划分到k 个簇类中，使得同一簇内之间所有样本之间的相似度最高，不同簇类的质心之间的相似度最低。设定对象集合为X={x1，x2，…，xn}，样本数为N，xi表示X中的任意对象，聚类中心点集合C={c1，c2，…，ck}。用Dist(xi，xj)衡量样本之间的相似度，Dist(xi，xj)代表对象xi，xj之间的距离，m 为对象的维度，xik为对象xi第k 个属性值，如下

聚类过程中一般使用的目标函数如下

其中，k 为聚类数;Ci为第i 个类;ci为第i 个类的聚类中心，如下

传统K－means 算法过程如下:

输入:原始的样本数据集X，聚类数k 值。

输出:k 个簇类。

(1)从样本集X 中无规则地取出k 个样本，将其当作最原始的聚类中心。(2)分别求出X 中其他样本到第一步选出的k 个中心的欧式距离，将其分给距其欧氏距离最小的簇类。(3)求各簇类的平均值，更新作为下一次聚类的中心，返回步骤(2);若准则函数收敛则算法终止。

2 改进的K－means 算法

2.1 与密度相关的基本概念

传统的K－means 算法得到局部最优解是因未考虑到数据的空间分布情况，无规则选取对象时会选到孤立点，根据不同的初始聚类中心得到的簇类也会相差很大。算法结合密度和距离则能避免孤立点被选中并且初始聚类中心之间也能保持一定间隔，分布稀疏。因此本文先从样本集中获取高密度集，再将距离因素用于高密度集优化初始聚类中心。已知样本集为X={x1，x2，…，xn}，维度为m，xi，xj均属于X。

定义1 样本密度:xi为样本集中的任意对象，将它作为中心，δ 作为邻域半径，在其δ 内的对象个数则是对象xi的密度，如下

定义2 邻域半径:

其中，n 为集合X 中的样本数，通常0 ＜δ≤1，根据实验结果选取最佳参数值。

定义3 高密度集:设定参数Minpts，样本密度不少于这个参数的对象集合就是高密度集，m 是高密度样本个数。

2.2 最大距离积法

最大最小距离法的缺点是选取的初始中心点之间距离较近且分布密集，使得本该划分为一个簇类的样本可能被分到两个或多个簇。文献［5］针对最大最小距离法的缺点提出的最大距离积法有较大的收敛速度和准确率，初始聚类中心点分散。采用高密度点对应的垂直中心点能在一定程度上扩大初始中心点存在的区域，这样有利于高密度区域能够相互融合，提高聚类的效果。最大距离积法阐述如下:

(1)根据关于密度的相关知识，得到高密度集HP={z1，z2，…，zm}，m 为此集合中的样本数量。

(2)选取HP 中欧氏距离最大的两个高密度样本对的均值作为最初的聚类中心添加入到C 中，此时C={c1，c2}。

(3)计算HP 中剩余样本到C 中样本的距离，若样本zi满足max(Dist(zi，c1)×Dist(zi，c2))，则将样本zi及其最邻近高密度点的均值作为下一个聚类中心记为c3，加入集合C 中。

(4)同理，若样本zm满足max(Dist(zm，c1)×Dist(zm，c2)×…×Dist(zm，ck－1))，则zm是最后一个聚类中心添加到集合C 中。

2.3 聚类指数index

随着k 值增大，簇内距离会相应减小，而簇间距离增大，即随着k 变化，二者朝着相反的方向改变，考虑到簇内距离与簇间距离之间的这种关系，文献［3］中提出的聚类指数index 能有效地判断聚类数k。设原始样本集合为X={x1，x2，…，xn}，聚类中心集合为C={c1，c2，…，ck}。

定义4 簇内距离是所有簇类中每个对象到其所属簇类中心的距离总和，如式(7)所示

定义5 簇间距离为所有簇类质心相互间的距离求和

定义6 聚类指数为聚类紧密度与聚类显著度之和

由定义可看出，index 达到最大时所对应的k 为最佳聚类数。随着k 值的增大，聚类中心之间计算距离和的数量也在增大，用平均簇间距离来定义聚类显著度并不合理，因此本文在这一基础上用平均簇间距离与聚类数的积表示聚类显著度。

2.4 基于密度和聚类指数改进的K－means 算法

提出结合密度和聚类指数改进的K－means 算法描述如下:

输入:样本数据集X(样本个数为n)，调节参数λ，常数Minpts。

输出:最好的k 值及对应的聚类结果。

(1)for 1 to n，根据输入的参数λ 计算样本集邻域半径δ，根据δ 计算得到每个对象xi的密度，将密度大于等于Minpts 的样本加入到高密度集HP 中。(2)在高密度集HP 中找到距离最远的两个对象zi，zj及各自的最邻近高密度点z’i，z’j组成两个高密度点对，将各高密度点对的均值加入到初始聚类中心集合C 中，将zi，zj，z’i，z’j从HP 中删除。(3)根据C 中的聚类中心进行聚类，并根据式(7)～式(11)计算此时的聚类指数index 值，并将其记录保存。(4)根据最大距离积法，在HP 剩余对象中寻找下一个高密度点对，将均值作为新的初始聚类中心加入到集合C 中，并从HP 中删除找到的高密度点对。(5)根据聚类中心集C 中的对象进行聚类，并计算对应新的聚类指数index，与上一次的index 作比较，如果indexlast＜indexlast－1，则输出上一次的聚类数k 及相应的聚类结果，算法终止，否则跳转至步骤(4)。

3 实验及结果分析

3.1 实验

文中的聚类数据为结构化数据，维度是确定的，其样本之间彼此无关，计算欧式距离作为对象相似度。为验证本文中提出算法的有效性及适用性，实验数据集采用了国际通用测试数据库UCI 中的Iris 数据集、Wine 数据集和Glass 数据集［7］，数据集的样本信息如表1 所示。

表1 数据集信息表

由于本文中提出的算法主要是基于文献［6 ～7］中的算法进行改进的，所以分别对4 个数据集采用ADK－means 算法、ASK－means 算法和本文中提出改进的K－means 算法进行聚类对照试验。实验的硬件环境为Windows XP 操作系统，2 GB 内存，用Java 代码实现。改进的K－means 算法中，参数Minpts 和参数λ的值则是通过多次试验根据聚类效果确定的。由于数据集各有特点，所以参数值也不同，试验中数据集对应的参数如表2 所示。

表2 数据集及对应的参数列表

3.2 实验结果分析比较

3.2.1 聚类结果对比分析

ADK－means、ASK－means 及AIK－means 算法对以上3 个数据集进行聚类得到的聚类正确率记为A、迭代次数记为I、误差平方值记为E、测试时间记为T，结果如表3 所示。

表3 3 种算法对各数据集聚类的结果

实验结果分析表明，表3 中算法聚类结果的运行时间取多次试验后的得到的均值，3 个算法的聚类结果均较为稳定，并无波动，得到的聚类数与实际聚类数完全一致。从表格中的正确率A 可看出，3 个数据集聚类结果中ASK－means 算法仅比ADK－means 算法的准确率略高，AIK－means 算法具有最高的准确度，且其误差平方E 的值最小，也能反映其的聚类结果质量最佳。虽AIK－means 算法对各数据集聚类时迭代次数均比ADK－means 算法多一次，但算法运行的实际时间却要比ASK－means 少，可见其收敛速度快，算法时间复杂度低。文献［7 ～8］中及其他类似于ASKmeans 的算法需通过对k 从2 ～kmax迭代计算各聚类评价指标的算法，相比于这些算法AIK－means 算法则减少了众多不必要的计算，既节省了硬件资源也大幅缩短了算法的运行时间。从3 个算法的输入来看，除ADK－means 算法需要用户输入聚类数k，另两个算法均不要求k 值的输入，AIK－means 算法能根据index的值智能判断最佳聚类数，有效避免了人为给出k 值对聚类结果造成的不良影响。

结合以上分析可看出，基于密度和聚类指数的改进得到的AIK－means 算法比考虑了密度参数的ADKmeans 算法有更高的准确率和收敛速度，ASK－means算法准确度比ADK－means 算法略高，虽其也能在无k值输入的前提下找到最佳的聚类数但要付出的代价远比AIK－means 算法多，所以AIK－means 算法既有ADK－means 算法运行效率高的特点又有ASKmeans 算法能自动获取最佳聚类数k 的特点，弥补了另外两种算法的不足。

3.2.2 index 指标对比分析

聚类发展至今已有诸多学者提出了诸多聚类有效性指标，并没有统一的评判标准，所以本文提出的算法采用了比较年轻的index 值作为聚类有效性指标，AIK－means算法中index 值的变化如图1 所示，根据3 个算法的最终聚类结果可分别计算出index 值，如图2 所示。

图1 AIK－means 算法中变化的聚类指数index

图2 3 个算法对各数据集聚类结果的index 值

以Iris 数据集为例，改进的聚类算法中，当聚类数k 由2 变成3 时，index 的值在增长，然而当k 增长到4时，index 的值骤降，说明当聚类数为3 时，得到的聚类结果聚类紧密度和聚类显著度都达到了巅峰值，因此3 即为最佳聚类数。其余两个数据集的聚类结果同样验证了这一规律，index 值会随着k 值增大而增大，但并不单调递增，当达到最大值后就会递减，最大值时对应的k 值就是数据集的最佳聚类数，对应的聚类结果质量自然也是最好的。若k 值选择不当，index 的值相对于最佳聚类数对应的index 值会小，k 值偏差越大，index 值越小，对聚类结果的影响越大。从图2 可看出，同一数据集中AIK－means 算法的index 值最大，同一算法聚类的前提下Iris 数据集的index 值最大，可见index 值能间接反映聚类质量，和正确率、误差平方E 成正相关的关系。

实验结果表明，本文提出的结合密度和聚类指数改进的K－means 算法能得到合理的聚类数，聚类中心的选取更为合理，能有效避免独立点对聚类结果的影响，也并未形成局部最优解的可能，聚类质量也有大幅提升。

4 结束语

K－means 算法原理简单、易于实现、收敛速度快，在各领域到了广泛应用，因此研究改进K－means 算法具有重要意义［9－12］。针对k 值需给定的缺点，学者们结合方差分析理论、全协方差矩阵、有效性指标等来解决这一问题，结合遗传学算法则可有效避免局部最优解，在样本量较大时还可随机抽取样本量聚类，以提高算法效率［13－15］。但没有任何算法是完美的，只有根据原数据的特点正确地选择算法，才能在准确率和效率之间找到最佳平衡点。实验证明了本文提出的算法去除了选取初始聚类中心的随机性，使聚类结果稳定，且基于密度选择初始聚类中心能有效避免孤立点对聚类结果的影响，不会形成局部最优解的情况。最大距离法则使得所选取的初始聚类中心足够稀疏，以防聚类中心过度密集导致一个类被分成多个类，聚类指数能帮助得到最佳聚类数k。正确率的提升反映了该算法比较高的聚类质量。

本文中的参数λ 及密度阈值Minpts 受到人的主观能动性影响，在没有先验知识的前提下需通过多次尝试决定最佳参数值，对不同的数据库参数不同，增大了工作量，算法的伸缩性也被减弱，有待更好的方法来确定这些参数值，若能解决这一问题收敛速度可更快。随着采用的数据集样本量和维度的增大，样本集若维度过高应采用合理的方式降维，选取中心点的方式也需要根据实际情况改进使之更有合理性，算法中用欧式距离作为衡量对象相似度的标准，实际应用中的数据大多为非结构化数据，欧式距离并不能完全反映出对象之间的相似度，这些将是本算法下一步改进的方向。

［1］ David Hand，Heikki Mannila，Padhraic Smyth.Principles of dara mining［M］.Beijing:China Machine Press，2003.

［2］ Onoda T，Sakai M，Yamada S.Careful seeding method based on independent components analysis for k－means clustering［J］.Journal of Emerging Technologies in Web Intelligence，2012，4(1):51－59.

［3］ 贾永娟.基于密度的改进K－means 文本聚类算法研究［D］.临汾:山西师范大学，2014.

［4］ 尹成祥，张宏军，张睿，等.一种改进的K－means 算法［J］.计算机技术与发展，2014，24(10):30－33.

［5］ 邓海，覃华，孙欣.一种优化初始中心的K－means 聚类算法［J］.计算机技术与发展，2013，23(11):42－45.

［6］ 刑长征，谷浩.基于平均密度优化初始聚类中心的K－means算法［J］.计算机工程与应用，2014，50(20):135－138.

［7］ 何云斌，肖宇鹏，万静，等.基于密度期望和有效性指标的K－均值算法［J］.计算机工程与应用，2013，49(24):105－111.

［8］ 王朔，顾进广.基于K 值改进的K－means 算法在入侵检测中的应用［J］.工业控制计算机，2014，27(7):93－97.

［9］ 张琳，陈燕，汲业，等.一种基于密度的K－means 算法研究［J］.计算机应用研究，2011，28(11):4071－4073，4085.

［10］Bhise R B，Thorat S S，Supekar A K.Importance of data mining in higher education system［J］.IOSR Journal of Humanities and Social Science，2013，6(6):18－21.

［11］Gu Chengjie，Zhang Shunyi，Liu Kai，et al.Fuzzy kernel Kmeans clustering method based on immune genetic algorithm［J］.Journal of Computational Information Systems，2011，7(1):221－231.

［12］聂晓伟.基于K－means 算法的雷达信号预分选方法［J］.电子科技，2013，26(11):55－58.

［13］翟东海，鱼江，高飞，等.最大距离法选取初始簇中心的K－means 文本聚类算法的研究［J］.计算机应用研究，2014，31(3):713－719.

［14］刘凤芹.K－means 聚类算法改进研究［D］.济南:山东师范大学，2013.

［15］张永晶.初始聚类中心优化的K－means 改进算法［D］.长春:东北师范大学，2013.