引入自检策略的进化K－means算法

宋天勇，赵 辉，李万龙，王 璐，田世元

（长春工业大学计算机科学与工程学院，吉林 长春 130012）

0 引言

随着大数据时代的到来，人们越来越关注如何从海量数据中高效地提取更多的知识.聚类就是通过计算对象间的相似度，按照类间相似性小、类内相似性高智能的将待聚类集合划分成若干簇［1－2］.聚类结果的准确度及划分簇的可解释性成为评价聚类算法的主要依据.聚类方法可分为划分法、层次法、基于密度的方法及基于网格的方法等.其中基于划分法中的K－means算法凭借其简单、收敛速度快等优势在工业中得到了广泛的应用［3］，但K－means算法有2个主要缺陷：（1）K的个数需要用户输入；（2）局部最优问题，即K－means产生的解是局部最优解而非全局最优解.目前已有很多文献已对K－means的缺陷进行了改进，例如：文献［1－2］提出通过迭代的选取彼此距离最远的点作为初始质心的方法；文献［4－7］在聚类时考虑密度因素，通过在密度较大的区域选取合适的初始质心；文献［8］提出将传统K－means算法与智能算法相结合的改进算法；文献［9］提出一种改进聚类准则函数的K－means算法；文献［10］提出了计算效率较高的进化K－means聚类算法（Fast Evolutionary Algorithms for Clustering，F－EAC），提出对部分簇进行分裂来调整聚类效果；文献［11－12］对F－EAC算法进行改进，提出基于一种全局性分裂算子的改进算法.F－EAC算法在分裂的过程中忽视了周边簇对待分裂簇的影响，而王留正等只改进了分裂算子的选取，待分裂簇更新过于频繁问题并未得到改善.针对这一问题，本文提出一种改进的进化K－means算法，通过在分裂完成后对分裂的结果进行评价来检测是否需要重新计算待分裂簇，阻止错误的待分裂选取，从而得到更好的聚类结果.本文通过理论分析和实验验证了引入自检策略的F－EAC算法相对于F－EAC算法具有较大的优越性.

1 进化K－means算法

1.1 K－means算法简介

K－means在运行前要求用户输入聚类个数K，然后从待聚类集合Σ中随机选取K个对象作为初始质心，通过迭代计算最终得到K个稳定的质心.传统K－means中每个质心可代表一个簇，每一次迭代中要求计算Σ中全部点与K个质心的距离，Σ中的每个点被分配到与其最近的簇中.一轮划分完毕后，根据划分好的K个簇计算出新的K个质心，通过收敛准则函数是否收敛来判断质心是否稳定，若稳定则聚类结束，否则继续迭代.其聚类准则函数为

其中：P表示集合中的点；Ci代表第i个簇；dist（P，Ci）表示点P到簇Ci的质心的距离.

1.2 F－EAC算法简介

F－EAC算法将变异与K－means强大的局部搜索能力相结合，通过适应度函数SP（Ci）评价簇的变异率，簇的适应度值越高其变异率就越低.在待分裂的簇中随机选择2个点作为分裂的基准，每次将待变异的簇分裂后通过执行K－means算法将变异的结果迅速稳定.F－EAC算法根据分裂的结果可以自适应调整K值，使聚类的结果更加合理.

设xi表示簇中的一个对象，则其适应度函数SS（xi）定义为

其中：a（xj）表示xj到其他簇质心的距离；b（xi）表示xi到其所属簇质心距离；SS（xi）表示簇中对象xi的稳定度.整个簇的适应度记为f（Ci），即

其中｜Cj｜表示簇Cj中成员的数目.根据公式（3）簇的变异率

2 改进F－EAC算法

2.1 F－EAC算法中的问题

F－EAC算法优先考虑分裂稳定度最低的簇，通过随机选取分裂算子将待分裂簇分裂，每次分裂都可能引发簇的变异率改变，使得整个聚类过程中任意2次分裂方向彼此相反.FEAC算法可能出现频繁更换变异对象而导致分裂效果弱化，无法得到较好的聚类结果（如图1所示）.类别C1和C4被划分为同一个簇C7，簇C2、簇C3虽属于同一类别却被划分为2个簇.由C1和C4组成的簇进行分裂，分裂后生成包含C3和C4的新簇C8.因为C3和C4之间相异度较大，C8的变异率将迅速升高，根据公式（4）可知，F－EAC算法将待变异簇更换成簇C8，但此时C7中仍有部分C4成员需要继续分裂.F－EAC算法将每次分裂孤立起来，不能以更宽阔的视角处理整个分裂过程，在对于一个连贯的分裂中的过渡阶段处理上存在缺陷.

