最优地聚类一维数据？

Question

有没有一篇介绍Ckmeans.1d.dp算法工作原理的论文？

或者，如何以最优方式在一维上进行K均值聚类？

- Laciel

---

谷歌搜索到了乌得勒支大学的Knops、Maintz、Pluim和Viergever（2004）的技术报告，题为“使用动态规划进行最优一维k-means聚类”，但该报告并未在线上公开。不幸的是，这个模块的C++代码非常难以阅读。对于这个有趣的问题点赞。 - Fred Foo

我认为这是您要找的论文：Ckmeans.1d.dp: 动态规划中一维最优k-均值聚类，作者为王海洲和宋明州。 - Christoph Hösler

Answer 1

基于蒙杰矩阵的理论结果，单变量k-means聚类可在O(kn)时间内解决（在已排序的输入上），但这种方法并不流行，最可能是由于数值不稳定性和编码挑战所导致。

更好的选择是一个O(knlgn)方法，现在已经实现在Ckmeans.1d.dp版本3.4.6中。这个实现速度与启发式k-means一样快，但能够提供保证的最优性，特别是对于大的k而言，比启发式k-means好得多。

Richard Bellman（1973）的通用动态规划解决方案没有涉及到k-means问题的细节，暗示的运行时间是O(kn^3)。

- user6417312