Bandit-PAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits

Mo Tiwari, Martin Jinye Zhang, James Mayclin, Sebastian Thrun, Chris Piech, Ilan Shomorony

Abstract

Clustering is a ubiquitous task in data science. Compared to the commonly used $k$-means clustering, $k$-medoids clustering requires the cluster centers to be actual data points and support arbitrary distance metrics, which permits greater interpretability and the clustering of structured objects. Current state-of-the-art $k$-medoids clustering algorithms, such as Partitioning Around Medoids (PAM), are iterative and are quadratic in the dataset size $n$ for each iteration, being prohibitively expensive for large datasets. We propose BanditPAM, a randomized algorithm inspired by techniques from multi-armed bandits, that reduces the complexity of each PAM iteration from $O(n^2)$ to $O(n \log n)$ and returns the same results with high probability, under assumptions on the data that often hold in practice. As such, BanditPAM matches state-of-the-art clustering loss while reaching solutions much faster. We empirically validate our results on several large real-world datasets, including a coding exercise submissions dataset, the 10x Genomics 68k PBMC single-cell RNA sequencing dataset, and the MNIST handwritten digits dataset. In these experiments, we observe that BanditPAM returns the same results as state-of-the-art PAM-like algorithms up to 4x faster while performing up to 200x fewer distance computations.

Introduction

While $k$-means is the standard for clustering, it has two major weaknesses: it is restricted to squared Euclidean distance, and its cluster centers (means) are often "ghost" points that do not exist in the real dataset. $k$-medoids addresses this by requiring cluster centers to be actual data points (medoids) and allowing for any distance metric, such as Manhattan, Cosine, or even Edit Distance for text and tree structures.

The gold standard for $k$-medoids is the Partitioning Around Medoids (PAM) algorithm. However, PAM is computationally expensive; each iteration requires a quadratic $O(n^2)$ runtime, creating a massive bottleneck for large datasets. Previous attempts to speed this up usually sacrificed clustering quality. BanditPAM aims to provide the speed of a randomized algorithm with the precision of the original PAM.

Methodology: A Multi-Armed Bandit Approach

BanditPAM observes that PAM’s two main steps—BUILD (finding initial centers) and SWAP (improving centers)—are essentially search problems. To find the best medoid, one does not need to calculate its exact distance to every other point; one only needs enough information to prove it is superior to other candidates.

BanditPAM treats each potential medoid as an "arm" in a Multi-Armed Bandit (MAB) framework:

  1. Adaptive Search: Instead of computing the total loss for every candidate, the algorithm samples small batches of "reference points" to estimate the loss.
  2. Upper Confidence Bounds (UCB): It maintains confidence intervals for each candidate. If a candidate's "best-case" performance is statistically worse than another's "worst-case," it is discarded early.
  3. Successive Elimination: The algorithm focuses its computational budget on the most promising candidates, only calculating exact distances when the competition between the final few candidates is too close to call.

Under reasonable assumptions about data distribution (sub-Gaussianity), the number of distance evaluations needed drops from $O(n^2)$ to $O(n \log n)$.

Experimental Results

The researchers evaluated BanditPAM on several large real-world datasets, including MNIST (70,000 digits), scRNA-seq (40,000 profiles), and HOC4 (3,360 unique programming solutions using Tree Edit Distance).

Clustering Quality Consistency

Unlike previous fast approximations like CLARANS, BanditPAM is designed to return the exact same medoids as the original PAM algorithm. Empirical tests on the MNIST dataset confirm that BanditPAM maintains a loss ratio of 1.0 relative to PAM, whereas other heuristics result in significantly higher loss.

Comparison of final clustering loss normalized to PAM on the MNIST dataset.

Computational Efficiency and Scalability

BanditPAM demonstrated a 4x wall-clock speedup over FastPAM1 on the MNIST dataset and performed up to 200x fewer distance computations. Its scalability is particularly evident when using expensive metrics like Tree Edit Distance. As shown in the figure below, BanditPAM's distance computations scale almost linearly with the dataset size, providing a massive improvement over the quadratic scaling of traditional methods.

Empirical scaling of distance computations on the HOC4 dataset using Tree Edit Distance.

Conclusion

BanditPAM enables $k$-medoids clustering on a wide range of applications that were previously computationally infeasible, such as identifying cell types in large-scale single-cell data. By reducing per-iteration complexity to $O(n \log n)$ while maintaining the precision of the original PAM algorithm, it provides a scalable, robust, and interpretable clustering solution. The authors have released highly optimized Python and C++ implementations to facilitate its use in the broader data science community.

Summary updated

Abstract

Clustering is a ubiquitous task in data science. Compared to the commonly used $k$-means clustering, $k$-medoids clustering requires the cluster centers to be actual data points and support arbitrary distance metrics, which permits greater interpretability and the clustering of structured objects. Current state-of-the-art $k$-medoids clustering algorithms, such as Partitioning Around Medoids (PAM), are iterative and are quadratic in the dataset size $n$ for each iteration, being prohibitively expensive for large datasets. We propose BanditPAM, a randomized algorithm inspired by techniques from multi-armed bandits, that reduces the complexity of each PAM iteration from $O(n^2)$ to $O(n \log n)$ and returns the same results with high probability, under assumptions on the data that often hold in practice. As such, BanditPAM matches state-of-the-art clustering loss while reaching solutions much faster. We empirically validate our results on several large real-world datasets, including a coding exercise submissions dataset, the 10x Genomics 68k PBMC single-cell RNA sequencing dataset, and the MNIST handwritten digits dataset. In these experiments, we observe that BanditPAM returns the same results as state-of-the-art PAM-like algorithms up to 4x faster while performing up to 200x fewer distance computations. The improvements demonstrated by BanditPAM enable $k$-medoids clustering on a wide range of applications, including identifying cell types in large-scale single-cell data and providing scalable feedback for students learning computer science online. We also release highly optimized Python and C++ implementations of our algorithm.
BibTeX
@inproceedings{tiwari2020bandit,
  author = {Mo Tiwari and Martin Jinye Zhang and James Mayclin and Sebastian Thrun and Chris Piech and Ilan Shomorony},
  title = {{Bandit-PAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=LKAhTGcGYA},
}
Figure