图1 类边界相对模糊图

2.2 改进F－EAC算法相关定义

定义1 d（a，b）表示a，b的欧式距离，计算公式为

其中ai表示点a在第i个属性上的值.

定义2 设簇Ci为待分裂的簇，其分裂点记为m1和m2，分裂的方向点记为sf（Ci），即

其中：NC代表Ci的近邻簇集合；｜NC｜代表近邻簇的个数；Oj表示近邻簇Cj的质心.对于∀xk∈Ci，∃m1和m2∈Ci，使得d（m1，sf（Ci））≤d（xk，sf（Ci）），且d（m1，m2）≥d（xk，m1）.

定义3 设第L轮Ci为待分裂簇，Ci分裂前质心为Oi（i＝1，2，…，k），记为Σf；Ci分裂后质心为O′i（i＝1，2，…，k），记为Σa；则评价函数EFL表示为

其中｜Σf｜表示集合Σf中成员的个数.若EFL＞1，第L＋1轮重新计算待分裂簇；否则，第L＋1轮待分裂簇仍为Ci.

2.3 改进F－EAC算法伪代码

输入：全局点集Σ，K 个初始中心Oi（i＝1，2，…，k）

输出：K 个簇Ci（i＝1，2，…，k）

%loopMax为最大迭代次数，currentLoop为当前迭代次数

① 输入loopMax，Oi（i＝1，2，…，k），全局点集Σ，currentLoop＝1；

② 对Σ中的每个对象进行 K－means聚类，生成K 个簇Ci（i＝1，2，…，k），质心分别为Oi（i＝1，2，…，k）；

③ 根据公式（4）计算SP（Ci）i（i＝1，2，…，k），取最大值的簇记为Dmax；

④ 依据定义2得到Dmax中的m1和m2及sf（Dmax）以m1和m2为基准将Dmax分裂，计算m2所在部分的质心Osplit，保存Osplit；

⑤ 以Oi（i＝1，2，…，k）为质心进行 K－means聚类，生成K′个簇Di（i＝1，2，…，k），质心分别为Oi′（i＝1，2，…，k）；

⑥ 若currentLoop＜loopMax，currentLoop＝currentLoop＋1，转第⑦步；否则，输出以O′i（i＝1，2，…，k）为质心的k个簇Ci（i＝1，2，…，k）；

%对分裂结果进行检测

⑦ 据公式（7）计算EFL，若EFL＞1，转第③步；否则，令Dmax＝Cspliti，转第④步.

2.4 改进F－EAC算法分析

（1）类与类之间边界明显时，改进F－EAC算法将待分裂簇分裂后，由于类与类之间的区别较为明显，待分裂簇分裂后其变异率迅速下降，在较短的时间内失去继续分裂的意义（见图2）.在图2中，待分裂簇C1分裂后，簇C2将吸收一部分成员，簇C1的变异率迅速减小，说明簇C1在当前状态下已稳定，失去分裂的意义；同理，簇C2分裂后变异率也迅速降低，保持稳定.

（2）类与类之间边界不明显时，聚类对象从需要分裂的状态达到类间相异度较大、类内相异度较小的状态所需的定向持续分裂次数较多.在质心调整过程中必然生成同时包含多个类别的簇，由于F－EAC算法强调对当前类间相异度小、类内相异度大的簇进行分裂，包含多个类别的簇就会成为下一个分裂对象，分裂就可能沿着反方向进行，分裂效果被削弱.如图1中，类别C1和C4被划分为同一个簇C7，簇C2、簇C3虽属于同一类别却被划分为2个簇.由C1和C4组成的簇进行分裂，分裂后生成包含C3和C4的新簇C8.因为C3和C4之间相异度较大，C8的变异率将迅速升高，但由于簇C7成员间相异度较大，根据公式（4）簇C7的变异率仍高于其余3个簇，按照改进F－EAC算法伪代码中的第⑦步，簇C7继续分裂，这保证了正确的分裂的连续性.

图2 类边界相对明显图

3 实验及分析

3.1 实验描述

实验机器配置：操作系统为Windows7；处理器为inter core i3－3110M，主频2.4GHz；内存为4GB；开发平台为matlab 2012a，myEclipse 8.5.实验数据选自UCI公共测试数据集中的Iris数据集和Wine数据集，实验中loopMax取值19，且对F－EAC和改进算法用相同的12组初始质心做测试.整个实验过程包括2组实验，在实验（1）中在Iris数据集上的测试，在实验（2）中采用Wine数据集作为测试对象.2组实验结果表明，改进后的算法在聚类结果的稳定性及准确度上相对于F－EAC都有较大的提高（见表1和2）.

