Medoid

A medoid is a representative object within a cluster that minimizes dissimilarity to all other objects in the same cluster. Formally, given a cluster C contained in a dataset X and a distance function d, the medoid m is defined as m = argmin_{x ∈ C} ∑_{y ∈ C} d(x, y). Unlike the centroid, which is the mean position and may not correspond to any actual data point, the medoid is always one of the observed data points and thus easily interpretable as a real item from the dataset.

Medoids are central to the k-medoids family of clustering methods. In k-medoids clustering, the goal is to partition data into k clusters by choosing k medoids and assigning each point to the nearest medoid, with the objective of minimizing the total within-cluster dissimilarity. This approach is often more robust to outliers than k-means, since it uses actual data points as centers and does not rely on averaging.

Algorithms used to compute medoids include the classical PAM (Partitioning Around Medoids), which iteratively swaps medoids with non-medoids to reduce the total cost. PAM can be computationally intensive for large datasets. Scalable alternatives include CLARA (Clustering Large Applications) that applies PAM to multiple samples, and CLARANS (Clustering Large Applications based on RANdomized Search), which performs a randomized search over medoid configurations.

Distance metrics are central to the medoid concept; any metric can be used, including Euclidean, Manhattan, cosine, or domain-specific dissimilarities (such as Gower for mixed data). Medoids are particularly suitable when a meaningful mean is not defined or when interpretability as an actual data point is desirable.