Optimization of cluster one-dimensional data?

Question

Does anyone have a document explaining how Ckmeans.1d.dp works?

Or: what is the most optimal way k-means clustering in one-dimensional?

Answer 1

I think this is the paper you are looking for:

Ckmeans.1d.dp: Optimal k-value Clustering in one dimension using dynamic programming by Haizhou Wang and Mingzhou Song .

Answer 2

This is a very old Bellman technique: A Note on Cluster Analysis and Dynamic Programming http://www.sciencedirect.com/science/article/pii/0025556473900072

www.informationgeometry.org

Answer 3

One-dimensional clustering of k-values ​​can be solved in O (kn) time (at an already sorted input) based on theoretical results on Monge matrices, but this approach was not popular, most likely due to numerical instability, and also, possibly, for encoding tasks.

The best option is the O (knlgn) method, which is now implemented in Ckmeans.1d.dp version 3.4.6. This implementation is as fast as the heuristic k-tool, but provides guaranteed optimality, an order of magnitude better than the heuristic k-tool, especially for large k.

The general dynamic programming solution by Richard Bellman (Richard Bellman, 1973) does not affect the specifics of the k-means problem, but the implied runtime is O (kn ^ 3).