K—means算法及其改进算法

廖礼

摘 要 聚类分析在科研和商业中都有着非常重要的应用。其算法可以被划分为五类：划分方法、层次方法、基于密度方法、基于网格方法和基于模型方法。K-means算法是聚类分析中一种常用的划分方法。但是随着数据量的增加，K-means算法的局限性日益突出。于是针对K-means算法的各种改进算法应运而生。本文主要介绍了两种典型的改进K-means算法。

关键词 聚类分析 K-means算法 改进的K-means算法

中图分类号：TP484.9 文献标识码：A

0引言

聚类分析是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。它是一种重要的数据挖掘技术，是分析数据并从中发现有用信息的一种有效手段，被广泛应用在商业、生物、地理、保险业、因特网等方面。作为统计学的一个分支和一种无监督的学习方法， 聚类从数学分析的角度提供了一种准确、细致的分析工具。

1 K-means算法

K-means算法首先随机地在N个对象中选取k个数，作为初始聚类中心（即把N个对象分为k个簇），采用距离作为相似性的评价指标，认为两个对象的距离越近，其相似度就越大。相似度通过一个簇中对象的平均值来计算。然后按最小距离原则将N个对象划分到不同的簇中。最后不断迭代计算聚类中心和调整各对象的类别，最终使每个对象到其判属的聚类中心的距离的平方和最小。步骤如下：

（1）在N个对象中随机地选取k个数作为初始聚类中心，即c1…ck；

（2）将N个对象按最小距离原则找到离它最近的聚类中心ci，并将其划分到ci所标明的簇中；

（3）计算每个簇中对象的均值，并且该均值作为该簇新的聚类中心；

（4）重复（2）—（3）步，直到没有对象或很少的对象被分配到不同的簇中。

2改进的K-means算法

2.1 K-means++算法

K-means++算法相较于K-means算法的不同之处是在对初始聚类中心的选取上，不同于K-means的随机选取，K-means++只有第一个初始聚类中心是随机选取的，其余k-1个则是根据一定的概率来有目地选择初始聚类中心。比传统的K-means算法在速度和精确性上都有了显著地提高。步骤如下：

（1）在N个对象中随机地选取1个数作为初始聚类中心，即c1；

（2）以概率P继续在N个对象中随机地选取新的数作为下一个初始聚类中心，即ci；

其中，P为选取新的聚类中心的概率：p=D（x）2/D（x）2式中，D（x） 表示一个对象到已经选择好的初始聚类中心的最小距离；

（3）重复步骤（2）直到选择到k个初始聚类中心；

（4）同K-means算法步骤（2）—（4）；

2.2基于均衡化评价函数的K-means改进算法

由上式，可以看出不需要事先给定k值而自动生成聚类的数目，为实际应用提供了很大的便利。根据大量的实验结果表明，k的值不会超过。算法从l到取整，循环执行K-means算法，以均衡化的评价函数作为准则函数，搜索评价函数值最小的并记下相应的k值，即最优聚类的结果。改进的算法自动生成聚类数目，其中在将样本对象聚类到最近的簇时，属于最近邻搜索问题，采用扩展的部分失真搜索算法。利用最近邻搜索算法减少算法的层次数，大大降低算法的时间复杂度。步骤如下：

（1）输入N个对象作为样本空间；

（2）For i=1 to do；

（3）任意选择个对象作为初始聚类中心；

（4）计算簇中的均值，使用EPDS算法将每个样本赋给最近的簇；

（5）更新簇的均值；

（6）计算J（c，k）直到其收敛为之，否则返回到（4）；

（7）搜索均衡化函数J（c，k）的最小值，记录下相应的k值；

（8）结束。

3总结

K-means算法作为聚类分析经典的方法之一，对大型数据集的处理效率较高，尤其是对样本分布呈现类团聚状时，可以达到很好的聚类效果。但是作为一个NP问题，它对初始聚类中心的选择以及k值大小的确定有很大的依赖性，在一定程度上限制了K-means算法的实际应用。本文主要总结了两种改进后的K-means算法，通过与传统的K-means比较，改进后的算法更加稳定，速度更快，时间花费小，应用更广。当然改进后的算法也不是完美无暇的，依然存在着一些不足之处，因此希望此文能对今后改进K-means算法提供一些理论指导。

参 考 文 献

[1] Mahamed G.H. Omran， Andries P. Engelbrecht and Ayed Salman .An overview of clustering methods[J].Intelligent Data Analysis， 2007（11）：583-605.

[2] 张建辉.k-means聚类算法研究及应用[D].武汉：武汉理工大学，2007.

[3] 张玉芳，毛嘉莉，熊忠阳.一种改进的K2means算法[J].计算机应用， 2003，23（08）.

[4] 施培蓓，钱雪忠，汪中.基于均衡化函数的快速K-means算法[J].計算机工程与应用，2008，44 （03）：189-191.endprint