k-means clustering

Splits points into $k$ groups. It repeats:

1. Color each point by its nearest center.
2. Move each center to the middle of its points.

Run this first. Rerun it for new points and new starting centers.

pie.clear()
pie.scalar(0, out='gridOpacity')
import numpy as np
k = 3
gray = '#a8a29e'
colors = ['#e11d48', '#2563eb', '#d97706', '#7c3aed', '#0d9488', '#65a30d']
blobs = [(-2.5, 1), (2.5, 1.5), (0, -2)]
rng = np.random.default_rng()
coords = np.concatenate([rng.normal(b, 0.8, size=(12, 2)) for b in blobs]).clip(-4, 4).round(2)
ps = [pie.point(x, y, fill=gray) for x, y in coords]

# The centers start on k different points, picked at random.
cs = coords[rng.choice(len(coords), k, replace=False)]
centers = [pie.point(x, y, hidden=True) for x, y in cs]
for c, color in zip(centers, colors):
    pie.circle(c, 0.2, fill=color, stroke='#1c1917')
tick = pie.scalar(0)  # not drawn; animating it is a half-second pause

def pause():
    pie.translate_scalar_by(tick, 1, animate=True)

def show(r, changed, spread):
    done = ', done' if changed == 0 else ''
    pie.text(f'round {r}: {changed} changed color, spread {spread:.1f}{done}', 0, 4.8, 14, stroke='#1c1917', out='status')

Then run this.

labels = np.full(len(coords), -1)
for r in range(1, 100):
    # Each point takes the color of its nearest center.
    d = ((coords[:, None, :] - cs[None, :, :]) ** 2).sum(axis=2)
    new = d.argmin(axis=1)
    changed = int((new != labels).sum())
    labels = new
    for c in range(k):
        group = [ps[i] for i in np.flatnonzero(labels == c)]
        if group:
            pie.set_fill(group, colors[c])
    show(r, changed, d[np.arange(len(coords)), labels].sum())
    if changed == 0:
        break
    pause()
    # Each center moves to the average of its points. A center with no points stays put.
    cs = np.array([coords[labels == c].mean(axis=0) if (labels == c).any() else cs[c] for c in range(k)])
    pie.translate_point_to(centers, cs[:, 0].tolist(), cs[:, 1].tolist(), animate=True)
    pause()

A bad start can end in a worse split. Set k up to 6.