表1 Iris数据集上的实验结果

表2 Wine数据集上的实验结果

3.2 实验分析

如表1所示，在实验1中第1，2，4，6，8，10和12组初始质心分布较为合理，F－EAC算法在这7组初始质心上划分的较为准确；第3，5，7，9和11组初始质心出现图1中的问题，F－EAC算法会因为频繁更换待分裂簇，导致分裂出现倒退现象，降低了聚类的准确度.本次实验中F－EAC算法聚类结果的准确度在47%～92%之间波动；改进F－EAC在处理第3，5，7，9，11组初始质心时通过连续的分裂将存在于同一个类别内的2个质心间的距离加大，始终保证分裂对增大质心间距离的有效性，最终得到3个分布较为合理的簇，将聚类准确度提高到90%以上；当处理初始质心分布较为合理的第1，2，4，6，8，10，12组数据时仍将聚类准确度保持在90%以上，总体聚类准确度达到91.50%.

如表2所示，在实验2中，F－EAC算法只在第8，10，11这三组初始质心上得到了较好的结果，其余9组数据都因为初始质心中2个质心存在于同一类别内而导致待变异簇的频繁更换，分裂无法产生质变的效果；在处理全部的12组数据时改进F－EAC通过评价质心间距离是否被增大来判断分裂是否合理，通过持续正确的分裂将最终聚类结果准确度保持在74.72%以上，平均准确度为74.86%，优于F－EAC的60.206%，说明改进F－EAC取得了相对不错的聚类准确度.两组实验都说明改进后的算法相对于传统算法在聚类结果的稳定性及准确度上都有较明显的提高.

4 结论

F－EAC算法通过分裂引发变异而提高聚类质量，但选取分裂基准时存在随机性，文献［12］虽然在选择分裂基准上对F－EAC算法进行了改进，但这种改进加强了分裂的指向性，在面对图1中的问题时其性能将略逊于F－EAC算法.本文在首先利用K－means算法快速地使分裂的结果形成局部最优，通过对分裂前后评价函数评价此次分裂是否有利于产生更好的结果，只有当产生的分裂阻碍聚类质量提高的情况下才重新计算每个簇的变异率，能够有效地控制待变异簇频繁的更新.实验结果表明，改进FEAC在保证算法产生的变异合理情况下能够连续地沿着正确的变异方向进行分裂，在处理类与类之间重叠或需要多次定向分裂对象时具有较好的效果.

［1］LAI YU－XIA，LIU JIAN－PING.Optimization study on initial center of K－means algorithm［J］.Computer Engineering and Applications，2008，44（10）：147－149.

［2］仝雪姣，孟凡荣，王志晓.对 K－means初始聚类中心的优化［J］.计算机工程与设计，2011，32（8）：2721－2723.

［3］JAIN A K.Data clustering 50years beyond K－means［J］.Pattern Recognition Letters，2010，31（8）：651－666.

［4］张健沛，杨悦，杨静，等.基于最优划分的 K－means初始聚类中心选取算法［J］.系统仿真学报，2009，21（9）：2586－2590.

［5］牛琨，张舒博，陈俊.融合网格密度的聚类中心初始化方案［J］.北京邮电大学学报，2007，30（2）：6－10.

［6］周爱武，于亚飞.K－means聚类算法的研究［J］.计算机技术与发展，2011，21（2）：62－65.

［7］韩凌波，王强，蒋正锋，等.一种改进的 K－means初始聚类中心选取算法［J］.计算机工程与应用，2010，46（17）：150－152.

［8］陶新民，徐晶，杨立标，等.一种改进的粒子群和K 均值混合聚类算法［J］.电子信息学报，2011，32（1）：92－97.

［9］ZHANG XUE－FENG，ZHANG GUI－ZHEN，LIU PENG.Improved K－means algorithm based on clustering criterion function［J］.Computer Engineering and Applications，2011，47（11）：123－127.

［10］ALVES V，CAMPELLO R J G B，HRUSCHKA E R.Towards a fast evolutionary algorithm for clustering ［C］／／IEEE Congress on Evolutionary Computation.Washington，DC：IEEE Computer Society，2006：1776－1783.

［11］NALDI M C，CAMPELLO R J G B HRUSCHKA E R，et al.Efficiency issues of evolutionary K－means［J］.Applied Soft Computing，2011，11（2）：1938－1952.

［12］王留正，何振峰.基于全局性分裂算子的进 K－mean算法［J］.计算机应用，2012，32（11）：3005－3008.