Clustering

Update Centroids

Recompute each centroid as the mean of its assigned points (k-means update step). A loop over points accumulates per-cluster sums and counts; a second loop divides. Library: NumPy boolean indexing points[assignments==c].mean. RESULT: updated centroid list [[cx0,cy0],[cx1,cy1]] (rounded).

By hand

points=[[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]], assignments=[0,0,0,1,1,1]. Cluster 0: x̄=(1+2+1)/3=1.3333, ȳ=(2+1+3)/3=2.0. Cluster 1: x̄=(7+8+6)/3=7.0, ȳ=(6+7+8)/3=7.0.

naive.py
Replay: real traced execution (multi-file project)
points = [[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]]
assignments = [0, 0, 0, 1, 1, 1]
k = 2
sums = [[0.0, 0.0], [0.0, 0.0]]
counts = [0, 0]
for i in range(len(points)):
    c = assignments[i]
    sums[c][0] = sums[c][0] + points[i][0]
    sums[c][1] = sums[c][1] + points[i][1]
    counts[c] = counts[c] + 1
centroids = []
for c in range(k):
    cx = round(sums[c][0] / counts[c], 4)
    cy = round(sums[c][1] / counts[c], 4)
    centroids.append([cx, cy])
print('RESULT:', centroids)

  1. points ← [[1, 2], [2, 1], [1, 3], [7, 6], [8, 7], [6, 8]]

    1points = [[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]]2assignments = [0, 0, 0, 1, 1, 1]
    values this step[[1, 2], [2, 1], [1, 3], [7, 6], [8, 7], [6, 8]]points

  2. assignments ← [0, 0, 0, 1, 1, 1]

    1points = [[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]]2assignments = [0, 0, 0, 1, 1, 1]3k = 2
    values this step[0, 0, 0, 1, 1, 1]assignments

  3. k ← 2

    2assignments = [0, 0, 0, 1, 1, 1]3k = 24sums = [[0.0, 0.0], [0.0, 0.0]]
    values this step2k

  4. sums ← [[0.0, 0.0], [0.0, 0.0]]

    3k = 24sums = [[0.0, 0.0], [0.0, 0.0]]5counts = [0, 0]
    values this step[[0.0, 0.0], [0.0, 0.0]]sums

  5. counts ← [0, 0]

    4sums = [[0.0, 0.0], [0.0, 0.0]]5counts = [0, 0]6for i in range(len(points)):
    values this step[0, 0]counts

  6. i ← 0, c ← 0, sums ← [[1.0, 2.0], [0.0, 0.0]], counts ← [1, 0]

    pass 1 of 6
    5counts = [0, 0]6for i in range(len(points)):7    c = assignments[i]8    sums[c][0] = sums[c][0] + points[i][0]9    sums[c][1] = sums[c][1] + points[i][1]10    counts[c] = counts[c] + 111centroids = []
    values this step0i0c[[1.0, 0.0], [0.0, 0.0]] → [[1.0, 2.0], [0.0, 0.0]]sums[0, 0] → [1, 0]counts
    All 6 passes — pass 1 is the card above
    passicsumscounts
    100[[1.0, 0.0], [0.0, 0.0]] → [[1.0, 2.0], [0.0, 0.0]][0, 0] → [1, 0]
    20 → 1—[[3.0, 2.0], [0.0, 0.0]] → [[3.0, 3.0], [0.0, 0.0]][1, 0] → [2, 0]
    31 → 2—[[4.0, 3.0], [0.0, 0.0]] → [[4.0, 6.0], [0.0, 0.0]][2, 0] → [3, 0]
    42 → 30 → 1[[4.0, 6.0], [7.0, 0.0]] → [[4.0, 6.0], [7.0, 6.0]][3, 0] → [3, 1]
    53 → 4—[[4.0, 6.0], [15.0, 6.0]] → [[4.0, 6.0], [15.0, 13.0]][3, 1] → [3, 2]
    64 → 5—[[4.0, 6.0], [21.0, 13.0]] → [[4.0, 6.0], [21.0, 21.0]][3, 2] → [3, 3]

  7. for i in range(len(points)):

    5counts = [0, 0]6for i in range(len(points)):7    c = assignments[i]

  8. centroids ← []

    10    counts[c] = counts[c] + 111centroids = []12for c in range(k):
    values this step[]centroids

  9. c ← 0, cx ← 1.3333, cy ← 2.0, centroids ← [[1.3333, 2.0]]

    pass 1 of 2
    11centroids = []12for c in range(k):13    cx = round(sums[c][0] / counts[c], 4)14    cy = round(sums[c][1] / counts[c], 4)15    centroids.append([cx, cy])16print('RESULT:', centroids)
    values this step1 → 0c1.3333cx2.0cy[] → [[1.3333, 2.0]]centroids

  10. c ← 1, cx ← 7.0, cy ← 7.0, centroids ← [[1.3333, 2.0], [7.0, 7.0]]

    pass 2 of 2
    11centroids = []12for c in range(k):13    cx = round(sums[c][0] / counts[c], 4)14    cy = round(sums[c][1] / counts[c], 4)15    centroids.append([cx, cy])16print('RESULT:', centroids)
    values this step0 → 1c1.3333 → 7.0cx2.0 → 7.0cy[[1.3333, 2.0]] → [[1.3333, 2.0], [7.0, 7.0]]centroids

  11. for c in range(k):

    11centroids = []12for c in range(k):13    cx = round(sums[c][0] / counts[c], 4)

  12. stdout ← RESULT: [[1.3333, 2.0], [7.0, 7.0]]

    15    centroids.append([cx, cy])16print('RESULT:', centroids)
    values this stepRESULT: [[1.3333, 2.0], [7.0, 7.0]]stdout

With NumPy

points[assignments == c] selects rows for cluster c; .mean(axis=0) averages along rows, giving the new centroid coordinates.

library.py 
import numpy as np
from dalib.display import set_display
set_display()

points = np.array([[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]], dtype=float)
assignments = np.array([0, 0, 0, 1, 1, 1])
centroids = []
for c in range(2):
    cluster_pts = points[assignments == c]
    cx = round(float(cluster_pts[:, 0].mean()), 4)
    cy = round(float(cluster_pts[:, 1].mean()), 4)
    centroids.append([cx, cy])
print('cluster_sizes:', [int(np.sum(assignments == c)) for c in range(2)])
print('RESULT:', centroids)

cluster_sizes: [3, 3]
RESULT: [[1.3333, 2.0], [7.0, 7.0]]

Implementation notes

  • sums[c][0] = sums[c][0] + points[i][0] accumulates x-coordinates per cluster; sums[c][1] accumulates y-coordinates. One loop handles all k clusters without if/else by indexing sums and counts with the assignment.
  • After one assign+update cycle (this chapter), c0 moves from [1,1] to [1.3333,2.0] and c1 stays at [7.0,7.0] (already the true mean). A second cycle's assign step would produce the same assignments — convergence in 1.
  • k-means does not guarantee the global optimum — initialization matters. assign-to-centroids and update-centroids are the two steps of a single k-means iteration (assign, then update); kmeans-one-iteration combines them; full k-means repeats this cycle until centroid change < tolerance.