Dictionary of Applied Machine Learning · $k$-means++

$k$-means++ — Python demo

Updated on 2026-11-19

Numerical companion to the entry $k$-means++: it recomputes what the entry states and prints one line per check

Numerical companion to the glossary entry 'kmeanspp' ($k$-means++). Lloyd's algorithm for k-means needs k initial cluster centroids, and the fixed point it reaches depends on them. k-means++ draws the initial centroids (the seeds) from the data points one after the other, each with probability proportional to its squared Euclidean distance to the nearest seed already chosen; uniform seeding draws k distinct data points with equal probability.

Run it without installing anything:
uv run https://dictionaryofml.org/terms/kmeanspp.py
uv downloads this script and the pinned NumPy and Matplotlib it needs, then runs it; the script fetches any input file it uses. To keep the output files, download kmeanspp.py into a folder and run uv run kmeanspp.py there. With NumPy and Matplotlib already installed, python3 kmeanspp.py, from any directory — it writes its output files into the current directory. Fixed seeds, so the printed numbers reproduce exactly. Download kmeanspp.py · Notebook · Open in Colab

Before running a downloaded copy, scan it: uvx bandit -q -t B102,B307,B602,B605 kmeanspp.py (B102,B307,B602,B605 are the exec, eval and shell checks of bandit) reports nothing: the script runs no shell command and evaluates no generated code.

The script, block by block

One cell per block of the script: the code, and what that code printed when it last ran here

setup

"""k-means++ seeding against uniform seeding of Lloyd's algorithm, on the
image patches of the Oetscher photograph and on a four-point example.

Purpose
-------
Numerical companion to the glossary entry 'kmeanspp' ($k$-means++).
Lloyd's algorithm for k-means needs k initial cluster centroids, and the
fixed point it reaches depends on them.  k-means++ draws the initial
centroids (the seeds) from the data points one after the other, each with
probability proportional to its squared Euclidean distance to the nearest
seed already chosen; uniform seeding draws k distinct data points with
equal probability.

The demo checks the entry's claims on the same 972 patches as the kmeans
demo (the photograph of the Oetscher massif, assets/oetscher.jpg, cut into
128 x 128 patches, each described by its average greenness and blueness):
given a vegetation patch as first seed, the second seed is a sky patch
far more often under k-means++ than under uniform seeding; the clustering
error of the k-means++ seeds themselves is, on
average, less than half that of uniform seeds, and its mean is below the
bound 8 (ln k + 2) times the smallest clustering error found, as Theorem
1.1 of Arthur and Vassilvitskii (2007) guarantees; Lloyd's algorithm
started from k-means++ seeds reaches the best clustering in more of 1000
runs and needs fewer iterations; and on four data points at (+-5, +-1)
the exact probability that two seeds on the same side are drawn, which
leads Lloyd's algorithm to the top/bottom split, is 1/3 under uniform
seeding and 1/52 under k-means++.

Deterministic: fixed seeds of numpy's default_rng.  Self-contained: numpy
+ matplotlib only; the photograph is read from the repository or fetched
once from dictionaryofml.org.

Blocks
------
[B-patches]  Cut the photograph into 128 x 128 patches and measure how
             green and how blue each one is; the reference clustering
             with k = 3 from the kmeans demo's deterministic start.
[B-toy]      Four data points at (+-5, +-1), k = 2: exact probabilities
             of two seeds on the same side (1/3 uniform, 1/52 k-means++),
             confirmed by 20000 draws; Lloyd's algorithm from such seeds
             ends at the top/bottom split with clustering error 25, from
             seeds on opposite sides at the left/right split with error
             1; the expected clustering error of the seeds under each
             rule.
[B-second]   Given a vegetation patch as first seed, the probability that
             the second seed is a sky or a mountain patch, under the
             squared-distance rule and under uniform seeding.
[B-seeds]    1000 draws of k = 3 seeds under each rule: the clustering
             error of the seeds themselves, its mean, and the bound
             8 (ln k + 2) times the smallest clustering error found.
[B-lloyd]    Lloyd's algorithm from each of the 2000 seed sets: how often
             it reaches the best clustering, where else it stops, and how
             many iterations it needs.
[B-plot]     Every 49th patch for the figure (20 of 972 patches) with its
             second-seed probability, the first seed, and the sorted
             clustering errors of the 1000 runs per rule.

Outputs
-------
kmeanspp_patches_plot.csv : the 20 drawn patches: green, blue, the
                            probability p of being the second seed, and a
                            marker size whose area is proportional to p.
kmeanspp_first_seed.csv   : the first seed used in [B-second].
kmeanspp_runs.csv         : for each fraction of the 1000 runs, the
                            clustering error of the seeds and after
                            Lloyd's algorithm, sorted, per seeding rule.
kmeanspp.png              : matplotlib preview (checking only).
"""

