Why is k-medoids more robust to outliers than k-means, and what does that robustness cost?
answer
- a mean is not the only summary
- the centre is an actual observation
- sums distances instead of squaring them
- needs only pairwise dissimilarities
- every candidate swap gets scored
basics
~20 sk-medoids uses an actual data point as each cluster centre and minimises the sum of distances to it, so one extreme value cannot drag the centre the way a mean can. The price is a far slower, roughly quadratic search.
solid answer
~40 sk-means sets each centre to the mean of its members and minimises squared distance, so an extreme point has quadratic leverage and pulls the centre toward itself. k-medoids instead requires the centre — the medoid — to be one of the observations, and minimises the sum of unsquared distances, so a far-away point contributes linearly and cannot invent a centre that sits where no data lives. That also makes the medoid a showable exemplar: on a B2B revenue table, one billion-dollar account skews a centroid into empty space, while the medoid stays a real account you can name to sales. Two costs. First, PAM's swap search is roughly `O(k*(n-k)^2)` work per iteration, versus linear-per-iteration for k-means. Second, it usually needs the full pairwise distance matrix, which is `O(n^2)` memory.
code
python · 14 linespoints = [1.0, 2.0, 3.0, 4.0, 500.0]
mean = sum(points) / len(points)
def total_distance(candidate):
return sum(abs(candidate - p) for p in points)
# the medoid must itself be one of the observed points
medoid = min(points, key=total_distance)
print("mean:", mean) # 102.0
print("medoid:", medoid) # 3.0
print("cost at mean:", total_distance(mean)) # 796.0
print("cost at medoid:", total_distance(medoid)) # 501.0go deeper
Recall the one-sentence contrast: the k-means centre is an average that may sit where no data point lies, the k-medoids centre is one of your actual rows. Be able to say why an extreme value moves the first and not the second.
Explain both halves of the mechanism — the centre is constrained to an observation, and the objective sums plain distances rather than squared ones — and describe PAM's build-then-swap loop well enough that the quadratic cost is obvious from your description.
Show you would check feasibility before proposing it: distance-matrix memory at your row count, the swap cost per iteration, and the sampling fallback. Interviewers want to hear you weigh a nameable exemplar for stakeholders against a slower, harder-to-rerun job.
Own the framing question: is outlier robustness the real requirement, or is it explainability to a business audience? Those pull toward different answers, and the cheap compromise — cluster with the fast method, report real exemplars — is worth putting on the table before anyone builds an n-squared matrix.
## The one-line difference Both methods partition `n` points into `k` groups by repeatedly assigning points to the nearest centre and then recomputing the centres. They differ in **what a centre is allowed to be** and **what quantity is being minimised**. - **k-means**: the centre of a cluster is the arithmetic mean of its members. It is generally *not* one of the data points. The objective is the total **squared** distance from each point to its assigned centre. - **k-medoids**: the centre — called the **medoid** — must be one of the actual observations. The objective is the total **unsquared** distance (more generally, dissimilarity) from each point to its assigned medoid. ## Why that makes it robust Robustness comes from both changes at once, and candidates usually only name one. 1. **Squared versus unsquared cost.** Squaring gives a point that is 10 units away 100 units of influence, and a point 100 units away 10,000 units. Minimising a sum of *unsquared* distances is the same reason a median resists outliers where a mean does not: an extreme value's pull grows linearly, not quadratically. 2. **The centre must be an observation.** Even under a robust cost, the mean is free to move anywhere in the space. A medoid can only ever be a point you actually collected, so it physically cannot land in an empty region. Concretely: a B2B revenue table where thousands of accounts bill five figures and one billion-dollar account sits alone. The centroid of the cluster containing that account is dragged into a revenue band where no customer exists, and every downstream segment description built from it is fiction. The medoid stays a real, nameable account — which is also why account teams find medoid segments easier to act on. ## The second superpower: arbitrary dissimilarities Computing a mean requires coordinates you can average. k-medoids never averages anything — it only ever asks *how far is point i from point j*. So it runs on **any** pairwise dissimilarity matrix, including ones where averaging is undefined: mixed-type property listings (numeric price, categorical property type, ordinal condition) scored with a mixed-type dissimilarity such as Gower, edit distances between strings, or a similarity a domain expert hand-built. Hand k-means the same matrix and there is nothing for it to do, because there is no space in which to place a mean. ## PAM, the classical algorithm PAM (Partitioning Around Medoids) has two phases. - **BUILD**: greedily choose k initial medoids, each time taking the point that most reduces total cost given the ones already chosen. - **SWAP**: consider every pair (current medoid, non-medoid), compute what the total cost would be if they traded roles, apply the single swap that reduces cost most, and repeat until no swap improves the objective. That is the expensive part. There are `k*(n-k)` candidate swaps and evaluating each one touches the assignment cost of the remaining points, giving roughly `O(k*(n-k)^2)` per SWAP iteration — quadratic in `n`. k-means, by contrast, does `O(n*k*d)` work per iteration. Add the `O(n^2)` memory for the distance matrix and PAM stops being usable somewhere in the low hundreds of thousands of rows, well before k-means struggles. The standard escapes are sampling-based: **CLARA** runs PAM on repeated random subsamples and keeps the medoid set that scores best on the full data. If you only need the *exemplar* property and not the robust objective, a cheaper trick is to run k-means and then report, for each centroid, the nearest real observation — a good enough exemplar, though the partition itself is still the non-robust one. ## Things that do not change k-medoids still needs `k` chosen up front, still converges only to a local optimum, and still gives spherical-ish, roughly equal-diameter clusters under a Euclidean dissimilarity. Swapping the centre definition fixes outlier sensitivity and the coordinate requirement — it does not turn a partitioning method into a density-based one. ## Interview shape A strong answer names the medoid as an observed point, names the unsquared objective, mentions that only pairwise dissimilarities are needed, and then volunteers the quadratic cost before being asked. A weak answer says only "it uses the median instead of the mean" — which describes a different method (coordinate-wise medians, k-medians) and misses that the medoid is a whole observation, not a per-feature summary.
- Why can k-medoids run on a precomputed mixed-type distance matrix when k-means cannot?k-medoids only ever asks how far one point is from another; it never averages coordinates. So a table of property listings mixing numeric price, categorical type and ordinal condition can be reduced to an `n x n` dissimilarity matrix and clustered directly. k-means must compute a mean, which requires a coordinate space where averaging the columns is meaningful — a dissimilarity matrix gives it nothing to average.
- PAM is too slow on your two million rows. What do you actually ship?Two options. Run a sampling variant such as CLARA: PAM on repeated random subsamples, keeping the medoid set with the best cost on the full data — you lose the guarantee of a globally best swap but keep the robust objective and the real-observation centres. Or, if you only need nameable exemplars, run k-means and report the nearest real observation to each centroid, accepting that the partition itself is still outlier-sensitive.
- Does switching to k-medoids remove the need to decide how many clusters you want?No. k-medoids is a partitioning method with `k` fixed in advance, exactly like k-means, and it still converges only to a local optimum of its objective. Changing what a centre is fixes outlier leverage and the coordinate requirement; it says nothing about how many groups exist in the data.
Picking a meeting point for a team: the mean is a GPS coordinate that may land in the middle of a lake, and one colleague who moved abroad shifts it hundreds of kilometres. The medoid is "we meet at Ana's office" — always a real address, and the distant colleague changes nothing.
saying these in an interview costs you the question
- Says a k-means centroid is always one of the data points
- Calls the medoid the per-feature median of the cluster
- Claims k-medoids and k-means cost about the same to run
- Thinks k-medoids only works with Euclidean distance
- Believes k-medoids removes the need to fix k in advance
- Says medoids make the clusters non-spherical