{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "hardclustering.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# hard clustering \u2014 Python demo\n\nNumerical companion to the entry [hard clustering](https://dictionaryofml.org/terms/hardclustering.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 'hardclustering'. The 366 days of 2024 at Krems are data points with the feature vector (morning minimum temperature, maximum daytime temperature). A hard clustering puts every day into exactly one of k clusters, so the clusters are disjoint subsets whose union is the data set. The cluster assignment is a label-like output: an index in {1, ..., k} for every day, or the one-hot vector that is the special case of a degree of belonging.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/hardclustering.py`](https://dictionaryofml.org/terms/hardclustering.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 hardclustering.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(), \"hardclustering.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"A hard clustering of the days of one year at Krems an der Donau:\na partition of the data set, the cluster assignment as a label-like\noutput, and its evaluation against a reference partition.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'hardclustering'.  The 366\ndays of 2024 at Krems are data points with the feature vector (morning\nminimum temperature, maximum daytime temperature).  A hard clustering\nputs every day into exactly one of k clusters, so the clusters are\ndisjoint subsets whose union is the data set.  The cluster assignment\nis a label-like output: an index in {1, ..., k} for every day, or the\none-hot vector that is the special case of a degree of belonging.\n\nThe demo checks the entry's claims: k-means with k = 2 delivers a\npartition of the days into cold and warm days; the one-hot vectors\nare the vertices of the probability simplex; the boundary between the\ntwo clusters is a hyperplane, so each cluster is a convex region of the\nfeature space; the cluster indices carry no meaning beyond the\npartition, so comparing the hard clustering with a reference partition\n(the cold half-year Oct-Mar and the warm half-year Apr-Sep) uses the\nbest matching of the indices or counts pairs of days, which is the Rand\nindex; and with k = 4 against the four seasons the agreement is lower,\nbecause spring and autumn days have the same temperatures.\n\nDeterministic: Lloyd's algorithm starts from k-means++ seeds drawn with\na fixed seed.  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\n               2024 at Krems (GeoSphere station 3805) or read the\n               committed copy; 366 days, no missing value.\n[B-partition]  k-means with k = 2: the two clusters are disjoint and\n               cover every day, and the one-hot vectors of the days have\n               exactly one entry 1 and sum to 1.\n[B-boundary]   The boundary between the two clusters is the\n               perpendicular bisector of the two centroids: every day\n               lies on the side of its own centroid.\n[B-eval]       The hard clustering against the reference partition\n               into half-years: contingency table, best-matching\n               accuracy, and the Rand index, which does not change when\n               the cluster indices are swapped.\n[B-seasons]    k = 4 against the four seasons: the best-matching\n               accuracy drops, since spring and autumn days share one\n               cluster.\n[B-plot]       Every 18th day for the figure (21 of 366 days) with its\n               cluster, the two centroids, the boundary, and the\n               per-month counts of days in the warm cluster.\n\nOutputs\n-------\nhardclustering_weather.csv      : date, tmin, tmax (committed copy).\nhardclustering_points_plot.csv  : the 21 drawn days with their cluster.\nhardclustering_centroids.csv    : the two centroids (k = 2).\nhardclustering_boundary.csv     : two points on the boundary line.\nhardclustering_months.csv       : month, days, days in the warm cluster.\nhardclustering.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 itertools\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 / \"hardclustering_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)\nmonths = np.array([int(d[5:7]) for d, _, _ in records])\n\n\n# ---- k-means: Lloyd's algorithm from k-means++ seeds\ndef sq_euclid(x, w):\n    return np.sum((x - w) ** 2, axis=-1)\n\n\ndef assign(X, W):\n    \"\"\"Index of the nearest centroid for every data point.\"\"\"\n    return np.argmin(np.stack([sq_euclid(X, w) for w in W], axis=1), axis=1)\n\n\ndef clustering_error(X, W):\n    return float(np.mean(np.min(np.stack([sq_euclid(X, w) for w in W],\n                                         axis=1), axis=1)))\n\n\ndef lloyd(X, W0, max_iter=500):\n    W = np.array(W0, dtype=float)\n    c = assign(X, W)\n    for _ in range(max_iter):\n        W = np.array([X[c == j].mean(axis=0) if np.any(c == j) else W[j]\n                      for j in range(len(W))])\n        c_new = assign(X, W)\n        if np.array_equal(c_new, c):\n            break\n        c = c_new\n    return W, c\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 kmeans(X, k, seed, restarts=20):\n    \"\"\"Smallest clustering error over k-means++ restarts.\"\"\"\n    rng = np.random.default_rng(seed)\n    best = None\n    for _ in range(restarts):\n        W, c = lloyd(X, kmeanspp_seeds(X, k, rng))\n        err = clustering_error(X, W)\n        if best is None or err < best[2]:\n            best = (W, c, err)\n    return best"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-partition]** k-means with k = 2: the two clusters are disjoint and cover every day, and the one-hot vectors of the days have exactly one entry 1 and sum to 1."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-partition] k-means with k = 2 delivers a partition of the days\")\nW2, c2, err2 = kmeans(X, 2, seed=2024)\ncold, warm = sorted(range(2), key=lambda j: W2[j, 1])\nclusters = [set(np.flatnonzero(c2 == j)) for j in range(2)]\ncheck(f\"[B-partition] the two clusters are disjoint and cover all {m} days \"\n      f\"({len(clusters[cold])} cold days, {len(clusters[warm])} warm days)\",\n      not (clusters[0] & clusters[1])\n      and clusters[0] | clusters[1] == set(range(m)))\ncheck(f\"[B-partition] cold days: centroid ({W2[cold, 0]:.1f}, \"\n      f\"{W2[cold, 1]:.1f}); warm days: centroid ({W2[warm, 0]:.1f}, \"\n      f\"{W2[warm, 1]:.1f}); clustering error {err2:.1f}\",\n      W2[cold, 1] < W2[warm, 1])\nU = np.zeros((m, 2))\nU[np.arange(m), c2] = 1.0\ncheck(\"[B-partition] the one-hot vector of every day has entries in {0, 1} \"\n      \"and sums to 1: a vertex of the probability simplex\",\n      np.all(np.isin(U, (0.0, 1.0))) and np.all(U.sum(axis=1) == 1.0)\n      and np.all(U.max(axis=1) == 1.0))\ncheck(\"[B-partition] the cluster index of a day is the position of the 1 \"\n      \"in its one-hot vector\", np.array_equal(np.argmax(U, axis=1), c2))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-boundary]** The boundary between the two clusters is the perpendicular bisector of the two centroids: every day lies on the side of its own centroid."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-boundary] the two clusters are separated by a straight line\")\nmid = W2.mean(axis=0)\nnormal = W2[warm] - W2[cold]\nside = (X - mid) @ normal          # > 0 on the warm side\ncheck(\"[B-boundary] every day lies on the side of the perpendicular \"\n      \"bisector of the centroids that holds its own centroid\",\n      np.all((side > 0) == (c2 == warm)) and np.all(side != 0))\nclosest = int(np.argmin(np.abs(side) / np.linalg.norm(normal)))\ncheck(f\"[B-boundary] the day nearest the boundary, {records[closest][0]}, \"\n      f\"is {np.abs(side[closest]) / np.linalg.norm(normal):.2f} degrees \"\n      \"from it\", True)\n# two points on the line, where it leaves the plotting window\ndirection = np.array([-normal[1], normal[0]]) / np.linalg.norm(normal)\nt_lo, t_hi = -np.inf, np.inf\nfor lo, hi, j in ((-9.0, 23.0, 0), (0.0, 50.0, 1)):\n    t_a, t_b = sorted(((lo - mid[j]) / direction[j],\n                       (hi - mid[j]) / direction[j]))\n    t_lo, t_hi = max(t_lo, t_a), min(t_hi, t_b)\nboundary = np.array([mid + t_lo * direction, mid + t_hi * direction])"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-eval]** The hard clustering against the reference partition into half-years: contingency table, best-matching accuracy, and the Rand index, which does not change when the cluster indices are swapped."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-eval] the hard clustering against the half-years Oct-Mar / Apr-Sep\")\nref2 = np.isin(months, [4, 5, 6, 7, 8, 9]).astype(int)   # 1 = warm half-year\ncheck(f\"[B-eval] the reference partition has {np.sum(ref2 == 0)} days in \"\n      f\"the cold half-year and {np.sum(ref2 == 1)} in the warm one\",\n      np.sum(ref2 == 0) == 183 and np.sum(ref2 == 1) == 183)\ntable = np.array([[np.sum((c2 == a) & (ref2 == b)) for b in (0, 1)]\n                  for a in (cold, warm)])\ncheck(f\"[B-eval] contingency table (rows: cold, warm cluster; columns: \"\n      f\"cold, warm half-year): {table.tolist()}\", table.sum() == m)\n\n\ndef best_matching_accuracy(c, ref, k):\n    \"\"\"Largest fraction of agreeing days over all bijections of the\n    cluster indices onto the reference indices.\"\"\"\n    best = 0.0\n    for perm in itertools.permutations(range(k)):\n        relabeled = np.array(perm)[c]\n        best = max(best, float(np.mean(relabeled == ref)))\n    return best\n\n\nacc2 = best_matching_accuracy(c2, ref2, 2)\nraw_agree = float(np.mean(c2 == ref2))\nswapped = float(np.mean((1 - c2) == ref2))\ncheck(f\"[B-eval] best-matching accuracy {100 * acc2:.1f}%: the indices as \"\n      f\"found agree on {100 * raw_agree:.1f}% of the days, swapped on \"\n      f\"{100 * swapped:.1f}%\", abs(acc2 - max(raw_agree, swapped)) < 1e-12)\n\n\ndef pair_counts(c, ref):\n    \"\"\"Numbers of pairs of data points in the same cluster in both\n    partitions (a), in the same cluster only in c (b), only in ref (d),\n    and in different clusters in both (e).\"\"\"\n    same_c = c[:, None] == c[None, :]\n    same_r = ref[:, None] == ref[None, :]\n    upper = np.triu(np.ones((len(c), len(c)), dtype=bool), 1)\n    a = int(np.sum(same_c & same_r & upper))\n    b = int(np.sum(same_c & ~same_r & upper))\n    d = int(np.sum(~same_c & same_r & upper))\n    e = int(np.sum(~same_c & ~same_r & upper))\n    return a, b, d, e\n\n\ndef rand_index(c, ref):\n    a, b, d, e = pair_counts(c, ref)\n    return (a + e) / (a + b + d + e)\n\n\na, b, d, e = pair_counts(c2, ref2)\nri2 = rand_index(c2, ref2)\ncheck(f\"[B-eval] of the {m * (m - 1) // 2} pairs of days, {a} are together \"\n      f\"in both partitions and {e} apart in both; Rand index \"\n      f\"{ri2:.3f}\", a + b + d + e == m * (m - 1) // 2)\ncheck(\"[B-eval] the Rand index from the contingency table equals the pair \"\n      \"count\",\n      abs(ri2 - (sum(n * (n - 1) // 2 for n in table.ravel()) * 2\n                 - sum(n * (n - 1) // 2 for n in table.sum(axis=1))\n                 - sum(n * (n - 1) // 2 for n in table.sum(axis=0))\n                 + m * (m - 1) // 2) / (m * (m - 1) // 2)) < 1e-12)\ncheck(\"[B-eval] swapping the two cluster indices leaves the Rand index \"\n      \"unchanged\", abs(rand_index(1 - c2, ref2) - ri2) < 1e-12)\ncheck(\"[B-eval] a reference partition compared with itself has Rand \"\n      \"index 1\", rand_index(ref2, ref2) == 1.0)\nwhole = [mo for mo in range(1, 13)\n         if len(set(c2[months == mo])) == 1]\nnames = [\"Jan\", \"Feb\", \"Mar\", \"Apr\", \"May\", \"Jun\", \"Jul\", \"Aug\", \"Sep\",\n         \"Oct\", \"Nov\", \"Dec\"]\nwhole_cold = [names[mo - 1] for mo in whole if c2[months == mo][0] == cold]\nwhole_warm = [names[mo - 1] for mo in whole if c2[months == mo][0] == warm]\ncheck(f\"[B-eval] months entirely in the cold cluster: {whole_cold}; \"\n      f\"entirely in the warm cluster: {whole_warm}\", len(whole) >= 4)\nwarm_per_month = np.array([int(np.sum(c2[months == mo] == warm))\n                           for mo in range(1, 13)])\ndays_per_month = np.array([int(np.sum(months == mo)) for mo in range(1, 13)])\nmixed = [f\"{names[mo - 1]} {warm_per_month[mo - 1]}/{days_per_month[mo - 1]}\"\n         for mo in range(1, 13)\n         if 0 < warm_per_month[mo - 1] < days_per_month[mo - 1]]\ncheck(f\"[B-eval] days in the warm cluster in the mixed months: {mixed}\",\n      len(mixed) >= 2)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-seasons]** k = 4 against the four seasons: the best-matching accuracy drops, since spring and autumn days share one cluster."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-seasons] k = 4 against the seasons DJF, MAM, JJA, SON\")\nW4, c4, err4 = kmeans(X, 4, seed=2024)\nseason = np.array([{12: 0, 1: 0, 2: 0, 3: 1, 4: 1, 5: 1, 6: 2, 7: 2, 8: 2,\n                    9: 3, 10: 3, 11: 3}[mo] for mo in months])\nacc4 = best_matching_accuracy(c4, season, 4)\nri4 = rand_index(c4, season)\ncheck(f\"[B-seasons] clustering error {err4:.1f}; best-matching accuracy \"\n      f\"{100 * acc4:.1f}% and Rand index {ri4:.3f}, both below the k = 2 \"\n      f\"values\", acc4 < acc2 and ri4 < ri2)\n# the cluster that holds most spring days: how many of its days are autumn?\nspring_cluster = int(np.argmax([np.sum((c4 == j) & (season == 1))\n                                for j in range(4)]))\nin_cl = c4 == spring_cluster\nshare = {names_s: float(np.mean(season[in_cl] == s))\n         for names_s, s in ((\"spring\", 1), (\"autumn\", 3))}\ncheck(f\"[B-seasons] the cluster with most spring days holds {np.sum(in_cl)} \"\n      f\"days, {100 * share['spring']:.0f}% of them spring and \"\n      f\"{100 * share['autumn']:.0f}% autumn days\", share[\"autumn\"] > 0.2)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-plot]** Every 18th day for the figure (21 of 366 days) with its cluster, the two centroids, the boundary, and the per-month counts of days in the warm cluster."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-plot] thinned scatter, centroids, boundary, per-month counts\")\nidx = np.arange(0, m, 18)\nwith open(OUT_DIR / \"hardclustering_points_plot.csv\", \"w\") as fh:\n    fh.write(\"tmin,tmax,cluster\\n\")\n    for i in idx:\n        fh.write(f\"{X[i, 0]:.1f},{X[i, 1]:.1f},{int(c2[i] == warm)}\\n\")\ncheck(f\"[B-plot] every 18th day: {len(idx)} of the {m} days are drawn\",\n      len(idx) == 21)\nwith open(OUT_DIR / \"hardclustering_centroids.csv\", \"w\") as fh:\n    fh.write(\"cluster,tmin,tmax\\n\")\n    for lab, j in ((0, cold), (1, warm)):\n        fh.write(f\"{lab},{W2[j, 0]:.4f},{W2[j, 1]:.4f}\\n\")\nwith open(OUT_DIR / \"hardclustering_boundary.csv\", \"w\") as fh:\n    fh.write(\"tmin,tmax\\n\")\n    for p in boundary:\n        fh.write(f\"{p[0]:.4f},{p[1]:.4f}\\n\")\nwith open(OUT_DIR / \"hardclustering_months.csv\", \"w\") as fh:\n    fh.write(\"month,name,days,warmdays,colddays\\n\")\n    for mo in range(1, 13):\n        fh.write(f\"{mo},{names[mo - 1]},{days_per_month[mo - 1]},\"\n                 f\"{warm_per_month[mo - 1]},\"\n                 f\"{days_per_month[mo - 1] - warm_per_month[mo - 1]}\\n\")\n\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.6, 3.9))\nfor j, mk, lab in ((cold, \"o\", \"cold days\"), (warm, \"s\", \"warm days\")):\n    sel = idx[c2[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)\")\nax1.plot(boundary[:, 0], boundary[:, 1], \"k--\", lw=1,\n         label=\"boundary between the clusters\")\nax1.scatter(W2[:, 0], W2[:, 1], marker=\"x\", color=\"black\", s=60,\n            label=\"cluster centroids\")\nax1.set_xlim(-9, 23)\nax1.set_ylim(0, 50)\nax1.set_xlabel(\"morning minimum temperature (\u00b0C)\")\nax1.set_ylabel(\"maximum daytime temperature (\u00b0C)\")\nax1.set_title(\"hard clustering: each day in exactly one cluster\")\nax1.legend(frameon=False, fontsize=8, loc=\"upper left\")\npos = np.arange(1, 13)\nax2.bar(pos, warm_per_month, width=0.6, color=\"black\",\n        label=\"days in the warm cluster (bars)\")\nax2.plot(pos, days_per_month, linestyle=\"none\", marker=\"_\", markersize=14,\n         markeredgewidth=1.5, color=\"black\",\n         label=\"days of the month (horizontal ticks)\")\nax2.set_xticks(pos)\nax2.set_xticklabels(names, fontsize=7)\nax2.set_ylim(0, 44)\nax2.set_xlabel(\"month of 2024\")\nax2.set_ylabel(\"number of days\")\nax2.set_title(\"the warm cluster against the warm half-year Apr-Sep\")\nax2.legend(frameon=False, fontsize=8, loc=\"upper left\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"hardclustering.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)"
  }
 ]
}