The K-Means Algorithm

The Algorithm

K-Means partitions $N$ data points into $K$ clusters. Each cluster is represented by its centroid (mean vector of all points assigned to it).

Step-by-Step

1. Initialise: choose $K$ initial centroids (standard approach: randomly select $K$ points from the data).
2. Assign: for each point $x_n$, assign it to the cluster of the nearest centroid using Euclidean distance: $z_n = \arg\min_{k} \lVert x_n - \mu_k \rVert^2$
3. Update: recompute each centroid as the mean of all points currently assigned to it: $\mu_k = \frac{1}{|C_k|} \sum_{n: z_n = k} x_n$
4. Repeat steps 2-3 until assignments stop changing (convergence).

Convergence Proof

K-Means always converges to a local optimum. The WCSS (Within-Cluster Sum of Squares) never increases across iterations.

Proof sketch: each iteration has two phases. The assignment phase moves points to their nearest centroid, which can only decrease or leave unchanged each point’s distance to its centroid; therefore WCSS cannot increase. The update phase sets each centroid to the mean of its cluster points; for Euclidean distance, the mean is the point that minimises the sum of squared distances to the cluster members; therefore WCSS cannot increase in the update phase either. Since WCSS is bounded below by 0 and cannot increase, and each step either decreases WCSS or leaves it unchanged (in which case convergence is reached), the algorithm must converge in a finite number of steps.

The algorithm is not guaranteed to find the global optimum. Different random initialisations can lead to different final clusterings.

Sensitivity to Initialisation

Poor initial centroids (two centroids starting near each other within the same true cluster) can lead to:

• Empty clusters (a centroid gets no points assigned).
• Suboptimal local optima (poor WCSS).
• Slow convergence.

Solution: K-Means++ initialisation (see K-Means++) or multiple random restarts, keeping the clustering with the lowest final WCSS.

Full Worked Example

Data

Six points in 2D: $p_1 = (1,2)$, $p_2 = (2,1)$, $p_3 = (3,3)$, $p_4 = (8,7)$, $p_5 = (9,8)$, $p_6 = (10,7)$. Set $K = 2$.

Initialisation

Randomly select $p_2 = (2,1)$ and $p_5 = (9,8)$ as initial centroids: $\mu_1^{(0)} = (2,1), \qquad \mu_2^{(0)} = (9,8)$

Iteration 1: Assignment

Compute Euclidean distances to each centroid:

Point	$\lVert p_i - \mu_1 \rVert^2$	$\lVert p_i - \mu_2 \rVert^2$	Assigned to
$p_1 = (1,2)$	$(1-2)^2 + (2-1)^2 = 2$	$(1-9)^2 + (2-8)^2 = 100$	Cluster 1
$p_2 = (2,1)$	$0$	$98$	Cluster 1
$p_3 = (3,3)$	$(3-2)^2 + (3-1)^2 = 5$	$(3-9)^2 + (3-8)^2 = 61$	Cluster 1
$p_4 = (8,7)$	$(8-2)^2 + (7-1)^2 = 72$	$(8-9)^2 + (7-8)^2 = 2$	Cluster 2
$p_5 = (9,8)$	$98$	$0$	Cluster 2
$p_6 = (10,7)$	$(10-2)^2 + (7-1)^2 = 100$	$(10-9)^2 + (7-8)^2 = 2$	Cluster 2

Assignment: $C_1 = \{p_1, p_2, p_3\}$, $C_2 = \{p_4, p_5, p_6\}$.

Iteration 1: Update

$\mu_1^{(1)} = \left(\frac{1+2+3}{3}, \frac{2+1+3}{3}\right) = (2, 2)$

$\mu_2^{(1)} = \left(\frac{8+9+10}{3}, \frac{7+8+7}{3}\right) = (9, \tfrac{22}{3}) = (9, 7.33)$

Iteration 2: Assignment

Point	To $(2,2)$	To $(9, 7.33)$	Assigned to
$p_1 = (1,2)$	1	92.4	Cluster 1
$p_2 = (2,1)$	1	89.1	Cluster 1
$p_3 = (3,3)$	2	54.8	Cluster 1
$p_4 = (8,7)$	61	1.1	Cluster 2
$p_5 = (9,8)$	85	0.4	Cluster 2
$p_6 = (10,7)$	89	1.1	Cluster 2

Assignments unchanged: converged.

Final WCSS

$\text{WCSS} = \lVert p_1 - \mu_1 \rVert^2 + \lVert p_2 - \mu_1 \rVert^2 + \lVert p_3 - \mu_1 \rVert^2 + \lVert p_4 - \mu_2 \rVert^2 + \lVert p_5 - \mu_2 \rVert^2 + \lVert p_6 - \mu_2 \rVert^2$

$= 1 + 1 + 2 + 1.1 + 0.4 + 1.1 = 6.6$

Summary

Aspect	Detail
Input	$N$ data points, desired number of clusters $K$
Output	$K$ cluster centroids + cluster assignments
Objective	Minimise WCSS = $\sum_n \lVert x_n - \mu_{z_n} \rVert^2$
Convergence	Guaranteed to converge, but to a local optimum only
Sensitivity	Depends on initial centroid choices
Complexity	$O(N K d)$ per iteration

Past paper questions: y2024p3q7e