Unsupervised Learning: Clustering and Dimensionality Reduction

SupervisedSupervised learning starts from labelled examples — every input comes with a known correct answer to learn from. Unsupervised learning starts from data with no labels at all, and asks a different kind of question: what structure is already in here? Two questions dominate the field. Clustering asks "which points belong together?" Dimensionality reduction asks "can this be described with far fewer numbers than it currently has, without losing what matters?"

K-Means Clustering

K-means,K-means, one of the earliest and still most widely used clustering algorithms, assumes the answer to "which points belong together" is: whichever cluster centre they're closest to¹. The algorithm alternates between two steps until nothing changes:

1. Assign: put every point into the cluster of its nearest centre
2. Update:  move each centre to the mean position of the points now assigned to it
3. Repeat until no point changes cluster

Walk it through on five 1-dimensional points — {1, 2, 4, 8, 9} — with k = 2 and initial centres placed (arbitrarily) at 1 and 2. Assign: {1} goes to centre 1; {2, 4, 8, 9} all go to centre 2 (each is closer to 2 than to 1... except 4, 8, 9 are actually all still closer to 2 than to 1 only because 1 is the sole alternative). Update: centre 1 becomes mean({1}) = 1; centre 2 becomes mean({2, 4, 8, 9}) = 5.75. Assign again: {1, 2, 4} are now closer to 1's neighbourhood... concretely, distance to 1 vs distance to 5.75 — 4 is 3 away from 1 and 1.75 away from 5.75, so 4 switches to cluster 2's side only if 5.75 is closer, which it is (1.75 < 3), so 4 moves to centre 2's cluster; 1 and 2 stay with centre 1. Update again: centre 1 becomes mean({1, 2}) = 1.5; centre 2 becomes mean({4, 8, 9}) = 7. One more assignment pass changes nothing further — the algorithm has converged to two clusters, {1, 2} and {4, 8, 9}, which is the intuitively obvious split for this data.

Two things about k-means are worth knowing before using it. First, k has to be chosen in advance — the algorithm has no way to discover how many clusters actually exist, only to partition the data into however many you ask for. Second, the result depends on where the initial centres happen to land — a different starting position can converge to a different, sometimes worse, local optimum, which is why real implementations typically run k-means several times from different random starting points and keep the best result.

Hierarchical Clustering

HierarchicalHierarchical clustering sidesteps the "choose k in advance" problem by building a whole tree of nested clusters at once. The most common form, agglomerative clustering, starts with every point as its own cluster and repeatedly merges the two closest clusters until only one remains, recording each merge as it happens. The result is a dendrogram — a tree whose branch heights show how far apart two clusters were when they merged — and any particular number of clusters can be read off afterward by cutting the tree at the appropriate height, rather than having to be decided before the algorithm runs.

What "closest" means between two clusters (rather than two points) is a genuine design choice, not a detail: single linkage uses the distance between the closest pair of points in the two clusters, complete linkage uses the farthest pair, and average linkage uses the mean distance across all pairs — each produces a different dendrogram from the same data, and each has known failure modes (single linkage in particular is prone to "chaining," where a thin bridge of points strings two otherwise-distant blobs into one cluster).

Dimensionality Reduction and PCA

AA dataset with a hundred columns is hard to visualise, slow to compute over, and often has columns that are redundant with each other (two measurements that both, roughly, track the same underlying thing). Principal Component Analysis (PCA), originally formulated by Pearson in 1901 and put into the form used today by Hotelling in 1933², finds a small number of new axes — the principal components — that capture as much of the data's variance as possible, ranked in order: the first component is the single direction along which the data varies the most, the second is the direction of next-most variance that is also perpendicular to the first, and so on.

The mechanism, at a conceptual level: centre the data (subtract each column's mean), compute the covariance matrix (how much every pair of columns varies together), and find that matrix's eigenvectors and eigenvalues — the eigenvectors give the principal components' directions, and their corresponding eigenvalues give how much variance each one explains. Keeping only the first few components — the ones with the largest eigenvalues — throws away the directions the data barely varies in, on the reasoning that a direction with almost no variance carries almost no information worth keeping. (The linear-algebra machinery behind eigenvectors and eigenvalues is covered in full on Linear Algebra for Computing.)

A useful way to sanity-check how many components to keep is a scree plot — the eigenvalues plotted in descending order — looking for the "elbow" where the curve flattens out: components before the elbow are doing real work; components after it are mostly capturing noise.

Anomaly Detection

AnomalyAnomaly (or outlier) detection asks a related but distinct question: not "how should these points be grouped," but "which points don't look like they belong to any sensible group at all." A common, simple approach builds directly on the tools above — cluster the data, then flag any point that ends up unusually far from every cluster centre, or any point that forms a cluster of size one when the rest of the data forms dense, populated clusters. More generally, the recurring idea across anomaly-detection methods is the same: build a model of what "normal" looks like from the bulk of the data, then measure how far a new point sits from that model — a large distance, a low density around the point, or a low probability under the fitted model, are all versions of the same underlying question.

References