Core day 14 of 60 · Week 3 · Part I · application depth

Unsupervised Learning

A k-means model splits loyalty members into segments with a silhouette of 0.55, and someone has already named them "Road Warriors" and "Deal Hunters". Before a campaign is built: would the algorithm return clusters if members had no types at all, would it return the same ones next quarter, and which decision would they change?

By the end: You run clustering with and without real structure, raw and scaled, and read silhouette, stability and an outcome difference together; you also show why the first principal component is not the most relevant one.

At a glance

Clustering always returns groups; scaling, a structureless reference, stability and a decision test decide whether they are real and useful.

Always k groups
k-means partitions any data, a smooth cloud included; no output says there is nothing here.
Units decide distance
The largest-number column dominates squared distances; standardize on the fitting rows.
Choosing k
Inertia always falls with k and silhouette peaks even on noise; compare with a reference.
Stable is not real
A raw-unit fare split was stable (0.90) and useless (churn gap 0.06).
Prove it with a decision
A segment counts only if its own action beats the baseline in a randomized holdout.

Recall · 5 min

Without notes: state which models need scaled inputs and which do not, and what the Day 9 rule says about the rows a scaler is fit on. Then say why 40 alerts from a 0.5% anomaly rate are mostly false (Day 13).

Open due reviews

Concept · 10 min

Clustering has no target, so nothing ever says "wrong": ask k-means for k groups and you get k groups, from real member types or from a smooth cloud alike. A finding differs from a drawing only by evidence outside the algorithm: groups that survive a resample, differ in an outcome you did not feed in, and change a decision.

k-means always returns k clusters, and scaling and real structure decide whether they mean anything

Predict first

Data have no groups at all. You run k-means with k = 3 and standardize the features. What do you get?

Text description of the figure

A scatter of 240 members by visits per month and basket value, coloured by k-means cluster, with sliders for k and toggles for whether the data contain three real groups and whether features are standardized. A second chart shows silhouette against k for the data and for a structureless reference. A readout gives silhouette, stability across random starts (agreement between runs with different seeds) and agreement with the true groups when they exist.

Units decide the partition, and a cloud still gets clusters Illustration

Basket value (SD 12.5) outweighs visits (SD 2.4) in every squared distance: the cut runs across the segments. Silhouette 0.48, agreement with the true segments 0.24.

Each column gets equal say and the visit gaps decide: silhouette 0.59, agreement 0.87.

One cloud with the same spreads still yields three tidy clusters, silhouette 0.33 (raw units: 0.46). Nothing here says "no structure".

Synthetic members from the cluster lab (180 per panel, seeded). Colour = k-means cluster (k = 3, best of 5 starts); marker shape = true segment where one exists. Axes in raw units in every panel; the clustering of the last two used standardized columns.

Colour is the k-means cluster, shape the true segment. Raw units cut across the segments; scaling recovers them; a structureless cloud is split all the same.

The evidence ladder for a segmentation Diagram

Scaled clustersneutral ids, no persona names
Beats the reference?
- no: to Description only
yes
Stable?
- yes: to Outcome differs?
no
Description onlydo not build offers on it
Outcome differs?
- no: back to Description only
yes
Holdout won?
- no: back to Description only
yes
Segmentationlaunch, monitor label churn

The rungs: silhouette above a structureless reference; stability across resamples and quarters; a difference in an outcome not used to cluster; the segment's own action winning a randomized holdout. Each rung is cheaper than the next; only the last shows that a segment changes a decision (Day 5).

Four clustering families and what they assume Comparison

Criterion	k-means	Gaussian mixture	DBSCAN / HDBSCAN	Hierarchical
Finds	Compact, round groups around centres; every row assigned	Elliptical groups with soft (probabilistic) membership	Dense regions of any shape, plus a noise label (-1)	A merge tree that can be cut at any level
You choose	k; scaled features	Number of components and covariance type; BIC helps	eps and min_samples (HDBSCAN: minimum cluster size)	A linkage and where to cut
Assumes	Similar-size spherical clusters	The data are a mix of Gaussians	One density level separates the clusters (HDBSCAN relaxes this)	Depends on linkage: Ward is round, single follows chains
Fails on	Crescents, stretched groups; outliers drag centres	Non-Gaussian shapes; many dimensions with full covariance	Clusters of very different density; high dimensions	Large n (time and memory grow fast); single linkage chains through noise

Pick the family whose assumption matches what "similar" means for the decision, then test it like any other.

Silhouette by k on real groups and on a structureless cloud (lab, part B) Chart

Two real groups
One Gaussian cloud

