Unsupervised Learning

Learning without labels

In 2008, geneticists took hundreds of thousands of DNA markers from over a thousand Europeans, gave an algorithm no information about where anyone came from, and asked it for the two most important directions of variation. When they plotted the result, it drew a map of Europe.

The algorithm was principal component analysis, and the finding was that the first two components lined up with latitude and longitude. Italians landed near Italy, Swedes near Sweden, and 90% of people could be placed within about 700 km of their origin (Novembre et al., Nature). Nobody labelled anything. The structure was in the data, waiting.

That is the promise of unsupervised learning: finding structure in data that nobody has labelled. It is also how the biggest AI systems of today begin their training.

What is unsupervised learning?

In supervised learning every example comes with an answer: this email is spam, this house sold for £310k. Unsupervised learning gets only the inputs. Its job is to describe them: which examples resemble each other, what the few important directions of variation are, which points do not fit anywhere.

Why does it matter?

Labels are expensive. Someone has to read every email, examine every scan, listen to every call. Raw data, by contrast, piles up for free: server logs, sensor streams, photos, text. Unsupervised methods let you explore that data before you know what questions to ask, compress it, clean it, and find the odd cases worth a human’s attention.

Key takeaways

• Unsupervised learning finds structure (groups, directions, outliers) in unlabelled data.
• Most data is unlabelled because labels cost human time; raw data is cheap.
• There is no answer key, so results are hypotheses to validate, not facts.

k-means clustering

k-means is the workhorse of clustering. It is two simple steps repeated until nothing changes, and watching it run tells you almost everything about what it can and cannot do.

What is it?

You choose a number of clusters k. The algorithm places k centres and gives every point to its nearest centre. The goal is to make the total squared distance from points to their centres, called inertia, as small as possible.

Inertia: the sum over every point of its squared distance to the centre of its cluster.

How does it work?

Lloyd’s algorithm, written at Bell Labs in 1957 and published in 1982 (Lloyd), alternates two steps. Assign: each point joins its nearest centre. Update: each centre moves to the mean of its points. Neither step can increase inertia, so the process must settle, usually within a few iterations. The coloured background below shows the regions each centre currently owns (a Voronoi diagram): every boundary is the perpendicular bisector between two centres.

With random initialisation, two centres sometimes start in the same blob. k-means then converges with one blob split in half and two blobs sharing a centre: a local minimum it cannot escape, because each step only makes local improvements. The fix is k-means++: pick the first centre at random, then pick each next centre with probability proportional to its squared distance from the nearest centre already chosen. Far-away points are likely picks, so centres spread out. It comes with a proven guarantee of being within a factor of O(log k) of the optimum in expectation (Arthur & Vassilvitskii), and it is the default in scikit-learn. In practice you also run several restarts and keep the lowest inertia.

Choosing k

Inertia always falls as k grows: with one centre per point it is zero. So you cannot just minimise it. The elbow method plots inertia against k and looks for the point where adding clusters stops paying off. The silhouette score asks, for each point, how much closer it is to its own cluster than to the next nearest one, giving a value from −1 to 1; the average is highest when clusters are tight and well separated (Rousseeuw).

On four clean blobs, inertia drops steeply until k = 4 and then flattens, and the silhouette peaks at 4 too. On the uneven dataset the signals disagree and the elbow is soft. That is common with real data, and it is honest: sometimes the data does not contain a single natural number of groups.

Key takeaways

• k-means alternates assign-to-nearest-centre and move-centre-to-mean, reducing inertia every step.
• It finds local minima; k-means++ seeding and several restarts make bad solutions rare.
• Choose k with the elbow and silhouette as evidence, not as proof; scale features first.

Density-based clustering

k-means assumes every cluster is a round blob around a centre. Plenty of real structure is not: roads, rivers of galaxies, crescent-shaped groups of customers. Density-based clustering follows the data instead.

What is DBSCAN?

DBSCAN (density-based spatial clustering of applications with noise) defines a cluster as a region where points are packed densely, separated by sparser regions (Ester et al., KDD 1996). It needs no k. Instead it takes a radius ε and a count minPts.

How does it work?

• A core point has at least minPts points (itself included) within radius ε.
• Core points within ε of each other belong to the same cluster, and clusters grow by chaining through core points.
• A border point is not a core itself but lies within ε of one; it joins that cluster.
• Everything else is noise, and DBSCAN says so rather than forcing it into a group.

