k-medoids

The k-medoids method is a classical partitioning technique of clustering that splits a data set of n objects into k clusters, where the number k 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 a 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 method (similar to k-means) does not work well if clusters vary significantly in diameter. If clusters vary in diameter or shape, other clustering method such as Gaussian mixture modeling or density-based clustering may work better.