一维数据最佳聚类？

有没有人有一篇文章解释Ckmeans.1d.dpalgorithm的工作原理？

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

Answer 1

我认为这是你正在寻找的文件：

Ckmeans.1d.dp：王海洲宋明明dynamic规划的一维最优k-均值聚类 。

Answer 2

这是来自Bellman的非常古老的技术：关于聚类分析和dynamic规划的说明http://www.sciencedirect.com/science/article/pii/0025556473900072

http://www.informationgeometry.org

Answer 3

单variablesk均值聚类可以基于Mongematrix的理论结果在O（kn）时间（在已经sorting的input上）求解，但是由于数值不稳定性和编码挑战，这种方法并不普遍。

更好的select是现在在Ckmeans.1d.dp版本3.4.6中实现的O（knlgn）方法。 这种实现与启发式k均值一样快，但是提供了保证的最优性，比启发式k均值好几个数量级，特别是对于大k值。

理查德·贝尔曼（Richard Bellman，1973）的通用dynamic规划解决scheme没有涉及到k-均值问题的具体细节，隐含的运行时间是O（kn ^ 3）。