Lloyd's Algorithm for K-Means

From the K-Means Objective to an Algorithm

The K-means objective describes a clustering by the sum of squared distances from each observation to its assigned cluster center. But minimizing this objective jointly over all possible assignments and centers is difficult: changing a center can change which observations belong to its cluster, and changing assignments changes the best centers. Lloyd’s algorithm handles this coupled problem by alternating between two simpler optimizations. First it assigns each observation to its nearest current center; then it replaces each center with the mean of the observations assigned to it.

For genomic profiles, an observation might be a sample represented by a vector of measured or transformed features. The distance calculation is meaningful only relative to the chosen representation and scale. In particular, Euclidean distance can be dominated by features with larger numerical scales, so the preprocessing choices discussed in the earlier material on centering and scaling matter before this algorithm is applied.

Definition: Let $\mathbf{x}_1,\ldots,\mathbf{x}_n$ be $n$ observations in $d$-dimensional Euclidean space, and choose a fixed number $K$ of clusters. Let $z_i\in\{1,\ldots,K\}$ denote the cluster assigned to observation $i$, and let $\mathbf{c}_k$ be the center of cluster $k$. The within-cluster sum of squares is $$ W(\mathbf{z},\mathbf{c})=\sum_{i=1}^{n}\|\mathbf{x}_i-\mathbf{c}_{z_i}\|^2. $$ For a nonempty cluster $C_k=\{i:z_i=k\}$, its centroid is $\bar{\mathbf{x}}_k=|C_k|^{-1}\sum_{i\in C_k}\mathbf{x}_i$.

The norm is Euclidean, so $\|\mathbf{x}_i-\mathbf{c}_k\|^2$ is the sum of squared coordinate differences. The algorithm below is defined for a fixed $K$, with a specified set of initial centers. Its basic monotonicity argument assumes each cluster has at least one observation when its center is updated. Ties for nearest center need a consistent rule, such as assigning to the lowest-index tied center.

Why the Two Steps Reduce the Objective

With centers fixed, each observation contributes one term to $W$, and its assignment does not affect any other observation’s term. Therefore the best assignment for observation $i$ is a center minimizing its squared distance. With assignments fixed, the terms separate by cluster. The best center for each nonempty cluster is its arithmetic mean. The second claim follows from an identity that also quantifies the improvement.

Theorem: For fixed centers, assigning each observation to a nearest center cannot increase $W$. For fixed assignments with nonempty clusters, setting each center to its cluster mean cannot increase $W$. Consequently, a complete assignment-and-update iteration cannot increase the within-cluster sum of squares.

To justify the centroid step, consider one cluster with $m$ observations and mean $\bar{\mathbf{x}}$. For any candidate center $\mathbf{c}$, write $\mathbf{x}_i-\mathbf{c}=(\mathbf{x}_i-\bar{\mathbf{x}})+(\bar{\mathbf{x}}-\mathbf{c})$, square the norm, and sum. The cross term vanishes because $\sum_i(\mathbf{x}_i-\bar{\mathbf{x}})=\mathbf{0}$. Thus

\sum_{i=1}^{m}\|\mathbf{x}_i-\mathbf{c}\|^2 = \sum_{i=1}^{m}\|\mathbf{x}_i-\bar{\mathbf{x}}\|^2 + m\|\bar{\mathbf{x}}-\mathbf{c}\|^2.

The second term is nonnegative and equals zero at $\mathbf{c}=\bar{\mathbf{x}}$, proving that the mean minimizes the sum of squared distances. This is a global minimum for that cluster’s center when the assignments are held fixed.

More explicitly, let $\mathbf{c}^{(t)}$ be the centers before an assignment step, let $\mathbf{z}^{(t+1)}$ be the resulting nearest-center assignments, and let $\mathbf{c}^{(t+1)}$ be their updated means. The assignment property gives the first inequality below, and the centroid identity gives the second:

W(\mathbf{z}^{(t+1)},\mathbf{c}^{(t)}) \leq W(\mathbf{z}^{(t)},\mathbf{c}^{(t)}), \qquad W(\mathbf{z}^{(t+1)},\mathbf{c}^{(t+1)}) \leq W(\mathbf{z}^{(t+1)},\mathbf{c}^{(t)}).

