Fast Approximate $K$-Means via Cluster Closures

Jingdong Wang 0001, Jing Wang 0068, Qifa Ke, Gang Zeng, Shipeng LiarXiv 2013 · arXiv

Introduction

The scalability of $k$-means clustering is a critical challenge in modern data science, particularly for high-dimensional datasets common in image retrieval. The standard Lloyd’s algorithm requires an assignment step where each of $n$ data points is compared against $k$ cluster centers, resulting in $O(nk)$ complexity per iteration. For datasets with millions of points and clusters, this becomes a prohibitive computational bottleneck.

While approximate methods like Hierarchical $K$-Means (HKM) and forest-based Approximate $K$-Means (AKM) have been proposed, they often suffer from accuracy loss or high maintenance overhead. This paper introduces Cluster Closures, a method that exploits the spatial stability of data points to achieve nearly $O(n)$ complexity.

The Active Point Hypothesis

A key insight of this work is that most data points do not change their cluster assignments between iterations. The "active" points—those that do switch—are typically found near the boundaries between clusters.

Distribution of distance ratios showing that active points (red) are concentrated at low distance ratios near cluster boundaries.

As shown in the figure above, points with a small distance ratio (the ratio of distances to the nearest and second-nearest centers) are much more likely to be active. By focusing computational effort on these boundary regions, the algorithm can bypass exhaustive searches for the majority of the dataset.

Methodology: Cluster Closures

The proposed algorithm, Cluster Closure, operates in three main phases:

1. Pre-processing and Neighborhood Indexing

Unlike previous methods that re-index moving cluster centers, Cluster Closure indexes the static data points once. Using multiple Random Partition (RP) trees, the algorithm groups neighboring points into leaf nodes. This neighborhood information remains valid throughout the clustering process.

2. Defining Cluster Closures

A "cluster closure" $\bar{G}$ is defined as the union of the neighborhoods $N_x$ of all points $x$ currently assigned to a cluster $G$. This creates an expanded region that encompasses the cluster and its immediate surroundings.

Conceptual diagram of a cluster $G$ and its closure $\bar{G}$, formed by the union of point neighborhoods $N_x$.

3. Fast Assignment

During the assignment step, a point $x$ is only compared against cluster centers whose closures contain $x$. Since any given point typically falls within only a few cluster closures, the number of candidate centers is reduced to a small constant, effectively decoupling the complexity from $k$.

Experimental Evaluation

The authors evaluated Cluster Closure on several large-scale computer vision datasets, including 1M SIFT features and 1M GIST features (Tiny Images).

Performance and Scalability

On a dataset of 1M GIST features with 10K clusters, the algorithm achieved a 2.5x speedup over state-of-the-art AKM and HKM implementations. Furthermore, the assignment step demonstrated nearly linear parallel speedup on multi-core systems.

Clustering Quality

In image retrieval benchmarks (Oxford 5K and Ukbench 10K), visual codebooks generated via Cluster Closures outperformed those from competing methods. For instance, a 750K-word codebook from this method yielded better retrieval accuracy than a 1M-word codebook from standard AKM, indicating superior cluster quality.

Conclusion

Cluster Closures offer a powerful alternative for large-scale $k$-means by shifting the focus from dynamic center indexing to static data indexing. By targeting the boundary regions where cluster assignments are most likely to change, the method achieves significant speedups without sacrificing accuracy. Future work may address memory overhead for massive datasets and explore the application of this technique to non-visual high-dimensional domains.

Summary updated

Abstract

K$-means, a simple and effective clustering algorithm, is one of the most widely used algorithms in multimedia and computer vision community. Traditional $k$-means is an iterative algorithm---in each iteration new cluster centers are computed and each data point is re-assigned to its nearest center. The cluster re-assignment step becomes prohibitively expensive when the number of data points and cluster centers are large. In this paper, we propose a novel approximate $k$-means algorithm to greatly reduce the computational complexity in the assignment step. Our approach is motivated by the observation that most active points changing their cluster assignments at each iteration are located on or near cluster boundaries. The idea is to efficiently identify those active points by pre-assembling the data into groups of neighboring points using multiple random spatial partition trees, and to use the neighborhood information to construct a closure for each cluster, in such a way only a small number of cluster candidates need to be considered when assigning a data point to its nearest cluster. Using complexity analysis, image data clustering, and applications to image retrieval, we show that our approach out-performs state-of-the-art approximate $k$-means algorithms in terms of clustering quality and efficiency.
BibTeX
@misc{wang2013fast,
  author = {Jingdong Wang and Jing Wang and Qifa Ke and Gang Zeng and Shipeng Li},
  title = {{Fast Approximate $K$-Means via Cluster Closures}},
  year = {2013},
  eprint = {1312.3061},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1312.3061},
}

Loading related content...

Figure