K-medoids · Lablypedia

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:
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_{best}$ and $o_{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 (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:
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

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})$ , 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 (\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.

5 more chapters are free with a Lably account.

Visualization of the medoid-based clustering process

Purpose

Visualization of medoid-based clustering can be helpful when trying to understand how medoid-based clustering work. Studies have shown that people learn better with visual information. In medoid-based clustering, the medoid is the center of the cluster. This is different from k-means clustering, where the center isn't a real data point, but instead can lie between data points. We use the medoid to group “clusters” of data, which is obtained by finding the element with minimal average dissimilarity to all other objects in the cluster. Although the visualization example used utilizes k-medoids clustering, the visualization can be applied to k-means clustering as well by swapping out average dissimilarity with the mean of the dataset being used.

Visualization using one-dimensional data

Distance matrix

A distance matrix is required for medoid-based clustering, which is generated using Jaccard Dissimilarity (which is 1 - the Jaccard Index). This distance matrix is used to calculate the distance between two points on a one-dimensional graph. The above image shows an example of a Jaccard Dissimilarity graph.

Clustering

Step 1

Medoid-based clustering is used to find clusters within a dataset. An initial one-dimensional dataset which contains clusters that need to be discovered is used for the process of medoid-based clustering. The image below depicts twelve different objects in the data set with varying x-positions.

Step 2

K random points are chosen to be the initial centers. The value chosen for K is known as the K-value. In the image below, 3 has been chosen as the K-value. The process for finding the optimal K-value will be discussed in step 7.

Step 3

Each non-center object is assigned to its nearest center. This is done using a distance matrix. The lower the dissimilarity, the closer the points are. In the image below, there are 5 objects in cluster 1, 3 in cluster 2, and 4 in cluster 3.

Step 4

The new center for each cluster is found by finding the object whose average dissimilarity to all other objects in the cluster is minimal. The center selected during this step is called the medoid. The image below shows the results of medoid selection.

Step 5

Steps 3-4 are repeated until the centers no longer move, as in the images below.

Step 6

The final clusters are obtained when the centers no longer move between steps. The image below shows what a final cluster can look like.

Step 7

The variation is added up within each cluster to see how accurate the centers are. By running this test with different K-values, an "elbow" of the variation graph can be acquired, where the graph's variation levels out. The "elbow" of the graph is the optimal K-value for the dataset.

Comparison to k-means clustering

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 known as the centroid). 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.

Despite these advantages, the results of k-medoids are subject to high variability. Since the first step when executing the algorithm is to select k medoids at random, this might lead to different results. k-medoids is also not suitable for clustering objects that are not spherical and may work inefficiently when dealing with large datasets depending on how it is implemented. Meanwhile, k-means is suitable for well-distributed and isotropic clusters and can handle larger datasets. Similarly to k-medoids, however, k-means also uses random initial points which varies the results the algorithm finds.

K-medoids in high dimensions

A common problem with k-medoids clustering and other medoid-based clustering algorithms is the "curse of dimensionality," in which the data points contain too many dimensions or features. As dimensions are added to the data, the distance between them becomes sparse, and it becomes difficult to characterize clustering by Euclidean distance alone. As a result, distance based similarity measures converge to a constant and we have a characterization of distance between points which may not be reflect our data set in meaningful ways.

One way to mitigate the effects of the curse of dimensionality is by using spectral clustering. Spectral clustering achieves a more appropriate analysis by reducing the dimensionality of then data using principal component analysis, projecting the data points into the lower dimensional subspace, and then running the chosen clustering algorithm as before. One thing to note, however, is that as with any dimension reduction we lose information, so it must be weighed against clustering in advanced how much reduction is necessary before too much data is lost.

High dimensionality doesn't only affect distance metrics however, as the time complexity also increases with the number of features. k-medoids is sensitive to initial choice of medoids, as they are usually selected randomly. Depending on how such medoids are initialized, k-medoids may converge to different local optima, resulting in different clusters and quality measures, meaning k-medoids might need to run multiple times with different initializations, resulting in a much higher run time. One way to counterbalance this is to use k-medoids++, an alternative to k-medoids similar to its k-means counterpart, k-means++ which chooses initial medoids to begin with based on a probability distribution, as a sort of "informed randomness" or educated guess if you will. If such medoids are chosen with this rationale, the result is an improved runtime and better performance in clustering. The k-medoids++ algorithm is described as follows:

The initial medoid is chosen randomly among all of the spatial points.
For each spatial point 𝑝, compute the distance between 𝑝 and the nearest medoids which is termed as D(𝑝) and sum all the distances to 𝑆 .
The next medoid is determined by using weighted probability distribution. Specifically, a random number 𝑅 between zero and the summed distance 𝑆 is chosen and the corresponding spatial point is the next medoid.
Step (2) and Step (3) are repeated until 𝑘 medoids have been chosen.

Now that we have appropriate first selections for medoids, the normal variation of k-medoids can be run.

Packages

Several software packages provide implementations of k-medoids clustering algorithms. These implementations vary in their algorithmic approaches and computational efficiency.

scikit-learn-extra

The scikit-learn-extra package includes a KMedoids class that implements k-medoids clustering with a Scikit-learn compatible interface. It offers two algorithm choices:

The original PAM algorithm
An alternate optimization method that is faster but less accurate

Parameters include:

n_clusters: The number of clusters to form (default is 8)
metric: The distance metric to use (default is Euclidean distance)
method: The algorithm to use ('pam' or 'alternate')
init: The medoid initialization method (options include 'random', 'heuristic', 'k-medoids++', and 'build')
max_iter: The maximum number of iterations (default is 300)

Example Python usage:

<span id="mwAXc"></span><span class="kn" id="mwAXg">from</span><span class="w" id="mwAXk"> </span><span class="nn" id="mwAXo">sklearn_extra.cluster</span><span class="w" id="mwAXs"> </span><span class="kn" id="mwAXw">import</span> <span class="n" id="mwAX0">KMedoids</span> <span class="n" id="mwAX4">kmedoids</span> <span class="o" id="mwAX8">=</span> <span class="n" id="mwAYA">KMedoids</span><span class="p" id="mwAYE">(</span><span class="n" id="mwAYI">n_clusters</span><span class="o" id="mwAYM">=</span><span class="mi" id="mwAYQ">2</span><span class="p" id="mwAYU">,</span> <span class="n" id="mwAYY">method</span><span class="o" id="mwAYc">=</span><span class="s2" id="mwAYg">"pam"</span><span class="p" id="mwAYk">)</span><span class="o" id="mwAYo">.</span><span class="n" id="mwAYs">fit</span><span class="p" id="mwAYw">(</span><span class="n" id="mwAY0">X</span><span class="p" id="mwAY4">)</span> <span class="nb" id="mwAY8">print</span><span class="p" id="mwAZA">(</span><span class="n" id="mwAZE">kmedoids</span><span class="o" id="mwAZI">.</span><span class="n" id="mwAZM">labels_</span><span class="p" id="mwAZQ">)</span>

kmedoids

The Python kmedoids package provides optimized implementations of PAM and related algorithms:

FasterPAM: An improved version with better time complexity
FastPAM1: An earlier optimization of PAM
DynMSC: A method for automatic cluster number selection

This package expects precomputed dissimilarity matrices and includes silhouette-based methods for evaluating clusters.