4.2 Centre objectives and Lloyd updates

Motivation

Assigning each observation to its nearest centre does not completely specify a clustering method. The remaining question is what to do with the assignment distances. Squaring and summing them gives k-means, summing their ordinary lengths gives a median objective, and taking their maximum gives k-center. These objectives agree about the nearest centre for fixed centres under the same Euclidean distance, but they generally disagree about the best locations of the centres.

The distinction becomes visible when a cluster contains an isolated observation far from the others. Its squared distance has a large effect on the k-means loss and pulls the mean toward it. An absolute-distance objective has a different minimizing representative. Restricting representatives to actual observations imposes another mathematical constraint. A centre update must minimize the objective that was defined, rather than being selected solely because it is called a centroid.

Lloyd's algorithm alternates between assignments and centre updates. Each step is easy once the other part is held fixed. Understanding its descent therefore begins with two small optimization problems, not with an assertion that the entire joint problem is easy. The termination argument also needs rules for ties and empty clusters, which are legitimate states of the iteration.

Definitions

Definition

Assignment loss and nearest-centre loss

Let $x_1,\ldots,x_n\in\mathbb R^d$ be observations, let $C=(c_1,\ldots,c_k)$ be a list of centres, and let $z_i\in\{1,\ldots,k\}$ be labels. Define

$$J(z,C)=\sum_{i=1}^n\|x_i-c_{z_i}\|_2^2,\qquad F(C)=\sum_{i=1}^n\min_{1\le j\le k}\|x_i-c_j\|_2^2 =\min_z J(z,C).$$

The labels specify a hard clustering. Some labels may have no observations, and centres in the list may coincide.

For fixed centres, choosing a nearest centre independently for every observation minimizes $J$. Tied nearest centres give the same contribution to the loss. For a fixed assignment, write $I_j=\{i:z_i=j\}$. When $I_j$ is nonempty, its mean is $\mu_j=|I_j|^{-1}\sum_{i\in I_j}x_i$.

The k-median objective uses $\sum_i\min_j\|x_i-c_j\|_2$ instead of squared distances. In one dimension its fixed-cluster minimizers are medians. In several dimensions, ordinary Euclidean distances require a geometric median. For Manhattan distance the coordinates separate and coordinatewise medians do minimize the corresponding objective. A medoid must additionally be one of the allowed observations and minimize the sum of distances to them.

On the line, moving a proposed median slightly to the right increases the distance to observations on its left and decreases the distance to those on its right. A minimizer balances these counts. With an even number of observations, every point between the two middle ordered values can minimize the sum. In higher-dimensional Euclidean distance, the square root couples the coordinates. For a proposed geometric median not coinciding with an observation, its gradient condition is $\sum_i(c-x_i)/\|c-x_i\|_2=0$. Coordinatewise medians instead exploit the separability of Manhattan distance; these are distinct mathematical justifications for different centre updates.

Theorem/proposition

Proposition

The mean minimizes squared Euclidean distance

For a nonempty cluster of $m$ observations with mean $\mu$ and any $c\in\mathbb R^d$,

$$\sum_{i=1}^m\|x_i-c\|_2^2 =\sum_{i=1}^m\|x_i-\mu\|_2^2+m\|c-\mu\|_2^2.$$

Thus the unique minimizing centre is $\mu$. An empty cluster contributes zero for every centre and has no mean to compute.

Proposition

A Lloyd iteration decreases the loss

Starting from nearest-centre labels, hold those labels fixed, replace every nonempty cluster centre by its mean, and keep an empty cluster's centre unchanged. Then reassign observations to nearest centres. Neither step increases $J$, and the resulting nearest-centre loss $F$ does not exceed its preceding value.

Proposition

Finite termination with a specified tie rule

Use exact arithmetic and the preceding mean/empty-cluster rule. During reassignment, retain an observation's old label whenever it is among the nearest centres; otherwise choose the smallest nearest index. Stop when the labels no longer change. Only finitely many label changes occur, and the final centres and labels form a Lloyd fixed point.

