Classical ML

How does K-means clustering work?

By Interview Clozo · Published 27 October 2026 · Last verified 26 October 2026 · 13 min read

How does K-means clustering work? K-means clustering is an unsupervised algorithm that splits unlabeled data into k groups by assigning each point to its nearest centroid, then moving each centroid to the mean of its points, until nothing changes. It minimizes a quantity called inertia, yet it can settle on a poor answer: in the worked example with three clusters, one run stops at an inertia of 101 when 1.5 is possible.¹

In this article

Before you start
Why interviewers ask this
K-means clustering from first principles
The Staff-level answer
The rubric
Three variants of this question
Common mistakes
Follow-up questions
Sources

Before you start

This page is one step of the machine learning algorithms learning path.

Why interviewers ask this

K-means is a natural first clustering question because the algorithm is short enough to explain in a minute, yet it has real failure modes. A candidate who only recites the steps shows memory. A candidate who explains why the loop stops, and why stopping is not the same as being right, shows understanding.

A weak answer says "pick k centers, assign, update" and ends. A strong answer names the objective, inertia, and says the loop reaches only a local minimum, so you restart it. A Staff-level answer adds how k is chosen without labels, why the starting centroids matter, and when the shape assumption breaks. Expect follow-ups such as "does it always converge?", "is the result optimal?" and "how do you pick k?". Each is answered below with numbers you can recompute.

K-means clustering from first principles

K-means clustering: K-means clustering is an unsupervised algorithm that partitions unlabeled data points into k groups by choosing k centers and repeatedly reassigning points to the nearest center, so that the total squared distance from each point to its own center becomes as small as the method can make it.

In plain words

Picture placing k pizza shops in a city so that every house is near a shop. Start with guesses. Each house picks its nearest shop. Then each shop moves to the middle of its houses. Repeat until no house switches. Each pass leaves the total squared walking distance the same or smaller, so the shops eventually stop moving.

The analogy breaks in one place. Real shops would cut walking distance, but k-means cuts squared distance, which punishes far-away houses much more.

In one precise sentence, k-means alternates between assigning points to their nearest centroid and replacing each centroid by the mean of its points, which lowers inertia until the assignments stop changing.

Step 1: Choose k and place the starting centroids

The loop starts from k initial centroids, and you choose k yourself. The scikit-learn documentation states that "this algorithm requires the number of clusters to be specified". The starting centroids are usually k data points picked at random, or points chosen by the k-means++ rule described below.

In the running example the data are six points on a line, at 0, 1, 10, 11, 20 and 21 (illustrative), with k equal to 2 and starting centroids at 0 and 1, a deliberately poor start.

Input: the data and k. Output: k centroids. You now know the loop's starting state; the next step uses it to form clusters.

Step 2: Assign every point to its nearest centroid

Each point is assigned to its nearest centroid, measured by squared Euclidean distance. The Stanford Computer Science 229 (CS229) notes write this as a minimum over the centroids.

In the example the point 1 sits exactly on the centroid at 1, so it joins that cluster together with 10, 11, 20 and 21, while the centroid at 0 keeps only the point 0.¹ The inertia of this first assignment, measured with the centroids in use, is 942.¹

Input: the points and the centroids. Output: one cluster label per point. If a point is equally close to two centroids, a fixed rule such as "take the lower-numbered one" settles it; any rule works if it is applied the same way every round. Assignment alone moves no centroid; that is the next step.

Step 3: Move each centroid to the mean of its points

Each centroid moves to the mean of its points. For a fixed assignment the mean is the point with the smallest sum of squared distances, so this move can only lower inertia. That is why the Stanford notes can show that the objective never rises.

In the example the cluster holding only 0 keeps its centroid at 0, and the cluster of 1, 10, 11, 20 and 21 moves its centroid to the mean, 12.6.¹

Input: the clusters. Output: new centroids. Old assignments may now be wrong, because some points are closer to a moved centroid, which is why the loop has a fourth step.

Step 4: Repeat until assignments stop changing, and why it can get stuck

