Clustering

Assign to Centroids

Assign each point to its nearest centroid (k-means assignment step). For each point compute squared distance to each centroid; assign to the closer one. Library: NumPy vectorized subtraction, np.sum(..., axis=1), np.where. RESULT: cluster assignment list (0/1 per point).

By hand

points=[[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]], c0=[1,1], c1=[7,7]. Squared distances to c0: 1,1,4,61,85,74. To c1: 61,61,52,1,1,2. Nearest: [0,0,0,1,1,1].

naive.py
Replay: real traced execution (multi-file project)
points = [[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]]
c0 = [1, 1]
c1 = [7, 7]
assignments = []
for pt in points:
    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2
    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2
    assignments.append(0 if d0 <= d1 else 1)
print('RESULT:', assignments)

  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]]2c0 = [1, 1]
    values this step[[1, 2], [2, 1], [1, 3], [7, 6], [8, 7], [6, 8]]points

  2. c0 ← [1, 1]

    1points = [[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]]2c0 = [1, 1]3c1 = [7, 7]
    values this step[1, 1]c0

  3. c1 ← [7, 7]

    2c0 = [1, 1]3c1 = [7, 7]4assignments = []
    values this step[7, 7]c1

  4. assignments ← []

    3c1 = [7, 7]4assignments = []5for pt in points:
    values this step[]assignments

  5. pt ← [1, 2]

    4assignments = []5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2
    values this step[1, 2]pt

  6. d0 ← 1

    5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2
    values this step1d0

  7. d1 ← 61

    6d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28assignments.append(0 if d0 <= d1 else 1)
    values this step61d1

  8. assignments ← [0]

    7    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28    assignments.append(0 if d0 <= d1 else 1)9print('RESULT:', assignments)
    values this step[] → [0]assignments

  9. pt ← [2, 1]

    4assignments = []5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2
    values this step[1, 2] → [2, 1]pt

  10. d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2

    5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2

  11. d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2

    6d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28assignments.append(0 if d0 <= d1 else 1)

  12. assignments ← [0, 0]

    7    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28    assignments.append(0 if d0 <= d1 else 1)9print('RESULT:', assignments)
    values this step[0] → [0, 0]assignments

  13. pt ← [1, 3]

    4assignments = []5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2
    values this step[2, 1] → [1, 3]pt

  14. d0 ← 4

    5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2
    values this step1 → 4d0

  15. d1 ← 52

    6d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28assignments.append(0 if d0 <= d1 else 1)
    values this step61 → 52d1

  16. assignments ← [0, 0, 0]

    7    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28    assignments.append(0 if d0 <= d1 else 1)9print('RESULT:', assignments)
    values this step[0, 0] → [0, 0, 0]assignments

  17. pt ← [7, 6]

    4assignments = []5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2
    values this step[1, 3] → [7, 6]pt

  18. d0 ← 61

    5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2
    values this step4 → 61d0

  19. d1 ← 1

    6d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28assignments.append(0 if d0 <= d1 else 1)
    values this step52 → 1d1

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

    7    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28    assignments.append(0 if d0 <= d1 else 1)9print('RESULT:', assignments)
    values this step[0, 0, 0] → [0, 0, 0, 1]assignments

  21. pt ← [8, 7]

    4assignments = []5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2
    values this step[7, 6] → [8, 7]pt

  22. d0 ← 85

    5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2
    values this step61 → 85d0

  23. d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2

    6d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28assignments.append(0 if d0 <= d1 else 1)

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

    7    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28    assignments.append(0 if d0 <= d1 else 1)9print('RESULT:', assignments)
    values this step[0, 0, 0, 1] → [0, 0, 0, 1, 1]assignments

  25. pt ← [6, 8]

    4assignments = []5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2
    values this step[8, 7] → [6, 8]pt

  26. d0 ← 74

    5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**2
    values this step85 → 74d0

  27. d1 ← 2

    6d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**27d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28assignments.append(0 if d0 <= d1 else 1)
    values this step1 → 2d1

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

    7    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**28    assignments.append(0 if d0 <= d1 else 1)9print('RESULT:', assignments)
    values this step[0, 0, 0, 1, 1] → [0, 0, 0, 1, 1, 1]assignments

  29. for pt in points:

    4assignments = []5for pt in points:6    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**2

  30. stdout ← RESULT: [0, 0, 0, 1, 1, 1]

    8    assignments.append(0 if d0 <= d1 else 1)9print('RESULT:', assignments)
    values this stepRESULT: [0, 0, 0, 1, 1, 1]stdout

With NumPy

np.sum((points - c)**2, axis=1) computes squared distances to one centroid for all points simultaneously. np.where applies the threshold.

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]])
c0 = np.array([1, 1])
c1 = np.array([7, 7])
d0 = np.sum((points - c0)**2, axis=1)
d1 = np.sum((points - c1)**2, axis=1)
assignments = np.where(d0 <= d1, 0, 1).tolist()
print('d0:', d0.tolist())
print('d1:', d1.tolist())
print('RESULT:', assignments)

d0: [1, 1, 4, 61, 85, 74]
d1: [61, 61, 52, 1, 1, 2]
RESULT: [0, 0, 0, 1, 1, 1]

Implementation notes

  • Squared distance is used for comparison (avoids sqrt); ranking is preserved since √a < √b ↔ a < b for non-negative a, b. Cross-reference: euclidean-distance (ch02) for the distance formula.
  • Points [1,2],[2,1],[1,3] cluster tightly around c0=[1,1]; [7,6],[8,7],[6,8] around c1=[7,7] — no ties possible. Picking centroid positions to eliminate ties avoids undefined assignment behavior.
  • This is ONE step of k-means. Full k-means alternates assign↔update until centroids stop moving. Cross-reference: update-centroids (this chapter).