K-Means++ | 愈宅屋

K-Means++ | 愈宅屋

根据维基上的说法，K-Means++这个算法步骤大概如下：

1. 在已有的所有点中随机选取一个点，将其加入初始点。
2. 对于所有的点，计算出他们的D值，D值就是每个点到距离他们最近的初始点的距离的平方。
3. 对所有点选取下一个点加入初始点的集合，每个点被选取的概率正比于他们的D值。
4. 如果初始点集合数目没有达到预定的数目，回到2，否则到5。
5. 执行K-Means算法

我们考虑二维点集的聚类问题，K-Means算法是随便选择初始点，那么就会有一定的概率在一个Cluster内部出现两个或者更多的初始点，还有一种可能就是初始点出现在两个Cluster的正中间这种，反正就是会导致算法不是很有效，一个最常见的失败的聚类经常就是在某些地方把两类聚为一类，然后在另外一些地方把一类分为两类。但是呢，K-Means++算法可以很有效的避免这种状况，比如我在某一Cluster中间已经出现了一个初始点了，那么这个Cluster的点到这个初始点的距离就很小，平方后D值就更小了，所以这里面的点被选为下一个Cluster的概率就会很小。大部分情况下，K-Means++初始化完成之后每个Cluster就会有一个初始化点，这种时候我们就知道里聚类完成也差不多了。所以呢，K-Means++算法也可以很好地降低K-Means算法的迭代次数，换言之，就是算法的时间消耗。

Code:
http://www.kylen314.com/archives/755
Read full article from K-Means++ | 愈宅屋