作者简介：
Treant人工智能爱好者社区专栏作者
专栏： https://www.cnblogs.com/en-heng
1、引言
k均值和kNN都以k开头，两种算法——kNN作为监控学习中的分类算法，k均值是非监控学习中的聚类算法； 两者的共同点是利用近邻的信息标记类别。
聚类是数据挖掘中非常重要的学习类型之一，是指将未标记的样本数据中相似的内容归为同一类别。 正所谓“物以类聚，人以群分”。 k均值是聚类算法中最简单、最高效、最核心的思想。 用户指定k个初始重心(initial centroids )作为簇的类别(cluster )，反复进行直到算法收敛。
2、基本算法
在k-means算法中，cluster用质心表示，并且很容易证明k-means算法的收敛等同于所有质心都不再变化。 基本的k均值算法流程如下。
选择k个初始重心作为初始群集；
repeat :
对于每个采样点，计算最接近的质心并将类别标记为与质心相对应的群集
重新计算与k个集群相对应的重心；
until重心不再更改
对于欧式空间样本数据，均方误差和(sum of the squared error，SSE )可以作为聚类目标函数，同时也可以作为衡量不同聚类结果好坏的指标。
表示采样点
到集群
的重心
距离平方和； 最佳聚类结果应是SSE达到最小值。
下图显示了通过四次迭代对三个集群进行群集的示例。
k-means有一个缺点： k-means局部最优，易受初始质心的影响，例如在下图中，由于初始质心选择不当，二次优聚类结果(SSE大) )。
另外，k值的选择直接影响聚类结果，最优聚类的k值必须与样本数据自身的结构信息一致，难以掌握这种结构信息，选择最优的k值非常困难。
3、优化
为了解决这些缺点，基于基本k均值发展了二分，其主要思想是，一个大的cluster分裂后得到两个小的cluster； 为了获得k个集群，可以进行中小学分裂。 算法流程如下。
最初只有一个cluster包含所有采样点；
报告：
从分裂的clusters中选择一个进行二元分裂，选择的cluster使SSE最小；
until有k个集群
在上述算法的流程中，为了从分裂的集群中求出局部最优解，可以采取对每个分裂的集群依次进行二元分裂(bisect )来求出最优分裂的暴力方法。 二分k均值算法的聚类过程如图所示：
从该图中可以看出，二分k均值算法对初始质心的选择不是很敏感，因为初始质心只选择了一个。
4、参考资料
[1] hhdzdj-高兴的月饼谭氏，Michael Steinbach，Vipin Kumar，Introduction to Data Mining。
[2] Xindong Wu，Vipin Kumar，thetoptenalgorithmsindatamining。