k-means, step by step

Nobody labeled these points. k-means looks for k groups by alternating two simple steps.

The centers start at randomly chosen data points. Next: assign every point to its nearest center.

Center moves0

Inertia (spread within clusters)n/a

Challenges

0 of 3 complete

On Three blobs with k = 3 and random starts, press New starting centers until a run settles with two centers sharing one blob. (not yet)
On Three blobs, run k-means to the end with k = 2, then 3, then 4, and compare the final inertia. (not yet)
Run Stretched with k = 2 to the end. Does k-means find the two stripes? (not yet)

Try this

Step through Three blobs one half-step at a time and watch the inertia chart only ever go down.
Press New starting centers a few times with random starts until two centers share one blob.
Try Stretched and No groups to see k-means find groups that are not really there.

k-means in NumPyPython with NumPy

import numpy as np

# Nine unlabeled points that happen to form three groups.
X = np.array([[-2.0, 1.0], [-1.6, 1.4], [-1.4, 0.8],
              [1.4, 1.2], [1.8, 1.0], [1.5, 0.6],
              [0.0, -1.2], [0.3, -1.6], [-0.3, -1.5]])
centers = X[[0, 1, 4]].copy()  # start at three of the points (two share a group)

labels = None
for step in range(1, 20):
    # Assign: every point joins its nearest center.
    d2 = ((X[:, None, :] - centers[None, :, :]) ** 2).sum(axis=2)
    new_labels = d2.argmin(axis=1)
    if labels is not None and np.array_equal(new_labels, labels):
        print(f"step {step}: no point changed group, converged")
        break
    labels = new_labels
    # Update: every center moves to the average of its points
    # (a center that lost all its points stays put).
    centers = np.array([X[labels == j].mean(axis=0) if np.any(labels == j) else centers[j]
                        for j in range(len(centers))])
    inertia = ((X - centers[labels]) ** 2).sum()  # total squared distance to own center
    print(f"step {step}: groups {labels}, inertia {inertia:.3f}")

print("centers:", centers.round(2).tolist())

step 1: groups [0 1 1 2 2 2 2 2 0], inertia 14.110
step 2: groups [1 1 1 2 2 2 0 2 0], inertia 6.753
step 3: groups [1 1 1 2 2 2 0 0 0], inertia 0.913
step 4: no point changed group, converged
centers: [[0.0, -1.43], [-1.67, 1.07], [1.57, 0.93]]