Skip to the lesson
ML Explorer Reju Sam John

ML Explorer · Level 3 · Classic ML

k-means clustering

With no labels at all, find groups by moving a few centres until they settle.

About 10 minutes · No maths needed; the maths is there if you want it

Overview

Every lesson so far had answers to learn from: a number to predict, or a label. This one has none. We have points, and we want to know whether they fall into groups.

k-means does it with two simple moves, repeated: give each point to its nearest centre, then move each centre to the middle of its points. We step through it, watch its score fall, see two starts end in different places, and ask how many groups to look for.

The points are made up. See "About the data" at the end.

You'll learn

  • how k-means alternates an assign step and an update step, and what inertia measures
  • why inertia never rises, and why the answer still depends on where you start
  • why the best inertia keeps falling as you add clusters, so it cannot choose K by itself
  1. No labels

    These points have no labels. The task is to find groups in them.

    Finding groups in data without labels is called clustering. It is a kind of unsupervised learning: unsupervised because there are no answers to check against.

    Your eye probably sees three clumps. k-means is a way to make a computer find groups like these, and to say exactly what it means by a good grouping.

    The maths

    The data are nn feature vectors x1,…,xn\mathbf{x}_1, \dots, \mathbf{x}_n, with no yiy_i. Clustering gives each point a cluster number c(i)∈{1,…,K}c(i) \in \{1, \dots, K\}. The numbers are names: nothing makes cluster 1 come before cluster 2.

  2. Start: K centres

    Decide how many clusters to look for, and place that many starting centres.

    We write the number of clusters as K, a capital letter. It is a different thing from the k in k-nearest neighbours, which counted neighbours. Here K = 3. You choose K; k-means does not learn it.

    k-means needs a starting spot for each centre. A simple rule is to pick K of the data points. Here we picked three points that all sit in the lower-left clump, a poor-looking start on purpose, so you can watch the centres travel.

    The centres are the large outlined shapes. Each has its own shape: circle for cluster 1, triangle for cluster 2, square for cluster 3. The algorithm made these numbers up. They are not true classes, and swapping them round would change nothing.

    The maths

    The centres are μ1,…,μK\boldsymbol{\mu}_1, \dots, \boldsymbol{\mu}_K, each a point in the same space as the data. Here μ\boldsymbol{\mu} is a centre, not a population mean of the whole data set.

  3. Assign: nearest centre

    Give every point to the centre nearest to it.

    Each point now takes the shape of its nearest centre. The shading shows, for every spot on the plot, which centre is nearest, and a line marks each border.

    To score a grouping, k-means uses the inertia. For every point, take the squared distance to its own centre, then add them all up. It is a sum, not an average: each point adds its own term. Smaller is better: it means points sit close to their centres.

    The value depends on the units. These features have none, but if they were recorded in units ten times smaller, every number would be ten times larger and the inertia a hundred times larger. Compare inertias only on the same data.

    The maths

    The assign step sets

    c(i)=arg⁡min⁡k∥xi−μk∥2c(i) = \arg\min_{k} \lVert \mathbf{x}_i - \boldsymbol{\mu}_k \rVert^2

    Here kk just numbers the clusters; it is not the kk of k-nearest neighbours. A tie goes to the lower-numbered centre. The inertia is

    inertia=∑i=1n∥xi−μc(i)∥2\text{inertia} = \sum_{i=1}^{n} \lVert \mathbf{x}_i - \boldsymbol{\mu}_{c(i)} \rVert^2

    Dividing by nn would give the mean squared distance; k-means software usually reports the sum. The shaded patches are called Voronoi cells: each holds the spots nearer to one centre than to any other. The shading is a simplification, worked out on a grid of 60 × 56 small squares, each coloured by the centre nearest to its middle, so the drawn borders follow the grid.

  4. Update: move to the mean

    Move each centre to the mean of its points. Then assign again, and repeat.

    Each centre moves to the mean of the points in its cluster: the average of their feature 1 values and the average of their feature 2 values. That is where the name comes from: K clusters, each summed up by its mean. The dashed lines trace where each centre has been.

    Press "Next: assign" and every point goes to whichever centre is now nearest. Right after an update, some points sit in another centre's patch; the next assign step moves them. Keep pressing. The chart shows the inertia after every step.

    The three clusters it ends with are exactly the three clumps the points were made from (see "About the data"). k-means did not know that. It never saw a label.

    The maths

    Neither step can raise the inertia. The assign step changes only c(i)c(i), and picking the nearest centre can only shrink each point's term. The update step changes only the centres. For one cluster CkC_k with nkn_k points and mean xˉk\bar{\mathbf{x}}_k, any centre μ\boldsymbol{\mu} gives

    ∑i∈Ck∥xi−μ∥2=∑i∈Ck∥xi−xˉk∥2+nk∥xˉk−μ∥2\sum_{i \in C_k} \lVert \mathbf{x}_i - \boldsymbol{\mu} \rVert^2 = \sum_{i \in C_k} \lVert \mathbf{x}_i - \bar{\mathbf{x}}_k \rVert^2 + n_k \lVert \bar{\mathbf{x}}_k - \boldsymbol{\mu} \rVert^2

    so the mean is the centre with the smallest sum of squared distances.

    Why it stops, in outline: there are only finitely many ways to split nn points into KK groups. Each round either lowers the inertia, so that split cannot come back, or leaves it unchanged, and then the centres stay put and the next assign step changes no label. So k-means always stops, at a fixed point: assigning changes no label and updating moves no centre.

    If a cluster ever lost all its points, it would have no mean to move to. Our version then keeps its centre where it is. That does not happen in this demo.

  5. Starting points matter

    A different start can stop at a worse answer. So run several starts and keep the best.

    Start A is the run you just watched. Start B swaps just one of its three starting points for another point in the same clump. The dotted rings mark the starting points. Press "Start B".

    Start B did nothing wrong. It reached a fixed point, where neither step changes anything. A fixed point need not have the lowest inertia possible, and k-means cannot tell which kind it has reached.

    There are also more careful ways to choose the starts. The best known is called k-means++. This page does not use it.

    The maths

    A fixed point of k-means is often loosely called a local minimum: no single assign or update step can lower the inertia from there. Finding the split with the lowest inertia of all is a hard problem in general: trying every split is hopeless, because their number grows enormously with nn, and no known shortcut works on every data set. That is why several starts are the standard practice.

    Keeping the lowest of several runs is safe because the inertia measures the same thing in every run: same data, same KK.

  6. Choosing K

    With more clusters the best inertia you can reach is always lower, so inertia alone cannot choose K. Look for the bend.

    Move the K slider. For each K from 1 to 8 we ran 10 random starts and kept the lowest inertia. The plot shows that run's centres as plus signs, with lines between their cells; the chart shows its inertia.

    The elbow is a hint, not a rule. On real data the bend is often soft or missing, and the right K also depends on what the groups are for.

    The maths

    The lowest possible inertia can never rise as KK grows: with K+1K + 1 centres you can keep the best KK centres and add one more anywhere, and the points that move to it only get nearer. Our numbers are the best of 10 starts, not the lowest possible, so that argument does not cover them; on this data they fall at every step all the same.

    With K=1K = 1 the single centre is the mean of all the points, and the inertia is the total sum of squares, ∑i∥xi−xˉ∥2\sum_i \lVert \mathbf{x}_i - \bar{\mathbf{x}} \rVert^2. That is n−1n - 1 times the sum of the two features' sample variances (dividing by n−1n - 1).

    In this step the plot draws only the cells' borders and the centres, because for more than three clusters there are not enough shapes.

