Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

LABS · 04  /  K-MEANS

The Gravity Wells.

A cloud of points, no labels. Drop three centroids anywhere and let two moves repeat: every point joins its nearest centroid, then every centroid slides to the middle of its crowd. Round after round, the mess snaps into clean clusters.

THE GIST · 20 SECONDS

K-means groups data into k clusters with no labels. Place k centroids, then loop two steps: assign — colour each point by its nearest centroid; move — slide each centroid to the mean of its points. Each round lowers the total within-cluster distance (inertia). When the assignment stops changing, you've converged.

  • Centroida cluster's center
  • Assignjoin the nearest centroid
  • Movecentroid → mean of its points
  • Inertiatotal spread, always drops

Hit Step to run the next move — or Play and watch the centroids drift into the heart of each cluster.

UNDER THE HOOD

What you just played, written down

Two dead-simple steps, alternated. Each one can only lower the total spread — so the loop marches downhill until the labels stop flipping.

How k-means thinks — four moves

  1. Pick k and seed centroids. Choose how many clusters, and drop k starting centers (randomly, or with k-means++).
  2. Assign. Give every point to its nearest centroid — that's the cluster it belongs to right now.
  3. Move. Recompute each centroid as the mean of the points assigned to it. The center follows its crowd.
  4. Repeat until stable. Assign, move, assign, move… When no point changes cluster, you've converged.
WHY IT ALWAYS SETTLES

Both steps reduce inertia — the total squared distance from points to their centroids. Assigning to the nearest center can't increase it, and moving to the mean minimizes it for that cluster. A quantity that only ever drops must stop.

The whole thing in code

import numpy as np

def kmeans(X, k, iters=100):
    C = X[np.random.choice(len(X), k, replace=False)]
    for _ in range(iters):
        # assign: nearest centroid per point
        d = ((X[:, None] - C[None]) ** 2).sum(-1)
        labels = d.argmin(axis=1)
        # move: centroid = mean of its points
        newC = np.array([X[labels == j].mean(0)
                         if (labels == j).any() else C[j]
                         for j in range(k)])
        if np.allclose(newC, C):
            break                       # converged
        C = newC
    return labels, C
TIMEO(n·k·i)points × clusters × iters
FINDSlocal mindepends on the seed
THE SEED MATTERS

K-means only finds a local optimum, so a bad start gives a bad clustering. Run it several times and keep the lowest inertia, or seed with k-means++ to spread the starting centroids apart.

⚠ You must choose k

K-means can't tell you how many clusters exist. Use the elbow method (plot inertia vs. k, find the bend) or the silhouette score to pick a sensible k.

↔ Its limits

It assumes roughly round, similar-sized clusters. For elongated or nested shapes, try DBSCAN or Gaussian mixtures; for non-flat geometry, spectral clustering.

★ Where it's used

Customer segmentation, image color quantization, grouping embeddings, anomaly detection, and as a quick way to summarize a large dataset.

STEP BY STEP

K-means, step by step

K-means lowers one number, the inertia: the sum of squared distances from every point to its own centroid. Here are the two rules as formulas, two full iterations worked by hand on six points, and the knobs that decide whether it works on real data.

Lloyd's algorithm, with the formulas

  1. Seed. Choose k starting centroids: k random points, or k-means++ (below).
  2. Assign. Give point x_i the label of its nearest centroid. Squared distance is enough, since the square root never changes which centroid wins.
  3. Update. Move each centroid to the mean of its points. The mean is the one location that minimizes the sum of squared distances to a set, so this step can only lower the inertia.
  4. Stop when no label changes, when centroids move less than a tolerance, or at an iteration cap. One round costs O(n·k·d) for n points in d dimensions.
# inertia: the number k-means lowers
J    = Σ_i ||x_i − μ_c(i)||²
# assign step
c(i) = argmin_j ||x_i − μ_j||²
# update step
μ_j  = mean of { x_i : c(i) = j }
K-MEANS++ IN NUMBERS

Pick the first seed at random, then each next seed with probability proportional to D(x)², its squared distance to the nearest seed so far. Starting from A in the example, the squared distances are 0, 1, 1, 41, 52 and 50 (total 145), so the second seed lands in the far group with probability 143/145 ≈ 98.6%. A uniform pick from the other five points gets there only 3 times in 5.

