Recombinator-k-means: A population based algorithm that exploits k-means++ for recombination

Carlo Baldassi

Abstract

We present a simple heuristic algorithm for efficiently optimizing the notoriously hard minimum sum-of-squares clustering problem, usually addressed by the classical $k$-means heuristic and its variants. The algorithm, called recombinator-$k$-means, uses populations of configurations that are optimized independently in parallel and then recombined in a next-iteration population batch by exploiting a variant of the $k$-means++ seeding algorithm. An additional reweighting mechanism ensures that the population eventually coalesces into a single solution. Extensive tests on synthetic and real-world data show that it consistently produces high-quality results across all time scales, outperforming state-of-the-art alternatives on large and complicated datasets.

Introduction

Clustering is a fundamental task in data science, yet the standard $k$-means algorithm (Lloyd’s algorithm) is notoriously prone to converging to local minima. While $k$-means++ provides a smarter initialization, practitioners often rely on multiple independent restarts to find a near-optimal solution. However, independent restarts are inefficient because they discard valuable information from "failed" runs that might have correctly identified most clusters. Recombinator-$k$-means addresses this by treating centroids from previous runs as a "reservoir" for seeding new ones.

The Recombinator-k-means Algorithm

The proposed algorithm resembles a genetic-style scheme but replaces traditional geometric crossover with a seeding-based recombination.

The Reservoir and Recombination

The algorithm maintains a population of $J$ configurations. All centroids from these configurations are pooled into a "reservoir." To generate a new configuration, the algorithm samples from this reservoir using a weighted variant of the $k$-means++ seeding procedure. This ensures that new starting points are constructed from components that have already proven effective in previous iterations.

Visualization of the centroid reservoir. Left: Four independent k-means runs with 'mistakes' (red stars). Right: Heatmap showing how correct centroids cluster together in the reservoir.

As shown in Figure 1, while individual runs may contain "mistakes" (red stars), the correct centroids consistently appear across multiple runs, forming dense clusters in the reservoir. The recombination process exploits this density to find the global optimum.

Reweighting and Coalescence

To prioritize better solutions, centroids are weighted based on the Sum-of-Squares Error (SSE) of their parent configuration. A parameter $\beta$ is gradually increased to "sharpen" these weights, eventually forcing the population to coalesce into a single, high-quality consensus solution. Crucially, the algorithm is highly parallelizable, as the configurations in each batch can be optimized independently.

Experimental Evaluation

The algorithm was tested on a variety of benchmarks, including synthetic high-dimensional data and large-scale real-world datasets like UrbanGB (~360,000 car accidents in the UK). Recombinator-$k$-means consistently outperformed state-of-the-art methods like random swaps and genetic algorithms with pairwise-nearest-neighbor crossover.

Comparison of SSE distributions. The greedy k-means++ seeding (blue) consistently achieves lower error closer to the ground truth compared to uniform random seeding (green).

Figure 2 illustrates the advantage of the seeding strategy. The distribution of SSE values for the proposed seeding method is significantly shifted toward the ground truth compared to uniform random seeding, demonstrating its effectiveness in avoiding poor local minima and recovering the true underlying cluster structure.

Conclusion

Recombinator-$k$-means offers a powerful framework for global clustering optimization. By replacing traditional genetic crossover with a seeding-based recombination from a centroid reservoir, it achieves superior performance with minimal parameter tuning. The implementation is publicly available in Julia, providing a robust tool for large-scale clustering challenges.

Summary updated

Abstract

We present a simple heuristic algorithm for efficiently optimizing the notoriously hard minimum sum-of-squares clustering problem, usually addressed by the classical k-means heuristic and its variants. The algorithm, called recombinator-k-means, is very similar to a genetic algorithmic scheme: it uses populations of configurations, that are optimized independently in parallel and then recombined in a next-iteration population batch by exploiting a variant of the k-means++ seeding algorithm. An additional reweighting mechanism ensures that the population eventually coalesces into a single solution. Extensive tests measuring optimization objective vs computational time on synthetic and real-word data show that it is the only choice, among state-of-the-art alternatives (simple restarts, random swap, genetic algorithm with pairwise-nearest-neighbor crossover), that consistently produces good results at all time scales, outperforming competitors on large and complicated datasets. The only parameter that requires tuning is the population size. The scheme is rather general (it could be applied even to k-medians or k-medoids, for example). Our implementation is publicly available at this https URL.
BibTeX
@article{baldassi2022recombinator,
  author = {Carlo Baldassi},
  title = {{Recombinator-k-means: A population based algorithm that exploits k-means++ for recombination}},
  journal = {IEEE Trans. Evol. Comput.},
  year = {2022},
  doi = {10.1109/tevc.2022.3144134},
}
Figure