What are the two steps of k-means?

The assignment step gives each point to whichever centroid is closest (usually by Euclidean distance). The update step recomputes each centroid as the mean of the points now assigned to it. Alternating these two — assign, then move — is guaranteed to lower the total within-cluster distance (inertia) each round until it stops changing.

Does k-means always find the best clustering?

No. K-means converges to a local optimum that depends on where the centroids start, so a bad initialization can produce a poor clustering. In practice you run it several times with different random starts (or use k-means++ to seed the centroids far apart) and keep the run with the lowest inertia.

K is a hyperparameter you must set. A common heuristic is the elbow method: run k-means for a range of k values, plot the inertia, and pick the k where the curve bends — adding more clusters after that point barely reduces the error. The silhouette score is another way to judge how well-separated the clusters are.

What is k-means used for?

Customer and market segmentation, image color quantization and compression, grouping documents or embeddings by similarity, anomaly detection, and as a fast preprocessing step to summarize data. It is one of the most widely used clustering methods because it is simple, fast, and scales well.

LABS · 04 / K-MEANS

The Gravity Wells.

Q: What is k-means clustering?

K-means is an unsupervised algorithm that partitions data into k groups. You pick k and place k centroids, then repeat two steps: assign every point to its nearest centroid, and move each centroid to the mean (average position) of the points assigned to it. When the assignments stop changing, the algorithm has converged and the centroids sit at the centers of the discovered clusters.

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

Pick k and seed centroids. Choose how many clusters, and drop k starting centers (randomly, or with k-means++).
Assign. Give every point to its nearest centroid — that's the cluster it belongs to right now.
Move. Recompute each centroid as the mean of the points assigned to it. The center follows its crowd.
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.

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

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

CPython · WebAssembly

QUICK CHECK

Did it stick?

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.

Finished this one? 0 / 61 Labs done

Explore the topic

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

ML Foundations