Why K-Means Needs a Stopping Rule
The Lloyd algorithm alternates between assigning observations to their nearest centers and updating each center to the arithmetic mean of its assigned observations. These steps can be repeated until the solution is stable, but a practical implementation also needs a rule for deciding when to stop. The rule affects both computation time and what can be concluded about the returned clusters.
Three common choices are to stop when assignments no longer change, when center movements are sufficiently small, or when a preset maximum number of iterations has been reached. These are different conditions. In particular, reaching a movement tolerance or an iteration limit does not, by itself, establish that the assignments are stable.
For a data point \(\mathbf{x}_i\), the usual k-means assignment is to the nearest center in Euclidean distance. The within-cluster sum of squares (WCSS) is the sum of squared Euclidean distances from each observation to its assigned center. The earlier material on the Lloyd algorithm establishes how the assignment and update steps are performed, and that a completed iteration cannot increase WCSS. A stopping rule determines when to end those steps; it does not change their definitions.
What Assignment Stability Establishes
Suppose assignments have not changed between consecutive assignment steps, and each cluster is nonempty. With exact mean updates, the center computed from a cluster depends only on the observations assigned to it. If the set of observations is unchanged, its mean is unchanged. Therefore, updating the centers again leaves them at the same locations. Reassigning using those same centers gives the same assignments again, provided ties are handled consistently.
This is a fixed point of the assignment-and-update procedure for that initialization. It does not establish that the result is the best possible clustering across different initial centers; the earlier material on local minima and multiple random restarts addresses that separate issue. An empty cluster also needs a specified handling convention, such as reinitializing its center, so the fixed-point argument requires nonempty clusters or an explicit empty-cluster policy.
Worked Example: Detecting Stable Assignments
Four hypothetical service locations have one-dimensional measurements \(0, 2, 8,\) and \(10\). Start a two-cluster Lloyd run with centers \(0\) and \(8\). Use a movement tolerance of \(0.5\) per center. Determine the assignments, updated centers, movements, and whether either the assignment or movement rule stops the run.
First assignment. The point \(0\) is assigned to center \(0\). The point \(2\) is closer to \(0\), since its distances are \(2\) and \(6\). The points \(8\) and \(10\) are assigned to center \(8\); for \(10\), the distances are \(10\) and \(2\). Thus the clusters are \(\{0,2\}\) and \(\{8,10\}\).
First update. Their means are \((0+2)/2=1\) and \((8+10)/2=9\). The center movements are \(|1-0|=1\) and \(|9-8|=1\). Since \(1>0.5\), the maximum movement exceeds the tolerance, so this rule does not stop after this update.
Next assignment. Using centers \(1\) and \(9\), the points \(0\) and \(2\) remain in the first cluster, while \(8\) and \(10\) remain in the second. The assignments are unchanged. Updating again gives means \(1\) and \(9\), so both movements are \(0\), which is at most \(0.5\).
Conclusion and check. The assignment rule stops because the assignments did not change. The movement rule also stops because the maximum movement is \(0\). The WCSS at these centers is \((0-1)^2+(2-1)^2+(8-9)^2+(10-9)^2=1+1+1+1=4\). Both means are indeed the centers used, confirming the update.
Center-Movement Tolerances
A movement tolerance needs a precise definition. One common absolute rule uses the largest Euclidean movement of any center. If there are \(K\) centers, define
The rule stops when \(\Delta_{\max}^{(t)}\leq\varepsilon\), where \(\varepsilon\) is a nonnegative tolerance specified before or during the run. This maximum-based rule requires every center to move by no more than the tolerance. Other implementations may use a different measure, such as the sum of movements or a relative change. A reported tolerance is meaningful only when its measure and scale are clear.
Worked Example: Maximum Movement Is Not Total Movement
During iteration 6 of a hypothetical run, two centers move Euclidean distances \(0.03\) and \(0.08\). The maximum-movement tolerance is \(0.05\), the run has a limit of 20 iterations, and the assignments changed during this iteration. Decide whether each stopping rule is met. Also calculate the total of the two movements.
Total movement. Adding the two distances gives \(0.03+0.08=0.11\). This is the sum of movements, not the maximum movement.
Maximum-movement test. The maximum is \(\max(0.03,0.08)=0.08\). Since \(0.08>0.05\), the stated maximum-movement tolerance is not met.
Assignment and iteration-limit tests. Assignments changed, so the assignment-based rule is not met. The run is at iteration 6, below its limit of 20, so the iteration-limit rule is not met either.
Conclusion and check. Under the stated rules, the run continues. The value \(0.11\) is the correct total movement; it does not replace the maximum \(0.08\) in the specified test. The assignment result is a separate check: center distances alone do not tell us whether assignments changed.
A small movement is a practical proxy for progress, not a proof that assignments are unchanged. A point near the boundary between two centers can change clusters after a small shift. Conversely, assignments can remain unchanged even while centers move appreciably during an update, because the same observations are still assigned to each cluster. The criterion being used therefore matters when interpreting why a run stopped.
Iteration Limits and the Returned Solution
An iteration limit is a computational safeguard. It guarantees that the algorithm will not continue indefinitely because of implementation issues or an unexpectedly long run. If the limit is reached before assignment stability, the returned result is the state available at the stopping point; it should not be described as having converged under the assignment rule.
There is a timing detail to check in practice: an iteration may mean one assignment-and-update pair, or a particular implementation may count initialization or individual steps differently. The meaning of the cap should be stated. The calculation below uses one iteration to mean one assignment step followed by one center update.
Worked Example: A Run Stops at Its Iteration Cap
Consider the one-dimensional observations \(0,2,3,10\), initial centers \(0\) and \(3\), and a maximum of one Lloyd iteration. Assign a tie to the first center if one occurs. Calculate the first update and WCSS, then determine whether the returned result is assignment-stable by checking what the next assignment would be.
Assignment in iteration 1. The point \(0\) goes to center \(0\). For \(2\), the distances are \(2\) to center \(0\) and \(1\) to center \(3\), so it goes to center \(3\). The points \(3\) and \(10\) also go to center \(3\). The clusters are therefore \(\{0\}\) and \(\{2,3,10\}\).
Update and WCSS. The updated centers are \(0\) and \((2+3+10)/3=5\). Using the assignments from this iteration, WCSS is \((0-0)^2+(2-5)^2+(3-5)^2+(10-5)^2=0+9+4+25=38\).
Test the next assignment. With centers \(0\) and \(5\), the distances for point \(2\) are \(2\) and \(3\), so it moves to the first cluster. Point \(3\) has distances \(3\) and \(2\), so it remains in the second cluster. The next assignments would be \(\{0,2\}\) and \(\{3,10\}\), different from the first assignments. Their means would be \(1\) and \(6.5\), respectively.
Conclusion and check. The iteration cap stops the run after the first update, even though the next assignment would change. The result has not met the assignment-based stopping condition. For a check on the next update, the WCSS would be \((0-1)^2+(2-1)^2+(3-6.5)^2+(10-6.5)^2=1+1+12.25+12.25=26.5\), which is below \(38\). The cap limits computation; it does not certify stability.
Choosing and Reporting a Rule
The appropriate stopping rule depends on the computational setting and the purpose of the analysis. Assignment stability has a direct interpretation: a complete assignment-and-update cycle did not alter the cluster membership. A movement tolerance can avoid spending time on negligible numerical changes, but its value should be considered relative to the data scale and the distance calculation being used. An iteration limit bounds run time but may return an unfinished iteration sequence.
| Rule | What it checks | What it does not guarantee |
|---|---|---|
| Assignments unchanged | Cluster membership is identical at consecutive assignment steps | That this initialization gives the best solution among all possible starts |
| Center movement at most \(\varepsilon\) | A stated measure of center displacement is sufficiently small | That assignments have stopped changing |
| Maximum iteration count reached | The preset computational limit has been reached | That either assignments or centers are stable |
A common exam trap is to treat “small center movements,” “unchanged assignments,” and “the algorithm has converged” as interchangeable. They are not. Identify the exact condition, calculate the exact movement measure specified, and check the iteration count separately. If a run stops under more than one rule, state which conditions were met rather than inferring one from another.
Determine whether it compares assignments, individual or aggregate center movement, or the number of iterations.
For a maximum-movement rule, find every center's Euclidean movement and take the maximum; do not substitute their sum.
Compare the quantity with the tolerance or cap, then say exactly what that stopping result establishes.
Check Your Understanding
For each problem, apply the stated rule rather than assuming that one stopping condition implies another.
- Three centers move \(0.012\), \(0.009\), and \(0.004\) units. The rule stops when the maximum movement is at most \(0.010\). Is it met, and what is the maximum movement? (Answer: No; the maximum is \(0.012\), which exceeds \(0.010\).)
- After a complete assignment-and-update cycle, all clusters are nonempty and the assignments match those from the preceding assignment step. Updates use exact arithmetic means and ties are handled consistently. What does the assignment rule establish? (Answer: It establishes a fixed point for this run: the means remain unchanged and the assignments remain the same.)
- Two centers move \(0.02\) and \(0.07\), and the maximum-movement tolerance is \(0.08\). Assignments changed, and the run is at iteration 4 of a 10-iteration limit. Has any of the three rules triggered? (Answer: Yes; the maximum movement is \(0.07\leq0.08\). The assignment rule and iteration-limit rule have not triggered.)
- A run reaches its stated cap of 12 iterations. A subsequent assignment check would change at least one observation's cluster. What is the correct interpretation? (Answer: The iteration-limit rule stopped the run at iteration 12; the assignments are not stable under the next check.)
- Two centers move \(0.03\) and \(0.08\). Compare the total movement with the maximum movement, then test the maximum against a tolerance of \(0.05\). (Answer: The total is \(0.11\), the maximum is \(0.08\), and the maximum-movement rule is not met because \(0.08>0.05\).)