A Hand-Calculated K-Means Iteration

Introduction

A k-means iteration is easy to describe but surprisingly easy to miscalculate by hand. Each iteration assigns observations to their nearest current center, then replaces each center with the arithmetic mean of the observations assigned to it. To follow the procedure correctly, keep the memberships, centers, and within-cluster sum of squares (WCSS) synchronized: a WCSS value is meaningful only when it is calculated for a specified set of memberships and centers.

This tutorial works through successive assignment and update steps. It uses squared Euclidean distance, which makes the assignment comparisons and WCSS calculations straightforward. The examples also distinguish WCSS evaluated at the old centers from WCSS after a center update.

Definition: For observations $x_1,\ldots,x_n$ and $K$ clusters, let $C_j$ be the set of observations assigned to cluster $j$, and let $\mu_j$ be its center. The within-cluster sum of squares is $$ \operatorname{WCSS}=\sum_{j=1}^{K}\sum_{x_i\in C_j}\|x_i-\mu_j\|^2. $$ For a one-dimensional observation, the squared distance is $(x_i-\mu_j)^2$. For a vector with coordinates $x_{i1},\ldots,x_{ip}$, it is the sum of the squared coordinate differences.

The Bookkeeping for One Iteration

An iteration has two distinct stages. In the assignment step, keep the current centers fixed and assign each observation to a nearest center. In the update step, keep those assignments fixed and calculate the mean of each cluster. The new means become the centers for the next assignment step.

For a point $x_i$, assignment can be made by comparing squared distances to the current centers. Taking square roots is unnecessary because squaring preserves the ordering of nonnegative distances. If two centers are equally close, the problem or implementation must specify a tie rule; none of the examples below has a tie. The WCSS at any stage is calculated using the centers and memberships that belong to that stage. In particular, after assignment but before updating, the memberships have changed while the centers have not.

Record the current centers.
Use these centers for every distance comparison in this assignment step.

Assign each observation.
Compare its squared distance to all current centers and select a nearest one.

Update the centers.
For each cluster, calculate the coordinate-wise arithmetic mean of its assigned observations.

Calculate WCSS for the stated stage.
Sum the squared distances from each observation to its assigned cluster's center. State whether those centers are pre-update or post-update.

The centroid update is appropriate because the mean minimizes the sum of squared distances within a fixed cluster. A short algebraic identity also helps verify hand calculations. For one-dimensional observations $x_1,\ldots,x_m$ in a cluster with mean $\bar{x}$, expand around that mean:

\sum_{i=1}^{m}(x_i-c)^2 = \sum_{i=1}^{m}(x_i-\bar{x})^2 + m(c-\bar{x})^2.

To see why, write $x_i-c=(x_i-\bar{x})+(\bar{x}-c)$, square and sum. The cross term is zero because $\sum_i(x_i-\bar{x})=0$. Since $m(c-\bar{x})^2$ is nonnegative and is zero at $c=\bar{x}$, the mean gives the smallest possible sum of squared distances. The coordinate-wise argument is the same for vector observations.

Worked Example: A One-Dimensional Assignment and Update

Consider the observations $1,2,4,8,9$, with two current centers at $1$ and $9$. Assign the observations, update the centers, calculate WCSS, and check whether a further assignment changes the memberships.

Method: compare squared distances to the current centers. For $1$, the squared distances are $0$ and $64$, so it joins the first cluster. For $2$, they are $1$ and $49$, so it joins the first. For $4$, they are $9$ and $25$, so it also joins the first. For $8$, they are $49$ and $1$, so it joins the second; $9$ joins the second with distances $64$ and $0$.

The resulting clusters are $C_1=\{1,2,4\}$ and $C_2=\{8,9\}$. The WCSS using the current centers $1$ and $9$, after this assignment, is $0+1+9+1+0=11$.

Update the centers. The first center becomes $(1+2+4)/3=7/3$. The second becomes $(8+9)/2=17/2$. Now calculate WCSS at these updated centers:

\begin{aligned} \operatorname{WCSS} &=\left(1-\frac{7}{3}\right)^2 +\left(2-\frac{7}{3}\right)^2 +\left(4-\frac{7}{3}\right)^2\\ &\quad+\left(8-\frac{17}{2}\right)^2 +\left(9-\frac{17}{2}\right)^2\\ &=\frac{16}{9}+\frac{1}{9}+\frac{25}{9} +\frac{1}{4}+\frac{1}{4}\\ &=\frac{42}{9}+\frac{1}{2} =\frac{14}{3}+\frac{1}{2} =\frac{31}{6}. \end{aligned}

