kmedoid

K-medoids, also known as k-medoids clustering, is a partitioning clustering algorithm that partitions a dataset into k clusters by minimizing the sum of dissimilarities between points and their cluster medoids. A medoid is the object in a cluster whose average dissimilarity to all other objects in the cluster is minimal; in other words, it is the most centrally located observation in the cluster. Unlike k-means, which uses centroids that may not correspond to actual data points, k-medoids uses real observations as centers, making it more robust to outliers and compatible with arbitrary dissimilarity measures.

A canonical approach is Partitioning Around Medoids (PAM). The algorithm initializes by selecting k medoids. It then alternates two steps: assignment, where each point is assigned to the nearest medoid; and update, where within each cluster the point that minimizes the sum of distances to all other points in that cluster is chosen as the new medoid. The process repeats until no change or until convergence. The objective is to minimize the total sum of dissimilarities between points and their medoids.

Variants such as CLARA (Clustering Large Applications) and CLARANS (Clustering Large Applications with Nearest neighbor Search) extend k-medoids to larger datasets. CLARA applies PAM to subsamples, reducing computation, while CLARANS uses a randomized search to explore medoid changes in the solution space.

Properties and use cases: k-medoids can use any dissimilarity metric, including non-Euclidean or categorical distances, enabling clustering in spaces where k-means would fail. It tends to be more computationally intensive than k-means and can be memory-intensive for large datasets, particularly with a full dissimilarity matrix. It is widely used for robust clustering tasks, outlier-prone data, and domains requiring interpretability since medoids correspond to actual observations.