{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.11"
  },
  "colab": {
   "provenance": []
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "id": "cell-0000",
   "metadata": {},
   "source": [
    "# Decision Trees\n",
    "\n",
    "Learn how decision trees carve up feature space with if/else questions, how gini impurity picks the best split, and how to read and control a tree in scikit-learn.\n",
    "\n",
    "*Part of the free [Machine Learning](https://ramadnsyh.dev/courses/machine-learning) course by [Muhammad Ramadiansyah](https://ramadnsyh.dev). This notebook is generated from the interactive lesson — [read it online](https://ramadnsyh.dev/courses/machine-learning/decision-trees).*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0001",
   "metadata": {},
   "source": [
    "Every model you've met so far draws smooth curves through the data. A decision\n",
    "tree does something completely different: it plays twenty questions. \"Is petal\n",
    "length below 2.45 cm? Yes → it's a setosa. No → ask another question.\" The\n",
    "result is a model you can literally read out loud — and the building block for\n",
    "random forests and gradient boosting, the workhorses of tabular machine\n",
    "learning."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0002",
   "metadata": {},
   "source": [
    "## A model made of if/else rules\n",
    "\n",
    "A trained tree is just a flowchart of yes/no questions about the features.\n",
    "Each internal **node** tests one feature against one threshold, each branch is\n",
    "an answer, and each **leaf** holds a prediction. Prediction is cheap: drop a\n",
    "sample in at the root and follow the answers down to a leaf.\n",
    "\n",
    "Training is where the magic happens — the algorithm *learns* which questions\n",
    "to ask, in which order, from the data. Each question splits the feature space\n",
    "with an axis-aligned cut, so the decision boundary is built from rectangles.\n",
    "Watch what happens to the boundary as you let the tree ask more questions:"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0003",
   "metadata": {},
   "source": [
    "> 🎛️ **Interactive demo** — this section has a hands-on visualization in the web version of this lesson: [open it here](https://ramadnsyh.dev/courses/machine-learning/decision-trees)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0004",
   "metadata": {},
   "source": [
    "At depth 1 the tree makes a single cut — one question. Each extra level lets\n",
    "it subdivide every region again, so the boundary gets more intricate. Push the\n",
    "depth high enough and the tree starts fencing off individual points: it has\n",
    "memorized the training set, noise included. Keep that picture in mind — depth\n",
    "is the tree's main complexity knob."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0005",
   "metadata": {},
   "source": [
    "## How a split is chosen: gini impurity\n",
    "\n",
    "At every node the algorithm tries many candidate splits — every feature, many\n",
    "thresholds — and keeps the one that makes the resulting child nodes as *pure*\n",
    "as possible. The default purity measure in scikit-learn is **gini impurity**:\n",
    "\n",
    "**G = 1 − Σ pₖ²**\n",
    "\n",
    "where pₖ is the fraction of samples in the node belonging to class k. A pure\n",
    "node (all one class) has G = 0; a 50/50 node has G = 0.5. A candidate split is\n",
    "scored by the **weighted average** of its children's impurities — lower is\n",
    "better. Let's work a tiny example by hand:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0006",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def gini(counts):\n",
    "    p = np.array(counts) / sum(counts)\n",
    "    return 1 - np.sum(p ** 2)\n",
    "\n",
    "# Parent node: 6 apples, 4 oranges\n",
    "print(f\"parent gini: {gini([6, 4]):.3f}\")\n",
    "\n",
    "# Split A -> left: 4 apples, 0 oranges | right: 2 apples, 4 oranges\n",
    "gA = (4/10) * gini([4, 0]) + (6/10) * gini([2, 4])\n",
    "print(f\"split A weighted gini: {gA:.3f}\")\n",
    "\n",
    "# Split B -> left: 3 apples, 2 oranges | right: 3 apples, 2 oranges\n",
    "gB = (5/10) * gini([3, 2]) + (5/10) * gini([3, 2])\n",
    "print(f\"split B weighted gini: {gB:.3f}\")\n",
    "\n",
    "print(\"\\\\nSplit A wins: it creates a perfectly pure left child.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0007",
   "metadata": {},
   "source": [
    "The parent starts at 0.48. Split A drops the weighted impurity to 0.267 —\n",
    "mostly because its left child is completely pure — while split B barely helps\n",
    "at all. The tree greedily picks the biggest impurity drop, then repeats the\n",
    "whole search inside each child. **Entropy** (`criterion=\"entropy\"`) is an\n",
    "alternative measure with the same spirit; in practice the two produce very\n",
    "similar trees, and gini is slightly cheaper to compute."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0008",
   "metadata": {},
   "source": [
    "## Depth and leaf size: the overfitting controls\n",
    "\n",
    "Left alone, a tree keeps splitting until every leaf is pure — which usually\n",
    "means memorizing the training data. Two hyperparameters rein it in:\n",
    "\n",
    "- **`max_depth`** — hard cap on the number of questions along any path.\n",
    "  Smaller = simpler boundary (exactly what you saw in the playground).\n",
    "- **`min_samples_leaf`** — a split is only allowed if each child keeps at\n",
    "  least this many samples. Larger values stop the tree from carving out tiny\n",
    "  regions around individual noisy points, which indirectly limits depth too.\n",
    "\n",
    "There's also `min_samples_split` (don't split nodes smaller than this) and\n",
    "`max_leaf_nodes`. You rarely need all of them — tuning `max_depth` plus\n",
    "`min_samples_leaf` covers most situations."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0009",
   "metadata": {},
   "source": [
    "## A real tree on iris\n",
    "\n",
    "Let's train one and — this is the fun part — print its rules as plain text:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0010",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.tree import DecisionTreeClassifier, export_text\n",
    "\n",
    "X, y = load_iris(return_X_y=True)\n",
    "iris = load_iris()\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, test_size=0.3, stratify=y, random_state=42)\n",
    "\n",
    "tree = DecisionTreeClassifier(max_depth=3, random_state=42)\n",
    "tree.fit(X_train, y_train)\n",
    "\n",
    "print(f\"train accuracy: {tree.score(X_train, y_train):.3f}\")\n",
    "print(f\"test accuracy : {tree.score(X_test, y_test):.3f}\\\\n\")\n",
    "\n",
    "print(export_text(tree, feature_names=iris.feature_names))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0011",
   "metadata": {},
   "source": [
    "Read the printout top to bottom: the very first question — petal length vs\n",
    "2.45 cm — separates all the setosas in one cut, and the rest of the tree works\n",
    "on telling versicolor from virginica. No coefficients, no probabilities to\n",
    "decode: the model *is* the explanation.\n",
    "\n",
    "Notice what we didn't do: **no feature scaling**. A tree only asks \"is this\n",
    "feature above this threshold?\", so stretching or squashing a feature's scale\n",
    "changes the threshold but not the tree. Standardization, so critical for KNN\n",
    "and SVMs, is simply irrelevant here."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0012",
   "metadata": {},
   "source": [
    "## Drawing the tree\n",
    "\n",
    "For reports and sanity checks, `plot_tree` renders the same structure\n",
    "graphically — each node shows its split rule, gini, sample count, and class\n",
    "mix:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0013",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.tree import DecisionTreeClassifier, plot_tree\n",
    "\n",
    "iris = load_iris()\n",
    "tree = DecisionTreeClassifier(max_depth=2, random_state=42)\n",
    "tree.fit(iris.data, iris.target)\n",
    "\n",
    "plt.figure(figsize=(9, 5))\n",
    "plot_tree(tree, feature_names=iris.feature_names,\n",
    "          class_names=iris.target_names, filled=True, rounded=True)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0014",
   "metadata": {},
   "source": [
    "Darker node colors mean purer nodes. Follow any root-to-leaf path and you can\n",
    "state the exact rule that produces that prediction — try explaining a neural\n",
    "network's prediction that easily."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0015",
   "metadata": {},
   "source": [
    "## Strengths — and the flaw that motivates forests\n",
    "\n",
    "Decision trees have a lot going for them:\n",
    "\n",
    "- **Interpretable** — the model is a readable set of rules.\n",
    "- **No scaling needed** — thresholds don't care about units.\n",
    "- **Mixed feature types** — numeric and (encoded) categorical features\n",
    "  coexist happily, and monotone transformations of features change nothing.\n",
    "- **Nonlinear out of the box** — no kernels or polynomial features required.\n",
    "\n",
    "But they have one serious weakness: **instability**. Because each split is a\n",
    "greedy, winner-takes-all choice, removing a handful of training samples can\n",
    "flip which question wins at the root — and everything below the root then\n",
    "changes too. Two nearly identical datasets can produce wildly different trees.\n",
    "In statistics terms, a deep tree is a **high-variance** model.\n",
    "\n",
    "Here's the beautiful trick: if one tree is unstable, train *hundreds* of\n",
    "slightly different trees and average them. The individual wobbles cancel out.\n",
    "That's a random forest — the subject of the next lesson."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0016",
   "metadata": {},
   "source": [
    "### 🏋️ Exercise — Find the sweet-spot depth on the wine dataset\n",
    "\n",
    "Load `load_wine` from scikit-learn, split it 70/30 (stratified), and train\n",
    "`DecisionTreeClassifier` models with `max_depth` from 1 to 10. Print train and\n",
    "test accuracy for each depth and plot both curves. At what depth does test\n",
    "accuracy peak, and where does the train–test gap start to widen?"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0017",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0018",
   "metadata": {},
   "source": [
    "<details><summary>✅ Show solution</summary>\n",
    "\n",
    "```python\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import load_wine\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "X, y = load_wine(return_X_y=True)\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    X, y, test_size=0.3, stratify=y, random_state=42)\n",
    "\n",
    "depths = range(1, 11)\n",
    "train_acc, test_acc = [], []\n",
    "for d in depths:\n",
    "    tree = DecisionTreeClassifier(max_depth=d, random_state=42)\n",
    "    tree.fit(X_train, y_train)\n",
    "    train_acc.append(tree.score(X_train, y_train))\n",
    "    test_acc.append(tree.score(X_test, y_test))\n",
    "    print(f\"depth={d:2d}  train={train_acc[-1]:.3f}  test={test_acc[-1]:.3f}\")\n",
    "\n",
    "plt.plot(depths, train_acc, \"o-\", label=\"train\")\n",
    "plt.plot(depths, test_acc, \"s-\", label=\"test\")\n",
    "plt.xlabel(\"max_depth\"); plt.ylabel(\"accuracy\"); plt.legend()\n",
    "plt.show()\n",
    "```\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0019",
   "metadata": {},
   "source": [
    "Next up: random forests — how averaging hundreds of deliberately randomized\n",
    "trees turns one unstable learner into one of the most reliable models in\n",
    "machine learning."
   ]
  }
 ]
}