How The K-Means Assignment And Update Steps Work

How Lloyd’s Algorithm Improves a Clustering

K-means represents each cluster by a centroid and seeks a partition whose observations are close to their cluster’s centroid. Lloyd’s algorithm alternates between two operations: assign each observation to its nearest current centroid, then recalculate each centroid from the observations assigned to it. The procedure is simple, but the order matters: each operation minimizes the objective while holding the other part fixed.

The input is a set of $n$ observations, each represented by $p$ numerical features, and a fixed number $K$ of clusters. Write observation $i$ as the vector $\mathbf{x}_i$, its cluster label as $c_i\in\{1,\ldots,K\}$, and centroid $j$ as $\boldsymbol{\mu}_j$. The distance used here is Euclidean distance. As with other distance-based methods, feature preparation and scaling matter: a feature recorded on a much larger numerical scale can dominate the distances.

Definition: For a given partition and its centroids, the within-cluster sum of squares (WCSS) is $$ W=\sum_{i=1}^{n}\left\|\mathbf{x}_i-\boldsymbol{\mu}_{c_i}\right\|^2. $$ Here, $\|\mathbf{x}_i-\boldsymbol{\mu}_{c_i}\|^2$ is the squared Euclidean distance from observation $i$ to the centroid of its assigned cluster. K-means seeks to reduce $W$, with the number of clusters $K$ held fixed.

The algorithm requires numerical features for which a mean and squared Euclidean distance are meaningful. It also requires each cluster to contain at least one observation when its centroid is updated. In a practical implementation, a consistent rule is needed for observations tied between centroids; different tie rules can lead to different partitions.

The Assignment and Update Steps

At an assignment step, hold all centroids fixed and assign each observation to a centroid at the smallest squared Euclidean distance. At an update step, hold the assignments fixed and replace each centroid by the coordinate-wise mean of the observations in its cluster. These steps are repeated until assignments stop changing, or another specified stopping condition is met.

Start with centroids.
Choose $K$ initial centroid locations. Different starts can produce different final solutions.

Assign observations.
For each observation, find the nearest centroid and assign it to that cluster. Resolve ties using a consistent rule.

Update centroids.
For each nonempty cluster, calculate the mean of its assigned observations in every feature.

Repeat and check.
Reassign using the updated centroids, then update again if needed. Stop when the assignments no longer change, or when a defined iteration or tolerance limit is reached.

Why the Update Uses the Mean

The mean is not an arbitrary representative: it is the point that minimizes the sum of squared distances to a fixed set of observations. The following identity gives a direct justification. For observations $\mathbf{x}_1,\ldots,\mathbf{x}_m$ in one cluster, let $\bar{\mathbf{x}}$ be their coordinate-wise mean. For any proposed centroid $\mathbf{a}$,

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

To see why, write $\mathbf{x}_i-\mathbf{a}=(\mathbf{x}_i-\bar{\mathbf{x}})+(\bar{\mathbf{x}}-\mathbf{a})$, expand each squared norm, and sum. The cross-term is zero because $\sum_{i=1}^{m}(\mathbf{x}_i-\bar{\mathbf{x}})=\mathbf{0}$. The final term, $m\|\mathbf{a}-\bar{\mathbf{x}}\|^2$, is nonnegative and is zero only when $\mathbf{a}=\bar{\mathbf{x}}$. Therefore the mean minimizes the cluster’s sum of squared distances.

Key result: An assignment step cannot increase WCSS when the centroids are held fixed, because each observation is assigned to a nearest centroid. An update step cannot increase WCSS when the assignments are held fixed, because each centroid is replaced by the mean of its cluster. Thus each step leaves WCSS unchanged or reduces it, provided clusters are nonempty and ties and empty clusters are handled appropriately.

Worked Example: Updating Two One-Dimensional Clusters

A hypothetical service team summarizes four numeric customer profiles using one feature. The observations are $1,3,8,10$, and the initial centroids are $2$ and $8$. Carry out an assignment and update, calculate WCSS before and after the update, and check whether another assignment changes the result.

Method. Compare each observation’s squared distance to the two current centroids. Then calculate the mean within each resulting cluster. This avoids updating a centroid before determining which observations it represents.

Assignment. The squared distances to centroids $2$ and $8$ are: for $1$, $1$ and $49$; for $3$, $1$ and $25$; for $8$, $36$ and $0$; and for $10$, $64$ and $4$. The clusters are therefore $\{1,3\}$ and $\{8,10\}$.

