The idea: centres that are real points

K-Means puts each centre at the mean of its points. A mean is usually not a data point, and one far-away point can pull it a long way. k-medoids chooses k of the data points themselves as centres. Such a centre is a medoid: the point of its group with the smallest total distance to the others. Every point joins its nearest medoid.

Group C of the page, points #10 to #13 around (7.5, 2.5), plus the outlier #14 at (9.5, 9.5) joined to medoid #10. Without #14 the mean of the group is at (7.38, 2.50), inside the ring of #10; with #14 an arrow shows it moving up to (7.80, 3.90), where there is no data point (cross). The medoid stays on point #10 (tick)
One far point moves the mean of group C by 1.46; the medoid stays on #10, a real point inside the group.

The cost: total distance TD

k-medoids minimizes the total distance TD: the sum, over all points, of the distance to the nearest medoid. The distances are plain (here Euclidean), not squared as in the K-Means SSE. Squaring makes a far point count much more, so it is one reason K-Means is more sensitive to outliers. Because only distances between data points are needed, k-medoids also works with any dissimilarity: Manhattan distance, edit distance between strings, or a ready-made distance matrix.

On the canvas a thin line joins each point to its medoid; TD is the total length of these lines.

PAM: BUILD, then SWAP

PAM (Partitioning Around Medoids, Kaufman and Rousseeuw) has two phases:

  1. BUILD: pick the point that gives the lowest TD as the only medoid; then, k − 1 more times, add the point that lowers TD the most.
  2. SWAP: for every medoid m and every non-medoid o, compute TD if o replaces m. That is k × (n − k) pairs, 3 × 10 = 30 on the page. If the best pair lowers TD, swap it and repeat. If no pair lowers TD, stop.

