K-medoids

The k-medoids problem is a clustering problem similar to k-means. 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. Because k-medoids minimizes a sum of pairwise dissimilarities instead of a sum of squared Euclidean distances, it is more robust to noise and outliers than k-means.

k-medoids is a classical partitioning technique of clustering that splits the data set of n objects into k clusters, where the number k of clusters assumed known a priori (which implies that the programmer must specify k before the execution of a k-medoids algorithm). The "goodness" of the given value of k can be assessed with methods such as the silhouette method.

The medoid of a cluster is defined as the object in the cluster whose average dissimilarity to all the objects in the cluster is minimal, that is, it is a most centrally located point in the cluster.

The current state-of-the-art algorithm for the k-medoids problem is BanditPAM. BanditPAM builds upon previous work such as Partitioning Around Medoids (PAM), which was proposed in 1987 for the work with $l_{1}$ norm and other distances.

Algorithms

PAM choosing initial medoids, then iterating to convergence for k=3 clusters, visualized with ELKI.

In general, the k-medoids problem is NP-hard to solve exactly. As such, many heuristic solutions exist.

Partitioning Around Medoids (PAM)

Until recently, the partitioning around medoids (PAM) algorithm was a widely used k-medoid clustering algorithm (it has since been superseded by BanditPAM). PAM uses a greedy search which may not find the optimum solution, but it is faster than exhaustive search. It works as follows:

1. (BUILD) Initialize: greedily select k of the n data points as the medoids to minimize the cost
2. Associate each data point to the closest medoid.
3. (SWAP) While the cost of the configuration decreases:
   1. For each medoid m, and for each non-medoid data point o:
      1. Consider the swap of m and o, and compute the cost change
      2. If the cost change is the current best, remember this m and o combination
   2. Perform the best swap of $m_{\text{best}}$ and $o_{\text{best}}$, if it decreases the cost function. Otherwise, the algorithm terminates.

The runtime complexity of the original PAM algorithm per iteration of (3) is $O(k(n-k)^{2})$, by only computing the change in cost. A naive implementation recomputing the entire cost function every time will be in $O(n^{2}k^{2})$. This runtime can be further reduced to $O(n^{2})$, by splitting the cost change into three parts such that computations can be shared or avoided.

BanditPAM

BanditPAM is a randomized algorithm that matches PAM in clustering quality. Crucially, however, BanditPAM reduces the dependence in dataset size from $O(n^{2})$ to $O(n\log n)$. BanditPAM tracks PAM's optimization trajectory in the BUILD and SWAP steps, but estimates the changes in losses at each step instead of computing these quantities exactly. In each each step of the algorithm, BanditPAM formulates finding the best new medoids (in the BUILD step) or the best medoid-nonmedoid pair (in the SWAP step) as multi-armed bandit problems. As BanditPAM matches PAM in clustering quality but is much faster, it is considered state-of-the-art.

Other Algorithms

Algorithms other than PAM and BanditPAM have also been suggested in the literature, including the following Voronoi iteration method:

1. Select initial medoids randomly
2. Iterate while the cost decreases:
   1. In each cluster, make the point that minimizes the sum of distances within the cluster the medoid
   2. Reassign each point to the cluster defined by the closest medoid determined in the previous step.

However, k-means-style Voronoi iteration finds worse results, as it does not allow reassigning points to other clusters while changing means, and thus only explores a smaller search space.

Other approximate algorithms such as CLARA and CLARANS trade optimality for runtime. CLARA applies PAM on multiple subsamples, keeping the best result. CLARANS works on the entire data set, but only explores a subset of the possible swaps of medoids and non-medoids using sampling.

Software

• BanditPAM is the state-of-the-art algorithm for the k-medoids problem with an open-source implementation. It is written in C++ for performance, and can be called from both C++ and Python.
• ELKI includes several k-medoid variants, including a Voronoi-iteration k-medoids, the original PAM algorithm, Reynolds' improvements, and the O(n²) FastPAM algorithm, CLARA, CLARANS, FastCLARA and FastCLARANS.
• Julia contains a k-medoid implementation of the k-means style algorithm (faster, but much worse result quality) in the JuliaStats/Clustering.jl package.
• KNIME includes a k-medoid implementation supporting a variety of efficient matrix distance measures, as well as a number of native (and integrated third-party) k-means implementations
• R contains PAM in the "cluster" package, including some of the FastPAM improvements via the pamonce=5 option.
• RapidMiner has an operator named KMedoids, but it does not implement the KMedoids algorithm correctly. Instead, it is a k-means variant, that substitutes the mean with the closest data point (which is not the medoid).
• MATLAB implements PAM, CLARA, and two other algorithms to solve the k-medoid clustering problem.