k均值的计算复杂性

Question

我正在浏览k-means wiki页面.基于该算法,我认为复杂度是O(n*k*i)(n=总元素,k=聚类迭代次数)

那么有人可以从维基百科向我解释这个声明吗？这个NP怎么样难？

如果k和d(维度)是固定的,问题可以及时准确地解决,其中是要聚类的实体的数量.O(ndk+1 log n)n

Answer 1

这取决于你所谓的k -means.找到k -means目标函数的全局最优的问题

是NP难的.但是,运行一个固定数量的我的迭代的标准算法只需要O(iknd为)ñ在点d的尺寸,这是什么实际的实现做(常与迭代之间随机重启).标准算法仅近似于上述函数的局部最优值,我所见过的所有k -means算法也是如此.