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

Question

的k均值++算法有助于以下两个原始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) - 与最佳解决方案竞争.无论ķ -means ++和常用的方法,所谓的劳合社的算法,是近似的NP难的优化问题.

我不确定k -means ++ 最糟糕的运行时间是什么; 请注意,在Arthur&Vassilvitskii的原始描述中,算法的步骤2-4涉及Lloyd的算法.他们确实声称它在实践中既更好又更快,因为它从更好的位置开始.

因此,k -means ++ 的缺点是:

1. 它也可以找到一个次优的解决方案(它仍然是一个近似值).
2. 它并不比Lloyd的算法更快(参见Arthur和Vassilvitskii的表格).
3. 它比Lloyd的算法更复杂.
4. 这是相对较新的,而劳埃德已经证明它超过50年的价值.
5. 特定度量空间可能存在更好的算法.

也就是说,如果你的k -means库支持k -means ++,那么一定要试一试.

Answer 2

不是你的问题,但对于大N的任何kmeans方法都很容易加速:

1)首先对点
2 的所述sqrt(N)的随机样本进行k均值,然后从这些中心运行完全k均值.

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

你的N(数据点数),暗淡(特征数量)和k是多少？
用户的N,dim,k,数据噪声,指标的巨大范围......更不用说缺乏公共基准,这使得比较方法变得困难.

补充:kmeans()和kmeanssample()的Python代码 在这里 ; 欢迎评论.