{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "graphclustering.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# graph clustering \u2014 Python demo\n\nNumerical companion to the entry [graph clustering](https://dictionaryofml.org/terms/graphclustering.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 'graphclustering'. Every 18th day of 2024 at Krems (21 days) is a data point with the feature vector (morning minimum temperature, maximum daytime temperature). The days are the nodes of a weighted graph: two days are connected if one is among the six nearest neighbors of the other, and the edge weight is the Gaussian similarity exp(-||x - x'||^2 / (2 sigma^2)) of their feature vectors with sigma = 5 degrees Celsius.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/graphclustering.py`](https://dictionaryofml.org/terms/graphclustering.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 graphclustering.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(), \"graphclustering.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"Graph clustering of the days of one year at Krems an der Donau: a\nsimilarity graph over 21 days, its cut and ratio cut, and the partition\nwith the smallest ratio cut.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'graphclustering'.  Every 18th\nday of 2024 at Krems (21 days) is a data point with the feature vector\n(morning minimum temperature, maximum daytime temperature).  The days are\nthe nodes of a weighted graph: two days are connected if one is among the\nsix nearest neighbors of the other, and the edge weight is the Gaussian\nsimilarity exp(-||x - x'||^2 / (2 sigma^2)) of their feature vectors with\nsigma = 5 degrees Celsius.\n\nThe demo checks the entry's claims: the cut of a cluster is the total\nweight of the edges leaving it and equals a quadratic form of the\nLaplacian matrix; the cut of a single day is its degree, so ranked by the\ncut alone a single-day split comes second, which is why the ratio cut\ndivides each cut by the number of nodes in the cluster; with 21 nodes\nevery two-way partition can be enumerated, so the partition with the\nsmallest ratio cut is known exactly (here the cold and the warm days,\njoined by one edge); the Fiedler vector of the Laplacian matrix orders\nthe nodes so that one of the 20 cuts along this order is that partition\n(spectral clustering); and a random partition of the same sizes has a far\nlarger cut.\n\nDeterministic: the only randomness is the random partition, drawn with a\nfixed 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 2024\n              at Krems (GeoSphere station 3805) or read the committed\n              copy; keep every 18th day, 21 days.\n[B-graph]     The similarity graph: 6-nearest-neighbor edges with Gaussian\n              edge weights; symmetric, nonnegative, connected.\n[B-cut]       The cut of a cluster and its Laplacian quadratic form; the\n              smallest cut over all two-way partitions; the cut of a\n              single day is its degree.\n[B-ratiocut]  The ratio cut; its minimizer over all 2^20 two-way\n              partitions; the single-day split under the ratio cut; the\n              ratio cut and cut of a random partition.\n[B-spectral]  The Fiedler vector orders the nodes; the best of the 20 cuts\n              along this order is the exact minimizer of the ratio cut.\n[B-plot]      CSVs for the figure (nodes, edges inside the clusters, cut\n              edges, the 20 sweep cuts) and the preview.\n\nOutputs\n-------\ngraphclustering_weather.csv      : date, tmin, tmax (committed copy).\ngraphclustering_nodes_plot.csv   : the 21 days with cluster and Fiedler\n                                   entry.\ngraphclustering_edges_within.csv : edges inside a cluster as segments.\ngraphclustering_edges_cut.csv    : edges between the clusters as segments.\ngraphclustering_sweep.csv        : the 20 cuts along the Fiedler order.\ngraphclustering_random.csv       : the random partition's cut and ratio cut.\ngraphclustering.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; keep every 18th day, 21 days."
  },
  {
   "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 / \"graphclustering_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))\nSTEP = 18\nkeep = np.arange(0, len(records), STEP)\ndays = [records[i] for i in keep]\nX = np.array([[lo, hi] for _, lo, hi in days], dtype=float)\nm = len(X)\ncheck(f\"[B-data] every {STEP}th day: {m} of the {len(records)} days are \"\n      f\"the nodes\", m == 21)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-graph]** The similarity graph: 6-nearest-neighbor edges with Gaussian edge weights; symmetric, nonnegative, connected."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-graph] similarity graph over the 21 days\")\nK_NN = 6\nSIGMA = 5.0\nD2 = np.sum((X[:, None, :] - X[None, :, :]) ** 2, axis=2)\norder = np.argsort(D2 + np.diag(np.full(m, np.inf)), axis=1)\nknn = np.zeros((m, m), dtype=bool)\nfor i in range(m):\n    knn[i, order[i, :K_NN]] = True\nadjacent = knn | knn.T                       # the k-nearest neighbor graph\nA = np.where(adjacent, np.exp(-D2 / (2 * SIGMA ** 2)), 0.0)\nnp.fill_diagonal(A, 0.0)\nedges = [(i, j) for i in range(m) for j in range(i + 1, m) if adjacent[i, j]]\ncheck(f\"[B-graph] {len(edges)} edges: each day is connected to its {K_NN} \"\n      f\"nearest neighbors and to every day that counts it among its own\",\n      all(adjacent[i, j] for i in range(m) for j in order[i, :K_NN]))\ncheck(\"[B-graph] edge weights are symmetric and between 0 and 1\",\n      np.allclose(A, A.T) and np.all(A >= 0) and np.all(A <= 1)\n      and all(A[i, j] > 0 for i, j in edges))\ndegree = A.sum(axis=1)\nL = np.diag(degree) - A\ncheck(f\"[B-graph] node degrees between {degree.min():.2f} and \"\n      f\"{degree.max():.2f}; the Laplacian matrix has zero row sums\",\n      np.allclose(L.sum(axis=1), 0))\n# connectivity: breadth-first search from node 0\nseen = {0}\nfrontier = [0]\nwhile frontier:\n    i = frontier.pop()\n    for j in np.flatnonzero(adjacent[i]):\n        if j not in seen:\n            seen.add(int(j))\n            frontier.append(int(j))\ncheck(\"[B-graph] the graph is connected\", len(seen) == m)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-cut]** The cut of a cluster and its Laplacian quadratic form; the smallest cut over all two-way partitions; the cut of a single day is its degree."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-cut] the cut of a cluster\")\n\n\ndef cut(mask):\n    \"\"\"Total weight of the edges leaving the cluster given by mask.\"\"\"\n    return float(A[np.ix_(mask, ~mask)].sum())\n\n\ndef ratio_cut(mask):\n    \"\"\"Ratio cut of the two-way partition {mask, ~mask}.\"\"\"\n    return cut(mask) * (1.0 / mask.sum() + 1.0 / (~mask).sum())\n\n\n# every two-way partition: node 0 on side 0, so each partition once\ncodes = np.arange(1, 2 ** (m - 1), dtype=np.int64)       # nonempty side 1\nbits = ((codes[:, None] >> np.arange(0, m - 1)) & 1).astype(np.int8)\nside1 = np.concatenate([np.zeros((len(codes), 1), dtype=np.int8), bits],\n                       axis=1)                            # node 0 on side 0\nn1 = side1.sum(axis=1)\ncuts = np.zeros(len(codes))\nfor i, j in edges:\n    cuts += A[i, j] * (side1[:, i] != side1[:, j])\nrcuts = cuts * (1.0 / n1 + 1.0 / (m - n1))\ncheck(f\"[B-cut] all {len(codes)} two-way partitions of the {m} days \"\n      f\"enumerated\", len(codes) == 2 ** (m - 1) - 1)\n\nbest_cut = int(np.argmin(cuts))\nmask_mincut = side1[best_cut].astype(bool)\nn_cross = sum(mask_mincut[i] != mask_mincut[j] for i, j in edges)\ncheck(f\"[B-cut] the smallest cut over all partitions is {cuts[best_cut]:.3f}; \"\n      f\"it crosses {n_cross} of the {len(edges)} edges and splits the days \"\n      f\"{mask_mincut.sum()} to {m - mask_mincut.sum()}\",\n      n_cross == 1 and 5 <= mask_mincut.sum() <= m - 5)\ns = np.where(mask_mincut, 1.0, -1.0)\ncheck(\"[B-cut] cut(C) = (1/4) s^T L s for the sign vector s of the \"\n      \"partition\", abs(cut(mask_mincut) - 0.25 * s @ L @ s) < 1e-9)\ni_min = int(np.argmin(degree))\nsingle = np.zeros(m, dtype=bool)\nsingle[i_min] = True\nrank_cut_single = int(np.sum(cuts < cut(single) - 1e-12)) + 1\ncheck(f\"[B-cut] the cut of a single day is its degree; the day with the \"\n      f\"smallest degree ({days[i_min][0]}, degree {degree[i_min]:.3f}) has \"\n      f\"the {rank_cut_single}nd smallest cut of all {len(codes)} partitions\",\n      abs(cut(single) - degree[i_min]) < 1e-9 and rank_cut_single == 2)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-ratiocut]** The ratio cut; its minimizer over all 2^20 two-way partitions; the single-day split under the ratio cut; the ratio cut and cut of a random partition."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-ratiocut] the ratio cut over all two-way partitions\")\nbest_rc = int(np.argmin(rcuts))\nmask_opt = side1[best_rc].astype(bool)\ncold = mask_opt if X[mask_opt, 1].mean() < X[~mask_opt, 1].mean() \\\n    else ~mask_opt                            # the colder side is cluster 0\nwarm = ~cold\nrc_opt, cut_opt = ratio_cut(cold), cut(cold)\ncheck(f\"[B-ratiocut] the smallest ratio cut is {rc_opt:.3f}, for a cold \"\n      f\"cluster of {cold.sum()} days and a warm cluster of {warm.sum()} \"\n      f\"days; it is the partition with the smallest cut, {cut_opt:.3f}\",\n      abs(rcuts[best_rc] - rc_opt) < 1e-9\n      and np.array_equal(mask_opt, mask_mincut))\ncut_edges = [(i, j) for i, j in edges if cold[i] != cold[j]]\ni_c, j_c = cut_edges[0]\ncheck(f\"[B-ratiocut] the one cut edge joins {days[i_c][0]} and \"\n      f\"{days[j_c][0]} with weight {A[i_c, j_c]:.3f}\",\n      len(cut_edges) == 1 and abs(A[i_c, j_c] - cut_opt) < 1e-9)\nrank_rc_single = int(np.sum(rcuts < ratio_cut(single) - 1e-12)) + 1\ncheck(f\"[B-ratiocut] splitting off the single day {days[i_min][0]} has \"\n      f\"ratio cut {ratio_cut(single):.3f}, {ratio_cut(single) / rc_opt:.0f} \"\n      f\"times the smallest; ranked by the ratio cut it falls from 2nd to \"\n      f\"{rank_rc_single}th place\",\n      rank_rc_single > 10 and ratio_cut(single) > 10 * rc_opt)\nmonths = np.array([int(d[0][5:7]) for d in days])\ncheck(\"[B-ratiocut] every January, February, and December day is a cold \"\n      \"day, every June, July, and August day a warm day\",\n      np.all(cold[np.isin(months, [1, 2, 12])])\n      and np.all(warm[np.isin(months, [6, 7, 8])]))\n# with 5 nearest neighbors the graph falls apart into these two clusters\nknn5 = np.zeros((m, m), dtype=bool)\nfor i in range(m):\n    knn5[i, order[i, :K_NN - 1]] = True\nadj5 = knn5 | knn5.T\ncheck(f\"[B-ratiocut] with {K_NN - 1} nearest neighbors no edge joins the two \"\n      f\"clusters: they are the connected components of that graph\",\n      not np.any(adj5[np.ix_(cold, warm)]))\n\nrng = np.random.default_rng(2024)\nperm = rng.permutation(m)\nmask_rand = np.zeros(m, dtype=bool)\nmask_rand[perm[: cold.sum()]] = True          # same sizes as the clusters\nrc_rand, cut_rand = ratio_cut(mask_rand), cut(mask_rand)\nn_cross_rand = sum(mask_rand[i] != mask_rand[j] for i, j in edges)\ncheck(f\"[B-ratiocut] a random partition of the same sizes cuts \"\n      f\"{n_cross_rand} edges: cut {cut_rand:.1f} and ratio cut \"\n      f\"{rc_rand:.2f}, {rc_rand / rc_opt:.0f} times the smallest\",\n      rc_rand > 20 * rc_opt)\nsame = n1 == cold.sum()\ncheck(f\"[B-ratiocut] over all {same.sum()} partitions of these sizes the \"\n      f\"ratio cut averages {rcuts[same].mean():.2f}; the second smallest \"\n      f\"is {np.sort(rcuts[same])[1]:.3f}\",\n      rcuts[same].mean() > 20 * rc_opt and np.sort(rcuts[same])[1] > 5 * rc_opt)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-spectral]** The Fiedler vector orders the nodes; the best of the 20 cuts along this order is the exact minimizer of the ratio cut."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-spectral] spectral clustering: sweep cuts along the Fiedler vector\")\neigval, eigvec = np.linalg.eigh(L)\ncheck(f\"[B-spectral] eigenvalues of the Laplacian matrix: smallest \"\n      f\"{eigval[0]:.1e} (zero), second smallest {eigval[1]:.3f}\",\n      abs(eigval[0]) < 1e-9 and eigval[1] > 1e-6)\nfiedler = eigvec[:, 1]\nif fiedler[np.argmin(X[:, 1])] > 0:\n    fiedler = -fiedler                        # cold days on the negative side\nrank = np.argsort(fiedler)\nsweep = []\nfor n_first in range(1, m):\n    mask = np.zeros(m, dtype=bool)\n    mask[rank[:n_first]] = True\n    sweep.append((n_first, cut(mask), ratio_cut(mask)))\nsweep = np.array(sweep)\nj_best = int(np.argmin(sweep[:, 2]))\nmask_sweep = np.zeros(m, dtype=bool)\nmask_sweep[rank[: int(sweep[j_best, 0])]] = True\ncheck(f\"[B-spectral] the best of the {m - 1} sweep cuts puts the \"\n      f\"{int(sweep[j_best, 0])} most negative entries on one side; it is the \"\n      f\"exact minimizer of the ratio cut\", np.array_equal(mask_sweep, cold))\nmask_sign = fiedler < 0\ncheck(\"[B-spectral] the sign cut (negative entries versus positive) is the \"\n      \"same partition\", np.array_equal(mask_sign, cold))\ncheck(f\"[B-spectral] the ratio cut along the order rises to \"\n      f\"{sweep[:, 2].max():.2f} for a cut through a cluster and is \"\n      f\"{sweep[0, 2]:.2f} and {sweep[-1, 2]:.2f} for the two single-day cuts\",\n      sweep[:, 2].max() > 20 * rc_opt and min(sweep[0, 2], sweep[-1, 2]) > 10 * rc_opt)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-plot]** CSVs for the figure (nodes, edges inside the clusters, cut edges, the 20 sweep cuts) and the preview."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-plot] nodes, edges, sweep cuts\")\nwith open(OUT_DIR / \"graphclustering_nodes_plot.csv\", \"w\") as fh:\n    fh.write(\"tmin,tmax,cluster,fiedler\\n\")\n    for i in range(m):\n        fh.write(f\"{X[i, 0]:.1f},{X[i, 1]:.1f},{int(warm[i])},\"\n                 f\"{fiedler[i]:.4f}\\n\")\nfor name, sel in ((\"within\", [e for e in edges if e not in cut_edges]),\n                  (\"cut\", cut_edges)):\n    with open(OUT_DIR / f\"graphclustering_edges_{name}.csv\", \"w\") as fh:\n        fh.write(\"x,y,u,v,weight\\n\")\n        for i, j in sel:\n            fh.write(f\"{X[i, 0]:.1f},{X[i, 1]:.1f},{X[j, 0] - X[i, 0]:.1f},\"\n                     f\"{X[j, 1] - X[i, 1]:.1f},{A[i, j]:.4f}\\n\")\nwith open(OUT_DIR / \"graphclustering_sweep.csv\", \"w\") as fh:\n    fh.write(\"nfirst,cut,ratiocut\\n\")\n    for n_first, c, rc in sweep:\n        fh.write(f\"{int(n_first)},{c:.4f},{rc:.4f}\\n\")\nwith open(OUT_DIR / \"graphclustering_random.csv\", \"w\") as fh:\n    fh.write(\"nfirst,cut,ratiocut\\n\")          # the random partition, as a line\n    for n_first in (1, m - 1):\n        fh.write(f\"{n_first},{cut_rand:.4f},{rc_rand:.4f}\\n\")\ncheck(f\"[B-plot] {m} nodes, {len(edges) - len(cut_edges)} edges inside the \"\n      f\"clusters, {len(cut_edges)} cut edges, {m - 1} sweep cuts written\",\n      len(sweep) == m - 1)\n\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.4, 3.9))\nfor i, j in edges:\n    if cold[i] != cold[j]:\n        ax1.plot(X[[i, j], 0], X[[i, j], 1], color=\"black\", lw=1.2, ls=\"--\")\n    else:\n        ax1.plot(X[[i, j], 0], X[[i, j], 1], color=\"0.6\", lw=0.8)\nax1.scatter(X[cold, 0], X[cold, 1], marker=\"o\", facecolors=\"white\",\n            edgecolors=\"black\", s=30, zorder=3, label=\"cold days (circles)\")\nax1.scatter(X[warm, 0], X[warm, 1], marker=\"s\", facecolors=\"white\",\n            edgecolors=\"black\", s=30, zorder=3, label=\"warm days (squares)\")\nax1.plot([], [], color=\"0.6\", lw=0.8, label=\"edge inside a cluster\")\nax1.plot([], [], color=\"black\", lw=1.2, ls=\"--\", label=\"cut edge\")\nax1.set_xlabel(\"morning minimum temperature (\u00b0C)\")\nax1.set_ylabel(\"maximum daytime temperature (\u00b0C)\")\nax1.set_title(\"similarity graph over 21 days and its best ratio cut\")\nax1.legend(frameon=False, fontsize=8)\nax2.plot(sweep[:, 0], sweep[:, 2], \"ko-\", ms=3, label=\"sweep cuts\")\nax2.axhline(rc_rand, color=\"black\", ls=\"--\", lw=0.8,\n            label=\"random partition\")\nax2.set_xlabel(\"number of days on the negative side of the Fiedler vector\")\nax2.set_ylabel(\"ratio cut\")\nax2.set_title(\"ratio cut of the 20 cuts along the Fiedler order\")\nax2.legend(frameon=False, fontsize=8)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"graphclustering.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)"
  }
 ]
}