AbstractWe describe a dynamic programming (DP) technique to compute the optimal Bregman k-means clustering of nscalar values. We further show how to incorporate constraints on theminimum sizes of clusters. We then illustrate how to use this DP algorithm for learning univari-ate statistical mixture models of exponential families maximizing the complete data likelihood,and perform model selection from the DP table. 1 Introduction Clustering is a fundamental and key primitive to discover structural groups of homogeneous data,called clusters, in d-dimensional data sets. The most famous clustering technique is the celebratedk-means [1] that seeks to minimize the sum of intra-cluster variances by prescribing beforehandthe number, k, of clusters. On one hand, solving for the k-mean problem is in general NP-hardwhen k>1 and d= 2 [8], or even when k= 2 and dis the parameter of interest [7]. There isa rich and still ourishing literature on k-means that proposes and studies heuristics. In practice,Lloyd’s batched k-means heuristic [1] is often used: Given an initialization of the cluster centers, ititeratively assigns data to their current closest center, and remap those cluster centers to their datacentroids. This heuristic monotonically decreases the sum of intra-cluster variances until it reachesconvergence after a nite number of iterations. It has been noticed that as the dimension increases,some clusters found by Lloyd’s heuristic may become empty [4]. This problem can be bypassed bysetting cluster size constraints [4]. A good initialization for Lloyd’s k-means heuristic is also essentialsince there are many local minima. The k-means++ heuristic [5] is such an initialization procedurethat picks cluster centers iteratively according to a distribution on the distances of the data pointsto the current chosen centers. Although k-means++ (viewed as a discrete k-means) guaranteesto nd a (logk) competitive initialization in expected analysis, it was found very recently thatthere exist bad planar point sets [5] for which the probability to get such a good initialization hasprobability exponentially small in k.
['Frank Nielsen', 'Richard Nock']
A note on the optimal scalar Bregman k-means clustering with an application to learning best statistical mixtures