K-medoids: Representative Observations, Dissimilarities and PAM Swaps

When an average is the wrong object

A mean customer vector can be useful. A mean DNA sequence, travel itinerary or text document may have no direct meaning. If a domain gives you a dissimilarity between complete objects, clustering around actual examples can be easier to interpret.

A medoid is an observed object that minimises total dissimilarity to the members it represents. The choice is discrete. Even with Euclidean coordinates, it differs from a centroid, which can lie anywhere in feature space. Interpretability here means the representative can be inspected, not that the grouping is automatically scientifically valid.

Write the objective before choosing an algorithm

Let \(d(i,j)\) be a nonnegative dissimilarity with a meaningful zero self-distance. Choose an index set M of size k:

Symmetric metric distances are common, but some procedures accept more general dissimilarities. Check the implementation’s assumptions. A dissimilarity matrix can be mathematically accepted yet encode the wrong notion of resemblance.

For fixed assignments, the representative of cluster C is

Computing this exactly examines candidate observations rather than differentiating a mean. The loss choice matters: Euclidean distance and squared Euclidean distance give different robustness. Restricting a representative to observed points does not by itself protect against every large-distance penalty.

An outlier example

Take one-dimensional observations \(0,1,2,20\) and absolute-distance dissimilarity. Candidate medoid costs are 23, 21, 21 and 57. Either 1 or 2 is optimal, with a deterministic tie rule selecting one.

The arithmetic mean is 5.75. It minimises squared error, but is dragged away from the three nearby observations. This example illustrates both a changed objective and a changed representative constraint. It would be incorrect to attribute the entire robustness difference to selecting an observed point while silently changing squared distance to absolute distance.

points = [0, 1, 2, 20]
cost = {m: sum(abs(x-m) for x in points) for m in points}
assert cost == {0: 23, 1: 21, 2: 21, 20: 57}
medoid = min(points, key=lambda m: (cost[m], m))
assert medoid == 1

Inspect the representative alongside the spread and extremes of its cluster. A single typical example can hide a heterogeneous collection just as a mean can.

PAM searches through swaps

Partitioning Around Medoids begins with a set of representatives and considers replacing a selected medoid with an unselected observation. For every candidate swap, evaluate the change in total nearest-medoid cost. Accept a beneficial swap and repeat until no improving swap remains under the search procedure.

This is stronger than merely alternating assignments with within-cluster medoid updates: a swap can alter membership across several clusters at once. It is still a local search. Different starting representatives can reach different solutions, and no-improving-single-swap does not certify the global optimum.

Caching each observation’s nearest and second-nearest medoid can accelerate evaluating a removal. When its closest representative disappears, the second-closest provides the fallback unless the newly added representative is nearer. This is an algorithmic optimisation that leaves the objective unchanged.

The price of flexible dissimilarity

A full pairwise matrix uses \(O(n^2)\) storage. At 100,000 observations, ten billion entries are already expensive before searching over medoid sets. Computing one edit distance or alignment can also be far more expensive than a vector subtraction.

Sampling approaches such as CLARA search for medoids on subsets and assess candidates on broader data. Faster PAM variants reuse distance calculations. Treat these as changes in search budget or approximation, then compare their full-data objective and representative stability.

A useful budget report includes how many pairwise distances were computed, whether they were cached, memory use and the number of starts. Counting only optimisation iterations hides the dominant cost.

Choose the dissimilarity deliberately

For mixed numerical and categorical records, an appropriate mixed-data dissimilarity may be more defensible than arbitrary integer codes. For sequences, decide whether insertions, substitutions and order changes carry the same cost. For texts, inspect whether the embedding captures the distinctions relevant to the application.

Missing values and incomparable observations need explicit handling. Pairwise distances computed from different subsets of features may not be comparable. Scaling, weighting and distance construction are part of the model, and any learned transformation belongs inside the training procedure.

What to report

Select k using application value, stability and clustering diagnostics. Display representative objects, cluster sizes, within-cluster distances and atypical members. Compare against k-means only where the objectives and representation make the comparison meaningful.

K-medoids is useful when representative examples and domain-specific dissimilarity matter. It is less attractive when a very large Euclidean dataset can be adequately summarised by means. Robustness is conditional on the loss and contamination pattern, not an unconditional property of a method’s name.

References

1. Park and Jun. A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications, 2009.
2. Schubert and Rousseeuw. Faster k-Medoids Clustering: Improving the PAM, CLARA, and CLARANS Algorithms. SISAP, 2019.