{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3be904b2",
   "metadata": {},
   "source": [
    "# Decision Trees · How mixed is this pile?\n",
    "\n",
    "A decision tree has to compare two questions and say which one is better. To do\n",
    "that it needs a number for **how mixed a pile is** — how much the things in it\n",
    "disagree about the outcome you care about.\n",
    "\n",
    "This notebook builds that number from scratch on ten deals, checks by brute\n",
    "force that it means what it claims to mean, and then shows what it does across\n",
    "every pile it could possibly be handed.\n",
    "\n",
    "The number is called **Gini impurity**, and everything in this path after this\n",
    "lesson is built on it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "6b7fe388",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:18:31.122971Z",
     "iopub.status.busy": "2026-08-19T12:18:31.122902Z",
     "iopub.status.idle": "2026-08-19T12:18:31.410056Z",
     "shell.execute_reply": "2026-08-19T12:18:31.409826Z"
    }
   },
   "outputs": [],
   "source": [
    "# hide — plumbing so this file runs both in the repo and in Colab.\n",
    "try:\n",
    "    from _figkit import save_fig, record\n",
    "except ImportError:  # Colab — no repo, no problem\n",
    "    def save_fig(name, plot, **kw):\n",
    "        import matplotlib.pyplot as plt\n",
    "        fig, ax = plt.subplots(figsize=kw.get('figsize', (7, 4.2))); plot(ax); plt.show()\n",
    "    def record(key, value):\n",
    "        print(f'{key} = {value}'); return value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "74cb9677",
   "metadata": {},
   "source": [
    "## 1. Ten deals\n",
    "\n",
    "Ten closed deals. Six won, four lost. That is the entire dataset for this\n",
    "lesson, and it is ten because you are going to check every number below by\n",
    "hand."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "f71185a7",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:18:31.411323Z",
     "iopub.status.busy": "2026-08-19T12:18:31.411225Z",
     "iopub.status.idle": "2026-08-19T12:18:31.414115Z",
     "shell.execute_reply": "2026-08-19T12:18:31.413880Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n_deals = 10\n",
      "n_won = 6\n",
      "n_lost = 4\n",
      "6 won, 4 lost, out of 10\n",
      "share won  = 6/10 = 0.6\n",
      "share lost = 4/10 = 0.4\n"
     ]
    }
   ],
   "source": [
    "#| caption: Ten closed deals — six won, four lost\n",
    "DEALS = [\"won\"] * 6 + [\"lost\"] * 4\n",
    "\n",
    "n = record(\"n_deals\", len(DEALS))\n",
    "won = record(\"n_won\", DEALS.count(\"won\"))\n",
    "lost = record(\"n_lost\", DEALS.count(\"lost\"))\n",
    "print(f\"{won} won, {lost} lost, out of {n}\")\n",
    "print(f\"share won  = {won}/{n} = {won / n}\")\n",
    "print(f\"share lost = {lost}/{n} = {lost / n}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c241341c",
   "metadata": {},
   "source": [
    "## 2. What the number has to mean\n",
    "\n",
    "Here is the definition to hold, and it is not a formula — it is a game:\n",
    "\n",
    "> **Reach into the pile, pull out a deal, put it back, pull out another.\n",
    "> How often do the two disagree?**\n",
    "\n",
    "An all-won pile: never. A pile that is half and half: about half the time. That\n",
    "is exactly the property a tree needs, and Gini impurity is that probability.\n",
    "\n",
    "So before writing any formula, just play the game a hundred thousand times and\n",
    "see what number comes out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "13c97f6f",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:18:31.415135Z",
     "iopub.status.busy": "2026-08-19T12:18:31.415062Z",
     "iopub.status.idle": "2026-08-19T12:18:31.441022Z",
     "shell.execute_reply": "2026-08-19T12:18:31.440795Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "measured_gini = 0.483\n",
      "48251 of 100000 pairs disagreed  ->  0.483\n"
     ]
    }
   ],
   "source": [
    "#| caption: Play the two-draws game 100,000 times and count the disagreements\n",
    "import random\n",
    "random.seed(3)\n",
    "\n",
    "TRIALS = 100_000\n",
    "disagreed = sum(1 for _ in range(TRIALS)\n",
    "                if random.choice(DEALS) != random.choice(DEALS))\n",
    "\n",
    "measured = record(\"measured_gini\", round(disagreed / TRIALS, 3))\n",
    "print(f\"{disagreed} of {TRIALS} pairs disagreed  ->  {measured}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "37144c5a",
   "metadata": {},
   "source": [
    "## 3. The same number, by hand\n",
    "\n",
    "Now the arithmetic, and it has to land on what the game just measured.\n",
    "\n",
    "Two draws **agree** if both are won, or both are lost:\n",
    "\n",
    "- both won: (6/10) × (6/10) = 0.36\n",
    "- both lost: (4/10) × (4/10) = 0.16\n",
    "- so they agree 0.36 + 0.16 = 0.52 of the time\n",
    "\n",
    "and they disagree the rest of the time: 1 − 0.52 = **0.48**.\n",
    "\n",
    "That is the whole of it. **Square each share, add them up, subtract from one.**\n",
    "The squares are not a trick — a square is what \"drew this twice in a row\" is."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "3f651b70",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:18:31.442189Z",
     "iopub.status.busy": "2026-08-19T12:18:31.442099Z",
     "iopub.status.idle": "2026-08-19T12:18:31.445804Z",
     "shell.execute_reply": "2026-08-19T12:18:31.445611Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "by hand      0.480\n",
      "by function  0.480\n",
      "by playing   0.483\n",
      "gini_by_hand = 0.48\n",
      "gap_to_simulation = 0.003\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.003"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#| caption: Gini impurity, written out, and checked against the simulation\n",
    "def gini(pile):\n",
    "    \"\"\"1 - the chance two draws agree.\"\"\"\n",
    "    if not pile:\n",
    "        return 0.0\n",
    "    shares = [pile.count(k) / len(pile) for k in set(pile)]\n",
    "    return 1 - sum(s * s for s in shares)\n",
    "\n",
    "by_hand = 1 - (6 / 10) ** 2 - (4 / 10) ** 2\n",
    "print(f\"by hand      {by_hand:.3f}\")\n",
    "print(f\"by function  {gini(DEALS):.3f}\")\n",
    "print(f\"by playing   {measured:.3f}\")\n",
    "\n",
    "record(\"gini_by_hand\", round(by_hand, 3))\n",
    "record(\"gap_to_simulation\", round(abs(by_hand - measured), 3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4d1edc3a",
   "metadata": {},
   "source": [
    "## 4. Every pile of ten there could be\n",
    "\n",
    "Ten deals can be anywhere from nought won to ten won. Score all eleven and the\n",
    "shape of the measure appears — and it is the shape you would want.\n",
    "\n",
    "Nought won and ten won both score **0**: a pile that agrees with itself is not\n",
    "mixed at all. Five and five scores **0.5**, the highest it can go with two\n",
    "outcomes. And notice how flat the top is: nine-one is much better than five-five,\n",
    "but six-four is barely better than five-five."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "6516c562",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:18:31.446839Z",
     "iopub.status.busy": "2026-08-19T12:18:31.446750Z",
     "iopub.status.idle": "2026-08-19T12:18:31.519583Z",
     "shell.execute_reply": "2026-08-19T12:18:31.519318Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 won, 10 lost   0.00  \n",
      " 1 won,  9 lost   0.18  #######\n",
      " 2 won,  8 lost   0.32  #############\n",
      " 3 won,  7 lost   0.42  #################\n",
      " 4 won,  6 lost   0.48  ###################\n",
      " 5 won,  5 lost   0.50  ####################\n",
      " 6 won,  4 lost   0.48  ###################\n",
      " 7 won,  3 lost   0.42  #################\n",
      " 8 won,  2 lost   0.32  #############\n",
      " 9 won,  1 lost   0.18  #######\n",
      "10 won,  0 lost   0.00  \n",
      "gini_5_5 = 0.5\n",
      "gini_9_1 = 0.18\n",
      "gini_10_0 = 0.0\n",
      "gap_5_5_to_6_4 = 0.02\n",
      "figure every-pile-of-ten -> how-mixed-is-this-pile.every-pile-of-ten.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: Every possible pile of ten, scored\n",
    "piles = [(w, gini([\"won\"] * w + [\"lost\"] * (10 - w))) for w in range(11)]\n",
    "for w, g in piles:\n",
    "    print(f\"{w:>2} won, {10 - w:>2} lost   {g:.2f}  {'#' * round(g * 40)}\")\n",
    "\n",
    "record(\"gini_5_5\", round(gini([\"won\"] * 5 + [\"lost\"] * 5), 3))\n",
    "record(\"gini_9_1\", round(gini([\"won\"] * 9 + [\"lost\"]), 3))\n",
    "record(\"gini_10_0\", round(gini([\"won\"] * 10), 3))\n",
    "record(\"gap_5_5_to_6_4\", round(gini([\"won\"] * 5 + [\"lost\"] * 5) - by_hand, 3))\n",
    "\n",
    "def plot(ax):\n",
    "    ps = [i / 200 for i in range(201)]\n",
    "    ax.plot(ps, [1 - p * p - (1 - p) ** 2 for p in ps], color=\"#9aa0aa\", lw=1.4, zorder=1)\n",
    "    ax.scatter([w / 10 for w, _ in piles], [g for _, g in piles], s=34, color=\"#e2574c\", zorder=3)\n",
    "    for w, g in [(0, 0.0), (5, 0.5), (6, by_hand)]:\n",
    "        label = {0: \"0 won\\nnot mixed at all\", 5: \"5 and 5\\nas mixed as it gets\",\n",
    "                 6: \"our pile\\n6 won, 4 lost\"}[w]\n",
    "        ax.annotate(label, (w / 10, g), textcoords=\"offset points\",\n",
    "                    xytext=(0, 14 if w == 0 else -40), ha=\"center\", fontsize=9, color=\"#77777f\")\n",
    "    ax.set_xlabel(\"Share of the pile that were won\")\n",
    "    ax.set_ylabel(\"Gini impurity\")\n",
    "    ax.set_ylim(-0.16, 0.62)\n",
    "\n",
    "save_fig(\"every-pile-of-ten\", plot, figsize=(7, 4.0))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91764473",
   "metadata": {},
   "source": [
    "## 5. More than two outcomes\n",
    "\n",
    "Nothing above assumed there were only two answers. Add a third — deals that\n",
    "broke even — and the same three lines of arithmetic work unchanged.\n",
    "\n",
    "What does change is the ceiling. With two outcomes the worst you can do is 0.5.\n",
    "With three it is 1 − 3 × (1/3)² = **0.667**, with four it is 0.75, and it climbs\n",
    "towards 1 as the number of outcomes grows. **So an impurity of 0.6 is terrible\n",
    "for a yes/no question and rather good for one with five answers** — the number\n",
    "is not comparable across problems with different numbers of outcomes, only\n",
    "across splits of the same one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "2c93ab89",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:18:31.520710Z",
     "iopub.status.busy": "2026-08-19T12:18:31.520627Z",
     "iopub.status.idle": "2026-08-19T12:18:31.524041Z",
     "shell.execute_reply": "2026-08-19T12:18:31.523822Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 outcomes, evenly spread   0.500   (= 1 - 2 x (1/2)^2)\n",
      "3 outcomes, evenly spread   0.667   (= 1 - 3 x (1/3)^2)\n",
      "4 outcomes, evenly spread   0.750   (= 1 - 4 x (1/4)^2)\n",
      "5 outcomes, evenly spread   0.800   (= 1 - 5 x (1/5)^2)\n",
      "6 outcomes, evenly spread   0.833   (= 1 - 6 x (1/6)^2)\n",
      "max_two = 0.5\n",
      "max_three = 0.667\n",
      "gini_three_way = 0.62\n",
      "\n",
      "5 won, 3 lost, 2 broke even  ->  0.620\n"
     ]
    }
   ],
   "source": [
    "#| caption: The ceiling rises with the number of outcomes\n",
    "for k in range(2, 7):\n",
    "    even = [str(i) for i in range(k)] * 12\n",
    "    print(f\"{k} outcomes, evenly spread   {gini(even):.3f}   (= 1 - {k} x (1/{k})^2)\")\n",
    "\n",
    "record(\"max_two\", round(gini([\"a\", \"b\"] * 12), 3))\n",
    "record(\"max_three\", round(gini([\"a\", \"b\", \"c\"] * 12), 3))\n",
    "\n",
    "three = [\"won\"] * 5 + [\"lost\"] * 3 + [\"broke even\"] * 2\n",
    "record(\"gini_three_way\", round(gini(three), 3))\n",
    "print(f\"\\n5 won, 3 lost, 2 broke even  ->  {gini(three):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b4c4c6de",
   "metadata": {},
   "source": [
    "## 6. What a split does to it\n",
    "\n",
    "A question does not score itself. It takes one pile and makes two, and the\n",
    "number you compare against is the **weighted** impurity of what you are left\n",
    "with — weighted, because a very clean pile of two matters less than a fairly\n",
    "clean pile of eight.\n",
    "\n",
    "Split the ten deals by whether the buyer had a budget signed off:\n",
    "\n",
    "- **budget signed off** — 4 deals, 4 won, 0 lost → impurity 0\n",
    "- **no budget** — 6 deals, 2 won, 4 lost → impurity 0.444\n",
    "\n",
    "and the weighted total is (4/10) × 0 + (6/10) × 0.444 = **0.267**, down from 0.48.\n",
    "\n",
    "The weighting is by *how many deals*, never a plain average of the two sides.\n",
    "Averaging the two would give 0.222 — a better-looking number produced entirely\n",
    "by a tiny, spotless pile being allowed to count as much as a large messy one.\n",
    "That is not a detail. It is the single easiest way to build a tree that scores\n",
    "well and decides nothing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ff46ee51",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2026-08-19T12:18:31.526581Z",
     "iopub.status.busy": "2026-08-19T12:18:31.526485Z",
     "iopub.status.idle": "2026-08-19T12:18:31.570912Z",
     "shell.execute_reply": "2026-08-19T12:18:31.570693Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "budget signed off     4 deals   impurity 0.00   weight 0.4\n",
      "no budget             6 deals   impurity 0.44   weight 0.6\n",
      "after_split = 0.267\n",
      "plain_average = 0.222\n",
      "\n",
      "weighted    0.267   <- what a tree compares against\n",
      "plain mean  0.222   <- wrong: it lets 4 spotless deals count as much as 6 messy ones\n",
      "figure before-and-after-a-split -> how-mixed-is-this-pile.before-and-after-a-split.{light,dark}.svg\n"
     ]
    }
   ],
   "source": [
    "#| caption: The impurity you are left with after a split, weighted by pile size\n",
    "SPLIT = {\n",
    "    \"budget signed off\": [\"won\"] * 4,\n",
    "    \"no budget\":         [\"won\"] * 2 + [\"lost\"] * 4,\n",
    "}\n",
    "\n",
    "after = 0.0\n",
    "for side, pile in SPLIT.items():\n",
    "    w = len(pile) / n\n",
    "    print(f\"{side:<20} {len(pile):>2} deals   impurity {gini(pile):.2f}   weight {w:.1f}\")\n",
    "    after += w * gini(pile)\n",
    "\n",
    "record(\"after_split\", round(after, 3))\n",
    "record(\"plain_average\", round(sum(gini(p) for p in SPLIT.values()) / len(SPLIT), 3))\n",
    "print(f\"\\nweighted    {after:.3f}   <- what a tree compares against\")\n",
    "print(f\"plain mean  {sum(gini(p) for p in SPLIT.values()) / len(SPLIT):.3f}   <- wrong: it lets 4 spotless deals count as much as 6 messy ones\")\n",
    "\n",
    "def plot2(ax):\n",
    "    labels = [\"before the split\\n10 deals\", \"budget signed off\\n5 deals\", \"no budget\\n5 deals\"]\n",
    "    vals = [gini(DEALS), gini(SPLIT[\"budget signed off\"]), gini(SPLIT[\"no budget\"])]\n",
    "    ax.bar(labels, vals, color=[\"#9aa0aa\", \"#e2574c\", \"#e2574c\"], width=0.55)\n",
    "    for i, v in enumerate(vals):\n",
    "        ax.text(i, v + 0.015, f\"{v:.2f}\", ha=\"center\", fontsize=10)\n",
    "    ax.axhline(after, ls=\"--\", lw=1.2, color=\"#3b6fd4\")\n",
    "    ax.text(2.42, after + 0.015, f\"weighted\\n{after:.2f}\", ha=\"center\", fontsize=9, color=\"#3b6fd4\")\n",
    "    ax.set_ylabel(\"Gini impurity\")\n",
    "    ax.set_ylim(0, 0.58)\n",
    "    ax.grid(axis=\"x\", visible=False)\n",
    "\n",
    "save_fig(\"before-and-after-a-split\", plot2, figsize=(7, 3.9))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dbe1d754",
   "metadata": {},
   "source": [
    "## Try this\n",
    "\n",
    "1. **Change the pile.** Make it 7 won and 3 lost, and predict the impurity before\n",
    "   you run it. Then 8 and 2. The curve in section 4 tells you both answers.\n",
    "2. **Break the weighting.** In section 6, use the plain average of the two sides\n",
    "   instead of the weighted one, then move one deal from the clean side to the\n",
    "   messy one. Watch the plain average say the split got *better*.\n",
    "3. **Two outcomes, unevenly named.** Replace \"lost\" with three different loss\n",
    "   reasons. The pile has not changed at all, but the impurity has. Work out why —\n",
    "   it is the ceiling from section 5, and it is the reason section 5 exists."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.13.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}