{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "kmeanspp.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# k-means++ \u2014 Python demo\n\nNumerical companion to the entry [k-means++](https://dictionaryofml.org/terms/kmeanspp.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nNumerical 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.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/kmeanspp.py`](https://dictionaryofml.org/terms/kmeanspp.py); CC BY 4.0.\n\nBefore 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](https://bandit.readthedocs.io/)) reports nothing: the script runs no shell command and evaluates no generated code."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Notebook shim: the script resolves output paths relative to __file__,\n# which a notebook kernel does not define; everything lands in the\n# working directory instead.\nimport os\n__file__ = os.path.join(os.getcwd(), \"kmeanspp.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"k-means++ seeding against uniform seeding of Lloyd's algorithm, on the\nimage patches of the Oetscher photograph and on a four-point example.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'kmeanspp' ($k$-means++).\nLloyd's algorithm for k-means needs k initial cluster centroids, and the\nfixed point it reaches depends on them.  k-means++ draws the initial\ncentroids (the seeds) from the data points one after the other, each with\nprobability proportional to its squared Euclidean distance to the nearest\nseed already chosen; uniform seeding draws k distinct data points with\nequal probability.\n\nThe demo checks the entry's claims on the same 972 patches as the kmeans\ndemo (the photograph of the Oetscher massif, assets/oetscher.jpg, cut into\n128 x 128 patches, each described by its average greenness and blueness):\ngiven a vegetation patch as first seed, the second seed is a sky patch\nfar more often under k-means++ than under uniform seeding; the clustering\nerror of the k-means++ seeds themselves is, on\naverage, less than half that of uniform seeds, and its mean is below the\nbound 8 (ln k + 2) times the smallest clustering error found, as Theorem\n1.1 of Arthur and Vassilvitskii (2007) guarantees; Lloyd's algorithm\nstarted from k-means++ seeds reaches the best clustering in more of 1000\nruns and needs fewer iterations; and on four data points at (+-5, +-1)\nthe exact probability that two seeds on the same side are drawn, which\nleads Lloyd's algorithm to the top/bottom split, is 1/3 under uniform\nseeding and 1/52 under k-means++.\n\nDeterministic: fixed seeds of numpy's default_rng.  Self-contained: numpy\n+ matplotlib only; the photograph is read from the repository or fetched\nonce from dictionaryofml.org.\n\nBlocks\n------\n[B-patches]  Cut the photograph into 128 x 128 patches and measure how\n             green and how blue each one is; the reference clustering\n             with k = 3 from the kmeans demo's deterministic start.\n[B-toy]      Four data points at (+-5, +-1), k = 2: exact probabilities\n             of two seeds on the same side (1/3 uniform, 1/52 k-means++),\n             confirmed by 20000 draws; Lloyd's algorithm from such seeds\n             ends at the top/bottom split with clustering error 25, from\n             seeds on opposite sides at the left/right split with error\n             1; the expected clustering error of the seeds under each\n             rule.\n[B-second]   Given a vegetation patch as first seed, the probability that\n             the second seed is a sky or a mountain patch, under the\n             squared-distance rule and under uniform seeding.\n[B-seeds]    1000 draws of k = 3 seeds under each rule: the clustering\n             error of the seeds themselves, its mean, and the bound\n             8 (ln k + 2) times the smallest clustering error found.\n[B-lloyd]    Lloyd's algorithm from each of the 2000 seed sets: how often\n             it reaches the best clustering, where else it stops, and how\n             many iterations it needs.\n[B-plot]     Every 49th patch for the figure (20 of 972 patches) with its\n             second-seed probability, the first seed, and the sorted\n             clustering errors of the 1000 runs per rule.\n\nOutputs\n-------\nkmeanspp_patches_plot.csv : the 20 drawn patches: green, blue, the\n                            probability p of being the second seed, and a\n                            marker size whose area is proportional to p.\nkmeanspp_first_seed.csv   : the first seed used in [B-second].\nkmeanspp_runs.csv         : for each fraction of the 1000 runs, the\n                            clustering error of the seeds and after\n                            Lloyd's algorithm, sorted, per seeding rule.\nkmeanspp.png              : matplotlib preview (checking only).\n\"\"\"\n\n# /// script\n# requires-python = \">=3.10\"\n# dependencies = [\"matplotlib==3.10.7\", \"numpy==2.3.4\"]\n# ///\n\nimport urllib.request\nfrom pathlib import Path\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\nfrom matplotlib.image import imread\n\nOUT_DIR = Path(__file__).parent\n\nASSET_URL = \"https://dictionaryofml.org/demoassets/\"\n\n\ndef demo_asset(name):\n    \"\"\"Path to the input file `name`, fetched once if it is not already here.\n\n    Inside the repository the committed copy is used (pythondemos/ first,\n    then assets/), so a run there reproduces the committed outputs exactly.\n    Run from anywhere else the file is downloaded and cached beside the\n    script, so the demo is runnable without the repository.\n    \"\"\"\n    for cand in (OUT_DIR / name, OUT_DIR.parent / \"assets\" / name):\n        if cand.exists():\n            return cand\n    cached = OUT_DIR / name\n    print(f\"    fetching {name} from {ASSET_URL}{name}\")\n    with urllib.request.urlopen(ASSET_URL + name, timeout=180) as resp:\n        cached.write_bytes(resp.read())\n    return cached\n\n\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")\n\n\ndef sq_dist(A, cents):\n    \"\"\"Squared Euclidean distance of every row of A to every centroid.\"\"\"\n    return ((A[:, None, :] - cents[None, :, :]) ** 2).sum(axis=2)\n\n\ndef clustering_error(A, cents):\n    \"\"\"Average squared Euclidean distance to the nearest centroid.\"\"\"\n    return float(sq_dist(A, cents).min(axis=1).mean())\n\n\ndef assign(A, cents):\n    \"\"\"Index of the nearest centroid for each row of A.\"\"\"\n    return sq_dist(A, cents).argmin(axis=1)\n\n\ndef lloyd(A, cents, max_iter=300):\n    \"\"\"Lloyd's algorithm from the given centroids.\n\n    Returns the centroids at the fixed point, the assignment they induce\n    and the number of iterations (assignment plus averaging steps).\"\"\"\n    cents = np.array(cents, dtype=float)\n    lab = assign(A, cents)\n    for it in range(1, max_iter + 1):\n        new = np.stack([A[lab == c].mean(axis=0) if np.any(lab == c)\n                        else cents[c] for c in range(len(cents))])\n        new_lab = assign(A, new)\n        if np.array_equal(new_lab, lab) and np.allclose(new, cents):\n            return new, new_lab, it\n        lab, cents = new_lab, new\n    return cents, lab, max_iter\n\n\ndef seeds_kmeanspp(A, k, rng):\n    \"\"\"k-means++: the first seed uniformly, each further seed with\n    probability proportional to the squared distance to the nearest\n    seed already chosen (the D^2 weighting of Arthur and Vassilvitskii).\"\"\"\n    seeds = [A[rng.integers(len(A))]]\n    for _ in range(1, k):\n        d2 = sq_dist(A, np.stack(seeds)).min(axis=1)\n        seeds.append(A[rng.choice(len(A), p=d2 / d2.sum())])\n    return np.stack(seeds)\n\n\ndef seeds_uniform(A, k, rng):\n    \"\"\"Uniform seeding: k distinct data points, each set equally likely.\"\"\"\n    return A[rng.choice(len(A), size=k, replace=False)]"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[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."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-patches] the photograph cut into patches, reference clustering\")\nPATCH = 128\nphoto = imread(demo_asset(\"oetscher.jpg\")) / 255.0\nrows = photo.shape[0] // PATCH\ncols = photo.shape[1] // PATCH\ntiles = photo[:rows * PATCH, :cols * PATCH].reshape(\n    rows, PATCH, cols, PATCH, 3).mean(axis=(1, 3))\nrgb = tiles.reshape(-1, 3)\nX = np.column_stack([rgb[:, 1], rgb[:, 2]])      # greenness, blueness\nm = len(X)\nNRCLUSTER = 3\ncheck(f\"[B-patches] {rows} x {cols} = {m} patches, each a feature vector \"\n      f\"of two numbers\", X.shape == (972, 2))\n# the kmeans demo's deterministic start: means of k equal parts by blueness\nparts = np.array_split(np.argsort(X[:, 1]), NRCLUSTER)\nref_cents, ref_lab, _ = lloyd(X, np.stack([X[g].mean(axis=0) for g in parts]))\norder = np.argsort(ref_cents[:, 1])              # greenest first, sky last\nref_cents = ref_cents[order]\nref_lab = np.argsort(order)[ref_lab]\nref_err = clustering_error(X, ref_cents)\nNAMES = (\"vegetation\", \"mountain and haze\", \"sky\")\nsizes = [int(np.sum(ref_lab == c)) for c in range(NRCLUSTER)]\ncheck(f\"[B-patches] reference clustering error {ref_err:.4f}; cluster sizes \"\n      f\"{sizes[0]} vegetation, {sizes[1]} mountain and haze, {sizes[2]} sky\",\n      sizes[0] > sizes[1] > 0 and sizes[0] > sizes[2] > 0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[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."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-toy] four data points at (+-5, +-1), k = 2\")\nT = np.array([[-5.0, 1.0], [-5.0, -1.0], [5.0, 1.0], [5.0, -1.0]])\nside = np.sign(T[:, 0])\n# exact probabilities: uniform picks 2 of 4 points, 2 of the 6 pairs share a\n# side; k-means++ picks the first uniformly, then the same-side point has\n# squared distance 4 against 100 and 104 for the two others\np_same_uniform = 2 / 6\np_same_pp = 4 / (4 + 100 + 104)\ncheck(f\"[B-toy] exact probability of two seeds on the same side: \"\n      f\"{p_same_uniform:.4f} = 1/3 (uniform), {p_same_pp:.4f} = 1/52 \"\n      f\"(k-means++)\", abs(p_same_uniform - 1 / 3) < 1e-12\n      and abs(p_same_pp - 1 / 52) < 1e-12)\nrng = np.random.default_rng(7)\nDRAWS = 20000\nsame_u = np.mean([side[0] == side[1] for s in range(DRAWS)\n                  for side in [np.sign(seeds_uniform(T, 2, rng)[:, 0])]])\nsame_p = np.mean([side[0] == side[1] for s in range(DRAWS)\n                  for side in [np.sign(seeds_kmeanspp(T, 2, rng)[:, 0])]])\ncheck(f\"[B-toy] {DRAWS} draws: same side in {same_u:.4f} (uniform) and \"\n      f\"{same_p:.4f} (k-means++) of the draws, within 0.01 of the exact \"\n      f\"values\", abs(same_u - p_same_uniform) < 0.01\n      and abs(same_p - p_same_pp) < 0.01)\nW_same, lab_same, _ = lloyd(T, T[:2])            # both seeds on the left\nW_opp, lab_opp, _ = lloyd(T, T[[0, 2]])          # one seed per side\nerr_same, err_opp = clustering_error(T, W_same), clustering_error(T, W_opp)\ncheck(f\"[B-toy] seeds on the same side: Lloyd's algorithm stops at the \"\n      f\"centroids (0, 1) and (0, -1), the top/bottom split, clustering \"\n      f\"error {err_same:.0f}\",\n      np.allclose(sorted(W_same.tolist()), [[0, -1], [0, 1]])\n      and abs(err_same - 25) < 1e-12)\ncheck(f\"[B-toy] seeds on opposite sides: the left/right split, clustering \"\n      f\"error {err_opp:.0f}\",\n      np.allclose(sorted(W_opp.tolist()), [[-5, 0], [5, 0]])\n      and abs(err_opp - 1) < 1e-12)\ncheck(\"[B-toy] the centroids (0, 1) and (0, -1) are a fixed point of \"\n      \"Lloyd's algorithm\", lloyd(T, np.array([[0.0, 1.0], [0.0, -1.0]]))[2]\n      == 1)\nseed_err_same = clustering_error(T, T[:2])\nseed_err_opp = clustering_error(T, T[[0, 2]])\nexp_seed_u = p_same_uniform * seed_err_same + (1 - p_same_uniform) * seed_err_opp\nexp_seed_p = p_same_pp * seed_err_same + (1 - p_same_pp) * seed_err_opp\nbound_toy = 8 * (np.log(2) + 2) * err_opp\ncheck(f\"[B-toy] clustering error of the seeds: {seed_err_same:.0f} on the \"\n      f\"same side, {seed_err_opp:.0f} on opposite sides; expected value \"\n      f\"{exp_seed_u:.2f} (uniform) and {exp_seed_p:.2f} (k-means++), the \"\n      f\"latter below the bound 8 (ln 2 + 2) * {err_opp:.0f} = {bound_toy:.2f}\",\n      exp_seed_p < bound_toy and exp_seed_p < exp_seed_u)\nexp_final_u = p_same_uniform * err_same + (1 - p_same_uniform) * err_opp\nexp_final_p = p_same_pp * err_same + (1 - p_same_pp) * err_opp\ncheck(f\"[B-toy] expected clustering error after Lloyd's algorithm: \"\n      f\"{exp_final_u:.2f} (uniform) and {exp_final_p:.2f} (k-means++)\",\n      exp_final_p < exp_final_u)\n\n\ndef exact_seed_expectations(P):\n    \"\"\"Exact expected clustering error of two seeds drawn from the data\n    points P, under uniform seeding and under k-means++, by summing over\n    every ordered pair of seeds with its probability.\"\"\"\n    n = len(P)\n    e_u = e_p = 0.0\n    for i in range(n):\n        d2 = sq_dist(P, P[i:i + 1])[:, 0]\n        for j in range(n):\n            if j == i:\n                continue\n            e = clustering_error(P, P[[i, j]])\n            e_u += e / (n * (n - 1))\n            e_p += e * (1 / n) * d2[j] / d2.sum()\n    return e_u, e_p\n\n\ne_u5, e_p5 = exact_seed_expectations(T)\ncheck(f\"[B-toy] the exact expectations over all seed pairs agree: \"\n      f\"{e_u5:.2f} (uniform), {e_p5:.2f} (k-means++)\",\n      abs(e_u5 - exp_seed_u) < 1e-9 and abs(e_p5 - exp_seed_p) < 1e-9)\nT_far = T.copy()\nT_far[:, 0] *= 10                              # the pairs at (+-50, +-1)\ne_u50, e_p50 = exact_seed_expectations(T_far)\nbest_far = clustering_error(T_far, np.array([[-50.0, 0.0], [50.0, 0.0]]))\ncheck(f\"[B-toy] moving the pairs apart to (+-50, +-1) keeps the smallest \"\n      f\"clustering error at {best_far:.0f} but raises the expected \"\n      f\"clustering error of two uniform seeds to {e_u50:.0f}, while that of \"\n      f\"two k-means++ seeds is {e_p50:.2f}\",\n      best_far == 1.0 and e_u50 > 1000 and e_p50 < 3.0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[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."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-second] the second seed, given a vegetation patch as first seed\")\nveg = np.where(ref_lab == 0)[0]\nfirst = veg[np.argmin(sq_dist(X[veg], ref_cents[:1])[:, 0])]\nd2 = sq_dist(X, X[first:first + 1])[:, 0]\np_second = d2 / d2.sum()\nmass = [float(p_second[ref_lab == c].sum()) for c in range(NRCLUSTER)]\nshare = [s / m for s in sizes]\ncheck(f\"[B-second] first seed: the vegetation patch nearest to the \"\n      f\"vegetation centroid, ({X[first, 0]:.3f}, {X[first, 1]:.3f})\",\n      ref_lab[first] == 0)\ncheck(f\"[B-second] probability that the second seed is a sky patch: \"\n      f\"{mass[2]:.2f} under k-means++, {share[2]:.2f} under uniform seeding; \"\n      f\"a mountain patch: {mass[1]:.2f} against {share[1]:.2f}; another \"\n      f\"vegetation patch: {mass[0]:.2f} against {share[0]:.2f}\",\n      mass[2] > 3 * share[2] and mass[0] < share[0] / 5)\ncheck(\"[B-second] the probabilities over the three clusters sum to one \"\n      \"under both rules\",\n      abs(sum(mass) - 1) < 1e-12 and abs(sum(share) - 1) < 1e-12)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[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."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-seeds] clustering error of the seeds, 1000 draws per rule\")\nRUNS = 1000\nrng = np.random.default_rng(2007)\nseed_sets = {\"k-means++\": [seeds_kmeanspp(X, NRCLUSTER, rng)\n                           for _ in range(RUNS)],\n             \"uniform\": [seeds_uniform(X, NRCLUSTER, rng)\n                         for _ in range(RUNS)]}\nseed_errs = {name: np.array([clustering_error(X, S) for S in sets])\n             for name, sets in seed_sets.items()}\nveg_set = {tuple(X[i]) for i in veg}\nall_veg = {name: float(np.mean([all(tuple(w) in veg_set for w in S)\n                                for S in sets]))\n           for name, sets in seed_sets.items()}\nn_v = sizes[0]\np_all_veg = (n_v * (n_v - 1) * (n_v - 2)) / (m * (m - 1) * (m - 2))\ncheck(f\"[B-seeds] all three seeds are vegetation patches with exact \"\n      f\"probability {p_all_veg:.2f} under uniform seeding ({100 * all_veg['uniform']:.1f}% \"\n      f\"of the draws), against {100 * all_veg['k-means++']:.1f}% of the \"\n      f\"k-means++ draws\",\n      abs(all_veg[\"uniform\"] - p_all_veg) < 0.03\n      and all_veg[\"k-means++\"] < all_veg[\"uniform\"] / 5)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[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."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-lloyd] Lloyd's algorithm from each seed set\")\nfinal_errs, iters = {}, {}\nfinal_cents = {}\nfor name, sets in seed_sets.items():\n    out = [lloyd(X, S) for S in sets]\n    final_cents[name] = [o[0] for o in out]\n    final_errs[name] = np.array([clustering_error(X, o[0]) for o in out])\n    iters[name] = np.array([o[2] for o in out])\nbest = min(e.min() for e in final_errs.values())\ncheck(f\"[B-lloyd] the smallest clustering error over all {2 * RUNS} runs, \"\n      f\"{best:.4f}, agrees with the reference clustering error {ref_err:.4f}\",\n      abs(best - ref_err) < 1e-5)\n\nbound = 8 * (np.log(NRCLUSTER) + 2)\nmean_pp, mean_u = seed_errs[\"k-means++\"].mean(), seed_errs[\"uniform\"].mean()\ncheck(f\"[B-seeds] mean clustering error of the seeds: {mean_pp:.4f} \"\n      f\"(k-means++), {mean_u:.4f} (uniform); ratios to the best clustering \"\n      f\"error found, {mean_pp / best:.2f} and {mean_u / best:.2f}; the \"\n      f\"bound 8 (ln 3 + 2) = {bound:.2f}\",\n      mean_pp < bound * best and mean_pp < 0.5 * mean_u)\ncheck(f\"[B-seeds] worst seed set: clustering error {seed_errs['k-means++'].max():.4f} \"\n      f\"(k-means++) against {seed_errs['uniform'].max():.4f} (uniform)\",\n      seed_errs[\"k-means++\"].max() < seed_errs[\"uniform\"].max())\n\nTOL = 1.01\nat_best = {n: float(np.mean(e <= TOL * best)) for n, e in final_errs.items()}\ncheck(f\"[B-lloyd] runs ending within 1% of the best clustering error: \"\n      f\"{100 * at_best['k-means++']:.1f}% (k-means++), \"\n      f\"{100 * at_best['uniform']:.1f}% (uniform)\",\n      at_best[\"k-means++\"] > at_best[\"uniform\"])\nothers = np.concatenate([e[e > TOL * best] for e in final_errs.values()])\nworst = others.max()\nat_worst = {n: float(np.mean(e >= worst / TOL)) for n, e in final_errs.items()}\ncheck(f\"[B-lloyd] every other run stops at a clustering error within 1% of \"\n      f\"{worst:.4f}, {worst / best:.2f} times the best: \"\n      f\"{100 * at_worst['k-means++']:.1f}% of the k-means++ runs, \"\n      f\"{100 * at_worst['uniform']:.1f}% of the uniform runs\",\n      np.all(others >= worst / TOL)\n      and all(abs(at_best[n] + at_worst[n] - 1) < 1e-12 for n in at_best))\n# what the worse fixed point looks like, in terms of the reference clusters\ni_worst = int(np.argmax(final_errs[\"uniform\"]))\nW_bad = final_cents[\"uniform\"][i_worst]\nlab_bad = assign(X, W_bad)\nveg_split = np.sort(np.bincount(lab_bad[ref_lab == 0], minlength=3))[::-1]\nmtn_counts = np.bincount(lab_bad[ref_lab == 1], minlength=3)\nmtn_home = int(np.argmax(mtn_counts))\nmtn_share = mtn_counts[mtn_home] / np.sum(lab_bad == mtn_home)\ncheck(f\"[B-lloyd] at that fixed point the vegetation patches are split \"\n      f\"{veg_split[0]} to {veg_split[1]} between two centroids, and no \"\n      f\"centroid belongs to the mountain: its {sizes[1]} patches are divided \"\n      f\"{mtn_counts[mtn_home]} to {sizes[1] - mtn_counts[mtn_home]} between \"\n      f\"two centroids, and even the first of these has only \"\n      f\"{100 * mtn_share:.0f}% mountain patches\",\n      veg_split[1] > 100 and mtn_share < 0.5)\nit_pp, it_u = iters[\"k-means++\"].mean(), iters[\"uniform\"].mean()\ncheck(f\"[B-lloyd] iterations of Lloyd's algorithm: {it_pp:.1f} on average \"\n      f\"from k-means++ seeds, {it_u:.1f} from uniform seeds\", it_pp < it_u)\nR = 5\ncheck(f\"[B-lloyd] probability that all of {R} restarts miss the best \"\n      f\"clustering: {100 * (1 - at_best['k-means++']) ** R:.1f}% \"\n      f\"(k-means++), {100 * (1 - at_best['uniform']) ** R:.1f}% (uniform)\",\n      (1 - at_best[\"k-means++\"]) ** R < (1 - at_best[\"uniform\"]) ** R)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[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."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-plot] thinned scatter with second-seed probabilities, sorted runs\")\nSTEP = 49\nidx = np.arange(0, m, STEP)\ncheck(f\"[B-plot] every {STEP}th patch: {len(idx)} of the {m} patches are \"\n      f\"drawn\", len(idx) == 20)\np_max = p_second[idx].max()\nwith open(OUT_DIR / \"kmeanspp_patches_plot.csv\", \"w\") as fh:\n    fh.write(\"green,blue,cluster,p,ms\\n\")\n    for i in idx:\n        ms = 5.0 * np.sqrt(p_second[i] / p_max)   # marker area ~ p\n        fh.write(f\"{X[i, 0]:.4f},{X[i, 1]:.4f},{ref_lab[i]},\"\n                 f\"{p_second[i]:.6f},{ms:.3f}\\n\")\nwith open(OUT_DIR / \"kmeanspp_first_seed.csv\", \"w\") as fh:\n    fh.write(\"green,blue\\n\")\n    fh.write(f\"{X[first, 0]:.4f},{X[first, 1]:.4f}\\n\")\nfrac = (np.arange(RUNS) + 1) / RUNS\nwith open(OUT_DIR / \"kmeanspp_runs.csv\", \"w\") as fh:\n    fh.write(\"frac,seed_pp,seed_uniform,final_pp,final_uniform\\n\")\n    for r in range(RUNS):\n        fh.write(f\"{frac[r]:.3f},{np.sort(seed_errs['k-means++'])[r]:.5f},\"\n                 f\"{np.sort(seed_errs['uniform'])[r]:.5f},\"\n                 f\"{np.sort(final_errs['k-means++'])[r]:.5f},\"\n                 f\"{np.sort(final_errs['uniform'])[r]:.5f}\\n\")\ncheck(\"[B-plot] the drawn second-seed probabilities are largest for sky \"\n      \"patches and smallest for vegetation patches\",\n      p_second[idx][ref_lab[idx] == 2].min()\n      > p_second[idx][ref_lab[idx] == 0].max())\n\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.4, 3.9))\narea = 220 * p_second[idx] / p_max\nax1.scatter(X[idx, 0], X[idx, 1], s=np.maximum(area, 2), marker=\"o\",\n            facecolors=\"0.75\", edgecolors=\"black\", linewidths=0.6,\n            label=\"patch, area = probability of being seed 2\")\nax1.scatter([X[first, 0]], [X[first, 1]], marker=\"s\", s=50, color=\"black\",\n            label=\"first seed (a vegetation patch)\")\nax1.set_xlabel(\"greenness of the patch\")\nax1.set_ylabel(\"blueness of the patch\")\nax1.set_title(\"k-means++: the second seed favors far-away patches\")\nax1.legend(frameon=False, fontsize=8, loc=\"upper left\")\nax2.plot(frac, np.sort(final_errs[\"k-means++\"]), \"k-\", lw=1.4,\n         label=\"k-means++ seeds (solid)\")\nax2.plot(frac, np.sort(final_errs[\"uniform\"]), \"k--\", lw=1.4,\n         label=\"uniform seeds (dashed)\")\nax2.set_xlabel(\"fraction of the 1000 runs\")\nax2.set_ylabel(\"clustering error after Lloyd's algorithm\")\nax2.set_title(\"sorted clustering errors of 1000 runs per seeding\")\nax2.legend(frameon=False, fontsize=8, loc=\"upper left\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"kmeanspp.png\", dpi=110)\n\nn_ok = sum(ok for _, ok in report)\nprint(f\"\\n{n_ok}/{len(report)} checks pass\")\nif n_ok != len(report):\n    raise SystemExit(1)"
  }
 ]
}