Proof sketch or proof idea

Write $x_i-c=(x_i-\mu)+(\mu-c)$ and expand the squared norm. The cross terms sum to zero because $\sum_i(x_i-\mu)=0$. This proves the mean identity. Its second term is strictly positive for $c\ne\mu$, giving uniqueness. The calculation uses the Euclidean inner product; replacing it by an arbitrary distance does not preserve the identity.

The mean is an average of the observations with nonnegative equal weights, so it lies in their convex hull, although it need not be an observed point. The multiplier $m$ in the decomposition also matters: moving a large cluster's centre a given distance from its mean costs more than making the same displacement in a small cluster. The full objective weights individual observations equally, not clusters equally. For the same reason, the mean of several cluster means should use their cluster sizes as weights to recover the overall sample mean. Equal weighting is justified by equal cluster sizes, but is not a general identity for unequal sizes.

The mean step minimizes each nonempty cluster's contribution to $J$. The assignment step then minimizes every observation's contribution with those centres fixed. If an empty cluster retains its centre, its zero contribution causes no difficulty. Since the starting labels are nearest-centre labels, $J(z,C)=F(C)$ at the start of the round. These two inequalities establish descent, but non-increasing values alone do not yet establish finite termination.

For the stronger conclusion, let $W(z)$ be the loss after setting all nonempty centres to the means determined by $z$. Empty centres do not enter that value. If reassignment changes any label under the specified rule, the old label was not nearest, so that observation's squared distance strictly decreases. If $z'$ is the new assignment and $C'$ the mean-updated centres,

$$W(z')\le J(z',C')<J(z,C')=W(z).$$

There are at most $k^n$ labelled assignments, and hence finitely many possible values of $W$. Strict decrease at every label change prevents an assignment from recurring. Eventually labels stop changing. The nonempty centres are already their means, and the empty centres were retained, so another round leaves the state unchanged. This proves a fixed point, without identifying it as the global minimum of $F$.

This algorithm uses a list of $k$ available centres; it does not assert that all $k$ clusters stay nonempty. Repeated centres or an unfavourable initial placement can leave a label unused. Requiring exactly $k$ nonempty clusters would add a constraint to the optimization problem. Moving an observation to an empty label simply to satisfy that constraint can increase the held assignment loss, so it is not part of the descent proof above. Keeping the empty centre unchanged is a complete specified rule for the version being analyzed here.

Worked examples

Worked example

Example 1: Trace mean updates and reassignment separately

Take observations $0,2,3,9,10$ on the line and initial centres $(0,3)$. The nearest labels put $0$ in the first cluster and the other four points in the second; the initial loss is $86$.

The first mean update gives centres $(0,6)$. For the old labels the loss is $50$. Reassignment moves $2$ to the first cluster, while $3$ retains its old label because both centres are distance $3$ away. The nearest-centre loss is now $38$.

The next means are $(1,22/3)$. Their old-assignment loss is $92/3$; reassignment moves $3$ to the first cluster and lowers the loss to $143/9$. The final means and loss are

$$C=(5/3,19/2),\qquad F(C)=\left(25/9+1/9+16/9\right)+\left(1/4+1/4\right) =31/6.$$

The nearest labels now remain unchanged: $0,2,3$ form one cluster and $9,10$ the other. Distinguishing $J$ for held labels from $F$ after reassignment explains why the intermediate values $50$ and $38$ refer to the same centres but different assignments.

Worked example

Example 2: A larger-k local run can return a worse loss

Use $X=\{0,1,8,9,20,21\}$. With three centres $(0,1,29/2)$, the first two clusters are singletons and the final cluster is $\{8,9,20,21\}$. Every centre is its cluster mean. Each observation strictly prefers its assigned centre, so this is a Lloyd fixed point. Its loss is

