AI · 08 Artificial Intelligence

Learning Without Labels: Clustering, PCA & Nearest Neighbors

Learning Without Labels: Clustering, PCA & Nearest Neighbors

Every model so far learned from labels. What if nobody gave it the answers? We hide the labels on 1,797 real handwritten digits and let the machine find structure: k-means step by step, choosing k, PCA squeezing 64 numbers into 2, k-nearest neighbors, scaling, the curse of dimensionality, and anomaly detection. Plus the trap: k-means finds "groups" even in pure noise. Every number on screen is real output from code you can run.

Chapters

Cheat sheet

Code

Try it yourself (pip install numpy scikit-learn)
import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import load_digits
from sklearn.decomposition import PCA
from sklearn.metrics import adjusted_rand_score, silhouette_score

X, y = load_digits(return_X_y=True) # y = the true digits, never shown to k-means
noise = np.random.default_rng(0).uniform(0, 16, size=X.shape) # same shape, pure static
print(f"images: {len(X)}, numbers per image: {X.shape[1]}")

for name, data in {"digits": X, "noise": noise}.items():
kmeans = KMeans(n_clusters=10, random_state=0).fit(data)
rerun = KMeans(n_clusters=10, random_state=1).fit(data) # same data, a different start
print(f"{name}: 10 clusters, sizes {sorted(np.bincount(kmeans.labels_).tolist())}")
print(f" silhouette {silhouette_score(data, kmeans.labels_):.3f}, "
f"agreement with a rerun {adjusted_rand_score(kmeans.labels_, rerun.labels_):.2f}")
if name == "digits":
print(f" match with the hidden labels: {adjusted_rand_score(y, kmeans.labels_):.2f}")

pca = PCA().fit(X) # no labels here either
print("variance kept by each component:", np.round(pca.explained_variance_ratio_[:5], 3).tolist(), "...")
print(f"the first 2 components keep {pca.explained_variance_ratio_[:2].sum():.1%}")
print("components needed to keep 90%:", PCA(n_components=0.9).fit(X).n_components_)

What we got: on the digits, silhouette 0.186, a rerun agrees 0.72, and the clusters match the hidden labels at 0.62. On static of the same shape, k-means still returns 10 tidy groups, but silhouette 0.012 and rerun agreement 0.03. PCA: the first 2 components keep 28.5%; 21 keep 90%.

Sources

Transcript

Every model so far learned from labels: someone gave it the right answers. Today, nobody does. Here are one thousand seven hundred ninety-seven handwritten digits, with the labels hidden. Ask an algorithm called k-means to sort them into ten groups, and it does. Average each group, and digits appear: a zero, a two, a six, a seven.

It found most of them on its own. Now give it pure static instead. It still returns ten tidy groups. Which raises a classic interview question: how do you choose k, and how would you know the clusters are real? Let's find out.

This is Just Known. From unknown, to known. Episode eight: learning without labels. Clustering, PCA, and nearest neighbors. In episode two, we met unsupervised learning: data with no labels, where the model finds structure on its own.

It has three classic jobs: finding groups, squeezing data into fewer numbers, and spotting the odd ones out. Our data comes bundled with scikit-learn: handwritten digits, scanned from forms. Each is a tiny image, eight by eight pixels, and each pixel holds an amount of ink, from zero to sixteen. So every image is sixty-four numbers, one point in a sixty-four-dimensional space, and similar images become nearby points. Everything today runs on that idea: distance.

Here's how k-means works. To draw it, I've taken four of the digits, zero, three, four and seven, and squeezed each image down to two numbers. Pick k, the number of groups: four. Drop four centers on random points. Then repeat two steps: assign every point to its nearest center, and move each center to the average of its points.

Each round, the total squared distance to the centers, called the inertia, goes down. After six moves, nothing changes. Without labels, its four groups still match the true digits closely. The idea goes back to the nineteen fifties, with Hugo Steinhaus and Stuart Lloyd. James MacQueen named it k-means in nineteen sixty-seven.

Now use all sixty-four numbers, and ten groups. Each center is an image too, the average of its group. And look: a zero, a two, a four, a six, a seven. Let's peek at the hidden labels, only to check. One group is a hundred seventy-seven zeros out of a hundred eighty.

But threes and nines landed together, ones and eights share a group, and the fives split in two. A score called the adjusted Rand index puts the match at point six two, where one is perfect and zero is chance. k-means only finds a local best, so where it starts matters. scikit-learn uses k-means plus plus, from two thousand seven, which spreads the first centers apart. We picked ten because we know the digits.

Usually you don't, so how do you choose k? The classic tool is the elbow plot: inertia for each k. More groups always lower it, so look for the bend where extra groups stop paying off. Here it bends gently, with no clear elbow, as is common on real data. The second tool is the silhouette score.

For each point, compare a, its average distance to its own group, with b, to the nearest other group. Near one: well placed. Near zero: on a border. For the digits, it peaks at nine groups, with ten right behind. Useful hints, not proof.

So what can go wrong? Here are four hundred random points in a square: pure noise. Ask k-means for four groups, and you get four neat ones. k-means always returns k groups; it never says there aren't any. Like episode five's noise lab, it finds a pattern in nothing.

Even the score can fool you: this noise gets a silhouette of point four two, higher than our digits. A score needs a baseline. So compare like with like: static shaped like the digits. Ten tidy groups again, but the silhouette drops to point zero one, the inertia barely falls, and a rerun from a new start barely agrees: point zero three, against point seven two for the digits. Shuffled pixels fail too.

