Appendix: From the k-Means Objective to Lloyd’s Algorithm
This appendix is a supplement to the two clustering lectures parts. In class we motivated k-means through the within-cluster sum of squared distances and stated its objective — the sum of squared errors (SSE); here we open the box and show how differentiating that objective produces the two update rules of Lloyd’s algorithm. We do this first in plain element-wise form (no matrices), and only afterwards rewrite the same derivation in matrix form, because that matrix form is the natural preview of the normal equations of linear regression that we will meet later in the course.
Throughout, denotes a data point (bold), a centroid (non-bold), the -th cluster, and the whole clustering — exactly the notation of the lectures.
1. The objective, motivated by Lemma 2¶
Lemma 2 from the lectures states that for any set of points with centroid ,
The left-hand side is the total within-set pairwise squared distance; the right-hand side is times the within-cluster sum of squares (WCSS). The two are proportional, so minimizing one is the same as minimizing the other, and both are achieved by the same mean .
Apply the same lemma to a single cluster of size with centroid :
So for any fixed cluster, “compactness” (small pairwise distances) is equivalent to a small WCSS, and both are minimized by placing the centroid at the cluster mean. For clusters, the natural overall objective is therefore the total SSE:
To make the partition an explicit variable we introduce the one-hot indicator
and rewrite the objective as
with two blocks of unknowns: the centroids and the assignments .
Iris sizes. The Iris dataset has specimens described by features (sepal length/width, petal length/width). With the usual clusters we therefore optimise continuous centroid coordinates and binary assignment variables.
2. Two unknowns of two different kinds¶
The objective has a mixed continuous–discrete structure:
Centroids : continuous, unconstrained, in .
Assignments : discrete, one-hot per column.
This split is the single reason k-means is not solvable by one differentiation. We will see that:
Differentiating the SSE with respect to a centroid gives a clean closed-form update.
Differentiating the SSE with respect to an assignment gives nothing useful directly — the objective is linear in , so the optimum sits at a vertex of the assignment simplex, not at a zero of the gradient.
Both updates are derived below without any matrix notation.
3. The centroid step — element-wise differentiation w.r.t. ¶
Fix the partition (i.e. fix all ). Differentiate the SSE with respect to a single coordinate , the -th feature of the -th centroid. The only terms in the double sum that mention are those with :
Setting this to zero and dividing by 2:
Writing for the size of cluster (which is non-zero as long as the cluster is non-empty), we obtain
Stacking the -indices back into a vector gives the centroid update rule:
i.e. the mean of the points assigned to cluster . This is exactly the centroid step of Lloyd’s algorithm. The derivation used nothing but the ordinary scalar chain rule on the original double-sum objective — no matrices, no Frobenius norm.
Iris check. For Iris setosa ( specimens) this gives , the 4-vector of feature means over those 50 flowers.
4. The assignment step — linear in , minimum at a vertex¶
Now fix the centroids. Then the SSE is linear in each , because multiplies the constant :
A linear function has no interior stationary point. Setting would require for every , which is impossible as soon as two centroids are distinct.
But does not live in an unconstrained space — it lives on the assignment simplex
whose vertices are the one-hot vectors . A linear function on a simplex always attains its minimum at a vertex. The minimizing vertex is the index of the smallest coefficient:
This is the nearest-centroid assignment step of Lloyd’s algorithm. It is a discrete , not the solution of . The derivative tells us which vertex is best, but it does not give us an interior stationary point to solve for.
5. Alternating the two steps is Lloyd’s algorithm¶
Neither step alone solves the full problem: the centroid step needs a partition, the assignment step needs centroids. The natural strategy is alternating minimization (block coordinate descent):
Assignment step. Fix , update by the nearest-centroid rule of §4.
Update step. Fix , update to the cluster means of §3.
Each step cannot increase the objective:
There are only finitely many partitions of points into clusters, so the SSE can take only finitely many values; combined with strict monotonicity this guarantees termination in finitely many steps at a local optimum.
This is Lloyd’s algorithm — the procedure we have used throughout the clustering lectures. We did not invent it here; we derived it from the objective by element-wise differentiation, with the mixed continuous–discrete structure of the SSE forcing the alternation on us.
6. Matrix form: a preview of the normal equations¶
The derivation above is complete and self-contained. We now rewrite the same objective in matrix form. This is not new mathematics — it is the same content packaged compactly — but the packaging is worth the trouble, because the resulting equations are exactly the normal equations that we will meet again in linear regression.
6.1 Setup¶
Stack the data as columns of , the centroids as columns of , and the assignments as the one-hot matrix with :
The residual has as its -th column , the displacement of from its assigned centroid. The squared Frobenius norm of this residual is the sum of all squared entries:
So the k-means objective is the squared Frobenius norm of the residual:
6.2 Centroid step — same answer, in matrix form¶
Fix and differentiate with respect to . Expanding and applying the standard matrix-calculus identities and , we get
Setting this to zero gives the centroid normal equation
and, because is one-hot so ,
Reading column by column, — exactly the rule of §3. Same content, packaged in matrix notation.
6.3 The same algebraic shape appears in linear regression¶
Later in the course we will study linear regression: given a design matrix and responses , find the coefficient matrix minimizing
This is the same expression as the k-means objective. The only difference is which matrix is fixed and which is unknown:
| Problem | Fixed | Unknown | Minimizer |
|---|---|---|---|
| k-means centroid step | (one-hot) | ||
| Linear regression | (design) | (free real) |
Differentiating the regression objective w.r.t. the free gives
and setting it to zero produces the normal equations of linear regression:
The two boxed equations — for k-means and for regression — are the same algebraic shape: a symmetric Gram matrix times the unknown equals the data matrix projected onto the fixed side. The only thing that changes is which matrix plays which role. Encountering the normal equations again in regression should therefore feel familiar, not new.
6.4 Why the matrix form does not let us escape the discrete step¶
The resemblance is tempting: could we just apply the regression formula to k-means with fixed and skip the discrete of §4? No, for three reasons:
must be one-hot. The regression solution is real-valued; its columns do not sum to 1; its entries are not in .
Its is not the nearest-centroid rule. is the coordinate vector of in the generally non-orthogonal basis formed by the rows of , weighted by the inverse Gram matrix . This is a projection operation, not a nearest-neighbour operation. The two coincide only when the rows of are mutually orthogonal, which essentially never happens for real centroids.
We verify both facts experimentally on Iris in §8. There, the relaxed solution disagrees with the nearest-centroid rule on of the specimens.
So in k-means, the assignment half of the problem genuinely requires the discrete of §4. The matrix form is a useful compact restatement and a preview of regression, but it does not let us differentiate our way out of the combinatorial step.
7. Iris walkthrough (concrete shapes)¶
For Iris with features, specimens, clusters:
If the partition happened to be balanced (50 specimens per species), and , so each centroid is the column mean of its 50 assigned points. In general the partition produced by Lloyd is not balanced (the Iris run below gives sizes ), and is still diagonal but with the actual cluster sizes on the diagonal.
8. Python verification on Iris (procedural, no classes)¶
The script below verifies, in plain procedural style, that:
matches the per-cluster feature mean, to machine precision.
equals the element-wise double sum , exactly.
The gradient matches a finite-difference numerical gradient.
Procedural Lloyd’s algorithm (k-means++ initialisation) reaches the same SSE whether computed pointwise as or as .
The relaxed is not one-hot, and its disagrees with the nearest-centroid rule of §4 — the direct empirical check of §6.4.
"""
Verification of the k-means matrix identities on Iris.
Lecture notation: bold x_j for points (here as columns of X), non-bold
mu_i for centroids, SSE for the objective. Convention: columns = points,
so X is (d x n) = (features x samples).
"""
import numpy as np
from sklearn.datasets import load_iris
SEED = 42
# 0. Load Iris -----------------------------------------------------
iris = load_iris()
Xsk = iris.data.astype(float) # (150, d): rows = samples
X = Xsk.T # (d, 150): cols = samples
d, n = X.shape
k = 3
y_true = iris.target
# 1. One-hot Z from the true species labels -----------------------
Z = np.zeros((k, n))
Z[y_true, np.arange(n)] = 1.0
ZZT = Z @ Z.T
print("ZZ^T diagonal (cluster sizes):", np.diag(ZZT).astype(int))
# 2. Centroid formula M = X Z^T (Z Z^T)^{-1} vs per-cluster mean
M_formula = X @ Z.T @ np.linalg.inv(ZZT)
M_mean = np.array([Xsk[y_true == i].mean(axis=0) for i in range(k)]).T
print("max |M_formula - M_mean| =", np.max(np.abs(M_formula - M_mean)))
# 3. SSE: matrix form == element-wise double sum
sse_matrix = float(np.sum((X - M_formula @ Z) ** 2))
sse_elem = 0.0
for i in range(k):
for j in range(n):
if Z[i, j] == 1.0:
sse_elem += np.sum((X[:, j] - M_formula[:, i]) ** 2)
print("SSE ||X-MZ||_F^2 =", sse_matrix)
print("SSE element-wise =", sse_elem)
# 4. Relaxed Z = (M^T M)^{-1} M^T X -- NOT a valid one-hot assignment
MTM = M_formula.T @ M_formula
Z_relaxed = np.linalg.inv(MTM) @ M_formula.T @ X
print("Z_relaxed first column:", Z_relaxed[:, 0])
print("column sums (first 5):", Z_relaxed.sum(axis=0)[:5])
print("all entries binary? ", np.all((Z_relaxed == 0) | (Z_relaxed == 1)))
# 5. argmax(Z_relaxed) vs nearest-centroid rule (they disagree)
labels_relaxed = np.argmax(Z_relaxed, axis=0)
dist = np.linalg.norm(Xsk[:, None, :] - M_formula.T[None, :, :], axis=2)
labels_nearest = np.argmin(dist, axis=1)
print("nearest-centroid accuracy: ", np.mean(labels_nearest == y_true) * 100, "%")
print("argmax(Z_relaxed) accuracy: ", np.mean(labels_relaxed == y_true) * 100, "%")
print("agreement argmax(Z_relaxed) vs nearest-centroid:",
np.mean(labels_relaxed == labels_nearest) * 100, "%")
# 6. Gradient formula d SSE/dZ = -2 M^T X + 2 M^T M Z vs finite differences
rng = np.random.default_rng(0)
Z_test = rng.standard_normal((k, n))
def sse_func(Zm):
return float(np.sum((X - M_formula @ Zm) ** 2))
grad_formula = -2 * M_formula.T @ X + 2 * M_formula.T @ M_formula @ Z_test
grad_num = np.zeros_like(Z_test)
eps = 1e-6
for i in range(k):
for j in range(n):
Zp = Z_test.copy(); Zp[i, j] += eps
Zm = Z_test.copy(); Zm[i, j] -= eps
grad_num[i, j] = (sse_func(Zp) - sse_func(Zm)) / (2 * eps)
print("max |grad_formula - grad_numerical| =",
np.max(np.abs(grad_formula - grad_num)))
# 7. Procedural Lloyd's k-means with k-means++ init (no classes)
def kmeans_pp_init(Xsk, k, rng):
n = len(Xsk)
centroids = [Xsk[rng.integers(n)]]
for _ in range(1, k):
d2 = ((Xsk[:, None, :] - np.array(centroids)[None, :, :]) ** 2) \
.sum(axis=2).min(axis=1)
centroids.append(Xsk[rng.choice(n, p=d2 / d2.sum())])
return np.array(centroids, dtype=float)
def kmeans(Xsk, k, max_iter=300, tol=1e-9, rng=None):
if rng is None:
rng = np.random.default_rng(0)
centroids = kmeans_pp_init(Xsk, k, rng)
for it in range(max_iter):
distances = np.linalg.norm(
Xsk[:, None, :] - centroids[None, :, :], axis=2)
labels = np.argmin(distances, axis=1)
new_centroids = centroids.copy()
for j in range(k):
members = Xsk[labels == j]
if len(members) > 0:
new_centroids[j] = members.mean(axis=0)
shift = np.max(np.abs(new_centroids - centroids))
centroids = new_centroids
if shift < tol:
break
inertia = float(np.sum((Xsk - centroids[labels]) ** 2))
return centroids, labels, inertia, it + 1
centroids, labels, inertia, n_iter = kmeans(Xsk, k, rng=np.random.default_rng(SEED))
print("Lloyd iterations:", n_iter)
print("cluster sizes:", np.bincount(labels, minlength=k))
print("inertia (pointwise SSE):", inertia)
# 8. Re-derive the SAME SSE via the matrix form with Lloyd's labels
Z_lloyd = np.zeros((k, n))
Z_lloyd[labels, np.arange(n)] = 1.0
M_lloyd = X @ Z_lloyd.T @ np.linalg.inv(Z_lloyd @ Z_lloyd.T)
sse_matrix_lloyd = float(np.sum((X - M_lloyd @ Z_lloyd) ** 2))
print("SSE ||X-MZ||_F^2 (Lloyd labels):", sse_matrix_lloyd)
print("match:", np.isclose(sse_matrix_lloyd, inertia))Program output (verbatim, Iris, SEED=42)¶
ZZ^T diagonal (cluster sizes): [50 50 50]
max |M_formula - M_mean| = 2.22e-16
SSE ||X-MZ||_F^2 = 89.297400
SSE element-wise = 89.297400
Z_relaxed first column: [ 1.02136683 0.10245177 -0.09474523]
column sums (first 5): [1.02907337 0.99771851 0.94616567 0.92274539 1.00252589]
all entries binary? False
nearest-centroid accuracy: 92.66666666666667 %
argmax(Z_relaxed) accuracy: 76.0 %
agreement argmax(Z_relaxed) vs nearest-centroid: 70.0 %
max |grad_formula - grad_numerical| = 5.90e-06
Lloyd iterations: 3
cluster sizes: [50 61 39]
inertia (pointwise SSE): 78.855666
SSE ||X-MZ||_F^2 (Lloyd labels): 78.855666
match: TrueWhat the numbers tell us¶
| Check | Result |
|---|---|
| equals per-cluster mean | max error (machine precision) |
| equals the element-wise double sum | both give 89.297400 |
| Gradient formula vs finite differences | max error (forward-diff tolerance) |
| Lloyd pointwise SSE vs on converged labels | both give 78.855666 |
| Relaxed binary? | no (entries range from -2.66 to +3.45) |
| vs nearest-centroid rule | disagree on of Iris specimens |
The first four rows confirm that the matrix form is exactly equivalent to the element-wise derivation — the same content, packaged compactly. The last two rows confirm that the matrix form, tempting as it is, does not give us a shortcut around the discrete assignment step.
9. Summary¶
Starting from Lemma 2 in the lectures, we wrote the k-means objective as the within-cluster sum of squared errors,
and showed that two elementary differentiations — both done element-wise, with no matrices — produce the two update rules of Lloyd’s algorithm:
Centroid step. gives , the cluster mean.
Assignment step. The SSE is linear in each ; on the one-hot simplex its minimum is the vertex , the nearest centroid.
Alternating these two closed-form updates is Lloyd’s algorithm. The mixed continuous–discrete structure of the SSE forces this alternation on us: the objective is differentiable in the centroids but only linear in the discrete assignments, so no single differentiation can solve both halves at once.
The matrix form packages the same derivation compactly and previews the normal equations of linear regression:
k-means centroid step: ;
linear regression: .
These are the same algebraic shape — a symmetric Gram matrix times the unknown equals the data matrix projected onto the fixed side — with the roles of “fixed” and “unknown” swapped. When we meet the normal equations again in regression, the only new ingredient will be that is allowed to be any real matrix rather than a one-hot assignment; the derivation will be the one we have already done here.
The matrix form does not, however, let us differentiate our way out of the discrete assignment: the relaxed is real-valued, and its disagrees with the nearest-centroid rule on of Iris specimens (§8). The discrete of §4 is genuinely irreducible — and that, in one sentence, is why k-means is a two-step algorithm rather than a one-shot differentiation.