$$F(0,1,29/2)=\frac{169+121+121+169}{4}=145.$$

For comparison, two centres $(9/2,41/2)$ produce clusters $\{0,1,8,9\}$ and $\{20,21\}$ and loss $65+1/2=131/2$. Thus this converged three-centre result is worse than a feasible two-centre result. A different three-centre initialization at $(1/2,17/2,41/2)$ gives three nearby pairs and loss $3/2$.

The example demonstrates both the role of initialization and the meaning of restarts. Repeating a run and keeping its lowest loss can improve the best observed result, while a particular fixed point is not an optimality certificate. Comparisons across independent local runs also need not be monotone in $k$.

Worked example

Example 3: Means, medians, and medoids answer different questions

For one cluster with observations $0,2,9$, the squared-distance minimizer is the mean $11/3$, with squared loss $134/3$. Centre $2$ has squared loss $53$. For the sum of ordinary absolute distances, however, the median $2$ gives loss $9$, while the mean gives $32/3$. Restricting the centre to an observed point gives the medoid $2$, whose distance sum is again $9$.

In the plane, consider $(0,0)$, $(2,0)$, and $(0,2)$. Their coordinatewise median is $(0,0)$ and has Euclidean-distance sum $4$. The feasible point $(1/2,1/2)$ gives

$$\frac1{\sqrt2}+\sqrt{10}<4.$$

Thus the coordinatewise median is not a Euclidean geometric median for this dataset. Coordinatewise minimization instead solves the Manhattan-distance problem, where the coordinate absolute differences add separately.

A reproducible Lloyd calculation

The code follows Example 1. It prints $F$ after reassignment, rather than the loss for labels held over from the preceding round. Empty centres are left in place, and an old label is preserved on an exact distance tie.

import numpy as np

X = np.array([0.0, 2.0, 3.0, 9.0, 10.0])[:, None]
C = np.array([[0.0], [3.0]])
rows = np.arange(len(X))
def distances2():
    return np.sum((X[:, None, :] - C[None, :, :]) ** 2, axis=2)
D = distances2()
labels = np.argmin(D, axis=1)
print(f"initial cost={D[rows, labels].sum():.6f}")
round_number = 0
while True:
    round_number += 1
    for j in range(len(C)):
        members = X[labels == j]
        if len(members):
            C[j] = members.mean(axis=0)
    D = distances2()
    nearest = np.argmin(D, axis=1)
    new_labels = np.where(D[rows, labels] <= D[rows, nearest], labels, nearest)
    cost = float(D[rows, new_labels].sum())
    centre_text = ", ".join(f"{centre[0]:.6f}" for centre in C)
    print(f"{round_number}: centres=({centre_text}), cost={cost:.6f}")
    if np.array_equal(new_labels, labels):
        break
    labels = new_labels
print("labels:", labels.tolist())

initial cost=86.000000
1: centres=(0.000000, 6.000000), cost=38.000000
2: centres=(1.000000, 7.333333), cost=15.888889
3: centres=(1.666667, 9.500000), cost=5.166667
labels: [0, 0, 0, 1, 1]

Initialization and the elbow curve

An initialization chooses a basin for the alternating updates. Farthest-first selection spreads centres by always taking a current farthest observation. The k-means++ initialization instead selects a first observation uniformly at random and then samples a new one with probability proportional to its squared distance from the chosen centres. For a positive sum of squared distances, those probabilities are

$$p_i=\frac{D_i^2}{\sum_{r=1}^nD_r^2},\qquad D_i=\min_{c\in C}\|x_i-c\|_2.$$

When every $D_i$ is zero, every input is already represented by a chosen centre. Otherwise the sampling favors currently poorly represented observations, but does not simply select the single farthest one. Lloyd updates follow after the initialization.