On the moons, k-means draws a straight boundary through both crescents, because a Voronoi boundary between two centres is always a straight line. DBSCAN traces each crescent. On the rings, k-means cuts the picture in half while DBSCAN finds the inner and outer ring. Now shrink ε: clusters fragment and noise grows. Grow it: clusters bleed into each other until everything is one cluster. That sensitivity is DBSCAN’s weakness, and it struggles when clusters have very different densities, since one ε cannot suit them all. HDBSCAN, a hierarchical extension, addresses that by considering many densities at once.

Key takeaways

• DBSCAN grows clusters through chains of dense core points and labels sparse points as noise.
• It finds arbitrary shapes and needs no k, but depends strongly on ε and minPts.
• k-means boundaries are always straight lines between centres, so it cannot follow curved clusters.

Hierarchical clustering

Sometimes the honest answer to “how many clusters?” is “it depends how closely you look”. Hierarchical clustering gives you every answer at once, as a tree.

What is it?

Agglomerative clustering starts with every point in its own cluster and repeatedly merges the two closest clusters until only one remains. The record of merges is a tree called a dendrogram. The height of each join is the distance at which those two groups merged. Cutting the tree horizontally at any height gives a flat clustering.

How is “closest” measured?

That choice, the linkage, shapes the result:

• Single linkage: distance between the two closest members. Follows chains and elongated shapes, but one stray point can bridge two groups.
• Complete linkage: distance between the two farthest members. Produces compact, similar-sized clusters.
• Average linkage: the mean of all pairwise distances. A compromise between the two.

Long vertical branches mean a group stayed separate for a wide range of distances: strong evidence it is real. A cut just below the longest gap in the tree usually gives the most defensible number of clusters. Notice where the isolated points Q and R join the tree under each linkage, and how the upper levels reorganise while the tight groups at the bottom barely change.

Hierarchical clustering is the standard tool in biology (gene expression heatmaps with trees along the edges are dendrograms) and anywhere nested groups are natural, such as taxonomies. Its cost is the catch: the simple algorithm compares all pairs, so it suits thousands of points, not millions.

Key takeaways

• Agglomerative clustering merges the closest pair of clusters repeatedly, recording a dendrogram.
• Cut the tree at any height to get a flat clustering; long branches suggest robust groups.
• Linkage (single, complete, average) decides what “closest” means and changes the result.

Principal component analysis

Real data often has dozens or thousands of features that move together. PCA finds the few directions that carry most of the variation, so you can keep those and drop the rest.

What is it?

Principal component analysis, first described by Karl Pearson in 1901 as finding “lines and planes of closest fit” (Pearson), rotates your coordinate system. The first new axis, PC1, points in the direction along which the data varies most. PC2 is the direction of most remaining variation at right angles to PC1, and so on.

How does it work?

Two views give the same answer. PC1 is the line that keeps the most variance when you project the points onto it. Equivalently, it is the line that loses the least: the smallest total squared distance from points to the line. Computationally, you centre the data, form the covariance matrix, and take its eigenvectors, ordered by eigenvalue. Each eigenvalue is the variance along its component.

As you rotate, the variance kept rises and falls, peaking exactly when your line lies on PC1. At that angle the whiskers are shortest. That is the whole idea: the best one-number summary of each point is its position along PC1.

PCA on real data

Fisher’s Iris data measures four things about 150 flowers: sepal and petal length and width (Fisher 1936). You cannot plot four dimensions, but you can plot the first two principal components. PCA never sees the species.

PC1 alone explains about 92% of the variance, and it is mostly petal length with some petal width and sepal length: a “flower size” axis. One species separates cleanly along it; the other two overlap. Everything here is linear, fast and reproducible, which is why PCA is usually the first thing to try, and why it is a standard step before clustering high-dimensional data.

Key takeaways

• PC1 is the direction of greatest variance, which is also the line of least squared reconstruction error.
• Components are eigenvectors of the covariance matrix; eigenvalues give the variance each explains.
• PCA is linear and fast; standardise features first, and remember low variance can still matter.

Nonlinear maps: t-SNE and UMAP

PCA can only rotate and flatten. When structure is curled up in many dimensions, nonlinear methods like t-SNE and UMAP can unfold it into a 2-D map. They produce beautiful pictures, which is exactly why they need careful reading.

