我们应该使用k-means++替代k-means吗？

Question

k-means++算法在以下两个方面能够帮助原始的k-means算法：

1. 原始的k-means算法在输入数据规模上存在超多项式的最坏运行时间，而k-means++声称其为O(log k)。
2. 相对于最优聚类，找到的近似结果可能会导致目标函数表现不太理想。

但是，k-means++有什么缺点呢？我们应该总是使用它来替代k-means吗？

- Karl

Answer 1

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

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

因此，k-means++的缺点如下：

1. 它也可能找到次优解（仍然是近似解）。
2. 它并不总是比Lloyd算法更快（请参见Arthur & Vassilvitskii的表格）。
3. 它比Lloyd算法更复杂。
4. 它相对较新，而Lloyd算法已经证明其价值超过50年。
5. 针对特定的度量空间，可能存在更好的算法。

话虽如此，如果您的k-means库支持k-means++，那么请尽管试用它。

- Fred Foo

---

只是一个小问题。它与最优解的竞争性是log K，而不是Lloyd's。事实上，Lloyd's相对于最优解可能会非常糟糕，并且没有合理的近似保证。 - Suresh

@Suresh：这不是我那边的小毛病，而是我的思维错误。已经更正了。 - Fred Foo

Answer 2

虽然不是你的问题，但是对于大型数据集，任何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、数据噪声、度量标准等范围巨大...更不用说缺乏公共基准，使得比较方法变得困难。

附加：Python代码kmeans()和kmeanssample()在SO上这里，欢迎评论。

- denis

---

论文《K-Means聚类的初始点优化（1998）》由Bradley和Fayyad撰写，更详细地描述了一种类似的技术：http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.5872 - Predictor

谢谢预测器；你用过这个吗？（好的想法会被重新发现，不太好的想法也是如此。） - denis

你有没有尝试先在一个随机样本上运行k-means++，然后再进行优化？ - Has QUIT--Anony-Mousse

@Anony-Mousse，听起来很合理，但我没有这样做过。请纠正我，数据集变化如此之大，以至于说“在像Y这样的数据上使用变量X”是不可能的吗？ - denis

K-means++是一种更聪明的方法，用于在几乎任何类型的数据上实现种子选择，而不仅仅是随机选择对象。因此，除非您有特定于域的启发式方法来选择更好的种子，否则实际上很少没有使用k-means ++的理由。 - Has QUIT--Anony-Mousse