The MinMax k-Means clustering algorithm

• We propose the MinMax k-Means algorithm to minimize the maximum intra-cluster variance objective.
• Weights are assigned to the clusters relative to their intra-cluster variance.
• Our method prevents the occurrence of clusters with large intra-cluster variances in the solution.
• Our method systematically uncovers high quality solutions, irrespective of the initialization.
• MinMax k-Means constitutes a sound approach for initializing k-Means.

Applying k-Means to minimize the sum of the intra-cluster variances is the most popular clustering approach. However, after a bad initialization, poor local optima can be easily obtained. To tackle the initialization problem of k-Means, we propose the MinMax k-Means algorithm, a method that assigns weights to the clusters relative to their variance and optimizes a weighted version of the k-Means objective. Weights are learned together with the cluster assignments, through an iterative procedure. The proposed weighting scheme limits the emergence of large variance clusters and allows high quality solutions to be systematically uncovered, irrespective of the initialization. Experiments verify the effectiveness of our approach and its robustness over bad initializations, as it compares favorably to both k-Means and other methods from the literature that consider the k-Means initialization problem.