The loop stops when assignments stop changing. In the example, round two moves only the point 1, to the centroid at 0. The inertia is 135.64, and the new centroids are 0.5 and 15.5. Round three changes nothing and ends at an inertia of 101.5.¹ Inertia fell from 942 to 135.64 to 101.5 and never rose. The Stanford notes show k-means is coordinate descent on the distortion J, which "must monotonically decrease, and the value of J must converge".

Convergence is not quality. The distortion is non-convex, so the loop can finish at a local minimum, a solution that no single reassignment or centroid move can improve even though a better one exists elsewhere. This poor start still reached the best two-cluster split (101.5), the same value as the elbow table below, so a bad start does not always mean a bad result. With three clusters it does: on the same points, starting at 0, 1 and 15 ends at an inertia of 101, while starting at 0, 10 and 20 ends at 1.5.¹

K-means is one loop: assign every point, move every centroid, and stop when no assignment changes.CC BY 4.0 — source: How does K-means clustering work?

Step-by-step description

Pick k starting centroids.
Each point joins its nearest centroid.
Each centroid moves to its cluster mean.
Stop if nothing changed, else assign again.

The loop starts from k initial centroids.
Each point is assigned to its nearest centroid.
Each centroid moves to the mean of its points.
The loop stops when assignments stop changing.

Why restarts and k-means++ reduce the risk of a poor result

Running k-means several times from different starts reduces the risk of a poor local minimum. As the scikit-learn documentation puts it, the computation is often done several times with different initializations. The KMeans reference says the final result is the best of n_init runs in terms of inertia. With n_init='auto' it uses 10 runs for random starts and 1 run for k-means++. So under scikit-learn's defaults (k-means++ start, n_init='auto') only one run is made; set n_init yourself if you want restarts.

K-means++ is a seeding method that selects the initial centroids one at a time, picking each new seed with probability proportional to its squared distance from the nearest seed already chosen, which speeds up convergence. It carries a proof: Arthur and Vassilvitskii show the expected cost is at most 8 times (ln k plus 2) times the optimal cost. For k equal to 10 that factor is 34.4207.¹ It is a worst-case bound on expected cost, not a promise of the optimum.

Worked example: the elbow on inertia

Inertia keeps falling as k grows and reaches zero with six clusters, because with one cluster per point every distance is zero. So the lowest inertia cannot pick k. The elbow method is the habit of running k-means for several values of k, plotting inertia against k and choosing the bend where further clusters add little.

On the six example points, the best inertia is 401.5 with one cluster, 101.5 with two, 1.5 with three, 1.0 with four, 0.5 with five and 0 with six.¹ After three clusters inertia barely moves. The bend is at three, matching the three visible pairs.

Inertia drops sharply until three clusters and flattens after, so the bend at three suggests k of three.CC BY 4.0 — source: How does K-means clustering work?

Text description of the diagram

Inertia is 401.5 with one cluster, 101.5 with two and 1.5 with three.
Inertia keeps falling as k grows and reaches zero with six clusters.

Worked example: the silhouette score

The silhouette score checks clusters without labels. For each point, a is the mean distance to the other points in its own cluster and b is the mean distance to the points of the next nearest cluster. The point's score is s equal to (b minus a) divided by the larger of a and b, as defined in the scikit-learn documentation, and the score is averaged over the points. A value close to one means b is much larger than a.

On the example points, the mean silhouette score is 0.8981 for the three-cluster solution and 0.6267 for the two-cluster solution.¹ The higher score agrees with the elbow. When the two disagree, domain judgment about how many groups are useful decides.

What k-means assumes about the data

K-means assumes clusters that are roughly round and similar in spread. The scikit-learn documentation says inertia "makes the assumption that clusters are convex and isotropic" and so responds "poorly to elongated clusters, or manifolds with irregular shapes". In very high-dimensional spaces, Euclidean distances tend to become inflated.

The loop itself is a heuristic. Wikipedia's k-means++ page notes that finding an exact solution for arbitrary input is nondeterministic polynomial-time (NP) hard, that the standard approach, Lloyd's algorithm, frequently finds reasonable solutions quickly, and that its result can be arbitrarily bad compared with the optimum.

Because the mean is pulled by extreme points, outliers can drag a centroid. Distance to the nearest centroid is a rough outlier signal; see anomaly detection on a time series.

Knowing it is half the job. Saying it is the other half.

Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.