Let $F_k^*$ denote the globally smallest loss using at most $k$ centres. Appending a centre cannot increase any observation's nearest distance, so $F_{k+1}^*\le F_k^*$. With one centre at each observation the loss is zero. An elbow plot examines where extra centres give a substantially smaller improvement. The feasible-set argument concerns global optima; Example 2 shows why losses from arbitrary local runs need not inherit that ordering. An elbow is a modelling aid for balancing simplicity and fit, not a theorem that a unique number of clusters can be recovered from every dataset.

Common mistakes

Common mistake

Changing the update while keeping the old objective

The arithmetic mean minimizes squared Euclidean distances. A one-dimensional absolute-distance objective uses medians; a multidimensional Euclidean absolute-distance objective uses a geometric median. A medoid must minimize the distance sum over allowed observed representatives, not just select an observation that looks close to the arithmetic mean.

The loss can remain unchanged at a tie, so non-increase and finitely many assignments alone do not exclude cycles of equal-cost states. The retained old-label rule makes every actual label change a strict improvement. Likewise, keeping an empty centre is an explicit valid operation because its fixed-assignment contribution is zero; taking the mean of an empty set is not a defined replacement.

Summary

Specify the distance, the aggregation of assignment costs, and the allowed centre locations before choosing an update. Lloyd's mean and nearest-centre steps decrease the squared Euclidean objective. With explicit tie and empty cluster rules the assignments eventually stabilize, although their fixed point can have a large loss. Initialization, restarts, and elbow comparisons should be interpreted relative to that distinction.

For repeated runs at one fixed $k$, retain the smallest objective value actually obtained. That retained value cannot increase as further runs are added, because the earlier candidates remain available. This is a statement about the best observed result, rather than the quality of each random initialization. Cluster index numbers also have no intrinsic meaning: permuting labels and the corresponding centres leaves the loss unchanged. Comparing two runs by their objectives and represented groups avoids mistaking different index names for a difference in clustering quality.

Exercises

Checkpoint

Exercise 1: For one cluster containing $1$, $2$, and $6$, find the mean, the minimum squared loss, and the extra loss from choosing centre $2$.

Use the squared-distance decomposition rather than differentiating again.

Checkpoint

Exercise 2: For observations $0$, $2$, $9$, and $11$ on the line, find all centres minimizing the absolute-distance sum. Which observed points are medoids?

Every point between the two middle observations is a median.

Checkpoint

Exercise 3: Let observations be $0$, $4$, $5$ and current centres be $(0,4,100)$. Use nearest assignments and the stated mean/empty-cluster rule. Find the updated centres and loss.

The third cluster is empty; its centre is retained.

Checkpoint

Exercise 4: Two observations both equal $0$, and both centres equal $0$. How could arbitrary tie changes keep loss zero while changing labels? What does the stated tie rule do?

Separate a fixed objective value from a fixed labelled state.

Solutions

Solution · Exercise 1 solution

The mean is $3$ and the minimum squared loss is $4+1+9=14$. At centre $2$ the loss is $1+0+16=17$; the extra loss is $3(2-3)^2=3$, matching the difference.

Solution · Exercise 2 solution

All real centres in $[2,9]$ minimize the absolute-distance sum, with value $18$. Restricting the centre to observed points leaves $2$ and $9$ as medoids, each attaining that value.

Solution · Exercise 3 solution

The clusters are $\{0\}$, $\{4,5\}$, and the empty set. Their updated centres are $(0,9/2,100)$. Reassignment leaves them the same, and the loss is $(4-9/2)^2+(5-9/2)^2=1/2$.

Solution · Exercise 4 solution

One could keep swapping labels $(1,2)$ and $(2,1)$: both assigned means remain zero and every distance is zero. This changes the labelled state without improving the objective. Retaining each old label when it is tied prevents these swaps, so the state stops changing.

Related notes

Voronoi cells and k-center derives nearest-site geometry and a maximum-distance objective. Model validation and ridge regression explains the separate task of comparing fitted models. The course reading list collects further reading on these clustering objectives.