Applying the K-Means Algorithm to a Small Dataset

Definition. K-means is a partitioning (centroid-based) algorithm that splits $n$ objects into $k$ clusters by minimising the within-cluster sum of squares

$$J = \sum_{c=1}^{k}\sum_{x_i \in C_c} \lVert x_i - \mu_c \rVert^2$$

where $\mu_c$ is the centroid of cluster $C_c$.

1. The dataset

The question leaves the data open, so we take $k = 2$ and these six 2-D points:

Point	Coordinates
P1	(1, 1)
P2	(2, 1)
P3	(1, 2)
P4	(8, 8)
P5	(9, 8)
P6	(8, 9)

2. Algorithm steps

1. Choose the number of clusters $k$ and pick $k$ initial centres.
2. Assign every point to the centre with the smallest Euclidean distance $d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$.
3. Recompute each centre as the mean of the points assigned to it.
4. Repeat steps 2-3 until no point changes its cluster.

3. Initialisation

Initial centres: $C_1 = P1 = (1, 1)$ and $C_2 = P4 = (8, 8)$.

4. Iteration 1 - assignment

Point	$d(\cdot, C_1)$	$d(\cdot, C_2)$	Nearest centre
P1 (1,1)	0.00	9.90	$C_1$
P2 (2,1)	1.00	9.22	$C_1$
P3 (1,2)	1.00	9.22	$C_1$
P4 (8,8)	9.90	0.00	$C_2$
P5 (9,8)	10.63	1.00	$C_2$
P6 (8,9)	10.63	1.00	$C_2$

Check: $d(P2, C_2) = \sqrt{(8-2)^2 + (8-1)^2} = \sqrt{36+49} = \sqrt{85} \approx 9.22$.

Recomputed centres:

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

$$\mu_2 = \left(\frac{8+9+8}{3},\ \frac{8+8+9}{3}\right) = (8.33,\ 8.33)$$

5. Iteration 2 - assignment with the new centres

Point	$d(\cdot, C_1)$	$d(\cdot, C_2)$	Nearest centre
P1 (1,1)	0.47	10.37	$C_1$
P2 (2,1)	0.75	9.69	$C_1$
P3 (1,2)	0.75	9.69	$C_1$
P4 (8,8)	9.43	0.47	$C_2$
P5 (9,8)	10.16	0.75	$C_2$
P6 (8,9)	10.16	0.75	$C_2$

Check: $d(P1, C_1) = \sqrt{(1-1.33)^2 + (1-1.33)^2} = \sqrt{0.109 + 0.109} \approx 0.47$.

Membership is identical to iteration 1, the recomputed centres do not move, so the algorithm converges after 2 iterations.

6. Final result

K-means result (k = 2)
----------------------
Cluster 1 : centre (1.33, 1.33) -> P1(1,1), P2(2,1), P3(1,2)
Cluster 2 : centre (8.33, 8.33) -> P4(8,8), P5(9,8), P6(8,9)
Iterations : 2  (no membership change after iteration 2)

7. Points an examiner rewards

• The result is only a local optimum of $J$; k-means++ initialises centres that are well spread out.
• It produces spherical, similarly sized clusters only — non-convex shapes are not found and outliers get no label.
• Empty clusters must be repaired, e.g. re-seeded from the farthest point.
• Choose $k$ with the elbow method or the silhouette coefficient; cost is $O(n \cdot k \cdot i)$ for $i$ iterations.