Values printed by the lab script. Real structure gives a clear peak far above the cloud; the cloud still "recommends" k = 6, by less than 0.01 over k = 3.

Key terms: k-means, silhouette, stability and adjusted Rand index. What each method assumes, how k-means works, how to choose k and how to validate a segmentation are in the pictures above and in the optional technical depth below.

Assumptions

Distance in the chosen features means "similar" for the decision; irrelevant or badly scaled features change who is near whom.
Members are measured at one cutoff date; an outcome-period column in the features leaks the answer (Day 2).
Structure persists over time; a segmentation that reshuffles every quarter cannot support a standing offer.

Application and workplace decision · 10 min

Day 2 card (member grain): decision = which members get which offer; features as of one cutoff date; baseline = the tier rule or one offer for all; unit = EUR of incremental revenue per 1,000 offers.
The script builds 900 synthetic members: two real types separated by trips per year, plus an average fare in EUR with a large spread and no type information. Churn depends on trips only.
It runs k-means (k = 2) on raw and standardized features, on the real data and on a smooth cloud with the same means and spreads, and prints silhouette, stability (ARI of two bootstrap fits), the churn gap and agreement with the true types.
A last line runs PCA on raw units.
Predict first: which setting has the highest silhouette?

Your answer to the task (decision, method, baseline). Write it before reading the interpretation.

Python

import numpy as np
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
from sklearn.metrics import adjusted_rand_score as ari, roc_auc_score, silhouette_score
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(14)
n = 900                                           # synthetic loyalty members: trips per year, average fare (EUR)
group = rng.integers(0, 2, n)                     # two real member types, separated by trips per year only
trips = rng.normal(np.array([3.0, 14.0])[group], 2.0)
fare = rng.normal(180, 60, n)                     # EUR: large numeric spread, carries no group information
churn = rng.random(n) < 1 / (1 + np.exp(0.4 * (trips - 8.5)))       # churn depends on trips, not on fare
smooth = np.c_[rng.normal(trips.mean(), trips.std(), n), rng.permutation(fare)]   # same means and spreads, no groups at all

def km(X, seed):
    return KMeans(2, n_init=10, random_state=seed).fit(X)

def stability(X):                                 # ARI between fits on two bootstrap resamples, labelling all rows
    labels = [km(X[rng.integers(0, n, n)], s).predict(X) for s in (1, 2)]
    return ari(*labels)

for name, X in [("two real groups", np.c_[trips, fare]), ("no groups (smooth cloud)", smooth)]:
    for scaled in (False, True):
        Z = StandardScaler().fit_transform(X) if scaled else X
        lab = km(Z, 0).labels_
        truth = f" | agreement with true groups {ari(group, lab):.2f}" if name.startswith("two") else ""
        rates = [churn[lab == c].mean() for c in range(2)]
        print(f"{name:24s} {'scaled' if scaled else 'raw   '}: silhouette {silhouette_score(Z, lab):.2f} | "
              f"stability {stability(Z):.2f} | churn range across clusters {max(rates) - min(rates):.2f}{truth}")

pca = PCA().fit(np.c_[trips, fare])               # PCA on raw units: the large-variance column wins
pc1 = pca.transform(np.c_[trips, fare])[:, 0]
auc = roc_auc_score(churn, pc1)
print(f"PC1 explains {pca.explained_variance_ratio_[0]:.1%} of variance; AUC for churn: PC1 {max(auc, 1 - auc):.2f} "
      f"vs trips {1 - roc_auc_score(churn, trips):.2f}")

This code is executed in the repository's checks (pnpm lesson:py / lesson:sql). It is not run on this site; copy it into your notebook.

Technical depth · optional · 41 min in total

Open only what you need. Nothing here is required to complete the day; the assessment covers the core above.

k-means: the objective, Lloyd's steps and why they stop7 minWhat is minimized, the two alternating steps, the convergence argument, and a full run on six numbers you can redo on paper.

What k-means minimizes (inertia) Formula

J = \sum_{j=1}^{k} \sum_{x_i \in C_j} \lVert x_i - \mu_j \rVert^{2}

$C_j$: the rows assigned to cluster j
$\mu_j$: the centre of cluster j (the mean of its rows)
$\lVert \cdot \rVert^{2}$: squared Euclidean distance, so large-unit columns and outliers weigh heavily
$J$: within-cluster sum of squares; its best value falls as k grows, so it cannot choose k alone

Centres are means, so features must be numeric where averaging makes sense; for categories use k-modes or a distance built for them.

