Why Each K-Means Iteration Cannot Increase WCSS

Why Monotonicity Matters

K-means is often described as a sequence of two operations: assign each observation to a center, then replace each center by the mean of the observations assigned to it. The within-cluster sum of squares (WCSS) gives a single quantity with which to assess these operations. The key guarantee is modest but useful: each operation, performed as specified, cannot increase WCSS. It does not say that the operations find the best possible clustering.

The argument assumes a fixed data set and a fixed number of clusters. It is an optimization argument, not a probability model, so no distributional assumptions, interest rates, or mortality assumptions are involved. Distances are ordinary squared Euclidean distances, and all clusters are assumed nonempty at the update step.

Definition: Let $x_1,\ldots,x_n$ be fixed observations in $p$-dimensional Euclidean space. For an assignment $C_1,\ldots,C_K$ of the observations to $K$ nonempty clusters and centers $\mu_1,\ldots,\mu_K$, define $$ \operatorname{WCSS}(C,\mu)=\sum_{k=1}^{K}\sum_{i:x_i\in C_k}\|x_i-\mu_k\|^2. $$ Here $\|x_i-\mu_k\|^2$ is the sum of the squared coordinate differences. For fixed assignments, the cluster mean is $\bar{x}_k=|C_k|^{-1}\sum_{i:x_i\in C_k}x_i$.

There are two different choices in this objective: which cluster receives each observation, and where each cluster center is placed. The assignment step changes the first while holding centers fixed. The update step changes centers while holding assignments fixed. Treating these steps separately is what makes the monotonicity proof precise.

The Assignment Step Cannot Increase WCSS

Suppose the current centers are $\mu_1,\ldots,\mu_K$, and the current assignment has WCSS $W_0$. In the assignment step, each observation is assigned to a nearest center. For observation $x_i$, its contribution after assignment is $\min_k\|x_i-\mu_k\|^2$. Its previous contribution was the squared distance to the center of its previous cluster, which cannot be smaller than this minimum. Therefore, summing the pointwise inequalities gives the result.

\sum_{i=1}^{n}\min_{1\leq k\leq K}\|x_i-\mu_k\|^2 \leq \sum_{k=1}^{K}\sum_{i:x_i\in C_k}\|x_i-\mu_k\|^2 =W_0.

The inequality also covers ties: assigning a tied observation to either nearest center gives the same distance for that observation. The assignment step leaves WCSS unchanged exactly when the total contribution does not fall. In particular, if every observation remains assigned to its previous center, the assignment-step WCSS is unchanged. Conversely, an assignment can change without reducing WCSS if the changed choices have equal distances.

Worked Example: Comparing the Two Assignment Costs

Consider the one-dimensional observations $0,2,7,9$, with two fixed centers at $0$ and $10$. Before reassignment, suppose the clusters are $C_1=\{0,2,7\}$ and $C_2=\{9\}$. Find the WCSS before and after the assignment step, and verify that reassignment cannot increase it.

Method. First calculate the current objective using the given memberships and fixed centers. Then assign each observation to its nearer center and recalculate.

Before reassignment, the contributions from $0,2,7$ to center $0$ are $0^2,2^2,7^2$, and the contribution from $9$ to center $10$ is $(9-10)^2$. Thus $W_0=0+4+49+1=54$.

For the assignment step, compare squared distances to the two centers. Observation $0$ goes to $0$, since $0<100$; observation $2$ goes to $0$, since $4<64$; observation $7$ goes to $10$, since $9<49$; and observation $9$ goes to $10$, since $1<81$. The new clusters are $\{0,2\}$ and $\{7,9\}$, and $W_1=0^2+2^2+(7-10)^2+(9-10)^2=0+4+9+1=14$.

The assignment step reduced WCSS from $54$ to $14$, so $W_1\leq W_0$. This calculation avoids the common mistake of calculating the first objective using the new memberships: $W_0$ must use the old memberships and the same fixed centers.

The Update Step Cannot Increase WCSS

Now hold a cluster’s membership fixed and consider any proposed center $\mu$. Write its mean as $\bar{x}$ and its size as $m$. The sum of squared distances to $\mu$ separates into the sum of squared distances to the mean plus a nonnegative penalty for placing the center away from the mean. This identity explains why the arithmetic mean minimizes the sum of squared Euclidean distances.

\sum_{i=1}^{m}\|x_i-\mu\|^2 = \sum_{i=1}^{m}\|x_i-\bar{x}\|^2 + m\|\mu-\bar{x}\|^2.

To derive the identity, write $x_i-\mu=(x_i-\bar{x})+(\bar{x}-\mu)$, expand each squared norm, and sum. The cross term is zero because $\sum_i(x_i-\bar{x})=0$:

