Kmeans

---

K-means与kNN虽然都是以k打头，但却是两类算法——kNN为监督学习中的分类算法，而k-means则是非监督学习中的聚类算法；二者相同之处：均利用近邻信息来标注类别，都需要提前得知有多少种类。

• 步骤：

先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算（利用簇重心调整聚类中心）。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：
1）没有（或最小数目）对象被重新分配给不同的聚类。
2）没有（或最小数目）聚类中心再发生变化。
3）误差平方和局部最小。

---

• 误差函数：

以平方误差和（sum of the squared error, SSE)作为聚类的目标函数，同时也可以衡量不同聚类结果好坏的指标：

image.png

缺点：

k-means是局部最优的，容易受到初始质心的影响；比如在下图中，因选择初始质心不恰当而造成次优的聚类结果（SSE较大）：

image.png

同时，k值的选取也会直接影响聚类结果，最优聚类的k值应与样本数据本身的结构信息相吻合，而这种结构信息是很难去掌握，因此选取最优k值是非常困难的。

---

解决方法：

为了解决上述存在缺点，在基本k-means的基础上发展而来二分 (bisecting) k-means，其主要思想：一个大cluster进行分裂后可以得到两个小的cluster；为了得到k个cluster，可进行k-1次分裂。算法流程如下：

初始只有一个cluster包含所有样本点；
repeat:
    从待分裂的clusters中选择一个进行二元分裂，所选的cluster应使得SSE最小；
until 有k个cluster

上述算法流程中，为从待分裂的clusters中求得局部最优解，可以采取暴力方法：依次对每个待分裂的cluster进行二元分裂（bisect）以求得最优分裂。二分k-means算法聚类过程如图：

image.png