algorithm - k-means++ vs 初始​​中心随机

Question

我在很多 K-means 实现中看到过，比如 VLFeat k-means或 OpenCV k-means ，基本上有两种选择起始质心的方法:

1. 随机
2. 在 K-Means++ 之后算法

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

Answer 1

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

因此从理论上讲，k-means++ 应该需要更少的迭代次数，并且更有可能找到全局最优值。

但是，k-means++ 并非完全“免费”，在我的实验中，我没有发现两者与更高级的 k-means 算法之间有任何系统差异。 k-means++ 需要 O(k n) 计算——大约一次完整迭代的成本。但是有改进的 k-means 算法，其迭代次数远少于此。使用这些算法，k-means++ 可能花费总运行时间的 10-20%(教科书 k-means 通常不到 1%)。

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