\begin{aligned} \sum_{i=1}^{m}\|x_i-\mu\|^2 &=\sum_{i=1}^{m}\|x_i-\bar{x}\|^2 +2\left(\sum_{i=1}^{m}(x_i-\bar{x})\right)^\mathsf{T}(\bar{x}-\mu) +m\|\bar{x}-\mu\|^2\\ &=\sum_{i=1}^{m}\|x_i-\bar{x}\|^2+m\|\bar{x}-\mu\|^2. \end{aligned}

The last term is nonnegative and is zero exactly when $\mu=\bar{x}$. Applying the identity separately to every cluster proves that replacing each old center by its cluster mean cannot increase the total WCSS. For nonempty clusters, the update step leaves WCSS unchanged exactly when every center was already the mean of its assigned observations.

Worked Example: Updating Centers After Reassignment

Continue with the observations $0,2,7,9$ and the assigned clusters $\{0,2\}$ and $\{7,9\}$. Their current centers are $0$ and $10$. Calculate the mean-update step and verify its effect on WCSS.

Method. Keep the new memberships fixed, calculate each cluster mean, and compare the objective before and after replacing the centers. The assignment-step objective was $W_1=14$.

For the first cluster, the mean is $(0+2)/2=1$. Its WCSS at the old center $0$ was $0^2+2^2=4$; at the mean it is $(0-1)^2+(2-1)^2=1+1=2$.

For the second cluster, the mean is $(7+9)/2=8$. Its WCSS at the old center $10$ was $(7-10)^2+(9-10)^2=9+1=10$; at the mean it is $(7-8)^2+(9-8)^2=1+1=2$. The updated total is $W_2=2+2=4$. Thus $W_2=4\leq W_1=14$. The update reduces WCSS by $10$, as also shown by the mean-identity penalties $2(0-1)^2=2$ and $2(10-8)^2=8$, whose sum is $10$.

The check is $14-10=4$, matching the directly calculated updated WCSS. The common mistake avoided here is to update a center using observations from the old memberships rather than the clusters produced by the assignment step.

Combining the Steps and Stating Equality Correctly

Let $W_0$ be WCSS before an iteration, $W_1$ be WCSS immediately after assignment, and $W_2$ be WCSS after the center update. The two separate results combine directly:

W_2\leq W_1\leq W_0.

For the complete iteration to leave WCSS unchanged, both inequalities must be equalities: the assignment step must not reduce WCSS, and the update step must not reduce WCSS. Unchanged assignments are sufficient for equality in the assignment step, but do not by themselves imply equality after the update. Likewise, centers already equal to the means of the old clusters do not prevent the assignment step from lowering WCSS.

Theorem: With fixed observations, a fixed number of nonempty clusters, nearest-center assignment, and updates to the assigned-cluster means, each step of a Lloyd iteration leaves WCSS unchanged or reduces it. The complete iteration leaves WCSS unchanged if and only if neither step reduces it. In particular, unchanged assignments together with centers already at the means of the new clusters are sufficient for equality over the complete iteration.

Worked Example: Why One Equality Condition Is Not Enough

Two claims are sometimes used incorrectly: “unchanged assignments imply equality for the whole iteration,” and “centers at the old cluster means imply equality for the whole iteration.” Check both claims with explicit calculations.

First claim: unchanged assignments. Take observations $0,2,10$, with clusters $\{0,2\}$ and $\{10\}$, and centers $0$ and $10$. The assignments are already nearest-center assignments: $0$ and $2$ are nearer $0$, and $10$ is at its center. The WCSS is $0+4+0=4$, so assignment leaves it at $4$. The cluster means are $1$ and $10$. Updating gives WCSS $(0-1)^2+(2-1)^2+0=1+1=2$. Assignments did not change, but the complete iteration reduced WCSS from $4$ to $2$.

Second claim: old centers at their cluster means. Take observations $0,2,3,10$, with old clusters $\{0,10\}$ and $\{2,3\}$. Their means, and hence their centers, are $5$ and $2.5$. The old WCSS is $(0-5)^2+(10-5)^2+(2-2.5)^2+(3-2.5)^2=25+25+0.25+0.25=50.5$.

With these fixed centers, $0$ is closer to $2.5$ than $5$, while $10$ is closer to $5$ than $2.5$; $2$ and $3$ are closer to $2.5$. The assignment-step WCSS is therefore $(0-2.5)^2+(2-2.5)^2+(3-2.5)^2+(10-5)^2=6.25+0.25+0.25+25=31.75$. The assignment step strictly reduces WCSS even though the centers were means of the old clusters. This avoids treating either condition alone as a guarantee of equality for the full iteration.

Monotonicity Does Not Guarantee a Global Minimum

