K-Means in machine learning, explained in 5 lines

Module 01 · Machine Learning · 55 concepts

In depth / 15 lines

K-Means, in more detail

K-Means splits your points into k groups, and you have to pick k yourself.

It starts by dropping k centres at random positions.

Every point joins whichever centre is nearest.

Each centre then moves to the middle of the points that joined it.

Those two steps repeat until nothing moves any more.

It always finishes, but not always in the same place.

A different random start gives a different answer, so tools run it several times.

It assumes clusters are round, similar in size and similar in density.

Real groups are often long, thin or nested, and it handles those badly.

It also forces every point into a cluster, including obvious outliers.

Features must be scaled, because it works entirely on distance.

Choosing k is the awkward part, and there is no correct answer.

The elbow method plots error against k and looks for the bend.

The silhouette score measures how well each point fits the group it landed in.

Both are guides rather than verdicts, and looking at the clusters still matters most.

Want the full technical article? Wikipedia ↗

Deep dive

What is underneath K-Means

What it is minimising

J = \sum_{k=1}^{K} \sum_{\mathbf{x} \in C_k} \left\| \mathbf{x} - \boldsymbol{\mu}_k \right\|^2

$K$ : how many clusters, chosen by you before it runs.
$C_k$ : the set of points assigned to cluster $k$ .
$\boldsymbol{\mu}_k$ : that cluster's centroid.

This is the within-cluster sum of squares: the total squared distance from every point to the centre of its own cluster.

Finding the global minimum of $J$ is NP-hard. What the algorithm actually does is descend it.

The two steps, which alternate

C_k = \left\{ \mathbf{x} : \left\| \mathbf{x} - \boldsymbol{\mu}_k \right\| \leq \left\| \mathbf{x} - \boldsymbol{\mu}_j \right\| \; \forall j \right\}

Assignment: each point joins the nearest centroid.

\boldsymbol{\mu}_k = \frac{1}{|C_k|} \sum_{\mathbf{x} \in C_k} \mathbf{x}

Update: each centroid moves to the mean of its members.

That mean is exactly the point minimising squared distance to a set, which is why the objective uses squares and the update uses a mean.

Both steps can only lower $J$ or leave it alone, so the algorithm converges. It converges to a local minimum, not the global one.

One run, in order

Choose $K$ and place the initial centroids.
Assign every point to its nearest centroid.
Move every centroid to the mean of its assigned points.
Repeat two and three until no assignment changes.
Record $J$ , then run the whole thing again from different starting points and keep the best.

Why the start matters so much

Two centroids landing inside one true cluster will split it and leave another cluster unclaimed, and no amount of iterating recovers from that.

P(\text{choose } \mathbf{x}) \propto D(\mathbf{x})^2

k-means++ picks each new starting centroid with probability proportional to its squared distance from the nearest centroid already chosen, which spreads them out.

It costs one extra pass and reliably beats random initialisation, which is why it is the default everywhere.

The assumptions hiding in the objective

Squared Euclidean distance makes clusters that are spherical, similarly sized, and similarly dense.

Elongated clusters get cut across their length. A small cluster next to a large one gets absorbed. Density-varying data comes out wrong in a way that looks plausible.

$K$ itself is an input, and the elbow method on $J$ is a heuristic rather than an answer: $J$ falls monotonically with $K$ and reaches zero when every point is its own cluster.

Test yourself

One question on this card. Every option explains itself once you pick, right or wrong.

Question 1

What must you decide before running K-Means?

Machine Learning

55 concepts in this module, then a graded test with every answer explained.

Study this module →