【Bisecting K-Means算法】{0} —— Bisecting K-Means算法的简单介绍

K-Means算法通常只能收敛于局部最小值，这可能导致“反直观”的错误结果。

因此，为了优化K-Means算法，提出了

Bisecting K-Means算法

，也就是二分K-Means算法。

Bisecting K-Means算法 是一种层次聚类方法。

层次聚类（Hierarchical Clustering）是聚类算法的一种，通过计算不同类别的相似度类创建一个有层次的嵌套的树。

Bisecting K-Means算法 和 K-Means算法 有什么不同？

Bisecting K-Means算法 并不是一开始就随机选择 K 个中心点，而是先把所有点归为一个簇，然后将该簇一分为二。计算各个所得簇的代价函数（SSE），选择SSE最大的簇再进行划分以尽可能地减小误差，重复上述基于SSE划分过程，直到得到用户指定的簇数目为止。

Bisecting K-Means算法 通常比 K-Means算法运算快一些。

聚类算法的代价函数SSE能够衡量聚类性能，该值越小表示数据点越接近于它们的质心，聚类效果就越好。所以需要对SSE最大的簇进行再一次划分，因为误差平方和越大，表示该簇聚类越不好，越有可能是多个簇被当成一个簇了，因此首先需要对SSE最大的簇进行划分。

Bisecting K-Means算法的伪代码如下:

将所有点看成一个簇
当簇数目小于k时:
	对于每一个簇:
		计算总误差
		在给定的簇上面进行K-均值聚类(k=2)
		计算将该簇一分为二之后的总误差
	选择使得误差最小的那个簇进行划分操作
           

参考资料：《机器学习实战》