k^2 k 2 -means for Fast and Accurate Large Scale Clustering

Eirikur Agustsson, Radu Timofte, Luc Van Gool

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:

  1. 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++.
  2. 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.
Comparison of k-means and Projective Split initialization.

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.

Efficiency benchmarks on CIFAR and MNIST datasets.

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

Abstract

We propose $$k^2$$ -means, a new clustering method which efficiently copes with large numbers of clusters and achieves low energy solutions. $$k^2$$ -means builds upon the standard k-means (Lloyd’s algorithm) and combines a new strategy to accelerate the convergence with a new low time complexity divisive initialization. The accelerated convergence is achieved through only looking at $$k_n$$ nearest clusters and using triangle inequality bounds in the assignment step while the divisive initialization employs an optimal 2-clustering along a direction. The worst-case time complexity per iteration of our $$k^2$$ -means is $$O(nk_nd\,+\,k^2d)$$ , where d is the dimension of the n data points and k is the number of clusters and usually $$n\gg k \gg k_n$$ . Compared to k-means’ O(nkd) complexity, our $$k^2$$ -means complexity is significantly lower, at the expense of slightly increasing the memory complexity by $$O(nk_n+k^2)$$ . In our extensive experiments $$k^2$$ -means is order(s) of magnitude faster than standard methods in computing accurate clusterings on several standard datasets and settings with hundreds of clusters and high dimensional data. Moreover, the proposed divisive initialization generally leads to clustering energies comparable to those achieved with the standard k-means++ initialization, while being significantly faster.
BibTeX
@inproceedings{agustsson2017k,
  author = {Eirikur Agustsson and Radu Timofte and Luc Van Gool},
  title = {{k^2 k 2 -means for Fast and Accurate Large Scale Clustering}},
  booktitle = {ECML/PKDD},
  year = {2017},
  doi = {10.1007/978-3-319-71246-8\_47},
}
Figure