K-means算法的改进.docVIP

K-means算法的改进 K-means 算法是一种基于划分的聚类算法，在对所给数据集进行聚类时，必须知道k值的大小，即聚类的数目。它的思想是：首先从所给定的包含 n 个数据对象的数据集中随机选取 k 个数据对象作为初始聚类中心点，然后计算其余的数据对象到各个聚类中心点的距离，根据距离最近原则，把数据对象分配给离它最近的聚类中心所代表的簇中；再重新计算各个簇的聚类中心，根据选定的聚类准则函数，采用迭代的方法，不断重复以上过程直到聚类准则函数收敛或者是相邻两次的聚类中心没有变化为止。每一次迭代，都增加了簇内紧凑性，降低了簇间相似性。当所有数据对象被正确划分后，下一次迭代聚类中心将不会再发生变化，这时聚类结果已达到最优，算法结束。 (1) 从给定样本数据集中随机选取 k 个数据点作为初始聚类中心； (2) 计算数据集中每个数据到这 k 个聚类中心的距离并将每个数据点分配给离它最近的中心点所代表的簇； (3) 计算每个簇中所有数据点的平均值作为每个簇的新的中心； (4) 判断聚类准则函数是否收敛或聚类中心点和上次是否完全相同，若收敛或中心点无变化，则算法结束，输出聚类结果，否则转到步骤(2)。 下面给出一个 K-means 算法的例子，以更好的说明该算法的聚类过程。 已知一个数据对象集合X =，各数据对象的值如表所示。现在要求将数据对象集 X 划分为两类，即 k=2。 首先随机选择两个点作为初始聚类中心，在这里我们选择和，分别作为和两个簇的初始聚类中心。然后计算到和的欧式距离，通过公式来计算，如下所示： 根据计算可知，距离比距离更近，所以应将划分到所表示的簇中，同理将划分到簇中，将中。 重新计算，中数据对象的均值作为他们新的聚类中心。 Z1（0.5,0.67） 和 Z2（2.17,1.33） 的距离，并将它们划分到最近的簇中。根据计算，将{, , }划分到簇 ??1，将 划分到簇 ??2中，这和第一次划分的结果一样，因此两个簇中的聚类中心没变化，算法结束。最终的聚类结果是数据集划分为两簇，分别为： ??1= {} ??2= {} K-means 算法是一种经典的聚类算法，它简单快捷并且有效，其时间复杂度为 O(nkt)，其中 n 表示数据集中所包含的对象数，k 表示聚类数，t 表示迭代次数，通常 kn，tn，所以在处理大型数据集或数据库时，K-means 算法是相对可伸缩的和高效的，并且该算法对凸型聚类有较好的结果，当结果中的簇是密集的，并且簇与簇之间的区别较大时，K-means 算法的聚类效果较好。但是该算法在也存在不少缺点，主要有以下几个： (1) 最终的聚类结果对初始聚类中心十分敏感，选取的初始中心点不同，得到的聚类结果就会不同，如果选取的初始聚类中心点太差，很有可能导致聚类结果非常差，聚类失败； (2) 无法确定 k 值，即不能确定聚类数，只能根据经验进行大概的估计。而根据经验所得的 k 值往往不是最佳聚类数目，从而影响聚类效果； (3) 算法容易陷入局部最优解，仅适合对数值型数据聚类，只适用于聚类结果为凸形(即类簇为凸形)的数据集； (4) 该算法容易受到噪声和孤立点的干扰，导致下一代聚类中心的偏离，最终影响聚类效果； (5) 算法需要循环不断的执行数据再分配操作，更新簇中心操作以将数据对象划分到更合适的簇中。因此当数据集复杂，数据量非常大时，将大大增加算法的时间开销，算法变得低效。 由以上的缺点我们可以知道传统 K-means 算法的初始聚类中心是随机选取的，聚类结果对初始聚类中心敏感，根据不同的初始聚类中心聚类得到的聚类结果不同。其中，初始聚类中心的选择对聚类结果的影响是很大的，如下图1是三个类的实际分布，图2是选取了较好的初始聚类中心（十字标记的数据对象）得到的结果，图3是选取不好的初始聚类中心得到的结果，从中可以看到，选择初始聚类中心是很关键的。 针对这一缺点，本文的改进算法首先对数据集中的每个数据点，计算其到原点的距离，然后按这个距离对所有的数据点排序，将排好序的本文平均划分为 k 组，选取每组中间的数据点作为 k 个初始聚类中心。这样就能够得到一个确定的较好的初始聚类中心。同时，对于将数据点分配到合适的簇中的操作，本文采用一种更有效的方式，使算法能够以更少的时间得到稳定的，质量更好的聚类结果。 二、改进算法流程描述 1、初始聚类中心的选取 本节采用的选取初始聚类中心的方法的基本思想是基于各数据点到原点的距离，均匀的选择 k 个数据点作为初始聚类中心。首先，检查数据集中的数据对象是否有负的属性值，如果没有，属性值不做改变，如果某个属性值存在负值，则进行属性值转变，方法是将数据集中每个数据点的该属性值减去数据集中该属性的最小值。在这里，对属性值转变是必需的，因为之后计算的距离是数据点到原点的欧式距离，如果不做转换，