Lloyd's algorithm: two easy steps, repeated until nothing moves Loop

Assign rowseach row to its nearest centreJ cannot rise ↓
Move centreseach centre to the mean of its rowsJ cannot rise ↓
Any row changed cluster?no: stop at a local minimumyes: again ↓
↺ back to 1 · Assign rows

Neither step can raise J, so the loop always stops, but only at a local minimum that depends on the start.

Why Lloyd's algorithm always stops, and where Sequence

Assignment cannot raise J
Each row moves to its nearest centre, so its term ||x - mu||^2 can only shrink or stay.
Update cannot raise J
For fixed members, the sum of ||x - mu||^2 is smallest at mu = their mean: set the derivative -2 sum(x - mu) to zero.
So it terminates
J never rises, is bounded below by 0, and there are finitely many partitions: the loop stops after finitely many steps.
At a local minimum
A fixed point where no single step helps. Finding the global minimum is NP-hard in general, hence restarts and good seeding.
Cost
Each iteration computes n x k distances in d dimensions, O(n k d); a few dozen iterations are typical.

Lloyd's algorithm by hand: six telecom customers, k = 2, a poor start Table

Step	Centres	Clusters	Inertia J
Data	monthly mobile data in GB	1, 2, 3, 8, 9, 13	start centres 1 and 2
Assign 1	1 \| 2	{1} \| {2, 3, 8, 9, 13}	0 + (0 + 1 + 36 + 49 + 121) = 207
Update 1	1 \| 7 (mean of 2, 3, 8, 9, 13)	unchanged	0 + (25 + 16 + 1 + 4 + 36) = 82
Assign 2	1 \| 7	{1, 2, 3} \| {8, 9, 13}: 2 and 3 switch	(0 + 1 + 4) + (1 + 4 + 36) = 46
Update 2	2 \| 10	unchanged	(1 + 0 + 1) + (4 + 1 + 9) = 16
Assign 3	2 \| 10	no row moves	16: stop

Hypothetical usage numbers. J falls at every half-step, 207, 82, 46, 16, as the convergence argument promises. scikit-learn's KMeans started at (1, 2) with n_init=1 returns centres 2 and 10, inertia 16, after 3 iterations.

Lloyd's algorithm from a poor start, step by step Illustration

Three random rows as centres; two land in the same group. J = 1264.

Centres move to their rows' means (arrows); 17 rows switch region. J = 875.

Centres move to their rows' means (arrows); 30 rows switch region. J = 497.

No row changes cluster, so the loop stops: J = 235. A local minimum; here also the right one.

Synthetic data: 150 points around three centres (seeded). Shaded regions: where each centre would claim a new point (the assignment step). Computed on the page; 7 update steps to convergence.

Shaded regions are the assignment step (nearest centre); arrows are the update step (centre to the mean of its rows).

k-means++ seeding and restartsadvanced2 minWhy spreading the first centres out avoids bad local minima, measured on one dataset.

k-means++ seeding (Arthur and Vassilvitskii, 2007) Sequence

First centre
Pick one row uniformly at random.
Distances
For every row compute D(x), the distance to the nearest centre chosen so far.
Next centre
Pick a row with probability proportional to D(x) squared: far rows are favoured.
Repeat
Until k centres are chosen, then run Lloyd's steps.
Guarantee
Expected inertia within a factor O(log k) of the optimum, before any Lloyd step.

Restarts (n_init) keep the lowest-inertia run. They fix bad starts, not a wrong shape assumption.

Random starts versus k-means++ seeding, 40 runs each Illustration

Final inertia of 40 single starts each. Within 1% of the best found: 4 of 40 random starts, 22 of 40 k-means++ starts.

Worst random start (J = 503): some groups share a centre while another group is split. Lloyd's steps cannot climb out.

Median k-means++ start (J = 146): one centre per group. scikit-learn's default (n_init="auto") runs one k-means++ start.

Synthetic data: 270 points in nine groups on a 3 x 3 grid (seeded), k = 9. Random starts pick k distinct rows; k-means++ uses the lab's seeded implementation. All runs computed on the page.

Same data, same k, same Lloyd steps; only the starting centres differ. Bad starts end in bad local minima.

Defaults you inherit (scikit-learn 1.9.1) Table

