Assign and Update

Recompute the Centroids

Once points are assigned, the update is an exact mean inside each cluster. The new centroid coordinates are rational because they are sums divided by counts.

highlighted = computed this step

The update rule

After assignment, each new centroid is the mean of its assigned points. For c1 the exact mean is (2/3, 2/3).

c1′=(2/3,2/3)c_1'=(2/3, 2/3)
Exact centroid meansNew centroids are exact means of assigned points.k-means assignment tabletie: equal d^2 uses lowest centroid index; empty clusters rejectpointd^2 to c1=(1,1)d^2 to c2=(7,7)assigned(0,0)298c1(2,0)274c1(0,2)274c1(6,6)502c2(6,8)742c2(8,6)742c2new centroids: c1'=(2/3,2/3), c2'=(20/3,20/3)

The other centroid

For c2 the mean of the last three assigned points is (20/3, 20/3).

c2′=(20/3,20/3)c_2'=(20/3, 20/3)
Exact centroid meansNew centroids are exact means of assigned points.k-means assignment tabletie: equal d^2 uses lowest centroid index; empty clusters rejectpointd^2 to c1=(1,1)d^2 to c2=(7,7)assigned(0,0)298c1(2,0)274c1(0,2)274c1(6,6)502c2(6,8)742c2(8,6)742c2new centroids: c1'=(2/3,2/3), c2'=(20/3,20/3)

Summary

The mean is the update rule because it minimizes total squared distance inside that assigned cluster. The coordinates remain exact rational values.

mean=sum/count\text{mean}=\text{sum}/\text{count}
Exact centroid meansNew centroids are exact means of assigned points.k-means assignment tabletie: equal d^2 uses lowest centroid index; empty clusters rejectpointd^2 to c1=(1,1)d^2 to c2=(7,7)assigned(0,0)298c1(2,0)274c1(0,2)274c1(6,6)502c2(6,8)742c2(8,6)742c2new centroids: c1'=(2/3,2/3), c2'=(20/3,20/3)