K-means and K-medoids
K-means partitions data by minimising within-cluster squared Euclidean distance using centroids; K-medoids is a robust variant that uses actual data points (medoids) and minimises sum of pairwise distances.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Clustering groups unlabeled data into sets (clusters) that are internally similar and externally different. Engineers use K-means for fast, simple partitioning (image segmentation, vector quantisation, customer segmentation) and use K-medoids when outliers or non-Euclidean distances make centroid means inappropriate.
Key ideas
The objective (exact statement): minimize J = sum_{i=1..k} sum_{x in Ci} ||x − μi||^2, where ||·|| is the Euclidean norm. Assumes Euclidean geometry and real-valued vector features. Exact minimization of this objective is NP-hard in general, so heuristics like Lloyd's algorithm are used to find a local minimum.
Lloyd's algorithm (standard K-means algorithm): iteratively performs two steps until convergence:
- Assignment step: assign each point x to the nearest centroid: assign x to cluster j = argmin_{i} ||x − μi||^2.
- Update step: for each cluster i set μi = (1/|Ci|) sum_{x in Ci} x (the mean of the cluster).
- Assumes clusters non-empty; if a cluster becomes empty, typical fixes are: reinitialise its centroid to a random point, or to the farthest point from existing centroids.
- Convergence guarantee: Lloyd's algorithm monotonically decreases J at each step and converges to a local minimum (not necessarily global). Proof follows because assignment reduces J for fixed centroids, and mean update minimizes J for fixed assignments (see derivation below).
Derivation of centroid update (theorem and proof exam-style):
- Theorem: For fixed cluster Ci, the point μ that minimises sum_{x in Ci} ||x − μ||^2 is μ = (1/|Ci|) sum_{x in Ci} x.
- Proof (standard): write f(μ) = sum ||x − μ||^2 = sum (||x||^2 − 2 x·μ + ||μ||^2) = constant − 2( sum x )·μ + |Ci| ||μ||^2. Differentiate w.r.t μ and set gradient to zero: −2 sum x + 2 |Ci| μ = 0, so μ = (1/|Ci|) sum x. QED.
K-medoids (definition): similar partitioning but each cluster i is represented by a medoid mi which is one of the actual data points in Ci. The objective is to minimize sum_{i=1..k} sum_{x in Ci} d(x, mi) for a chosen distance d (often Euclidean or Manhattan). Because medoids are actual points, K-medoids is more robust to outliers.
Partitioning Around Medoids (PAM) algorithm (high level):
- Initialise: choose k data points as medoids.
- Assign each non-medoid to nearest medoid by d(·,·).
- For each medoid m and each non-medoid o consider swapping m and o; accept swap if total cost decreases.
- Repeat until no swap decreases cost.
- PAM finds a local minimum of the medoid objective. It is more computationally expensive than K-means (pairwise distances and swaps).
Properties and practical points:
- K-means assumes spherical, equal-variance clusters in Euclidean space; it is sensitive to outliers and initialisation.
- K-medoids works with arbitrary distance metrics and is robust to outliers but usually slower (O(k(N−k)^2) per PAM iteration in a naive implementation). By contrast, one Lloyd iteration for K-means costs O(N k d) for N points in R^d.
- Common initialisation for K-means: random, or K-means++ (probabilistic seeding to improve final J). K-means++ reduces bad initialisations by seeding each new centroid with probability proportional to the squared distance to the nearest existing centroid. Choosing k is model selection; common methods include the elbow plot and the silhouette score.
Diagram to draw for exam: draw 2D scatter of points that form two clear groups. Mark two initial centroids (label μ1, μ2). Draw arrows from each point to its assigned centroid. After update, draw new centroids and show reduced within-cluster SSE. Label axes x1, x2, and annotate centroid coordinates.
Formulas
J = Σ_{i=1..k} Σ_{x∈Ci} ||x − μi||^2 — J is the K-means objective (sum of squared errors), μi is centroid i, units: (feature units)^2, applies for Euclidean distance.
μi = (1/|Ci|) Σ_{x∈Ci} x — centroid update; μi in same units as xi; applies when minimizing sum of squared Euclidean distances for fixed cluster Ci.
Assignment: Ci = { x : i = argmin_j ||x − μj||^2 } — cluster membership by nearest centroid (ties broken arbitrarily), units same as xi.
K−medoids objective: J_medoid = Σ_{i=1..k} Σ_{x∈Ci} d(x, mi) — d(·,·) is a distance (units of features), mi is medoid (actual data point), applies to robust clustering with arbitrary distance.
Euclidean distance: d(x,y) = sqrt( Σ_{j=1..d} (x_j − y_j)^2 ) — units same as features.
Worked examples
Example 1 — K-means numeric (step-by-step, k=2). Data in 2D (units: units): Points: P1=(1,1), P2=(1.5,2), P3=(3,4), P4=(5,7), P5=(3.5,5), P6=(4.5,5). Initialise μ1=P1=(1,1), μ2=P4=(5,7). Step 1 — Assign points (Euclidean distance):
- Distances (rounded): P1→μ1:0, P1→μ2:7.211 → assign C1.
- P2→μ1:1.118, P2→μ2:6.103 → C1.
- P3→μ1:3.606, P3→μ2:3.606 → tie; choose C1 (or either).
- P4→μ2:0 → C2.
- P5→μ1:4.717, P5→μ2:2.500 → C2.
- P6→μ1:5.316, P6→μ2:2.062 → C2.
Clusters: C1={P1,P2,P3}, C2={P4,P5,P6}.
Step 2 — Update centroids: means of each cluster:
μ1 = ((1+1.5+3)/3, (1+2+4)/3) = (1.8333, 2.3333)μ2 = ((5+3.5+4.5)/3, (7+5+5)/3) = (4.3333, 5.6667)Step 3 — Reassign with new centroids (compute distances; rounding): - All P1,P2,P3 remain nearer to μ1; P4,P5,P6 nearer to μ2. No change → converged. Final centroids: μ1 = (1.8333, 2.3333), μ2 = (4.3333, 5.6667).
Example 2 — K-medoids (PAM) with same data (Python program). This produces medoids that are actual data points. Code (complete):
# K-medoids (simple PAM) for small dataset
import math
points = [(1,1),(1.5,2),(3,4),(5,7),(3.5,5),(4.5,5)]
k = 2
def dist(a,b):
return math.hypot(a[0]-b[0], a[1]-b[1])
# initialise medoids: pick first k points
medoids = [points[0], points[3]]
def assign(meds):
clusters = {m: [] for m in meds}
for p in points:
nearest = min(meds, key=lambda m: dist(p,m))
clusters[nearest].append(p)
return clusters
# compute total cost
def total_cost(meds, clusters):
return sum(dist(p, m) for m, pts in clusters.items() for p in pts)
clusters = assign(medoids)
current_cost = total_cost(medoids, clusters)
improved = True
while improved:
improved = False
for i, m in enumerate(medoids):
for o in points:
if o in medoids: continue
trial = medoids.copy()
trial[i] = o
trial_clusters = assign(trial)
trial_cost = total_cost(trial, trial_clusters)
if trial_cost < current_cost:
medoids = trial
clusters = trial_clusters
current_cost = trial_cost
improved = True
break
if improved:
break
print('Medoids:', medoids)
print('Clusters:')
for m, pts in clusters.items():
print(m, '->', pts)
Sample exact output when run (order of medoids as in code): Medoids: [(1.5, 2), (3.5, 5)] Clusters: (1.5, 2) -> [(1, 1), (1.5, 2)] (3.5, 5) -> [(3, 4), (5, 7), (3.5, 5), (4.5, 5)]
So final medoids are (1.5, 2) and (3.5, 5); these clusters do not exactly match the K-means partition in this example (point (3, 4) joins the second cluster).
Common mistakes
- Confusing centroid (not necessarily a data point) with medoid (must be a data point).
- Forgetting to handle empty clusters after an assignment step.
- Not scaling features: different feature scales distort Euclidean distances — always standardise/normalise when features have different units.
- For K-medoids: forgetting that it uses pairwise distances and that complexity is higher; naive PAM can be slow for large N.
For your exam
Typical question types:
- Definitions: define clustering, K-means objective, centroid, medoid and state assumptions.
- Short notes: describe Lloyd's algorithm, K-means++ initialisation, and pros/cons of K-means vs K-medoids.
- Derivations: show that the mean minimises sum of squared distances (differentiate objective and solve for μ).
- Numericals: run one or two iterations of K-means on a small 2D dataset, provide centroid updates and final clusters.
- Programs: write simple code for K-means or a small PAM implementation for K-medoids.
- Diagrams: draw data points, initial centroids, assignment arrows, updated centroids, annotate reduction in SSE. What a full-marks answer includes: clear statement of definitions with bold names, step-by-step algorithm, derivation using calculus for centroid update, careful numeric steps with distances shown and rounding, and a discussion of limitations and complexity.
Quick check
- State the K-means objective function symbolically.
- Why is K-medoids preferred over K-means when outliers are present?
- Give one correct method to initialise centroids for K-means to reduce bad local minima.
Answers: 1. J = Σ_{i=1..k} Σ_{x∈Ci} ||x − μi||^2. 2. Because medoids are actual data points and the objective uses distances (not squared), making it robust to outliers. 3. K-means++ (probabilistic seeding) or multiple random restarts and choose best final J.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?