Estimator	Defaults	Watch out for
KMeans	init='k-means++', n_init='auto', max_iter=300, tol=1e-4	'auto' means one k-means++ start (ten with init='random'): set n_init when k is large or groups are uneven
GaussianMixture	covariance_type='full', n_init=1, init_params='kmeans', tol=1e-3, max_iter=100, reg_covar=1e-6	Compare component counts by BIC (lower is better); full covariances add parameters fast in many dimensions
DBSCAN	eps=0.5, min_samples=5; low-density rows labelled -1 (noise)	One eps for all clusters; HDBSCAN (scikit-learn 1.3+) handles varying density
silhouette_score	every row	O(n^2) distances: on large tables pass sample_size and score a random sample

Defaults change between versions; pin and record them with every result.

Choosing k: silhouette by hand, elbow, stability6 minThe silhouette computed row by row on six customers, the elbow and the adjusted Rand index, and why none of them names a k on structureless data.

Silhouette of one row Formula

s(i) = \frac{b(i) - a(i)}{\max\{a(i),\, b(i)\}}

$a(i)$: mean distance from row i to the other rows of its own cluster (cohesion)
$b(i)$: mean distance from row i to the rows of the nearest other cluster (separation)
$s(i)$: from -1 (wrong cluster) to 1 (well placed); the score is the mean over rows

Defined only for 2 to n-1 clusters, so silhouette can never say "one cluster, no structure".

Silhouette by hand on the same six customers Table

Customer (GB)	a: mean distance, own cluster	b: mean distance, other cluster	s = (b - a) / max(a, b)
1	(1 + 2) / 2 = 1.5	(7 + 8 + 12) / 3 = 9.0	0.833
2	(1 + 1) / 2 = 1.0	(6 + 7 + 11) / 3 = 8.0	0.875
3	(2 + 1) / 2 = 1.5	(5 + 6 + 10) / 3 = 7.0	0.786
8	(1 + 5) / 2 = 3.0	(7 + 6 + 5) / 3 = 6.0	0.500
9	(1 + 4) / 2 = 2.5	(8 + 7 + 6) / 3 = 7.0	0.643
13	(5 + 4) / 2 = 4.5	(12 + 11 + 10) / 3 = 11.0	0.591
Mean	over all six rows	-	0.705

Clusters {1, 2, 3} and {8, 9, 13} from Lloyd's run. Customer 8 is the least well placed: almost as close to the other cluster as to its own. scikit-learn's silhouette_samples returns the same numbers.

Inertia by k (lab data, standardized, computed) Chart

Two real groups
One Gaussian cloud

Inertia falls with every k on both datasets. A sharp elbow suggests structure; a smooth curve is what noise looks like. Read each diagnostic against a structureless reference with the same marginals: the gap, not the peak. When the decision fixes k (three offer tiers, four crews), let it choose and use the diagnostics as checks.

Adjusted Rand index between two labellings Formula

\mathrm{ARI} = \frac{\mathrm{RI} - \mathbb{E}[\mathrm{RI}]}{\max(\mathrm{RI}) - \mathbb{E}[\mathrm{RI}]}

$\mathrm{RI}$: share of row pairs on which the two labellings agree (same or different cluster)
$\mathbb{E}[\mathrm{RI}]$: the agreement expected by chance with the same cluster sizes
$ARI$: 1 identical, about 0 random, can be negative; cluster ids may be permuted

Measuring stability Sequence

Resample
Draw a bootstrap sample, a new seed, or next quarter's members.
Refit
Same features, scaling, k and settings.
Label everyone
Assign all original rows with both fits.
Compare
ARI between the two labellings; per cluster, the Jaccard overlap (Hennig, 2007).
Repeat and report
The spread over many resamples, and the same check across time.

Stability shows the algorithm repeats itself on these data. Raw-unit fare splits are stable too, so it is a filter, not a proof.

Gaussian mixtures: soft clusters fitted by EMadvanced6 minThe mixture model, the E and M steps, one round worked by hand, and how EM relates to k-means.

Gaussian mixtures and the EM idea Sequence

Model
Each row comes from one of k Gaussians: component j is picked with probability pi_j, then x ~ N(mu_j, Sigma_j). The component is hidden.
E-step
Responsibility r_ij = pi_j N(x_i; mu_j, Sigma_j) over the same sum for all components: a soft membership summing to 1.
M-step
Re-estimate every component from all rows weighted by r_ij: weighted means, weighted covariances, and pi_j = mean of r_ij.
Guarantee
The log-likelihood never decreases from one round to the next, so EM converges, to a local maximum that depends on the start.
Link to k-means
With equal round covariances shrinking to zero, responsibilities become 0 or 1 and EM turns into Lloyd's algorithm.
Where it breaks
A component can collapse onto one row (variance 0, likelihood infinite); scikit-learn adds reg_covar = 1e-6 to each covariance diagonal.

