Q8(b) - K-means Clustering of the Eight Points

Data: $A_1(2,10), A_2(2,5), A_3(8,4), B_1(5,8), B_2(7,5), B_3(6,4), C_1(1,2), C_2(4,9)$; $k = 3$; Euclidean distance $d(P,Q)=\sqrt{(x_P-x_Q)^2+(y_P-y_Q)^2}$; initial centres $A_1, B_1, C_1$.

Algorithm: (1) assign every point to the nearest centre, (2) recompute each centre as the mean of its cluster, (3) repeat until no membership changes.

Iteration 1 - centres $A_1(2,10)$, $B_1(5,8)$, $C_1(1,2)$

Point	$d$ to $(2,10)$	$d$ to $(5,8)$	$d$ to $(1,2)$	Nearest
$A_1(2,10)$	0.000	3.606	8.062	A
$A_2(2,5)$	5.000	4.243	3.162	C
$A_3(8,4)$	8.485	5.000	7.280	B
$B_1(5,8)$	3.606	0.000	7.211	B
$B_2(7,5)$	7.071	3.606	6.708	B
$B_3(6,4)$	7.211	4.123	5.385	B
$C_1(1,2)$	8.062	7.211	0.000	C
$C_2(4,9)$	2.236	1.414	7.616	B

Clusters after iteration 1

• Cluster A = $\{A_1\}$, centre $= (2,10)$
• Cluster B = $\{A_3, B_1, B_2, B_3, C_2\}$, centre $= \left(\frac{8+5+7+6+4}{5},\frac{4+8+5+4+9}{5}\right) = (6,6)$
• Cluster C = $\{A_2, C_1\}$, centre $= \left(\frac{2+1}{2},\frac{5+2}{2}\right) = (1.5,3.5)$

Iteration 2 - centres $(2,10)$, $(6,6)$, $(1.5,3.5)$

Point	$d$ to $(2,10)$	$d$ to $(6,6)$	$d$ to $(1.5,3.5)$	Nearest
$A_1(2,10)$	0.000	5.657	6.519	A
$A_2(2,5)$	5.000	4.123	1.581	C
$A_3(8,4)$	8.485	2.828	6.519	B
$B_1(5,8)$	3.606	2.236	5.701	B
$B_2(7,5)$	7.071	1.414	5.701	B
$B_3(6,4)$	7.211	2.000	4.528	B
$C_1(1,2)$	8.062	6.403	1.581	C
$C_2(4,9)$	2.236	3.606	6.042	A

Clusters after iteration 2

• Cluster A = $\{A_1, C_2\}$, centre $= \left(\frac{2+4}{2},\frac{10+9}{2}\right) = (3,9.5)$
• Cluster B = $\{A_3, B_1, B_2, B_3\}$, centre $= \left(\frac{8+5+7+6}{4},\frac{4+8+5+4}{4}\right) = (6.5,5.25)$
• Cluster C = $\{A_2, C_1\}$, centre $= (1.5,3.5)$ (unchanged)

Iteration 3 - centres $(3,9.5)$, $(6.5,5.25)$, $(1.5,3.5)$

Point	$d$ to $(3,9.5)$	$d$ to $(6.5,5.25)$	$d$ to $(1.5,3.5)$	Nearest
$A_1(2,10)$	1.118	6.538	6.519	A
$A_2(2,5)$	4.610	4.507	1.581	C
$A_3(8,4)$	7.433	1.953	6.519	B
$B_1(5,8)$	2.500	3.133	5.701	A
$B_2(7,5)$	6.021	0.559	5.701	B
$B_3(6,4)$	6.265	1.346	4.528	B
$C_1(1,2)$	7.762	6.388	1.581	C
$C_2(4,9)$	1.118	4.507	6.042	A

Note that $B_1$ moves from cluster B to cluster A. New centres:

• Cluster A = $\{A_1, B_1, C_2\}$, centre $= \left(\frac{2+5+4}{3},\frac{10+8+9}{3}\right) = (3.67,9)$
• Cluster B = $\{A_3, B_2, B_3\}$, centre $= \left(\frac{8+7+6}{3},\frac{4+5+4}{3}\right) = (7,4.33)$
• Cluster C = $\{A_2, C_1\}$, centre $= (1.5,3.5)$

Iteration 4 - centres $(3.67,9)$, $(7,4.33)$, $(1.5,3.5)$

Point	$d$ to $(3.67,9)$	$d$ to $(7,4.33)$	$d$ to $(1.5,3.5)$	Nearest
$A_1(2,10)$	1.944	7.557	6.519	A
$A_2(2,5)$	4.333	5.044	1.581	C
$A_3(8,4)$	6.616	1.054	6.519	B
$B_1(5,8)$	1.667	4.177	5.701	A
$B_2(7,5)$	5.207	0.667	5.701	B
$B_3(6,4)$	5.518	1.054	4.528	B
$C_1(1,2)$	7.491	6.438	1.581	C
$C_2(4,9)$	0.333	5.548	6.042	A

The memberships are identical to iteration 3, so no point moves, the centres would not change any further, and the algorithm converges.

Final result

Cluster	Points	Final centre
Cluster 1 (A)	$A_1(2,10),\ C_2(4,9),\ B_1(5,8)$	$(3.67,\ 9)$
Cluster 2 (B)	$A_3(8,4),\ B_2(7,5),\ B_3(6,4)$	$(7,\ 4.33)$
Cluster 3 (C)	$A_2(2,5),\ C_1(1,2)$	$(1.5,\ 3.5)$

The three groups are geometrically sensible: a top-left group around $(3.67,9)$, a right-hand group around $(7,4.33)$, and a bottom-left group around $(1.5,3.5)$.