Worked example: six points, k = 2

  1. Data and seeds. A(1,1), B(2,1), C(1,2), D(6,5), E(7,5), F(6,6). Unlucky random seeds: μ₁ = A = (1, 1) and μ₂ = C = (1, 2), both in the lower-left group.
  2. Iteration 1, assign. Squared distance to μ₁ vs μ₂: A 0 vs 1, B 1 vs 2, C 1 vs 0, D 41 vs 34, E 52 vs 45, F 50 vs 41. Clusters {A, B} and {C, D, E, F}. Inertia 121.
  3. Iteration 1, update. μ₁ = (1.5, 1); μ₂ = ((1+6+7+6)/4, (2+5+5+6)/4) = (5, 4.5). Inertia falls to 31.5 before any label changes.
  4. Iteration 2, assign. C's squared distances are now 1.25 to μ₁ and 22.25 to μ₂, so it switches; D, E and F stay. Clusters {A, B, C} and {D, E, F}. Inertia 10.5.
  5. Iteration 2, update. μ₁ = (4/3, 4/3) ≈ (1.33, 1.33); μ₂ = (19/3, 16/3) ≈ (6.33, 5.33). Inertia 8/3 ≈ 2.67.
  6. Iteration 3. No point changes label, so the loop stops. Inertia went 121 → 31.5 → 10.5 → 2.67 and never rose. This seed recovered; on messier data two centroids can end up sharing one real cluster for good.

⚠ Scale features first

Distance treats every unit alike. Two customers 30 years apart in age and $1,000 apart in income differ by 900 + 1,000,000 in squared units, so income decides 99.9% of the distance. Standardize each feature (subtract its mean, divide by its standard deviation) before clustering.

◎ Restarts and empty clusters