The same E/M idea fits any model with hidden labels; Day 13's prevalence estimate without labels is one more instance.

One EM round by hand: soft memberships for the six customers Table

Customer (GB)	Distance to 2 \| to 10	Responsibility, cluster 1	Responsibility, cluster 2
1	1 \| 9	0.988	0.012
2	0 \| 8	0.972	0.028
3	1 \| 7	0.935	0.065
8	6 \| 2	0.145	0.855
9	7 \| 1	0.065	0.935
13	11 \| 3	0.002	0.998
M-step: new means	responsibility-weighted mean of the GB values	2.42	9.85
M-step: new weights	mean responsibility	0.518	0.482

Start: means 2 and 10, both SDs 3, equal weights; variances held fixed here for brevity. For customer 8: r = 1 / (1 + e^(-(36 - 4) / 18)) for cluster 2. Customer 8 is 85% cluster 2, not 100%: the soft membership k-means throws away, and a customer split 55/45 should not get a confidently targeted offer. Verified in numpy.

PCA as an eigendecomposition, worked on a 2x26 minWhat PCA estimates, the eigenvalue problem solved by hand on five machines, and the properties that decide when to use it.

PCA: the directions of largest variance are eigenvectors Formula

S = \tfrac{1}{n-1} X_c^\top X_c = V \Lambda V^\top, \quad v_1 = \arg\max_{\lVert v \rVert = 1} v^\top S v

$X_c$: the data with each column's mean subtracted; scikit-learn's PCA centres but does not scale
$V, \Lambda$: eigenvectors (orthonormal component directions) and eigenvalues (the variance along each), sorted largest first
$\lambda_j / \sum \lambda$: explained variance ratio; the eigenvalues add up to the total variance, the trace of S
$X_c v_j$: the scores: each row's coordinate along component j; their variance is exactly lambda_j

Libraries compute it from an SVD of X_c rather than forming S. A component's sign is arbitrary: v and -v describe the same axis.

PCA by hand: a 2x2 covariance matrix from five machines Table

Step	Working	Result
Centred data	temperature and vibration deviations of five machines	x = -3, -1, 0, 1, 3; y = 0, -2, 0, 0, 2
Covariance	sums of squares 20 and 8, cross-products 8, divided by n - 1 = 4	S = [[5, 2], [2, 2]]
Characteristic equation	det(S - lambda I) = (5 - lambda)(2 - lambda) - 4	lambda^2 - 7 lambda + 6 = 0
Eigenvalues	lambda = (7 +/- 5) / 2; they sum to the trace, 7	6 and 1
PC1 direction	(S - 6I) v = 0 gives -v1 + 2 v2 = 0, then normalize	(2, 1) / sqrt 5 = (0.894, 0.447)
PC2 direction	orthogonal to PC1	(-1, 2) / sqrt 5 = (-0.447, 0.894)
Explained variance	6 / 7 and 1 / 7	85.7% and 14.3%
PC1 scores	(2x + y) / sqrt 5 for each machine	-2.68, -1.79, 0, 0.89, 3.58
Check	variance of the scores: (7.2 + 3.2 + 0 + 0.8 + 12.8) / 4	6.0 = lambda 1

Hypothetical sensor readings (manufacturing). scikit-learn's PCA returns eigenvalues 6 and 1 and the same axes, up to sign. Keeping PC1 alone loses one seventh of the variance.

The same eigendecomposition on 150 rows, raw versus standardized Illustration

Raw units: the covariance matrix is [[5.4, 65], [65, 1797]]. Spend's variance dwarfs visits', so PC1 (99.8% of variance) is the spend axis renamed - the eigendecomposition measured the units.

Standardized: both columns have variance 1, so the correlation matrix [[1, 0.66], [0.66, 1]] is decomposed instead. Its eigenvalues are 1 + r = 1.66 and 1 - r = 0.34: PC1 (83%) is now the shared visits-and-spend direction.

Synthetic retail-style data: 150 members, spend built from visits plus noise (correlation 0.66). Both panels eigendecompose the matrix shown in their note with the same closed form as the depth chapter's 2x2; arrows are the eigenvectors, 2 standard deviations long.

Arrows are the computed eigenvectors, two standard deviations long. On raw units PC1 is the spend axis renamed; standardized, it is the direction in which visits and spend move together.

Four properties that decide when PCA helps Overview

Two definitions, one answer
PC1 maximizes projected variance; the first q components also minimize squared reconstruction error (Eckart-Young).
Blind to the target
Found without y: high variance is not relevance, and on raw units the largest-number column wins (next chapter).
Linear only
Components are linear combinations; curved structure needs other tools or features that encode it.
Noisy when rows are few
Trailing components are noise and leading ones wobble: check them across resamples; fit PCA inside the fold (Day 9).