Real groups survive these checks. Noise doesn't. The second job: fewer numbers. Principal component analysis, or PCA, finds the direction where the data varies most, then the next one at a right angle, and so on. Keep the first few, drop the rest.

Here are all one thousand seven hundred ninety-seven digits, squeezed from sixty-four numbers to two. Now reveal the hidden labels: zeros at the bottom, fours on the right, threes on the left, sevens at the top. PCA never saw a label, yet the digits pull apart, with just twenty-eight point five percent of the variation. Karl Pearson described the idea in nineteen oh one, and Harold Hotelling named principal components in nineteen thirty-three. How many should you keep?

The first component explains fifteen percent of the variation, the second fourteen, then less and less. Twenty-one components keep ninety percent: a third of the numbers. Watch one test image, a two, rebuilt from its components. With two, a blur. With ten, roughly a two.

With twenty-one, clearly a two. One caution: PCA keeps what varies most, not what predicts best. In this made-up example, a loud, useless column holds ninety-five percent of the variance. Keep only PCA's first component, and a classifier drops from ninety-nine and a half percent to fifty-five, about a coin flip. The third tool brings the labels back: k-nearest neighbors.

To label a new image, find the k closest training images, and let them vote. We hold back four hundred fifty test images. Here's one, a two. Its five nearest neighbors, out of one thousand three hundred forty-seven, are all twos, about twenty to twenty-five away, while a typical training image is fifty-two away. Five votes for two.

Over all the test images, it scores ninety-eight percent. There's no real training step: it just stores the examples. The idea goes back to a nineteen fifty-one report by Fix and Hodges. Two things matter. First, k: one neighbor can be fooled by a single odd example, and too many blur the classes.

Here, one to fifteen neighbors all score about ninety-eight percent; two hundred and one drop to about eighty-nine. Second, scale. In a classic table of Italian wines, proline runs into the hundreds and thousands, while hue stays around one, so raw distances are nearly all proline, and accuracy is sixty-seven percent. Standardize the columns, and it jumps to ninety-three. k-means has the same problem.

And every prediction measures the distance to every stored example. At scale, that takes approximate search, the heart of vector databases, in episode twenty. Why not just add more features? Because of the curse of dimensionality, Richard Bellman's phrase. Scatter a thousand random points in a square, and pick one more.

Its nearest neighbor is close, and its farthest is far: on average, the ratio is under two percent. In ten dimensions, it's about a quarter. In a hundred, seventy percent. In a thousand, about ninety: nearest and farthest are almost the same, so nearest stops meaning much. A nineteen ninety-nine paper showed this under broad conditions.

Our digits escape it: their ratio is point two four, while static of the same shape sits at point six two. Real data has structure. The last job: spotting the odd ones out. Reuse the k-means model: measure each image's distance to its nearest center. A typical image sits about twenty-five away.

Flag the top one percent, beyond thirty-eight, and you get eighteen images. Here are the five most unusual. Three are sevens, two of them with a bar through the middle. None is wrong; it's just unusual handwriting. The three most typical are all zeros.

That's the recipe of anomaly detection, from fraud checks to failing servers: learn what normal looks like, and flag what's far from it. Unusual isn't the same as bad, and you choose the threshold. One more trap. k-means only measures distance to a center, so it expects round groups of similar size. Take two interlocking half-moons, made-up data.

k-means slices straight across them: a match of just point two four. DBSCAN, a density-based method from nineteen ninety-six, grows clusters through crowded regions instead. It needs no k, and it finds both moons perfectly. Pictures can mislead too. Popular maps like t-SNE and UMAP draw beautiful clusters, but their sizes, and the gaps between them, don't always mean much.

You can run this yourself, in about twenty lines of scikit-learn. The code is in the description. It makes static shaped like the digits, and runs k-means with ten clusters on both, twice. The digits: groups of different sizes, a silhouette of point one eight six, and a rerun agrees at point seven two. The noise: near-equal groups, point zero one two, and just point zero three.

Only then does it check the hidden labels: point six two. Then PCA: twenty-eight point five percent of the variance in two components, and twenty-one components for ninety percent. Interview corner. How do you choose k in k-means? And how would you know the clusters are real?

Pause here, and try answering in thirty seconds.

Here's a strong answer. k-means assigns each point to its nearest center, moves each center to the mean of its points, and repeats, lowering the inertia, the within-cluster sum of squares. It finds a local optimum, so use k-means plus plus and several starts. To choose k, look for an elbow in the inertia, check the silhouette score, and ask what the groups are for. To know the clusters are real, beat a baseline of the same shape, like noise or shuffled columns, and check that they're stable across seeds and subsamples.

Scale your features. And k-means expects round groups of similar size, so for other shapes, try DBSCAN, Gaussian mixtures, or hierarchical clustering. To stand out: k-means always returns k clusters, even on noise. Mention the gap statistic, which compares against noise and can even answer: just one group. Let's recap.

Unsupervised learning finds structure without labels. k-means groups points around centers. PCA keeps the directions with the most variation. And nearest neighbors label new examples by asking the closest ones. All of them run on distance, so scale your features and beware of high dimensions.

And clusters always appear, so check them against noise. That wraps up classic machine learning. Next, we climb into deep learning, starting with its building block: a single artificial neuron. That's episode nine: neurons and neural networks. This is Just Known.

From unknown, to known.

Note: the handwritten digits and wines are real data; the static, shuffled pixels, random points and half-moons are made-up data. Pictures marked "illustration" are not data.
Narration voice generated with Google Gemini text-to-speech.