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

Question

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

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

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

Answer 1

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

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

因此， k -means++的缺点是：

1. 它也可以找到一个次优的解决方案（它仍然是一个近似值）。
2. 它并不总是比 Lloyd 的算法快（参见 Arthur & Vassilvitskii 的表格）。
3. 它比劳埃德的算法更复杂。
4. 它相对较新，而劳合社 50 多年来已经证明它的价值。
5. 对于特定的度量空间，可能存在更好的算法。

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

Answer 2

不是您的问题，而是对大 N 的任何 kmeans 方法的简单加速：

1）首先对点的sqrt（N）的随机样本进行k-means
2）然后从这些中心运行完整的k-means。

对于 N 10000、k 20，我发现这比 kmeans++ 快 5-10 倍，结果相似。
它对您的效果如何取决于 sqrt(N) 样本与整体的近似程度，以及 N、dim、k、ninit、delta ...

您的 N（数据点数）、dim（特征数）和 k 是多少？
用户的 N、dim、k、数据噪声、指标的巨大范围......更不用说缺乏公共基准，使得比较方法变得困难。

补充：kmeans() 和 kmeanssample()的Python 代码 在 SO 上；欢迎评论。