K-medoids

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. In general, the k-medoids problem is NP-hard to solve exactly.