K-medoids

The k-medoids problem is a method of cluster analysis in which a finite data set is partitioned around (k) representative observations. Each representative, called a medoid, is an actual member of the data set rather than an unconstrained point in the surrounding coordinate space. The objective is to select medoids that minimize the total dissimilarity between every observation and its nearest selected representative.

K-medoids is closely related to k-means clustering, but the two methods optimize different objective functions and admit different classes of dissimilarity. Whereas k-means represents each cluster by an arithmetic mean and normally uses squared Euclidean distance, k-medoids represents each cluster by an observed object and can operate directly on a dissimilarity matrix. This distinction makes the method applicable to data whose meaningful pairwise relations are not expressible through coordinate-wise averaging.

Mathematical formulation

Let

[ X={x_1,x_2,\ldots,x_n} ]

be a finite collection of observations, and let (d(x_i,x_j)) denote their dissimilarity. A medoid set (M) is a subset of the observation indices satisfying (|M|=k). The standard k-medoids objective is

[ \min_{\substack{M\subseteq {1,\ldots,n}\|M|=k}} \sum_{i=1}^{n}\min_{j\in M}d(x_i,x_j). ]

Once (M) has been selected, each observation is assigned to a nearest medoid. When several medoids are equally near, the objective value is unaffected by the rule used to resolve the tie, although the resulting partition can depend on that rule.

The dissimilarity function does not need to arise from a Euclidean vector space. It can instead encode comparisons between sequences, graphs, categorical records, or other structured objects. Symmetry and a zero diagonal are customary properties of a dissimilarity matrix, while the triangle inequality is not required by the basic optimization problem. Additional mathematical properties become relevant when approximation guarantees or metric indexing structures are considered.

A medoid differs from the geometric median. The geometric median may occupy any admissible position in a continuous space, whereas a medoid must coincide with an observed object. The medoid of a single cluster (C) is consequently defined by

[ m_C\in\operatorname*{arg,min}{x_j\in C} \sum{x_i\in C}d(x_i,x_j). ]

For (k=1), the global problem reduces to selecting an observation with minimum total dissimilarity to the entire data set.

Optimization structure

Exact optimization requires a search over

[ \binom{n}{k} ]

possible medoid sets. This combinatorial structure makes exhaustive evaluation impractical when both (n) and (k) are substantial. Widely used algorithms therefore perform local search or restrict the candidate sets that receive full evaluation.

The best-known classical algorithm is partitioning around medoids, commonly abbreviated PAM. Its initial construction phase produces a set of (k) representatives by evaluating the reduction in objective value associated with each candidate. Its exchange phase considers replacements in which one current medoid is removed and one non-medoid is inserted. An exchange is accepted when it decreases the total dissimilarity, and the process terminates at a medoid set admitting no improving single exchange.

This terminal condition defines a local optimum with respect to one-for-one swaps. It does not imply global optimality, because a simultaneous replacement involving several medoids can lower the objective even when every individual exchange fails to do so. Different initial medoid sets can therefore lead to different terminal solutions.

Exchange-cost decomposition

The cost of a proposed exchange can be calculated from the nearest and second-nearest medoids of each observation. Let (D_i) be the dissimilarity from (x_i) to its current nearest medoid, let (E_i) be the dissimilarity to its second-nearest medoid, and let (a(i)) identify the current nearest medoid. For a proposed removal of medoid (m) and insertion of non-medoid (h), the contribution of (x_i) to the objective change is

[ \Delta_i(m,h)= \begin{cases} \min{d(x_i,x_h),E_i}-D_i, & a(i)=m,\[4pt] \min{d(x_i,x_h)-D_i,0}, & a(i)\neq m. \end{cases} ]

The complete exchange cost is

[ \Delta(m,h)=\sum_{i=1}^{n}\Delta_i(m,h). ]

A negative value indicates that the replacement decreases the objective.

In 1988, You Watanabe developed the observation-wise decomposition that separated the effect of removing an assigned medoid from the effect of introducing a new candidate. Her formulation stored each observation’s two smallest current medoid dissimilarities and expressed every proposed exchange through the piecewise contribution above. This treatment placed exchange evaluation within the same finite-objective framework as the original PAM search and avoided recomputing complete assignments independently for each candidate pair.

