K-means clustering, from scratch

Most machine learning needs labelled examples — "this is a cat, this is a dog." But sometimes you just have a pile of data and want to find the natural groups in it, with no labels at all. That's clustering, and the most popular method is k-means. It's beautifully simple: two steps, repeated until things stop moving. Let's run it by hand.

The idea

You tell k-means how many groups you want — that's the k. It then finds k cluster centres (called centroids) by repeating two steps:

1. Assign — put each data point into the group whose centroid is nearest.
2. Update — move each centroid to the average (mean) position of the points assigned to it.

Repeat. Each round, points get sorted better and centroids drift to the middle of their group, until nothing changes. That's it.

"Nearest" is measured by distance. In 1-D it's just $|a - b|$; in general it's the straight-line (Euclidean) distance $\sqrt{(a_1-b_1)^2 + (a_2-b_2)^2 + \cdots}$.

Worked example

Four points on a line: 1, 2, 10, 11. We want k = 2 groups. To show that k-means self-corrects, let's start with two deliberately bad centroids: $c_1 = 1$ and $c_2 = 2$.

Round 1 — assign (each point to its nearer centroid):

point 1  → c1 (dist 0) 
point 2  → c2 (dist 0)
point 10 → c2 (|10−2|=8  <  |10−1|=9)
point 11 → c2 (|11−2|=9  <  |11−1|=10)
groups: {1}   and   {2, 10, 11}

Round 1 — update (centroid = mean of its group):

c1 = mean{1}        = 1
c2 = mean{2,10,11}  = 23/3 ≈ 7.67

Round 2 — assign (with the new centroids 1 and 7.67):

point 1  → c1 (0)
point 2  → c1 (|2−1|=1  <  |2−7.67|=5.67)
point 10 → c2 (|10−7.67|=2.33  <  9)
point 11 → c2 (3.33  <  10)
groups: {1, 2}   and   {10, 11}

Round 2 — update:

c1 = mean{1,2}   = 1.5
c2 = mean{10,11} = 10.5

Round 3 — assign: 1 and 2 stay with $c_1=1.5$; 10 and 11 stay with $c_2=10.5$. Nothing changed → done. Final clusters {1, 2} and {10, 11}, centroids 1.5 and 10.5 — exactly the two natural groups, recovered from a bad starting guess in two rounds.

The gotchas

• You choose k. Pick too few or too many and the groups won't match reality. A common trick is the elbow method: try several k's and look for where adding another cluster stops helping much.
• The start matters. Different starting centroids can lead to different final groups (k-means finds a good grouping, not always the best). In practice you run it several times and keep the best.
• It likes round blobs. K-means assumes clusters are roughly circular and similar-sized; for stranger shapes, other methods (like DBSCAN) do better.

Why this matters

Clustering is how you find structure with no answer key: customer segments, topics in documents, anomalies that don't fit any group, compressing colours in an image. The assign → update rhythm also reappears in more advanced algorithms (it's a special case of a method called EM), so the intuition pays off well beyond k-means.

Now run it. In the demo, start from rough centroids, press assign, then update, and repeat — watch messy guesses snap onto the real clusters, exactly like our worked example.

---

This is your first taste of learning without labels. Want to run k-means yourself? Try a free lesson.