k-means++ vs 初始中心随机
k-means++ vs random for initial centers
我看到在许多 K-means 实现中，例如 VLFeat k-means or OpenCV k-means，基本上有 2 种选择起始质心的方法：
- 随机
- 遵循 K-Means++ 算法
但是，我不知道在哪些情况下哪个更好，尤其是因为启动方法被认为很重要。你能帮我理解这一点吗？
理论上，k-means++ 更好。它是一种偏向随机抽样，更喜欢彼此距离较远的点，并避免接近的点。随机初始化可能运气不好，选择附近的中心。
所以从理论上讲，k-means++ 应该需要更少的迭代并且有更高的机会找到全局最优值。
然而，k-means++ 并不完全是 "free"，在我的实验中，我没有看到两者与更高级的 k-means 算法之间有任何系统差异。 k-means++ 需要 O(k n) 计算——大约一次完整迭代的成本。但是有改进的 k-means 算法，其迭代次数远少于此。使用这些算法，k-means++ 可能花费总运行时间的 10-20%（教科书 k-means 通常不到 1%）。
我想我现在更喜欢简单的随机初始化，尝试多次，每次尝试 10 次迭代以优化样本，然后只用最好的继续。
我看到在许多 K-means 实现中，例如 VLFeat k-means or OpenCV k-means，基本上有 2 种选择起始质心的方法：
- 随机
- 遵循 K-Means++ 算法
但是，我不知道在哪些情况下哪个更好，尤其是因为启动方法被认为很重要。你能帮我理解这一点吗？
理论上，k-means++ 更好。它是一种偏向随机抽样，更喜欢彼此距离较远的点，并避免接近的点。随机初始化可能运气不好，选择附近的中心。
所以从理论上讲，k-means++ 应该需要更少的迭代并且有更高的机会找到全局最优值。
然而，k-means++ 并不完全是 "free"，在我的实验中，我没有看到两者与更高级的 k-means 算法之间有任何系统差异。 k-means++ 需要 O(k n) 计算——大约一次完整迭代的成本。但是有改进的 k-means 算法，其迭代次数远少于此。使用这些算法，k-means++ 可能花费总运行时间的 10-20%（教科书 k-means 通常不到 1%）。
我想我现在更喜欢简单的随机初始化，尝试多次，每次尝试 10 次迭代以优化样本，然后只用最好的继续。