Scaling, units and what PCA really ranks3 minHow one column's units decide the partition and the first principal component in today's run.

The application run, side by side Table

Data	Features	Silhouette	Stability (ARI)	Churn gap	Agreement with truth
Two real groups	raw units	0.55	0.90	0.06	0.00
Two real groups	standardized	0.46	1.00	0.74	1.00
Smooth cloud	raw units	0.55	0.90	0.06	no truth
Smooth cloud	standardized	0.31	0.03	0.05	no truth

Raw units produce a stable fare split on both datasets; only the scaled real data pass every check. Fit the scaler (and any PCA) on the fitting rows inside the pipeline (Day 9). Standardizing gives every column equal say; weight columns deliberately if the decision needs it.

High variance is not relevance (application run) Chart

PC1 on raw units (99.1% of variance)0.51 AUC for churn
Trips per year alone0.91 AUC for churn
Chance0.5 AUC for churn

PC1 on raw units is nearly the fare column. Scale before PCA, and judge components against the target (Day 17).

DBSCAN and hierarchical clusteringadvanced4 minWhat the density and merge-tree families assume, where they beat k-means, and what they cost.

Two crescents: k-means versus DBSCAN, and DBSCAN's one knob Illustration

k-means, k = 2: the boundary halfway between two centres is a straight line, so it slices each crescent. Agreement with the true shapes 0.34.

eps 0.08: few points have 5 neighbours that close. 22 clusters, 85 noise points, agreement 0.06.

eps 0.2: the density gap between the crescents separates them. 2 clusters, 1 noise point, agreement 0.99.

eps 0.5: neighbourhoods bridge the gap and everything joins. 1 cluster, 0 noise points, agreement 0.00.

Synthetic crescents: 300 points, noise 0.08 (seeded). DBSCAN with min_samples = 5, computed on the page; small dots are border points, crosses are noise (label -1). Agreement = adjusted Rand index with the true crescents.

k-means draws straight boundaries. DBSCAN follows density, but only a narrow band of eps separates the crescents without fragmenting them. To choose eps, sort every row's distance to its k-th neighbour (k = min_samples) and look for the knee (Ester et al., 1996).

Agreement with known truth (ARI) by data shape (computed) Table

Data shape	k-means	Ward linkage	Best other method
Two crescents (lab, part A)	0.26	0.53	Single linkage 1.00; DBSCAN eps=0.2 1.00
Three stretched blobs	0.59	0.66	Gaussian mixture, full covariance: 1.00
Three blobs, spreads 1.0, 2.5 and 0.5	0.80	0.95	Gaussian mixture: 0.96

scikit-learn 1.9.1 on make_moons (lab) and make_blobs (600 points, random_state 170); k-means n_init=10. Each method wins where its assumption holds.

Hierarchical clustering, one linkage at a time Table

Linkage	Distance between two clusters	Tends to
Single	Closest pair of rows	Follow chains and odd shapes; chains through noise
Complete	Farthest pair of rows	Compact clusters of similar diameter
Average	Mean over all pairs	Sit between single and complete
Ward	Increase in within-cluster sum of squares	Round, k-means-like clusters; Euclidean only; scikit-learn's default

Every linkage works from pairwise distances, so memory grows with the square of the row count.

Where clustering fails2 minSix failure modes to test before trusting any partition.

Six ways clustering misleads Overview

Non-spherical shapes
k-means cuts crescents and stretched groups across (ARI 0.26 on the crescents).
Unequal density
One eps cannot fit a dense and a sparse group; try HDBSCAN or a mixture.
Outliers
Squared distances let a few extreme rows drag a centre; flag them first.
High dimensions
Distances concentrate: nearest and farthest rows look alike. Select or reduce features.
Unit dominance
The largest-number column decides the partition; standardize on fitting rows.
Leaky features
Outcome-period columns make clusters look predictive of churn (Day 2).

Anomaly scores are rankings, not verdicts2 minWhat an isolation forest's list looks like at a low base rate, and what contamination really sets.

An isolation forest's top 50 at a 0.5% anomaly rate (lab, part C) Chart

Precision in the top 5010 of 5020 %
Recall in the top 5010 of 25 anomalies40 %
Base rate (a random list)0.5 %

