You can cluster any dataset with k-means — but first you have to tell it how many clusters to find. Nothing in the algorithm discovers k for you; you supply the number, and the method trusts it completely. So how do you choose?
The obvious first instinct is to measure how tight the clusters are and pick the k that makes them tightest. That tightness score is inertia — the total squared distance from every point to its centre, the very quantity k-means spends its whole loop driving down. Smaller inertia means points sit closer to their centres, which sounds like better clustering. There is a catch, and it is a large one: inertia can only fall as k grows. Split one cluster into two and every point can only end up nearer to a centre, never farther. So if you simply minimise inertia, the algorithm cheerfully reports that the best number of clusters is one per point — inertia zero, and entirely useless.
flowchart LR A["k = 1<br/>inertia high"] --> B["k = 2<br/>big drop"] B --> C["k = 3<br/>smaller drop"] C --> D["k = 4, 5, 6<br/>nearly flat"] D --> E["the elbow<br/>sits near k = 3"] style B fill:#b45309,color:#fff style E fill:#166534,color:#fff
Why the minimum is a trap
Add a cluster and inertia stays the same or drops — it can never rise. Push k all the way up to the number of points and every point becomes its own cluster of one, sitting exactly on its centre, for an inertia of zero. By the minimise-inertia rule, that degenerate answer is the best possible, which tells you the rule is broken, not that the answer is good.
The cure is to stop hunting for the minimum and start looking for the bend. Plot inertia against k and the curve falls steeply at first, then levels off. The point where it stops dropping fast — the kink in the curve — is called the elbow, and it is the heuristic every practitioner reaches for first.
import math, random
def distance(p, q):
return math.sqrt(sum((a - b) ** 2 for a, b in zip(p, q)))
def assign(points, centers):
labels = []
for p in points:
best, best_d = 0, distance(p, centers[0])
for i in range(1, len(centers)):
d = distance(p, centers[i])
if d < best_d:
best, best_d = i, d
labels.append(best)
return labels
def update(points, labels, k):
new_centers = []
for c in range(k):
members = [points[i] for i in range(len(points)) if labels[i] == c]
centroid = tuple(sum(m[d] for m in members) / len(members) for d in range(len(members[0])))
new_centers.append(centroid)
return new_centers
def kmeans(points, k, seed=0, max_iters=100):
rng = random.Random(seed)
centers = rng.sample(list(points), k)
for _ in range(max_iters):
labels = assign(points, centers)
new_centers = update(points, labels, k)
if new_centers == centers:
break
centers = new_centers
labels = assign(points, centers)
return centers, labels
def inertia(points, centers, labels):
total = 0.0
for p, l in zip(points, labels):
c = centers[l]
total += sum((p[d] - c[d]) ** 2 for d in range(len(p)))
return total
data = [(0, 0), (1, 0), (0, 1), (1, 1),
(10, 10), (11, 10), (10, 11), (11, 11),
(20, 0), (21, 0), (20, 1), (21, 1)]
for k in range(1, 7):
centers, labels = kmeans(data, k, seed=0)
print('k =', k, ' inertia =', round(inertia(data, centers, labels), 1))
Reading the elbow
Run that curve and watch the numbers. With three genuine clusters in the data, inertia plummets as k climbs from one to three, then barely moves for k = four, five, and six — those extra clusters are slicing existing groups into pieces and buying almost nothing in tightness. The elbow sits where the free reductions run out.
The successive drops make the bend easier to see than the raw curve. The gap between consecutive inertials is large while each new cluster captures a real group, then collapses to a trickle once you are just subdividing. That collapse is the elbow, plain to read off a short list of differences.
# A typical inertia curve for data with three natural clusters:
inertias = [600.0, 300.0, 60.0, 40.0, 28.0, 22.0]
for k in range(1, len(inertias)):
drop = round(inertias[k - 1] - inertias[k], 1)
print('k', k, '->', k + 1, ' drops by', drop)
flowchart TD Q["add a cluster"] --> R["inertia can only<br/>stay the same or drop"] R --> P["so k = number of points<br/>gives inertia zero"] P --> W["minimising inertia<br/>picks a useless k"] style W fill:#b91c1c,color:#fff
def inertia_at(points, centers, labels):
return sum(sum((p[d] - centers[l][d]) ** 2 for d in range(len(p))) for p, l in zip(points, labels))
pts = [(0, 0), (2, 0), (4, 0), (6, 0)]
print('k=1:', inertia_at(pts, [(3, 0)], [0, 0, 0, 0]))
print('k=2:', inertia_at(pts, [(1, 0), (5, 0)], [0, 0, 1, 1]))
print('k=4:', inertia_at(pts, pts, [0, 1, 2, 3]))
Heuristics help, judgement decides
A handy shortcut is to find the k with the largest single drop — the step where adding a cluster paid off the most. It is quick to compute and often lands near the elbow, but treat it as a hint, not an oracle: the very first drop is frequently the biggest, because going from one cluster to two removes the most variance, so a naive biggest-drop rule can point a little low. Use it to shortlist, then look at the curve and the points.
That last step — looking at the points — is the one no formula replaces. Inertia and its elbow summarise tightness, but tightness alone cannot tell you whether the clusters are meaningful, well separated, or aligned with anything you care about. Validation closes the gap: a scatter plot of the clusters, a silhouette score, or simply asking whether the groups are actionable.
flowchart TD D["draw inertia vs k"] --> L["look for the kink<br/>where drops shrink"] L --> J["several k may look<br/>equally defensible"] J --> C["context and validation,<br/>not just the curve, decide"] style J fill:#b45309,color:#fff style C fill:#3776ab,color:#fff
What does this print? Each entry is the drop from one k to the next.
inertias = [100.0, 60.0, 30.0, 25.0] drops = [inertias[i - 1] - inertias[i] for i in range(1, len(inertias))] print([round(d, 1) for d in drops])
Drop from k=1 to k=2 is 100 - 60 = 40.
Then 60 - 30 = 30, and 30 - 25 = 5.
Using the provided kmeans and inertia, write inertias_for_k(points, max_k, seed=0) that returns a list of the inertia for k = 1, 2, ..., max_k (one k-means run per value of k).
import math, random
def distance(p, q):
return math.sqrt(sum((a - b) ** 2 for a, b in zip(p, q)))
def assign(points, centers):
labels = []
for p in points:
best, best_d = 0, distance(p, centers[0])
for i in range(1, len(centers)):
d = distance(p, centers[i])
if d < best_d:
best, best_d = i, d
labels.append(best)
return labels
def update(points, labels, k):
new_centers = []
for c in range(k):
members = [points[i] for i in range(len(points)) if labels[i] == c]
centroid = tuple(sum(m[d] for m in members) / len(members) for d in range(len(members[0])))
new_centers.append(centroid)
return new_centers
def kmeans(points, k, seed=0, max_iters=100):
rng = random.Random(seed)
centers = rng.sample(list(points), k)
for _ in range(max_iters):
labels = assign(points, centers)
new_centers = update(points, labels, k)
if new_centers == centers:
break
centers = new_centers
labels = assign(points, centers)
return centers, labels
def inertia(points, centers, labels):
total = 0.0
for p, l in zip(points, labels):
c = centers[l]
total += sum((p[d] - c[d]) ** 2 for d in range(len(p)))
return total
def inertias_for_k(points, max_k, seed=0):
# one inertia value for each k in 1..max_k
pass
Loop k from 1 to max_k inclusive: range(1, max_k + 1).
For each k, run kmeans(points, k, seed=seed), then inertia(points, centers, labels), and collect the result.
import math, random
def distance(p, q):
return math.sqrt(sum((a - b) ** 2 for a, b in zip(p, q)))
def assign(points, centers):
labels = []
for p in points:
best, best_d = 0, distance(p, centers[0])
for i in range(1, len(centers)):
d = distance(p, centers[i])
if d < best_d:
best, best_d = i, d
labels.append(best)
return labels
def update(points, labels, k):
new_centers = []
for c in range(k):
members = [points[i] for i in range(len(points)) if labels[i] == c]
centroid = tuple(sum(m[d] for m in members) / len(members) for d in range(len(members[0])))
new_centers.append(centroid)
return new_centers
def kmeans(points, k, seed=0, max_iters=100):
rng = random.Random(seed)
centers = rng.sample(list(points), k)
for _ in range(max_iters):
labels = assign(points, centers)
new_centers = update(points, labels, k)
if new_centers == centers:
break
centers = new_centers
labels = assign(points, centers)
return centers, labels
def inertia(points, centers, labels):
total = 0.0
for p, l in zip(points, labels):
c = centers[l]
total += sum((p[d] - c[d]) ** 2 for d in range(len(p)))
return total
def inertias_for_k(points, max_k, seed=0):
result = []
for k in range(1, max_k + 1):
centers, labels = kmeans(points, k, seed=seed)
result.append(inertia(points, centers, labels))
return result
This drops function subtracts in the wrong order, so every drop comes out negative — the elbow would look upside down. Fix the subtraction so each entry is the drop from one k to the next.
def drops(values):
# bug: subtracts in the wrong order -> negative drops
return [round(values[i] - values[i - 1], 4) for i in range(1, len(values))]
A drop is how much the value fell: the earlier minus the later.
Use values[i - 1] - values[i], not the reverse.
def drops(values):
return [round(values[i - 1] - values[i], 4) for i in range(1, len(values))]
Write biggest_drop_k(values) returning the k (counting from 2) where the inertia dropped the most from the previous k. Compute the drops, find the index of the largest, and add 2 — because the drop at index 0 is the step from k=1 to k=2. This is a rough elbow hint, not a verdict.
def biggest_drop_k(values):
# k (from 2) at which inertia dropped the most
pass
Build the drops: values[i] - values[i + 1] for each adjacent pair.
Track the index of the largest drop, then return that index plus 2.
def biggest_drop_k(values):
drops = [values[i] - values[i + 1] for i in range(len(values) - 1)]
best = 0
for i in range(1, len(drops)):
if drops[i] > drops[best]:
best = i
return best + 2
Why can you NOT choose k by picking the value that gives the smallest inertia?
Each extra cluster can only move points closer to a centre, so inertia is non-increasing in k. Minimising it trivially picks k equal to the number of points — one cluster each, inertia zero — which is useless. That is why we read the elbow, not the minimum.
Recap
- K-means needs k handed to it; the algorithm does not discover the number of clusters.
- Inertia — total squared distance from points to their centres — measures cluster tightness, but it is non-increasing in k, so minimising it always picks one cluster per point.
- The elbow method plots inertia against k and looks for the kink where the curve stops falling fast.
- Reading the drops between successive k makes the bend easier to spot than the raw curve.
- A naive biggest-drop rule is a quick hint, not an answer; the real choice needs validation — scatter plots, silhouette scores, and domain judgment.
K is a judgement call, and so is trusting any single clustering of unlabelled data. The next lesson makes that danger concrete: k-means always assumes clusters are round, and roundly fails when they are not.