Clustering Visualizer

About

Clustering is the problem of finding groups in data that nobody labelled. There is no answer key: the algorithm only sees coordinates, and has to decide which points "belong together" from distance alone. That makes the choice of algorithm a choice about what a cluster is.

This lab runs three classic answers to that question on the same points, for real, in your browser:

• K-means says a cluster is a set of points closer to one centre than to any other. It is fast and simple but assumes round, similarly sized groups.
• DBSCAN says a cluster is a dense region, separated from other dense regions by sparse space. It finds odd shapes and labels outliers as noise, but struggles when density varies.
• Hierarchical (agglomerative) clustering does not commit to one answer. It merges the two closest groups again and again, recording a tree (a dendrogram) that you can cut at any height.

Click the canvas to add points, shift-click to drop a small burst, and alt-click (option-click) to remove one. Then compare how each algorithm reacts. Try moons and rings with K-means: it fails in a very instructive way.

Real uses include customer segmentation, grouping news stories, compressing colour palettes (k-means on pixel colours), finding hot spots in location data, and, increasingly, organising text embeddings produced by language models. See the Unsupervised Learning lesson for the bigger picture and the Embedding Explorer for clusters in meaning space.

How it works

All three algorithms here use plain Euclidean distance between points. What differs is the rule for grouping.

What the canvas shows

• Point colours are cluster ids, drawn from the viridis palette. Grey dots are not yet assigned.
• K-means: tinted regions are the Voronoi cells of the centroids (every location is coloured by its nearest centroid). Dashed lines are centroid trails.
• DBSCAN: filled dots are core points, hollow rings are border points, crosses are noise. Hover a point to see its eps-ball and neighbours.
• Hierarchical: colours come from cutting the dendrogram below the yellow line. Click the dendrogram to move the cut.

Everything is computed exactly: no precomputed answers, no simulated animation. Datasets are generated from a seeded random number generator so you can reproduce a run; press N for a fresh sample.

K-means

K-means looks for k centres that minimise the inertia: the sum of squared distances from each point to its nearest centre. Finding the global minimum is NP-hard, so everyone uses Lloyd's heuristic (Lloyd, 1982), which alternates two steps:

1. Assign: give each point the colour of its nearest centroid.
2. Update: move each centroid to the mean of the points assigned to it.

Each step can only lower (or keep) the inertia, and there are finitely many assignments, so the loop always stops. But it stops at a local minimum that depends on where the centroids started. Step through a run and watch the inertia chart: it falls quickly, then flattens.

Why initialisation matters

Random initialisation picks k data points at random. Two centroids can land in the same blob and never separate. k-means++ (Arthur and Vassilvitskii, 2007) picks the first centre at random and each next one with probability proportional to its squared distance from the nearest centre already chosen. That spreads centres out and gives an expected inertia within O(log k) of optimal. It is the default in scikit-learn. Compare the two on the blobs dataset a few times with R.

Where it breaks

Voronoi cells are convex, so k-means can only carve the plane with straight boundaries. It cannot follow moons or rings, and on stretched (anisotropic) blobs it prefers to cut across them. It also has no notion of outliers: every point pulls on some centroid. An empty cluster keeps its previous centroid in this lab; libraries usually relocate it to a far-away point.

DBSCAN

DBSCAN (Ester, Kriegel, Sander and Xu, 1996) defines clusters by density. With two settings, a radius eps and a count minPts, every point gets a role:

• Core: at least minPts points (including itself) lie within eps.
• Border: not core, but within eps of a core point.
• Noise: neither. These are reported as outliers rather than forced into a group.

A cluster is everything reachable by hopping from core point to core point in steps of at most eps, plus the border points hanging off them. Press Run to watch that flood-fill: it starts at an unvisited core point and grows until no more points are reachable, then starts the next cluster.

Choosing eps

The original paper suggests the k-distance plot shown under the canvas: for each point, the distance to its (minPts minus 1)-th nearest neighbour, sorted. Points inside clusters have small values; noise has large ones. A good eps sits near the knee where the curve shoots up. Click the chart to set eps there. A common rule of thumb for minPts is twice the number of dimensions (Schubert et al., 2017), so 4 in 2D, higher for noisy data.

Where it breaks

One eps for the whole dataset means clusters of very different density cannot all be found at once: a radius big enough for the sparse cluster merges the dense ones. HDBSCAN extends the idea by effectively trying every eps and keeping the most stable clusters. Border points that touch two clusters are assigned to whichever reaches them first.

Hierarchical

Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest clusters until one remains. The record of merges, with the distance at which each happened, is a dendrogram. Cutting it with a horizontal line gives a flat clustering: every branch below the line is one cluster.

"Closest clusters" needs a definition. That is the linkage:

• Single: distance between the two nearest members. Follows chains, so it recovers rings and moons, but one bridge of points can glue two clusters together.
• Complete: distance between the two farthest members. Produces compact clusters of similar diameter.
• Average: mean distance over all cross pairs (UPGMA). A compromise between the two.
• Ward: merge the pair that increases total within-cluster variance the least (Ward, 1963). The hierarchical cousin of k-means, with a similar taste for round clusters.

The lab updates distances with the Lance-Williams formula, which expresses the distance from a newly merged cluster to every other cluster in terms of distances already known, so nothing is recomputed from raw points. Heights are drawn on a square-root scale so the early, small merges stay visible.

Evaluating clusters

Without labels, how do you know a clustering is good? You cannot, fully. But two internal measures help.

Inertia and the elbow

Inertia always falls as k grows (k equal to n gives zero). Plot it against k and look for the "elbow" where extra clusters stop paying for themselves. The chart under the canvas runs k-means++ to convergence for k = 1 to 8 (best of four restarts) on your current points. Click a k to use it. Elbows are often ambiguous, which is why the second measure exists.

Silhouette

For each point, let a be its mean distance to the other members of its own cluster and b its mean distance to the members of the nearest other cluster. Its silhouette is (b - a) / max(a, b) (Rousseeuw, 1987). Near 1 means well inside a clear cluster, near 0 means on a boundary, negative means probably in the wrong cluster. The lab reports the mean over all clustered points (noise is excluded for DBSCAN). The yellow bar in the elbow chart marks the k with the best silhouette.

Both measures reward round, well separated blobs. On moons and rings, the "right" answer (one cluster per shape) often scores worse than a k-means cut. That is a real lesson: internal metrics encode assumptions too. When you have even a few labels, external measures such as the adjusted Rand index are more trustworthy.

Things to try

• Rings with K-means (k = 2), then DBSCAN, then single linkage. Which ones recover the two rings?
• Uniform noise: the elbow chart has no elbow, and silhouettes are mediocre for every k. There are no clusters to find.
• Anisotropic blobs: K-means cuts across the ellipses; average or single linkage does better.
• Add a far-away burst with shift-click and watch it drag a k-means centroid, while DBSCAN calls it noise or a new cluster.