{
 "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": [
    "# Random Forests\n",
    "\n",
    "Turn one unstable tree into a reliable model by averaging hundreds of randomized trees — bootstrap sampling, random feature subsets, OOB scores, and feature importances.\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/random-forests).*"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0001",
   "metadata": {},
   "source": [
    "A single decision tree is interpretable but twitchy — nudge the training data\n",
    "and the whole tree can restructure itself. Random forests fix this with a\n",
    "wonderfully simple idea: train *many* trees, each on a slightly different view\n",
    "of the data, and let them vote. In this lesson you'll see why averaging works,\n",
    "where the randomness comes from, and how to read a forest's feature\n",
    "importances without being fooled by them."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0002",
   "metadata": {},
   "source": [
    "## Wisdom of crowds\n",
    "\n",
    "Ask one person to guess the number of beans in a jar and they'll probably be\n",
    "far off. Average a hundred independent guesses and the result is often\n",
    "startlingly good — individual errors point in different directions and cancel\n",
    "out. The same logic applies to models: if each tree overfits in its *own*\n",
    "random way, the average of their predictions keeps the signal (which all trees\n",
    "agree on) and washes out the noise (which they don't).\n",
    "\n",
    "The crucial word is **independent**. A hundred copies of the *same* tree vote\n",
    "unanimously and average to... the same tree. Diversity is not a nice-to-have;\n",
    "it's the entire mechanism. So a random forest goes out of its way to make its\n",
    "trees disagree."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0003",
   "metadata": {},
   "source": [
    "## Two sources of randomness\n",
    "\n",
    "A random forest decorrelates its trees in two ways:\n",
    "\n",
    "1. **Bootstrap sampling (bagging).** Each tree trains on a *bootstrap\n",
    "   sample*: n rows drawn from the n training rows **with replacement**. Some\n",
    "   rows appear twice or three times, and on average about 37% of rows are left\n",
    "   out of any given tree's sample entirely. Every tree therefore sees a\n",
    "   slightly different dataset.\n",
    "\n",
    "2. **Random feature subsets per split.** At every node, the tree is only\n",
    "   allowed to consider a random subset of features (`max_features`, by default\n",
    "   the square root of the feature count for classification). Without this, one\n",
    "   dominant feature would win the root split in *every* tree and the trees\n",
    "   would all look alike. Restricting the menu forces different trees to\n",
    "   discover different structure.\n",
    "\n",
    "Bagging alone helps; the feature restriction is what makes it a *random*\n",
    "forest rather than just bagged trees. To classify a new sample, every tree\n",
    "votes and the majority wins (for regression, predictions are averaged)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0004",
   "metadata": {},
   "source": [
    "## Forest vs a single tree\n",
    "\n",
    "Talk is cheap — let's race them on the same split of the breast cancer\n",
    "dataset:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0005",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "\n",
    "X, y = load_breast_cancer(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",
    "tree = DecisionTreeClassifier(random_state=42).fit(X_train, y_train)\n",
    "forest = RandomForestClassifier(n_estimators=100, random_state=42)\n",
    "forest.fit(X_train, y_train)\n",
    "\n",
    "print(f\"single tree : train={tree.score(X_train, y_train):.3f}  test={tree.score(X_test, y_test):.3f}\")\n",
    "print(f\"forest (100): train={forest.score(X_train, y_train):.3f}  test={forest.score(X_test, y_test):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0006",
   "metadata": {},
   "source": [
    "Both models hit a perfect train score — every individual tree still overfits\n",
    "its bootstrap sample. But the forest's *test* accuracy is clearly higher: the\n",
    "overfitting of a hundred different trees averages out. That's variance\n",
    "reduction in action, and it's why forests are such a strong default for\n",
    "tabular data."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0007",
   "metadata": {},
   "source": [
    "## The knobs that matter\n",
    "\n",
    "- **`n_estimators`** — number of trees. More is monotonically better (the\n",
    "  average just gets more stable) until it plateaus; the only cost is compute.\n",
    "  100–500 is typical. You cannot overfit by adding trees.\n",
    "- **`max_features`** — the size of the random feature menu per split. Smaller\n",
    "  values mean more diverse (less correlated) trees but each tree is weaker.\n",
    "  The default (`\"sqrt\"` for classification) is a solid starting point.\n",
    "- **`max_depth` / `min_samples_leaf`** — same meaning as for a single tree.\n",
    "  Forests tolerate deep trees much better than a lone tree does, so these\n",
    "  often stay at their defaults; tune them if the forest is slow or still\n",
    "  overfits."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0008",
   "metadata": {},
   "source": [
    "## Free validation: the OOB score\n",
    "\n",
    "Remember that each tree never sees about 37% of the training rows. Those rows\n",
    "are **out-of-bag (OOB)** for that tree — so we can use them as a private\n",
    "little test set. For every training row, collect votes only from the trees\n",
    "that didn't train on it, and score the result. You get an honest performance\n",
    "estimate *without* sacrificing any data to a validation split:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0009",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "\n",
    "X, y = load_breast_cancer(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",
    "forest = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=42)\n",
    "forest.fit(X_train, y_train)\n",
    "\n",
    "print(f\"OOB score : {forest.oob_score_:.3f}\")\n",
    "print(f\"test score: {forest.score(X_test, y_test):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0010",
   "metadata": {},
   "source": [
    "The OOB score lands very close to the held-out test score — it's a built-in\n",
    "cross-validation you get almost for free."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0011",
   "metadata": {},
   "source": [
    "## Feature importances\n",
    "\n",
    "Forests come with a bonus: a ranking of which features mattered. Each split\n",
    "reduces impurity by some amount; add up the reductions credited to each\n",
    "feature across all trees and you get **impurity-based feature importance**\n",
    "(`feature_importances_`):"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0012",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "import numpy as np\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.ensemble import RandomForestClassifier\n",
    "from sklearn.inspection import permutation_importance\n",
    "\n",
    "wine = load_wine()\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    wine.data, wine.target, test_size=0.3, stratify=wine.target, random_state=42)\n",
    "\n",
    "forest = RandomForestClassifier(n_estimators=100, random_state=42)\n",
    "forest.fit(X_train, y_train)\n",
    "\n",
    "order = np.argsort(forest.feature_importances_)\n",
    "plt.barh(np.array(wine.feature_names)[order], forest.feature_importances_[order])\n",
    "plt.xlabel(\"impurity-based importance\")\n",
    "plt.tight_layout()\n",
    "plt.show()\n",
    "\n",
    "# The more trustworthy alternative: shuffle a feature, watch the score drop\n",
    "perm = permutation_importance(forest, X_test, y_test, n_repeats=5, random_state=42)\n",
    "top = np.argsort(perm.importances_mean)[::-1][:5]\n",
    "print(\"top 5 by permutation importance:\")\n",
    "for i in top:\n",
    "    print(f\"  {wine.feature_names[i]:<30s} {perm.importances_mean[i]:.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0013",
   "metadata": {},
   "source": [
    "> **Impurity importances have a known bias**\n",
    "> \n",
    "> Impurity-based importances are computed on *training* data and systematically\n",
    "> favor features with many possible split points — continuous features and\n",
    "> high-cardinality categoricals — even when they carry no real signal. A random\n",
    "> ID column can look \"important\". **Permutation importance** avoids both\n",
    "> problems: shuffle one feature's values on held-out data and measure how much\n",
    "> the score drops. If shuffling barely hurts, the model wasn't really using that\n",
    "> feature. When the two rankings disagree, trust the permutation one."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0014",
   "metadata": {},
   "source": [
    "One more caution, no matter which importance you use: important ≠ causal. A\n",
    "feature can rank highly because it's *correlated* with the true driver.\n",
    "Importance tells you what the model leaned on, not what makes the outcome\n",
    "happen in the real world."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0015",
   "metadata": {},
   "source": [
    "## Regression forests\n",
    "\n",
    "Everything transfers directly to regression: `RandomForestRegressor` averages\n",
    "each tree's numeric prediction instead of taking a vote, and splits minimize\n",
    "MSE instead of gini. Same knobs, same OOB trick, same importances:"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0016",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_diabetes\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.ensemble import RandomForestRegressor\n",
    "\n",
    "X, y = load_diabetes(return_X_y=True)\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)\n",
    "\n",
    "forest = RandomForestRegressor(n_estimators=100, random_state=42).fit(X_train, y_train)\n",
    "print(f\"train R2: {forest.score(X_train, y_train):.3f}\")\n",
    "print(f\"test R2 : {forest.score(X_test, y_test):.3f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0017",
   "metadata": {},
   "source": [
    "And like all tree models, forests need **no feature scaling** — you can drop\n",
    "the `StandardScaler` from your pipeline entirely."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0018",
   "metadata": {},
   "source": [
    "### 🏋️ Exercise — How many trees are enough?\n",
    "\n",
    "On the breast cancer dataset (same 70/30 stratified split as above), train\n",
    "random forests with `n_estimators` set to 1, 5, 10, 25, 50, 100, and 200.\n",
    "Plot test accuracy against the number of trees. Where does the curve flatten\n",
    "out — and is a 200-tree forest meaningfully better than a 50-tree one here?"
   ]
  },
  {
   "cell_type": "code",
   "id": "cell-0019",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": [
    "# Your solution here"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0020",
   "metadata": {},
   "source": [
    "<details><summary>✅ Show solution</summary>\n",
    "\n",
    "```python\n",
    "import matplotlib.pyplot as plt\n",
    "from sklearn.datasets import load_breast_cancer\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "\n",
    "X, y = load_breast_cancer(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",
    "counts = [1, 5, 10, 25, 50, 100, 200]\n",
    "scores = []\n",
    "for n in counts:\n",
    "    forest = RandomForestClassifier(n_estimators=n, random_state=42)\n",
    "    forest.fit(X_train, y_train)\n",
    "    scores.append(forest.score(X_test, y_test))\n",
    "    print(f\"n_estimators={n:3d}  test acc={scores[-1]:.3f}\")\n",
    "\n",
    "plt.plot(counts, scores, \"o-\")\n",
    "plt.xlabel(\"n_estimators\"); plt.ylabel(\"test accuracy\")\n",
    "plt.show()\n",
    "```\n",
    "\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cell-0021",
   "metadata": {},
   "source": [
    "Next up: forests are just one member of a bigger family — voting, bagging,\n",
    "stacking, and boosting all combine models, and ensemble learning is the map\n",
    "that ties them together."
   ]
  }
 ]
}