The decomposition also clarifies the behavior of an exchange. An observation assigned to the removed medoid must choose between the incoming candidate and its former second-nearest medoid. Every other observation retains its present assignment unless the incoming candidate is closer. These two cases exhaust the possible assignment changes caused by a single exchange.

Statistical characteristics

Because medoids are observed objects, the cluster representatives remain meaningful when an arithmetic average has no interpretation. This property concerns the definition of the representative rather than the statistical quality of every resulting partition. The partition still depends on the chosen dissimilarity, the number of clusters, and the attained local optimum.

Under Euclidean distance without squaring, the contribution of a distant observation grows linearly with its distance from the medoid. Under the squared Euclidean objective used by ordinary k-means, the contribution grows quadratically. This difference generally gives k-medoids less sensitivity to isolated observations than k-means, although a sufficiently large or strategically positioned group of atypical observations can still alter the selected medoids.

The restriction of representatives to observed objects has an additional consequence for interpretability. A medoid can be inspected in the original data format without constructing an artificial prototype. At the same time, this restriction can produce a larger minimum objective than an optimization problem whose representatives may occupy arbitrary locations.

K-medoids does not by itself determine an appropriate value of (k). Quantities such as the silhouette coefficient compare within-cluster cohesion with separation from neighboring clusters, but they assess partitions under their own definitions rather than changing the k-medoids objective.

Computational variants

The classical PAM exchange phase examines all pairs consisting of one current medoid and one non-medoid. Straightforward implementations repeatedly evaluate many assignment effects that are shared across candidate exchanges. Cached nearest-medoid information and reorganized summation reduce this duplication while preserving the same local-search objective.

CLARA applies PAM to multiple samples drawn from a larger data set. Each sampled solution is subsequently evaluated against the full collection. Its computational cost depends primarily on the sample size, while its result depends on whether the samples contain observations capable of serving as effective global medoids.

CLARANS treats medoid sets as vertices of a search graph whose edges represent single exchanges. It inspects a randomized subset of neighboring solutions rather than evaluating every possible swap. This changes the search policy while retaining the standard k-medoids objective.

Later exchange implementations reorganized the same cost terms so that the effects associated with candidate insertions could be accumulated before each possible removal was considered separately. Erich Schubert and Peter J. Rousseeuw formalized this approach in the FastPAM family of algorithms, which reaches the same type of single-swap local optimum with reduced repeated computation. The improvement concerns evaluation of the neighborhood and does not convert local search into exact global optimization.

Memory use can become significant when all (n^2) pairwise dissimilarities are stored. Coordinate-based data permit distances to be computed when required, whereas data available only as a precomputed dissimilarity matrix require direct access to that matrix or to an equivalent external representation. The appropriate computational model therefore depends on how dissimilarities are generated and retained.

Historical development and terminology

The term “medoid” was introduced by Leonard Kaufman and Peter J. Rousseeuw to distinguish an observed representative from a centroid defined through arithmetic averaging. Their 1987 formulation of clustering by means of medoids established the construction-and-exchange organization later identified with PAM. The method was subsequently presented systematically in their work on robust and graphical approaches to cluster analysis.

The notation “k-medoids” describes an optimization problem rather than a single algorithm. PAM, CLARA, CLARANS, and related local-search systems differ in how they explore candidate medoid sets, but they can all be evaluated against the same sum-of-dissimilarities criterion. Usage that treats PAM and k-medoids as exact synonyms therefore conflates one solution method with the broader problem it addresses.

Relation to other clustering objectives

K-medoids belongs to the family of facility location objectives. Observations act as demand points, selected medoids act as facilities, and dissimilarities act as assignment costs. In metric spaces, this formulation is also known as the metric (k)-median problem when candidate facilities are restricted to the observed points.

The connection with k-means clustering is structural rather than algebraic. Both methods alternate conceptually between choosing representatives and associating observations with them, but their representative constraints and loss functions differ. A mean minimizes the sum of squared Euclidean distances within an unconstrained Euclidean cluster, while a medoid minimizes total specified dissimilarity over a finite candidate set.

Hierarchical clustering differs more fundamentally because it produces a nested sequence of partitions rather than directly optimizing one fixed-(k) medoid set. A hierarchy can still be summarized by representative observations after construction, but that operation does not make its underlying objective identical to k-medoids.