K均值聚类算法优缺点

1、J.B.MacQueen在1967年提出的K-means算法22到目前为止用于科学和工业 应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方法，常常采用误差平方和准则函数作为 聚类准则函数，误差平方和准则函数定义为：(3-1)其中，是类中数据对象的均值，即，(j=1,2, ,n),是K个聚类中心， 分别代表K个类。K-means算法的工作原理：算法首先随机从数据集中选取 K个点作为初始聚类中心，然后计算各个样 本到聚类中的距离，把样本归到离它最近的那个聚类中心所在的类。计算新形成的每一个聚类的数据对象的平均值来得到新的聚类中心，如果 相邻两次的聚类中心没有任何变化，说明样本

2、调整结束，聚类准则函数已经收 敛。本算法的一个特点是在每次迭代中都要考察每个样本的分类是否正确。若不正确，就要调整，在全部样本调整完后，再修改聚类中心，进入下一 次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中 心也不会有任何变化，这标志着已经收敛，因此算法结束。算法描述如下：算法：K-meanSo划分的K-means算法基于类中对象的平均值。输入：类的数目K和包含N个对象的数据库。方法： 对于数据对象集，任意选取 K个对象作为初始的类中心； 根据类中 对象的平均值，将每个对象重新赋给最相似的类； 更新类的平均值，即计算每个类中对象的平均值；Repeat； 直到不再发生

3、变化。其中，初始聚类中心的选择对聚类结果的影响是很大的，如图3.1,图a是三个类的实际分布，图b是选取了好的初始聚类中心（+字标记 的数据对象）得到的结果。图c是选取不好的初始聚类中心得到的结果，从中可以看到，选择初始聚 类中心是很关键的。abc图3.1基于K-means算法的一组对象的聚类算法的数据描述为：把n个向量（j=1,2,rn）分成c个类（i=1,2,c）,并求每类的聚类中心，使 得非相似性（或距离）指标的目标函数达到最小。当选择第i类中向量与相应聚类中心间的度量为欧几里德距离时，目标函数 可以定义为：（3-2）其中是类的目标函数。J值依赖于的几何形状和的位置。可以看出J是样本和聚类

4、中心的函数，样本集 X给定的情况下J的值取决于 K个聚类中心。J描述n个样本聚类成K个类时所产生的总的误差平方和。显然，若J值越大，说明误差越大，聚类结果越不好。因此，应该寻求使J最小的聚类结果，即在误差平方和准则下的最优结这种聚类通常也称为最小方差划分。3.1.3K均值聚类存在的问题K-means算法的特点一一采用两阶段反复循环过 程算法，结束的条件是不再有数据元素被重新分配： 指定聚类，即指定数据到某一个聚类，使得它与这个聚类中心的距离 比它到其它聚类中心的距离要近。修改聚类中心。优点：本算法确定的K个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集

5、，这个算法是相对可伸缩和高效的，计算的复杂度为 O(NKt),其中N是数据对象的数目，t是迭代的次数。一般来说，K<<N t<<N。缺点主要有三个： 在K-means算法中K是事先给定的，这个K值的选定是非常难以估计 的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是K-means算法的一个不足。有的算法是通过类的自动合并和分裂，得到较为合理的类型数目K,例如ISODAT# 法。关于K-means算法中聚类数目K值的确定在文献23中，是根据方差分析理 论，应用混合F统计量来确定最佳分类数，并应用了模糊划分嫡来验证最佳分 类数的正确性。在文献24中，

6、使用了一种结合全协方差矩阵的 RPCLS法，并逐步删除那 些只包含少量训练数据的类。而文献25中使用的是一种称为次胜者受罚的竞争学习规则，来自动决定类 的适当数目。它的思想是:对每个输入而言，不仅竞争获胜单元的权值被修正以适应输入值，而且对 次胜单元采用惩罚的方法使之远离输入值。 在K-means算法中，首先需要根据初始聚类中心来确定一个初始划 分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响 26-29, 一旦初始值选 择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要 问题。对于该问题的解决，许多算法采用遗传算法（GA）,例如文献中采用遗传 算法（GA）进行初始化，以内部聚类准则作为评价30指标。从K-means算法框架可以看出，该算法需要不断地进行样本分类调 整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间 开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献31,32中从该算法的时间复杂度进行分析考虑，通过一定的相似性 准则来去掉聚类中