Big-means++ Algorithm Improves K-means Clustering for Large Datasets

Researchers have developed Big-means++, a new algorithm designed to overcome the challenges of K-means clustering on massive datasets, particularly when dealing with arbitrarily large numbers of observations. The traditional Minimum Sum-of-Squares Clustering (MSSC) problem, which K-means addresses, is NP-hard, and existing solutions often fall into poor local minima or require computationally expensive metaheuristic approaches. Big-means++ tackles this by curating inputs for MSSC optimization on big data, effectively orchestrating local K-means refinements into a global search mechanism. Instead of directly optimizing the full-data MSSC objective, Big-means++ navigates through "sample-induced surrogate landscapes." Each random sample generates a distinct empirical MSSC approximation, and the variation between these samples is leveraged as a global-search mechanism. A key innovation is its "flowing-incumbent strategy," which propagates centroid states across these empirical landscapes using K-means refinements on fresh samples, promoting mobility and favoring stable, high-quality configurations. Additionally, a new "shaking mechanism" geometrically varies sample sizes to explore broader surrogate landscapes and account for cluster imbalance. The algorithm also incorporates a competitive multi-agent system that asynchronously explores independent sampled landscapes, transforming diverse stochastic trajectories into collective search intelligence, with automatic convergence detection for efficiency.