Expand description

k-Medoids Clustering with the FasterPAM Algorithm

For details on the implemented FasterPAM algorithm, please see:

Erich Schubert, Peter J. Rousseeuw
Fast and Eager k-Medoids Clustering:
O(k) Runtime Improvement of the PAM, CLARA, and CLARANS Algorithms

Information Systems (101), 2021, 101804
https://doi.org/10.1016/j.is.2021.101804 (open access)

Erich Schubert, Peter J. Rousseeuw:
Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms
In: 12th International Conference on Similarity Search and Applications (SISAP 2019), 171-187.
Preprint: https://arxiv.org/abs/1810.05691

This is a port of the original Java code from ELKI to Rust. But it does not include all functionality in the original benchmarks.

If you use this in scientific work, please consider citing above articles.


Given a dissimilarity matrix of size 4 x 4, use:

let data = ndarray::arr2(&[[0,1,2,3],[1,0,4,5],[2,4,0,6],[3,5,6,0]]);
let mut meds = kmedoids::random_initialization(4, 2, &mut rand::thread_rng());
let (loss, assi, n_iter, n_swap): (f64, _, _, _) = kmedoids::fasterpam(&data, &mut meds, 100);
println!("Loss is: {}", loss);


pub use crate::arrayadapter::ArrayAdapter;


Adapter trait for accessing different types of arrays.


Run the Alternating algorithm, a k-means-style alternate optimization.

Run the FasterPAM algorithm.

Run the FastPAM1 algorithm, which yields the same results as the original PAM.

Use the first objects as initial medoids.

Run the original PAM algorithm (BUILD and SWAP).

Run the original PAM BUILD algorithm.

Run the original PAM SWAP algorithm (no BUILD, but given initial medoids).

Run the FasterPAM algorithm (parallel version).

Compute the Silhouette of a strict partitional clustering (parallel implementation).

Run the FasterPAM algorithm with additional randomization.

Random initialization (requires the rand crate)

Compute the Silhouette of a strict partitional clustering.