K-means聚类算法是否总是产生相同的解？初始化应该是随机的，那么无论初始化如何，聚类是否会收敛到相同的结果？

回答：

初始化应该是随机的，那么无论初始化如何，聚类是否会收敛到相同的结果？

恰恰相反。如果k-means问题是一个很好的凸优化问题，我们就不会随机初始化它，因为从(0,0,…,0)开始就能得到正确的答案。

随机初始化的原因正是你可以通过尝试不同的随机种子得到不同的解，然后在所有k-means运行结束后选择最佳的一个。十次运行是许多应用的一个好经验法则。

寻找k-means问题的全局最小值在一般情况下是NP难的。常用的算法实际上是一种启发式方法。