Machine Learning · Lecture 15

Lecture 15
Clustering

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)

Cartoon: how many groups?Two stick figures look at the same scatter of dots. One has drawn two big circles around them and says there are clearly two groups; the other has drawn five small circles and says there are clearly five. Two groups. Obviously.Just look at it. Five groups. Obviously.Just look closer.
Both are right: a clustering answers a question about scale and similarity that the data alone do not pose
In this lecture
  1. k-means
  2. Choosing k
  3. Hierarchical clustering and dendrograms
  4. Density-based clustering: DBSCAN and HDBSCAN
  5. Spectral clustering
  6. Is clustering well defined?
  7. Summary, exercises, projects, reading

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.

1 — k-means

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.

definition 15.1 — the k-means objective

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.

idea — shops and customers

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.

theorem 15.1 — Lloyd's algorithm decreases the objective and terminates

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.

theorem 15.2 — k-means is NP-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.

theorem 15.3 — k-means++ seeding (Arthur and Vassilvitskii, 2007)

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.

data — Citi Bike trips, January 2014

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.

code — station profiles, Lloyd's algorithm and k-means++
# 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
weekdays06121823weekends061218230123hour of departurerate ÷ flat
The three cluster centres: hourly departure rates relative to a flat profile, weekdays (left) and weekends (right). Peaks: morning rush; evening rush with little weekend use; evening with the most weekend use.

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.

morning peakevening peak, few weekend tripsevening and weekendManhattanBrooklyn
The 290 stations by latitude and longitude, coloured by cluster. Evening-peak stations with few weekend trips (rose) concentrate in Midtown and at the southern tip of Manhattan, the business districts. Morning-peak stations (sky) are commonest in eastern lower Manhattan and Brooklyn, where people live. The third cluster (moss) fills the mixed residential, shopping and nightlife districts between.

Lloyd's algorithm, one step at a time

Drag the crosses to place the starting centres, then press step (alternately assign and average); the objective can only fall. Try two centres in one blob, and the uneven and two-moons data, where even the best k-means solution cuts across the visible groups.

spot check 15.1

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\)?

Assign, average, then sum the squared distances.
Clusters {0, 2} and {10}; centres 1 and 10; \(J=1^2+1^2+0^2=2\). Nothing changes after this, and it is also the global minimum.
spot check 15.2

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?

The probability is proportional to \(D(x)^2\).
\(3^2/(1^2+2^2+3^2)=9/14\approx0.64\), against \(1/3\) for uniform seeding.

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).

code — colour quantisation with k-means
# 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
originalk = 2k = 4k = 16
NASA's portrait of astronaut Eileen Collins (from scikit-image's sample images; NASA images are in the public domain), resized to 256×256 pixels, and its k-means quantisations to 2, 4 and 16 colours.

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.

2 — Choosing k

\(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.

definition 15.2 — silhouette

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.

code — three ways to choose k for the station profiles
# 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.

spot check 15.3

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?

Definition 15.2: \(s=(b-a)/\max\{a,b\}\).
\((5-2)/5=0.6\): the point sits well inside its cluster. With the distances swapped, \(s=(2-5)/5=-0.6\) and the point would belong elsewhere.

3 — Hierarchical clustering and dendrograms

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.

definition 15.3 — linkage

The linkage defines the distance between clusters \(A\) and \(B\) from point distances \(d\):

$$\Delta(A,B)=\frac{|A||B|}{|A|+|B|}\lVert\bar x_A-\bar x_B\rVert^2.$$

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.

data — development indicators for 160 countries

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.

code — four linkages on the countries
# 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.

Cutting a dendrogram

Ward's dendrogram of the 160 countries. Slide the cut (dashed rose line); the readout gives, for the six largest clusters, size, two commonest continents and a few members.

spot check 15.4

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 .

Which linkage follows chains of neighbours, and what is its weakness?
Single linkage follows chains of neighbours, so it tracks curves, but one chain of noise points across the gap merges them. DBSCAN (next section) requires chains to pass through dense regions.
history — Lloyd's memo, Ward's tree, and a test of time

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.

4 — Density-based clustering: DBSCAN and HDBSCAN

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.

definition 15.4 — DBSCAN

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.

code — DBSCAN and HDBSCAN on two moons with background noise
# 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.

DBSCAN's two dials

The same 440 points: filled circles are core, hollow border, grey crosses noise; the dashed circle shows \(\varepsilon\). Find settings that separate the moons, and see how narrow the good range is.

spot check 15.5

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?

Check the core condition, then whether it is within \(\varepsilon\) of a core point.
Not core (3 < 5), but within \(\varepsilon\) of a core point: a border point. A border point near two clusters joins whichever reaches it first, the one order-dependent part of DBSCAN.

5 — Spectral clustering

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.

definition 15.5 — normalised cut

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.

theorem 15.4 — spectral clustering relaxes the normalised cut

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).

idea — the slowest-varying patterns on a graph

