OneBatchPAM: A Fast and Frugal K-Medoids Algorithm

2025-01-31 · Antoine de Mathelin, Nicolas Enrique Cecchi, François Deheeger, Mathilde Mougeot, Nicolas Vayatis

This paper proposes a novel k-medoids approximation algorithm to handle large-scale datasets with reasonable computational time and memory complexity. We develop a local-search algorithm that iteratively improves the medoid selection based on the estimation of the k-medoids objective. A single batch of size m << n provides the estimation, which reduces the required memory size and the number of pairwise dissimilarities computations to O(mn), instead of O(n^2) compared to most k-medoids baselines. We obtain theoretical results highlighting that a batch of size m = O(log(n)) is sufficient to guarantee, with strong probability, the same performance as the original local-search algorithm. Multiple experiments conducted on real datasets of various sizes and dimensions show that our algorithm provides similar performances as state-of-the-art methods such as FasterPAM and BanditPAM++ with a drastically reduced running time.

📄 PDF Abstract BibTeX arXiv:2501.19285

Code (1)

antoinedemathelin/obpam 공식 구현

BanditPAM++: Faster $k$-medoids Clustering

2023-09-21 · NeurIPS 2023 11

Clustering is a fundamental task in data science with wide-ranging applications. In $k$-medoids clustering, cluster centers must be actual datapoints and arbitrary distance metrics may be used; these features allow for g…

The K-modes algorithm for clustering

2013-04-24 · Miguel Á. Carreira-Perpiñán, Weiran Wang

Many clustering algorithms exist that estimate a cluster centroid, such as K-means, K-medoids or mean-shift, but no algorithm seems to exist that clusters data by returning exactly K meaningful modes. We propose a natura…

Clustering valid

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

2020-12-01 · NeurIPS 2020 12 · Mo Tiwari, Martin J. Zhang, James Mayclin, Sebastian Thrun 외

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 supports arbitrary distance metrics, which…

Clustering Multi-Armed Bandits

BanditPAM: Almost Linear Time $k$-Medoids Clustering via Multi-Armed Bandits

2020-06-11 · Mo Tiwari, Martin Jinye Zhang, James Mayclin, Sebastian Thrun 외

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, wh…

Clustering Multi-Armed Bandits

Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms

2018-10-12 · Erich Schubert, Peter J. Rousseeuw

Clustering non-Euclidean data is difficult, and one of the most used algorithms besides hierarchical clustering is the popular algorithm Partitioning Around Medoids (PAM), also simply referred to as k-medoids. In Euclide…

Clustering