Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic
Programming Haizhou Wang, Mingzhou Joe Song · 2011
The heuristic k-means algorithm, widely used for cluster analysis, does not guarantee optimality. We developed a dynamic programming algorithm for optimal one-dimensional clustering. The algorithm is implemented as an R package called Ckmeans.1d.dp. We demonstrate its advantage in optimality and runtime over the standard iterative k-means algorithm.