What is t-SNE?

t-distributed stochastic neighbour embedding (van der Maaten & Hinton) tries to keep each point’s neighbours as neighbours. In the original space it turns distances into probabilities: “how likely is it that point i would pick j as its neighbour?” Then it moves points around a 2-D map, by gradient descent, until the same probabilities computed on the map (with a heavy-tailed t-distribution) match. The perplexity setting is roughly how many neighbours each point pays attention to.

On ‘Tight vs wide’, PCA shows the truth: one compact cluster and one sprawling one. t-SNE draws them at roughly the same size, because it adapts to local density. On ‘Near and far’, PCA shows two clusters close together and one far off; t-SNE’s spacing between clusters does not reliably reflect that. Rerun from a new random start and the layout changes. These are exactly the pitfalls catalogued in the excellent Distill article (Wattenberg, Viégas & Johnson): cluster sizes and between-cluster distances in t-SNE plots may mean nothing.

And UMAP?

UMAP builds a graph of each point’s nearest neighbours and lays it out in 2-D so the graph is preserved (McInnes et al.). It is much faster than t-SNE on large datasets and tends to keep a little more of the global arrangement, which has made it the default in fields like single-cell biology. It shares the same basic caveat, though. Chari and Pachter showed that squeezing thousands of dimensions into two inevitably distorts the data, and warned against reading biological conclusions directly off these maps (Chari & Pachter).

Key takeaways

• t-SNE and UMAP keep neighbours together, revealing local structure PCA cannot.
• Cluster sizes and distances between clusters on these maps are not trustworthy.
• Use them to generate hypotheses, then confirm in the original feature space.

Anomaly detection

Fraud, failing turbines and network intrusions have something in common: they are rare, and they look different. Anomaly detection finds them without needing labelled examples of every way things can go wrong.

What is it?

An anomaly detector assigns every point a score for how unusual it is, relative to the bulk of the data. Many approaches exist: distance to the k-th nearest neighbour, DBSCAN’s noise label, low density under a fitted model, or large PCA reconstruction error.

How does an isolation forest work?

Isolation forests turn the problem around (Liu, Ting & Zhou). Instead of modelling what normal looks like, they measure how easy a point is to isolate. Build a random tree: pick a random feature and a random split value, and keep splitting until each point is alone. A point in a dense crowd needs many splits to isolate. An outlier gets cut off after a few. Average the path length over many random trees, normalise it, and you have a score near 1 for anomalies and well below 0.5 for normal points.

Points in the two clusters sit in dark regions, while the scattered points glow yellow and get circled first. Add a point in empty space and it is flagged immediately. Add several close together and they start to protect each other: a small cluster of anomalies is harder to isolate than a single one. The method is fast, needs no distance computations, and scales to millions of rows, which is why it is a common first line of defence in fraud and monitoring systems.

Key takeaways

• Anomaly detectors score how unusual each point is, without labelled examples of anomalies.
• Isolation forests use random splits: anomalies are isolated in fewer splits than normal points.
• Anomaly is a statistical property; human review and later labels decide what is actually a problem.

Self-supervised learning

The most important unsupervised idea of the last decade is a trick: hide part of the data and train a model to predict it. The data supplies its own labels, so you can train on almost unlimited amounts of it.

What is it?

Self-supervised learning creates a supervised task, called a pretext task, from unlabelled data. The model is trained with ordinary supervised machinery (a loss, gradient descent) but no human wrote the answers. What it learns along the way, a rich internal representation of the data, turns out to be useful for many other tasks.

How does it work in practice?

Language. BERT hid 15% of the words in its input and learned to predict them (Devlin et al.). GPT-style models predict the next token, which is the same idea applied left to right. Every sentence on the web is a free training example.

Images. Masked autoencoders hide 75% of an image’s patches and learn to reconstruct them (He et al.). Contrastive methods such as SimCLR make two random crops and colour distortions of the same photo and train the network to give them similar representations, while pushing representations of different photos apart (Chen et al.).

Images and text together. CLIP applied the contrastive idea to 400 million image-caption pairs from the internet: match each image to its own caption among many (Radford et al.). The result can classify images into categories it was never explicitly trained on, just by comparing them with text descriptions.

Why does it matter?