Objective before updating. Using the current centroids, WCSS is

$$ (1-2)^2+(3-2)^2+(8-8)^2+(10-8)^2 =1+1+0+4=6. $$

Update. The new centroids are the cluster means: $(1+3)/2=2$ and $(8+10)/2=9$. With these centroids, WCSS is

$$ (1-2)^2+(3-2)^2+(8-9)^2+(10-9)^2 =1+1+1+1=4. $$

Check. The midpoint between the updated centroids is $5.5$. The observations $1$ and $3$ remain nearer $2$, while $8$ and $10$ remain nearer $9$. The assignments do not change, so the next update leaves the centroids and WCSS at $2$, $9$, and $4$. WCSS has fallen from $6$ to $4$, as required. The common mistake is to compare the updated objective using the old centroids; the objective after updating must be calculated using the new means.

Worked Example: Assigning Points in Two Dimensions

A hypothetical analyst represents four service locations by two scaled numeric features. The points are $(0,0)$, $(0,2)$, $(4,0)$, and $(5,1)$. The current centroids are $(0,0)$ and $(4,2)$. Find the assignments, update both centroids, and compare WCSS before and after the update.

Assignment. For $(0,0)$, the squared distances are $0$ and $20$; it joins the first cluster. For $(0,2)$, they are $4$ and $16$; it also joins the first. For $(4,0)$, they are $16$ and $4$; it joins the second. For $(5,1)$, they are $26$ and $2$; it joins the second. The clusters are $\{(0,0),(0,2)\}$ and $\{(4,0),(5,1)\}$.

Objective before updating. With the supplied centroids, the assigned squared distances sum to

$$ 0+4+4+2=10. $$

Update. The first cluster mean is $(0,(0+2)/2)=(0,1)$. The second cluster mean is $((4+5)/2,(0+1)/2)=(4.5,0.5)$. Calculate the new WCSS from these updated centroids:

\begin{aligned} W &=[(0-0)^2+(0-1)^2]+[(0-0)^2+(2-1)^2]\\ &\quad+[(4-4.5)^2+(0-0.5)^2]+[(5-4.5)^2+(1-0.5)^2]\\ &=1+1+0.5+0.5=3. \end{aligned}

Check. The new centroids are $ \sqrt{(4.5)^2+(0.5)^2}$ apart, and the points remain nearer their respective centroids: the left points are close to $(0,1)$, and the right points are close to $(4.5,0.5)$. The update reduces WCSS from $10$ to $3$. The common mistake is to average distances rather than feature coordinates: the update requires a separate mean for each coordinate.

Worked Example: Tracking Several Assignment and Update Steps

For the one-dimensional observations $0,2,3,8,10$, start with centroids $0$ and $3$. Apply Lloyd’s algorithm until assignments stop changing. Show the assignments and objective as the algorithm proceeds. Use the smaller centroid’s cluster first when describing a pair of clusters.

First assignment. The point $0$ joins centroid $0$. The points $2,3,8,10$ join centroid $3$: for example, $2$ is one unit from $3$ and two units from $0$. The clusters are $\{0\}$ and $\{2,3,8,10\}$. With the initial centroids, WCSS is $0+1+0+25+49=75$.

First update. The centroids become $0$ and $(2+3+8+10)/4=23/4=5.75$. The updated WCSS is

$$ 0+(2-5.75)^2+(3-5.75)^2+(8-5.75)^2+(10-5.75)^2 =0+14.0625+7.5625+5.0625+18.0625=44.75. $$

Second assignment and update. With centroids $0$ and $5.75$, point $2$ is nearer $0$, since $2^2=4$ and $(2-5.75)^2=14.0625$. Points $3,8,10$ are nearer $5.75$. The assignment objective, evaluated at these fixed centroids, is $0+4+7.5625+5.0625+18.0625=34.6875$. The new cluster means are $1$ and $(3+8+10)/3=7$. Their WCSS is

$$ [(0-1)^2+(2-1)^2]+[(3-7)^2+(8-7)^2+(10-7)^2] =2+26=28. $$

Third assignment and update. With centroids $1$ and $7$, point $3$ is nearer $1$, since $4<16$; points $0,2$ are also nearer $1$, and $8,10$ are nearer $7$. The assignment objective is $1+1+4+1+9=16$. The updated means are $(0+2+3)/3=5/3$ and $(8+10)/2=9$. The new WCSS is

