Spotify groups your 10,000 songs into 'moods' you never named. Pinterest finds your style in a sea of pins. Both rely on unsupervised clustering — finding structure with no labels. Here's how it works.
Learning Objectives
After this lesson, you will be able to:
Walk through K-Means step by step: drop some center points, assign each data point to the nearest center, move centers, repeat until stable
Understand why K-Means can fail (bad starting points, wrong number of clusters, weirdly shaped groups) and how to fix each issue
Know when to use DBSCAN instead of K-Means — DBSCAN finds clusters by density and handles weird shapes that K-Means cannot
Build a hierarchy of clusters with agglomerative linkage (single, complete, average, Ward) and read a dendrogram to pick the right number of clusters without committing to K up front
Pick the right clustering algorithm — K-Means, DBSCAN, hierarchical, or GMM — based on cluster shape, density, scale, and whether you need a hierarchy
Use the elbow method and silhouette score to choose the right number of clusters K without labeled data
Don't worry if "unsupervised learning" feels vague — clustering is the most intuitive part. You have already done it: every time you sorted your laundry by color, organized your desk, or grouped your friends by interests, you were clustering!
The Spotify question: Spotify has 10,000 of your listened songs and zero "mood" labels — yet it groups them into Workout / Chill / Focus / Party so reliably it powers your Discover Weekly. How? The audio API returns features per track (tempo, energy, danceability, valence, acousticness, …). Run K-Means with K=4 on those features and you have four "moods" — defined entirely by the cluster centers in feature space, no human labels needed. That's clustering in industry.
Watch K-Means iterate through assign-update cycles. Try different initial centroid positions and observe how they affect the final clusters.
Loading visualization...
Try this: Watch K-Means iterate. First, centroids are placed randomly. Then points are assigned to their nearest centroid (watch colors change). Then centroids move to the center of their assigned points. Repeat until stable. Try different initial positions and notice how the final result can change -- K-Means is sensitive to initialization.
Now step through K-Means iteration-by-iteration on five different datasets — including moons and rings, where K-Means visibly fails.
K-Means iteration stepper — including datasets where K-Means breaksInteractive
Loading visualization...
Try this: Run the stepper on the blobs dataset and watch it converge cleanly in 5-10 iterations. Then switch to the moons or rings preset — K-Means will still converge, but the result is obviously wrong: it slices the moons in half with a straight line because its assumption (convex, roughly spherical clusters) is violated. That's not a bug; it's the algorithmic boundary you need to recognize before reaching for DBSCAN or GMM.
Quick check
K-Means converges on a dataset of two interlocking moons. The final clustering cuts each moon roughly in half rather than putting each moon in its own cluster. Why?
⚡ Playground:Clustering → — drag data points and watch k-means centroids adapt in real time across multiple initializations.
Try it! Open the Python REPL and type these lines yourself. Cluster random data into 3 groups: from sklearn.cluster import KMeans; import numpy as np; X = np.random.randn(100, 2); km = KMeans(n_clusters=3).fit(X); print(f"Cluster sizes: {[sum(km.labels_==i) for i in range(3)]}") — you just found 3 groups in random data!
Step-by-step
Initialize: Randomly place K centroids in feature space
Assign: Each point is assigned to its nearest centroid (Euclidean distance)
Update: Move each centroid to the mean of all points assigned to it
Repeat: Steps 2-3 until centroids stop moving (convergence)
Step 5 — reassign. No assignment changes. Converged in 2 iterations. Final clusters: and — exactly the natural grouping a human would see.
Notice the bad initialization: starting with two centroids almost on top of each other (μ₁=(1,1), μ₂=(1,2)) gave initial assignments where 4 of 6 points were in cluster 2 — but two iterations of assign-then-update were enough to recover. With worse initialization (both centroids inside the lower-left blob, say), K-Means can converge to a bad local minimum where one centroid swallows everything. That's why n_init=10 is non-negotiable in practice.
Random initialization can lead to poor results. K-Means++ picks initial centroids that are spread apart:
Choose the first centroid randomly from the data points
For each remaining centroid: pick a data point with probability proportional to its squared distance from the nearest existing centroid
Repeat until K centroids are placed
This ensures centroids start in different regions of the data, dramatically reducing the chance of bad convergence. Scikit-learn uses K-Means++ by default.
How do you know the right number of clusters K if there are no labels?
The elbow method: plot the total within-cluster variance (inertia) as a function of K. As K increases, inertia always decreases. But at some point, adding another cluster provides diminishing returns -- the curve bends like an elbow. The K at the elbow is a good choice.
The silhouette score is a more principled alternative: for each point, measure how similar it is to its own cluster versus the nearest other cluster. Values range from -1 (wrong cluster) to +1 (well-clustered). Choose K that maximizes the average silhouette score.
Run K-Means against three classic datasets where it succeeds, struggles, and outright fails — then run DBSCAN on the same data and watch it handle the non-convex shapes that K-Means can't.
The k-distance graph helps: for each point, compute the distance to its k-th nearest neighbor (k = min_samples). Sort these distances and plot them. The "elbow" in this curve is a good epsilon value -- it separates dense regions from sparse regions.
Agglomerative (bottom-up). Start with each point as its own cluster, then greedily merge the closest pair at each step until one cluster remains. This is the common one — sklearn, scipy, and R's hclust are all agglomerative.
Divisive (top-down). Start with one giant cluster containing everything, then recursively split. Conceptually elegant but rarely used in practice because choosing where to split is hard.
Once a cluster has more than one point, "distance to another cluster" is ambiguous. Linkage is the rule that resolves this. It is the single most important choice in hierarchical clustering — different linkages give wildly different results on the same data.
Single linkage -- distance between the closest points across clusters. Tends to produce long stringy clusters (the "chaining effect"). Useful when you actually expect chained structure (rivers, tubes, manifold edges), but a disaster on noisy data because a single bridging point links unrelated clusters.
Complete linkage -- distance between the farthest points. Forces tight, compact clusters with similar diameters. Sensitive to outliers (one far point inflates the distance).
Average linkage -- mean of all pairwise distances. Balanced, often a sensible default.
Ward's method -- minimizes the increase in within-cluster sum of squares at each merge. Produces compact, roughly equal-sized clusters and tends to recover spherical groupings -- much like K-Means but without committing to K up front. Sklearn's default.
The dendrogram is the killer feature of hierarchical clustering. Every leaf is a data point. Every internal node is a merge. The height of a node is the distance at which the merge happened.
To get clusters, draw a horizontal line across the dendrogram. Every vertical branch the line crosses becomes one cluster. Move the line up = fewer, bigger clusters. Move it down = more, smaller clusters. You see the entire spectrum at once -- no need to re-run the algorithm to try different k.
A natural number of clusters often shows up as a big vertical gap in the dendrogram: a height range where no merges happen. Cutting in that gap gives a clustering that resists small perturbations.
You don't know K and want to see the full spectrum of possible clusterings at once.
You need a dendrogram to communicate cluster relationships to a non-technical audience (genomics papers, customer-segmentation reports, taxonomic studies).
Cluster structure is nested — sub-groups within groups, like species within genera or product categories within departments.
You have a custom distance function (sequence edit distance, graph distance) that K-Means and GMM cannot use directly.
Naive agglomerative clustering is O(N³) time and O(N²) memory -- you precompute the full pairwise distance matrix and update it after every merge. Modern implementations get to O(N² log N), but the N² distance matrix is the hard wall. Above ~10K points you cannot use vanilla agglomerative clustering -- switch to BIRCH, CURE, or sample first.
pythonplayground.py · Pyodide
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Tests · Verify that single, complete, average, and ward give different cluster size distributions on the same data. Verify ward and average produce balanced sizes near [15, 15, 15]; single linkage often gives lopsided sizes.
Quick check
You run K-Means with K from 2 to 10. The inertia curve has no clear elbow — it bends smoothly the whole way. The silhouette score peaks sharply at K=4. Which K should you pick, and why?
Quick check
You need to cluster customer behavior. The cluster sizes vary wildly (3 huge segments, a long tail of small niche segments), and you also want to present a tree of nested sub-segments to non-technical stakeholders. Which algorithm fits?
GMMs are a soft clustering generalization of K-Means. Instead of hard assignment (each point belongs to exactly one cluster), GMMs assign probabilities:
P(x)=k=1∑KπkN(x∣μk,Σk)
GMMs are trained using the Expectation-Maximization (EM) algorithm:
E-step: Compute the probability of each point belonging to each Gaussian (soft assignment)
M-step: Update each Gaussian's parameters (mean, covariance, mixing weight) using the soft assignments
K-Means assigns each point to exactly ONE cluster (hard assignment). GMM says "this point is 70% Cluster A and 30% Cluster B" (soft assignment). This matters when clusters overlap -- real data almost always has overlapping groups.
Consider customer segmentation: a customer who buys both budget groceries and premium electronics does not fit neatly into either the "bargain hunter" or "luxury buyer" segment. K-Means forces a binary choice, losing nuance. GMM captures the blend, letting you tailor marketing that acknowledges both sides of their behavior.
Soft assignment is also crucial for uncertainty quantification. When a GMM says a point is 51% Cluster A and 49% Cluster B, that point is ambiguous -- you should treat it differently from a point that is 99% Cluster A. Hard clustering throws away this uncertainty information entirely.
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.preprocessing import StandardScaler
# COMMON BUG: forgetting to scale features → distance dominated by largest feature
X_raw, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=0)
X = StandardScaler().fit_transform(X_raw) # FIX: always scale before K-Means
# COMMON BUG: n_init=1 (default in older sklearn) → bad local optima
km = KMeans(n_clusters=4, n_init=10, random_state=0).fit(X)
print(f"Inertia: {km.inertia_:.1f}")
print(f"Silhouette: {silhouette_score(X, km.labels_):.3f}")
# Expected: Inertia ~ 200-500, Silhouette ~ 0.55-0.75 for well-separated blobs
A silhouette score above ~0.5 indicates well-separated clusters; below 0.2 means K-Means is the wrong tool — try DBSCAN or GMM.
Tests · Verify convergence occurs (changed=0). Verify inertia decreases monotonically. Test with K=3 and check that centroids are near the true centers [2,2], [8,8], [2,8].
K-Means alternates between assign and update. Points are assigned to their nearest centroid, then centroids move to the mean of assigned points; this cycle repeats until convergence, which is guaranteed
K-Means assumes spherical, equal-sized clusters. It fails on elongated, overlapping, or density-varying clusters; always visualize results to verify the assumptions hold
DBSCAN discovers clusters of arbitrary shape. By grouping points based on local density rather than distance to centroids, DBSCAN handles non-spherical clusters and automatically identifies noise points as outliers
Choosing K is the hardest part of K-Means. The elbow method and silhouette scores provide guidance, but there is no perfect automatic answer; domain knowledge often determines the right number of clusters
Gaussian Mixture Models provide soft clustering. Instead of hard assignments, GMMs assign probabilities of belonging to each cluster, capturing the uncertainty that K-Means ignores
You can now find groups in unlabeled data with K-Means, DBSCAN, and hierarchical clustering. But what if a point belongs partially to multiple clusters, or you want a real probabilistic model of the data? Next up: Gaussian Mixture Models and the EM Algorithm — soft clustering with full probabilistic semantics, and the foundational EM algorithm that powers half of unsupervised learning.