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.
Text and figures are licensed under Creative Commons Attribution CC BY 4.0. The figures that have been reused from other sources don't fall under this license and can be recognized by a note in their caption: "Figure from ...".
For attribution, please cite this work as
Wang & Song, "Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming", The R Journal, 2011
BibTeX citation
@article{RJ-2011-015,
author = {Wang, Haizhou and Song, Mingzhou},
title = {Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming},
journal = {The R Journal},
year = {2011},
note = {https://doi.org/10.32614/RJ-2011-015},
doi = {10.32614/RJ-2011-015},
volume = {3},
issue = {2},
issn = {2073-4859},
pages = {29-33}
}