Why this session exists
k-means is the workhorse of clustering, and the field's best teachers vote with their syllabi: Andrew Ng's ML specialization teaches exactly one clustering algorithm - k-means - and Google's clustering course does the same. Their bet, and this course's bet, is that understanding one algorithm's two-step loop deeply beats knowing ten algorithms shallowly. After today you will know what k-means optimizes, why it always settles, why WHERE it starts decides WHERE it ends, and what modern scikit-learn actually does about that (spoiler: not what older tutorials say).
Lloyd's loop 8 min live
Here is the entire algorithm. Place k centroids somewhere. Then repeat two steps: (1) assign every point to its nearest centroid, (2) move each centroid to the average of its members - until assignments stop changing. That is ALL of k-means. Everything else you will ever read about it is commentary on these two steps.
LiveOne round, six imaginary customers4 min▶
Take six customers on a single scaled axis (call it "engagement"): A at 1, B at 2, C at 3, and X at 8, Y at 9, Z at 10. Two centroids start awkwardly at 4 and 6. Run one round by hand:
Assign. A, B, C are nearer to the centroid at 4 - they join it. X, Y, Z are nearer to 6 - they join that one. Every customer now has exactly one cluster.
Update. Centroid 1 moves to the average of A, B, C: (1+2+3)/3 = 2. Centroid 2 moves to the average of X, Y, Z: 9. Both centroids just jumped into the heart of their members.
Assign again. Everyone re-checks their nearest centroid... and nobody switches. Assignments unchanged - the loop stops. Two rounds, done.
| Round | Centroid 1 | Centroid 2 | What happened |
|---|---|---|---|
| Start | at 4 | at 6 | awkward guesses, near neither group |
| 1 · assign | gets A, B, C | gets X, Y, Z | memberships set by nearest-centroid |
| 1 · update | moves to 2 | moves to 9 | each jumps to its members' average |
| 2 · assign | keeps A, B, C | keeps X, Y, Z | nobody switches - the loop stops |
What did the loop optimize? Inertia: the within-cluster sum of squared distances - add up, for every customer, the squared distance to their own centroid. Assigning to the NEAREST centroid can only shrink those distances; moving a centroid to its members' AVERAGE is mathematically the spot that minimizes their squared distances. Each round can only lower inertia - which is exactly why k-means always settles and never oscillates forever.
Self-studyVoronoi territories: why the borders are straight3 min▶
"Assign every point to its nearest centroid" quietly draws a map. The set of locations closer to centroid 1 than to any other centroid is a territory; the border between two territories is the line exactly halfway between the two centroids - and halfway lines are STRAIGHT. This carving of space into nearest-centroid territories is called a Voronoi diagram, and it means k-means clusters are always separated by straight borders (flat planes, in more dimensions).
File this away for Part 3 and for session 5: any real group whose true boundary is curved - a crescent, a ring, an S - is a shape k-means literally cannot draw around. Not "struggles with." Cannot. Its borders have no curves in them.
Self-studyWhat a round costs (why k-means is everyone's default)2 min▶
Each round of the loop is honest arithmetic: measure the distance from every point to every centroid (assign), then average each cluster's members (update). No pairwise point-to-point comparisons, no tree building, no probability fitting - just points-times-centroids distance checks, a handful of rounds, done. That frugality is a big part of why Ng, Google, and half the BI tools on earth reach for k-means first: it is not just simple to explain, it is cheap to run at customer-base scale. Session 5's comparison card puts this in context - some of the rivals that fix k-means' blind spots pay for it in exactly this currency.
Where you start matters 6 min live
The loop only ever improves - and that is precisely its weakness. It rolls downhill on the inertia landscape and stops in the first valley it reaches. If the starting centroids are placed badly, that valley is a local optimum: a genuinely bad clustering that no amount of further looping will ever fix, because escaping it would require inertia to go UP first, and the loop cannot do that.
Livek-means++ decoded3 min▶
The classic fix has two flavors. The brute-force one: run the whole thing many times from different random starts and keep the run with the lowest inertia. The smart one is k-means++, and it is one sentence: place the first centroid at random, then pick each next centroid preferring points FAR from the centroids already placed.
Why that works: bad starts are almost always crowded starts - two centroids landing in the same real group, leaving another real group centroid-less. Spreading the initial centroids out makes each one likely to land near a different real group, so the loop starts near the deep valley instead of near a shallow one. It is not a guarantee - you will see a good start land at 85% truth match in the lab, not 100% - but it turns "pray" into "usually fine".
Self-studyThe landscape metaphor, made precise2 min▶
The valley picture above is not just a cartoon. Imagine every possible clustering of the 300 customers as a location, and the inertia of that clustering as the altitude there. Lloyd's loop is a walker on this landscape who can only step downhill: assign is one kind of downhill step, update is another. Convergence means reaching a spot where neither step goes down - a valley floor. Which floor you reach depends entirely on where the walker was dropped, and the landscape for five centroids has many valleys. Initialization is the drop point. That is all of Part 2 in one image.
Self-studyYour restart budget, in plain terms3 min▶
Three strategies, one decision: how much will you pay for insurance against a shallow valley?
| Strategy | What it does | When it fits |
|---|---|---|
| Random starts, many retries | run the full loop from many random drops, keep the lowest-inertia result | the old world - random drops crash often, so the old n_init=10 default bought ten tickets |
| k-means++, one run | one smart, spread-out start | sklearn's modern n_init='auto' - usually enough, as your 85% lab run shows |
| k-means++, best of N | several smart starts, keep the best | when the answer ships to marketing and must not wobble - our full-run labs use best-of-5 |
Notice the pattern: the smarter the start, the fewer retries you need. The two fixes trade against each other - which is exactly why sklearn's default retry count changed when its default initialization did.
n_init='auto', which for k-means++ initialization means ONE run - because a spread-out start usually does not need retries. The old default, n_init=10, was designed for RANDOM initialization, where ten retries were cheap insurance against crowded starts. Plenty of older tutorials still teach "always set n_init=10" as gospel without saying why. Now you know what the knob actually does: it is the brute-force fix, and k-means++ is the reason you rarely need it anymore.
What k-means assumes 4 min live
Averages and straight borders are not neutral machinery - they are a worldview. k-means implicitly assumes your real groups are round-ish blobs of roughly similar size, separable by straight lines. Our scaled Mango Lane pile happens to fit that worldview, which is why it works so well here. Not all data is so polite.
LiveThe worldview in three lines4 min▶
- Round-ish blobs: a centroid is an average, and an average is only a good summary of a group that clusters around its center. Stretched or curved groups have averages that sit in weird places - sometimes outside the group entirely.
- Similar sizes: a big sprawling group next to a tight small one tempts k-means to slice the big one in half and hand a piece to the small one's centroid, because that lowers inertia.
- Straight borders: the Voronoi territories from Part 1. Two crescent moons interlocking? k-means will draw one straight line through both and confidently report two clusters that each contain half of each moon.
| Assumption | Data that breaks it | Who handles it (session 5) |
|---|---|---|
| Round-ish blobs | stretched, curved, or ring-shaped groups | DBSCAN traces arbitrary shapes |
| Similar sizes | a sprawling group beside a tight one | GMM lets clusters own their spread |
| Straight borders | the two interlocking moons | DBSCAN again - it follows density, not lines |
Session 5 shows you those two moons live - and the algorithms (DBSCAN especially) that CAN trace curved shapes. Today's point is simpler: when k-means fails, it fails silently and confidently, because the loop always settles and always reports clusters.
Step the loop yourself 🥭 ★ 20 min · one press per round
The lab below runs REAL k-means on the scaled Mango Lane sample - but hands YOU the loop. Every press of ⏭ Step is one round: assignments, then centroid moves, then the new inertia. You will watch a good start settle, then manufacture a bad one and watch it trap itself, live.
Read the opening position. Five centroids have been placed by k-means++ - notice they are spread out across the PCA view of the scaled pile, not clumped. That spread is the whole trick, and it happened before a single round ran.
Press ⏭ Step repeatedly. Each round: customers join their nearest centroid, centroids walk to their members' average, and inertia falls. Watch it fall EVERY round - never rise - until the loop settles around 6 rounds at inertia 92, truth match about 85%. You just ran Lloyd's loop to convergence by hand.
Press ↺ Reset, then 🎲 Unlucky random start, then step about 10 times. The loop still behaves perfectly - inertia falls every round - but it settles PERMANENTLY at inertia 278, truth match 65%. Two centroids are sharing one real segment while two real segments share a centroid. Keep pressing: nothing will ever change. That is a local optimum, live.
Say the moral out loud. The unlucky run did not malfunction - the loop did exactly its job and rolled into the nearest valley. The fix is better STARTS: k-means++ placement or multiple restarts. Not paranoia, and not more looping. The full-run labs in the other sessions all use best-of-5 restarts for exactly this reason.
Compare across sessions. Today's single k-means++ run reached about 85% truth match; the best-of-5-restarts labs elsewhere reach 100% on the same pile. Even good starts vary - and choosing how many starts to pay for is precisely what sklearn's n_init knob is about. The stale-default callout from Part 2 should feel concrete now.
Homework 📝 ◐ 20 minutes
- Explain the loop with coins on a table. A handful of coins as customers, two bottle caps as centroids: assign, average, move, repeat. If you can run three rounds for a colleague and they can predict the fourth, you both own the algorithm.
- Write three sentences on why inertia can never rise during the loop. One sentence per step (why assignment can only lower it, why the update can only lower it), one for the conclusion (why the loop must settle). This is the session's core logic in your own words.
- Find k-means hiding in a BI tool you use. Clustering buttons in dashboards, "auto-segment" features, spreadsheet add-ins - many are k-means under a friendlier name. Check whether the tool lets you see (or set) the initialization or number of runs. Most hide it - now you know what is hidden.
Three questions before you go 🎯 ◐ 90 seconds
1 · One round of Lloyd's loop is...
Assign, then update - that is the entire algorithm, repeated until assignments stop changing. Both steps can only lower inertia (within-cluster sum of squared distances), which is why the loop always settles.
2 · Why does a bad start produce a PERMANENTLY bad answer instead of a temporarily bad one?
The loop is pure downhill. That guarantees convergence AND guarantees it stays in whatever valley it reaches first. You watched it live: the unlucky start locked at inertia 278 while a better answer at 92 existed. The fix is better starts, not more rounds.
3 · What does k-means++ do differently from plain random initialization?
Spread-out starts make crowded starts (the cause of most local optima) rare. Option A describes the n_init brute-force fix - useful with random starts, which is why sklearn's modern n_init='auto' runs k-means++ just ONCE.
What this session covered from the official universe
Certificates, videos, and graded assessments stay with the official providers - this course teaches the working core with a live in-browser lab.