Ckmeans clustering is an improvement on 1-dimensional heuristic-based clustering approaches such as Jenks. The algorithm was developed by Haizhou Wang and Mingzhou Song (2011) as a dynamic programming approach to the problem of clustering numeric data into groups with the least within-group sum-of-squared-deviations.
Minimizing the difference within groups – what Wang & Song refer to as withinss, or within sum-of-squares – means that groups are optimally homogenous within and the data is split into representative groups. This is very useful for visualization, where one may wish to represent a continuous variable in discrete colour or style groups. This function can provide groups that emphasize differences between data.
Being a dynamic approach, this algorithm is based on two matrices that store incrementally-computed values for squared deviations and backtracking indexes.
Unlike the original implementation, this implementation does not include any code to automatically determine the optimal number of clusters: this information needs to be explicitly provided. It does provide the roundbreaks method to aid labelling, however.
This is a port (including documentation) of David Schnurr's package https://github.com/schnerd/ckmeans, incorporating some improvements from Bill Mill's Python + Numpy implementation at https://github.com/llimllib/ckmeans.
On an M2 Pro, the algorithm will classify 110k uniformly-distributed i32 values between 0 and 250 into 7 classes in ~16 ms.
$O(n^2k)$
The "matrices" are nested vectors and thus don't have optimal memory layout. In addition, we're not trying to leverage any of the fast linear algebra libraries that might be available if we used e.g. ndarray.
Perhaps some property-based tests