\left[(0-\tfrac{5}{3})^2+(2-\tfrac{5}{3})^2+(3-\tfrac{5}{3})^2\right] +[(8-9)^2+(10-9)^2] =\frac{42}{9}+2=\frac{20}{3}.

Convergence check. The midpoint of $5/3$ and $9$ is $16/3$. Points $0,2,3$ remain below this boundary, while $8,10$ remain above it, so the next assignment is unchanged. The WCSS sequence after the initial assignment is $75$, $44.75$, $34.6875$, $28$, $16$, and $20/3$, with assignment and update values alternating. This verifies that the objective did not increase. The common mistake is to stop as soon as one update is complete: reassignment is needed to establish that the partition is stable.

What Convergence Does and Does Not Guarantee

With a fixed number of observations and clusters, there are only finitely many possible assignments. Under deterministic tie handling and nonempty clusters, each assignment or update does not increase WCSS. Once an assignment repeats, the corresponding mean updates are determined and the algorithm has reached a stable solution. In practice, implementations may also stop when the assignments cease changing, centroid movements become sufficiently small, or a maximum iteration count is reached.

This is a convergence guarantee for the alternating procedure, not a guarantee of finding the best possible clustering among all partitions. The objective can have multiple local minima, and the initial centroids influence which solution is reached. Several initializations can be run and their resulting WCSS compared, but a lower WCSS by itself does not determine an appropriate number of clusters.

An empty cluster is an important special case: its mean is undefined because it has no assigned observations. An implementation must handle this explicitly, for example by reinitializing its centroid or using a documented rule for relocating a centroid. The non-increase argument for a mean update assumes a nonempty cluster; do not claim that a centroid update is defined when no observations belong to that cluster.

Common Calculation Trap

Suppose a cluster contains the one-dimensional observations $1,4,7$ and a proposed centroid is $5$. The WCSS at that proposed centroid is not $3^2+1^2+2^2=14$. Those terms are not the squared deviations from $5$. The correct calculation before updating is

$$ (1-5)^2+(4-5)^2+(7-5)^2=16+1+4=21. $$

The minimizing centroid is the mean, $(1+4+7)/3=4$. At that centroid the WCSS is

$$ (1-4)^2+(4-4)^2+(7-4)^2=9+0+9=18. $$

Thus the update reduces WCSS from $21$ to $18$. In any such comparison, use the same observations, square each deviation from the centroid currently being evaluated, and then sum.

Key takeaway: Lloyd’s algorithm alternates nearest-centroid assignment with mean-based centroid updates. Each step cannot increase WCSS under the stated conditions, but the final stable clustering can depend on initialization and need not be a global minimum.

Check Your Understanding

For each problem, calculate assignments and objectives using squared Euclidean distances where applicable.

A one-cluster data set contains $2,4,8$. A proposed centroid is $5$. Find the updated centroid and WCSS before and after updating. (Answer: mean $14/3$; WCSS decreases from $19$ to $56/3$.)
In two dimensions, the observations are $(1,0),(3,0),(8,0)$, with initial centroids $(0,0)$ and $(10,0)$. Give the assignments, updated centroids, and WCSS before and after the update. (Answer: clusters $\{(1,0),(3,0)\}$ and $\{(8,0)\}$; updated centroids $(2,0)$ and $(8,0)$; WCSS decreases from $14$ to $2$.)
Observations are $(0,0),(2,0),(0,4),(6,4)$, with centroids $(0,0)$ and $(6,4)$. Assign the points and update both centroids. (Answer: clusters $\{(0,0),(2,0),(0,4)\}$ and $\{(6,4)\}$; updated centroids $(2/3,4/3)$ and $(6,4)$; updated WCSS is $40/3$.)
For observations $1,2,7,9$, start with centroids $1$ and $8$. Carry out assignment and update, then check if another assignment changes the clusters. (Answer: clusters $\{1,2\}$ and $\{7,9\}$; updated centroids $1.5$ and $8$; WCSS is $2.5$; the next assignment is unchanged.)
Two centroids are both initialized at $(0,0)$, and the observations are $(0,0)$ and $(2,0)$. If ties are always assigned to the first centroid, what issue occurs, and why can the ordinary update rule not update both centroids? (Answer: the second cluster is empty; its mean is undefined, so the implementation needs an explicit empty-cluster rule.)

What You'll Learn