epochs

Learn · Module 16 · ML from scratch · Lesson 1 of 5

k-means from scratch

k-means is the simplest clustering algorithm, and a classic first thing to implement. It's four lines of logic in a loop.

3 minute read

In short
  • k-means repeats: assign each point to the nearest centre, move centres to the mean.
  • Use broadcasting for distances and guard against empty clusters.
  • Results depend on the start; use several runs or k-means++.

The idea

k-means groups points into k clusters. Start with k centres. Then repeat two steps: assign each point to its nearest centre, and update each centre to the average of its points. Stop when the centres stop moving.

The code

Python, NumPy only
import numpy as np

def kmeans(X, k, steps=10, seed=0):
    rng = np.random.default_rng(seed)
    centres = X[rng.choice(len(X), k, replace=False)]
    for _ in range(steps):
        # distance from every point to every centre: shape (n, k)
        d = ((X[:, None, :] - centres[None, :, :]) ** 2).sum(axis=2)
        labels = d.argmin(axis=1)
        new = np.array([X[labels == j].mean(axis=0) if (labels == j).any() else centres[j] for j in range(k)])
        if np.allclose(new, centres):
            break
        centres = new
    return centres, labels

X = np.array([[1, 1], [1.5, 2], [1, 1.5], [8, 8], [8.5, 9], [9, 8]], dtype=float)
centres, labels = kmeans(X, k=2)
print(np.round(centres, 2).tolist())   # [[8.5, 8.33], [1.17, 1.5]]
print(labels.tolist())                 # [1, 1, 1, 0, 0, 0]
  1. 1
    Broadcasting does the distances

    X[:, None, :] has shape (6, 1, 2) and centres[None, :, :] has (1, 2, 2). Subtracting gives (6, 2, 2): every point minus every centre, with no loops.

  2. 2
    argmin picks the nearest centre
  3. 3
    Empty clusters keep their old centre

    Without this guard, mean() of no points returns NaN, a classic bug.

  4. 4
    The result

    The two groups are found: the three points near (1, 1.5) and the three near (8.5, 8.3).

Your turn

Why can k-means give different answers on different runs?

Take it further

How to choose k (the elbow method: plot total distance against k), its complexity (n points × k centres × dimensions per step), and its weaknesses (assumes round, similar-sized clusters; sensitive to scale, so standardise features first).

Common mistakes

  • Computing distances with nested Python loops instead of broadcasting.
  • Not handling empty clusters, which produce NaN centres.
  • Forgetting a convergence check or an iteration cap.
Check yourself

Answer in your own words, out loud or on paper, before you open the model answer.

Implement k-means in NumPy.

I'd first confirm the inputs: an n-by-d array and k. Then: pick k distinct data points as starting centres, using a seeded random generator so it's reproducible. Loop: compute the squared distance from every point to every centre in one step with broadcasting, giving an n-by-k array; assign each point to the nearest centre with argmin; compute each centre as the mean of its points, keeping the old centre if a cluster ends up empty. Stop when the centres stop moving or after a maximum number of iterations. I'd mention the cost per iteration, n times k times d, that results depend on the starting centres so k-means++ or several restarts help, and that features should be on similar scales.

More to think about
  • How do you choose the number of clusters?
  • What are the limitations of k-means?

Go further

Was this lesson clear?