# /// script
# requires-python = ">=3.10"
# dependencies = ["matplotlib==3.10.7", "numpy==2.3.4"]
# ///

import urllib.request
from pathlib import Path

import numpy as np
import matplotlib

matplotlib.use("Agg")
import matplotlib.pyplot as plt
from matplotlib.image import imread

OUT_DIR = Path(__file__).parent

ASSET_URL = "https://dictionaryofml.org/demoassets/"


def demo_asset(name):
    """Path to the input file `name`, fetched once if it is not already here.

    Inside the repository the committed copy is used (pythondemos/ first,
    then assets/), so a run there reproduces the committed outputs exactly.
    Run from anywhere else the file is downloaded and cached beside the
    script, so the demo is runnable without the repository.
    """
    for cand in (OUT_DIR / name, OUT_DIR.parent / "assets" / name):
        if cand.exists():
            return cand
    cached = OUT_DIR / name
    print(f"    fetching {name} from {ASSET_URL}{name}")
    with urllib.request.urlopen(ASSET_URL + name, timeout=180) as resp:
        cached.write_bytes(resp.read())
    return cached


report = []


def check(name, ok):
    report.append((name, bool(ok)))
    print(f"  [{'ok' if ok else 'FAIL'}] {name}")


def sq_dist(A, cents):
    """Squared Euclidean distance of every row of A to every centroid."""
    return ((A[:, None, :] - cents[None, :, :]) ** 2).sum(axis=2)


def clustering_error(A, cents):
    """Average squared Euclidean distance to the nearest centroid."""
    return float(sq_dist(A, cents).min(axis=1).mean())


def assign(A, cents):
    """Index of the nearest centroid for each row of A."""
    return sq_dist(A, cents).argmin(axis=1)


def lloyd(A, cents, max_iter=300):
    """Lloyd's algorithm from the given centroids.

    Returns the centroids at the fixed point, the assignment they induce
    and the number of iterations (assignment plus averaging steps)."""
    cents = np.array(cents, dtype=float)
    lab = assign(A, cents)
    for it in range(1, max_iter + 1):
        new = np.stack([A[lab == c].mean(axis=0) if np.any(lab == c)
                        else cents[c] for c in range(len(cents))])
        new_lab = assign(A, new)
        if np.array_equal(new_lab, lab) and np.allclose(new, cents):
            return new, new_lab, it
        lab, cents = new_lab, new
    return cents, lab, max_iter


def seeds_kmeanspp(A, k, rng):
    """k-means++: the first seed uniformly, each further seed with
    probability proportional to the squared distance to the nearest
    seed already chosen (the D^2 weighting of Arthur and Vassilvitskii)."""
    seeds = [A[rng.integers(len(A))]]
    for _ in range(1, k):
        d2 = sq_dist(A, np.stack(seeds)).min(axis=1)
        seeds.append(A[rng.choice(len(A), p=d2 / d2.sum())])
    return np.stack(seeds)


def seeds_uniform(A, k, rng):
    """Uniform seeding: k distinct data points, each set equally likely."""
    return A[rng.choice(len(A), size=k, replace=False)]

B-patches

Cut the photograph into 128 x 128 patches and measure how green and how blue each one is; the reference clustering with k = 3 from the kmeans demo's deterministic start.

print("[B-patches] the photograph cut into patches, reference clustering")
PATCH = 128
photo = imread(demo_asset("oetscher.jpg")) / 255.0
rows = photo.shape[0] // PATCH
cols = photo.shape[1] // PATCH
tiles = photo[:rows * PATCH, :cols * PATCH].reshape(
    rows, PATCH, cols, PATCH, 3).mean(axis=(1, 3))
rgb = tiles.reshape(-1, 3)
X = np.column_stack([rgb[:, 1], rgb[:, 2]])      # greenness, blueness
m = len(X)
NRCLUSTER = 3
check(f"[B-patches] {rows} x {cols} = {m} patches, each a feature vector "
      f"of two numbers", X.shape == (972, 2))
