算法步骤

算法很简单一共4步：

1）随机在图中取K个种子点。
2）然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点）
3）接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）
4）然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A，B，C，下面的种子点聚合了D，E）。

这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法”。

k-means算法的缺点：

1）K的值需要人工指定，这个K值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。只能不断试验不同的K。
2）K-Means算法需要用初始随机种子点来搞，这个随机种子点太重要，不同的随机种子点会有得到完全不同的结果。（K-Means++算法可以用来解决这个问题，其可以有效地选择初始点）。

K-means++算法

这个算法只是解决了第二个缺点， k-means++算法选择初始seeds的基本思想就是：初始的聚类中心之间的相互距离要尽可能的远。具体算法如下：
1）先从我们的数据库随机挑一个随机点当“种子点”。
2）对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
3）然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
4）重复第（2）和第（3）步直到所有的K个种子点都被选出来。
5）进行K-Means算法。

K-means和K-means++的实现（matlab）

k-means和k-means++：https://github.com/WZFish/K-means.git