Together these show non-increase over a full iteration. They do not show that the algorithm finds the globally smallest possible value of $W$. Each step optimizes one part while holding the other part fixed.

Assign observations.
For every $i$, choose $z_i$ to minimize $\|\mathbf{x}_i-\mathbf{c}_k\|^2$ over $k=1,\ldots,K$, resolving ties consistently.

Update centers.
For each nonempty cluster $C_k$, set $\mathbf{c}_k=|C_k|^{-1}\sum_{i\in C_k}\mathbf{x}_i$.

Check for stopping.
Stop when assignments no longer change, or when an explicitly chosen numerical stopping rule is met; otherwise repeat the assignment and update steps.

Worked Iterations

Worked Example: Assigning Four Profiles to Two Fixed Centers

Suppose four hypothetical two-feature profiles are $(0,0),(2,0),(5,0),(7,0)$, and the current centers are $\mathbf{c}_1=(1,0)$ and $\mathbf{c}_2=(6,0)$. Compute the nearest-center assignments and the objective after assignment.

For $(0,0)$, the squared distances are $1$ to $\mathbf{c}_1$ and $36$ to $\mathbf{c}_2$, so assign it to cluster 1. For $(2,0)$, they are $1$ and $16$, so assign it to cluster 1. For $(5,0)$, they are $16$ and $1$, so assign it to cluster 2. For $(7,0)$, they are $36$ and $1$, so assign it to cluster 2. There are no ties, and every observation is assigned to its nearer center.

The resulting objective, using these fixed centers, is $W=1+1+1+1=4$ squared feature units. Since each observation was given its smaller of the two available squared distances, no other assignment with these same centers can yield a smaller objective.

Worked Example: Updating One Cluster Center

Consider a hypothetical one-dimensional cluster with observations $0,2,4$. Its current center is $1$. Find the updated center and compare the cluster’s contributions to the objective before and after the update.

The cluster mean is $$ \bar{x}=\frac{0+2+4}{3}=2. $$ With the old center, the sum of squared distances is $(0-1)^2+(2-1)^2+(4-1)^2=1+1+9=11$. With the mean as center, it is $(0-2)^2+(2-2)^2+(4-2)^2=4+0+4=8$. The update reduces this cluster’s contribution by $11-8=3$ squared units.

The identity above verifies the same reduction: $m(\bar{x}-c)^2=3(2-1)^2=3$. This calculation concerns the center update with the three assignments held fixed; it does not imply that those assignments would remain unchanged if a later assignment step were performed.

Worked Example: A Complete Lloyd Iteration

Take the hypothetical one-dimensional observations $0,2,3,8,9$, with $K=2$ and initial centers $c_1=1$ and $c_2=8$. Calculate the assignment step, update the centers, and compare the objective before and after the full iteration.

The squared distances to centers 1 and 8, respectively, are: for observation 0, $1$ and $64$; for 2, $1$ and $36$; for 3, $4$ and $25$; for 8, $49$ and $0$; and for 9, $64$ and $1$. Thus the assignment step gives $C_1=\{0,2,3\}$ and $C_2=\{8,9\}$. The objective after assignment, evaluated at the old centers, is $1+1+4+0+1=7$ squared units.

The updated centers are the cluster means: $$ c_1=\frac{0+2+3}{3}=\frac{5}{3}, \qquad c_2=\frac{8+9}{2}=\frac{17}{2}=8.5. $$

At these updated centers, the first cluster contributes $(0-5/3)^2+(2-5/3)^2+(3-5/3)^2=25/9+1/9+16/9=42/9=14/3$. The second contributes $(8-8.5)^2+(9-8.5)^2=0.25+0.25=0.5$. The updated objective is $14/3+0.5=31/6\approx5.167$ squared units, which is less than 7. The assignment step cannot increase the objective, and the centroid step reduces it here.