# the kmeans demo's deterministic start: means of k equal parts by blueness
parts = np.array_split(np.argsort(X[:, 1]), NRCLUSTER)
ref_cents, ref_lab, _ = lloyd(X, np.stack([X[g].mean(axis=0) for g in parts]))
order = np.argsort(ref_cents[:, 1])              # greenest first, sky last
ref_cents = ref_cents[order]
ref_lab = np.argsort(order)[ref_lab]
ref_err = clustering_error(X, ref_cents)
NAMES = ("vegetation", "mountain and haze", "sky")
sizes = [int(np.sum(ref_lab == c)) for c in range(NRCLUSTER)]
check(f"[B-patches] reference clustering error {ref_err:.4f}; cluster sizes "
      f"{sizes[0]} vegetation, {sizes[1]} mountain and haze, {sizes[2]} sky",
      sizes[0] > sizes[1] > 0 and sizes[0] > sizes[2] > 0)
[B-patches] the photograph cut into patches, reference clustering
  [ok] [B-patches] 27 x 36 = 972 patches, each a feature vector of two numbers
  [ok] [B-patches] reference clustering error 0.0179; cluster sizes 566 vegetation, 202 mountain and haze, 204 sky

B-toy

Four data points at (+-5, +-1), k = 2: exact probabilities of two seeds on the same side (1/3 uniform, 1/52 k-means++), confirmed by 20000 draws; Lloyd's algorithm from such seeds ends at the top/bottom split with clustering error 25, from seeds on opposite sides at the left/right split with error 1; the expected clustering error of the seeds under each rule.

print("[B-toy] four data points at (+-5, +-1), k = 2")
T = np.array([[-5.0, 1.0], [-5.0, -1.0], [5.0, 1.0], [5.0, -1.0]])
side = np.sign(T[:, 0])
# exact probabilities: uniform picks 2 of 4 points, 2 of the 6 pairs share a
# side; k-means++ picks the first uniformly, then the same-side point has
# squared distance 4 against 100 and 104 for the two others
p_same_uniform = 2 / 6
p_same_pp = 4 / (4 + 100 + 104)
check(f"[B-toy] exact probability of two seeds on the same side: "
      f"{p_same_uniform:.4f} = 1/3 (uniform), {p_same_pp:.4f} = 1/52 "
      f"(k-means++)", abs(p_same_uniform - 1 / 3) < 1e-12
      and abs(p_same_pp - 1 / 52) < 1e-12)
rng = np.random.default_rng(7)
DRAWS = 20000
same_u = np.mean([side[0] == side[1] for s in range(DRAWS)
                  for side in [np.sign(seeds_uniform(T, 2, rng)[:, 0])]])
same_p = np.mean([side[0] == side[1] for s in range(DRAWS)
                  for side in [np.sign(seeds_kmeanspp(T, 2, rng)[:, 0])]])
check(f"[B-toy] {DRAWS} draws: same side in {same_u:.4f} (uniform) and "
      f"{same_p:.4f} (k-means++) of the draws, within 0.01 of the exact "
      f"values", abs(same_u - p_same_uniform) < 0.01
      and abs(same_p - p_same_pp) < 0.01)
W_same, lab_same, _ = lloyd(T, T[:2])            # both seeds on the left
W_opp, lab_opp, _ = lloyd(T, T[[0, 2]])          # one seed per side
err_same, err_opp = clustering_error(T, W_same), clustering_error(T, W_opp)
check(f"[B-toy] seeds on the same side: Lloyd's algorithm stops at the "
      f"centroids (0, 1) and (0, -1), the top/bottom split, clustering "
      f"error {err_same:.0f}",
      np.allclose(sorted(W_same.tolist()), [[0, -1], [0, 1]])
      and abs(err_same - 25) < 1e-12)
check(f"[B-toy] seeds on opposite sides: the left/right split, clustering "
      f"error {err_opp:.0f}",
      np.allclose(sorted(W_opp.tolist()), [[-5, 0], [5, 0]])
      and abs(err_opp - 1) < 1e-12)
check("[B-toy] the centroids (0, 1) and (0, -1) are a fixed point of "
      "Lloyd's algorithm", lloyd(T, np.array([[0.0, 1.0], [0.0, -1.0]]))[2]
      == 1)
