Why Lloyd’s Algorithm Alternates Two Steps
K-means clustering represents each cluster by a center and seeks groups whose observations are close to their cluster centers. Lloyd’s algorithm is a procedure for constructing such a clustering when the number of clusters, \(k\), has already been specified. It begins with \(k\) initial centers and repeatedly alternates between assigning observations to centers and updating the centers from the resulting groups.
The assignment and update steps answer different questions. Given the current centers, which center is nearest to each observation? Given those assignments, where should each center be placed? Keeping these operations distinct makes it possible to trace an iteration carefully and identify when the assignments or centers have stopped changing.
- Assignment: assign each observation \(x_i\) to a nearest current center, minimizing the Euclidean distance \(\lVert x_i-\mu_j\rVert\).
- Update: for each nonempty cluster, replace its center by the arithmetic mean of all observations assigned to it.
The input includes the observations, the fixed value of \(k\), and initial centers. Lloyd’s algorithm does not, by itself, prescribe how those initial centers are selected. Each observation is assigned to one cluster; ties between equally near centers require a consistent convention, such as assigning to the lowest-indexed center. This convention makes the assignments reproducible.
How the Assignment and Update Steps Work
At the start of an iteration, the centers are held fixed while all observations are assigned. The distance is measured from each observation to each current center, not to a center being recomputed partway through the assignment step. After every observation has been assigned, the centers are updated using the completed groups.
For a cluster \(C_j\) containing \(n_j\) observations, the updated center is the coordinate-wise arithmetic mean:
For example, if the observations in a two-dimensional cluster are \((1,2)\), \((3,4)\), and \((5,0)\), its updated center is \(((1+3+5)/3,(2+4+0)/3)=(3,2)\). The update uses the observations assigned to that cluster, not the old center and not the centers of other clusters.
Record all \(k\) center coordinates before assigning any observations.
Compare its distances to all current centers. Apply the stated rule if there is a tie.
For each nonempty cluster, calculate the mean of its assigned observations in every coordinate.
Compare the new assignments or centers with those from the preceding iteration. If they have not stabilized, repeat the assignment and update steps.
An unchanged assignment is a clear stopping condition: recomputing the means from the same groups gives the same centers, so another iteration repeats the same result. The method can also be described as stopping when the centers no longer change. In numerical calculations, rounding may make very small changes look like zero; any practical numerical stopping rule should be kept distinct from the exact condition of unchanged centers.
An empty cluster requires special attention. If no observations are assigned to cluster \(j\), then \(n_j=0\) and the mean formula is undefined. An implementation must specify a policy, such as choosing a replacement center; there is no mean to compute for that cluster. The worked examples below all have nonempty clusters.
Why Nearest-Center Assignment Is the Right Step
With the centers fixed, each observation contributes its squared distance to its assigned center to the total within-cluster squared distance. The assignment of one observation does not constrain the assignment of another. Therefore, assigning \(x_i\) to a center with a larger distance cannot reduce its contribution; choosing a nearest center minimizes that observation’s contribution for the current centers. Squaring the distances does not change which center is nearest because distances are nonnegative.
This explains the assignment rule, but it does not mean that one can skip the update step: after assignments change, their cluster means may change too. Lloyd’s algorithm alternates the two operations because each one is defined using the result of the other.
Worked Example: Trace Assignments Until They Stabilize
Consider the one-dimensional observations \(0,2,3,10,11\), with \(k=2\) and initial centers \(\mu_1=0\) and \(\mu_2=3\). Use nearest-center assignment, with ties assigned to cluster 1. Perform iterations until the assignments stabilize.
Method. Assign using the centers at the start of each iteration, then calculate each cluster’s mean. The common mistake is to update a center as soon as one observation is assigned and then use that partially updated center for later observations.
Iteration 1: assign. Compare absolute distances to 0 and 3. The observation 0 has distances 0 and 3, so it goes to cluster 1. The observation 2 has distances 2 and 1, so it goes to cluster 2. The observation 3 has distances 3 and 0, so it goes to cluster 2. The observation 10 has distances 10 and 7, so it goes to cluster 2. The observation 11 has distances 11 and 8, so it goes to cluster 2.
The clusters are \(C_1=\{0\}\) and \(C_2=\{2,3,10,11\}\). Their updated centers are \(\mu_1=0/1=0\) and \(\mu_2=(2+3+10+11)/4=26/4=6.5\).
Iteration 2: reassign using 0 and 6.5. For observation 0, the distances are 0 and 6.5, so it goes to cluster 1. For 2, they are 2 and 4.5, so it goes to cluster 1. For 3, they are 3 and 3.5, so it goes to cluster 1. For 10, they are 10 and 3.5, so it goes to cluster 2. For 11, they are 11 and 4.5, so it goes to cluster 2.
Now \(C_1=\{0,2,3\}\) and \(C_2=\{10,11\}\). The updated centers are \(\mu_1=(0+2+3)/3=5/3\) and \(\mu_2=(10+11)/2=10.5\).
Iteration 3: check the assignments. With centers \(5/3\) and \(10.5\), observation 0 is closer to \(5/3\) (distances \(5/3\) and \(10.5\)); 2 is closer to \(5/3\) (distances \(1/3\) and \(8.5\)); and 3 is closer to \(5/3\) (distances \(4/3\) and \(7.5\)). Observations 10 and 11 are closer to 10.5: their distances are respectively \(25/3\) versus \(0.5\), and \(28/3\) versus \(0.5\). The assignments are unchanged, so the means remain \(5/3\) and \(10.5\), and the algorithm stops.
Check: The final clusters contain three and two observations, and their means are exactly the final centers. The final assignment step reproduced those same groups.
Worked Example: Update Two-Dimensional Centers
Five hypothetical policy records are represented by the two-feature vectors \((1,1),(2,1),(5,4),(7,5),(8,4)\). For \(k=2\), start from centers \((1,1)\) and \((7,5)\). Perform one full iteration and check whether the assignments stabilize.
Method. Compare squared Euclidean distances; this gives the same nearest-center assignments as comparing distances and avoids unnecessary square roots. A common mistake is to average the distances instead of averaging each coordinate of the observations.
Assignment. For \((1,1)\), the squared distances to the two centers are \(0\) and \(52\), so it goes to cluster 1. For \((2,1)\), they are \(1\) and \(41\), so it also goes to cluster 1. For \((5,4)\), they are \(25\) and \(8\), so it goes to cluster 2. For \((7,5)\), they are \(52\) and \(0\), so it goes to cluster 2. For \((8,4)\), they are \(58\) and \(2\), so it goes to cluster 2.
Thus \(C_1=\{(1,1),(2,1)\}\) and \(C_2=\{(5,4),(7,5),(8,4)\}\). The updated centers are \[ \mu_1=\left(\frac{1+2}{2},\frac{1+1}{2}\right)=(1.5,1), \qquad \mu_2=\left(\frac{5+7+8}{3},\frac{4+5+4}{3}\right)=\left(\frac{20}{3},\frac{13}{3}\right). \]
Check the assignments. Using the updated centers, the squared distances for \((1,1)\) are \(1/4\) and \(389/9\); for \((2,1)\), they are \(1/4\) and \(296/9\). Both remain in cluster 1. For \((5,4)\), the squared distances are \(85/4\) and \(26/9\); for \((7,5)\), they are \(185/4\) and \(5/9\); and for \((8,4)\), they are \(205/4\) and \(17/9\). Each of these three observations remains in cluster 2.
Check: The assignments did not change, so the updated centers are the means of the same groups and the algorithm has stabilized.
Worked Example: Apply a Tie Rule Consistently
For the observations \(0,2,8,10\), use \(k=2\), initial centers 0 and 4, and the rule that a tie goes to cluster 1. Find the updated centers and determine whether one more assignment step changes the groups.
Method. Apply the tie rule during assignment before computing means. The trap is to treat the tied observation as belonging to both clusters or to leave it unassigned.
Assignment. Observation 0 has distances 0 and 4, so it goes to cluster 1. Observation 2 has distances 2 and 2, so the stated tie rule assigns it to cluster 1. Observation 8 has distances 8 and 4, so it goes to cluster 2. Observation 10 has distances 10 and 6, so it goes to cluster 2. The groups are \(C_1=\{0,2\}\) and \(C_2=\{8,10\}\).
Update. The centers become \(\mu_1=(0+2)/2=1\) and \(\mu_2=(8+10)/2=9\).
Reassign and check. Using centers 1 and 9, observation 0 has distances 1 and 9, and observation 2 has distances 1 and 7; both stay in cluster 1. Observation 8 has distances 7 and 1, and observation 10 has distances 9 and 1; both stay in cluster 2. The groups and centers are unchanged.
Check: Each cluster is nonempty, each updated center is its group’s arithmetic mean, and the second assignment confirms stabilization.
Common Traps and Practical Interpretation
Lloyd’s algorithm is a step-by-step procedure, so errors often come from mixing up which centers are in use at a particular point. Keep the original centers fixed during an assignment step; update only after every observation has been assigned. Then use the updated centers for the next assignment step. Write down the groups explicitly before calculating the means.
| Common mistake | Correction |
|---|---|
| Updating a center while still assigning observations | Complete the assignment step using one fixed set of current centers. |
| Using the old center as the updated center | Compute the mean of the observations assigned to each nonempty cluster. |
| Ignoring a tied distance | Apply a stated, consistent tie rule so every observation has one assignment. |
| Applying the mean formula to an empty cluster | Recognize that its count is zero and use a specified empty-cluster policy. |
| Stopping after calculating new centers without checking assignments | Make the next assignment check, or otherwise verify that the centers have stabilized. |
A stabilized result means that repeating the algorithm’s steps under the same rules produces no change. It does not, by itself, establish that the resulting clustering is the best possible clustering among all possible choices. The algorithm’s role here is to describe how assignments and centers are alternately updated for the chosen \(k\) and starting centers.
Check Your Understanding
For each problem, follow the assignment and update steps in order. Use the stated tie rule where needed.
- For observations \(1,3,9,11\), take \(k=2\) with initial centers 1 and 9. Assign the observations, update the centers, and check whether the assignments change. (Answer: \(C_1=\{1,3\}\), \(C_2=\{9,11\}\); updated centers 2 and 10; assignments stabilize.)
- For the one-dimensional observations \(0,4,6,10\), start with centers 0 and 6. Assign and update once, then check the next assignment. (Answer: \(C_1=\{0\}\), \(C_2=\{4,6,10\}\); updated centers 0 and \(20/3\); assignments stabilize.)
- For points \((0,0),(2,0),(6,2),(8,2)\), start with centers \((0,0)\) and \((6,2)\). Find the clusters and updated centers, then verify stability. (Answer: \(C_1=\{(0,0),(2,0)\}\), \(C_2=\{(6,2),(8,2)\}\); centers \((1,0)\) and \((7,2)\); assignments stabilize.)
- For observations \(0,2,6,8\), start with centers 0 and 4 and assign ties to cluster 1. Find the updated centers and check the assignments again. (Answer: \(C_1=\{0,2\}\), \(C_2=\{6,8\}\); centers 1 and 7; assignments stabilize.)
- For observations \((1,0),(3,0),(5,4),(7,4)\), use \(k=2\) and initial centers \((1,0)\) and \((5,4)\). Perform the assignment and update, then determine whether the groups change. (Answer: \(C_1=\{(1,0),(3,0)\}\), \(C_2=\{(5,4),(7,4)\}\); centers \((2,0)\) and \((6,4)\); assignments stabilize.)