K-means算法的改进

《K-means算法的改进》由会员分享，可在线阅读，更多相关《K-means算法的改进（6页珍藏版）》请在金锄头文库上搜索。

1、K-means 算法的改进J.B.MacQueen 在 1967 年提出的 K-means 算法到目前为止用于科学和工业 应用的诸多聚类算法中一种极有影响的技术。它是聚类方法中一个基本的划分方 法，常常采用误差平方和准则函数作为聚类准则函数。K-means 算法是一种基于划分的聚类算法，在对所给数据集进行聚类时， 必须知道 k 值的大小，即聚类的数目。它的思想是：首先从所给定的包含 n 个 数据对象的数据集中随机选取 k 个数据对象作为初始聚类中心点，然后计算其 余的数据对象到各个聚类中心点的距离，根据距离最近原则，把数据对象分配给 离它最近的聚类中心所代表的簇中；再重新计算各个簇的聚类中心，

2、根据选定的 聚类准则函数，采用迭代的方法，不断重复以上过程直到聚类准则函数收敛或者 是相邻两次的聚类中心没有变化为止。每一次迭代，都增加了簇内紧凑性，降低 了簇间相似性。当所有数据对象被正确划分后，下一次迭代聚类中心将不会再发 生变化，这时聚类结果已达到最优，算法结束。K-means 算法的具体过程描述如下：(1) 从给定样本数据集中随机选取 k 个数据点作为初始聚类中心；(2) 计算数据集中每个数据到这 k 个聚类中心的距离并将每个数据点分配 给离它最近的中心点所代表的簇；(3) 计算每个簇中所有数据点的平均值作为每个簇的新的中心；(4) 判断聚类准则函数是否收敛或聚类中心点和上次是否完全相

3、同，若收敛 或中心点无变化，则算法结束，输出聚类结果，否则转到步骤(2)。下面给出一个 K-means 算法的例子，以更好的说明该算法的聚类过程。首先随机选择两个点作为初始聚类中心，在这里我们选择，和“，分别作为 二和G两个簇的初始聚类中心。然后计算工:到，和“的欧式距离，通过公式来计 算，如下所示：Iki - x31| = V(i -1)2 + (o -1)2 = i晦-壮 II = 7(1 - 3)2 + (0 - 2)2 = 2.82根据计算可知，距离“比距离更近，所以应将匚划分到，所表示的簇二 中，同理将：、：x划分到簇G中，将-划分到簇。中。重新计算G，G中数据对象的均值作为他们新的

4、聚类中心。孔=(0 + 0 + 1 + 岁。+1 + 1 + 2) =( 5,0.67) 抵=(3 + 3 + 4+匕(1+2 + 2+3) = a 心 3)计算数据集中所有点到新的聚类中心 Z1(0.5,0.67) 和 Z2(2.17,1.33) 的 距离，并将它们划分到最近的簇中。根据计算，将工:，工：5工汀划分到簇, 将I - ；划分到簇2中，这和第一次划分的结果一样，因此两个簇中的 聚类中心没变化，算法结束。最终的聚类结果是数据集划分为两簇，分别为：1= ，:二 1 E 2= * r * 三 Z 一、K-means算法的优缺点分析K-means 算法是一种经典的聚类算法，它简单快捷并且

5、有效，其时间复杂度为O(nkt)，其中n表示数据集中所包含的对象数，k表示聚类数，t表示迭 代次数，通常kvvn, tvvn,所以在处理大型数据集或数据库时，K-means算法 是相对可伸缩的和高效的，并且该算法对凸型聚类有较好的结果，当结果中的簇 是密集的，并且簇与簇之间的区别较大时， K-means 算法的聚类效果较好。但 是该算法在也存在不少缺点，主要有以下几个：(1) 最终的聚类结果对初始聚类中心十分敏感，选取的初始中心点不同，得 到的聚类结果就会不同，如果选取的初始聚类中心点太差，很有可能导致聚类结 果非常差，聚类失败；(2) 无法确定 k 值，即不能确定聚类数，只能根据经验进行大概

6、的估计。 而根据经验所得的 k 值往往不是最佳聚类数目，从而影响聚类效果；(3) 算法容易陷入局部最优解，仅适合对数值型数据聚类，只适用于聚类结 果为凸形(即类簇为凸形)的数据集；(4) 该算法容易受到噪声和孤立点的干扰，导致下一代聚类中心的偏离，最 终影响聚类效果；(5) 算法需要循环不断的执行数据再分配操作，更新簇中心操作以将数据对 象划分到更合适的簇中。因此当数据集复杂，数据量非常大时，将大大增加算法 的时间开销，算法变得低效。由以上的缺点我们可以知道传统 K-means 算法的初始聚类中心是随机选 取的，聚类结果对初始聚类中心敏感，根据不同的初始聚类中心聚类得到的聚类 结果不同。其中，

7、初始聚类中心的选择对聚类结果的影响是很大的，如下图 1 是三个类的实际分布，图 2 是选取了较好的初始聚类中心(十字标记的数据对象) 得到的结果，图 3 是选取不好的初始聚类中心得到的结果，从中可以看到，选择 初始聚类中心是很关键的。针对这一缺点，本文的改进算法首先对数据集中的每个数据点，计算其到原 点的距离，然后按这个距离对所有的数据点排序，将排好序的本文平均划分为 k 组，选取每组中间的数据点作为 k 个初始聚类中心。这样就能够得到一个确定 的较好的初始聚类中心。同时，对于将数据点分配到合适的簇中的操作，本文采 用一种更有效的方式，使算法能够以更少的时间得到稳定的，质量更好的聚类结 果。二