\(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.

data — Zachary's karate club

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.

code — spectral clustering of the moons and the karate club
# 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.

The spectral embedding

Left: the 400 moon points. Right: each point at its row of the first two eigenvectors of the normalised Laplacian, scaled to unit length (Ng, Jordan and Weiss), so on the unit circle. Colours: spectral clustering, or k-means if ticked. Tap a point to find it in the other picture. With 5 neighbours each moon collapses to one point; with more, the moons spread along arcs that meet.

Bayes — k-means is a Gaussian mixture with the variance turned down

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.

6 — Is clustering well defined?

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.

definition 15.6 — Kleinberg's axioms

A clustering function \(f\) may satisfy:

theorem 15.5 — Kleinberg's impossibility theorem

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

  • very small within the clusters of \(\Gamma'\);
  • moderate between clusters of \(\Gamma'\) that lie in the same cluster of \(\Gamma\);
  • very large between clusters of \(\Gamma\).

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.

code — how well do five methods agree on the stations?
# 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.

spot check 15.6

Which of Kleinberg's axioms does k-means with \(k=3\) fixed in advance violate?

Can k-means with \(k=3\) ever return 2 clusters, or 5?
With \(k\) fixed, only partitions into (at most) 3 clusters are possible, so richness fails. The objective scales by \(\alpha^2\) with the distances, so the optimal partition is scale invariant; Kleinberg also shows by example that k-means violates consistency.
big picture — where clustering runs in 2026

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.

7 — Summary, exercises, projects, reading

summary
exercises
  1. Run Lloyd's algorithm on the points 1, 2, 3, 8, 9 and 20 on a line with \(k=2\), starting from centres 1 and 2. Show that it converges to a local minimum that is not the global one, and find the global minimum.

    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.

  2. Show that Ward's merge cost \(\Delta(A,B)\) of Definition 15.3 equals the increase in the within-cluster sum of squares when \(A\) and \(B\) are merged.

    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.$$
  3. A graph consists of two triangles joined by a single edge (6 nodes, 7 unit-weight edges). Compute the normalised cut of the split into the two triangles, and of the split that cuts off one node of degree 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.

  4. Show that if a graph has two connected components, the generalised eigenproblem \(Lf=\lambda Df\) has eigenvalue 0 with two independent eigenvectors, the indicator vectors of the components.

    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.)

  5. Show that single linkage stopped when \(k\) clusters remain satisfies scale invariance and consistency but not richness, and that single linkage stopped at a fixed distance threshold \(r\) satisfies richness and consistency but not scale invariance.

    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.

  6. (Code.) Recompute the station profiles using only weekday hours (24 numbers), cluster them with k-means for \(k=3\), and compare with the 48-number clustering using the adjusted Rand index. Which stations change cluster, and why?

    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.

student projects

Each project uses this lecture's methods and public data, and has a clear result.

1. Station personalities before and after the pandemic

question
Did the pandemic and the shift to hybrid work change the "personalities" of Citi Bike stations (or subway stations), and which neighbourhoods changed most?
data
Citi Bike monthly trip files (citibikenyc.com/system-data) for 2019 and 2024, restricted to stations present in both years; alternatively, MTA subway hourly ridership by station complex (data.ny.gov) for 2019-equivalent turnstile data and 2024.
method
Hourly weekday and weekend profiles as in Section 1; k-means, Ward and spectral clustering for each year; stability across methods and bootstrap resamples (adjusted Rand index); transition matrices of stations between clusters from 2019 to 2024, mapped.
outcome
A measured answer to "how much did the morning commute disappear, and where", with a stability analysis showing which changes are robust to the method.

2. Do 311 complaints cluster the way the city files them?

question
When 311 complaint descriptions are clustered by meaning, do the clusters match the city's official complaint types, and where do they disagree?
data
NYC 311 Service Requests (NYC Open Data), the free-text descriptor and resolution fields, with the official complaint type held out for evaluation.
method
Sentence embeddings from an open pre-trained encoder; k-means, HDBSCAN and agglomerative clustering; agreement with official types (adjusted Rand index, normalised mutual information); inspection of clusters that split or merge official types.
outcome
A map of where the city's taxonomy and the language of complaints diverge, with candidate new categories, of practical interest to the city's 311 service.

3. Neighbourhoods from data

question
If New York's census tracts are clustered by demographic and housing indicators alone, how closely do the clusters follow the official Neighborhood Tabulation Areas, and which "neighbourhoods" are really several?
data
American Community Survey 5-year estimates by census tract (US Census Bureau); NYC Neighborhood Tabulation Areas (NYC Department of City Planning).
method
Standardised indicators; Ward clustering with and without a spatial-contiguity constraint; spectral clustering on a tract adjacency graph weighted by indicator similarity; agreement with the official areas.
outcome
Data-driven neighbourhood boundaries, with an analysis of how much they depend on the method (Section 6), useful to urban planners and social scientists.

Reading and sources

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)