什么是二分K均值算法？

二分K均值算法是对基本K均值算法的简单改进，其核心思想是：为了得到K个聚类，将一些点的集合分成两个聚类，选择其中一个聚类进行分割，以此类推，直到产生K个聚类。

K均值算法接收输入参数k，并将n个对象的集合分成k个聚类，使得聚类内的相似性高，而聚类间的相似性低。聚类相似性是根据聚类中对象的平均值来评估的，该平均值可以看作是聚类的中心或重心。

均值的初始值是任意指定的。这些值可以随机指定，或者可以使用前k个输入项的值。收敛标准可以基于平方误差，但并非必须如此。例如，算法可以被分配到多个集群。其他终止方法是设定固定的迭代次数。可以设置最大迭代次数，即使没有收敛也能保证程序结束。

二分K均值算法步骤如下：

• 初始化聚类列表，包含一个包含所有点的聚类。

• 重复

• 从聚类列表中移除一个聚类。

• {对选定的聚类执行多次“试验”二分。

• 对于i：1到试验次数执行

• 使用基本K均值算法对选择的聚类进行二分。

• 结束循环

• 选择总SSE最小的二分聚类。

• 将这两个聚类插入到聚类列表中。

• 直到聚类列表包含K个聚类。

选择哪个聚类进行分割的方法有很多种。它可以在每一步选择最大的聚类，选择SSE最大的聚类，或者使用基于大小和SSE的元素。不同的选择会导致不同的聚类结果。

可以使用它们的中心点作为基本K均值算法的初始中心点来改进最终的聚类结果。这一点很重要，因为虽然K均值算法保证能找到关于SSE的局部最小值的聚类，但在二分K均值算法中，它是“局部”地使用K均值算法，即对单个聚类进行二分。因此，最终的聚类集并不一定代表关于总SSE的局部最小值。

最后，通过记录K均值算法对聚类进行二分时创建的一系列聚类，也可以使用二分K均值算法来创建层次聚类。

Ginni

更新于：2022年2月14日

5K+浏览量

启动你的职业生涯

完成课程获得认证

开始学习