algorithm - 我们应该使用 k-means++ 而不是 k-means 吗？

Question

k-means++算法有助于原始k-means算法的以下两点:

1. 原始的 k-means 算法在输入大小的 super 多项式的最坏情况下运行时间，而 k-means++ 声称是 O(log k)。
2. 与最佳聚类相比，找到的近似值在目标函数方面可能会产生不太令人满意的结果。

但是 k-means++ 有什么缺点吗？我们是否应该从现在开始一直使用它而不是 k-means？

Answer 1

无人认领k-means++在 O(lg k) 时间内运行；它的解决方案质量是 O(lg k) - 与最优解决方案具有竞争力。 k-means++ 和称为 Lloyd 算法的常用方法都是 NP 难优化问题的近似值。

我不确定k-means++ 的最坏情况运行时间是多少；请注意，在 Arthur & Vassilvitskii's原始描述，算法的步骤2-4引用劳埃德算法。他们确实声称它在实践中工作得更好更快，因为它从更好的位置开始。

k-means++ 的缺点是:

1. 它也可以找到一个次优的解决方案(它仍然是一个近似值)。
2. 它并不总是比 Lloyd 的算法更快(参见 Arthur 和 Vassilvitskii 的表格)。
3. 它比 Lloyd 的算法更复杂。
4. 它相对较新，而 Lloyd's 已在 50 多年的时间里证明了它的值(value)。
5. 对于特定的度量空间可能存在更好的算法。

也就是说，如果您的 k-means 库支持 k-means++，那么一定要尝试一下。