A decreasing objective is not the same as a globally optimal objective. The assignment step optimizes memberships with the centers held fixed; the update step optimizes centers with memberships held fixed. Neither step, by itself, searches all possible combinations of assignments and centers. Together they give a nonincreasing sequence of WCSS values, but a clustering can be stable under both steps and still have higher WCSS than another feasible clustering.

The following example verifies this distinction without relying on an algorithm’s starting procedure. Repeated observations are allowed: they represent distinct observations with the same measured value.

Worked Example: A Stable Clustering That Is Not Globally Best

Consider 12 one-dimensional observations: one observation at $0$, ten observations at $10$, and one observation at $11$. Use $K=2$. Show that a clustering can be unchanged by both Lloyd steps while another feasible clustering has lower WCSS.

Method. First verify stability of the proposed clustering by checking nearest-center assignments and the mean update. Then calculate WCSS for a different feasible clustering. A strictly smaller feasible value is enough to prove the stable clustering is not a global minimum.

Consider the clusters $C_1=\{0,\text{ the ten observations at }10\}$ and $C_2=\{11\}$. Their means are $100/11$ and $11$. Use these as centers. Each observation at $10$ is closer to $100/11$ than to $11$, because its distances are $10/11$ and $1$. The observation at $0$ is also closer to $100/11$, and $11$ is at the second center. Thus the assignment step returns the same clusters.

The first cluster’s WCSS is $(0-100/11)^2+10(10-100/11)^2=10000/121+10(100/121)=11000/121$. The singleton cluster contributes zero. Since the centers are already the cluster means, the update step also leaves WCSS unchanged. The stable value is $11000/121$, approximately $90.9091$.

Now consider the alternative clusters consisting of $\{0\}$ and the ten observations at $10$ together with the observation at $11$. Their means are $0$ and $111/11$. Their WCSS is $0+10(10-111/11)^2+(11-111/11)^2=10(1/121)+100/121=110/121$, approximately $0.9091$.

Since $110/121<11000/121$, the stable clustering is not a global minimum. This comparison does not require identifying the global minimum; a single feasible solution with lower WCSS establishes that the stable solution is suboptimal. The common mistake avoided is concluding “globally optimal” merely because neither Lloyd step changes the clustering or its centers.

Practical Conditions and Common Traps

The proof depends on the specified objective and operations. In particular, the update to arithmetic means minimizes a sum of squared Euclidean distances; a different distance measure or a different update rule need not satisfy the same proof. The nearest-center step must also use the same squared Euclidean distance as the WCSS being evaluated.

The assumption of nonempty clusters matters because a mean cannot be calculated for an empty cluster. If an assignment produces an empty cluster, the ordinary mean update for that cluster is undefined, so the two-step proof as stated does not apply until an empty-cluster handling rule is specified. In calculations, also distinguish the objective before assignment, after assignment, and after update. Each uses the memberships and centers in effect at that particular stage.

Hold centers fixed.
Each nearest-center distance is no larger than the distance to the previous center, so assignment cannot increase WCSS.

Hold memberships fixed.
The mean-update identity shows that each mean minimizes its cluster’s squared-distance contribution, so updating cannot increase WCSS.

Interpret the result narrowly.
The iteration is nonincreasing, but a stable result can still have greater WCSS than another feasible clustering.

Key takeaway: Lloyd’s assignment and update steps each optimize one part of WCSS while holding the other part fixed. This guarantees $W_2\leq W_1\leq W_0$, not that the final clustering is globally optimal.

Check Your Understanding

For each problem, distinguish the WCSS before assignment, after assignment, and after update when the question asks for them.

The observations are $1,2,8,9$, and the fixed centers are $1$ and $10$. Assign each observation to its nearest center and calculate the assignment-step WCSS. (Answer: Clusters $\{1,2\}$ and $\{8,9\}$; WCSS $=6$.)
The observations are $0,2,9$, with clusters $\{0,2\}$ and $\{9\}$ and centers $0$ and $10$. Verify whether assignment changes the clusters, then calculate WCSS after the mean update. (Answer: Assignment is unchanged; WCSS after update is $2$.)
For fixed clusters $\{1,5,9\}$ and $\{10,14\}$, find the updated centers and WCSS. (Answer: Centers $5$ and $12$; WCSS $=40$.)
There is one observation at $0$, ten at $10$, and one at $11$, with $K=2$. Compare the stable clustering $\{0,\text{ ten at }10\},\{11\}$ with the alternative $\{0\},\{\text{ten at }10,11\}$. Give both WCSS values and state what they imply. (Answer: Stable value $11000/121$; alternative value $110/121$; the stable clustering is not globally optimal.)
State the two conditions required for equality over a complete Lloyd iteration. Is unchanged assignment alone sufficient? (Answer: Neither the assignment step nor the update step reduces WCSS; unchanged assignment alone is not sufficient.)

What You'll Learn