K-medoids


The -medoids or partitioning around medoids algorithm is a clustering algorithm reminiscent of the -means algorithm. Both the -means and -medoids algorithms are partitional and both 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 -means algorithm, -medoids chooses data points as centers and can be used with arbitrary distances, while in -means the centre of a cluster is not necessarily one of the input data points. The PAM method was proposed in 1987 for the work with norm and other distances.
-medoid is a classical partitioning technique of clustering, which clusters the data set of objects into clusters, with the number of clusters assumed known a priori. The "goodness" of the given value of can be assessed with methods such as the silhouette method.
It is more robust to noise and outliers as compared to -means because it minimizes a sum of pairwise dissimilarities instead of a sum of squared Euclidean distances.
A medoid can be defined as the object of a 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.

Algorithms

The most common realisation of -medoid clustering is the partitioning around medoids algorithm. PAM uses a greedy search which may not find the optimum solution, but it is faster than exhaustive search. It works as follows:
  1. Initialize: greedily select of the data points as the medoids to minimize the cost
  2. Associate each data point to the closest medoid.
  3. While the cost of the configuration decreases:
  4. # For each medoid, and for each non-medoid data point :
  5. ## Consider the swap of and, and compute the cost change
  6. ## If the cost change is the current best, remember this m and o combination
  7. #Perform the best swap of and, if it decreases the cost function. Otherwise, the algorithm terminates.
The runtime complexity of the original PAM algorithm per iteration of is, by only computing the change in cost. A naive implementation recomputing the entire cost function every time will be in. This runtime can be further reduced to, by splitting the cost change into three parts such that computations can be shared or avoided.
Algorithms other than PAM have also been suggested in the literature, including the following Voronoi iteration method:
  1. Select initial medoids randomly
  2. Iterate while the cost decreases:
  3. # In each cluster, make the point that minimizes the sum of distances within the cluster the medoid
  4. # 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.
The approximate algorithms 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