Run several seeds (scikit-learn's n_init) and keep the lowest inertia; cap the loop with max_iter and a tolerance. If a centroid loses all its points, re-seed it, for example at the point farthest from its current centroid.

★ In production

For millions of points, mini-batch k-means updates centroids from small random samples. For embeddings, normalize to unit length first: then ||a − b||² = 2 − 2·cos(a, b), so plain k-means groups by cosine similarity. That is how an IVF vector index is built: k-means splits the vectors into buckets, and a query searches only the nearest few.

SOLVE IT YOURSELF

Solve it: one k-means iteration

This one is yours to write — in Python or TypeScript, running for real in your browser. Given points and centroids, do one assignment. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement assign(points, centroids): for each point (an [x, y] pair), return the index of the nearest centroid by squared Euclidean distance. Return a list of cluster indices, one per point.

HINTS — 4 IDEAS
  1. For a point p and centroid c, squared distance is (p[0]-c[0])**2 + (p[1]-c[1])**2.
  2. You don't need the square root — comparing squared distances gives the same nearest.
  3. For each point, scan all centroids and remember the index of the smallest distance.
  4. Return one cluster index per point, in order.
CPython · WebAssembly
THE PICTURE

The six points, before and after

A B C D E F A B C D E F μ₂ → (5, 4.5) round 1: seeds A and Cround 3: converged inertia 121 → 31.5 → 10.5 → 2.67
The worked example above as a picture. Dashed outlines are clusters; crosses are centroids. In round 1 both seeds sit in the lower-left group, so C gets dragged into a stretched cluster with D, E and F, and that cluster’s mean jumps most of the way across. Once the centroid has left, C is closer to the other one and switches sides. By round 3 nothing moves.
WHAT IT COSTS

Cost and trade-offs at scale

For n points in d dimensions, k clusters and i iterations.

CaseTimeSpaceWhy
Assign stepO(n·k·d) per iterationO(n) labelsEvery point measured against every centroid. This is the step that dominates, so it is what every speed-up attacks.
Update stepO(n·d)O(k·d) centroidsOne pass to sum each cluster’s points. Cheap next to assigning.
The NumPy broadcast in the code aboveSame O(n·k·d)O(n·k·d) temporary arrayFine for a lab. At 100,000 points, 50 clusters and 768 dimensions in float64 that array is 30.72 GB. Expanding |x−c|² = |x|² − 2x·c + |c|² turns it into one matrix product with a 40 MB result.
k-means++ seedingO(n·k·d), one pass per seedO(n) distancesAbout one extra iteration’s worth of work, usually repaid by fewer iterations and a better final inertia.
Elkan’s variantSkips most distance computations once centroids settleO(n·k) boundsUses the triangle inequality to prove a point cannot have changed cluster. scikit-learn offers it as algorithm="elkan"; the memory grows with k.
RestartsTotal cost × number of runsUnchangedLinear in the number of runs, and the cheapest insurance against a bad local minimum.
WATCH FOR

Common mistakes with k-means

  • Choosing the k with the lowest inertia

    Inertia always falls as k rises. With one centroid per point it is 0: on the six points above, k = 6 “wins” with inertia 0 and tells you nothing. Look for the bend in the curve, or compare silhouette scores, never the minimum.

  • Feeding it category codes

    Encode three cities as 1, 2 and 3 and k-means believes city 3 is twice as far from city 1 as city 2 is. The mean of a category code means nothing either. Use one-hot columns, or a method built for categorical data, such as k-modes.

  • Ignoring outliers

    A mean follows its most distant member. Add one point O(30, 30) to the six above and the best 2-cluster answer gives O a centroid of its own. Both real groups then merge around (3.83, 3.33), for an inertia of 64.2 against 879.1 for the natural split. Find and handle outliers first, or use k-medoids.

  • Treating cluster numbers as stable

    Cluster ids are arbitrary. Refit on next month’s data and last month’s cluster 0 can come back as cluster 2, even when the groups barely changed. Match new centroids to old ones by distance before you compare segments, or a dashboard tracking “segment 2” silently swaps meaning.

  • Believing the clusters exist

    Ask for 4 clusters on uniformly random points and you get 4 tidy-looking groups. K-means always returns k clusters, whether or not the data has any. Check that the structure is real: a low silhouette score, or clusters that change with every seed, mean there is nothing there.

QUICK CHECK

Did it stick?

See every answer, with the reasoning
  1. What are the two steps k-means alternates?

    Answer: Assign each point to its nearest centroid, then move each centroid to the mean of its points — K-means loops the assignment step (each point joins its nearest centroid) and the update step (each centroid becomes the mean of its assigned points) until the labels stop changing.

  2. Why is k-means guaranteed to converge?

    Answer: Because both steps only ever lower the total within-cluster distance (inertia) — Assigning to the nearest centroid can’t raise inertia, and moving a centroid to its mean minimizes inertia for that cluster. A value that only decreases and is bounded below must settle.

  3. Why run k-means several times with different starts?

    Answer: Because it only finds a local optimum that depends on the initial centroids — K-means converges to a local minimum determined by where the centroids started. Different seeds can give different clusterings, so you run it multiple times (or use k-means++) and keep the lowest-inertia result.

FAQ

K-means, answered

What is k-means clustering?

An unsupervised algorithm that splits data into k groups by alternating two steps — assign each point to its nearest centroid, then move each centroid to the mean of its points — until the assignment stops changing.

What are the two steps?

Assignment: each point joins its closest centroid. Update: each centroid becomes the average position of its assigned points. Repeating them lowers the within-cluster spread every round.

Does it find the best clustering?

No — only a local optimum that depends on the starting centroids. Run it several times or seed with k-means++ and keep the lowest-inertia result.

How do I choose k?

K is a hyperparameter. Use the elbow method (inertia vs. k) or the silhouette score to pick a sensible number of clusters.

Where is it used?

Customer segmentation, image color quantization, grouping embeddings, anomaly detection, and quick dataset summarization.

RESULT

—

Next → swap "nearest centroid" for soft probabilities and you have a Gaussian mixture; keep only dense neighbourhoods and it's DBSCAN. Same goal, different shapes.

Finished this one? 0 / 61 Labs done
NextThe Meaning Map: Embeddings Next on the “Structure, and making new things” ladder · rung 3 of 6

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Labs