K-means算法优化

目录：

（1）回顾K-means算法缺点

（2）二分K-means算法介绍

（3）用Python实现二分k-means算法

（1）k-means算法缺点

上一篇文章《聚类算法之K-means算法》中介绍了K-means算法所有知识点并指出K-means算法的缺点。今天我们来回顾一下K-means的这些缺点：

对噪声和孤立点数据比较敏感。表现为：K-means将簇中所有点的均值作为新质心，若簇中含有异常点，将导致均值偏离严重，容易陷入局部最小值。

必须事先给出K值。

在K-均值聚类中簇的数目k是一个用户预先定义的参数，那么用户如何才能知道k的选择是否正确呢？如何才能知道生成的簇比较好呢？在包含簇分配结果的矩阵中保存着每个样本的误差，即该样本到簇质心的距离平方值。这一点在《聚类算法之K-means算法》中有用Python实现。下面会讨论利用该误差来评价聚类质量的方法。

图1：K-means算法实现西瓜数据集4.0聚成3簇

考虑图1的聚类结果，这是在一个包含三个簇的数据集上运行k-means算法之后的结果，但是点的簇分结果值没有那么准确。K-means算法收敛但聚类效果较差的原因是，k-means算法收敛到了局部最小值，而非全局最小值（局部最小值指结果还可以但并非最好结果，全局最小值是可能的最好结果）。

一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和)，对应《聚类算法之K-means算法》的Python程序代码，如图2所示。SSE值越小表示数据点越接近于它们的质心，聚类效果也越好。因为对误差取了平方，因此更加重视那些远离中心的点。一种肯定可以降低SSE值的方法是增加簇的个数，但这违背了聚类的目标。聚类的目标是在保持簇数目不变的情况下提高簇的质量。

图2：Python实现SSE

（2）二分K-means算法介绍

那么如何对图1的结果进行改进呢？你可以对生成的簇进行后处理，一种方法是将具有最大SSE值的簇划分成两个簇。具体实现时可以将最大簇包含的点过滤出来并在这些点上运行K-means算法，其中的K设置为2。

图3：由于质心随机初始化导致K-means算法效果不好的一个例子，这需要额外的后处理操作来清理聚类结果

为了保持簇总数不变，可以将某两个簇进行合并。从图3中很明显就可以看出，应该将图下部两个出错的簇质心进行合并。可以很容易对二维数据上的聚类进行可视化，知道哪几个簇可以合并，但是如果遇到40维的数据应该如何去做？

有两种可以量化的办法：合并最近的质心，或者合并两个使得SSE增幅最小的质心。第一种思路通过计算所有质心之间的距离，然后合并距离最近的两个点来实现。第二种方法需要合并两个簇然后计算总SSE值。必须在所有可能的两个簇上重复上述处理过程，直到找到合并最佳的两个簇为止。接下来将讨论利用上述簇划分技术得到更好的聚类结果的方法。

为克服K-均值算法收敛于局部最小值的问题，有人提出了另一个称为二分K-均值（bisecting K-means）的算法。该算法首先将所有点作为一个簇，然后将该簇一分为二。之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。

二分K-means算法的伪代码形式如下：

（3）用Python实现二分k-means算法

代码运行后最终的效果，如图4所示。具体的代码和数据集在我的gitHub中，数据集是周志华《机器学习》西瓜数据集4.0，地址：https://github.com/Microstrong0305/machine_learning/tree/master/K-means

图4：二分K-means算法实现西瓜数据集4.0聚成3簇

下面我再把图1和图4放到一起来比较，如图5所示。很明显K-means算法和二分K-means算法最后聚类的结果差别很大，且二分K-means算法效果更好一些。

图5:左图是K-means算法聚类西瓜数据集4.0;右图是二分K-means算法聚类西瓜数据集4.0