Ckmeans.1d.dp: Optimal k-means Clustering in One Dimension by Dynamic Programming

Abstract

The heuristic <i>k</i>-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 <b>Ckmeans.1d.dp</b>. We demonstrate its advantage in optimality and runtime over the standard iterative <i>k</i>-means algorithm.