Further heuristics for -means: The merge-and-split heuristic and the -means
arXiv:1406.6314
Abstract
Finding the optimal -means clustering is NP-hard in general and many heuristics have been designed for minimizing monotonically the -means objective. We first show how to extend Lloyd's batched relocation heuristic and Hartigan's single-point relocation heuristic to take into account empty-cluster and single-point cluster events, respectively. Those events tend to increasingly occur when or increases, or when performing several restarts. First, we show that those special events are a blessing because they allow to partially re-seed some cluster centers while further minimizing the -means objective function. Second, we describe a novel heuristic, merge-and-split -means, that consists in merging two clusters and splitting this merged cluster again with two new centers provided it improves the -means objective. This novel heuristic can improve Hartigan's -means when it has converged to a local minimum. We show empirically that this merge-and-split -means improves over the Hartigan's heuristic which is the {\em de facto} method of choice. Finally, we propose the -means objective that generalizes the -means objective by associating the data points to their closest cluster centers, and show how to either directly convert or iteratively relax the -means into a -means in order to reach better local minima.
14 pages