K-medoids

K-medoids is a family of partitioning clustering methods used in unsupervised learning. It splits a data set of n objects into k clusters, where k is chosen in advance, and it picks as the centre of each cluster a medoid, the actual object whose total dissimilarity to every other object in the cluster is smallest. Because the centre is a real data point rather than an average, the method works with any dissimilarity measure and is less distorted by outliers than k-means. The name was coined by Leonard Kaufman and Peter J. Rousseeuw for their Partitioning Around Medoids (PAM) algorithm, which builds an initial set of medoids greedily and then swaps medoids with non-medoids while the cost falls. Solving the problem exactly is NP-hard, so practical variants such as alternating optimisation, CLARA, CLARANS, FastPAM and BanditPAM trade some solution quality for speed. Like k-means it copes poorly when clusters differ greatly in diameter or shape.