As a check, $31/6$ is approximately $5.1667$, which is less than the WCSS of $11$ calculated at the old centers. To check the next assignment, the midpoint between $7/3$ and $17/2$ is $(7/3+17/2)/2=65/12$, approximately $5.42$. The observations $1,2,4$ are below this midpoint, and $8,9$ are above it, so all memberships stay the same. Updating again therefore leaves the centers and WCSS unchanged.

Common mistake avoided: Do not report $11$ as the WCSS after the update. It uses the old centers. Conversely, do not use the updated means when describing the WCSS before updating.

When a Point Changes Cluster

An update can move centers enough that a later assignment changes membership. When that happens, do not simply retain the previous means: first assign all observations using the current centers, then recompute every affected cluster mean. The following two-dimensional example makes the timing explicit.

Worked Example: Reassignment Changes One Membership

Take the points $(0,0),(0,2),(4,0),(5,0),(5,2)$ and current centers $A=(0,0)$ and $B=(8,2)$. Perform an assignment and update, then assign again and update once more.

First assignment. The squared distances for $(0,0)$ to $A$ and $B$ are $0$ and $68$, so it joins $A$. For $(0,2)$, they are $4$ and $64$, so it joins $A$. For $(4,0)$, they are $16$ and $20$, so it joins $A$. For $(5,0)$, they are $25$ and $13$, so it joins $B$; for $(5,2)$, they are $29$ and $9$, so it also joins $B$.

Thus, $C_A=\{(0,0),(0,2),(4,0)\}$ and $C_B=\{(5,0),(5,2)\}$. Their updated centers are $\mu_A=(4/3,2/3)$ and $\mu_B=(5,1)$. At the original centers, the assignment-stage WCSS is $0+4+16+13+9=42$.

WCSS after the first update. For cluster $A$, the squared distances to $(4/3,2/3)$ are $20/9,32/9,68/9$, summing to $120/9=40/3$. For cluster $B$, the distances to $(5,1)$ are $1$ and $1$, summing to $2$. Therefore the updated-center WCSS is $40/3+2=46/3$.

Second assignment. The point $(4,0)$ has squared distance $68/9$ to $\mu_A$ and $2$ to $\mu_B$, so it moves to $B$. The point $(0,0)$ has distances $20/9$ and $26$; $(0,2)$ has distances $32/9$ and $26$. Both remain in $A$. The points $(5,0)$ and $(5,2)$ remain in $B$, with distances $1$ to $B$ and $26$ to $A$ for each.

With these new memberships but the old updated centers, the WCSS is $20/9+32/9+2+1+1=88/9$. Now update the centers: cluster $A$ has mean $(0,1)$, and cluster $B$ has mean $(14/3,2/3)$.

WCSS after the second update. The two points in $A$ each have squared distance $1$, giving $2$. In $B$, the squared distances for $(4,0),(5,0),(5,2)$, respectively, are $8/9,5/9,17/9$, giving $30/9=10/3$. The total is $2+10/3=16/3$.

As a final check, at the new centers $(0,1)$ and $(14/3,2/3)$, each point is closer to its current cluster's center: for example, $(4,0)$ is at squared distance $8/9$ from the second center and $17$ from the first. The other four points also remain in their current clusters. This confirms that the next assignment makes no changes.

Common mistake avoided: After $(4,0)$ changes clusters, the old center $(5,1)$ is not the updated center for its new cluster. Recompute the mean of all three points in that cluster before reporting post-update WCSS.

Checking a Two-Dimensional WCSS

For vector data, square each coordinate difference and add them to obtain a point's squared Euclidean distance. Then add those point-level squared distances across all clusters. Do not add ordinary distances, and do not average the squared distances when the requested quantity is WCSS.

Worked Example: Verify WCSS Coordinate by Coordinate

Consider $(1,1),(2,1),(6,2),(7,4),(8,3)$, with current centers $A=(1,1)$ and $B=(7,4)$. Find the assignments, update both centers, and calculate WCSS after the update.

