#k-means — Unsupervised learning

Grouping without labels: centroids that move, inertia that drops, the choice of k — and the shapes where k-means fails.

What you'll play with

Welcome to #k-means. On screen: 150 grey points inside a cube, visibly gathered into four clumps… that no one labelled. The four large coloured spheres are the centroids: we just dropped them at random on four points of the dataset, and no point is coloured yet. That is all k-means gets: a point cloud, a number k, and one simple rule to repeat. No ground truth to copy: this is unsupervised learning.
Run one round: /step. Two phases. Assignment: each point joins the nearest centroid and takes its colour. Update: each centroid jumps to the mean of the points it just won.
Another /step. A few points switch sides at the boundary between two groups, and the centroids move less than the first time. Watch the inertia in the right panel: the sum of squared distances from each point to its centroid. It drops every round, never the other way: neither of the two phases can raise it.
Let it run to the end: /run. When no point changes sides anymore, the centroids stop moving: this is convergence. But look at the result: with this start, two centroids that fell into the same clump share it, while a single centroid has to cover two clumps at once. This is a local minimum: nothing will dislodge them.
The most common remedy is a better start: /init kmeans++. The first centroid is drawn at random; each next one is drawn with a probability proportional to the square of its distance to the nearest centroid already placed. Isolated points, far from everything, are much more likely to be picked: the initial centroids spread out, and bad starts become rare.
Run /run again and compare the final inertia with the previous run (I remember it for you). Same points, same k: only the starting point changed.
Let us change the shape of the cloud: /dataset rings. Two concentric rings, one inside the other, in the horizontal plane. To a human eye, two obvious groups.
First /run, to see the pie-slice cut: k-means does not see the shape of a group, only the distance to a centre (for rings, you will need #dbscan). Then the question we have been dodging: why 4? Type /elbow: I re-run k-means for k = 1 to 8 and record each final inertia.
Your turn: /dataset blobs then /elbow for a clean elbow at k = 4; /k 2 then /run on the rings (two slices, not two rings); /dataset moons and /dataset elongated, two more shapes k-means cuts wrong; /init random with several /seed values to collect local minima; /links to see who belongs to whom; /reset to start over. Next: #pca, to project these clouds into 2D before clustering them, and #hierarchical-clustering, which frees you from picking k.

Channel commands

/k <1..8> — Change the number of clusters; drops the centroids again, iteration 0.
/step — One Lloyd iteration: assignment then centroid update.
/run — Iterates to convergence (displacement < 1e-4) or 30 rounds.
/init <random|kmeans++> — Change the centroid initialisation; restarts at iteration 0.
/seed <1..99> — Redraws points and starting centroids with another seed.
/dataset <blobs|rings|moons|elongated> — Change the shape of the point cloud; restarts at iteration 0.
/links — Show or hide a thin line from each point to its centroid.
/elbow — Elbow method: final inertia for k = 1..8.
/reset — Back to blobs, k = 4, random init, iteration 0.

Glossary

k-means: Partitioning algorithm that assigns n points to k groups by minimising the sum of squared distances from each point to its group centre. Fast and simple, but it assumes round groups and requires you to pick k in advance.
centroid: Centre of a cluster: the mean (barycentre) of all points assigned to it. This is the only "memory" a cluster leaves with k-means.
inertia: Sum, over all points, of the squared Euclidean distance to their cluster centroid. This is what k-means shrinks at each iteration; it always decreases as k grows.
assignment / update: The two phases of Lloyd's algorithm: each point joins the nearest centroid (assignment), then each centroid jumps to the mean of its points (update). Repeat until nothing changes.
convergence: When no point changes cluster anymore: centroids stop moving and inertia stops dropping. Here we stop when the mean displacement falls below 1e-4, or after 30 rounds.
local minimum: A partition where k-means stops without being the best possible: two centroids share a group while another one covers two groups. The algorithm has no way out; only a different start can do better.
k-means++: Initialisation that picks the first centroid at random, then each next one with a probability proportional to the squared distance to the nearest centroid already placed. Starting centroids are spread out, which avoids most bad local minima.
elbow method: A way to pick k: plot the final inertia for k = 1, 2, 3… and keep the k where the curve breaks, the "elbow": beyond it, one more centroid barely helps.
unsupervised learning: Learning without labels: the model only sees data, never the right answer. Clustering (k-means), dimensionality reduction (PCA) and anomaly detection all belong to it.
cluster: A group of points judged similar to each other and different from the others. Clustering means partitioning a dataset into clusters without knowing any categories in advance.

Other channels in Unsupervised learning

#k-means — Grouping without labels: centroids that move, inertia that drops, the choice of k — and the shapes where k-means fails.
#pca — Principal component analysis: find the axes where data varies most, project, compress — and measure what is lost.
#hierarchical-clustering — Merge the points two at a time until only one is left: the dendrogram, the linkage criteria, and the cut height that decides the number of clusters.
#dbscan — Group by density: epsilon, MinPts, core, border and noise points — the algorithm that finds arbitrary shapes and ignores intruders.
#anomaly-detection — Spot what fits nothing: z-score / Mahalanobis, Isolation Forest, LOF — three ways to say 'this point is odd'.
#t-sne-umap — Map the high dimensions: t-SNE and UMAP unfold 10-dimensional data into a readable 2D map — perplexity, neighbors, and reading pitfalls.