Abstract
Finding the global optimum in k-means clustering is an NP-hard problem often plagued by local minima. We present recombinator-k-means, a new evolutionary algorithm that utilizes a population-wide crossover mechanism. By pooling centroids from an entire population and "recombining" them using a modified k-means++ seeding strategy, the algorithm effectively navigates complex data landscapes. Experimental results on synthetic and real-world datasets demonstrate that Recombinator-k-means consistently achieves superior success rates and lower error compared to standard local search and traditional genetic algorithms, particularly on difficult, high-dimensional datasets.
Introduction
The k-means clustering problem—minimizing the Sum-of-Squares Error (SSE)—is a cornerstone of data science. However, the standard Lloyd’s algorithm is a local search method that frequently gets trapped in sub-optimal local minima depending on its initial "seeding." Even advanced seeding techniques like k-means++ often fail when the data landscape is riddled with local minima. To find the true global optimum in complex datasets, researchers often turn to evolutionary algorithms (EAs). Yet, most existing EAs for clustering rely on pairwise crossover, which can be slow to explore the vast space of possible clusterings. Recombinator-k-means addresses these limitations through a novel population-wide crossover approach.
Methodology
Recombinator-k-means is a memetic algorithm that hybridizes evolutionary strategies with local refinement. Its core innovation is the population-wide crossover process:
- The Pool: Instead of selecting two parents, the algorithm pools all centroids from every individual in the current generation into a single reservoir.
- Reservoir-k-means++: A repurposed version of the k-means++ algorithm selects $k$ new centroids from this massive pool, effectively recombining the best features of multiple solutions.
- Soft Selection: A reweighting mechanism, controlled by a parameter $\beta$, ensures that better-performing individuals have a higher probability of contributing their centroids. This parameter increases over time to transition the algorithm from exploration to exploitation.
- Local Optimization: Each new individual is refined using Lloyd’s algorithm to ensure convergence to a local optimum.
Experimental Setup
The algorithm was evaluated against several benchmarks, including an optimized implementation of the state-of-the-art GA-k-means (augmented with k-means++ seeding, referred to as GA++). Testing spanned both synthetic datasets with known ground truths and complex real-world datasets.
Results and Discussion
Global Optimum Recovery
On synthetic benchmarks, Recombinator-k-means and the augmented GA++ achieved a 100% success rate in finding the global optimum. In contrast, standard k-means++ and basic k-means performed poorly, with k-means++ achieving only a 5.4% success rate on the A3 dataset.
Time-Quality Trade-offs
The experiments revealed a distinct trade-off between runtime and solution quality. For shorter runtimes, GA++ is often superior due to the lower computational cost of pairwise crossover. However, for longer runtimes or highly difficult datasets like UrbanGB (car accident coordinates) and Olivetti (face images), Recombinator-k-means consistently finds lower SSE values and more structurally meaningful clusters, as indicated by improved Variation of Information (VI) scores.
Key Insights
A critical observation is that when k-means fails, different runs usually make uncorrelated mistakes. By pooling centroids from many runs, the reservoir likely contains all "correct" centroids. The k-means++ logic then excels at selecting one representative from each true cluster while ignoring the "outlier" centroids produced by individual failures. Furthermore, the results demonstrate that starting with a high-quality seed is crucial even for evolutionary algorithms; without it, populations may miss small, well-defined clusters entirely.
Conclusion
Recombinator-k-means offers a simple yet powerful approach to global clustering optimization. By leveraging the logic of k-means++ for population-wide recombination, it avoids the pitfalls of local minima that stymie traditional methods. While the population-wide crossover is more memory-intensive and computationally expensive per generation, its ability to find the global optimum in complex landscapes makes it a robust tool for high-stakes clustering tasks. Future work will explore parallelization on GPU architectures and extending the reservoir approach to other representative-based clustering objectives.
Summary updated