Quick check

Why can't inertia rise during k-means?

There is no check and no undoing. Each step lowers the inertia, or leaves it alone, by the way it is built.

Right. With the centres fixed, the nearest centre gives each point its smallest squared distance. With the clusters fixed, the mean gives each cluster its smallest sum of squared distances. Neither step can make things worse.

k-means never sees labels. Clustering is unsupervised: there are no true labels to compare with.

Update steps lower it too: for a fixed set of points, the mean is the centre with the smallest sum of squared distances.

Inertia at K = 8 is lower than at K = 3. Does that make K = 8 better?

Lower inertia is better only at a fixed K. The best inertia keeps falling as K grows, so a larger K wins by default.

Right. Here the best inertia is at K = 8 against at K = 3, but the extra five centres only cut real clumps into pieces. Look for the bend instead, and treat it as a hint.

None of them is empty here. Every centre in the best K = 8 run has points; they just split the three clumps into smaller pieces.

Same units make the numbers comparable, but a lower number at a larger K is still expected, so it says nothing about which K is right.

Lesson complete

  • Clustering finds groups in data without labels. The cluster numbers are names the algorithm makes up.
  • k-means repeats two steps: assign each point to its nearest centre, then move each centre to the mean of its points.
  • Inertia, the sum of squared distances to the assigned centres, never rises. k-means stops at a fixed point, which need not be the lowest inertia possible.
  • Run several starts and keep the lowest inertia. Choose K with care: the best inertia keeps falling as K grows, and the elbow is only a hint.

Common misconceptions

  • "k-means always finds the best grouping." It finds a fixed point, which depends on the start.
  • "Cluster 1 means the same thing every time." The numbering is arbitrary; another run can give the same groups different numbers.
  • "The K with the lowest inertia is best." The largest K always wins on best inertia.
Next lesson: Principal component analysis →

Further reading

  1. James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning (2nd ed.), Section 12.4.1, "K-Means Clustering". The book starts from random cluster numbers rather than random centres, shows why each step cannot make the objective worse, and runs the algorithm from several starts, keeping the best.

About the data. The points are made up, in three round clumps of 20, made one clump after another: feature 1 = m₁ + 0.8 z₁ and feature 2 = m₂ + 0.8 z₂, where z₁ and z₂ are independent draws from a normal distribution with mean 0 and SD 1, made with mulberry32 and seed 101 (z₁ before z₂ for each point). The clump centres (m₁, m₂) are (2, 2), (6, 2.5) and (4, 6). Start A uses the 1st, 2nd and 3rd points made as its centres; start B uses the 1st, 2nd and 4th. Start B was found by trying every set of three points as a start, in order, and taking the first whose final inertia is more than 20% above the lowest any of them reached. The random starts in steps 5 and 6: for each K, 10 starts, each K different data points picked by index with mulberry32(200 + K) (index = whole part of 60 × draw; a repeat is drawn again). When a point is equally near two centres, it goes to the lower-numbered one. Displayed values are rounded; the calculations are not.

If this helped, you can .