The k-medoids method is used in unsupervised learning. It is a classical partitioning technique of clustering that splits a data set of n objects into k clusters, where the k number of clusters is assumed to be 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 name of the clustering method was coined by Leonard Kaufman and Peter J. Rousseeuw with their PAM (Partitioning Around Medoids) algorithm. The medoid of a cluster is defined as the object in the cluster whose sum (and, equivalently, the average) of dissimilarities to all the objects in the cluster is minimal. That is, it is the most centrally located point in the cluster. Unlike certain objects used by other algorithms, the medoid is an actual point in the cluster. As every point is typically assigned to its nearest medoid, the k-medoids method (like k-means clustering) does not work well if clusters vary significantly in diameter. If clusters vary in diameter or shape, other clustering methods, such as Gaussian mixture modeling or density-based clustering, may work better.
Algorithms
In general, the k-medoids problem is NP-hard to solve exactly. As such, multiple heuristics to optimize this problem exist.
Partitioning around medoids (PAM) PAM uses a greedy search method which may not find the optimum solution, but is faster than exhaustive search. It works as follows:
(BUILD) Initialize: greedily select k of the n data points as the medoids to minimize the cost Associate each data point to the closest medoid. (SWAP) While the cost of the configuration decreases: For each medoid m, and for each non-medoid data point o: Consider the swap of m and o, and compute the cost change If the cost change is the current best, remember this m and o combination Perform the best swap of m best {\displaystyle m_{\text{best}}} and o best {\displaystyle 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 ) {\displaystyle 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 ) {\displaystyle O(n^{2}k^{2})} . This runtime can be further reduced to O ( n 2 ) {\displaystyle O(n^{2})} , 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), at which point a random initialization becomes a viable alternative to BUILD.
Alternating optimization 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:
Select initial medoids randomly Iterate while the cost decreases: In each cluster, make the point that minimizes the sum of distances within the cluster the medoid Reassign each point to the cluster defined by the closest medoid determined in the previous step k-means-style Voronoi iteration tends to produce worse results, and exhibits "erratic behavior". Because it does not allow reassigning 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 as compared to swap based methods.
Hierarchical clustering Multiple variants of hierarchical clustering with a "medoid linkage" have been proposed. The Minimum Sum linkage criterion directly uses the objective of medoids, but the Minimum Sum Increase linkage was shown to produce better results (similar to how Ward linkage uses the increase in squared error). Earlier approaches simply used the distance of the cluster medoids of the previous medoids as linkage measure, but this tends to result in worse solutions, as the distance of two medoids does not ensure there exists a good medoid for the combination. These approaches have a runtime complexity of O ( n 3 ) {\displaystyle O(n^{3})} , and when the dendrogram is cut at a particular number of clusters k, the results will typically be worse than the results found by PAM. Hence these methods are primarily of interest when a hierarchical tree structure is desired.
Other algorithms Other approximate algorithms such as CLARA and CLARANS trade quality for runtime. CLARA applies PAM on multiple subsamples, keeping the best result. By setting the sample size to O ( n ) {\displaystyle O({\sqrt {n}})} , a linear runtime (just as to k-means) can be achieved. 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.
Visualization of the medoid-based clustering process
… excerpt ends here. Continue reading the full article.
