k-medoids

The name was coined by Leonard Kaufman and Peter J. Rousseeuw with their PAM (Partitioning Around Medoids) algorithm.

[1] Both the k-means and k-medoids algorithms are partitional (breaking the dataset up into groups) and attempt to minimize the distance between points labeled to be in a cluster and a point designated as the center of that cluster.

In contrast to the k-means algorithm, k-medoids chooses actual data points as centers (medoids or exemplars), and thereby allows for greater interpretability of the cluster centers than in k-means, where the center of a cluster is not necessarily one of the input data points (it is the average between the points in the cluster).

Furthermore, k-medoids can be used with arbitrary dissimilarity measures, whereas k-means generally requires Euclidean distance for efficient solutions.

, by splitting the cost change into three parts such that computations can be shared or avoided (FastPAM).

The runtime can further be reduced by eagerly performing swaps (FasterPAM),[2] at which point a random initialization becomes a viable alternative to BUILD.

Algorithms other than PAM have also been suggested in the literature, including the following Voronoi iteration method known as the "Alternating" heuristic in literature, as it alternates between two optimization steps:[3][4][5] k-means-style Voronoi iteration tends to produce worse results, and exhibit "erratic behavior".

[6]: 957  Because it does not allow re-assigning points to other clusters while updating means it only explores a smaller search space.

It can be shown that even in simple cases this heuristic finds inferior solutions the swap based methods can solve.

CLARANS works on the entire data set, but only explores a subset of the possible swaps of medoids and non-medoids using sampling.

BanditPAM uses the concept of multi-armed bandits to choose candidate swaps instead of uniform sampling as in CLARANS.