Assignment. The first two points go to $A$: their squared distances to $A$ are $0$ and $1$, while their distances to $B$ are $45$ and $34$. For $(6,2)$, the squared distances to $A$ and $B$ are $26$ and $5$, so it goes to $B$. The point $(7,4)$ goes to $B$, with distances $45$ and $0$. The point $(8,3)$ goes to $B$, with distances $53$ and $2$. Hence $C_A=\{(1,1),(2,1)\}$ and $C_B=\{(6,2),(7,4),(8,3)\}$.

The new means are $\mu_A=(3/2,1)$ and $\mu_B=(7,3)$. For $A$, the two squared distances are $1/4$ and $1/4$, totaling $1/2$. For $B$, they are $(6-7)^2+(2-3)^2=2$, $(7-7)^2+(4-3)^2=1$, and $(8-7)^2+(3-3)^2=1$. Thus, the post-update WCSS is $1/2+2+1+1=9/2=4.5$.

To verify the calculation, the first cluster's coordinate differences from its mean are $(-1/2,0)$ and $(1/2,0)$, contributing $1/4+1/4$. The second cluster contributes $2+1+1=4$. The total $4.5$ is a sum of five squared distances, not a mean or a sum of unsquared distances.

Common mistake avoided: For $(6,2)$ and center $(7,3)$, the squared distance is $(-1)^2+(-1)^2=2$, not $\sqrt{2}$. The square root is the ordinary Euclidean distance, not the quantity used in WCSS.

Common Calculation Traps

A reliable hand calculation labels each WCSS by its stage and writes one squared distance for every observation. Several errors can otherwise produce plausible-looking but incorrect totals.

Mixing centers from different stages. Use the old centers for the assignment-stage WCSS and the new means for post-update WCSS.
Omitting observations. In the first worked example, the four residual squares after updating are $1,1,1,1$ for observations $2,4,8,9$ only if centers were $3$ and $10$. The total is $4$, not $2$. In any calculation, list every observation's contribution before summing.
Using ordinary rather than squared distances. WCSS sums squared Euclidean distances, so a coordinate difference of $3$ contributes $9$, not $3$.
Updating only the cluster that changed. After reassignment, calculate the mean of every cluster from its full current membership.
Forgetting a coordinate. In two dimensions, a point contributes the squared difference in its first coordinate plus the squared difference in its second coordinate.

Key takeaway: State the memberships and centers before giving a WCSS. Assign using the current centers, update using the resulting memberships, and calculate each squared distance against the centers appropriate to the stage being reported.

Check Your Understanding

For each problem, track the assignments and use the requested centers when calculating WCSS.

For observations $0,2,7,9$ with centers $1$ and $8$, find the clusters, updated centers, and post-update WCSS. (Answer: clusters $\{0,2\}$ and $\{7,9\}$; centers $1$ and $8$; WCSS $4$.)
For observations $1,3,4,10$ with centers $2$ and $8$, assign, update, and calculate post-update WCSS. (Answer: clusters $\{1,3,4\}$ and $\{10\}$; centers $8/3$ and $10$; WCSS $14/3$.)
For points $(0,0),(0,2),(3,0),(4,0)$ with centers $(0,0)$ and $(4,0)$, give the clusters, updated centers, and post-update WCSS. (Answer: clusters $\{(0,0),(0,2)\}$ and $\{(3,0),(4,0)\}$; centers $(0,1)$ and $(7/2,0)$; WCSS $5/2$.)
For observations $0,2,7,10$ with centers $1$ and $9$, calculate the assignment-stage WCSS using the stated centers and the post-update WCSS. (Answer: clusters $\{0,2\}$ and $\{7,10\}$; updated centers $1$ and $17/2$; assignment-stage WCSS $7$; post-update WCSS $13/2$.)
For points $(0,0),(0,4),(6,0),(7,0),(7,4)$ with centers $(0,0)$ and $(11,4)$, perform two assignment-update rounds. Give the memberships and WCSS after the second update. (Answer: after round one the clusters are $\{(0,0),(0,4),(6,0)\}$ and $\{(7,0),(7,4)\}$, with centers $(2,4/3)$ and $(7,2)$; $(6,0)$ moves to the second cluster on the next assignment. After round two the clusters are $\{(0,0),(0,4)\}$ and $\{(6,0),(7,0),(7,4)\}$, and WCSS is $58/3$.)

What You'll Learn