"""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] the 972 patches and the reference clustering
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-toy] four data points at (+-5, +-1), two seeds
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-second] where the second seed falls, given a vegetation first seed
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-seeds] 1000 seed sets per rule, k = 3
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-lloyd] Lloyd's algorithm from every seed set
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-plot] CSVs and preview
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)
