K-Medoids

Like k-means, but every center must be an actual data point, so any distance works and outliers pull less.

16 min read1607 wordscore15 viewsupdated 2026-10-07

Definition

K-medoids partitions nn points into kk 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 D∈Rn×nD\in\mathbb{R}^{n\times n} (or points + a metric) and kk → kk medoid indices and a cluster label per point
Learns
a set MM of kk actual data points; each point belongs to its nearest medoid
Objective
total deviation TD=∑imin⁡m∈Md(i,m)\text{TD}=\sum_i \min_{m\in M} d(i,m)
Training
O(n2)O(n^2) memory for DD; classic PAM SWAP costs O(k(n−k)2)O(k(n-k)^2) per round, FasterPAM O(n2)O(n^2)
Prediction
O(k)O(k) 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 kk 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 nn 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 mm minimizing ∑i∈Cd(i,m)\sum_{i\in C} d(i,m): the most central actual point. In 1-D with ∣⋅∣|\cdot| it is a median of the cluster.
Dissimilarity matrix
Dij=d(xi,xj)D_{ij}=d(x_i,x_j) for all pairs. Only needs d≥0d\ge0 and d(i,i)=0d(i,i)=0; 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 mm with a non-medoid hh, apply the best exchange if it lowers TD, repeat.
Nearest / second-nearest
did_i and eie_i: distance from point ii to its closest and second-closest medoid. Used to evaluate swaps quickly.
PAM
Partitioning Around Medoids (Kaufman & Rousseeuw, 1987): BUILD + SWAP.

The math

Let M⊆{1,…,n}M\subseteq\{1,\dots,n\} with ∣M∣=k|M|=k be the medoid set. Each point is assigned to its nearest medoid, and the objective is the total deviation:

TD(M)=∑i=1nmin⁡m∈Md(xi,xm)M⋆=arg⁡min⁡M⊆{1..n},  ∣M∣=kTD(M)\text{TD}(M)=\sum_{i=1}^{n}\min_{m\in M} d(x_i,x_m)\qquad M^\star=\arg\min_{M\subseteq\{1..n\},\;|M|=k}\text{TD}(M)
nn
number of points
kk
number of clusters (medoids)
MM
set of medoid indices — each is a real data point
d(xi,xm)d(x_i,x_m)
dissimilarity between point ii and medoid mm (entry DimD_{im})
TD(M)\text{TD}(M)
total deviation: sum of each point's distance to its nearest medoid

Compare k-means, which minimizes ∑imin⁡j∥xi−μj∥2\sum_i\min_j\lVert x_i-\mu_j\rVert^2 over arbitrary vectors μj\mu_j. Two things change: the centre is constrained to the data, and the loss is dd, not d2d^2. Finding M⋆M^\star exactly is NP-hard (it is the discrete kk-median problem), so we use local search. There are (nk)\binom{n}{k} medoid sets; the heuristics below explore only a tiny fraction of them.