If the algorithm assigns again using centers $5/3$ and $8.5$, the clusters remain the same: observation 3 is closer to $5/3$ than to $8.5$, and observations 8 and 9 are closer to $8.5$. The next mean update therefore leaves both centers unchanged. This is a stable assignment for these data and starting centers, not evidence that no other clustering has a smaller objective.

Stopping, Diagnostics, and Limitations

In exact arithmetic, the objective is bounded below by zero and does not increase from one complete iteration to the next. This supports stopping when assignments are unchanged: if the clusters do not change, their means do not change either. Software may instead stop when the objective’s decrease is smaller than a tolerance or when the center movement is small. Such numerical rules should specify their tolerance and should not be confused with a proof of global optimality.

There are only finitely many possible assignments of $n$ observations to $K$ labeled clusters. If every change of assignment strictly reduces the objective and clusters remain nonempty, the algorithm cannot revisit an earlier assignment and must eventually stop. Ties can allow equal-objective alternatives, however, so a deterministic tie rule and a practical iteration limit are useful. In floating-point calculations, a small reported change can also reflect rounding rather than meaningful progress.

An assignment step can leave a cluster empty. Its mean is then undefined, so the stated centroid update cannot be applied to that cluster. An implementation must specify a policy. Keeping the old center for an empty cluster leaves that center’s contribution absent from the current objective and permits the nonempty-cluster mean updates to retain their non-increase property. Reinitializing an empty center is a different operation; it may alter future assignments and does not automatically inherit the two-step monotonicity proof. The chosen policy should be reported when it affects the result.

Lloyd’s algorithm is an alternating optimization procedure, not an exhaustive search over all partitions. Its result can depend on the initial centers, and it can stop at a solution that is only locally optimal with respect to these two update steps. How to choose initial centers and how to assess different resulting solutions are separate questions. Likewise, K-means is not a general model for every type of genomic profile: its squared-Euclidean objective favors compact clusters around means and can be sensitive to outliers, feature scaling, and the chosen representation.

Useful diagnostics include checking that each observation has been assigned exactly once, confirming that each updated center equals the mean of its assigned observations, and recomputing $W$ after each phase to verify it has not increased. Also inspect cluster sizes and the distance scale in the feature representation. A zero-sized cluster, a sudden objective increase after an update, or centers that do not match the assigned means indicates either an implementation issue or a special empty-cluster policy that needs to be understood.

Approach	What is optimized directly	Key consequence
Lloyd’s alternating steps	Assignments with centers fixed, then centers with assignments fixed	Each step is simple and non-increasing, but the final result need not be globally optimal
Joint global minimization	All assignments and centers together	Defines the global minimum of the K-means objective, but requires considering a combinatorial set of possible assignments

Key takeaway: Nearest-center assignment minimizes the objective one observation at a time when centers are fixed; replacing each nonempty cluster’s center by its mean minimizes that cluster’s squared distances when assignments are fixed. These facts guarantee non-increase, not a globally optimal clustering.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions.

With centers fixed, why can the assignment of one observation be chosen independently of the assignments of the other observations?
A cluster contains observations $1,3,5$, and its current center is $2$. Calculate its mean and its sum of squared distances before and after the centroid update.
Does a non-increasing objective prove that Lloyd’s algorithm has found the global minimum? Explain.
What issue arises if a cluster is empty at the update step, and why does reinitializing its center require care?

Solutions. (1) With the centers fixed, the objective is a sum of separate terms $\|\mathbf{x}_i-\mathbf{c}_{z_i}\|^2$. Changing $z_i$ changes only observation $i$'s term, so choosing its nearest center minimizes that term without affecting the others. (2) The mean is $(1+3+5)/3=3$. At the old center 2, the sum is $(1-2)^2+(3-2)^2+(5-2)^2=1+1+9=11$. At the mean it is $(1-3)^2+(3-3)^2+(5-3)^2=4+0+4=8$. (3) No. Each step optimizes only assignments or centers while holding the other part fixed, so the algorithm can stop at a solution that is not the global minimum. (4) An empty cluster has no observations to average, so its centroid is undefined. Reinitializing its center can change subsequent assignments, and that operation is not itself covered by the non-increase proof for a mean update.

What You'll Learn