{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "decisiontree.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# decision tree \u2014 Python demo\n\nNumerical companion to the entry [decision tree](https://dictionaryofml.org/terms/decisiontree.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nA single depth-2 regression tree is trained, in the CART fashion the entry describes, on actual weather measurements from the open data server of the Finnish Meteorological Institute (FMI): the 366 days of 2024 at the Helsinki Kaisaniemi station, with the daily minimum temperature as the feature and the daily maximum temperature as the label. Growing the tree greedily \u2014 each split chooses the threshold that most reduces the variance of the labels routed to the children \u2014 yields a piecewise constant hypothesis with four pieces, one per leaf node.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/decisiontree.py`](https://dictionaryofml.org/terms/decisiontree.py); CC BY 4.0."
  },
  {
   "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(), \"decisiontree.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"decisiontree.py \u2014 numerical companion to the glossary entry\n'decisiontree' (decision tree).\n\nA single depth-2 regression tree is trained, in the CART fashion the\nentry describes, on actual weather measurements from the open data\nserver of the Finnish Meteorological Institute (FMI): the 366 days of\n2024 at the Helsinki Kaisaniemi station, with the daily minimum\ntemperature as the feature and the daily maximum temperature as the\nlabel.  Growing the tree greedily \u2014 each split chooses the threshold\nthat most reduces the variance of the labels routed to the children \u2014\nyields a piecewise constant hypothesis with four pieces, one per leaf\nnode.\n\nBlocks\n------\n[B-fetch]   Download the 366 daily temperature pairs for 2024 from the\n            FMI open data server and write them to\n            decisiontree_weather.csv; check the count and one pinned\n            measurement.\n[B-tree]    Grow a depth-2 regression tree by greedy variance\n            splitting; check that the hypothesis is piecewise constant\n            with at most four pieces, that each split reduced the\n            variance, and that the tree predicts the label far better\n            than a constant.\n[B-picture] Write the scatterplot and the step-function curve read by\n            the entry's figure (decisiontree_scatter.csv,\n            decisiontree_curve.csv).\n\nDeterministic: historical measurements, greedy splits, no randomness.\nSelf-contained: numpy + matplotlib only (stdlib urllib for the\ndownload).\n\nOutputs\n-------\ndecisiontree_weather.csv : day, tmin, tmax for the 366 days of 2024\ndecisiontree_scatter.csv : tmin, tmax of the 366 days\ndecisiontree_curve.csv   : tmin, pred -- the tree's step function\ndecisiontree.png         : preview (checking only) -- the scatterplot\n                           with the depth-2 tree's step function\n\"\"\"\n\nimport re\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-fetch]** Download the 366 daily temperature pairs for 2024 from the FMI open data server and write them to decisiontree_weather.csv; check the count and one pinned measurement."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "URL = (\"https://opendata.fmi.fi/wfs?service=WFS&version=2.0.0\"\n       \"&request=getFeature\"\n       \"&storedquery_id=fmi::observations::weather::daily::simple\"\n       \"&fmisid=100971&starttime=2024-01-01T00:00:00Z\"\n       \"&endtime=2024-12-31T00:00:00Z&parameters=tmin,tmax\")\nwith urllib.request.urlopen(URL, timeout=120) as resp:\n    xml = resp.read().decode()\ntriples = re.findall(\n    r\"<BsWfs:Time>(\\S+?)T.*?</BsWfs:Time>\\s*\"\n    r\"<BsWfs:ParameterName>(\\w+)</BsWfs:ParameterName>\\s*\"\n    r\"<BsWfs:ParameterValue>(\\S+)</BsWfs:ParameterValue>\", xml, re.S)\nrows = {}\nfor day, name, value in triples:\n    rows.setdefault(day, {})[name] = float(value)\ndays = sorted(rows)\ntmin = np.array([rows[d][\"tmin\"] for d in days])\ntmax = np.array([rows[d][\"tmax\"] for d in days])\nwith open(OUT_DIR / \"decisiontree_weather.csv\", \"w\") as f:\n    f.write(\"day,tmin,tmax\\n\")\n    for d in days:\n        f.write(f\"{d},{rows[d]['tmin']:.1f},{rows[d]['tmax']:.1f}\\n\")\ncheck(\"[B-fetch] 366 daily temperature pairs downloaded for 2024\",\n      len(days) == 366)\ncheck(\"[B-fetch] the record matches the archive \"\n      \"(May 2: 4.5 to 14.5 degrees)\",\n      rows[\"2024-05-02\"][\"tmin\"] == 4.5\n      and rows[\"2024-05-02\"][\"tmax\"] == 14.5)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-tree]** Grow a depth-2 regression tree by greedy variance splitting; check that the hypothesis is piecewise constant with at most four pieces, that each split reduced the variance, and that the tree predicts the label far better than a constant."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "MINLEAF = 20\n\n\ndef best_split(x, y):\n    \"\"\"Threshold minimizing the summed squared error of the two parts.\"\"\"\n    order = np.argsort(x)\n    xs, ys = x[order], y[order]\n    best, best_sse = None, np.inf\n    for i in range(MINLEAF, len(xs) - MINLEAF + 1):\n        if xs[i - 1] == xs[i]:\n            continue\n        left, right = ys[:i], ys[i:]\n        sse = ((left - left.mean()) ** 2).sum() \\\n            + ((right - right.mean()) ** 2).sum()\n        if sse < best_sse:\n            best_sse, best = sse, (xs[i - 1] + xs[i]) / 2\n    return best, best_sse\n\n\nroot_t, root_sse = best_split(tmin, tmax)\ncuts = [root_t]\nfor side in (tmin <= root_t, tmin > root_t):\n    t, _ = best_split(tmin[side], tmax[side])\n    if t is not None:\n        cuts.append(t)\ncuts = sorted(cuts)\nedges = [-np.inf] + cuts + [np.inf]\nmeans = np.array([tmax[(tmin > lo) & (tmin <= hi)].mean()\n                  for lo, hi in zip(edges[:-1], edges[1:])])\n\n\ndef predict(xq):\n    return means[np.searchsorted(np.array(cuts), xq)]\n\n\nerr_tree = float(np.mean((tmax - predict(tmin)) ** 2))\nerr_const = float(np.var(tmax))\nprint(f\"    thresholds {[round(c, 2) for c in cuts]}, \"\n      f\"leaf values {[round(m, 1) for m in means]}\")\nprint(f\"    average squared error: tree {err_tree:.1f}, \"\n      f\"constant {err_const:.1f}\")\ncheck(\"[B-tree] the hypothesis is piecewise constant with at most \"\n      \"four pieces\", len(means) <= 4)\ncheck(\"[B-tree] the root split reduced the variance of the labels\",\n      root_sse < err_const * len(tmax))\ncheck(\"[B-tree] the tree predicts the label far better than a constant\",\n      err_tree < err_const / 3)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-picture]** Write the scatterplot and the step-function curve read by the entry's figure (decisiontree_scatter.csv, decisiontree_curve.csv)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "np.savetxt(OUT_DIR / \"decisiontree_scatter.csv\",\n           np.stack([tmin, tmax], 1),\n           delimiter=\",\", header=\"tmin,tmax\", comments=\"\", fmt=\"%.1f\")\nbounds = [tmin.min() - 0.5] + cuts + [tmin.max() + 0.5]\ngx, gy = [], []\nfor k, (lo, hi) in enumerate(zip(bounds[:-1], bounds[1:])):\n    gx += [lo, hi]\n    gy += [means[k], means[k]]\ngx, gy = np.array(gx), np.array(gy)\nnp.savetxt(OUT_DIR / \"decisiontree_curve.csv\",\n           np.stack([gx, gy], 1),\n           delimiter=\",\", header=\"tmin,pred\", comments=\"\", fmt=\"%.2f\")\ncheck(\"[B-picture] the written curve has one constant level per leaf\",\n      len(set(np.round(gy, 4))) == len(means))\n\nfig, ax = plt.subplots(figsize=(6.4, 4.2))\nax.plot(tmin, tmax, \"o\", ms=2.5, color=\"0.6\", label=\"days of 2024\")\nax.plot(gx, gy, \"-\", lw=2.2, color=\"black\",\n        label=\"depth-2 tree (step function)\")\nax.set_xlabel(\"minimum temperature of the day (\u00b0C)\")\nax.set_ylabel(\"maximum temperature of the day (\u00b0C)\")\nax.set_title(\"a depth-2 regression tree at Kaisaniemi\")\nax.legend(frameon=False, fontsize=8)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"decisiontree.png\", dpi=150)\n\nfailed = [name for name, ok in report if not ok]\nprint(f\"{len(report) - len(failed)}/{len(report)} checks passed\"\n      + (f\", FAILED: {failed}\" if failed else \"\"))"
  }
 ]
}