seed_err_same = clustering_error(T, T[:2])
seed_err_opp = clustering_error(T, T[[0, 2]])
exp_seed_u = p_same_uniform * seed_err_same + (1 - p_same_uniform) * seed_err_opp
exp_seed_p = p_same_pp * seed_err_same + (1 - p_same_pp) * seed_err_opp
bound_toy = 8 * (np.log(2) + 2) * err_opp
check(f"[B-toy] clustering error of the seeds: {seed_err_same:.0f} on the "
      f"same side, {seed_err_opp:.0f} on opposite sides; expected value "
      f"{exp_seed_u:.2f} (uniform) and {exp_seed_p:.2f} (k-means++), the "
      f"latter below the bound 8 (ln 2 + 2) * {err_opp:.0f} = {bound_toy:.2f}",
      exp_seed_p < bound_toy and exp_seed_p < exp_seed_u)
exp_final_u = p_same_uniform * err_same + (1 - p_same_uniform) * err_opp
exp_final_p = p_same_pp * err_same + (1 - p_same_pp) * err_opp
check(f"[B-toy] expected clustering error after Lloyd's algorithm: "
      f"{exp_final_u:.2f} (uniform) and {exp_final_p:.2f} (k-means++)",
      exp_final_p < exp_final_u)


def exact_seed_expectations(P):
    """Exact expected clustering error of two seeds drawn from the data
    points P, under uniform seeding and under k-means++, by summing over
    every ordered pair of seeds with its probability."""
    n = len(P)
    e_u = e_p = 0.0
    for i in range(n):
        d2 = sq_dist(P, P[i:i + 1])[:, 0]
        for j in range(n):
            if j == i:
                continue
            e = clustering_error(P, P[[i, j]])
            e_u += e / (n * (n - 1))
            e_p += e * (1 / n) * d2[j] / d2.sum()
    return e_u, e_p


e_u5, e_p5 = exact_seed_expectations(T)
check(f"[B-toy] the exact expectations over all seed pairs agree: "
      f"{e_u5:.2f} (uniform), {e_p5:.2f} (k-means++)",
      abs(e_u5 - exp_seed_u) < 1e-9 and abs(e_p5 - exp_seed_p) < 1e-9)
T_far = T.copy()
T_far[:, 0] *= 10                              # the pairs at (+-50, +-1)
e_u50, e_p50 = exact_seed_expectations(T_far)
best_far = clustering_error(T_far, np.array([[-50.0, 0.0], [50.0, 0.0]]))
check(f"[B-toy] moving the pairs apart to (+-50, +-1) keeps the smallest "
      f"clustering error at {best_far:.0f} but raises the expected "
      f"clustering error of two uniform seeds to {e_u50:.0f}, while that of "
      f"two k-means++ seeds is {e_p50:.2f}",
      best_far == 1.0 and e_u50 > 1000 and e_p50 < 3.0)
[B-toy] four data points at (+-5, +-1), k = 2
  [ok] [B-toy] exact probability of two seeds on the same side: 0.3333 = 1/3 (uniform), 0.0192 = 1/52 (k-means++)
  [ok] [B-toy] 20000 draws: same side in 0.3298 (uniform) and 0.0195 (k-means++) of the draws, within 0.01 of the exact values
  [ok] [B-toy] seeds on the same side: Lloyd's algorithm stops at the centroids (0, 1) and (0, -1), the top/bottom split, clustering error 25
  [ok] [B-toy] seeds on opposite sides: the left/right split, clustering error 1
  [ok] [B-toy] the centroids (0, 1) and (0, -1) are a fixed point of Lloyd's algorithm
  [ok] [B-toy] clustering error of the seeds: 50 on the same side, 2 on opposite sides; expected value 18.00 (uniform) and 2.92 (k-means++), the latter below the bound 8 (ln 2 + 2) * 1 = 21.55
  [ok] [B-toy] expected clustering error after Lloyd's algorithm: 9.00 (uniform) and 1.46 (k-means++)
  [ok] [B-toy] the exact expectations over all seed pairs agree: 18.00 (uniform), 2.92 (k-means++)
  [ok] [B-toy] moving the pairs apart to (+-50, +-1) keeps the smallest clustering error at 1 but raises the expected clustering error of two uniform seeds to 1668, while that of two k-means++ seeds is 3.00

B-second

Given a vegetation patch as first seed, the probability that the second seed is a sky or a mountain patch, under the squared-distance rule and under uniform seeding.

