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:
- Adaptive Search: Instead of computing the total loss for every candidate, the algorithm samples small batches of "reference points" to estimate the loss.
- 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.
- 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.
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.
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