Optimal interval clustering: Application to Bregman clustering and statistical mixture learning
This work provides a foundational algorithm for interval clustering, applicable to domains like Bregman clustering and statistical mixture learning, but it is incremental as it builds on existing dynamic programming approaches.
The authors tackled the problem of optimally clustering scalar elements into intervals using a generic dynamic programming method, achieving exact solutions for various clustering criteria like k-means and extending it to include cluster size constraints and model selection for choosing k.
We present a generic dynamic programming method to compute the optimal clustering of $n$ scalar elements into $k$ pairwise disjoint intervals. This case includes 1D Euclidean $k$-means, $k$-medoids, $k$-medians, $k$-centers, etc. We extend the method to incorporate cluster size constraints and show how to choose the appropriate $k$ by model selection. Finally, we illustrate and refine the method on two case studies: Bregman clustering and statistical mixture learning maximizing the complete likelihood.