print("[B-second] the second seed, given a vegetation patch as first seed")
veg = np.where(ref_lab == 0)[0]
first = veg[np.argmin(sq_dist(X[veg], ref_cents[:1])[:, 0])]
d2 = sq_dist(X, X[first:first + 1])[:, 0]
p_second = d2 / d2.sum()
mass = [float(p_second[ref_lab == c].sum()) for c in range(NRCLUSTER)]
share = [s / m for s in sizes]
check(f"[B-second] first seed: the vegetation patch nearest to the "
      f"vegetation centroid, ({X[first, 0]:.3f}, {X[first, 1]:.3f})",
      ref_lab[first] == 0)
check(f"[B-second] probability that the second seed is a sky patch: "
      f"{mass[2]:.2f} under k-means++, {share[2]:.2f} under uniform seeding; "
      f"a mountain patch: {mass[1]:.2f} against {share[1]:.2f}; another "
      f"vegetation patch: {mass[0]:.2f} against {share[0]:.2f}",
      mass[2] > 3 * share[2] and mass[0] < share[0] / 5)
check("[B-second] the probabilities over the three clusters sum to one "
      "under both rules",
      abs(sum(mass) - 1) < 1e-12 and abs(sum(share) - 1) < 1e-12)
[B-second] the second seed, given a vegetation patch as first seed
  [ok] [B-second] first seed: the vegetation patch nearest to the vegetation centroid, (0.282, 0.138)
  [ok] [B-second] probability that the second seed is a sky patch: 0.74 under k-means++, 0.21 under uniform seeding; a mountain patch: 0.20 against 0.21; another vegetation patch: 0.06 against 0.58
  [ok] [B-second] the probabilities over the three clusters sum to one under both rules

B-seeds

1000 draws of k = 3 seeds under each rule: the clustering error of the seeds themselves, its mean, and the bound 8 (ln k + 2) times the smallest clustering error found.

print("[B-seeds] clustering error of the seeds, 1000 draws per rule")
RUNS = 1000
rng = np.random.default_rng(2007)
seed_sets = {"k-means++": [seeds_kmeanspp(X, NRCLUSTER, rng)
                           for _ in range(RUNS)],
             "uniform": [seeds_uniform(X, NRCLUSTER, rng)
                         for _ in range(RUNS)]}
seed_errs = {name: np.array([clustering_error(X, S) for S in sets])
             for name, sets in seed_sets.items()}
veg_set = {tuple(X[i]) for i in veg}
all_veg = {name: float(np.mean([all(tuple(w) in veg_set for w in S)
                                for S in sets]))
           for name, sets in seed_sets.items()}
n_v = sizes[0]
p_all_veg = (n_v * (n_v - 1) * (n_v - 2)) / (m * (m - 1) * (m - 2))
check(f"[B-seeds] all three seeds are vegetation patches with exact "
      f"probability {p_all_veg:.2f} under uniform seeding ({100 * all_veg['uniform']:.1f}% "
      f"of the draws), against {100 * all_veg['k-means++']:.1f}% of the "
      f"k-means++ draws",
      abs(all_veg["uniform"] - p_all_veg) < 0.03
      and all_veg["k-means++"] < all_veg["uniform"] / 5)
[B-seeds] clustering error of the seeds, 1000 draws per rule
  [ok] [B-seeds] all three seeds are vegetation patches with exact probability 0.20 under uniform seeding (20.8% of the draws), against 0.5% of the k-means++ draws
  [ok] [B-seeds] mean clustering error of the seeds: 0.0376 (k-means++), 0.0859 (uniform); ratios to the best clustering error found, 2.11 and 4.81; the bound 8 (ln 3 + 2) = 24.79
  [ok] [B-seeds] worst seed set: clustering error 0.1493 (k-means++) against 0.5505 (uniform)

B-lloyd

Lloyd's algorithm from each of the 2000 seed sets: how often it reaches the best clustering, where else it stops, and how many iterations it needs.

print("[B-lloyd] Lloyd's algorithm from each seed set")
final_errs, iters = {}, {}
final_cents = {}
for name, sets in seed_sets.items():
    out = [lloyd(X, S) for S in sets]
    final_cents[name] = [o[0] for o in out]
    final_errs[name] = np.array([clustering_error(X, o[0]) for o in out])
    iters[name] = np.array([o[2] for o in out])
