# BanditPAM: Almost Linear-Time k-medoids Clustering via Multi-Armed Bandits

DevFeed: [BanditPAM: Almost Linear-Time k-medoids Clustering via Multi-Armed Bandits](<https://devfeed.tech/articles/banditpam-almost-linear-time-k-medoids-clustering-via-multi-armed-bandits-7579.md>)

Original publisher: [Read original article](<https://ai.stanford.edu/blog/banditpam/>)

Author: A Href; Mo Tiwari

Published: 2021-12-17T08:00:00Z

Content type: article

Language: en

Sources: [The Stanford AI Lab Blog](<https://devfeed.tech/sources/the-stanford-ai-lab-blog.md>)

Topics: [AI, ML & Data Engineering](<https://devfeed.tech/topics/ai-ml-data-engineering.md>), [C++](<https://devfeed.tech/topics/c-plus-plus.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [c-plus-plus](<https://devfeed.tech/tags/c-plus-plus.md>), [code](<https://devfeed.tech/tags/code.md>), [complexity](<https://devfeed.tech/tags/complexity.md>), [neurips](<https://devfeed.tech/tags/neurips.md>), [speed](<https://devfeed.tech/tags/speed.md>)

## AI overview

BanditPAM is a publicly available k-medoids clustering implementation that reduces the stated runtime from O(n²) to O(n log n). It is pip-installable, written in C++, and designed to resemble the sklearn.cluster.KMeans interface.

## Source excerpt

TL;DR Want something better than \(k\)-means? Our state-of-the-art \(k\)-medoids algorithm from NeurIPS, BanditPAM, is now publicly available! \(\texttt{pip install banditpam}\) and you're good to go! Like the \(k\)-means problem, the \(k\)-medoids problem is a clustering problem in which our objective is to partition a dataset into disjoint subsets. In \(k\)-medoids, however, we require that the cluster centers must be actual datapoints, which permits greater interpretability of the cluster centers. \(k\)-medoids also works better with arbitrary distance metrics, so your clustering can be more robust to outliers if you're using metrics like \(L_1\). Despite these advantages, most people don't use \(k\)-medoids because prior algorithms were too slow. In our NeurIPS paper, BanditPAM, we sped up the best known algorithm from \(O(n^2)\) to \(O(n\text{log}n)\). We've released our implementation, which is pip-installable. It's written in C++ for speed and supports parallelization and intelligent caching, at no extra complexity to end users. Its interface also matches the \(\texttt{sklearn.cluster.KMeans}\) interface, so minimal changes are necessary to existing code. Useful Links: 3-minute video summary PyPI Github Repository Full Paper \(k\)-means vs. \(k\)-medoids If you're an ML practitioner, you're probably familiar with the \(k\)-means problem. In fact, you may know some of the common algorithms for the \(k\)-means problem. You're much less likely, however, familiar with the \(k\)-medoids problem. The \(k\)-medoids problem is a clustering problem similar to \(k\)-means. Given a dataset, we want to partition our dataset into subsets where the points in each cluster are closer to a single cluster center than all other \(k-1\) cluster centers. Unlike in \(k\)-means, however, the \(k\)-medoids problem requires cluster centers to be actual datapoints. Figure 1: The \(k\)-medoids solution (left) forces the cluster centers to be actual datapoints. This solution is often di