Clustering

K-Means One Iteration

Run one full k-means iteration: assign every point to its nearest centroid, then recompute each centroid as the mean of its cluster. A single loop accumulates per-cluster sums and counts in one pass (no separate assignment list). Library: sklearn KMeans with init=given, n_init=1, max_iter=1. RESULT: updated centroid list [[cx0,cy0],[cx1,cy1]] (rounded).

By hand

points=[[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]], c0=[1,1], c1=[7,7]. Assign: d0=[1,1,4,61,85,74], d1=[61,61,52,1,1,2] → [0,0,0,1,1,1]. Update: c0=[(1+2+1)/3,(2+1+3)/3]=[1.3333,2.0]; c1=[(7+8+6)/3,(6+7+8)/3]=[7.0,7.0].

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]
sums = [[0.0, 0.0], [0.0, 0.0]]
counts = [0, 0]
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
    c = 0 if d0 <= d1 else 1
    sums[c][0] = sums[c][0] + pt[0]
    sums[c][1] = sums[c][1] + pt[1]
    counts[c] = counts[c] + 1
c0 = [round(sums[0][0]/counts[0], 4), round(sums[0][1]/counts[0], 4)]
c1 = [round(sums[1][0]/counts[1], 4), round(sums[1][1]/counts[1], 4)]
print('RESULT:', [c0, c1])

  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]4sums = [[0.0, 0.0], [0.0, 0.0]]
    values this step[7, 7]c1

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

    3c1 = [7, 7]4sums = [[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 pt in points:
    values this step[0, 0]counts

  6. pt ← [1, 2], d0 ← 1, d1 ← 61, c ← 0, sums ← [[1.0, 2.0], [0.0, 0.0]]

    pass 1 of 6
    5counts = [0, 0]6for pt in points:7    d0 = (pt[0]-c0[0])**2 + (pt[1]-c0[1])**28    d1 = (pt[0]-c1[0])**2 + (pt[1]-c1[1])**29    c = 0 if d0 <= d1 else 110    sums[c][0] = sums[c][0] + pt[0]11    sums[c][1] = sums[c][1] + pt[1]12    counts[c] = counts[c] + 113c0 = [round(sums[0][0]/counts[0], 4), round(sums[0][1]/counts[0], 4)]
    values this step[1, 2]pt1d061d10c[[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
    passptd0d1csumscounts
    1[1, 2]1610[[1.0, 0.0], [0.0, 0.0]] → [[1.0, 2.0], [0.0, 0.0]][0, 0] → [1, 0]
    2[1, 2] → [2, 1]———[[3.0, 2.0], [0.0, 0.0]] → [[3.0, 3.0], [0.0, 0.0]][1, 0] → [2, 0]
    3[2, 1] → [1, 3]1 → 461 → 52—[[4.0, 3.0], [0.0, 0.0]] → [[4.0, 6.0], [0.0, 0.0]][2, 0] → [3, 0]
    4[1, 3] → [7, 6]4 → 6152 → 10 → 1[[4.0, 6.0], [7.0, 0.0]] → [[4.0, 6.0], [7.0, 6.0]][3, 0] → [3, 1]
    5[7, 6] → [8, 7]61 → 85——[[4.0, 6.0], [15.0, 6.0]] → [[4.0, 6.0], [15.0, 13.0]][3, 1] → [3, 2]
    6[8, 7] → [6, 8]85 → 741 → 2—[[4.0, 6.0], [21.0, 13.0]] → [[4.0, 6.0], [21.0, 21.0]][3, 2] → [3, 3]

  7. for pt in points:

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

  8. c0 ← [1.3333, 2.0]

    12    counts[c] = counts[c] + 113c0 = [round(sums[0][0]/counts[0], 4), round(sums[0][1]/counts[0], 4)]14c1 = [round(sums[1][0]/counts[1], 4), round(sums[1][1]/counts[1], 4)]
    values this step[1, 1] → [1.3333, 2.0]c0

  9. c1 ← [7.0, 7.0]

    13c0 = [round(sums[0][0]/counts[0], 4), round(sums[0][1]/counts[0], 4)]14c1 = [round(sums[1][0]/counts[1], 4), round(sums[1][1]/counts[1], 4)]15print('RESULT:', [c0, c1])
    values this step[7, 7] → [7.0, 7.0]c1

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

    14c1 = [round(sums[1][0]/counts[1], 4), round(sums[1][1]/counts[1], 4)]15print('RESULT:', [c0, c1])
    values this stepRESULT: [[1.3333, 2.0], [7.0, 7.0]]stdout

With scikit-learn

KMeans(init=given, n_init=1, max_iter=1) performs exactly one assign+update cycle starting from the supplied centroids.

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

X = np.array([[1,2],[2,1],[1,3],[7,6],[8,7],[6,8]], dtype=float)
init = np.array([[1.0, 1.0], [7.0, 7.0]])
km = KMeans(n_clusters=2, init=init, n_init=1, max_iter=1, random_state=0)
km.fit(X)
print('labels:', km.labels_.tolist())
centroids = [[round(float(v), 4) for v in c] for c in km.cluster_centers_]
print('RESULT:', centroids)

labels: [0, 0, 0, 1, 1, 1]
RESULT: [[1.3333, 2.0], [7.0, 7.0]]

Implementation notes

  • The assign and update steps are fused into a single loop: c = 0 if d0 <= d1 else 1 selects the cluster; sums[c][0] and counts[c] accumulate inline. This avoids storing a separate assignments list while keeping each logical step visible in the trace.
  • sklearn's max_iter=1 performs one assign+update cycle and stops — confirmed to match the manual result exactly when init is supplied directly.
  • c1 returns to [7.0,7.0] (unchanged from initialization) because [7,7] is already the exact mean of its three cluster members. A second iteration would produce the same assignments, so the algorithm converges in one step here.
  • Cross-reference: assign-to-centroids and update-centroids (this chapter) for the individual steps shown separately.