Source-linked AI summary
Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms
Erich Schubert, Peter J. Rousseeuw
TL;DR
PAM supports clustering with arbitrary dissimilarities but is computationally expensive, especially as the number of medoids grows. The paper accelerates SWAP through caching and multiple swaps, then extends the benefits to initialization and related algorithms. The reported improvements include an O(k)-fold speedup and benefits for larger-k clustering, while retaining a distance-matrix scope boundary.
Problem
PAM supports arbitrary dissimilarities, but its SWAP refinement and distance-matrix requirements make clustering costly, particularly for large k and large datasets.
Method
The paper changes SWAP loop organization to cache partial results, executes multiple medoid swaps per iteration, and uses linear approximative BUILD initialization.
Results
An O(k)-fold SWAP speedup is reported, with the modifications also benefiting CLARA, CLARANS, and related PAM-based methods.
Takeaways & Limitations
The faster refinement enables PAM use on larger datasets and at larger k, within the requirement that the distance matrix be computable and stored.
Takeaways & Limitations
The method still requires a precomputed distance matrix, requiring O(n^2) time and memory and limiting direct use on big data.
Abstract
from arXiv · showhide
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 Euclidean geometry the mean-as used in k-means-is a good estimator for the cluster center, but this does not hold for arbitrary dissimilarities. PAM uses the medoid instead, the object with the smallest dissimilarity to all others in the cluster. This notion of centrality can be used with any (dis-)similarity, and thus is of high relevance to many domains such as biology that require the use of Jaccard, Gower, or more complex distances. A key issue with PAM is its high run time cost. We propose modifications to the PAM algorithm to achieve an O(k)-fold speedup in the second SWAP phase of the algorithm, but will still find the same results as the original PAM algorithm. If we slightly relax the choice of swaps performed (at comparable quality), we can further accelerate the algorithm by performing up to k swaps in each iteration. With the substantially faster SWAP, we can now also explore alternative strategies for choosing the initial medoids. We also show how the CLARA and CLARANS algorithms benefit from these modifications. It can easily be combined with earlier approaches to use PAM and CLARA on big data (some of which use PAM as a subroutine, hence can immediately benefit from these improvements), where the performance with high k becomes increasingly important. In experiments on real data with k=100, we observed a 200-fold speedup compared to the original PAM SWAP algorithm, making PAM applicable to larger data sets as long as we can afford to compute a distance matrix, and in particular to higher k (at k=2, the new SWAP was only 1.5 times faster, as the speedup is expected to increase with k).
1 Introduction
Clustering methods differ in their notions of cluster and center. k-medoids uses data objects as representatives, enabling arbitrary dissimilarities and input domains where means are unsuitable.
- Clustering partitions data so objects within clusters are more similar than objects in different clusters.
- k-means iteratively assigns objects to nearest means and recomputes those means while optimizing sum-of-squared errors.
- k-medoids replaces means with representative data objects and uses total deviation, the sum of dissimilarities to assigned medoids.
- For squared Euclidean distances, means are optimal for fixed assignments, whereas other distances may require medians, solve the Weber problem, or lack closed-form centers.
- Medoid-based clustering does not require a metric, can maximize similarities, and underlies PAM, a widely known method for finding good partitions.
2 Partitioning Around Medoids (PAM)
PAM combines BUILD initialization with iterative SWAP refinement over medoid replacements, but its distance-matrix and search costs make large datasets and large k challenging.
- PAM requires a dissimilarity matrix that uses O(n^2) memory and can require O(n^2d) computation for common distances.
- BUILD initialization: BUILD selects k medoids greedily, first minimizing total distance and then repeatedly choosing the point producing the largest reduction in total deviation.
- SWAP refinement: SWAP evaluates k(n −k) medoid/non-medoid replacements, applies the best improving swap, and repeats until no improvement remains.
- SWAP refinement: Each SWAP iteration runs in O(k(n −k)^2) when cached nearest and second-nearest medoid distances support efficient change evaluation.
- Related methods: CLARA repeatedly runs PAM on subsamples and assigns remaining objects afterward, while CLARANS performs randomized greedy exploration of medoid-swap edges.
- Scalability: The distance-matrix requirement and quadratic memory make PAM unsuitable for big data, motivating approximations and parallel or distributed variants.
3 Finding the Best Swap
The paper accelerates PAM’s SWAP phase by caching shared computations and reorganizing loops, then extends the approach to multiple swaps and faster initialization. These changes also transfer to CLARA, while the multiple-swap variant trades exact equivalence for comparable quality.
- Original SWAP: Caching nearest and second-nearest medoid distances avoids recomputing assignments when evaluating each candidate swap.The per-object change can immediately be zero when the object remains assigned to its current medoid.
- FastPAM1: FastPAM1 moves medoid loops inward and exploits a case in Equation 4 that does not depend on the current medoid, removing redundant work.Under a roughly balanced cluster-size assumption, the expected SWAP cost falls to O((n −k)^2) from O(k(n −k)^2), with typical speedup on the order of O(k).
- FastPAM2: FastPAM2 stores the best candidate swap for each medoid and can execute up to k swaps in one iteration.Strict mode executes apparently independent swaps, whereas greedy mode executes any swap that still improves TD.
- FastPAM2: FastPAM2 provides measurable additional speedup but no longer guarantees exactly the same result as PAM, although experiments often found slightly better results.The authors characterize both methods as steepest-descent strategies with equivalent expected quality.
- Initialization and integration: LAB reduces BUILD initialization to O(kn), and FastPAM combines LAB with FastPAM2; LAB performed significantly better than k-means++ in the reported experiments.LAB samples 10 + ⌈√n⌉ non-medoid points before choosing each medoid and repeats sampling k times.
4 Experiments
The experiments show that FastPAM substantially reduces PAM's SWAP runtime, with larger gains as k increases, while FastPAM2 and related FastCLARA/FastCLARANS variants offer speed-quality trade-offs. The approach remains constrained by quadratic distance-matrix requirements, although it enables practical clustering when that matrix is affordable.
- PAM runtime: O(k) speedup is theoretically expected for FastPAM1, with low cache-maintenance overhead making the gain immediately measurable.The experiments were designed to verify that constant factors do not obscure the theoretical improvement.
- Initialization and iterations: FastPAM2's multiple-swap strategy substantially reduces iterations, enabling cheaper but initially worse LAB or k-means++ initialization to become viable.k-means++ required roughly 2–4× as many iterations as BUILD, while FastPAM2 can perform up to k swaps per iteration.
- Quality: FastPAM2 produced results comparable to PAM, while CLARA was considerably worse; larger CLARA samples improved quality only modestly for large k.FastCLARA matched CLARA x2 quality while being much faster, and FastCLARANS was slightly better than CLARANS and considerably faster.
- Additional data: On Optical Digits, FastPAM again showed O(k) speedup, reaching about 1000× at k = 200 but about 10× at the more reasonable k = 10.FastCLARA and FastCLARANS again outperformed their non-fast versions when some quality loss was acceptable.
- Scalability: FastPAM requires O(n^2) time and memory for the complete distance matrix, limiting its direct suitability for big data.When the matrix is affordable, FastPAM added about 30% of matrix-computation time at k = 10 and about the same time as matrix computation at k = 100; FastCLARA scales linearly in n but was about 10% worse in quality in these experiments.
5 Conclusions
The paper accelerates PAM through cached SWAP computations and multiple swaps per iteration, and introduces LAB initialization as a linear-time BUILD approximation. These improvements also benefit PAM-based methods such as CLARA and CLARANS and are available in major clustering tools.
- Cached partial results avoid recomputation and typically make PAM O(k) times faster.The speedup comes from changing loop nesting to enable caching.
- LAB initialization approximates PAM BUILD in linear time, making cheaper initialization worthwhile with the faster refinement procedure.LAB is proposed as a linear-time approximation of the original PAM BUILD algorithm.
- PAM-based methods including CLARA, CLARANS, and parallel or distributed variants can benefit from the improvements.CLARA uses PAM as a subroutine, while CLARANS uses a similar swapping method that can be modified accordingly.
- The methods are implemented in ELKI and FastPAM2 is included in the R cluster package.LAB, FastCLARA, and FastCLARANS are implemented in ELKI but not yet in R.