AP 0.35 against a floor of 0.005: a good ranking still gives a short, impure list; price it as on Day 13. Contamination only moves where scores are cut into labels, never the order. Unusual is not harmful (a recalibrated sensor, a card used on holiday), so judge the list by precision at the review capacity and the value of a found case.

Validating clusters by business use3 minRead stability and outcome difference together, then let a randomized holdout decide.

Stability and outcome difference together Map

Real but fragile

Fix features, scaling or drift before any standing offer.

Candidate segmentation

Scaled real data: stability 1.00, churn gap 0.74. Run the holdout.

Noise

Scaled smooth cloud: stability 0.03, churn gap 0.05. Drop it.

Stable artefact

Raw-unit fare split: stability 0.90, churn gap 0.06. Looks validated; is not.

Validating segments by business use Sequence

Freeze labels
Assign cluster ids at a cutoff date; no persona names yet.
Randomize
Within each segment, randomly give its own offer or the standard offer.
Measure
Incremental EUR per 1,000 offers per segment against the standard offer (Day 5).
Keep or merge
Keep a segment only if its offer beats standard by more than it costs to run.
Monitor
Track label churn at each refit; retire segments that reshuffle.

Memory anchor

Clusters always appear; stability and a decision test make them real.

Useful for

Exploring structure and outliers in unlabeled data (retail baskets, machine sensor profiles, patient lab panels) and generating hypotheses that a holdout can test.
Compressing correlated measurements before a model, such as dozens of correlated sensor channels or survey items, when the components are checked against the target (Day 17).
Screening rare unusual rows for review (card transactions, network-fault logs, insurance claims) when the list length and the base rate are priced.

Not suitable for

Proving that customer or patient types exist, or naming personas, without a stability check and a downstream decision test.
Choosing features for a supervised problem by variance alone; relevance to the target needs the target.

Traps

Silhouette and stability as proof

Raw-unit clustering on a large-spread column gives a high silhouette and a stable partition that mirrors the units. The numbers look like validation and describe an artefact.

How to avoid it

Standardize, compare with a structureless reference, and add an outcome difference and a holdout decision test.

Personas named before the evidence

Labels such as "Deal Hunters" spread through slides and campaigns, so people defend the names even after refits reshuffle the members behind them.

How to avoid it

Keep working labels neutral (cluster ids) until stability, outcomes and the holdout test have been shown.

Senior reasoning

A senior treats a clustering as a hypothesis with a price tag. They ask what the segments would change, build a structureless reference and a stability check, test scale sensitivity, look for a difference in outcomes that were not used to build the clusters, and insist on a holdout before naming anyone. They know PCA and anomaly scores are rankings of variance and unusualness, not of relevance or harm, and they price the alert list.

Interview question

"You clustered customers and found five segments. How do you know they are real and useful?" How would you structure the answer?

Outline your answer first.

Recall cards scheduled after completion

Name four checks before calling a clustering a segmentation, in order from cheapest to most decisive.
Why can PC1 be useless for prediction, and what do you do before PCA or k-means?

Reviewed on a 1 · 3 · 7 · 14 · 30-day schedule; a miss returns the card to 1 day.

Prerequisites and related concepts

References

Clustering (scikit-learn User Guide 2.3) — scikit-learn developerscore
States k-means assumptions (convex, isotropic clusters, k required, local minima), the sensitivity of DBSCAN to eps, and the silhouette and adjusted Rand index definitions. (2.3.2 K-means; 2.3.7 DBSCAN; 2.3.11 Clustering performance evaluation)
Silhouettes: A graphical aid to the interpretation and validation of cluster analysis — Peter J. Rousseeuw, 1987optional
Defines the silhouette width as a graphical aid comparing cluster cohesion with separation.
Cluster-wise assessment of cluster stability — Christian Hennig, 2007core
Cluster-wise stability by bootstrap resampling, which supports judging individual clusters by how often they recur.
A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise — Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, 1996optional
Density-based clusters of arbitrary shape with explicit noise points and the eps and minimum-points parameters.
Isolation Forest — Fei Tony Liu, Kai Ming Ting, Zhi-Hua Zhou, 2008optional
Anomalies are isolated in fewer random splits, so a short average path length signals an outlier.
k-means++: The Advantages of Careful Seeding — David Arthur, Sergei Vassilvitskii, 2007optionalaccess required
Defines k-means++ seeding (sampling each new centre with probability proportional to squared distance) and its O(log k)-competitive expected guarantee.

Optional sections

Deep dive · 10 min

k-means objective. k-means minimizes the within-cluster sum of squares by alternating assignments and centre updates; it converges to a local minimum, which is why n_init restarts and k-means++ seeding exist (Arthur and Vassilvitskii, 2007). The objective always falls as k rises, so inertia cannot choose k; silhouette can help but, as the lab shows, peaks arbitrarily on structureless data.