best = min(e.min() for e in final_errs.values())
check(f"[B-lloyd] the smallest clustering error over all {2 * RUNS} runs, "
      f"{best:.4f}, agrees with the reference clustering error {ref_err:.4f}",
      abs(best - ref_err) < 1e-5)

bound = 8 * (np.log(NRCLUSTER) + 2)
mean_pp, mean_u = seed_errs["k-means++"].mean(), seed_errs["uniform"].mean()
check(f"[B-seeds] mean clustering error of the seeds: {mean_pp:.4f} "
      f"(k-means++), {mean_u:.4f} (uniform); ratios to the best clustering "
      f"error found, {mean_pp / best:.2f} and {mean_u / best:.2f}; the "
      f"bound 8 (ln 3 + 2) = {bound:.2f}",
      mean_pp < bound * best and mean_pp < 0.5 * mean_u)
check(f"[B-seeds] worst seed set: clustering error {seed_errs['k-means++'].max():.4f} "
      f"(k-means++) against {seed_errs['uniform'].max():.4f} (uniform)",
      seed_errs["k-means++"].max() < seed_errs["uniform"].max())

TOL = 1.01
at_best = {n: float(np.mean(e <= TOL * best)) for n, e in final_errs.items()}
check(f"[B-lloyd] runs ending within 1% of the best clustering error: "
      f"{100 * at_best['k-means++']:.1f}% (k-means++), "
      f"{100 * at_best['uniform']:.1f}% (uniform)",
      at_best["k-means++"] > at_best["uniform"])
others = np.concatenate([e[e > TOL * best] for e in final_errs.values()])
worst = others.max()
at_worst = {n: float(np.mean(e >= worst / TOL)) for n, e in final_errs.items()}
check(f"[B-lloyd] every other run stops at a clustering error within 1% of "
      f"{worst:.4f}, {worst / best:.2f} times the best: "
      f"{100 * at_worst['k-means++']:.1f}% of the k-means++ runs, "
      f"{100 * at_worst['uniform']:.1f}% of the uniform runs",
      np.all(others >= worst / TOL)
      and all(abs(at_best[n] + at_worst[n] - 1) < 1e-12 for n in at_best))
# what the worse fixed point looks like, in terms of the reference clusters
i_worst = int(np.argmax(final_errs["uniform"]))
W_bad = final_cents["uniform"][i_worst]
lab_bad = assign(X, W_bad)
veg_split = np.sort(np.bincount(lab_bad[ref_lab == 0], minlength=3))[::-1]
mtn_counts = np.bincount(lab_bad[ref_lab == 1], minlength=3)
mtn_home = int(np.argmax(mtn_counts))
mtn_share = mtn_counts[mtn_home] / np.sum(lab_bad == mtn_home)
check(f"[B-lloyd] at that fixed point the vegetation patches are split "
      f"{veg_split[0]} to {veg_split[1]} between two centroids, and no "
      f"centroid belongs to the mountain: its {sizes[1]} patches are divided "
      f"{mtn_counts[mtn_home]} to {sizes[1] - mtn_counts[mtn_home]} between "
      f"two centroids, and even the first of these has only "
      f"{100 * mtn_share:.0f}% mountain patches",
      veg_split[1] > 100 and mtn_share < 0.5)
it_pp, it_u = iters["k-means++"].mean(), iters["uniform"].mean()
check(f"[B-lloyd] iterations of Lloyd's algorithm: {it_pp:.1f} on average "
      f"from k-means++ seeds, {it_u:.1f} from uniform seeds", it_pp < it_u)
R = 5
check(f"[B-lloyd] probability that all of {R} restarts miss the best "
      f"clustering: {100 * (1 - at_best['k-means++']) ** R:.1f}% "
      f"(k-means++), {100 * (1 - at_best['uniform']) ** R:.1f}% (uniform)",
      (1 - at_best["k-means++"]) ** R < (1 - at_best["uniform"]) ** R)
