Abstract
Clustering is a fundamental task in data science, but the standard Lloyd’s algorithm ($k$-means) faces severe scalability issues as datasets grow in size and complexity. We present $k^2$-means, a high-performance clustering algorithm designed to handle massive datasets with thousands of clusters. By combining a novel "Projective Split" initialization with a localized search strategy, $k^2$-means achieves order-of-magnitude speedups over standard $k$-means while maintaining identical accuracy. Our approach effectively makes the assignment step sublinear in the number of clusters, enabling efficient processing of millions of points.
Introduction
Lloyd’s algorithm is the "bread and butter" of clustering, yet its $O(ndki)$ complexity makes it prohibitively slow for large-scale applications where $n$ (samples) and $k$ (clusters) are large. While $k$-means++ improves solution quality, its initialization phase is itself as slow as a full iteration. Approximate methods like MiniBatch $k$-means offer speed but often at the cost of significant clustering quality. $k^2$-means addresses these bottlenecks by optimizing both initialization and the iterative refinement process.
Methodology: Fast Initialization and Localized Assignment
The $k^2$-means algorithm introduces two primary innovations to overcome the limitations of traditional $k$-means:
- Greedy Divisive Initialization (GDI): Instead of sequential sampling, GDI uses a Projective Split algorithm. It starts with a single cluster and recursively splits the highest-energy cluster. By picking two seeds and projecting points onto the line between them, it finds an optimal split point significantly faster than $k$-means++.
- Localized Assignment: Recognizing that cluster centers move slowly between iterations, $k^2$-means restricts the search for a point's new cluster to the $k_n$ nearest neighbors of its current center. This exploits temporal coherence to ignore the vast majority of the search space.
The algorithm also integrates Elkan’s triangle inequality pruning, adapted for localized neighbor sets to minimize memory overhead. The resulting per-iteration complexity drops to approximately $O(nk_nd + k^2d)$, where $k_n \ll k$.
Experimental Results
We evaluated $k^2$-means on diverse benchmarks including computer vision (MNIST, CIFAR) and general datasets (Covtype). $k^2$-means consistently outperformed existing methods in efficiency while maintaining high accuracy.
In experiments reaching an energy within 1% of the optimal Lloyd++ solution, $k^2$-means was 33x faster on average. On specific datasets like covtype with 1,000 clusters, it reached the target 176x faster. Unlike approximate methods like AKM, $k^2$-means consistently reaches exact convergence (0% error) while remaining significantly faster, averaging a 104x speedup for exact solutions.
Conclusion
$k^2$-means provides a scalable solution for large-scale clustering by exploiting temporal coherence and efficient initialization. By making the assignment step effectively sublinear in $k$, it offers a rare combination of extreme speed and high accuracy, making it suitable for modern big data challenges.
Summary updated