A k-Means Clustering Trace

Run Lloyd's algorithm on six points with two clusters, alternating assignment and mean update until the centers stop moving.

Problem

k-means partitions data into k clusters by minimizing within-cluster squared distance. Lloyd's algorithm alternates two steps: assign each point to its nearest center, then move each center to the mean of its assigned points. It converges to a local optimum, so initialization matters.

Data and initialization

Six points on a line: 1, 2, 3, 10, 11, 12, with k=2. Initialize centers at 2 and 11. Each iteration reassigns points then recomputes means.

import numpy as np
X=np.array([1,2,3,10,11,12.]); C=np.array([2.,11.])
for it in range(5):
    d=np.abs(X[:,None]-C[None,:])
    a=d.argmin(1)
    newC=np.array([X[a==k].mean() for k in range(2)])
    print('iter',it,'assign',a,'centers',np.round(newC,2))
    if np.allclose(newC,C): break
    C=newC

Result

The algorithm assigns the first three points to cluster 0 and the last three to cluster 1 immediately, then the centers converge to 2 and 11, which are the group means. It stops when an update leaves the centers unchanged. A bad initialization, such as both centers among the low points, could converge to a worse partition, which is why k-means++ seeding is standard.

• Lloyd's algorithm monotonically decreases the objective, guaranteeing convergence but only to a local minimum.
• The number of clusters k must be chosen in advance; the elbow or silhouette methods help.
• Kronos uses clustering to group similar plasma-shot conditions before per-cluster modeling.