r - 对一维数据进行最佳聚类？

Question

有没有人有一篇论文解释了Ckmeans.1d.dp算法是如何工作的？

或者：在一维中进行 k-means 聚类的最佳方法是什么？

Answer 1

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

更好的选择是现在在 Ckmeans.1d.dp 版本 3.4.6 中实现的 O(knlgn) 方法。这种实现与启发式 k-means 一样快，但提供了有保证的最优性，比启发式 k-means 好几个数量级，尤其是对于较大的 k。

Richard Bellman (1973) 的通用动态规划解决方案没有涉及 k-means 问题的细节，并且隐含的运行时间为 O(kn^3)。