K-means is an optimist. Hand it a dataset and a number k, and it always comes back with exactly k clusters and a tidy score for how tight they are. It never says it cannot find any structure here. That sounds helpful until you meet data whose real groups are not the round, evenly sized blobs the algorithm imagines, at which point that same confidence becomes the trap. This lesson is about the moment clustering stops being a convenience and starts lying to you, and about the single geometric reason behind almost every k-means failure you will ever meet.
flowchart LR P["each point"] -->|"sent to nearest center"| C["a cluster center"] C -.->|"boundary is the perpendicular<br/>bisector of two centers"| L["a straight line"] L --> E["the plane is carved into<br/>straight-edged convex cells"] E --> F["a ring is non-convex:<br/>no straight-edged cell can hold it"] style C fill:#10b981,color:#fff style F fill:#b91c1c,color:#fff
Why the cuts are always straight
K-means sends every point to its nearest center by straight-line Euclidean distance. Take any two neighbouring centers and ask where the tie is: the set of points equally close to both is the perpendicular bisector of the segment joining them, which is a straight line. Stitch those lines together and the whole plane is divided into convex polygonal cells, one per center. This Voronoi tessellation is not a choice the algorithm makes, it is a direct consequence of nearest-center assignment. A convex cell has no dents, so it can hold a round blob but never a ring, a crescent, or any shape with a hole or a bend in it. The geometry forbids such shapes before a single update runs.
def sq_dist(a, b):
return sum((x - y) ** 2 for x, y in zip(a, b))
c0 = [0, 0]
c1 = [4, 0]
for x in range(-1, 6):
p = [x, 2]
winner = 0 if sq_dist(p, c0) < sq_dist(p, c1) else 1
print('point', p, '-> cluster', winner)
Two centers sit on the x-axis, and the winner flips at a single vertical line, the perpendicular bisector. For data that is itself round and spread out, a handful of straight cuts is exactly the right tool. The next block shows k-means succeeding on exactly that kind of data.
def sq_dist(a, b):
return sum((x - y) ** 2 for x, y in zip(a, b))
def assign(points, centers):
out = []
for p in points:
best, best_d = 0, sq_dist(p, centers[0])
for i in range(1, len(centers)):
d = sq_dist(p, centers[i])
if d < best_d:
best, best_d = i, d
out.append(best)
return out
def update(points, labels, k):
centers = []
for c in range(k):
members = [points[i] for i in range(len(points)) if labels[i] == c]
if members:
centers.append([sum(m[d] for m in members) / len(members) for d in range(len(members[0]))])
else:
centers.append([0.0, 0.0])
return centers
def kmeans(points, centers, iters=25):
for _ in range(iters):
labels = assign(points, centers)
centers = update(points, labels, len(centers))
return assign(points, centers)
blob_a = [[0, 0], [1, 0], [0, 1], [1, 1]]
blob_b = [[10, 10], [11, 10], [10, 11], [11, 11]]
labels = kmeans(blob_a + blob_b, [[0, 0], [10, 10]])
print('blob A point -> cluster', labels[0])
print('blob B point -> cluster', labels[4])
Two clean blobs, each a tight square of four points, sit far apart. K-means finds them perfectly: one cluster swallows the first blob, the other the second. This is the happy path, and it is the picture every clustering tutorial leads with. Now keep the identical algorithm and feed it data whose true structure is not a pair of blobs at all.
import math
def sq_dist(a, b):
return sum((x - y) ** 2 for x, y in zip(a, b))
def assign(points, centers):
out = []
for p in points:
out.append(min(range(len(centers)), key=lambda i: sq_dist(p, centers[i])))
return out
def update(points, labels, k):
centers = []
for c in range(k):
members = [points[i] for i in range(len(points)) if labels[i] == c]
if members:
centers.append([sum(m[d] for m in members) / len(members) for d in range(len(members[0]))])
else:
centers.append([0.0, 0.0])
return centers
def ring(radius, n, offset_deg=22.5):
off = math.radians(offset_deg)
return [[radius * math.cos(off + 2 * math.pi * i / n), radius * math.sin(off + 2 * math.pi * i / n)] for i in range(n)]
inner = ring(1.0, 8)
outer = ring(3.0, 8)
points = inner + outer
centers = [[3.0, 0.0], [-3.0, 0.0]]
for _ in range(10):
labels = assign(points, centers)
centers = update(points, labels, 2)
labels = assign(points, centers)
for c in (0, 1):
inner_n = sum(1 for i in range(8) if labels[i] == c)
outer_n = sum(1 for i in range(8, 16) if labels[i] == c)
print('cluster', c, '-> inner:', inner_n, 'outer:', outer_n)
Reading the failure
The data is two concentric rings: eight points on a small circle and eight on a larger one around it, so the natural grouping is inner ring against outer ring. Yet each found cluster contains four inner and four outer points. Neither cluster is a clean ring. Instead of separating the two rings, k-means drew a straight line through the centre and sliced both of them in half, the way a knife through a pair of onion rings cuts each ring into two arcs. That is the Voronoi geometry from the first figure doing exactly what it must. The algorithm did not glitch and the initialisation is fixed; it behaved correctly under an assumption the data violates.
flowchart TD T["true structure:<br/>an inner ring and an outer ring"] --> K["k-means with k equals 2"] K --> S["result: one straight cut<br/>slices BOTH rings in half"] S --> M["each found cluster mixes<br/>inner and outer points"] style T fill:#166534,color:#fff style S fill:#b91c1c,color:#fff
The assumptions, and what to reach for instead
The algorithm quietly assumes clusters are roughly spherical, similarly sized, and similarly dense, because that is the shape its mean-and-distance objective rewards. When those hold, nothing beats it for speed and simplicity. When they break, you need a different notion of similarity, not a different k. Density-based methods like DBSCAN grow clusters out of crowded regions and can follow a ring or a bent shape, ignoring the empty middle. Spectral clustering reframes the points as a graph of which neighbours connect and then cuts that graph, capturing structure straight-line distance cannot see. Each tool encodes a different assumption about what a cluster is, and the real skill is matching that assumption to the data in front of you.
There is one more way k-means can mislead even on friendly data. Its result depends on where the centers start, so two different random seeds can land on two different clusterings of the same points, both locally optimal. Seeding fixes a single run for reproducibility, and smarter initialisation reduces the problem, but neither erases it. Whenever a clustering decision matters, run several seeds and compare, and never treat a single run as the answer.
flowchart TD D["data shape"] --> B["round, similarly-sized blobs"] D --> R["concentric rings or moons"] D --> V["uneven density, with noise"] B --> KM["k-means works well"] R --> SP["spectral clustering or DBSCAN"] V --> DB["DBSCAN"] style KM fill:#166534,color:#fff style SP fill:#b45309,color:#fff style DB fill:#b45309,color:#fff
Write sq_dist(a, b) returning the squared straight-line distance between two equal-length points: the sum of the squared coordinate differences.
def sq_dist(a, b):
# sum of (a[i] - b[i]) squared
pass
Pair up coordinates with zip, then square each difference.
Sum the squared differences; do not take a square root.
def sq_dist(a, b):
return sum((x - y) ** 2 for x, y in zip(a, b))
What does this print? Four points sit in a ring around the origin. If k-means assigns all four to one cluster and moves that center to their mean, where does the center land?
pts = [[1, 0], [0, 1], [-1, 0], [0, -1]] cx = sum(p[0] for p in pts) / len(pts) cy = sum(p[1] for p in pts) / len(pts) print(round(cx, 2), round(cy, 2))
The x-coordinates are 1, 0, -1, 0, which add up to 0.
A symmetric ring has its mean at the empty centre, not on any point.
This assign sends each point to the FARTHEST center (it uses max), so the clusters explode. K-means assigns each point to its NEAREST center. Fix the one word so points join their closest center.
def assign(point, centers):
return max(range(len(centers)), key=lambda i: sum((point[j] - centers[i][j]) ** 2 for j in range(len(point))))
Nearest means the smallest squared distance, not the largest.
Change max to min.
def assign(point, centers):
return min(range(len(centers)), key=lambda i: sum((point[j] - centers[i][j]) ** 2 for j in range(len(point))))
Write inertia(points, labels, centers) returning the total within-cluster sum of squares: for each point, add the squared distance from that point to the center it was assigned to. labels[i] is the cluster index of points[i], and centers[c] is that cluster's center.
def inertia(points, labels, centers):
# for each point, add squared distance to centers[its label]
total = 0
pass
return total
Look up the center for each point with centers[label].
Sum the squared coordinate differences to that center, across all points.
def inertia(points, labels, centers):
total = 0
for p, c in zip(points, labels):
ctr = centers[c]
total += sum((p[j] - ctr[j]) ** 2 for j in range(len(p)))
return total
Why can k-means not separate two concentric rings into two clusters, no matter how you set k?
Nearest-center assignment produces straight, convex decision cells. A ring is non-convex with a hole in the middle, so no straight-edged cell can capture it, and the cut lands across both rings.
Recap
- K-means is confident by design: it always returns k clusters and a finite tightness score, even when no real structure exists.
- Its boundaries are straight lines (a Voronoi tessellation), so it can only carve the plane into convex cells and cannot represent rings, crescents, or any non-convex shape.
- It assumes spherical, similarly sized, similarly dense clusters; when the data violates that, reach for a different similarity model (DBSCAN, spectral), not a different k.
- Low inertia is not proof: the objective measures roundness, not truth, so always check a clustering against a plot or task.
- Seeds matter: different starts can give different clusterings, so compare several runs.
Next you will step back and ask what to do when your data has so many features that distance itself stops being meaningful, the problem dimensionality reduction exists to solve.