Unsupervised Learning: Structure Without Labels

Every method up to this point has had a response to predict, and that response has been doing more work than it looks. It defines what the model is estimating, it makes a held-out error meaningful, and it settles every tuning decision by cross-validation. Remove it and all three go at once.

Unsupervised learning is what remains: only $X$, and the question of what structure it contains. This article covers the three standard answers and is honest throughout about the thing that makes them harder to use than anything in the supervised path - there is nothing to check them against.

A. Principal components: the direction of maximum variance

The first principal component is the normalised linear combination

$$Z_1 = \phi_{11}X_1 + \dots + \phi_{p1}X_p, \qquad \sum_{j=1}^{p}\phi_{j1}^2 = 1,$$

with the largest variance. The constraint carries real weight: without it you could double every $\phi_{j1}$, quadruple the variance, and repeat without limit, so no maximum would exist. Fixing the length to one makes the question one of direction.

There is a second, equivalent description worth holding onto, because it is the one that makes PCA feel geometric rather than algebraic: the same direction is the line closest to all $n$ observations, measured by squared perpendicular distance. The total variance is fixed, so whatever the projections fail to capture is left over as distance to the line - maximising one and minimising the other are one problem.

A worked example

Six observations on two variables:

$$X = \begin{bmatrix} 2&0\\ 3&1\\ 4&3\\ 5&4\\ 6&7\\ 4&2 \end{bmatrix}, \qquad S = \begin{bmatrix} 2.0000 & 3.4000 \\ 3.4000 & 6.1667 \end{bmatrix} .$$

The eigenvalues of $S$ are $\lambda_1 = 8.0708$ and $\lambda_2 = 0.0958$, and the first loading vector is $\phi_1 = (0.4886,\ 0.8725)$. Projecting the centred data onto $\phi_1$ gives scores whose variance is $8.0708$ - the eigenvalue is the variance its component captures, which is why the proportion of variance explained can be read straight off:

$$\text{PVE}_1 = \frac{8.0708}{8.1667} = 0.9883 .$$

One direction carries 98.83% of the variation. A scree plot orders these and the usual advice is to look for an elbow - which is an eyeball judgement, not a test. There is no widely accepted objective rule for how many components to keep, and this is the first place the missing response is felt.

Loadings are not scores. A loading says how much a variable contributes to a component and belongs to the dataset as a whole; a score says where an observation sits along it. Confusing them is the most common way to misread a PCA output.

PCA is also not scale invariant. Variance carries the square of the units, so recording a length in millimetres rather than metres multiplies its variance by $10^6$ and hands that variable the first component for no reason but the choice of ruler. Standardise each variable to standard deviation one first - unless the variables already share units and their differing variances are genuinely meaningful, in which case scaling discards real information.

B. K-means, and the local optimum it settles into

K-means partitions the observations into $K$ exhaustive, non-overlapping clusters, minimising the total within-cluster variation

$$W(C_k) = \frac{1}{|C_k|}\sum_{i,\,i' \in C_k}\ \sum_{j=1}^{p}\big(x_{ij} - x_{i'j}\big)^2 .$$

Dividing by $|C_k|$ matters: a cluster of $m$ points has $m^2$ ordered pairs, so an undivided sum would penalise large clusters for their size rather than their spread.

There are $K^n$ ways to assign $n$ observations to $K$ labelled clusters, and about $K^n/K!$ distinct partitions once the labels are ignored, so the exact problem is not solved but approximated. The algorithm assigns at random, then alternates: compute each cluster's centroid, and reassign each observation to the nearest one. It converges because neither step can increase the objective - the centroid minimises squared deviations, and moving a point to a nearer centroid cannot make things worse - and there are finitely many partitions.

It converges. That is not the same as being right.

Take seven points and $K = 3$:

$$\{\,1,\ 2,\ 3,\ 10,\ 11,\ 20,\ 21\,\}$$

Exhaustive search over all $3^7 = 2187$ assignments gives the global optimum $\{1,2,3\}, \{10,11\}, \{20,21\}$ with $\sum_k W(C_k) = 6.0$.

Now start from $\{1,2,3,10,11\}, \{20\}, \{21\}$. The centroids are $5.4$, $20$ and $21$, and every point is already assigned to its nearest centroid - so the first pass changes nothing and the algorithm halts immediately, reporting

$$\textstyle\sum_k W(C_k) = 178.4 ,$$

nearly thirty times worse. Nothing is broken: convergence to a local optimum is all the method promises, and the failure is silent.

So K-means is run many times from different random starts and the best result kept. That is part of the method, not a refinement for when you have time. And $K$ itself cannot be chosen by the objective, which falls monotonically as $K$ rises and reaches zero when every observation is its own cluster.

C. Hierarchical clustering, and the linkage that decides the answer

Agglomerative clustering removes the need to commit to $K$: start with every observation alone, repeatedly fuse the two least dissimilar clusters, and record the height at which each fusion happened. Cutting the resulting dendrogram horizontally gives a clustering, so one tree contains an answer for every $K$.

Two cautions. First, the clusterings are nested by construction - if the true grouping is not, no cut will recover it. Second, and the usual misreading: only fusion height measures similarity. Horizontal position means nothing, and two adjacent leaves may fuse only at the very top.

Fusing needs a dissimilarity between groups, and the choice is the linkage: complete takes the largest distance between the groups, single the smallest, average the mean, centroid the distance between centroids.

The same points, two different answers

Ten points: a compact group of three, a compact group of three, and four evenly spaced points bridging them.

Single linkage needs only one close pair, so each bridge point attaches to the growing blob in turn and the chain drags an entire group along - a trailing cluster. Complete and average linkage look at the largest and mean distances, refuse to fuse groups that are far apart overall, and split the data down the middle. This is the general pattern, which is why complete and average linkage are generally preferred; centroid linkage has a defect of its own, an inversion, where two clusters fuse below the height of one of them.

Those are the same ten points below, clustered four ways. Switch the linkage and watch the colours move: single linkage drags the whole bridge into one cluster of seven, complete and average refuse and split down the middle. Nothing in the data prefers one answer, which is the uncomfortable part. The second dataset is three points and exists for honesty - centroid linkage produces no inversion on the ten, so pointing at them and claiming one would be claiming something they do not show. On three points it does, and the fusion heights say so.

D. What is actually missing

Collect the decisions this article has required: whether to standardise; how many components to keep; how many clusters; which dissimilarity measure; which linkage; where to cut. Every one changes the answer, and not one of them can be settled from inside the data.

In the supervised path each would have been a straightforward cross-validation against a held-out response. Unsupervised learning has no response to hold out, which is what James et al. mean by calling these small decisions with big consequences. The consequence for practice is a discipline rather than a technique: try several sensible sets of choices, and report the structure that appears under most of them - rather than presenting a single run as the answer.

The training path Unsupervised Learning works through the same three methods with the derivations in full, and the encyclopedia entries Principal Component Analysis and K-Means Clustering cover them as references.