劳埃德算法
是否可以运行劳埃德算法来在多项式时间内找到一维的 k 均值？
我知道 k 均值问题对于一维以外的任何事物都是 NP 困难的。 如果你有一个固定的维度，劳埃德算法将在多项式时间内运行，对吧？
Is it possible to run Lloyd's algorithm to find the k-means in one-dimension in polynomial-time?
I know that that the k-means problem is NP-hard for anything more than one-dimensions.
Any if you have a fixed dimension, Lloyd's algorithm will run in polynomial time, right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在实践中我不会太担心 k 均值的运行时间。您可以构建使其需要指数时间才能运行的分布，但如果这些输入有一点噪音，则运行时间将是多项式。 http://theory.stanford.edu/~sergei/papers/kMeans-socg .pdf
I wouldn't worry too much about the running times of k means in practice. You can construct distributions that make it take exponential time to run, but if those inputs are noised up a little bit, the running time will be polynomial. http://theory.stanford.edu/~sergei/papers/kMeans-socg.pdf
真正的 k 均值算法是 NP 难的，并且始终会产生最优结果。 Lloyd 算法是一种启发式 k 均值算法，它“可能”产生最优值，但通常更可取，因为它可以多次运行。
A true k-means algorithm is in NP hard and always results in the optimum. Lloyd's algorithm is a Heuristic k-means algorithm that "likely" produces the optimum but is often preferable since it can be run in poly-time.