K-Means Clustering

Step through assigning points to centroids and moving centroids to the mean

Beginner

Dataset:

Number of clusters (k)4

Initialisation

Region shadingLines to centroids

Tap the plot to add a point. Large discs with a cross are centroids; dashed lines are their trails.

Next: assignment step. Give every point to its nearest centroid.

Points: 160
Iteration: 0
WCSS (inertia): -
Phase: assign

WCSS per iteration

Take an assignment step to start the curve.

Elbow method (best of 5 runs)

Tap a column to set k. Look for the bend where extra clusters stop helping much.

What is k-means?

K-means is an unsupervised algorithm: it gets points with no labels and has to find groups on its own. You choose the number of clusters k, and the algorithm looks for k centroids that make every point as close as possible to the centroid of its own cluster.

It does this with two alternating steps (Lloyd's algorithm). Assign every point to its nearest centroid, then move every centroid to the mean of its points. Repeat until no point changes cluster. Each step lowers the within-cluster sum of squares, so the process always converges, but only to a local minimum that depends on where the centroids started.

Centroid

The centre of a cluster: the mean of the points assigned to it. K-means keeps exactly k of them.

Assignment step

Every point joins the cluster of its nearest centroid. This carves the plane into Voronoi regions with straight borders.

Update step

Every centroid jumps to the mean of its points, the position that minimises that cluster’s squared distances.

Inertia (WCSS)

The total squared distance from each point to its centroid. Both steps can only lower it, so the algorithm always stops.

Key formulas

Objective: within-cluster sum of squares

WCSS = Σⱼ Σ_{x ∈ Cⱼ} ‖x − μⱼ‖²

Cⱼ: the set of points in cluster j
μⱼ: the centroid of cluster j

The two steps

assign: c(x) = argminⱼ ‖x − μⱼ‖² update: μⱼ = (1 / |Cⱼ|) Σ_{x ∈ Cⱼ} x

k-means++ seeding

P(pick x as next centroid) = D(x)² / Σ D(x′)²

D(x): distance from x to the nearest centroid chosen so far

Choosing k with the elbow method

WCSS always falls as k grows (with k = n it reaches zero), so you cannot just minimise it. Plot it against k and pick the point where the curve bends: after that, extra clusters buy very little.

Where k-means fails

It assumes roughly round clusters of similar size and spread, because boundaries between clusters are always straight lines halfway between centroids. Curved shapes such as the moons, or clusters of very different sizes, need methods like DBSCAN, spectral clustering or Gaussian mixtures.

How to use this visualizer

1
Pick a dataset or press Clear and tap the plot to add your own points.
2
Set k and choose an initialisation. Random picks k data points; k-means++ spreads the starts out.
3
Press Assign points: each point takes the colour of its nearest centroid and a line is drawn to it.
4
Press Update centroids: each centroid moves to the mean of its points, leaving a dashed trail.
5
Keep stepping (or use Auto-play) until no point changes cluster. Watch WCSS fall in the chart.
6
Use New random start several times with Random points to find starts that get stuck in a worse solution.
7
Check the elbow chart, then load Moons with k = 2 to see the classic failure case.

K-means in code

Python

import numpy as np

def kmeans(X, k, iters=100, seed=0):
    rng = np.random.default_rng(seed)
    C = X[rng.choice(len(X), k, replace=False)]      # random data points
    for _ in range(iters):
        d = ((X[:, None, :] - C[None, :, :]) ** 2).sum(axis=2)
        labels = d.argmin(axis=1)                    # assignment step
        new_C = np.array([X[labels == j].mean(axis=0) if np.any(labels == j) else C[j]
                          for j in range(k)])        # update step
        if np.allclose(new_C, C):
            break
        C = new_C
    wcss = ((X - C[labels]) ** 2).sum()
    return C, labels, wcss

Complexity

Time complexity

O(n · k · d · i)

n points, k clusters, d dimensions, i iterations. Each assignment step compares every point with every centroid.

Space complexity

O(n + k · d)

The data, one label per point and k centroids.

Practice problems

Problem 1: One full iteration by hand

Points on a line: 1, 2, 3, 8, 9, 10, 11. Start with k = 2 and centroids μ₁ = 1, μ₂ = 3. Run k-means until it converges and give the final WCSS.

Show solution

Assign: 1 → μ₁. 2 is a tie (distance 1 to both); break it towards μ₁.

3, 8, 9, 10, 11 → μ₂

Update: μ₁ = 1.5, μ₂ = (3+8+9+10+11)/5 = 8.2

Assign: 1, 2, 3 → μ₁ (3 is 1.5 from μ₁, 5.2 from μ₂); 8, 9, 10, 11 → μ₂

Update: μ₁ = 2, μ₂ = 9.5

Assign: nothing changes, so the algorithm has converged.

WCSS = (1 + 0 + 1) + (2.25 + 0.25 + 0.25 + 2.25) = 2 + 5 = 7

Final clusters {1, 2, 3} and {8, 9, 10, 11}, WCSS = 7.

Problem 2: Reading an elbow chart

A dataset gives these WCSS values for k = 1 to 6: 120, 48, 21, 18, 16, 15. Which k would you choose, and why not k = 6?

Show solution

Drops: 1→2: 72, 2→3: 27, 3→4: 3, 4→5: 2, 5→6: 1

The big gains stop after k = 3; every extra cluster after that removes only 1 to 3 units.

k = 6 has the lowest WCSS, but WCSS always decreases with k (it is 0 when every point is its own cluster),

so the lowest value just means the most clusters, not the best structure.

Choose k = 3, the elbow of the curve.

Discussion

Questions, ideas or a different approach? Join the conversation.