Kmeans++

序

为了解决传统kmeans需要随即初始化聚类中心带来的缺陷，引入kmeans++来做优化

基本思想

1）从输入的数据点集合中随机选择一个点作为第一个聚类中心
2）对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
3）选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
4）重复2和3直到k个聚类中心被选出来
5）利用这k个初始的聚类中心来运行标准的k-means算法

从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下：
1）先从我们的数据库随机挑个随机点当“种子点”
2）对于每个点，我们都计算其和最近的一个“种子点”的距离并保存在一个数组里，然后把这些距离加起来得到。
3）然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是:

4）重复2和3直到k个聚类中心被选出来
5）利用这k个初始的聚类中心来运行标准的k-means算法

可以看到算法的第三步选取新中心的方法，这样就能保证距离D(x)较大的点，会被选出来作为聚类中心了。至于为什么原因比较简单，如下图 所示：

假设A、B、C、D的D(x)如上图所示，当算法取值 时，该值会以较大的概率落入D(x)较大的区间内，所以对应的点会以较大的概率被选中作为新的聚类中心。

转载注明：https://www.jianshu.com/p/680dbffad345