k-means的时间复杂度是什么？

Question

我正在阅读 k-means聚类 的维基百科页面。根据算法，我认为复杂度为O(n*k*i)（其中n = 元素总数，k = 群集迭代次数）。

那么，有人能解释一下维基百科中这个陈述的含义以及它是如何成为NP难题的吗？

如果 k 和 d（维度）固定，则该问题可以在时间 O(ndk+1 log n) 内得到精确解，其中n是要进行聚类的实体数量。

- parallel

Answer 1

这取决于你所谓的k-means是什么。

找到k-means目标函数的全局最优解的问题。

这里涉及的问题是NP-hard，其中Si是簇i（共有k个簇），xj是簇Si中的d维点，μi是簇Si的质心（点的平均值）。

然而，运行标准算法的固定迭代次数t仅需要O(t*k*n*d)，其中n为d维点的数量，k是质心（或簇）的数量。实际实现通常采用此方法（在迭代之间进行随机重启）。

标准算法只能近似得找到上述函数的局部最优解，我所看到的所有k-means算法也是如此。

- Fred Foo

Answer 2

问题是NP-Hard，因为有另一个已知的NP难题可以归约到（平面）k-means问题。请参阅Mahajan等人的论文{{link1：Planar k-means问题是NP-hard}}了解更多信息。

- Trect