Part IV · Unsupervised learning | the k-means objective, Lloyd's algorithm and k-means++, choosing k (elbow, silhouette, gap statistic), hierarchical clustering and linkage, DBSCAN and HDBSCAN, spectral clustering and the normalised cut, Kleinberg's impossibility theorem | reading: Hastie, Tibshirani & Friedman, The Elements of Statistical Learning (2nd ed.), §14.3; von Luxburg, "A tutorial on spectral clustering" (2007); Arthur & Vassilvitskii (2007); Kleinberg (2002)
Lecture 14 listed four kinds of structure in unlabelled data; this lecture takes the second, groups. A clustering divides the data so that points in the same group are more alike than points in different groups. It is the most used unsupervised method and the least well defined: "alike" needs a similarity and "groups" a scale. We meet four families (centroids, trees, density, graphs) and end with a theorem: no clustering method has three properties that each seem indispensable.
By the end you should be able to run Lloyd's algorithm and k-means++ and prove that Lloyd's algorithm terminates; choose \(k\) three ways and explain why they disagree; read a dendrogram and the effect of the linkage; explain DBSCAN's core, border and noise points and what HDBSCAN adds; derive spectral clustering from the normalised cut, using the Laplacian of Lecture 9; and state Kleinberg's impossibility theorem.
The simplest description of a group is its centre: summarise \(n\) points by \(k\) centres, minimising the squared distance from each point to its nearest centre.
Let \(x_1,\dots,x_n\in\mathbb R^d\) and let \(k\) be an integer. The k-means problem is to choose
to minimise the within-cluster sum of squares
$$J(c,\mu)=\sum_{i=1}^n\lVert x_i-\mu_{c(i)}\rVert^2.$$For fixed centres, the best assignment sends each point to its nearest centre. For a fixed assignment, the best centre of each cluster is the mean (centroid) of its points.
Lloyd's algorithm alternates these two steps from some starting centres until the assignment stops changing.
Customers choose the nearest of \(k\) shops; each shop moves to the average position of its customers; repeat. The total walking only falls (Theorem 15.1), but two shops that start in one neighbourhood may stay there while a distant one shares a single shop: a local minimum. Squared distance also favours round clusters of similar spread, and lets one far-away point pull a centre a long way.
Each assignment step and each update step of Lloyd's algorithm leaves \(J\) unchanged or lowers it.
If ties in the assignment step are broken in favour of a point's current cluster, the algorithm reaches a partition that no step changes after finitely many iterations (at most the number of partitions of \(n\) points into \(k\) groups).
Assignment. With the centres fixed, \(J\) is a sum of separate terms \(\lVert x_i-\mu_{c(i)}\rVert^2\), each minimised by the nearest centre. The old assignment is one of the options, so \(J\) cannot rise.
Update. With the assignment fixed, \(J\) splits into one term per cluster \(S_j\). Writing \(\bar x_j\) for the mean of \(S_j\),
$$\sum_{i\in S_j}\lVert x_i-\mu\rVert^2=\sum_{i\in S_j}\lVert x_i-\bar x_j\rVert^2+|S_j|\,\lVert\bar x_j-\mu\rVert^2,$$because the cross term vanishes:
$$2(\bar x_j-\mu)^\top\sum_{i\in S_j}(x_i-\bar x_j)=0.$$So the mean is the unique minimiser, and \(J\) cannot rise.
Termination. After each update the centres are the means of the current partition, so \(J\) is a function of the partition alone. With the tie rule, an assignment step that changes the partition moves some point to a strictly nearer centre, so \(J\) falls strictly; the following update does not raise it.
Hence no partition occurs twice, and there are finitely many partitions. \(\square\)
The theorem promises a local minimum, a partition neither step can improve, not the global one. The global problem is hard.
Finding the partition that minimises \(J\) is NP-hard:
(Statement.)
So we run Lloyd's algorithm from several starts and keep the best. A point far from every centre chosen so far probably lies in a cluster with no centre yet, so k-means++ favours it, with enough randomness that a lone outlier is not always chosen.
Choose the centres as follows.
Then, before any Lloyd iterations,
$$\mathbb E\,J_{\text{k-means++}}\;\le\;8(\ln k+2)\,J_{\text{opt}}.$$(Statement. Lloyd's algorithm started from these centres can only lower \(J\) further, by Theorem 15.1.)
Our first data set is a city's bike-share system in its first winter. A station's character shows in when people ride from it (home stations empty in the morning, office stations in the evening, leisure stations at weekends and late at night), so we describe each station by the shape of its hourly departures.
All 300,400 Citi Bike trips that started in January 2014 (one row per trip: start and end times, stations with coordinates, rider type), from the operator's public system data, via the copy in the GitHub repository Tmills1/Citibike-Tripdata; the official Amazon S3 archive was not reachable from the build environment. The system then had about 330 stations, in Manhattan below 60th Street and western Brooklyn. We keep the 290 stations with at least 200 departures and describe each by 48 numbers: average departures per day in each hour on weekdays (23 days, including New Year's Day and Martin Luther King Jr Day) and weekends (8 days), divided by their total so that only the shape remains. January is cold, so weekend leisure trips are scarcer than in summer.
# Citi Bike, January 2014: each station's hourly departure profile, clustered with Lloyd's algorithm import numpy as np, pandas as pd tr = pd.read_csv('data/2014-01 - Citi Bike trip data.csv', parse_dates=['starttime']) tr['weekend'] = tr.starttime.dt.dayofweek >= 5 tr['hour'] = tr.starttime.dt.hour st = tr.groupby('start station id').agg(name=('start station name', 'first'), lat=('start station latitude', 'first'), lon=('start station longitude', 'first'), trips=('hour', 'size')) st = st[st.trips >= 200] # stations with at least 200 departures in the month sub = tr[tr['start station id'].isin(st.index)] row = st.index.get_indexer(sub['start station id']) cnt = np.zeros((len(st), 48)); np.add.at(cnt, (row, sub.weekend.to_numpy() * 24 + sub.hour.to_numpy()), 1) rate = cnt / np.repeat([23, 8], 24) # per day: January 2014 had 23 weekdays, 8 weekend days prof = rate / rate.sum(1, keepdims=True) # 48 numbers per station, summing to 1: the *shape* Xc = prof * 48 # scaled so that a flat profile is all ones print(f"{len(tr):,} trips, {len(st)} stations with 200+ departures; profile = 24 weekday + 24 weekend hours") def lloyd(X, C, max_iter=100): # Lloyd's algorithm from given starting centres obj = [] for _ in range(max_iter): d2 = ((X[:, None, :] - C[None]) ** 2).sum(-1); lab = d2.argmin(1) obj.append(d2[np.arange(len(X)), lab].sum()) Cn = np.array([X[lab == j].mean(0) if np.any(lab == j) else C[j] for j in range(len(C))]) if np.allclose(Cn, C): break C = Cn return lab, C, obj def kmeanspp(X, k, rng): # k-means++ seeding (Arthur and Vassilvitskii, 2007) C = [X[rng.integers(len(X))]] for _ in range(k - 1): d2 = ((X[:, None, :] - np.array(C)[None]) ** 2).sum(-1).min(1) C.append(X[rng.choice(len(X), p=d2 / d2.sum())]) return np.array(C) rng = np.random.default_rng(0); k = 3 lab, C, obj = lloyd(Xc, kmeanspp(Xc, k, rng)) assert np.all(np.diff(obj) <= 1e-9) # Theorem 15.1: the objective never increases print(f"k = {k}: Lloyd converged in {len(obj)} iterations; objective {obj[0]:.1f} -> {obj[-1]:.1f}") res = {'random': [], 'k-means++': []} for s in range(50): r = np.random.default_rng(100 + s) res['random'].append(lloyd(Xc, Xc[r.choice(len(Xc), k, replace=False)])[2][-1]) res['k-means++'].append(lloyd(Xc, kmeanspp(Xc, k, r))[2][-1]) best = min(min(v) for v in res.values()) for nm, v in res.items(): v = np.array(v); print(f" 50 starts, {nm:9s} seeding: final objective mean {v.mean():.1f}, worst {v.max():.1f}, " f"within 0.1% of the best found in {np.mean(v < best * 1.001):.0%}") r = np.random.default_rng(7); runs = [lloyd(Xc, kmeanspp(Xc, k, r)) for _ in range(20)] lab, C, obj = min(runs, key=lambda t: t[2][-1]) # keep the best of 20 runs peak = lambda c: int(np.argmax(c[:24])) order = np.argsort([peak(c) for c in C]); lab = np.argsort(order)[lab]; C = C[order] for j in range(k): m = lab == j print(f"cluster {j}: {m.sum():3d} stations, weekday peak at {peak(C[j]):2d}:00, weekend share of departures " f"{(cnt[m, 24:].sum(1) / cnt[m].sum(1)).mean():.2f}, e.g. {', '.join(st.name[m].head(3))}")
300,400 trips, 290 stations with 200+ departures; profile = 24 weekday + 24 weekend hours k = 3: Lloyd converged in 6 iterations; objective 7463.9 -> 3868.8 50 starts, random seeding: final objective mean 3911.2, worst 4448.2, within 0.1% of the best found in 46% 50 starts, k-means++ seeding: final objective mean 3906.1, worst 4442.9, within 0.1% of the best found in 54% cluster 0: 74 stations, weekday peak at 8:00, weekend share of departures 0.19, e.g. W 52 St & 11 Ave, St James Pl & Pearl St, Clinton St & Joralemon St cluster 1: 90 stations, weekday peak at 17:00, weekend share of departures 0.12, e.g. W 17 St & 8 Ave, E 56 St & Madison Ave, E 40 St & 5 Ave cluster 2: 126 stations, weekday peak at 18:00, weekend share of departures 0.22, e.g. Franklin St & W Broadway, Atlantic Ave & Fort Greene Pl, Barrow St & Hudson St
Lloyd's algorithm converges in 6 iterations; the assertion in the code checks Theorem 15.1 at every step. Over 50 runs, k-means++ beats random seeding only slightly (mean 3906.1 against 3911.2; within 0.1% of the best in 54% of runs against 46%), and both sometimes end near 4,440 (a poor local minimum); hence libraries use several starts. The best of 20 runs gives 74 stations whose weekday departures peak at 8 a.m., 90 that peak at 5 p.m. with the fewest weekend trips (12%), and 126 that peak at 6 p.m. with the most (22%). The clusters are geographical, although location was not used.
The points 0, 2 and 10 on a line are clustered with \(k=2\), starting from centres at 0 and 10. After one assignment step and one update step, what is \(J\)?
k-means++ has chosen its first centre. The three remaining points are at distances 1, 2 and 3 from it. What is the probability that the point at distance 3 becomes the second centre?
k-means also compresses. Replace each point by its nearest centre and the data become \(k\) centres plus an index of \(\log_2k\) bits per point. This is vector quantisation, the purpose of Lloyd's memo, and how GIF and PNG-8 reduce an image to a palette of \(k\) colours. Quality is the peak signal-to-noise ratio (PSNR): largest possible pixel value squared over mean squared error, in decibels (10 log₁₀ of the ratio).
# Colour quantisation: k-means on the 65,536 pixels of a public-domain NASA photograph, in RGB space from skimage import data, transform from sklearn.cluster import KMeans img = transform.resize(data.astronaut(), (256, 256), anti_aliasing=True) # Eileen Collins, NASA (public domain) pix = img.reshape(-1, 3) print(f"{len(pix):,} pixels; distinct colours (8 bits per channel): {len(np.unique((pix * 255).round(), axis=0)):,}") quant = {} for kq in [2, 4, 8, 16, 64]: km = KMeans(kq, n_init=4, random_state=0).fit(pix) q = km.cluster_centers_[km.labels_]; quant[kq] = q.reshape(img.shape) psnr = 10 * np.log10(1 / np.mean((q - pix) ** 2)) bits = np.log2(kq) * len(pix) + 24 * kq print(f" k = {kq:2d}: mean squared error {np.mean((q - pix)**2):.5f}, PSNR {psnr:5.1f} dB, " f"{bits / 8 / 1024:6.1f} KiB vs {24 * len(pix) / 8 / 1024:.0f} KiB uncompressed")
65,536 pixels; distinct colours (8 bits per channel): 37,391 k = 2: mean squared error 0.02916, PSNR 15.4 dB, 8.0 KiB vs 192 KiB uncompressed k = 4: mean squared error 0.01007, PSNR 20.0 dB, 16.0 KiB vs 192 KiB uncompressed k = 8: mean squared error 0.00394, PSNR 24.0 dB, 24.0 KiB vs 192 KiB uncompressed k = 16: mean squared error 0.00174, PSNR 27.6 dB, 32.0 KiB vs 192 KiB uncompressed k = 64: mean squared error 0.00042, PSNR 33.8 dB, 48.2 KiB vs 192 KiB uncompressed
The 65,536 pixels use 37,391 colours. With 16 colours the PSNR is 27.6 dB (around 30 dB differences are hard to see at a glance), and the image needs 32 KiB instead of 192 KiB. Each doubling of \(k\) from 2 to 16 cuts the squared error by 2.3 to 2.9, more than the \(2^{2/3}\approx1.6\) that high-resolution quantisation theory predicts in three dimensions (distortion \(\propto k^{-2/d}\)): a photograph's colours crowd into a few regions, which is what clusters are.
\(J\) always falls as \(k\) grows (it is zero at \(k=n\)), so it cannot choose \(k\). Three heuristics look for where more clusters stop paying.
Let point \(i\) lie in cluster \(A\).
The silhouette of \(i\) is
$$s(i)=\frac{b(i)-a(i)}{\max\{a(i),b(i)\}}\in[-1,1],$$and the silhouette of a clustering is the mean of \(s(i)\) over all points.
Values near 1 mean tight, well-separated clusters; near 0, points on a boundary; negative, points nearer another cluster than their own.
# Choosing k for the station profiles: elbow, silhouette and the gap statistic from sklearn.metrics import silhouette_score def km_fit(X, kk, seed=0): return KMeans(kk, n_init=10, random_state=seed).fit(X) ks = range(2, 9); W = {}; sil = {} for kk in ks: m = km_fit(Xc, kk); W[kk] = m.inertia_; sil[kk] = silhouette_score(Xc, m.labels_) # gap statistic (Tibshirani, Walther and Hastie, 2001): compare log W_k with uniform data in the principal-axes box rg = np.random.default_rng(1); mu = Xc.mean(0); U = np.linalg.svd(Xc - mu, full_matrices=False)[2] Z = (Xc - mu) @ U.T; lo, hi = Z.min(0), Z.max(0); B = 10 refW = {kk: [np.log(km_fit(rg.uniform(lo, hi, Z.shape) @ U + mu, kk, b).inertia_) for b in range(B)] for kk in ks} gap = {kk: np.mean(refW[kk]) - np.log(W[kk]) for kk in ks} sk = {kk: np.std(refW[kk]) * np.sqrt(1 + 1 / B) for kk in ks} print(" k W_k (within SS) drop silhouette gap gap s.e.") for kk in ks: print(f"{kk:2d} {W[kk]:10.1f} {('%6.1f' % (W[kk-1] - W[kk])) if kk > 2 else ' -'} {sil[kk]:.3f} {gap[kk]:.3f} {sk[kk]:.3f}") k_gap = min(kk for kk in list(ks)[:-1] if gap[kk] >= gap[kk + 1] - sk[kk + 1]) if any( gap[kk] >= gap[kk + 1] - sk[kk + 1] for kk in list(ks)[:-1]) else None print(f"best silhouette: k = {max(sil, key=sil.get)}; gap rule (smallest k with gap_k >= gap_k+1 - s_k+1): k = {k_gap}")
k W_k (within SS) drop silhouette gap gap s.e. 2 4471.0 - 0.254 1.233 0.015 3 3867.7 603.3 0.182 1.292 0.010 4 3475.6 392.1 0.165 1.329 0.007 5 3211.2 264.3 0.158 1.360 0.014 6 3068.1 143.2 0.111 1.366 0.005 7 2923.3 144.7 0.126 1.389 0.014 8 2831.4 91.9 0.119 1.391 0.010 best silhouette: k = 2; gap rule (smallest k with gap_k >= gap_k+1 - s_k+1): k = 7
The methods disagree. The drops in \(W_k\) shrink steadily (603, 392, 264, 143, 145, 92), with no sharp elbow. The silhouette peaks at \(k=2\) at only 0.254, between "weak" and "no substantial structure" in Kaufman and Rousseeuw's (1990) rule of thumb. The gap statistic keeps rising and chooses \(k=7\).
This is typical of real data: the profiles vary continuously between "residential", "office" and "nightlife", and every \(k\) from 2 to 7 is a defensible summary. Choosing \(k=3\) was a decision, not a discovery.
A point's mean distance to the other points in its cluster is 2, and to the points of the nearest other cluster 5. What is its silhouette?
Instead of one \(k\), we can build the whole nested family. Agglomerative clustering starts with every point alone and repeatedly merges the two closest clusters. The merges form a binary tree, the dendrogram, like a family tree drawn upside down: two branches join at the distance at which their groups merged. A horizontal cut gives a clustering; raising it gives fewer, larger clusters.
The linkage defines the distance between clusters \(A\) and \(B\) from point distances \(d\):
Single linkage is "a friend of a friend is a friend": it follows curved clusters, but a few bridging points join two groups, and it often leaves one giant cluster plus outliers. Complete linkage wants everyone close to everyone (tight, round groups); average is in between. Ward's greedily minimises the k-means objective, giving compact clusters of similar size. The cophenetic correlation, the correlation between \(d(i,j)\) and the height at which \(i\) and \(j\) first join, measures how faithfully a dendrogram represents the distances.
The indicators below are first standardised (mean 0, standard deviation 1), so that GDP in dollars does not dominate the distances.
Eight country-level indicators from Our World in Data's COVID-19 data set (owid/covid-19-data on GitHub, CC BY 4.0, file latest/owid-covid-latest.csv), which collects them from the World Bank's World Development Indicators, the UN's population estimates and the Global Burden of Disease study: GDP per head (purchasing-power adjusted), life expectancy, median age, share aged 65 or over, hospital beds per thousand, diabetes prevalence, cardiovascular death rate, and population density. The World Bank's own data service was not reachable from the build environment; values date from around 2015–2020 by indicator. We keep the 160 countries with all eight, take logarithms of GDP, density and beds, and standardise.
# Hierarchical clustering of countries by development indicators from scipy.cluster.hierarchy import linkage, fcluster, cophenet from scipy.spatial.distance import pdist wd = pd.read_csv('data/owid-latest.csv') cols = ['gdp_per_capita', 'life_expectancy', 'median_age', 'aged_65_older', 'hospital_beds_per_thousand', 'diabetes_prevalence', 'cardiovasc_death_rate', 'population_density'] wd = wd[wd.iso_code.str.len() == 3].dropna(subset=cols + ['continent']).set_index('location') # countries only F = wd[cols].copy() for c in ['gdp_per_capita', 'population_density', 'hospital_beds_per_thousand']: F[c] = np.log(F[c]) Zc = ((F - F.mean()) / F.std()).to_numpy() # standardised: each indicator counts equally print(f"{len(wd)} countries with all {len(cols)} indicators (GDP, density and beds on log scales)") Dc = pdist(Zc); links = {} for meth in ['single', 'complete', 'average', 'ward']: links[meth] = linkage(Zc, meth) cut = fcluster(links[meth], 4, 'maxclust'); sizes = sorted(np.bincount(cut)[1:].tolist(), reverse=True) print(f"{meth:9s} cophenetic correlation {cophenet(links[meth], Dc)[0]:.3f}; 4-cluster sizes {sizes}") cw = fcluster(links['ward'], 4, 'maxclust') for j in range(1, 5): m = cw == j; cont = wd.continent[m].value_counts() print(f"Ward cluster {j} ({m.sum():2d}): median GDP/head ${np.exp(F.gdp_per_capita[m].median()):,.0f}, " f"life exp. {wd.life_expectancy[m].median():.1f}; {', '.join(f'{c} {n}' for c, n in cont.items())}") print(" e.g.", ", ".join(wd.index[m][:6]))
160 countries with all 8 indicators (GDP, density and beds on log scales)
single cophenetic correlation 0.371; 4-cluster sizes [157, 1, 1, 1]
complete cophenetic correlation 0.569; 4-cluster sizes [66, 55, 20, 19]
average cophenetic correlation 0.647; 4-cluster sizes [99, 44, 10, 7]
ward cophenetic correlation 0.596; 4-cluster sizes [52, 48, 42, 18]
Ward cluster 1 (18): median GDP/head $9,582, life exp. 70.5; Asia 8, Africa 5, Oceania 3, South America 2
e.g. Azerbaijan, Botswana, East Timor, Egypt, Fiji, Gabon
Ward cluster 2 (48): median GDP/head $2,846, life exp. 65.8; Africa 30, Asia 13, North America 4, Oceania 1
e.g. Afghanistan, Bangladesh, Benin, Burkina Faso, Burundi, Cambodia
Ward cluster 3 (52): median GDP/head $20,422, life exp. 76.8; Asia 16, North America 15, South America 10, Europe 5, Africa 4, Oceania 2
e.g. Algeria, Antigua and Barbuda, Argentina, Australia, Bahamas, Bahrain
Ward cluster 4 (42): median GDP/head $28,699, life exp. 79.0; Europe 35, Asia 6, North America 1
e.g. Albania, Armenia, Austria, Barbados, Belarus, Belgium
The linkage changes the answer completely. Cut into four clusters, single linkage gives one cluster of 157 countries and three singletons, chaining at its most extreme; average linkage gives 99, 44, 10 and 7; Ward gives 52, 48, 42 and 18. Average linkage preserves distances best (cophenetic correlation 0.647), but that does not make its clusters more useful. Ward's groups read like a development atlas: 48 countries with median GDP per head about $2,800 and median life expectancy 65.8 years, 30 of them in Africa; 18 middle-income countries; 52 higher-income countries with young populations across Asia and the Americas; and 42 countries, 35 of them European, marked above all by old populations. That last group includes Albania, Armenia and Belarus: the indicators measure demography and health as much as income.
A data set contains two long, thin, curved clusters that come close to each other at one end, and nothing else. To recover them by agglomerative clustering, the better linkage is , as long as .
Stuart Lloyd devised the alternating algorithm at Bell Labs in 1957, in an internal memo on quantising signals for pulse-code modulation; it circulated for 25 years before appearing as "Least squares quantization in PCM" (IEEE Transactions on Information Theory, 1982). Hugo Steinhaus had proposed the objective in 1956, Edward Forgy published the same algorithm in 1965, and James MacQueen coined the name "k-means" in 1967. Joe Ward Jr., a statistician with the US Air Force, published his minimum-variance merging rule in 1963 (Journal of the American Statistical Association), and Robert Sokal and Peter Sneath's Principles of Numerical Taxonomy (1963) made dendrograms the standard picture in biology. DBSCAN, by Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu (KDD 1996), received the KDD test-of-time award in 2014, and is among the most cited papers in data mining.
k-means and Ward's linkage look for round groups and place every point somewhere. Alternatively (Lecture 14), a cluster is a high-density region separated from others by low density, and points in low-density regions belong to no cluster.
Fix a radius \(\varepsilon\) and a count minPts.
DBSCAN is single linkage restricted to dense points: clusters may take any shape, like a crowd that snakes as easily as it huddles, but chains must pass through core points, so a thin line of stray points no longer bridges two groups. The parameters set a density threshold (a box-kernel density estimate compared with a fixed level). To choose \(\varepsilon\), sort each point's distance to its \((\text{minPts}-1)\)-th neighbour and look for the knee. HDBSCAN (Campello, Moulavi and Sander, 2013) removes \(\varepsilon\): it builds the hierarchy of DBSCAN clusterings over all density levels, as a dendrogram, and keeps the clusters that persist over the widest range of levels, subject to a minimum cluster size.
The adjusted Rand index (ARI) scores agreement between two clusterings over all pairs of points, corrected for chance: 1 means identical, about 0 means chance.
# Density-based clustering: DBSCAN and HDBSCAN find shapes and noise that k-means cannot from sklearn.datasets import make_moons from sklearn.cluster import DBSCAN, HDBSCAN from sklearn.metrics import adjusted_rand_score as ari from sklearn.neighbors import NearestNeighbors Xm, ym = make_moons(400, noise=0.07, random_state=0) rn = np.random.default_rng(5); Xn = rn.uniform([-1.5, -1], [2.5, 1.5], (40, 2)) # 40 points of background noise Xdb = np.vstack([Xm, Xn]); ydb = np.r_[ym, -np.ones(40, int)] kd = np.sort(NearestNeighbors(n_neighbors=5).fit(Xdb).kneighbors(Xdb)[0][:, -1]) print(f"distance to 4th neighbour: median {np.median(kd):.3f}, 90th percentile {np.quantile(kd, 0.9):.3f}, " f"95th {np.quantile(kd, 0.95):.3f}") real = ydb >= 0 for name, labs in [('k-means, k = 2', KMeans(2, n_init=10, random_state=0).fit_predict(Xdb))] + \ [(f'DBSCAN eps = {e}, minPts = 5', DBSCAN(eps=e, min_samples=5).fit_predict(Xdb)) for e in (0.05, 0.12, 0.2, 0.4)] + \ [('HDBSCAN min_cluster_size = 15', HDBSCAN(min_cluster_size=15, copy=True).fit_predict(Xdb))]: ncl = len(set(labs) - {-1}) print(f"{name:30s} clusters {ncl:2d}, noise points {np.sum(labs == -1):3d} " f"(of which true noise {np.sum((labs == -1) & ~real):2d}/40), ARI on the moons {ari(ym, labs[real]):.3f}")
distance to 4th neighbour: median 0.072, 90th percentile 0.138, 95th 0.248 k-means, k = 2 clusters 2, noise points 0 (of which true noise 0/40), ARI on the moons 0.274 DBSCAN eps = 0.05, minPts = 5 clusters 21, noise points 304 (of which true noise 36/40), ARI on the moons 0.009 DBSCAN eps = 0.12, minPts = 5 clusters 2, noise points 32 (of which true noise 27/40), ARI on the moons 0.975 DBSCAN eps = 0.2, minPts = 5 clusters 1, noise points 22 (of which true noise 22/40), ARI on the moons 0.000 DBSCAN eps = 0.4, minPts = 5 clusters 1, noise points 10 (of which true noise 10/40), ARI on the moons 0.000 HDBSCAN min_cluster_size = 15 clusters 2, noise points 33 (of which true noise 28/40), ARI on the moons 0.966
The data are 400 points on two half-moons plus 40 noise points. k-means cuts the moons in half (ARI 0.274). DBSCAN with \(\varepsilon=0.12\) (near the 90th percentile of neighbour distances) recovers both moons (ARI 0.975) and labels 27 of the 40 noise points as noise, but also 5 moon points (32 noise labels): density methods sacrifice sparse cluster edges to keep clusters apart. The parameter is touchy: at \(\varepsilon=0.05\) most points are noise and the moons fall into 21 fragments; at 0.2 they merge. HDBSCAN, told only that a cluster has at least 15 points, does almost as well (ARI 0.966) with no radius to tune.
With minPts = 5, a point has only 3 points (itself included) within \(\varepsilon\), and one of them is a core point. What does DBSCAN call it?
Lecture 9 built graphs whose nodes are data points and whose edges join similar points, with the graph Laplacian \(L=D-A\) (\(A\) the weight matrix, \(D\) the diagonal matrix of degrees). Clustering becomes a graph problem: cut few edges, without cheating by cutting off one lonely node.
Let a graph have weights \(w_{ij}\) and degrees \(d_i=\sum_jw_{ij}\). For a split of the nodes into \(A\) and its complement \(\bar A\), set
$$\operatorname{cut}(A,\bar A)=\sum_{i\in A,\,j\in\bar A}w_{ij},\qquad \operatorname{vol}(A)=\sum_{i\in A}d_i.$$\(\operatorname{vol}(A)\) is the volume of \(A\). The normalised cut (Shi and Malik, 2000) is
$$\operatorname{Ncut}(A,\bar A)=\operatorname{cut}(A,\bar A)\left(\frac1{\operatorname{vol}(A)}+\frac1{\operatorname{vol}(\bar A)}\right).$$The volume terms penalise unbalanced splits: cutting off one weak node has a small cut but a large \(1/\operatorname{vol}(A)\). Minimising Ncut is NP-hard; a relaxation makes it an eigenvalue problem.
For a split \((A,\bar A)\) define \(f\in\mathbb R^n\) by
$$f_i=\sqrt{\frac{\operatorname{vol}(\bar A)}{\operatorname{vol}(A)}}\ (i\in A),\qquad f_i=-\sqrt{\frac{\operatorname{vol}(A)}{\operatorname{vol}(\bar A)}}\ (i\in\bar A).$$Then
$$f^\top D\mathbf 1=0\qquad\text{and}\qquad\operatorname{Ncut}(A,\bar A)=\frac{f^\top Lf}{f^\top Df}.$$Minimising the right-hand side over all real \(f\) with \(f^\top D\mathbf 1=0\), instead of over two-valued \(f\), is solved by the eigenvector of \(Lf=\lambda Df\) with the second-smallest eigenvalue.
Splitting the nodes by the sign of that eigenvector (or running k-means on the first few eigenvectors, for more than two clusters) is spectral clustering.
Write \(V=\operatorname{vol}(A)+\operatorname{vol}(\bar A)\), and let \(\alpha\) and \(\beta\) be the two values of \(|f_i|\):
$$\alpha=\sqrt{\operatorname{vol}(\bar A)/\operatorname{vol}(A)},\qquad\beta=\sqrt{\operatorname{vol}(A)/\operatorname{vol}(\bar A)}.$$Orthogonality. Both terms below equal \(\sqrt{\operatorname{vol}(A)\operatorname{vol}(\bar A)}\), so
$$f^\top D\mathbf 1=\alpha\operatorname{vol}(A)-\beta\operatorname{vol}(\bar A)=0.$$Denominator.
$$f^\top Df=\alpha^2\operatorname{vol}(A)+\beta^2\operatorname{vol}(\bar A)=\operatorname{vol}(\bar A)+\operatorname{vol}(A)=V.$$Numerator. The Laplacian's quadratic form (Lecture 9) is \(f^\top Lf=\tfrac12\sum_{i,j}w_{ij}(f_i-f_j)^2\). Only pairs across the cut contribute, each with \((f_i-f_j)^2=(\alpha+\beta)^2\). Since \(\alpha+\beta=V/\sqrt{\operatorname{vol}(A)\operatorname{vol}(\bar A)}\),
$$f^\top Lf=\operatorname{cut}(A,\bar A)\,(\alpha+\beta)^2=\operatorname{cut}(A,\bar A)\,\frac{V^2}{\operatorname{vol}(A)\operatorname{vol}(\bar A)}.$$Dividing by \(f^\top Df=V\) gives
$$\frac{f^\top Lf}{f^\top Df}=\operatorname{cut}(A,\bar A)\,\frac{V}{\operatorname{vol}(A)\operatorname{vol}(\bar A)}=\operatorname{Ncut}(A,\bar A).$$Relaxation. The smallest eigenvalue of \(Lf=\lambda Df\) is 0, with eigenvector \(\mathbf 1\). By the Rayleigh–Ritz (Courant–Fischer) theorem, the minimum of \(f^\top Lf/f^\top Df\) over \(f\) that are \(D\)-orthogonal to \(\mathbf 1\) is the second eigenvalue, attained at its eigenvector.
The relaxed minimum is a lower bound on the minimum Ncut; how close the rounded split comes to the optimum depends on the graph (von Luxburg, 2007, §5). \(\square\)
Two facts make the method work. If the graph has \(c\) components, the eigenvalue 0 has multiplicity \(c\) with eigenvectors constant on each component, so clusters can be read off exactly, and small perturbations move the eigenvectors only a little. And the eigenvectors depend on the graph, not on cluster shape, so a well-connected curved cluster is as easy as a round one. In practice one uses the normalised Laplacian \(D^{-1/2}LD^{-1/2}\), whose eigenvectors are those of \(Lf=\lambda Df\) rescaled by \(D^{1/2}\), and normalises the rows of the eigenvector matrix before k-means (Ng, Jordan and Weiss, 2002).
\(f^\top Lf\) is small when connected nodes have similar values, so the eigenvectors run from the smoothest pattern on the graph to the roughest, like a drum's modes from the deepest note up. The smoothest is constant. The next, the Fiedler vector after Miroslav Fiedler, who studied it in 1973, changes sign where there are few edges to cross: at the best cut.
Wayne Zachary observed a university karate club for three years in the early 1970s and recorded which of its 34 members interacted outside the club (78 friendships). The club split after a dispute between the instructor ("Mr Hi") and the president (the "Officer"), and Zachary recorded each member's faction (Journal of Anthropological Research, 1977). The graph, with the faction labels, is distributed with NetworkX and was used in Lecture 9.
# Spectral clustering: the graph Laplacian of Lecture 9 separates what k-means cannot import networkx as nx from scipy.sparse.csgraph import laplacian def spectral_embed(X, nn=10, k=2): A = NearestNeighbors(n_neighbors=nn + 1).fit(X).kneighbors_graph(X).toarray(); np.fill_diagonal(A, 0) A = np.maximum(A, A.T) # symmetric k-nearest-neighbour graph L = laplacian(A, normed=True); vals, vecs = np.linalg.eigh(L) U = vecs[:, :k]; U = U / np.linalg.norm(U, axis=1, keepdims=True) # Ng, Jordan and Weiss row normalisation return vals[:4], U lab_km = KMeans(2, n_init=10, random_state=0).fit_predict(Xm) print(f"two moons, 400 points: k-means ARI with the true moons {ari(ym, lab_km):.3f}") for nn in (5, 10, 20, 40): vals, Um = spectral_embed(Xm, nn) lab_sp = KMeans(2, n_init=10, random_state=0).fit_predict(Um) print(f" spectral, {nn:2d}-NN graph: smallest eigenvalues {np.round(vals, 4)}, ARI {ari(ym, lab_sp):.3f}") G = nx.karate_club_graph(); Ak = nx.to_numpy_array(G) truth = np.array([G.nodes[i]['club'] == 'Officer' for i in G]) # which club each member joined after the split Dk = Ak.sum(1); Lk = np.diag(Dk) - Ak from scipy.linalg import eigh lv, lvec = eigh(Lk, np.diag(Dk)) # generalised problem L f = lambda D f (Theorem 15.4) fied = lvec[:, 1]; split = fied > 0 acc = max(np.mean(split == truth), np.mean(split != truth)) cutw = Ak[split][:, ~split].sum(); ncut = cutw / Dk[split].sum() + cutw / Dk[~split].sum() print(f"karate club: second eigenvalue {lv[1]:.4f}; sign of the Fiedler vector puts {acc * 34:.0f} of 34 members " f"in their actual club; cut {cutw:.0f} edges, Ncut {ncut:.3f}") wrong = np.flatnonzero((split == truth) != (np.mean(split == truth) > 0.5)) print(f" misplaced member(s): {wrong.tolist()} (Fiedler values {np.round(fied[wrong], 3).tolist()})") print(f" k-means on the 2-D spring layout, for comparison: ARI {ari(truth, KMeans(2, n_init=10, random_state=0).fit_predict(np.array(list(nx.spring_layout(G, seed=1).values())))):.3f}")
two moons, 400 points: k-means ARI with the true moons 0.269 spectral, 5-NN graph: smallest eigenvalues [-0. 0. 0.0008 0.0008], ARI 1.000 spectral, 10-NN graph: smallest eigenvalues [0. 0.0006 0.0018 0.0033], ARI 0.748 spectral, 20-NN graph: smallest eigenvalues [-0. 0.0025 0.0069 0.0109], ARI 0.713 spectral, 40-NN graph: smallest eigenvalues [0. 0.0103 0.0257 0.0429], ARI 0.554 karate club: second eigenvalue 0.1101; sign of the Fiedler vector puts 33 of 34 members in their actual club; cut 22 edges, Ncut 0.191 misplaced member(s): [8] (Fiedler values [0.013]) k-means on the 2-D spring layout, for comparison: ARI 0.882
On the moons (without noise), k-means again scores ARI about 0.27. Spectral clustering depends on the graph. With 5 nearest neighbours per point the graph falls into two pieces, one per moon: two eigenvalues are exactly 0 and the clustering is perfect. With 10, 20 and 40 neighbours a few edges cross, the second eigenvalue rises above 0, and the ARI falls to 0.748, 0.713 and 0.554: better than k-means, but now a user's choice decides the answer. On the karate club, the sign of the second generalised eigenvector puts 33 of the 34 members in the faction they joined, cutting 22 friendships (Ncut 0.191). The misplaced member, number 9 in Zachary's numbering, has Fiedler value 0.013, near zero; Zachary's min-cut analysis also misassigned him: three of his five friends joined the Officer, but he joined Mr Hi.
Suppose the data come from \(k\) Gaussians with means \(\mu_j\), equal weights and common covariance \(\sigma^2I\). The posterior probability that \(x_i\) came from component \(j\) is
$$r_{ij}=\frac{\exp(-\lVert x_i-\mu_j\rVert^2/2\sigma^2)}{\sum_l\exp(-\lVert x_i-\mu_l\rVert^2/2\sigma^2)}.$$As \(\sigma\to0\) this tends to 1 for the nearest mean and 0 for the others: a hard assignment. The expectation–maximisation algorithm for the mixture (Lecture 17a) alternates computing \(r_{ij}\) with re-estimating the means as \(r\)-weighted averages, so in the limit it is Lloyd's algorithm.
Hence k-means' preference for round clusters of equal spread and size; the full mixture relaxes each assumption and gives soft memberships. The same limit of a Dirichlet-process mixture gives DP-means (Kulis and Jordan, 2012): k-means plus a penalty \(\lambda\) per cluster, so a point farther than \(\sqrt\lambda\) from every centre starts a new cluster.
Our methods disagree, and so do our rules for \(k\). Is the fault in the methods or the question? Kleinberg (2002) wrote down three properties any reasonable method seems to need, and proved that no method has all three. A clustering function \(f\) takes a distance function \(d\) on a set of \(n\ge2\) points and returns a partition of the points.
A clustering function \(f\) may satisfy:
For \(n\ge2\) points, no clustering function satisfies scale invariance, richness and consistency.
Each pair of the three can be satisfied (by single linkage with a suitable stopping rule).
A partition \(\Gamma'\) refines \(\Gamma\) if every cluster of \(\Gamma'\) lies inside a cluster of \(\Gamma\). The key lemma: under scale invariance and consistency, the range of \(f\) is an antichain, that is, no partition in it is a proper refinement of another.
Suppose \(\Gamma=f(d)\) and \(\Gamma'=f(d')\), with \(\Gamma'\) a proper refinement of \(\Gamma\). Build a distance \(d''\) that is
From \(d'\): rescale it so that its within-cluster distances exceed those of \(d''\) (scale invariance). If the moderate distances are large enough, \(d''\) shrinks distances inside the clusters of \(\Gamma'\) and stretches those between them, so consistency gives \(f(d'')=\Gamma'\).
From \(d\), with a different rescaling: if the moderate distances are small enough, \(d''\) shrinks distances inside the clusters of \(\Gamma\) and stretches those between them, so \(f(d'')=\Gamma\).
Kleinberg shows that one choice of the moderate distances meets both requirements, giving \(\Gamma=\Gamma'\), a contradiction.
Richness requires every partition to be in the range, including the partition into singletons, which refines every other partition. With at least two points this contradicts the antichain property. For the full argument see Kleinberg (2002), Theorem 3.1. \(\square\)
Each of our methods gives up one axiom. k-means with fixed \(k\) fails richness; single linkage stopped at a fixed distance threshold fails scale invariance; stopped at a threshold relative to the largest distance, it fails consistency. So every method makes a choice (of scale, number of clusters, or what counts as "more separated") that the data cannot make for it, and disagreement is to be expected. Kleinberg himself considered weakening consistency to "refinement consistency"; later work studied quality measures for clusterings rather than clustering functions (Ackerman and Ben-David, 2008).
The practical lesson: a clustering answers a question you chose, not a fact found in the data; report how it moves when the choices move.
# No single right answer: how much do different methods agree on the Citi Bike stations? from sklearn.cluster import AgglomerativeClustering, SpectralClustering from sklearn.mixture import GaussianMixture methods = {'k-means': KMeans(3, n_init=10, random_state=0).fit_predict(Xc), 'Ward': AgglomerativeClustering(3, linkage='ward').fit_predict(Xc), 'average link': AgglomerativeClustering(3, linkage='average').fit_predict(Xc), 'spectral': SpectralClustering(3, affinity='nearest_neighbors', n_neighbors=10, random_state=0).fit_predict(Xc), 'Gaussian mixture': GaussianMixture(3, covariance_type='diag', random_state=0).fit(Xc).predict(Xc)} names_m = list(methods) print(" " * 18 + "".join(f"{n[:9]:>10s}" for n in names_m)) for a in names_m: print(f"{a:18s}" + "".join(f"{ari(methods[a], methods[b]):10.2f}" for b in names_m)) print("cluster sizes:", {n: sorted(np.bincount(v).tolist(), reverse=True) for n, v in methods.items()}) seedari = [ari(KMeans(3, n_init=1, random_state=s).fit_predict(Xc), methods['k-means']) for s in range(20)] print(f"k-means with a single random start, 20 seeds: ARI with the best run min {min(seedari):.2f}, median {np.median(seedari):.2f}")
k-means Ward average l spectral Gaussian
k-means 1.00 0.60 0.06 0.67 0.47
Ward 0.60 1.00 0.03 0.44 0.42
average link 0.06 0.03 1.00 0.05 0.02
spectral 0.67 0.44 0.05 1.00 0.42
Gaussian mixture 0.47 0.42 0.02 0.42 1.00
cluster sizes: {'k-means': [126, 90, 74], 'Ward': [118, 114, 58], 'average link': [260, 17, 13], 'spectral': [115, 94, 81], 'Gaussian mixture': [101, 100, 89]}
k-means with a single random start, 20 seeds: ARI with the best run min 0.28, median 0.80
Five methods, each asked for three clusters of the 290 profiles, agree only moderately. The ARI is 0.67 between k-means and spectral clustering, 0.60 between k-means and Ward, and 0.42–0.47 between the Gaussian mixture and the others. Average linkage disagrees with everything (ARI at most 0.06): one cluster of 260 stations and two small unusual groups. Over 20 single-start runs, k-means' ARI with its best of ten starts is as low as 0.28 (median 0.80). What is robust is the morning-peak versus evening-peak contrast; the boundaries are a matter of method.
Which of Kleinberg's axioms does k-means with \(k=3\) fixed in advance violate?
Retailers and banks segment customers with k-means or Gaussian mixtures. In single-cell RNA sequencing (thousands of genes in each of millions of cells), new cell types are found by clustering a nearest-neighbour graph with community detection (Louvain, Leiden), close to spectral clustering, by default in Seurat and Scanpy. Pipelines remove near-duplicates by clustering embeddings. Vector databases, serving the retrieval of Lecture 12, index billions of embeddings by k-means: the inverted-file index searches only the Voronoi cells of k-means centres nearest a query, and product quantisation runs k-means on pieces of each vector, Lloyd's quantiser at scale.
Assignment: {1} to centre 1 and {2, 3, 8, 9, 20} to centre 2. Update: centres 1 and 8.4.
Assignment: 1 and 2 are nearer to 1 (the point 3 is at distance 2 from 1 and 5.4 from 8.4), so {1, 2, 3} and {8, 9, 20}. Update: centres 2 and 12.33.
Assignment: {1, 2, 3} and {8, 9, 20} again (8 is at distance 6 from 2 and 4.33 from 12.33), so the algorithm stops with
$$J=2+\big((8-12.33)^2+(9-12.33)^2+(20-12.33)^2\big)=2+88.67=90.67.$$The split {1, 2, 3, 8, 9} and {20} has centres 4.6 and 20 and \(J=53.2\), which is lower; it is the global minimum among the splits of the sorted points into two intervals (the only candidates in one dimension). Lloyd's algorithm stopped at a local minimum.
Let \(m\) be the merged mean:
$$m=\frac{|A|\bar x_A+|B|\bar x_B}{|A|+|B|}.$$By the identity in the proof of Theorem 15.1,
$$\sum_{i\in A}\lVert x_i-m\rVert^2=\sum_{i\in A}\lVert x_i-\bar x_A\rVert^2+|A|\lVert\bar x_A-m\rVert^2,$$and similarly for \(B\). The increase is therefore \(|A|\lVert\bar x_A-m\rVert^2+|B|\lVert\bar x_B-m\rVert^2\). Since
$$\bar x_A-m=\frac{|B|}{|A|+|B|}(\bar x_A-\bar x_B),\qquad\bar x_B-m=-\frac{|A|}{|A|+|B|}(\bar x_A-\bar x_B),$$the increase is
$$\frac{|A||B|^2+|B||A|^2}{(|A|+|B|)^2}\lVert\bar x_A-\bar x_B\rVert^2=\frac{|A||B|}{|A|+|B|}\lVert\bar x_A-\bar x_B\rVert^2.$$The degrees are 2, 2, 3 in each triangle (the bridge raises one node to 3), so each triangle has volume 7 and the total is 14.
Splitting the triangles cuts 1 edge: \(\operatorname{Ncut}=1\cdot(1/7+1/7)=0.286\).
Cutting off a degree-2 node cuts 2 edges: \(\operatorname{Ncut}=2(1/2+1/12)=1.167\).
The balanced split wins, although a plain minimum cut (1 edge against 2) would also choose it here; with a pendant node of degree 1, the plain cut would be tied between cutting it off and splitting the triangles (both cost 1 edge), while Ncut clearly prefers the balanced split.
For the indicator \(\mathbf 1_C\) of a component \(C\),
$$\mathbf 1_C^\top L\mathbf 1_C=\tfrac12\sum_{ij}w_{ij}(\mathbf 1_C(i)-\mathbf 1_C(j))^2=0,$$because every edge has both ends in \(C\) or neither. Since \(L\) is positive semi-definite, a zero quadratic form means \(L\mathbf 1_C=0=0\cdot D\mathbf 1_C\). The two indicators have disjoint supports, so they are independent.
(Conversely every \(f\) with \(f^\top Lf=0\) is constant on each component, so the multiplicity is exactly the number of components; this is what happened with the 5-nearest-neighbour graph of the moons.)
Fixed \(k\). The merges depend only on the order of the distances, which scaling does not change. Shrinking within-cluster and stretching between-cluster distances keeps every within-cluster merge before every between-cluster merge, so the same \(k\) clusters result. But only partitions into exactly \(k\) clusters are produced: richness fails.
Threshold \(r\). The clusters are the connected components of the graph joining points at distance at most \(r\). Any partition arises by making distances within the intended clusters small and those between them larger than \(r\) (richness), and shrinking within / stretching between keeps the components (consistency). Scaling by a large \(\alpha\) pushes all distances above \(r\), giving singletons: scale invariance fails.
Replace Xc by the first 24 columns of cnt, divided by their row sums and multiplied by 24, and use adjusted_rand_score against lab. The morning-peak and evening-peak groups mostly survive, because they are defined by weekday timing. The stations that move are those whose distinguishing feature was weekend use: without the weekend half, the evening-and-weekend cluster loses its defining feature and splits between the other two, or reforms around a different feature such as late-evening weekday trips. The choice of features defines what "similar" means, before any clustering method is chosen.
Each project uses this lecture's methods and public data, and has a clear result.
Data. Citi Bike trip data, January 2014: Citi Bike / Lyft system data (citibikenyc.com/system-data, used under the Citi Bike data licence agreement), copy of the official monthly file from github.com/Tmills1/Citibike-Tripdata because the official archive was not reachable from the build environment. Astronaut photograph: NASA (public domain), via scikit-image's skimage.data.astronaut. Country indicators: Our World in Data, github.com/owid/covid-19-data (CC BY 4.0), compiled from the World Bank, the United Nations and the Global Burden of Disease study, used in place of the World Bank's own data service, which was not reachable. Two moons: scikit-learn's make_moons. Karate club: W. W. Zachary (1977), via NetworkX.
numbers in the text not printed by a code box are computed in verify_L15.py, figures and widget data in figs_L15.py; code-box outputs are pasted from actual runs (numpy, SciPy, scikit-learn and NetworkX on one CPU core)