The panel lists, for each medoid, the best non-medoid to swap it with and the TD that would give; the green row is the swap that is made. (Demo 2: BUILD, then SWAP: BUILD picks #5, #10 and #6, TD = 14.64; one swap, #5 out and #1 in, gives TD = 11.70, the best possible for k = 3.)

Before and after one SWAP from the poor start. Left: medoids #1, #2, #3 all in the lower-left group, the upper and right groups joined to them with long lines, TD = 41.75. Right: #1 is swapped out and #6 in, the upper group now has its own medoid, TD = 25.00; #1 is now an ordinary point of the lower-left group
One SWAP round: of 30 trades, #1 out and #6 in lowers TD the most, from 41.75 to 25.00.

The start matters: local optima

SWAP only accepts a trade that lowers TD, so it always stops, but it can stop at a local optimum, where no single swap helps though a better set of medoids exists.

RunTD after each stepResult
k = 3, poor start #1 #2 #3 (Demo 1)41.75 → 25.00 → 13.16 → 11.703 swaps, best possible
k = 3, BUILD (Demo 2)14.64 → 11.701 swap, best possible
k = 2, poor start #1 #2 (Demo 3)46.48 → 30.08 → 28.62stops; the best is 28.27 (BUILD finds it)

BUILD costs more than a random start, but it usually starts close to the answer, so few swaps follow. Some libraries start with k-medoids++ (random seeding as in k-means++) instead and accept the risk.

Outliers: medoid vs mean

Add #14 at (9.5, 9.5) and run PAM with k = 3: it joins group C, but the medoid of C stays #10 (7.5, 2.5). The K-Means button runs Lloyd's algorithm from the same medoids. The mean of C moves from (7.38, 2.50) to (7.80, 3.90), 1.46 away, to a place where there is no data. (Demo 4: an outlier pulls the mean)

K-Meansk-medoids (PAM)
centremean, any point in spaceone of the data points
costsum of squared distances (SSE)sum of distances (TD)
one outlierpulls the mean toward itadds one distance; the medoid stays
distanceEuclidean (the mean needs coordinates)any dissimilarity
cost per roundO(nk)O(k(n − k)²) for a PAM SWAP round

The silhouette of one point

A clustering is good when each point is close to its own cluster and far from the others. The silhouette measures this per point i:

  • a(i): the mean distance from i to the other points of its own cluster.
  • b(i): the mean distance from i to the points of each other cluster; take the smallest (the nearest other cluster).
  • s(i) = (b − a) / max(a, b), between −1 and 1.

s near 1: well inside its cluster. Near 0: on the border between two clusters. Below 0: on average closer to another cluster, so probably in the wrong one. A point alone in its cluster has no a(i); it gets s = 0.

Point #5 at (1.5, 3.5) with solid lines to the four other points of its lower-left group, mean a = 1.94, and dashed lines to the four points of the upper group, mean b = 4.29 (the right-hand group is farther, 5.99). Beside it, the formula s = (4.29 − 1.94) / 4.29 = 0.55
#5 has the lowest silhouette for k = 3: a = 1.94 to its own group, b = 4.29 to the nearest other group, s = 0.55.

The Silhouette button first works through the point with the lowest s, then draws all bars, grouped by cluster, and the average silhouette s̄ as a black line. (Demo 5: k = 3 gives s̄ = 0.70; the lowest is #5 with 0.55.) With the outlier, #14 gets s = −0.01 for k = 3: it is about as far from its own group C as from group B.

Choosing k with the average silhouette

TD always falls when k grows (one more medoid can only bring points closer), so the lowest TD would always pick the largest k. The average silhouette does not: too few clusters make a(i) large, too many split a group so that b(i) becomes small. Pick the k with the highest s̄. (Demo 6: choose k)

kTDaverage s
228.270.49
311.700.70 ✓ highest
410.120.58

With the outlier and k = 4, PAM gives #14 a medoid of its own (TD = 11.70); #14 is then alone and gets s = 0, and s̄ = 0.65. (Demo 7) Kaufman and Rousseeuw's rough guide: s̄ above 0.70 means a strong structure, 0.51–0.70 a reasonable one, 0.26–0.50 a weak one, and 0.25 or less no real structure.

The silhouette works for any clustering, not only k-medoids: it can also score K-Means (next to its elbow plot), a cut of a dendrogram or DBSCAN (leaving the noise out). For soft clusters with probabilities, see K-Means vs Gaussian mixtures.

Cost and faster variants

  • A plain PAM SWAP round tries k(n − k) pairs and each costs O(n), so O(k(n − k)²) per round: fine for thousands of points, too slow for millions.
  • CLARA runs PAM on several random samples and keeps the medoids with the lowest TD on all the data; CLARANS tries random swaps instead of all of them.
  • FasterPAM (Schubert and Rousseeuw) finds the same kind of answer about O(k) times faster by sharing work between pairs and taking the first good swap.
  • The silhouette needs all pairwise distances: O(n²).

See also The EM Algorithm, Step by Step for soft clustering with a mixture of Gaussians fitted by EM.

What the page leaves out

The data has 13 or 14 points in 2-D, so every swap and every distance can be shown. The page uses Euclidean distance only, and PAM as first described (best swap per round); it does not run CLARA, CLARANS or FasterPAM, and skips the "alternating" k-medoids (a K-Means-like loop) that is faster but finds worse answers. Other ways to choose k (the gap statistic, the elbow on TD) and the silhouette plot of very large data sets are only mentioned.

On the mind map

Open the Machine Learning mind mapMachine LearningLearning setup: what feedback, how to scoreLearning setupLinear models: weighted sum w·x + bLinear modelsOther classic models: trees, margins, neighboursOther classic modelsUnsupervised: find structure without labelsUnsupervisedTraining: loss, gradient, small stepTrainingNeural networks: layers of σ(W·a + b)Neural networksArchitectures: how layers share informationArchitecturesLanguage models: predict the next tokenLanguage modelsLLM speed and tuning: cheaper to run, safer to useLLM speed and tuningRetrieval and agents: give the model data and toolsRetrieval and agentsK-meansK-meansassign to nearest centroid, move centroidK-Medoids and SilhouetteReal points as centres; pick k by avg sApriori RulesApriori RulesSubset not frequent → skip the supersetDBSCANDBSCANgrow clusters from dense core pointsPCA vs t-SNEPCA vs t-SNEPCA keeps variance, t-SNE keeps neighboursk-means vs GMMk-means vs GMMhard circles vs soft covariance ellipsesEM algorithmEM algorithmE: soft labels, M: refit; ℓ never dropsHierarchical clusteringHierarchical clusteringMerge closest pair; cut the dendrogramMatrix factorization recsMatrix factorization recsRatings ≈ user vectors · item vectorsCollaborative FilteringCollaborative FilteringSimilar users' ratings fill the empty cellOpen the Machine Learning mind mapMachine Learningfind structure without labelsUnsupervisedK-meansK-meansassign to nearest centroid, move centroidK-Medoids and SilhouetteReal points as centres; pick k by avg sApriori RulesApriori RulesSubset not frequent → skip the supersetDBSCANDBSCANgrow clusters from dense core pointsPCA vs t-SNEPCA vs t-SNEPCA keeps variance, t-SNE keeps neighboursk-means vs GMMk-means vs GMMhard circles vs soft covariance ellipsesEM algorithmEM algorithmE: soft labels, M: refit; ℓ never dropsHierarchical clusteringHierarchical clusteringMerge closest pair; cut the dendrogramMatrix factorization recsMatrix factorization recsRatings ≈ user vectors · item vectorsCollaborative FilteringCollaborative FilteringSimilar users' ratings fill the empty cell
This page on the Machine Learning mind map · 81 pages in 10 branches · open it to see the whole map and test yourself in recall mode.