Why medoids resist outliers. With one cluster in 1-D and d=∣⋅∣d=|\cdot|, the best centre minimizes ∑i∣xi−c∣\sum_i |x_i-c|, whose derivative is ∑isign⁡(c−xi)\sum_i \operatorname{sign}(c-x_i) = (#points below cc) − (#points above cc). 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 2∑i(c−xi)2\sum_i(c-x_i), zero at the mean, which moves by Δ/n\Delta/n whenever one point moves by Δ\Delta. The robustness is a property of the unsquared loss; making the centre a data point is what lets that loss work with any dd.

BUILD (greedy start). The first medoid is the single best centre, the point with the smallest row sum of DD. Each later medoid is the candidate cc that removes the most cost given the medoids chosen so far, where did_i is point ii's current nearest-medoid distance:

m1=arg⁡min⁡c∑id(i,c),mt+1=arg⁡max⁡c∉M  ∑imax⁡(0,  di−d(i,c))m_1=\arg\min_{c}\sum_{i} d(i,c),\qquad m_{t+1}=\arg\max_{c\notin M}\;\sum_{i}\max\big(0,\;d_i-d(i,c)\big)
did_i
distance from point ii to its nearest medoid in the current MM
max⁡(0, di−d(i,c))\max(0,\,d_i-d(i,c))
how much point ii saves if cc becomes a medoid (zero if cc is not closer than what ii already has)

The gain is exactly TD(M)−TD(M∪{c})\text{TD}(M)-\text{TD}(M\cup\{c\}), because adding cc changes each point's cost from did_i to min⁡(di,d(i,c))\min(d_i,d(i,c)), and di−min⁡(di,d(i,c))=max⁡(0,di−d(i,c))d_i-\min(d_i,d(i,c))=\max(0,d_i-d(i,c)).

SWAP (local search). For a medoid m∈Mm\in M and a non-medoid hh, the change in cost from exchanging them is

Δ(m,h)=TD(M∖{m}∪{h})−TD(M)=∑i(min⁡j∈M∖{m}∪{h}d(i,j)  −  di)\Delta(m,h)=\text{TD}\big(M\setminus\{m\}\cup\{h\}\big)-\text{TD}(M)=\sum_{i} \Big(\min_{j\in M\setminus\{m\}\cup\{h\}} d(i,j)\;-\;d_i\Big)
mm
the medoid being removed
hh
the non-medoid being promoted
Δ(m,h)\Delta(m,h)
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 O(n)O(n) instead of re-clustering. Let eie_i be the distance to the second-nearest medoid. If mm was point ii's medoid, then after the swap ii goes to hh or to its second-nearest medoid: contribution min⁡(d(i,h),ei)−di\min(d(i,h),e_i)-d_i. Otherwise ii keeps its medoid unless hh is closer: contribution min⁡(d(i,h),di)−di≤0\min(d(i,h),d_i)-d_i\le0. PAM applies the swap with the most negative Δ\Delta and stops when every Δ≥0\Delta\ge0. 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 kk (adding a medoid can only lower each min⁡\min); at k=nk=n every point is its own medoid and TD =0=0. So choose kk with silhouette or a held-out criterion, never by TD alone.
Distance d
defines the whole problem. With d=∥⋅∥2d=\lVert\cdot\rVert^2 the loss grows quadratically and outliers dominate, exactly like k-means; with ∣⋅∣1|\cdot|_1 or ∥⋅∥2\lVert\cdot\rVert_2 it grows linearly.
Feature scale
for vector data dd 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 k=2k=2 and the Manhattan distance d(p,q)=∣p1−q1∣+∣p2−q2∣d(p,q)=|p_1-q_1|+|p_2-q_2|, so every distance is an integer you can check by hand (e.g. d(F,J)=∣4−8∣+∣4−6∣=6d(F,J)=|4-8|+|4-6|=6).

Pointx₁x₂Σ d(i, c)d(i, F)gain if added
A1180614
B2173515
C1370412
D2266416
E3263313
F44580—
G6664418
H7564418
I7776618
J8674620
K1861641616
The data, with each point's total Manhattan distance to all others (BUILD step 1) and its gain if added next to F (BUILD step 2). Highlighted: F (smallest total, first medoid) and J (largest gain, second medoid).

PAM by hand

  1. 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.
  2. 2BUILD, medoid 2. With F as the only medoid, point ii costs d(i,F)d(i,F). Adding J saves max⁡(0,4−2)+max⁡(0,4−2)+max⁡(0,6−2)+6+(16−10)=2+2+4+6+6=20\max(0,4-2)+\max(0,4-2)+\max(0,6-2)+6+(16-10)=2+2+4+6+6=20 (from G, H, I, J itself and K), the largest gain. Medoids {F,J}\{F,J\}.
  3. 3Assign. A–F go to F (distances 6, 5, 4, 4, 3, 0) and G–K go to J (2, 2, 2, 0, 10). TD=22+16=38\text{TD}=22+16=38.
  4. 4SWAP round 1. Evaluate all 2×9=182\times9=18 exchanges (table below). The best is F → D with Δ=−12\Delta=-12: 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: TD=38−12=26\text{TD}=38-12=26.
  5. 5SWAP round 2. With medoids {D,J}\{D,J\} all 18 exchanges have Δ≥0\Delta\ge0; the smallest is +2+2 (D → B, D → E, J → G, J → H, J → I). Stop. An exhaustive check of all (112)=55\binom{11}{2}=55 pairs confirms TD = 26 is the global optimum here.
  6. 6Result. Clusters {A,B,C,D,E,F}\{A,B,C,D,E,F\} with medoid D = (2, 2) and {G,H,I,J,K}\{G,H,I,J,K\} 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.
  7. 7Predict. A new point (5, 3) is ∣5−2∣+∣3−2∣=4|5-2|+|3-2|=4 from D and ∣5−8∣+∣3−6∣=6|5-8|+|3-6|=6 from J, so it joins D's cluster.
remove ↓ / add →ABCDEGHIK
F−8−10−8−12−10+22+22+34+26
J+6+5+8+4+7+2+2+2+4
SWAP round 1: ΔTD for replacing a medoid (row) by a candidate (column), starting from TD = 38. Negative entries lower the cost; the best is F → D (−12). Replacing J never helps.

For comparison, k-means with k=2k=2 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 102=10010^2=100, so giving K its own centre is "cheaper" than splitting the two real groups.

▸ k-medoids · PAM (BUILD + SWAP)step 1/7
0246810121416182002468drag the outlier KABCDEFGHIJKrings will mark the medoids — always actual data points
phase datamedoids —TD = —
  1. 1D ← pairwise distances (any metric)
  2. 2BUILD: m₁ ← argmin_c Σᵢ d(i, c)
  3. 3 add argmax_c Σᵢ max(0, dᵢ − d(i,c))
  4. 4SWAP: repeat
  5. 5 Δ(m,h) ← TD(M − m + h) − TD(M)
  6. 6 if min Δ < 0: swap that (m, h)
  7. 7 else: stop (local optimum)
  8. 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 |·|₁).

