{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "clusteringerror.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# clustering error \u2014 Python demo\n\nNumerical companion to the entry [clustering error](https://dictionaryofml.org/terms/clusteringerror.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 'clusteringerror'. The 366 days of 2024 at Krems are data points with the feature vector (morning minimum temperature, maximum daytime temperature). A hard clustering represents each cluster by a centroid and assigns a day to the nearest centroid; its clustering error is the average, over the days, of a loss that measures how far a day is from the centroid it is assigned to.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/clusteringerror.py`](https://dictionaryofml.org/terms/clusteringerror.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 clusteringerror.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(), \"clusteringerror.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"The clustering error of the days of one year at Krems an der Donau:\nthe average loss of a clustering, under three choices of the loss.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'clusteringerror'.  The 366\ndays of 2024 at Krems are data points with the feature vector (morning\nminimum temperature, maximum daytime temperature).  A hard clustering\nrepresents each cluster by a centroid and assigns a day to the nearest\ncentroid; its clustering error is the average, over the days, of a loss\nthat measures how far a day is from the centroid it is assigned to.\n\nThe demo checks the entry's claims: the clustering error is the average\nof a per-data-point loss, so it is a training error; Lloyd's algorithm\nnever increases it and stops at a fixed point where every centroid is\nthe mean of its days; replacing the squared Euclidean distance by the\nEuclidean distance or by the Manhattan distance changes the centroid\nupdate (geometric median, coordinate-wise median) but not the\nassignment step; adding a centroid never increases the clustering\nerror, so it falls with the number of clusters and reaches zero when\nevery day is its own cluster, which is why it cannot choose the number\nof clusters.\n\nDeterministic: Lloyd's algorithm starts from k-means++ seeds drawn with\na fixed seed and from the previous solution warm-started with one more\ncentroid.  Self-contained: numpy + matplotlib only; the GeoSphere\ndownload falls back to the committed CSV.\n\nBlocks\n------\n[B-data]      Download the daily minimum and maximum temperature of 2024\n              at Krems (GeoSphere station 3805) or read the committed\n              copy; 366 days, no missing value.\n[B-loss]      The clustering error for k = 2 centroids equals the\n              average of the per-day loss, the squared Euclidean\n              distance to the nearest centroid.\n[B-lloyd]     Lloyd's algorithm with k = 2: the clustering error never\n              increases, the assignments stop changing, and at the\n              fixed point each centroid is the mean of its days; the two\n              clusters are the cold and the warm days.\n[B-norms]     The same two clusters under the Euclidean distance\n              (centroid = geometric median, Weiszfeld's iteration) and\n              under the Manhattan distance (centroid = coordinate-wise\n              median): the assignment rule is unchanged, the centroids\n              and the error values are not.\n[B-k]         Clustering error for k = 1, ..., 8 under the squared\n              Euclidean loss: non-increasing in k (a warm start with one\n              more centroid cannot be worse), and zero at k = 366.\n[B-plot]      Every 18th day for the figure (21 of 366 days) with\n              its cluster for k = 2, the two centroids, and the error\n              curve.\n\nOutputs\n-------\nclusteringerror_weather.csv     : date, tmin, tmax (committed copy).\nclusteringerror_points_plot.csv : the 21 drawn days with their cluster.\nclusteringerror_centroids.csv   : the two centroids under each loss.\nclusteringerror_curve.csv       : k, clustering error, k = 1, ..., 8.\nclusteringerror.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 json\nimport urllib.request\nfrom pathlib import Path\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nOUT_DIR = Path(__file__).parent\n\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** Download the daily minimum and maximum temperature of 2024 at Krems (GeoSphere station 3805) or read the committed copy; 366 days, no missing value."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-data] daily minimum and maximum temperature at Krems, 2024\")\nURL = (\"https://dataset.api.hub.geosphere.at/v1/station/historical/\"\n       \"klima-v2-1d?parameters=tlmin,tlmax&station_ids=3805\"\n       \"&start=2024-01-01&end=2024-12-31\")\nCSV = OUT_DIR / \"clusteringerror_weather.csv\"\ntry:\n    with urllib.request.urlopen(URL, timeout=120) as resp:\n        payload = json.load(resp)\n    params = payload[\"features\"][0][\"properties\"][\"parameters\"]\n    records = [(stamp[:10], lo, hi)\n               for stamp, lo, hi in zip(payload[\"timestamps\"],\n                                        params[\"tlmin\"][\"data\"],\n                                        params[\"tlmax\"][\"data\"])]\n    with open(CSV, \"w\") as fh:\n        fh.write(\"date,tmin,tmax\\n\")\n        for day, lo, hi in records:\n            fh.write(f\"{day},{lo},{hi}\\n\")\n    print(f\"    downloaded {len(records)} days\")\nexcept OSError as err:\n    print(f\"    download failed ({err}); reading the committed CSV\")\n    rows = CSV.read_text().strip().splitlines()[1:]\n    records = [(d, float(a), float(b))\n               for d, a, b in (r.split(\",\") for r in rows)]\n\ncheck(\"[B-data] 366 days for 2024\", len(records) == 366)\ncheck(\"[B-data] no day is missing a temperature\",\n      all(lo is not None and hi is not None for _, lo, hi in records))\nX = np.array([[lo, hi] for _, lo, hi in records], dtype=float)\nm = len(X)\n\n\n# ---- the three losses and their centroid updates\ndef sq_euclid(x, w):\n    return np.sum((x - w) ** 2, axis=-1)\n\n\ndef euclid(x, w):\n    return np.sqrt(np.sum((x - w) ** 2, axis=-1))\n\n\ndef manhattan(x, w):\n    return np.sum(np.abs(x - w), axis=-1)\n\n\ndef geometric_median(pts, iters=200):\n    \"\"\"Weiszfeld's fixed-point iteration for the geometric median.\"\"\"\n    w = pts.mean(axis=0)\n    for _ in range(iters):\n        d = np.sqrt(np.sum((pts - w) ** 2, axis=1))\n        if np.any(d < 1e-12):\n            return pts[np.argmin(d)]\n        wts = 1.0 / d\n        w = (wts[:, None] * pts).sum(axis=0) / wts.sum()\n    return w\n\n\nLOSSES = {\n    \"squared Euclidean\": (sq_euclid, lambda pts: pts.mean(axis=0)),\n    \"Euclidean\": (euclid, geometric_median),\n    \"Manhattan\": (manhattan, lambda pts: np.median(pts, axis=0)),\n}\n\n\ndef assign(X, W, dist):\n    \"\"\"Index of the nearest centroid for every data point.\"\"\"\n    return np.argmin(np.stack([dist(X, w) for w in W], axis=1), axis=1)\n\n\ndef clustering_error(X, W, dist):\n    \"\"\"Average loss: the loss of a data point is its distance to the\n    nearest centroid.\"\"\"\n    return float(np.mean(np.min(np.stack([dist(X, w) for w in W], axis=1),\n                                axis=1)))\n\n\ndef lloyd(X, W0, dist, update, max_iter=500):\n    \"\"\"Lloyd's algorithm from the centroids W0; returns the centroids,\n    the assignments, and the clustering error after every iteration.\"\"\"\n    W = np.array(W0, dtype=float)\n    errors = [clustering_error(X, W, dist)]\n    c = assign(X, W, dist)\n    for _ in range(max_iter):\n        W_new = np.array([update(X[c == j]) if np.any(c == j) else W[j]\n                          for j in range(len(W))])\n        c_new = assign(X, W_new, dist)\n        W = W_new\n        errors.append(clustering_error(X, W, dist))\n        if np.array_equal(c_new, c):\n            c = c_new\n            break\n        c = c_new\n    return W, c, errors\n\n\ndef kmeanspp_seeds(X, k, rng):\n    W = [X[rng.integers(m)]]\n    for _ in range(1, k):\n        d2 = np.min(np.stack([sq_euclid(X, w) for w in W], axis=1), axis=1)\n        W.append(X[rng.choice(m, p=d2 / d2.sum())])\n    return np.array(W)\n\n\ndef best_clustering(X, k, dist, update, rng, warm=None, restarts=20):\n    \"\"\"Smallest clustering error over k-means++ restarts and, if given,\n    a warm start (the previous centroids plus one more).\"\"\"\n    best = None\n    starts = [kmeanspp_seeds(X, k, rng) for _ in range(restarts)]\n    if warm is not None:\n        starts.append(warm)\n    for W0 in starts:\n        W, c, errs = lloyd(X, W0, dist, update)\n        if best is None or errs[-1] < best[2][-1]:\n            best = (W, c, errs)\n    return best"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-loss]** The clustering error for k = 2 centroids equals the average of the per-day loss, the squared Euclidean distance to the nearest centroid."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-loss] the clustering error of two centroids is an average loss\")\nrng = np.random.default_rng(2024)\nW_two, c_two, errs_two = best_clustering(X, 2, sq_euclid,\n                                         LOSSES[\"squared Euclidean\"][1], rng)\nper_day = np.array([sq_euclid(x, W_two[c]) for x, c in zip(X, c_two)])\nerr_two = clustering_error(X, W_two, sq_euclid)\ncheck(f\"[B-loss] average of the per-day losses {per_day.mean():.2f} equals \"\n      f\"the clustering error {err_two:.2f}\",\n      abs(per_day.mean() - err_two) < 1e-9)\ncheck(\"[B-loss] the per-day loss is the squared distance to the NEAREST \"\n      \"centroid\", np.all(per_day <= sq_euclid(X, W_two[1 - c_two]) + 1e-12))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-lloyd]** Lloyd's algorithm with k = 2: the clustering error never increases, the assignments stop changing, and at the fixed point each centroid is the mean of its days; the two clusters are the cold and the warm days."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-lloyd] Lloyd's algorithm with k = 2\")\norder = np.argsort(X[:, 0])\nW0 = np.array([X[order[: m // 2]].mean(axis=0), X[order[m // 2:]].mean(axis=0)])\nW_l, c_l, errs_l = lloyd(X, W0, sq_euclid, LOSSES[\"squared Euclidean\"][1])\ncheck(f\"[B-lloyd] the clustering error never increases over \"\n      f\"{len(errs_l) - 1} iterations ({errs_l[0]:.2f} -> {errs_l[-1]:.2f})\",\n      all(b <= a + 1e-9 for a, b in zip(errs_l, errs_l[1:])))\ncheck(\"[B-lloyd] at the fixed point each centroid is the mean of its days\",\n      all(np.allclose(W_l[j], X[c_l == j].mean(axis=0)) for j in range(2)))\ncheck(\"[B-lloyd] the fixed point is the best of the k-means++ restarts\",\n      abs(errs_l[-1] - err_two) < 1e-6)\ncold, warm = sorted(range(2), key=lambda j: W_two[j, 1])\nn_cold, n_warm = int(np.sum(c_two == cold)), int(np.sum(c_two == warm))\ncheck(f\"[B-lloyd] cold days: centroid ({W_two[cold, 0]:.1f}, \"\n      f\"{W_two[cold, 1]:.1f}) with {n_cold} days; warm days: centroid \"\n      f\"({W_two[warm, 0]:.1f}, {W_two[warm, 1]:.1f}) with {n_warm} days\",\n      W_two[cold, 1] < 12 < W_two[warm, 1] and n_cold + n_warm == m)\nmonths = np.array([int(d[5:7]) for d, _, _ in records])\ncheck(\"[B-lloyd] every July and August day is a warm day, every January \"\n      \"and February day a cold day\",\n      np.all(c_two[np.isin(months, [7, 8])] == warm)\n      and np.all(c_two[np.isin(months, [1, 2])] == cold))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-norms]** The same two clusters under the Euclidean distance (centroid = geometric median, Weiszfeld's iteration) and under the Manhattan distance (centroid = coordinate-wise median): the assignment rule is unchanged, the centroids and the error values are not."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-norms] k = 2 under the Euclidean and the Manhattan distance\")\nresults = {\"squared Euclidean\": (W_two, c_two, err_two)}\nfor name in (\"Euclidean\", \"Manhattan\"):\n    dist, update = LOSSES[name]\n    rng = np.random.default_rng(2024)\n    W, c, errs = best_clustering(X, 2, dist, update, rng, warm=W_two)\n    results[name] = (W, c, errs[-1])\n    kind = (\"geometric median\" if name == \"Euclidean\"\n            else \"coordinate-wise median\")\n    check(f\"[B-norms] {name}: at the fixed point each centroid is the \"\n          f\"{kind} of its days\",\n          all(np.allclose(W[j], update(X[c == j]), atol=1e-3)\n              for j in range(2)))\n    agree = np.mean(c == c_two) if np.mean(c == c_two) > 0.5 \\\n        else np.mean(c != c_two)\n    check(f\"[B-norms] {name}: clustering error {errs[-1]:.2f}, centroids \"\n          f\"({W[0, 0]:.1f}, {W[0, 1]:.1f}) and ({W[1, 0]:.1f}, \"\n          f\"{W[1, 1]:.1f}); {100 * agree:.1f}% of the days keep their \"\n          f\"cluster\", agree > 0.9)\nW_e = results[\"Euclidean\"][0]\ncheck(\"[B-norms] the assignment rule is the same: nearest centroid under \"\n      \"the Euclidean distance and under its square agree for every day\",\n      np.array_equal(assign(X, W_e, euclid), assign(X, W_e, sq_euclid)))\ncheck(\"[B-norms] the Euclidean error is below the square root of the \"\n      \"squared Euclidean error (Jensen)\",\n      results[\"Euclidean\"][2] < np.sqrt(err_two))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-k]** Clustering error for k = 1, ..., 8 under the squared Euclidean loss: non-increasing in k (a warm start with one more centroid cannot be worse), and zero at k = 366."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-k] clustering error for k = 1, ..., 8 (squared Euclidean)\")\ncurve = {}\nprev = None\nfor k in range(1, 9):\n    rng = np.random.default_rng(100 + k)\n    warm_start = None\n    if prev is not None:\n        W_prev, c_prev, _ = prev\n        far = np.argmax(np.min(np.stack([sq_euclid(X, w) for w in W_prev],\n                                        axis=1), axis=1))\n        warm_start = np.vstack([W_prev, X[far]])\n    prev = best_clustering(X, k, sq_euclid, LOSSES[\"squared Euclidean\"][1],\n                           rng, warm=warm_start)\n    curve[k] = prev[2][-1]\ncheck(\"[B-k] \" + \", \".join(f\"k={k}: {curve[k]:.2f}\" for k in curve),\n      all(curve[k + 1] <= curve[k] + 1e-9 for k in range(1, 8)))\ncheck(f\"[B-k] k = 1: the clustering error {curve[1]:.2f} is the total \"\n      f\"variance of the two features\",\n      abs(curve[1] - np.sum(X.var(axis=0))) < 1e-9)\ncheck(f\"[B-k] k = 2 halves it and more ({curve[2]:.2f}); the fall from \"\n      f\"k = 2 to 8 ({curve[2] - curve[8]:.2f}) is smaller than the fall \"\n      f\"from k = 1 to 2 ({curve[1] - curve[2]:.2f})\",\n      curve[2] < curve[1] / 2 and curve[2] - curve[8] < curve[1] - curve[2])\ncheck(\"[B-k] k = 366, every day its own centroid: clustering error 0\",\n      clustering_error(X, X.copy(), sq_euclid) == 0.0)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-plot]** Every 18th day for the figure (21 of 366 days) with its cluster for k = 2, the two centroids, and the error curve."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-plot] thinned scatter, centroids, error curve\")\nidx = np.arange(0, m, 18)\nwith open(OUT_DIR / \"clusteringerror_points_plot.csv\", \"w\") as fh:\n    fh.write(\"tmin,tmax,cluster,ctmin,ctmax\\n\")\n    for i in idx:\n        j = c_two[i]\n        fh.write(f\"{X[i, 0]:.1f},{X[i, 1]:.1f},{int(j == warm)},\"\n                 f\"{W_two[j, 0]:.4f},{W_two[j, 1]:.4f}\\n\")\ncheck(f\"[B-plot] every 18th day: {len(idx)} of the {m} days are drawn\",\n      len(idx) == 21)\nwith open(OUT_DIR / \"clusteringerror_centroids.csv\", \"w\") as fh:\n    fh.write(\"lossid,loss,cluster,tmin,tmax,error\\n\")\n    for lid, (name, (W, c, e)) in enumerate(results.items()):\n        cold_j = int(np.argmin(W[:, 1]))\n        for j in (cold_j, 1 - cold_j):\n            fh.write(f\"{lid},{name},{int(j != cold_j)},{W[j, 0]:.4f},\"\n                     f\"{W[j, 1]:.4f},{e:.4f}\\n\")\nwith open(OUT_DIR / \"clusteringerror_curve.csv\", \"w\") as fh:\n    fh.write(\"k,error\\n\")\n    for k, e in curve.items():\n        fh.write(f\"{k},{e:.4f}\\n\")\n\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.4, 3.9))\nfor j, mk, lab in ((cold, \"o\", \"cold days\"), (warm, \"s\", \"warm days\")):\n    sel = idx[c_two[idx] == j]\n    ax1.scatter(X[sel, 0], X[sel, 1], marker=mk, facecolors=\"none\",\n                edgecolors=\"black\", s=28, label=f\"{lab} (every 18th day)\")\n    for i in sel:\n        ax1.plot([X[i, 0], W_two[j, 0]], [X[i, 1], W_two[j, 1]],\n                 color=\"0.6\", lw=0.6, ls=\"--\")\nax1.scatter(W_two[:, 0], W_two[:, 1], marker=\"x\", color=\"black\", s=60,\n            label=\"centroids (k = 2)\")\nax1.set_xlabel(\"morning minimum temperature (\u00b0C)\")\nax1.set_ylabel(\"maximum daytime temperature (\u00b0C)\")\nax1.set_title(\"loss of a day: squared length of its dashed line\")\nax1.legend(frameon=False, fontsize=8)\nks = sorted(curve)\nax2.plot(ks, [curve[k] for k in ks], \"ko-\")\nax2.set_xlabel(\"number of clusters k\")\nax2.set_ylabel(\"clustering error (squared Euclidean)\")\nax2.set_title(\"the clustering error only falls with k\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"clusteringerror.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)"
  }
 ]
}