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.
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.
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