fig.PAM on the 11 points above (k = 2, Manhattan). BUILD picks F (total 58), then J (gain 20), TD = 38; SWAP round 1 scores all 18 exchanges in the heat-table and applies F → D (−12, TD 26); round 2 finds no negative Δ (smallest +2) and stops; the new point (5, 3) joins D (4 vs 6). Drag the outlier K along its row (y = 6): with Manhattan the medoids stay D and J and TD = 16 + d(K, J). Drag it up or down and the right-hand medoid hops to H or I; drag it to a far corner such as (18, 0) and PAM gives K its own medoid, so robustness has limits. Switch to squared distance and PAM ends with F and K as medoids (TD 110, while {D, J} would cost 122); with plain Euclidean BUILD chooses K over J by 14.14 to 14.02 and SWAP cannot escape (TD 30.78 versus the optimum 22.49). Toggle k-means to see its centres at (4.1, 3.7) and (18, 6).

The algorithm, step by step

PAM(D, k)

  1. 1Distances. Compute or receive the n×nn\times n dissimilarity matrix DD. This is the only input the rest of the algorithm touches.
  2. 2BUILD. m1←arg⁡min⁡c∑iDicm_1\leftarrow\arg\min_c\sum_i D_{ic}. While ∣M∣<k|M|<k: compute every point's nearest-medoid distance did_i and add arg⁡max⁡c∉M∑imax⁡(0,di−Dic)\arg\max_{c\notin M}\sum_i\max(0,d_i-D_{ic}).
  3. 3SWAP. For each medoid m∈Mm\in M and each non-medoid hh, compute Δ(m,h)\Delta(m,h) using the nearest/second-nearest trick. Keep the most negative.
  4. 4Apply or stop. If the best Δ<0\Delta<0, replace mm by hh, update di,eid_i,e_i, and repeat SWAP. Otherwise stop: MM is a local optimum for single swaps.
  5. 5Label. Each point gets the index of its nearest medoid. New points: compute kk distances and take the nearest.

Cost

Distance matrix
O(n2)O(n^2) time and memory — the real bottleneck: n=50,000n=50{,}000 needs 2.5×1092.5\times10^9 entries (10 GB in float32).
BUILD
O(kn2)O(kn^2)
PAM SWAP round
k(n−k)k(n-k) candidate swaps × O(n−k)O(n-k) each =O(k(n−k)2)=O(k(n-k)^2)
FasterPAM round
O(n2)O(n^2): evaluates all kk removals for a candidate hh in one pass and applies any improving swap immediately (Schubert & Rousseeuw, 2021)
Prediction
O(k)O(k) distances per new point

