初始中心的k-均值++与随机

Question

我已经看到，在许多K-means实现中，如VLFeat K-means或OpenCV K-means，基本上有两种方法可以选择起始质心：

1. 随机
2. 遵循K-Means++算法

然而，我不知道在哪种情况下一个比另一个好，尤其是因为启动方法被认为很重要。你能帮我理解这一点吗？

Answer 1

理论上，k-means++要好得多。这是一种有偏差的随机采样，它更喜欢彼此相距较远的点，并避免接近点。随机初始化可能不吉利，选择附近的中心。

因此，理论上，k-means++应该需要更少的迭代，并且有更高的机会找到全局最优。

然而，k-means++并不是完全"免费"的，在我的实验中，我没有看到更先进的k-means算法在两者之间有任何系统性的差异。k-均值++需要O（k n）计算——大约是一次完整迭代的成本。但也有一些改进的k-均值算法，其迭代时间远小于此。使用这些算法，k-means++可能花费总运行时间的10-20%（使用教科书中的k-means，它通常小于1%）。

我想我现在更喜欢简单的随机初始化，尝试多次，每次尝试10次迭代来细化一个样本，然后只继续最好的。