Self-supervised pre-training is how foundation models are built. A large model first learns general representations from vast unlabelled data; a much smaller amount of labelled data or human feedback then adapts it to specific tasks. The clustering and embedding ideas from this lesson come back too: the representations these models learn are vectors in which similar things lie close together, ready to be clustered, searched or projected into a map.

Key takeaways

• Self-supervised learning manufactures labels from raw data by hiding part of it and predicting it.
• Masked prediction and contrastive matching are the two dominant families of pretext task.
• It is the pre-training step behind LLMs, CLIP and most modern foundation models.

Check your understanding

Seven situations where you have data but no labels. Choose what you would actually do.

An online shop runs k-means with k = 5 on customers described by “annual spend in pounds” (0 to 20,000) and “visits per month” (0 to 30). Every cluster turns out to be a band of spend levels. What went wrong?

References

The original papers behind every algorithm in this lesson, plus two essential warnings about reading 2-D maps.

References

1. [1]

   Genes mirror geography within Europe(opens in a new tab)

   Novembre, Johnson, Bryc et al., 2008

   Nature. The first two principal components of European genotypes reproduce a map of Europe.

2. [2]

   Least squares quantization in PCM(opens in a new tab)

   Lloyd, 1982

   IEEE Transactions on Information Theory. The assign-and-update algorithm now called k-means (written at Bell Labs in 1957).

3. [3]

   k-means++: the advantages of careful seeding(opens in a new tab)

   Arthur & Vassilvitskii, 2007

   SODA. Seeding centres with probability proportional to squared distance gives an O(log k) approximation guarantee.

4. [4]

   Silhouettes: a graphical aid to the interpretation and validation of cluster analysis(opens in a new tab)

   Rousseeuw, 1987

   Journal of Computational and Applied Mathematics. Introduces the silhouette coefficient.

5. [5]

   A density-based algorithm for discovering clusters in large spatial databases with noise(opens in a new tab)

   Ester, Kriegel, Sander & Xu, 1996

   KDD. The DBSCAN paper: core, border and noise points defined by ε and minPts.

6. [6]

   On lines and planes of closest fit to systems of points in space(opens in a new tab)

   Pearson, 1901

   Philosophical Magazine. The origin of principal component analysis.

7. [7]

   The use of multiple measurements in taxonomic problems(opens in a new tab)

   Fisher, 1936

   Annals of Eugenics. Source of the Iris measurements (collected by Edgar Anderson) used in this lesson.

8. [8]

   Visualizing data using t-SNE(opens in a new tab)

   van der Maaten & Hinton, 2008

   JMLR. The t-SNE algorithm implemented in the demo.

9. [9]

   How to use t-SNE effectively(opens in a new tab)

   Wattenberg, Viégas & Johnson, 2016

   Distill. Interactive guide to what t-SNE plots do and do not show; the tight-vs-wide and near-and-far datasets follow its examples.

10. [10]

    UMAP: Uniform manifold approximation and projection for dimension reduction(opens in a new tab)

    McInnes, Healy & Melville, 2018

    arXiv. A faster neighbour-graph embedding that has become the default in many fields.

11. [11]

    The specious art of single-cell genomics(opens in a new tab)

    Chari & Pachter, 2023

    PLOS Computational Biology. Shows that reducing thousands of dimensions to two inevitably distorts the data.

12. [12]

    Isolation forest(opens in a new tab)

    Liu, Ting & Zhou, 2008

    ICDM. Anomalies are few and different, so random splits isolate them quickly.

13. [13]

    BERT: pre-training of deep bidirectional transformers for language understanding(opens in a new tab)

    Devlin, Chang, Lee & Toutanova, 2019

    NAACL. Masked-token prediction as a self-supervised pre-training task.

14. [14]

    Masked autoencoders are scalable vision learners(opens in a new tab)

    He, Chen, Xie, Li, Dollár & Girshick, 2022

    CVPR. Hide 75% of image patches and train a network to reconstruct them.

15. [15]

    A simple framework for contrastive learning of visual representations(opens in a new tab)

    Chen, Kornblith, Norouzi & Hinton, 2020

    ICML. SimCLR: learn image features by pulling two augmented views of the same image together.

16. [16]

    Learning transferable visual models from natural language supervision(opens in a new tab)

    Radford, Kim, Hallacy et al., 2021

    ICML. CLIP: contrastive training on 400 million image-text pairs gathered from the internet.