Variants and practical tuning

AlgorithmSearchCost per roundUse when
PAM (BUILD + SWAP)best single swap per roundO(k(n−k)2)O(k(n-k)^2)small n (≲ few thousand), you want the classic, well-studied result
FasterPAMfirst improving swap, all removals at onceO(n2)O(n^2)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 medoidabout O(n2/k)O(n^2/k)quick, but gets stuck more easily
CLARAPAM on several random samples, keep the best medoidsPAM on sample size ≈ 40 + 2kn too large for an n × n matrix
CLARANSrandomized swap search on the full datarandom subset of swapslarge n, moderate k, quality between CLARA and PAM
The main k-medoids algorithms. All minimize the same TD; they differ in how hard they search and how much memory they need.

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 {C,D}\{C,D\} it stalls at {D,G}\{D,G\} with TD 28, and from any start containing K it stays at {F,K}\{F,K\} with TD 42 (9 of the 55 possible starts end at a worse solution). PAM's SWAP escapes both: from {D,G}\{D,G\} it swaps G → J (Δ=−2\Delta=-2), and from {F,K}\{F,K\} it swaps K → J (−4-4), then F → D (−12-12), 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

python
1import numpy as np
2
3def 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)
10
11def total_deviation(D, medoids):
12 return D[:, medoids].min(axis=1).sum()
13
14def build(D, k):
15 medoids = [int(np.argmin(D.sum(axis=1)))] # the 1-medoid
16 while len(medoids) < k:
17 near = D[:, medoids].min(axis=1) # distance to current nearest medoid
18 gain = np.maximum(near[:, None] - D, 0).sum(axis=0)
19 gain[medoids] = -1
20 medoids.append(int(np.argmax(gain)))
21 return medoids
22
23def 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 continue
34 trial = medoids.copy(); trial[slot] = h
35 delta = total_deviation(D, trial) - td
36 if delta < best[0]:
37 best = (delta, slot, h)
38 if best[1] is None: # no swap lowers TD: local optimum
39 break
40 delta, slot, h = best
41 print(f"swap {medoids[slot]} -> {h}: delta = {delta:g}")
42 medoids[slot] = h
43 td += delta
44 labels = D[:, medoids].argmin(axis=1)
45 return medoids, labels, td
46
47X = 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())
From scratch: PAM with BUILD and best-swap SWAP. Prints BUILD → medoids [5, 9], TD = 38; swap 5 -> 3: delta = -12; final medoids [3, 9] = (2, 2) and (8, 6), TD = 26; the new point is 4 and 6 away.
python
1import numpy as np
2import kmedoids # pip install kmedoids
3from sklearn.cluster import KMeans
4from sklearn.metrics import pairwise_distances
5
6X = np.array([[1,1],[2,1],[1,3],[2,2],[3,2],[4,4],[6,6],[7,5],[7,7],[8,6],[18,6]])
7
8km = 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_)
10
11D = pairwise_distances(X, metric="manhattan") # any precomputed dissimilarity works
12res = kmedoids.fasterpam(D, 2, init="random", random_state=0)
13print("FasterPAM medoids", sorted(res.medoids.tolist()), "TD", res.loss)
14
15print("predict (5,3) ->", km.predict(np.array([[5, 3]])).tolist()) # [3]: the medoid's row index (D)
16
17means = 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())
With the kmedoids package (pip install kmedoids; scikit-learn style API), compared with k-means. Output: PAM medoids [3, 9], labels [0]*6 + [1]*5, TD 26.0; FasterPAM from a random start also reaches [3, 9] with TD 26.0; k-means labels put only K in cluster 1, centres (4.1, 3.7) and (18.0, 6.0).

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

  • −nn is large (≳ 50k) and you cannot afford the O(n2)O(n^2) 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 kk actual data points as centres and minimizes the total (unsquared) distance TD=∑imin⁡md(i,m)\text{TD}=\sum_i\min_{m}d(i,m).
  • ✓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 Δ(m,h)\Delta(m,h); FasterPAM gets the same quality in O(n2)O(n^2) per round.
  • ✓The price is O(n2)O(n^2) memory and time for the distance matrix; for big nn use CLARA, sampling or k-means.
← back to ML Algorithms roadmap