解决方案的K均值聚类唯一性

Question

k均值聚类算法是否总是产生相同的解决方案？初始化应该是随机的，所以无论初始化如何，聚类都会收敛到相同的结果？

Answer 1

初始化应该是随机的，所以不管初始化如何，聚类收敛到相同的结果？

恰恰相反。如果问题是一个很好的凸优化问题，我们不会随机地初始化它，因为简单地从（0,0，...，0）开始就会给出正确的答案。

随机初始化的原因正是你可以通过尝试不同的随机种子获得不同的解决方案，然后选择最好的一个，当你所有的运行完成。对许多应用来说，十次运行是一个很好的经验法则。

查找k的全局最小值 - 一般意义上的问题是NP-hard。通用算法实际上是一种启发式算法。

Answer 2

实际上k-means算法的初始化对获得的结果有明显的影响。为了防止“坏”初始化，你可以求助于克服这个问题的k-means ++算法。你可以在wikipedia（http://en.wikipedia.org/wiki/K-means%2B%2B）中查看。