8、、改进算法流程描述1、初始聚类中心的选取本节采用的选取初始聚类中心的方法的基本思想是基于各数据点到原点的 距离，均匀的选择 k 个数据点作为初始聚类中心。首先，检查数据集中的数据 对象是否有负的属性值，如果没有，属性值不做改变，如果某个属性值存在负值， 则进行属性值转变，方法是将数据集中每个数据点的该属性值减去数据集中该属 性的最小值。在这里，对属性值转变是必需的，因为之后计算的距离是数据点到 原点的欧式距离，如果不做转换，不同的数据点（例如关于原点中心对称的数据 点），它们到原点的欧式距离可能会相同。这将导致对初始聚类中心的选择出现 错误。为了解决这个问题，必须将所有数据点转化到正空间，这样

9、每个数据点将 会得到一个唯一的距离。接下来，计算每个数据点到原点的欧式距离，然后对所 有的数据点按照它们到原点的距离进行排序。最后将排好序的数据点平均分成 k 组，选择每组的中间那个数据点作为 k 个初始聚类中心点。基于这些初始聚类 中心进行聚类，得到的聚类结果将会更理想。下面举例说明如何选取初始聚类中 心。有数据集X为：=.：,：、，各数据点的值如表所示，聚类数 k=2。包含负属性值的数据集X数据%4属性 值1 二 1Q-0.8)(1 0;-05?-1-5)(0/7?0 9?0.8)(1.3,-1.0,0-5)(0.6,1.0?-0.3)(0.9,1.2,0.2)由上表可知，数据集 X 包含

10、6个数据点，每个点有3个属性值，其中第 2 和第3个属性值有负值，因此必须进行属性值转变。第2个属性值的最小值为-1.0， 第3 个属性值的最小值为-1.5，因此给每个数据点的第2 个属性值减去 -1.0，第 3 个属性减去-1.5。转变后的数据集 X 中各数据点的值如下表所示：属性值转变后的数据集X数据点咒12x4巧属性 值0-2,10,0.7)(100.5,0)(0.7,1.9,13)130,2.0)(0.6,2 0,1.2)(0.9,2.2,13)接着计算各点到原点的距离，假设2表示工:到原点的距离，利用欧式距离公 式计算如下。d丄=7(1-2 - o)2 -F (2.0 - O)2 -

11、F (0.7 - 0)2 = 2.43用同样的方法，可计算出其他各数据点到原点的距离：数据山2X4咒5与原点的距离2.431.123 062.392.412.71由上表可知，数据集中数据点按与原点的距离排序是I：、： 、u 工三将其平均分为两组即是是和：.w：。取各组的中间数据点作为初始聚 类的中心，这里即是匚和“。2.数据对象的分配选取好初始聚类中心后，接下来就是将数据集中的数据点分配到合适的簇 中。这是一个迭代的过程，在本文改进算法中采用了一种试探性的方法以减少计 算时间。在算法中，每个数据点包含两个属性Cluster和MinDis，分别代表该数 据点所属的簇和当前离最近聚类中心点的距离。

12、首先计算每个数据点到各聚类中 心的距离，之后将数据点划分到具有离它最近的聚类中心点的簇中，并将该数据 点到该簇的中心点的距离赋给M，C的值则设置为该簇的编号。下一步，对于每个簇，计算其中所有的数据点的平均值作为该簇的新的中心。 然后对每个数据点，计算它到所在簇的新的中心点的距离。如果该距离小于等于 它当前M的值，则该数据点继续留在该簇中，否则计算该数据点到k个新中心 点的距离。距离计算出来之后，将该数据点划分到相应的簇中，并将C, M的值 分别更新为该簇的编号和数据点离该簇的中心点的距离。这个再分配的过程重复 执行直到聚类准则函数收敛或相邻两次的聚类中心无变化。这种方法避免了在每 一次迭代过程

13、中对每一个点都要进行重新的计算与分配，大大减少了计算量，减 少算法的时间开销，提高算法的效率。步骤：(1) 对于给定的数据集，检查所有的属性值是否都是正值，如果是，则转到 步骤(4)，否则转到步骤(2)；(2) 对于每个包含负值的属性，找出该属性的最小值；(3) 为数据集中的每个数据点，在每个包含负值的属性值上减去该属性的最 小值；(4) 计算每个数据点到原点的距离；(5) 将所有数据点按步骤(4)所得的距离排序；(6) 将排好序的数据点平均分为k组；(7) 在每一组中，选取中间的数据点作为初始聚类中心；(8) 计算每个数据点 到k个中心点的距离(，)，其中1W ；(9) 对于每个数据点，找到离它最近的中心点，并将分配给簇j；(10) 将该数据点的Cluster值设置为j；(11) 将该数据点的 MinDis 值设置为 ( ， )；(12) 重新计算每个簇的中心点；(13) 对于每个数据点 计算它和现在所在簇的中心点的距离；(14) 如果这个距离小于等于目前最短距离，数据点留在该簇中不变；(15) 否则对于每个中心点，(1W W )，计算到数据点的距离(，); 并转向步骤(9)。