Skip to content
Tutorials Center
My learning

Topics

Lesson 46 of 49 ยท Projects

Project: K-Means Clustering

Implement k-means clustering in NumPy. Build a distance matrix with broadcasting, update centroids without loops, detect convergence, restart for stability and plot the clusters.

Sometimes you have data but no labels. A shop has thousands of customers described by two numbers and wants natural groups; a biologist has measurements and wants to see whether they form families. Clustering finds such groups automatically, and k-means is the most famous method. It is simple enough to write in a few lines of NumPy, and it is a perfect workout for broadcasting, aggregation along axes and boolean masks.

In this project you will generate three blobs of random points, compute the distance from every point to every center in one broadcast expression, assign points to the nearest center, move the centers to the middle of their points, repeat until nothing changes, improve the result with random restarts, and draw the final clusters.

The algorithm

K-means needs one number from you: k, the number of clusters. Then it repeats two steps:

  1. Assign: give every point the label of its nearest center.
  2. Update: move each center to the mean of the points assigned to it.

Both steps can only lower (or keep) the total squared distance of points to their centers, called the inertia. So the algorithm always settles down. It may settle in a local optimum rather than the best possible answer, which is why we will add restarts later.

flowchart TD
    A["Pick k starting centers<br/>(random data points)"] --> B["Assign each point<br/>to its nearest center"]
    B --> C["Move each center to<br/>the mean of its points"]
    C --> D{"Centers moved?"}
    D -- yes --> B
    D -- no --> E["Done: labels and centers"]

K-means alternates between assigning points and updating centers until the centers stop moving.

Step 1: blob data

We create three groups by adding Gaussian noise around three known centers, then stack them into one array of shape (180, 2). K-means will never see the true group labels.

Python Three random blobs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 2: the distance matrix with broadcasting

This is the heart of the project. We need the distance between each of n points and each of k centers, as an (n, k) table. The trick is to reshape the two inputs so that broadcasting builds all pairs:

  • X has shape (n, 2). Insert an axis: X[:, None, :] has shape (n, 1, 2).
  • centers has shape (k, 2). Insert an axis: centers[None, :, :] has shape (1, k, 2).
  • Subtracting them broadcasts to (n, k, 2): the coordinate differences for every point-center pair.
  • Squaring and summing over the last axis gives (n, k) squared distances.
flowchart LR
    P["X[:, None, :]<br/>(180, 1, 2)"] --> S["subtract<br/>(180, 3, 2)"]
    Q["centers[None, :, :]<br/>(1, 3, 2)"] --> S
    S --> T["square and sum<br/>over axis 2"]
    T --> U["squared distances<br/>(180, 3)"]

Broadcasting stretches the size-1 axes, so one subtraction compares every point with every center.

For choosing the nearest center we do not need the actual distance. The square root keeps the order, so squared distances are enough and cheaper.

Python Distances to all centers in one expression

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

argmin(axis=1) gives, for each point (each row), the column index of the smallest distance, which is its cluster label. np.bincount counts how many points each cluster got. Comparing against a slow loop for one row is a cheap way to be sure the broadcasting is right.

Step 3: updating the centers without a loop

The new center of cluster j is the mean of all points with label j. The simplest version loops over clusters and uses a boolean mask: X[labels == j].mean(axis=0). That is only a few iterations (k is small), so it is perfectly fine.

There is also a loop-free version that is worth knowing. Build a one-hot matrix onehot of shape (n, k) where onehot[i, j] is 1 if point i belongs to cluster j. Then onehot.T @ X sums the points of each cluster in one matrix product, and dividing by the cluster sizes gives the means.

Python Two ways to compute cluster means

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

np.eye(k)[labels] is a handy idiom: indexing the identity matrix with an integer array picks one row per label, producing the one-hot matrix directly. Dividing by counts[:, None] turns the 1D counts into a column so each row of sums is divided by its own count.

If a cluster ends up with no points, its mean is 0 / 0 (nan, with a warning), and the center would vanish. Robust implementations keep the old center for empty clusters, which is what the final code below does.

Step 4: the complete algorithm with convergence and restarts

Now we wrap everything into kmeans(X, k, rng). We stop when the largest movement of any center is below a tiny tolerance, or after max_iter rounds as a safety net. We track the inertia, ((X - centers[labels]) ** 2).sum(), to measure quality. Because the starting centers are random, different starts can land in different local optima; a standard remedy is to run the algorithm several times and keep the result with the lowest inertia.

Python Full k-means with restarts, and a scatter plot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The inertia list shows the guarantee in action: it never goes up, and it stops changing once the assignments are stable. The three recovered centers are close to the true ones (0, 0), (5, 5) and (0, 6), and each cluster holds 60 points.

Step 5: how do you choose k?

Real data does not come with the answer. A common heuristic is the elbow method: run k-means for several values of k and plot the inertia. Adding clusters always lowers inertia, but past the true number of groups the improvement becomes small, so the curve bends like an elbow.

Python The elbow plot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see a big drop from k=1 to k=2 and again to k=3, then much smaller gains. The bend at k=3 matches how the data was made. Real data is rarely this clean, so treat the elbow as a hint, not a proof.

Ideas to extend the project

  • Use k-means++ seeding: choose the first center randomly, then choose each next center with probability proportional to its squared distance from the nearest chosen center, using rng.choice(n, p=...).
  • Standardize features first (subtract the mean, divide by the standard deviation) when columns use different units.
  • Compress an image: treat each pixel's RGB values as a point and replace every pixel with its center color.
  • Compare your result with sklearn.cluster.KMeans; the labels may be numbered differently, but the groups should match.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. X has shape (180, 2) and centers has shape (3, 2). What is the shape of X[:, None, :] - centers[None, :, :]?

    The shapes (180, 1, 2) and (1, 3, 2) broadcast to (180, 3, 2): every point paired with every center, with the two coordinate differences along the last axis.
  2. 2. What does labels = d2.argmin(axis=1) return, where d2 has shape (n, k)?

    axis=1 collapses the columns, which are centers. For every row (point) argmin returns the column index with the smallest distance, i.e. the nearest center.
  3. 3. Why do we run k-means several times from random starts?

    The algorithm always converges, but to a result that depends on the starting centers. Keeping the run with the lowest inertia reduces the chance of a bad local optimum.
  4. 4. What does np.eye(k)[labels] build?

    Indexing the identity matrix with an array of n labels picks n rows, each with a single 1 in the column of its label, giving shape (n, k).

Summary

  • K-means alternates between assigning points to the nearest center and moving centers to the mean of their points.
  • points[:, None, :] - centers[None, :, :] builds all point-center differences by broadcasting; sum squares over the last axis for distances.
  • argmin(axis=1) gives labels; masks or a one-hot matrix product give the new centers.
  • Inertia never increases during a run; stop when the centers stop moving, and keep the best of several random restarts.
  • The elbow plot suggests k, but it is only a heuristic.

Next up: practice what you have learned in the Practice Exercises.