Why this session exists
k-means assigns every point to its nearest centroid, which means every border it draws is straight and every territory it imagines is round-ish. On our RFM blobs that assumption happens to be true - which is exactly why it has worked for three sessions. But assumptions that happen to be true are the most dangerous kind: nobody remembers they were assumptions. Today we break k-means on purpose, on a shape planted to defeat it, and meet the algorithms built for the shapes it cannot see.
Hierarchical clustering and the dendrogram 6 min live
k-means starts with an answer (k centroids) and sorts everyone into it. Hierarchical clustering refuses to start with an answer: every point begins as its own cluster of one, and the algorithm repeatedly merges the closest pair - point with point, point with group, group with group - until only one cluster remains. That is the whole algorithm. The product is not one clustering; it is the entire merge history.
LiveBottom-up, and the tree you get for free3 min▶
The flavor we mean is agglomerative - bottom-up. Round one merges the two closest points in the pile. Round two merges the next closest pair (which might now involve that little group). Repeat n-1 times and everything is one cluster. Record every merge and the height (distance) at which it happened, and you have the dendrogram - the tree above.
Here is the payoff k-means cannot match: cut the tree at any height and you get a clustering at that granularity. Cut high, few clusters; cut low, many. Session 4's whole agony - choosing k - becomes a slider you drag AFTER the single run, instead of a reason to re-run the algorithm at every candidate k. You also get the nesting itself: which segments are cousins, which merged last, which pair was inseparable from round one.
Self-studyWhen it shines, and what it costs3 min▶
When it shines: taxonomy-like questions ("show me the nesting, not just the groups"), small-to-medium data, and any situation where the distances between points are exotic - sklearn's comparison table lists agglomerative clustering as the choice for many clusters, connectivity constraints, and any pairwise distance. If you can compute a distance between two things - customers, documents, gene sequences - you can grow a dendrogram over them. k-means, by contrast, is married to Euclidean distance and means.
What it costs: the merge loop compares everything with everything, so it is O(n²)-ish in time and memory. Our 300-customer lab sample is nothing; 12,000 customers is workable; millions is not the tool's territory. The pros' pattern: dendrogram on a sample to UNDERSTAND the structure, faster algorithm on the full pile to ASSIGN it.
DBSCAN: follow the density 7 min live
DBSCAN abandons centroids entirely and asks one local question at every point: is this neighborhood crowded? A point with at least min_samples neighbors within radius eps is a core point. Core points recruit their neighbors, those neighbors' cores recruit theirs, and a cluster is whatever the chain reaction reaches - whatever shape that turns out to be. Moons, rings, chains: if the density connects, DBSCAN traces it.
LiveNoise as a first-class answer3 min▶
Remember session 1's sticky note: k-means always succeeds - every point gets filed somewhere, including points that belong nowhere. DBSCAN is the only algorithm today allowed to say "this customer belongs to nothing." A point that is neither a core nor within reach of one gets the label -1: noise. Not cluster negative-one - an explicit refusal to file it.
For Mango Lane that is not a bug report, it is a feature: the customer who bought one wedding outfit at 3am and vanished does not deserve to distort the VIP centroid. Filing her as noise is more honest than filing her anywhere.
LiveThe price: two touchy knobs, and no new arrivals4 min▶
No free lunch, and DBSCAN's bill has two lines:
- No k needed - but eps and min_samples are crucial and touchy. You escaped choosing k and inherited choosing a radius. Too small an eps and the chain breaks: one moon shatters into fragments and stragglers flood the noise bin. Too large and the two moons fuse into one blob. There is no session-4-style curve that picks eps for you; it takes domain sense and experimentation.
- Transductive: it cannot label a brand-new point. sklearn's terms: k-means is inductive - it learns centroids, so tomorrow's new customer gets assigned with one distance check. DBSCAN only ever labeled THIS pile; a new arrival means re-running the chain reaction. For a segmentation that must score every new signup nightly, that is disqualifying on its own.
Hold both in mind during the shape-off: DBSCAN will win the moons outright - and would still be the wrong production choice for Mango Lane's daily pipeline.
GMM: the soft answer 6 min live
A Gaussian mixture model says: the pile was generated by k overlapping fuzzy ellipses (Gaussians), and every customer is a draw from one of them - we just do not know which. The EM algorithm fits the ellipses and then answers the only way honesty allows: with probabilities, not verdicts. Customer #4821 is not "cluster 2"; she is 60% steady mid-basket, 40% VIP regular.
LiveFuzzy ellipses and predict_proba3 min▶
The safe sentence, straight from sklearn's docs: mixtures "generalize k-means to incorporate covariance structure". Say generalization, never identical - k-means draws each territory as a same-size circle around a centroid; a GMM lets each cluster be an ellipse with its own stretch and tilt (four covariance types in sklearn, from spherical to fully free). Where k-means answers predict (a verdict), GMM also answers predict_proba (a probability per cluster). And its cousin of session 4's k-question has a principled answer: BIC scores fit-versus-complexity to pick the component count.
The business payoff is exactly the borderline customer. Hard clustering forces the 51/49 case into one campaign; a GMM hands marketing the 60/40 truth - which is precisely what a marketer wants to know about a customer sitting between segments.
Self-studyWhen soft labels beat hard ones2 min▶
What do you actually DO with 60/40? Judgment calls, all of them: send both campaigns (and eat the cost and the inbox fatigue)? Send the 60% one (and accept being wrong 40% of the time)? Hold her out of both and watch another month? There is no formula - but notice that every one of those options was invisible under hard clustering, which silently made the choice for you by rounding 60/40 up to 100/0. Soft labels do not remove the decision; they surface it. Write down which policy you would pick for Mango Lane and why - session 7's segment sheet has a column for exactly this.
LiveChoosing like sklearn does: the comparison table3 min▶
sklearn's clustering guide opens with a big comparison table, and its axes are the whole lesson: choose by geometry (flat borders vs non-flat shapes), cluster sizes (even vs uneven), scale (how many points survive the algorithm's appetite), and whether you must label NEW points - inductive algorithms like k-means and BIRCH can; transductive ones like DBSCAN, hierarchical, and spectral cannot without a re-run. Here is that thinking on today's four:
| Algorithm | Needs k? | Shapes | Noise handling | New points | Mango Lane verdict |
|---|---|---|---|---|---|
| k-means | Yes, up front | Round-ish, straight borders | None - everyone gets filed | Yes (inductive) | The workhorse - our blobs fit it |
| Hierarchical | No - cut the tree for any k | Depends on linkage; any pairwise distance | None | No (re-run) | Grab for "show me the nesting" |
| DBSCAN | No - but eps/min_samples touchy | Arbitrary - chains density | First-class: label -1 | No (transductive) | Grab when the scatter shows moons |
| GMM | Yes - BIC helps pick | Ellipses via covariance | None, but low proba everywhere flags it | Yes (predict_proba) | Grab when borderline cases matter |
The verdict row's conclusion: our RFM blobs are round-ish and k-means is fine - the rivals are for the days the data is not. Knowing WHICH rival, from a table like this rather than from fashion, is the skill.
The shape-off 🥊 ★ 18 min · three algorithms, one planted shape
The lab below swaps the customer pile for two interleaved moons - a shape planted specifically to be non-round - and lets you run all three algorithms on it for real, in your browser. Same points, three worldviews, three very different scores. Referee honestly.
Look at the two interleaved moons first. Your eye separates them instantly - two curved bands, hooked into each other. No blob, no centroid, nowhere to stand a flag. This shape was planted to be non-round; hold your eye's answer as the reference.
▶ Run k-means (k=2): truth match 83%. It drew a straight border through both moons - because straight borders are all it has. Each centroid grabs the nearest half of BOTH bands. Note the confidence: no error, no warning, a perfectly tidy wrong answer.
▶ Run DBSCAN (eps .32, min 5): 100%. It traced each moon by chaining dense neighborhoods, and nobody gave it a k. This tidy sample yields no noise points - shrink eps in your head and stragglers at the moon tips would start going -1.
▶ Run GMM: 83% soft. Spherical gaussians struggle on moons for the same reason k-means does - but note the concept: it returned probabilities. The points near the border between moons are exactly the ones it is least sure about, and it says so.
Say the moral out loud: no winner exists - only fit between assumptions and shape. DBSCAN did not "beat" k-means; its assumption (density chains) happened to match this data. On well-separated round blobs the ranking flips.
Connect back to Mango Lane: our customer pile IS round-ish blobs, so k-means stays our workhorse for the rest of the course. What you gained today is knowing which rival to grab on the day the scatter says otherwise - and the table to justify the grab.
Homework 📝 ◐ 20 minutes
- Sketch the failure, both ways: draw (on paper) one dataset where k-means wins and DBSCAN embarrasses itself, and one where the reverse holds. Hint for the first: two round blobs of very different density, close together - what does a single eps do to them?
- Read one row we skipped: open sklearn's clustering comparison table (user guide 2.3) and read the row for an algorithm we only named - spectral, BIRCH, or OPTICS. Classify it yourself: inductive or transductive? What geometry? Write two sentences on when you would grab it.
- Write the 60/40 policy memo: one paragraph deciding what Mango Lane should do with a customer who is 60% steady mid-basket, 40% VIP - both campaigns, the likelier one, or hold out? Defend the cost trade-off; there is no right answer, only an owned one.
Three questions before you go 🎯 ◐ 90 seconds
1 · Cutting a dendrogram at a chosen height gives you...
The dendrogram is the whole merge history; the cut just chooses where to stop reading it. One O(n²)-ish run, every k for free afterward - the exact opposite of k-means, which must re-run per k.
2 · Among today's three algorithms, the power that belongs to DBSCAN alone is...
Noise as a first-class answer is DBSCAN's signature: k-means and GMM file everyone somewhere. (A is real but not alone - hierarchical with the right linkage bends too. C is false: eps and min_samples are crucial and touchy.)
3 · GMM's "soft assignment" means...
A mixture model treats membership as uncertain and says so: 60% this segment, 40% that one. That is the payoff for borderline customers - and the sentence to remember is that GMM generalizes k-means to incorporate covariance structure.
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.