Definition
K-medoids partitions points into clusters, each represented by a medoid: the member of the cluster whose total distance to the other members is smallest. It minimizes the sum of (unsquared) dissimilarities from each point to its nearest medoid, and it needs nothing but a distance matrix, so it works with any distance you can compute.
At a glance
- Task
- Clustering (unsupervised partitioning)
- Input → output
- a dissimilarity matrix (or points + a metric) and → medoid indices and a cluster label per point
- Learns
- a set of actual data points; each point belongs to its nearest medoid
- Objective
- total deviation
- Training
- memory for ; classic PAM SWAP costs per round, FasterPAM
- Prediction
- distance computations: assign to the nearest medoid
- Hyperparameters
- k, the distance function, the algorithm (PAM / FasterPAM / alternating / CLARA), initialization
- Assumes
- clusters are compact around a central member under your distance; no vector space or mean needed
The problem
k-means represents each cluster by its mean. That single choice causes three problems. First, a mean only exists when you can average — there is no "average" of three DNA sequences, two customer journeys or a set of job titles. Second, k-means minimizes squared Euclidean distance, so a point 10 units away counts 100 times as much as a point 1 unit away; one outlier can drag a centre off the data, or capture a whole centre for itself. Third, the centre is a synthetic point that may correspond to nothing real, which makes it hard to explain to a person.
K-medoids fixes all three by restricting every centre to be one of the data points and by summing plain distances. It only ever looks up entries of the distance matrix, so Manhattan, cosine, edit distance, dynamic-time-warping or a hand-made dissimilarity all work. In the worked example below, k-means spends one of its two centres on a single outlier, while k-medoids keeps the two real groups.
The idea
Pick data points to act as "representatives". Every other point joins the representative it is closest to, and pays its distance as a cost. Try to choose the representatives so the total cost is as small as possible. Because there are only candidates for each representative, the search is discrete: start with a sensible choice, then repeatedly ask would swapping one representative for some other point make the total cost smaller? and stop when no swap helps.
Vocabulary
- Medoid
- the cluster member minimizing : the most central actual point. In 1-D with it is a median of the cluster.
- Dissimilarity matrix
- for all pairs. Only needs and ; symmetry and the triangle inequality help but are not required by the objective.
- Total deviation (TD)
- the objective: sum over all points of the distance to their nearest medoid. Lower is better.
- BUILD
- PAM's greedy initialization: add medoids one at a time, each time the point that lowers TD the most.
- SWAP
- PAM's improvement phase: evaluate exchanging a medoid with a non-medoid , apply the best exchange if it lowers TD, repeat.
- Nearest / second-nearest
- and : distance from point to its closest and second-closest medoid. Used to evaluate swaps quickly.
- PAM
- Partitioning Around Medoids (Kaufman & Rousseeuw, 1987): BUILD + SWAP.
The math
Let with be the medoid set. Each point is assigned to its nearest medoid, and the objective is the total deviation:
- number of points
- number of clusters (medoids)
- set of medoid indices — each is a real data point
- dissimilarity between point and medoid (entry )
- total deviation: sum of each point's distance to its nearest medoid
Compare k-means, which minimizes over arbitrary vectors . Two things change: the centre is constrained to the data, and the loss is , not . Finding exactly is NP-hard (it is the discrete -median problem), so we use local search. There are medoid sets; the heuristics below explore only a tiny fraction of them.
Why medoids resist outliers. With one cluster in 1-D and , the best centre minimizes , whose derivative is = (#points below ) − (#points above ). It is zero at the median, and moving one point far away does not change which point is in the middle. The squared loss has derivative , zero at the mean, which moves by whenever one point moves by . The robustness is a property of the unsquared loss; making the centre a data point is what lets that loss work with any .
BUILD (greedy start). The first medoid is the single best centre, the point with the smallest row sum of . Each later medoid is the candidate that removes the most cost given the medoids chosen so far, where is point 's current nearest-medoid distance:
- distance from point to its nearest medoid in the current
- how much point saves if becomes a medoid (zero if is not closer than what already has)
The gain is exactly , because adding changes each point's cost from to , and .
SWAP (local search). For a medoid and a non-medoid , the change in cost from exchanging them is
- the medoid being removed
- the non-medoid being promoted
- change in TD; negative means the swap helps
Each point's contribution falls into one of two cases, which is how PAM evaluates a swap in instead of re-clustering. Let be the distance to the second-nearest medoid. If was point 's medoid, then after the swap goes to or to its second-nearest medoid: contribution . Otherwise keeps its medoid unless is closer: contribution . PAM applies the swap with the most negative and stops when every . TD strictly decreases at every applied swap and there are finitely many medoid sets, so it always terminates, at a set that no single exchange can improve.
How the choices act on the objective
- k
- TD is non-increasing in (adding a medoid can only lower each ); at every point is its own medoid and TD . So choose with silhouette or a held-out criterion, never by TD alone.
- Distance d
- defines the whole problem. With the loss grows quadratically and outliers dominate, exactly like k-means; with or it grows linearly.
- Feature scale
- for vector data is computed on raw features, so a feature measured in thousands swamps one measured in units. Standardize first, or use a scale-free dissimilarity.
- Algorithm
- BUILD+SWAP (PAM) searches more thoroughly than the k-means-style alternating update, at higher cost per round (see Variants).
Worked example: 11 points and one outlier
Two groups in the plane — A to F in the lower left, G to J in the upper right — plus one outlier K far to the right. We use and the Manhattan distance , so every distance is an integer you can check by hand (e.g. ).
| Point | x₁ | x₂ | Σ d(i, c) | d(i, F) | gain if added |
|---|---|---|---|---|---|
| A | 1 | 1 | 80 | 6 | 14 |
| B | 2 | 1 | 73 | 5 | 15 |
| C | 1 | 3 | 70 | 4 | 12 |
| D | 2 | 2 | 66 | 4 | 16 |
| E | 3 | 2 | 63 | 3 | 13 |
| F | 4 | 4 | 58 | 0 | — |
| G | 6 | 6 | 64 | 4 | 18 |
| H | 7 | 5 | 64 | 4 | 18 |
| I | 7 | 7 | 76 | 6 | 18 |
| J | 8 | 6 | 74 | 6 | 20 |
| K | 18 | 6 | 164 | 16 | 16 |
PAM by hand
- 1BUILD, medoid 1. Sum each row of the distance matrix. F, the "bridge" point at (4, 4), has the smallest total, 58: alone, it is the best single centre. Note that F is between the groups — a good 1-medoid, a poor member of a 2-medoid solution.
- 2BUILD, medoid 2. With F as the only medoid, point costs . Adding J saves (from G, H, I, J itself and K), the largest gain. Medoids .
- 3Assign. A–F go to F (distances 6, 5, 4, 4, 3, 0) and G–K go to J (2, 2, 2, 0, 10). .
- 4SWAP round 1. Evaluate all exchanges (table below). The best is F → D with : A–F now cost 2, 1, 2, 0, 1, 4 = 10 instead of 22, and G–K are unaffected because they are all closer to J than to D. Apply it: .
- 5SWAP round 2. With medoids all 18 exchanges have ; the smallest is (D → B, D → E, J → G, J → H, J → I). Stop. An exhaustive check of all pairs confirms TD = 26 is the global optimum here.
- 6Result. Clusters with medoid D = (2, 2) and with medoid J = (8, 6). The second cluster's mean is (9.2, 6.0), pulled 1.2 units toward K; its medoid stays inside the group.
- 7Predict. A new point (5, 3) is from D and from J, so it joins D's cluster.
| remove ↓ / add → | A | B | C | D | E | G | H | I | K |
|---|---|---|---|---|---|---|---|---|---|
| F | −8 | −10 | −8 | −12 | −10 | +22 | +22 | +34 | +26 |
| J | +6 | +5 | +8 | +4 | +7 | +2 | +2 | +2 | +4 |
For comparison, k-means with on the same points (best of 10 starts) puts K alone in one cluster with centre (18, 6) and all ten other points in the other with centre (4.1, 3.7), inertia 109.0. Under squared distance, K's cost to any centre near the right group is about , so giving K its own centre is "cheaper" than splitting the two real groups.
- 1D ← pairwise distances (any metric)
- 2BUILD: m₁ ← argmin_c Σᵢ d(i, c)
- 3 add argmax_c Σᵢ max(0, dᵢ − d(i,c))
- 4SWAP: repeat
- 5 Δ(m,h) ← TD(M − m + h) − TD(M)
- 6 if min Δ < 0: swap that (m, h)
- 7 else: stop (local optimum)
- 8predict: x → nearest medoid
11 points, k = 2. PAM never looks at coordinates again: everything below uses only the 11×11 distance matrix D (Manhattan |·|₁).
The algorithm, step by step
PAM(D, k)
- 1Distances. Compute or receive the dissimilarity matrix . This is the only input the rest of the algorithm touches.
- 2BUILD. . While : compute every point's nearest-medoid distance and add .
- 3SWAP. For each medoid and each non-medoid , compute using the nearest/second-nearest trick. Keep the most negative.
- 4Apply or stop. If the best , replace by , update , and repeat SWAP. Otherwise stop: is a local optimum for single swaps.
- 5Label. Each point gets the index of its nearest medoid. New points: compute distances and take the nearest.
Cost
- Distance matrix
- time and memory — the real bottleneck: needs entries (10 GB in float32).
- BUILD
- PAM SWAP round
- candidate swaps × each
- FasterPAM round
- : evaluates all removals for a candidate in one pass and applies any improving swap immediately (Schubert & Rousseeuw, 2021)
- Prediction
- distances per new point
Variants and practical tuning
| Algorithm | Search | Cost per round | Use when |
|---|---|---|---|
| PAM (BUILD + SWAP) | best single swap per round | small n (≲ few thousand), you want the classic, well-studied result | |
| FasterPAM | first improving swap, all removals at once | default choice for n up to tens of thousands; same swaps evaluated far more cheaply, similar quality to PAM | |
| Alternating (Voronoi iteration) | k-means-style: assign, then re-pick each cluster's medoid | about | quick, but gets stuck more easily |
| CLARA | PAM on several random samples, keep the best medoids | PAM on sample size ≈ 40 + 2k | n too large for an n × n matrix |
| CLARANS | randomized swap search on the full data | random subset of swaps | large n, moderate k, quality between CLARA and PAM |
The alternating variant is what you get if you copy k-means literally: assign each point to its nearest medoid, then replace each medoid by the most central member of its own cluster, and repeat. Each medoid only looks inside its current cluster, so it cannot move a medoid to a different group. On our data, starting from it stalls at with TD 28, and from any start containing K it stays at with TD 42 (9 of the 55 possible starts end at a worse solution). PAM's SWAP escapes both: from it swaps G → J (), and from it swaps K → J (), then F → D (), reaching TD 26.
Tuning checklist
- Choosing k
- Silhouette works directly from the same distance matrix (no means needed); also plot TD vs k and look for the elbow, as with k-means.
- Choosing d
- Pick the distance that matches what similar means in your domain: Manhattan for robust tabular data, cosine for text/embeddings, Gower for mixed numeric/categorical, edit or DTW for sequences.
- Scaling
- Standardize numeric features before Manhattan/Euclidean, or one feature dominates the distance.
- Initialization
- BUILD is deterministic and strong; with random init use several restarts (FasterPAM is cheap enough) and keep the lowest TD.
- Large n
- CLARA / CLARANS, or cluster a sample and assign the rest to the nearest medoid.
In code
1import numpy as np23def pairwise(X, metric="manhattan"):4 diff = X[:, None, :] - X[None, :, :]5 if metric == "manhattan":6 return np.abs(diff).sum(-1)7 if metric == "euclidean":8 return np.sqrt((diff ** 2).sum(-1))9 raise ValueError(metric)1011def total_deviation(D, medoids):12 return D[:, medoids].min(axis=1).sum()1314def build(D, k):15 medoids = [int(np.argmin(D.sum(axis=1)))] # the 1-medoid16 while len(medoids) < k:17 near = D[:, medoids].min(axis=1) # distance to current nearest medoid18 gain = np.maximum(near[:, None] - D, 0).sum(axis=0)19 gain[medoids] = -120 medoids.append(int(np.argmax(gain)))21 return medoids2223def pam(X, k, metric="manhattan", max_iter=100):24 D = pairwise(X, metric)25 medoids = build(D, k)26 td = total_deviation(D, medoids)27 print(f"BUILD -> medoids {medoids}, TD = {td:g}")28 for it in range(max_iter):29 best = (0.0, None, None) # (delta, slot, candidate)30 for slot in range(k):31 for h in range(len(X)):32 if h in medoids:33 continue34 trial = medoids.copy(); trial[slot] = h35 delta = total_deviation(D, trial) - td36 if delta < best[0]:37 best = (delta, slot, h)38 if best[1] is None: # no swap lowers TD: local optimum39 break40 delta, slot, h = best41 print(f"swap {medoids[slot]} -> {h}: delta = {delta:g}")42 medoids[slot] = h43 td += delta44 labels = D[:, medoids].argmin(axis=1)45 return medoids, labels, td4647X = np.array([[1,1],[2,1],[1,3],[2,2],[3,2],[4,4],[6,6],[7,5],[7,7],[8,6],[18,6]])48medoids, labels, td = pam(X, k=2)49print("medoids", medoids, "=", X[medoids].tolist())50print("labels ", labels.tolist(), " TD =", td)51new = np.array([5, 3])52print("new point ->", np.abs(X[medoids] - new).sum(axis=1).tolist())1import numpy as np2import kmedoids # pip install kmedoids3from sklearn.cluster import KMeans4from sklearn.metrics import pairwise_distances56X = np.array([[1,1],[2,1],[1,3],[2,2],[3,2],[4,4],[6,6],[7,5],[7,7],[8,6],[18,6]])78km = kmedoids.KMedoids(n_clusters=2, metric="manhattan", method="pam", init="build").fit(X)9print("PAM medoids", km.medoid_indices_.tolist(), "labels", km.labels_.tolist(), "TD", km.inertia_)1011D = pairwise_distances(X, metric="manhattan") # any precomputed dissimilarity works12res = kmedoids.fasterpam(D, 2, init="random", random_state=0)13print("FasterPAM medoids", sorted(res.medoids.tolist()), "TD", res.loss)1415print("predict (5,3) ->", km.predict(np.array([[5, 3]])).tolist()) # [3]: the medoid's row index (D)1617means = KMeans(n_clusters=2, n_init=10, random_state=0).fit(X)18print("k-means labels", means.labels_.tolist(), "centres", means.cluster_centers_.round(2).tolist())Use when
- +Your data has no meaningful mean: strings, sequences, graphs, sets, mixed-type records with Gower distance.
- +You have only a similarity or distance matrix, e.g. from a domain-specific comparison.
- +Outliers are present and you use an unsquared distance.
- +You need interpretable prototypes: each cluster is summarized by a real example you can show someone.
Avoid when
- − is large (≳ 50k) and you cannot afford the distance matrix — use k-means, mini-batch k-means or CLARA.
- −Clusters are non-convex or chained (rings, moons) — use DBSCAN, spectral or single-linkage clustering.
- −Clusters have very different sizes or densities: a nearest-medoid rule splits big clusters, as k-means does.
- −Your data is plain Euclidean vectors without outliers: k-means gives nearly the same answer much faster.
Where it's used
Bioinformatics
Clustering gene-expression profiles or protein sequences under correlation or alignment distances; the medoid is a real representative gene or sequence.
Time-series grouping
Load curves, sensor traces or user sessions clustered with dynamic time warping, where a mean curve would be blurred and meaningless.
Facility & sensor placement
Choose k actual sites (warehouses, base stations) minimizing total travel distance — the k-median problem in its natural form.
Prototype selection
Pick k representative customers, documents or images for review, labelling or a small training set.
Check yourself
One cluster contains the 1-D points 1, 2, 3, 4, 100. With d = |a − b|, what are its medoid and its mean?
Check yourself
PAM with n = 11 points and k = 2. How many (medoid, non-medoid) swaps does one SWAP round evaluate?
Check yourself
In the worked example, medoids are D = (2, 2) and J = (8, 6) with Manhattan distance. If the outlier K moves from (18, 6) to (20, 6), what is the new TD?
Check yourself
Which change would make k-medoids about as sensitive to outliers as k-means?
Remember
- ✓K-medoids picks actual data points as centres and minimizes the total (unsquared) distance .
- ✓It needs only a dissimilarity matrix, so any distance works: Manhattan, cosine, Gower, edit distance, DTW.
- ✓Robustness to outliers comes from the unsquared loss (median-like behaviour); with squared Euclidean it behaves like k-means.
- ✓PAM = greedy BUILD + SWAP local search on ; FasterPAM gets the same quality in per round.
- ✓The price is memory and time for the distance matrix; for big use CLARA, sampling or k-means.