[B-lloyd] Lloyd's algorithm from each seed set
  [ok] [B-lloyd] the smallest clustering error over all 2000 runs, 0.0179, agrees with the reference clustering error 0.0179
  [ok] [B-lloyd] runs ending within 1% of the best clustering error: 64.1% (k-means++), 48.4% (uniform)
  [ok] [B-lloyd] every other run stops at a clustering error within 1% of 0.0249, 1.39 times the best: 35.9% of the k-means++ runs, 51.6% of the uniform runs
  [ok] [B-lloyd] at that fixed point the vegetation patches are split 368 to 198 between two centroids, and no centroid belongs to the mountain: its 202 patches are divided 111 to 91 between two centroids, and even the first of these has only 36% mountain patches
  [ok] [B-lloyd] iterations of Lloyd's algorithm: 10.0 on average from k-means++ seeds, 12.7 from uniform seeds
  [ok] [B-lloyd] probability that all of 5 restarts miss the best clustering: 0.6% (k-means++), 3.7% (uniform)

B-plot

Every 49th patch for the figure (20 of 972 patches) with its second-seed probability, the first seed, and the sorted clustering errors of the 1000 runs per rule.

print("[B-plot] thinned scatter with second-seed probabilities, sorted runs")
STEP = 49
idx = np.arange(0, m, STEP)
check(f"[B-plot] every {STEP}th patch: {len(idx)} of the {m} patches are "
      f"drawn", len(idx) == 20)
p_max = p_second[idx].max()
with open(OUT_DIR / "kmeanspp_patches_plot.csv", "w") as fh:
    fh.write("green,blue,cluster,p,ms\n")
    for i in idx:
        ms = 5.0 * np.sqrt(p_second[i] / p_max)   # marker area ~ p
        fh.write(f"{X[i, 0]:.4f},{X[i, 1]:.4f},{ref_lab[i]},"
                 f"{p_second[i]:.6f},{ms:.3f}\n")
with open(OUT_DIR / "kmeanspp_first_seed.csv", "w") as fh:
    fh.write("green,blue\n")
    fh.write(f"{X[first, 0]:.4f},{X[first, 1]:.4f}\n")
frac = (np.arange(RUNS) + 1) / RUNS
with open(OUT_DIR / "kmeanspp_runs.csv", "w") as fh:
    fh.write("frac,seed_pp,seed_uniform,final_pp,final_uniform\n")
    for r in range(RUNS):
        fh.write(f"{frac[r]:.3f},{np.sort(seed_errs['k-means++'])[r]:.5f},"
                 f"{np.sort(seed_errs['uniform'])[r]:.5f},"
                 f"{np.sort(final_errs['k-means++'])[r]:.5f},"
                 f"{np.sort(final_errs['uniform'])[r]:.5f}\n")
check("[B-plot] the drawn second-seed probabilities are largest for sky "
      "patches and smallest for vegetation patches",
      p_second[idx][ref_lab[idx] == 2].min()
      > p_second[idx][ref_lab[idx] == 0].max())

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.4, 3.9))
area = 220 * p_second[idx] / p_max
ax1.scatter(X[idx, 0], X[idx, 1], s=np.maximum(area, 2), marker="o",
            facecolors="0.75", edgecolors="black", linewidths=0.6,
            label="patch, area = probability of being seed 2")
ax1.scatter([X[first, 0]], [X[first, 1]], marker="s", s=50, color="black",
            label="first seed (a vegetation patch)")
ax1.set_xlabel("greenness of the patch")
ax1.set_ylabel("blueness of the patch")
ax1.set_title("k-means++: the second seed favors far-away patches")
ax1.legend(frameon=False, fontsize=8, loc="upper left")
ax2.plot(frac, np.sort(final_errs["k-means++"]), "k-", lw=1.4,
         label="k-means++ seeds (solid)")
ax2.plot(frac, np.sort(final_errs["uniform"]), "k--", lw=1.4,
         label="uniform seeds (dashed)")
ax2.set_xlabel("fraction of the 1000 runs")
ax2.set_ylabel("clustering error after Lloyd's algorithm")
ax2.set_title("sorted clustering errors of 1000 runs per seeding")
ax2.legend(frameon=False, fontsize=8, loc="upper left")
fig.tight_layout()
fig.savefig(OUT_DIR / "kmeanspp.png", dpi=110)

n_ok = sum(ok for _, ok in report)
print(f"\n{n_ok}/{len(report)} checks pass")
if n_ok != len(report):
    raise SystemExit(1)
[B-plot] thinned scatter with second-seed probabilities, sorted runs
  [ok] [B-plot] every 49th patch: 20 of the 972 patches are drawn
  [ok] [B-plot] the drawn second-seed probabilities are largest for sky patches and smallest for vegetation patches

25/25 checks pass
Preview figure produced by kmeanspp.py
The preview figure the block B-plot writes when the script runs