是否可以运行劳埃德算法以在多项式时间内找到一维的 k 均值？
我知道 k-means 问题对于任何一维以上的问题都是 NP-hard 的。任何如果你有一个固定的维度，劳埃德的算法将在多项式时间内运行，对吧？
问问题
1810 次
2 回答
0
真正的 k-means 算法是 NP 难的，并且总是会产生最优结果。Lloyd 算法是一种启发式 k-means 算法，它“可能”产生最优值，但通常更可取，因为它可以多次运行。
于 2015-01-24T02:19:54.917 回答
0
在实践中，我不会太担心 k 均值的运行时间。您可以构建使其运行时间呈指数增长的分布，但如果这些输入被噪声化了一点，运行时间将是多项式的。 http://theory.stanford.edu/~sergei/papers/kMeans-socg.pdf
于 2011-10-18T18:55:59.433 回答