Why the raw clustering is stable. The partition is a threshold on the fare column; resamples of a Gaussian column cut near the same value, so labels agree. Stability measures the repeatability of the algorithm on the data, not whether the data contain groups.

A structureless reference. Generate data that keep each feature's marginal distribution and destroy joint structure (permute columns independently, or sample from a Gaussian with the same covariance), cluster it with the same settings and compare silhouette and stability. More formal versions are gap-statistic style methods; the idea is the same, a null you can compute.

PCA. Components are eigenvectors of the covariance matrix ordered by eigenvalue; scaled inputs give components of the correlation matrix. Whether to keep a component should depend on the downstream metric, tested on held-out data, with the PCA fitted inside the training fold (Day 9 rule).

Anomaly detection. Isolation forests, local outlier factors and distance-to-nearest-neighbour scores differ in what unusual means. The contamination parameter converts scores to labels using an assumed share of anomalies; it is a decision threshold in disguise (Day 13).

Hands-on lab: Method assumptions, choosing k, and a short anomaly list · 20 min

Run the script. Part A clusters two crescents with four methods, part B reads silhouette against k on two real groups and on one Gaussian cloud, part C ranks 25 anomalies among 5,025 rows with an isolation forest. Then:

Why does k-means fail on crescents while single linkage and DBSCAN succeed, and what would break them?
How much does the silhouette differ across k on the cloud, and what does that say about "the best k"?
At 0.5% anomalies, what precision does the top 50 reach and what would you need before acting on the list?

import numpy as np
from sklearn.cluster import DBSCAN, AgglomerativeClustering, KMeans
from sklearn.datasets import make_moons
from sklearn.ensemble import IsolationForest
from sklearn.metrics import adjusted_rand_score as ari, average_precision_score, silhouette_score
from sklearn.preprocessing import StandardScaler

# A) Method assumptions: k-means wants compact round groups; DBSCAN and single linkage follow density and chains
X, truth = make_moons(600, noise=0.06, random_state=14)
for name, lab in [("k-means", KMeans(2, n_init=10, random_state=0).fit_predict(X)),
                  ("Ward linkage", AgglomerativeClustering(2, linkage="ward").fit_predict(X)),
                  ("single linkage", AgglomerativeClustering(2, linkage="single").fit_predict(X)),
                  ("DBSCAN eps=0.2", DBSCAN(eps=0.2, min_samples=5).fit_predict(X))]:
    print(f"A) {name:15s} agreement with the true shapes {ari(truth, lab):.2f}")

# B) The number of clusters is a choice, and silhouette keeps recommending one on structureless data too
rng = np.random.default_rng(14)
cloud = StandardScaler().fit_transform(rng.normal(size=(900, 2)))
groups = StandardScaler().fit_transform(np.r_[rng.normal([0, 0], 0.5, (450, 2)), rng.normal([4, 4], 0.5, (450, 2))])
for name, Z in [("two real groups", groups), ("one Gaussian cloud", cloud)]:
    s = {k: silhouette_score(Z, KMeans(k, n_init=10, random_state=0).fit_predict(Z)) for k in range(2, 7)}
    print(f"B) {name:18s} silhouette by k: " + ", ".join(f"{k}:{v:.2f}" for k, v in s.items()) + f" -> best k = {max(s, key=s.get)}")

# C) Anomaly scores: 0.5% true anomalies, so even a decent ranking gives a short, impure list (Day 13)
normal = rng.normal(size=(5000, 4))
odd = rng.normal(size=(25, 4)) * 0.8 + rng.choice([-1, 1], (25, 4)) * 1.6
Xa = np.vstack([normal, odd]); ya = np.r_[np.zeros(5000, bool), np.ones(25, bool)]
score = -IsolationForest(n_estimators=200, random_state=0).fit(Xa).score_samples(Xa)
top = np.argsort(score)[::-1][:50]
print(f"C) isolation forest: AP {average_precision_score(ya, score):.2f} (floor {ya.mean():.3f}); "
      f"top 50 holds {ya[top].sum()} of 25 anomalies, precision {ya[top].mean():.0%}")

Interview practice · 10 min

Your team clustered 2 million app users into eight segments and wants to use them for product decisions. What do you ask before agreeing?

Answer as you would in the interview.

Content version 6 · last verified 2026-10-11 · depends on scikit-learn, numpy

1 Recall · 5 min

2 Concept · 10 min