\( \newcommand{\vect}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\mat}[1]{\boldsymbol{\mathbf{#1}}} \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\Prob}{\mathbb{P}} \newcommand{\T}{^{\top}} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\ihat}{\mkern1mu\hat{\boldsymbol{\imath}}\mkern2mu} \newcommand{\jhat}{\mkern1mu\hat{\boldsymbol{\jmath}}\mkern2mu} \newcommand{\pd}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\argmax}{\operatorname*{arg\,max}} \newcommand{\argmin}{\operatorname*{arg\,min}} \newcommand{\cdata}[1]{\class{c-data}{#1}} \newcommand{\cmodel}[1]{\class{c-model}{#1}} \newcommand{\ctruth}[1]{\class{c-truth}{#1}} \newcommand{\cgrad}[1]{\class{c-grad}{#1}} \newcommand{\closs}[1]{\class{c-loss}{#1}} \newcommand{\cparam}[1]{\class{c-param}{#1}} \newcommand{\csecond}[1]{\class{c-second}{#1}} \renewcommand{\,}{\mkern3mu} \)

Lloyd’s algorithm

Alternate the two facts of k-means: assign every point to its nearest centre, then move every centre to the mean of its points. Prove that J never goes up and that the algorithm stops, trace it by hand on nine points, and see why it can stop at a local minimum.

ML03.1.2L2 Intermediate25 min

In review

The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.

Before this lesson: ML03.1.1 Clustering as an objective

What you will be able to do

State Lloyd’s algorithm as an alternation of an assignment step and an update step.
Prove that neither step can raise J, and that the algorithm stops after finitely many steps.
Trace the algorithm by hand on a small data set, recording J after every half-step.
Explain why the point where it stops can be a local minimum rather than the best clustering.
Implement the algorithm with vectorised distances and match it with scikit-learn’s KMeans.

The question

The last lesson left a chicken-and-egg problem. If we knew the clusters, the best centres would be their means. If we knew the centres, the best clusters would be their Voronoi cells. We know neither. What happens if we simply guess one and keep alternating, and is that guaranteed to settle down?

From the last lesson

1. With the assignments fixed, where should each centre go?

Show answer

At the mean of the points assigned to it: \(\vect{\mu}_k = \frac{1}{n_k}\sum_{i \in C_k} \vect{x}_i\).

2. For the nine points with the bridge point in the upper group, what is \(J\)?

Show answer

\(J = 2 + 8.8 = 10.8\), with centres \((1.5, 1.5)\) and \((6, 5.2)\).

Intuition

Guess \(K\) centres anywhere. Then repeat two moves. Assign: every point joins its nearest centre. Update: every centre moves to the mean of the points that joined it. Each move is the best possible answer to one half of the problem while the other half is held still.

This is Lloyd’s algorithm, the method almost everyone means when they say “k-means”.

ML03.1.2-F1

One round of Lloyd’s algorithm on the nine points from the centres \((1, 1)\) and \((2, 1)\). Assign: each point joins its nearest centre, so all but two points go to \((2, 1)\). Update: each centre moves to the mean of its points (green arrows).

A bad start, as here, gets corrected quickly. After one update the second centre has been dragged up towards the crowd of points it was given. The next assignment hands the lower points back to the first centre, and so on until nothing changes.

Build it up

Step 1. Start. Choose \(K\) starting centres. The simplest choice is \(K\) data points picked at random. Here we take \((1, 1)\) and \((2, 1)\) on purpose: two centres jammed into one corner.

Step 2. Assign. For every point, compute its squared distance to each centre and pick the smallest. With fixed centres this is the best assignment (Fact 2 of the last lesson).

Step 3. Update. Move each centre to the mean of its points. With fixed assignments this is the best choice of centres (Fact 1).

Step 4. Repeat, and know when to stop. Go back to Step 2. If no point changes cluster, the next update would put every centre exactly where it already is, so nothing can ever change again. That is the moment to stop.

Step 5. Keep score. Record \(J\) after every half-step. The first four half-steps from our start give \(179\), then \(52.214\), then \(23.918\), then \(10.8\), and the next assignment changes nothing. The numbers only go down. The next section proves that they always do.

The formal statement

Lloyd’s algorithm

Given points \(\vect{x}_1, \dots, \vect{x}_n\) and starting centres \(\vect{\mu}_1, \dots, \vect{\mu}_K\):

Assign. For each \(i\), set \(z_i = \argmin_k \norm{\vect{x}_i - \vect{\mu}_k}^2\). If the current cluster of \(\vect{x}_i\) is among the nearest, keep it.
Update. For each \(k\) with at least one point, set \(\vect{\mu}_k\) to the mean of the points with \(z_i = k\). A centre with no points stays where it is.
Stop if no \(z_i\) changed in step 1. Otherwise go to step 1.

The tie rule in step 1 (“keep the current cluster”) looks like a detail, but the proof needs it.

Theorem

Neither step can raise \(J\), and the algorithm stops after finitely many rounds.

The assignment step cannot raise \(J\). Each point’s term is \(\norm{\vect{x}_i - \vect{\mu}_{z_i}}^2\). Step 1 replaces it by the smallest of the \(K\) squared distances, which is no larger than the one it had. A point that switches cluster switches to a centre that is strictly nearer, by the tie rule, so its term strictly falls.

The update step cannot raise \(J\). For each cluster, the sum of squared distances to a centre is smallest when the centre is the mean (last lesson). Replacing each centre by the mean can only lower each cluster’s sum. A centre with no points does not appear in \(J\) at all.

The algorithm stops. Let \(J_t\) be the value of \(J\) after the \(t\)-th update. It depends on the assignment only, because after an update the centres are the means of the assigned points. If round \(t + 1\) changes any assignment, the assign step strictly lowers \(J\) and the update does not raise it, so

\[ J_{t+1} < J_t . \]

So while the algorithm keeps going, the values \(J_1 > J_2 > J_3 > \cdots\) are all different, and therefore the assignments behind them are all different: no assignment can come back. There are at most \(K^n\) assignments of \(n\) points to \(K\) clusters. So after at most \(K^n\) rounds an assignment must repeat, and the only way that can happen is that nothing changed: the algorithm has stopped.

ML03.1.2-F2

\(J\) after every half-step on the nine points from \((1, 1)\) and \((2, 1)\). Each step can only lower \(J\), and when an assignment step changes nothing the algorithm stops.

But it stops at a local minimum. When it stops, every point is in the cell of its own centre and every centre is the mean of its cell. No single step can improve \(J\). That is a local minimum of \(J\), and it need not be the best clustering. The proof guarantees descent, not the global minimum. Finding the best clustering exactly is NP-hard, even for two clusters, so no fast algorithm is expected to guarantee it.

Go deeper: how many rounds does it take?

The bound \(K^n\) is enormous: for the nine points it is \(2^9 = 512\), and it grows exponentially with \(n\). In practice Lloyd’s algorithm usually stops after a handful of rounds, a few dozen at most on large data. Arthur and Vassilvitskii note that the number of possible clusterings is at most \(K^n\) and that “in practice, very few iterations are usually required”. scikit-learn also stops early when the centres move less than a small tolerance (tol=1e-4, relative to the spread of the data), and caps the rounds at max_iter=300.

Worked example

Run Lloyd’s algorithm on the nine points from the centres \((1, 1)\) and \((2, 1)\).

Assign 1. The bridge point \((4, 4)\) is at squared distance \({9 + 9} = 18\) from \((1, 1)\) and \({4 + 9} = 13\) from \((2, 1)\), so it joins \((2, 1)\). Every point except \((1, 1)\) and \((1, 2)\) does the same. Adding each point’s smaller squared distance:

\[ \begin{aligned} J &= 0 + 0 + 1 + 1 + 32 + 41 \\ &\quad + 41 + 50 + 13 = 179 . \end{aligned} \]

Update 1. Cluster 1 is \(\{(1, 1), (1, 2)\}\), with mean \((1, 1.5)\). Cluster 2 holds the other seven points, whose coordinates add to \((34, 29)\), so its mean is \({(34/7,\; 29/7)} \approx (4.857,\; 4.143)\). With the same assignments and these centres, \(J = 731/14 \approx 52.214\).

Assign 2. The second centre now sits near the upper group. The point \((2, 1)\) is at squared distance \(1.25\) from \((1, 1.5)\) but about \(18.0\) from \((4.857, 4.143)\), so it moves to cluster 1, and so does \((2, 2)\). The bridge point stays in cluster 2: about \(0.76\) against \(15.25\). Now \(J = 1172/49 \approx 23.918\).

Update 2. The means are \((1.5, 1.5)\) and \((6, 5.2)\), the centres of the last lesson, and \(J = 10.8\).

Assign 3. Every point is already nearest its own centre (the bridge point: \(5.44\) against \(12.5\)), so nothing changes and the algorithm stops.

ML03.1.2-F3

Lloyd’s algorithm on the nine points, four half-steps. Assignment frames show the Voronoi cells; update frames show each centre’s move as a green arrow. \(J\) falls \(179 \to 52.214 \to 23.918 \to 10.8\), and a fifth half-step changes nothing.

Code

From scratch. The one trick is to compute all \(n \times K\) squared distances at once by broadcasting, instead of looping over points.

import numpy as np

X = np.array([(1, 1), (2, 1), (1, 2), (2, 2), (6, 5), (7, 5), (6, 6), (7, 6), (4, 4)], dtype=float)

def lloyd(X, C, max_rounds=100):
    """Lloyd's algorithm. Returns the final centres, the assignment and J after every half-step."""
    C = np.array(C, dtype=float)
    z, history = None, []
    for _ in range(max_rounds):
        D2 = ((X[:, None, :] - C[None, :, :]) ** 2).sum(axis=-1)   # n by K squared distances
        new_z = D2.argmin(axis=1)
        if z is not None:                                         # tie rule: keep a tied cluster
            keep = D2[np.arange(len(X)), z] == D2.min(axis=1)
            new_z[keep] = z[keep]
        history.append(D2[np.arange(len(X)), new_z].sum())        # J after assigning
        if z is not None and np.array_equal(new_z, z):
            break
        z = new_z
        for k in range(len(C)):
            if np.any(z == k):
                C[k] = X[z == k].mean(axis=0)                     # an empty cluster keeps its centre
        history.append(((X - C[z]) ** 2).sum())                    # J after updating
    return C, z, history

C, z, history = lloyd(X, [(1, 1), (2, 1)])
print("J after each half-step:", [round(h, 3) for h in history])
print("final centres:", C.round(3).tolist())

J after each half-step: [np.float64(179.0), np.float64(52.214), np.float64(23.918), np.float64(10.8), np.float64(10.8)]
final centres: [[1.5, 1.5], [6.0, 5.2]]

The algorithm stopped at \(J = 10.8\). Is that the best possible? With nine points we can simply try every way to split them into two non-empty groups. There are \({(2^9 - 2)/2} = 255\), since each split can be written with point 1 in group 1.

def J_of(z):
    return sum(((X[z == k] - X[z == k].mean(axis=0)) ** 2).sum() for k in (0, 1))

splits = [np.array([0] + [(b >> i) & 1 for i in range(8)]) for b in range(1, 2 ** 8)]
values = np.sort([J_of(s) for s in splits])
print(len(splits), "splits; the three lowest J:", values[:3].round(3).tolist())

255 splits; the three lowest J: [10.8, 14.0, 32.0]

ML03.1.2-F4

All 255 two-group splits of the nine points, sorted by \(J\). Lloyd’s answer from \((1, 1)\) and \((2, 1)\) is the very best. The second best, \(J = 14\), matters too: it is the trap in the pitfalls.

Now the library. KMeans with the same starting centres and one run follows the same path. Its inertia_ is \(J\) and n_iter_ counts the rounds.

from sklearn.cluster import KMeans

km = KMeans(n_clusters=2, init=np.array([(1, 1), (2, 1)], dtype=float), n_init=1,
            algorithm="lloyd").fit(X)
print("centres:", km.cluster_centers_.round(3).tolist(), " J:", round(km.inertia_, 3),
      " rounds:", km.n_iter_)

centres: [[1.5, 1.5], [6.0, 5.2]]  J: 10.8  rounds: 3

With init="random" and n_init=1, scikit-learn starts from two data points chosen at random, as our Step 1 suggested. Running it from twenty seeds shows that the answer depends on the start, and our from-scratch version agrees once it is started from every pair of distinct points.

library = {round(KMeans(2, init="random", n_init=1, random_state=s).fit(X).inertia_, 3)
           for s in range(20)}
pairs = [(a, b) for a in range(9) for b in range(a + 1, 9)]
ends = [round(lloyd(X, X[[a, b]])[2][-1], 3) for a, b in pairs]
print("KMeans, 20 random starts, J values seen:", sorted(library))
print("from scratch, all", len(pairs), "starts:", {v: ends.count(v) for v in sorted(set(ends))})

KMeans, 20 random starts, J values seen: [10.8, 14.0]
from scratch, all 36 starts: {np.float64(10.8): 22, np.float64(14.0): 14}

Of the 36 starts at a pair of data points, 22 end at \(J = 10.8\) and 14 end at \(J = 14\). Four of these counts hang on a tie: from those four starts, some point is exactly as far from both starting centres, our code gives it to the first centre listed, and the other choice would change where the run ends. Which starts fall into the trap, and why, is the subject of the pitfalls and of the next lesson.

Explore

ML03.1-X1

k-means stepper

Pick a data set and \(K\), then place centres by clicking the plot or with the random or k-means++ buttons. Press assign and update in turn, or step and play, and watch \(J\) after every half-step. Drag any point, or move the selected one with its sliders, to see how the cells react. Try the nine points from \((2, 2)\) and \((7, 6)\), and then the moons.

Four step frames of Lloyd's algorithm on the nine points from the centres (1, 1) and (2, 1): assign with J = 179, update with J = 52.214, assign with J = 23.918 and update with J = 10.8, with Voronoi cells tinted and green arrows for the centres' moves.

Pitfalls

ML03.1.2-F5

Wrong beside right. Started from \((2, 2)\) and \((7, 6)\), a start that looks sensible, Lloyd’s algorithm stops at \(J = 14\) with the bridge point in the lower group. Started from \((1, 1)\) and \((2, 1)\) it reaches the best, \(J = 10.8\).

“J never goes up, so the algorithm finds the best clustering.”

It finds a clustering that no single step can improve. From \((2, 2)\) and \((7, 6)\) the first assignment puts the bridge point with \((2, 2)\), at squared distance \(8\) against \(13\). The update moves the centres to \((2, 2)\) and \((6.5, 5.5)\), and the bridge point is now at \(8\) against \(8.5\), so it stays. Every point is in its own cell, every centre is its cell’s mean, and \(J = 14\) for good.

“The algorithm has converged when the centres stop moving, so test them for equality.”

Comparing floating-point centres for exact equality can fail by a rounding error on every round. Test whether the assignment changed, which is exact, or, as scikit-learn does, stop when the centres move less than a small tolerance.

“A cluster can never end up empty.”

It can, when a centre starts so far out that no point is nearest to it. Our version leaves such a centre where it is. scikit-learn instead moves it to the point that is farthest from its own centre, so that every cluster ends with at least one point.

Check yourself

Recall

1. What are the two steps of Lloyd’s algorithm?

Show answer

Assign: every point joins its nearest centre. Update: every centre moves to the mean of its points.

2. Why can the assignment step not raise \(J\)?

Show answer

Each point’s term is replaced by its smallest squared distance to any centre, which is no larger than the term it had.

3. Why does the algorithm stop after finitely many rounds?

Show answer

While assignments keep changing, \(J\) strictly falls, so no assignment can repeat. There are at most \(K^n\) assignments, so the changes must end.

4. On the nine points from \((1, 1)\) and \((2, 1)\), what is \(J\) after each half-step?

Show answer

\(179\), \(52.214\), \(23.918\), \(10.8\), and then \(10.8\) again, when the assignment no longer changes.

5. What does “a local minimum” mean for k-means?

Show answer

An assignment and centres where every point is nearest its own centre and every centre is the mean of its points, so no step improves \(J\), although another clustering may have a lower \(J\).

Exercises

1. ★ Run Lloyd’s algorithm by hand on the values \(1, 2, 6, 7, 8\) on a line with \(K = 2\), starting from the centres \(1\) and \(2\). Give the centres and \(J\) after each update.

Show solution

Assign 1: \(1\) joins centre \(1\); \(2, 6, 7, 8\) join centre \(2\) (a tie is impossible here). Update 1: centres \(1\) and \({(2 + 6 + 7 + 8)/4} = 5.75\), with \(J = 0 + 3.75^2 + 0.25^2 + 1.25^2 + 2.25^2 = 20.75\).

Assign 2: \(2\) is \(1\) from centre \(1\) and \(3.75\) from \(5.75\), so it joins centre \(1\); the rest stay. Update 2: centres \(1.5\) and \(7\), with \(J = 0.25 + 0.25 + 1 + 0 + 1 = 2.5\).

Assign 3: nothing changes, so the algorithm stops at centres \(1.5\) and \(7\) with \(J = 2.5\).

2. ★★ The last lesson proved that, for any point \(\vect{c}\), a cluster’s sum of squared distances to \(\vect{c}\) equals its sum about the mean plus \({n_k \norm{\bar{\vect{x}} - \vect{c}}^2}\). Use it to say exactly how much the update step lowers each cluster’s sum, and find how much \(J\) falls in Update 2 of the worked example.

Show solution

Take \(\vect{c}\) to be the old centre. The update replaces it by \(\bar{\vect{x}}\), which removes the term \(n_k \norm{\bar{\vect{x}} - \vect{c}}^2 \ge 0\) and changes nothing else, so \(J\) falls by exactly that amount.

In Update 2, cluster 2 has \(n_k = 5\), old centre \((34/7, 29/7)\) and new centre \((6, 5.2)\). The difference is \((8/7,\; 1.057)\), more exactly \({(8/7,\; 37/35)}\), with squared length \(64/49 + 1369/1225 = 2969/1225 \approx 2.424\). So cluster 2’s sum falls by \(5 \times 2.424 \approx 12.118\). Cluster 1 moves from \((1, 1.5)\) to \((1.5, 1.5)\) with \(n_k = 4\), a fall of \(4 \times 0.25 = 1\). In total \(J\) falls by about \(13.118\), from \(23.918\) to \(10.8\).

3. ★★★ Find a start for the nine points that leads Lloyd’s algorithm to \(J = 14\) in one assignment, and explain, using the border between two Voronoi cells, why the bridge point can never leave the lower group once the centres are \((2, 2)\) and \((6.5, 5.5)\).

Show solution

The centres \((2, 2)\) and \((7, 6)\) work: the bridge point is at squared distance \(8\) from \((2, 2)\) and \(13\) from \((7, 6)\), so the first assignment already gives the groups of \(J = 14\), and the update moves the centres to \((2, 2)\) and \((6.5, 5.5)\).

With those centres, \(\vect{\mu}_2 - \vect{\mu}_1 = (4.5, 3.5)\), \(\norm{\vect{\mu}_2}^2 = 42.25 + 30.25 = 72.5\) and \(\norm{\vect{\mu}_1}^2 = 8\), so the border equation of the last lesson reads

\[ \begin{aligned} 2\,(4.5x + 3.5y) &= 72.5 - 8, \\ 9x + 7y &= 64.5 . \end{aligned} \] At \((4, 4)\), \(9x + 7y = 64 < 64.5\): the bridge point is on the side of \((2, 2)\), just. The assignment does not change, so the centres do not change, so the border does not move. The algorithm has stopped.

Summary card

Assign to the nearest centre, move each centre to its mean, repeat.

ML03.1.2-F1

Two moves, repeated.

Assign. \(z_i = \argmin_k \norm{\vect{x}_i - \vect{\mu}_k}^2\).
Update. \(\vect{\mu}_k = \frac{1}{n_k}\sum_{i : z_i = k} \vect{x}_i\).
Guarantee. \(J\) never rises; the algorithm stops after finitely many rounds.
Catch. It stops at a local minimum that depends on the start.
Nine points. \(179 \to 52.214 \to 23.918 \to 10.8\).

Sources and next steps

Sources. Each was opened and checked against this lesson on 15 November 2026.

Trevor Hastie, Robert Tibshirani and Jerome Friedman, The Elements of Statistical Learning, 2nd edition. Algorithm 14.1 (Section 14.3.6) alternates the two minimisations; the text notes that each step reduces the criterion, so convergence is assured, but the result may be a suboptimal local minimum, and recommends many random starts.
Andrew Ng, CS229 lecture notes: The k-means clustering algorithm. Presents k-means as coordinate descent on the distortion \(J\), so \(J\) decreases monotonically, remarks that clusterings with exactly equal \(J\) could in theory oscillate, and that \(J\) is not convex, so local optima occur.
David Arthur and Sergei Vassilvitskii, k-means++: The Advantages of Careful Seeding. Section 1: solving the problem exactly is NP-hard even with two clusters, there are at most \(K^n\) clusterings, and very few iterations are usually needed. Section 2.1 states the algorithm in the same four steps as here.
scikit-learn developers, sklearn.cluster.KMeans, version 1.9.1. The parameters init, n_init, algorithm="lloyd", tol and max_iter, and the attributes inertia_ (the sum of squared distances to the closest centre) and n_iter_. The relocation of an empty cluster to a far point is in the library’s source, _k_means_common.pyx.

Next. ML03.1.3 Starting well and choosing K asks how to pick the start, and how many clusters to ask for.

This lesson unlocks

ML03.1.3 Starting well and choosing K

Your progress is saved in this browser only. No account, no tracking.