Unsupervised Learning from Scratch — Clustering and Dimensionality Reduction

How to pull structure out of data that carries no labels at all, assuming nothing. What k-means, hierarchical clustering and DBSCAN are each good for, what PCA is actually maximizing, and the three ways people misread a t-SNE or UMAP picture — metaphor, then formula, then a figure you can move, then code.

UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction

What can you do with data that has no answer key

Picture a hundred moving boxes stacked in a new apartment with the labels peeled off. Nobody can tell you what is inside. You still open them and put similar things together — this pile is kitchen, this pile is books. No answer key was handed to you; you worked from how the contents resemble each other. That is clustering.

There is a second move. Describe each box with just two numbers — weight and size — and lay them out on the floor. The detail is gone, but the spread of the whole collection is visible at a glance. Crushing many attributes down to a few axes so a human can look at them is dimensionality reduction.

The supervised learning covered in what is machine learning was a problem set with the answers in the back. Unsupervised learning has no answers, and that difference is heavier than it sounds: there is no such thing as accuracy here. Almost every pitfall in this article descends from that one fact.

"Similar" is whatever your distance function says it is

To a computer, a data point is a list of numbers — a vector. How alike two of them are is measured by distance. The usual choices are straight-line distance (Euclidean, L2) and cosine similarity, which ignores length and compares direction only.

The choice changes the answer. In embedding vectors, the length of a vector often encodes something like "this user wrote a lot." Use straight-line distance and the prolific posters separate from the quiet ones, while the actual topic similarity you were after stays invisible. That is cosine's job.

A more elementary trap is mismatched units. Put annual income (hundreds of thousands) and age (tens) in the same table and measure straight-line distance, and income decides everything while age is effectively discarded. For any distance-based method, standardizing each column to mean 0 and variance 1 is a de facto prerequisite. Skip it and you will end up reporting "we found five customer segments" when what you found was a split on income alone.

k-means: drop centroids, assign, move, repeat

The most widely used clustering method is k-means, and the whole procedure fits in four lines.

1. Pick a number of clusters $k$ and scatter $k$ points (centroids) somewhere
2. Assign every data point to its nearest centroid
3. Move each centroid to the average position of the points assigned to it
4. Repeat 2 and 3 until the centroids stop moving

What it is aiming at can be written as a single expression.

Here $x_i$ is the $i$-th data point, $c(i)$ is the index of the cluster it belongs to, $\mu_{c(i)}$ is that cluster's centroid, and $\|\cdot\|^2$ is squared distance. So the formula says only this: for every point, how far it sits from the centre of its own group, added up over all points. k-means is looking for the partition that makes this total as small as it can. Step 2 (reassign to a nearer centroid) and step 3 (move the centroid to the mean) can each only decrease that total or leave it alone, which is why the loop always comes to a stop.

But "always stops" and "arrives at the best answer" are different claims. Where it stops depends on where the initial centroids landed, and with bad luck it freezes into an awkward partition. Two mitigations exist: k-means++, which picks starting centroids spread far apart, and n_init, which reruns the whole thing from different starts and keeps the run with the smallest total. If your k-means result changes on every execution, an unset random_state and this initialization are why.

There are three weaknesses. It quietly assumes round blobs of roughly equal size (two interlocking crescents defeat it), it uses means so it is dragged around by outliers, and a human has to choose $k$ up front.

Hierarchical clustering: build the tree, cut it later

When you do not want to commit to $k$ in advance, the alternative is hierarchical clustering. Every point starts as its own cluster; the two nearest clusters are merged; repeat until everything is one lump. Drawing the merge history as a tree gives you a dendrogram, and slicing it horizontally at any height fixes the number of clusters. Splitting first and deciding the count afterwards is the appeal.

What matters here is the linkage, meaning the definition of distance between two clusters. Single linkage uses the closest pair, which lets it follow long thin shapes but invites the chaining effect, where points string together like beads until everything is one chain. Complete linkage looks at the farthest pair, producing compact blobs but severing elongated structures. Ward linkage merges whichever pair increases $J$ from Equation (1) the least, and is a common default.

The weakness is cost. It holds distances between all pairs, so memory grows with the square of the number of points $n$, and past a few tens of thousands it stops being practical without approximation.