Optimal interval clustering: Application to Bregman clustering and statistical mixture learning

2014/03/11 by Frank Nielsen, Nielsen, Frank, Richard Nock +1
Computer Science · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #cs.IT #cs.LG #math.IT

paper · pdf · doi:10.48550/arxiv.1403.2485

10 pages, 3 figures

arxiv created 2014/05/26 · arxiv updated 2014/05/27

Abstract

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.

Related

• Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D
• k-MLE, k-Bregman, k-VARs: Theory, Convergence, Computation
• Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models
• Clustering subgaussian mixtures by semidefinite programming
• Probabilistic Clustering Using Maximal Matrix Norm Couplings