# Decision Trees

> Recursively split on the feature threshold that most reduces impurity (Gini or entropy).

Source: https://www.mlfoundry.in/learn/decision-trees  
Section: ML Algorithms › Supervised · Classification  
Level: core · 18 min read · updated 2026-10-07

**A decision tree:** predicts by asking a sequence of yes/no questions about single features — *is $x_j \le t$?* or *is Outlook = Sunny?* — until it reaches a leaf, which outputs the majority class (classification) or the mean target (regression) of the training points that ended there.

- **Task:** Classification and regression
- **Input → output:** $x$ → the prediction stored in the leaf $x$ falls into
- **Learns:** a feature and threshold per internal node; a value (or class distribution) per leaf
- **Split criterion:** entropy / information gain (ID3, C4.5), Gini impurity (CART), variance / MSE (regression)
- **Training:** greedy, top-down; about $O(d\,n\log n)$ per level with pre-sorted features
- **Prediction:** $O(\text{depth})$ comparisons
- **Hyperparameters:** max depth, min samples per split / leaf, criterion, pruning strength α
- **Assumes:** nothing about distributions; decision boundaries are axis-aligned

## The problem

Many real decisions look like rules: *if income < 30k and debt > 10k, then high risk*. A linear model cannot express thresholds and interactions like this without hand-made features. We want a model that **discovers** such rules from data — and that a person can read and audit.

## Anatomy of a tree

**Vocabulary**

- **Root node:** the first question; it sees the whole training set
- **Internal node:** a question *feature $\le$ threshold?* (numeric) or *feature = value?* (categorical)
- **Branch:** one answer to a node's question; it routes a subset of the data to a child
- **Leaf:** a node with no question; it stores the prediction
- **Depth:** number of questions on the longest root-to-leaf path
- **Rule:** the conjunction of answers along one root-to-leaf path

**A pure node:** contains training points of only one class. Its impurity is 0 by every measure — there is nothing left to separate — so a pure node always becomes a leaf. The whole algorithm is a search for questions that make the children **purer** than their parent.

## Measuring impurity

To pick a question we need a number that says how *mixed* a node is. Let $p_c$ be the fraction of points in node $S$ that belong to class $c$. Three measures are used; all are 0 for a pure node and largest for an even mix.

$$
H(S)=-\sum_{c}p_c\log_2 p_c
$$

- $H(S)$: entropy of node S, in bits
- $p_c$: fraction of class $c$ in $S$ (with $0\log 0 = 0$)

**Entropy** is the average number of bits needed to encode the class of a random point from the node. For two classes it ranges from 0 (pure) to 1 bit (50/50); with $K$ classes the maximum is $\log_2 K$. Example: 9 Yes and 5 No gives $H=-\tfrac{9}{14}\log_2\tfrac{9}{14}-\tfrac{5}{14}\log_2\tfrac{5}{14}=0.940$ bits.

$$
G(S)=1-\sum_{c}p_c^2=\sum_c p_c(1-p_c)
$$

- $G(S)$: Gini impurity of node S

**Gini impurity** is the probability that two points drawn at random (with replacement) from the node have different classes — equivalently, the error rate if you labelled points randomly according to $p$. It ranges from 0 to $1-1/K$ (0.5 for two classes). Same 9/5 node: $G=1-(0.643^2+0.357^2)=0.459$.

**Misclassification error** $E(S)=1-\max_c p_c$ is the error of predicting the majority. It is what we ultimately care about, but it is a poor *splitting* criterion: it is piecewise linear, so many splits that clearly improve purity leave it unchanged.

> Figure: Drag p. All three are 0 at the edges (pure nodes) and peak at p = ½. Entropy and Gini are strictly concave, so any split that changes the class mix lowers their weighted average; misclassification error is flat on each side of ½ and often does not move.

> **Entropy vs Gini in practice:** They pick the same split the large majority of the time. Gini is slightly cheaper (no logarithm) and is the default in scikit-learn; entropy has the cleaner information-theoretic meaning. Tune max depth before you worry about the criterion.

## Information gain: scoring a split

A split sends the parent's points into children $S_1,\dots,S_m$. We score it by how much impurity it removes, weighting each child by its share of the points — a tiny pure child should not count as much as a large one.

$$
\text{IG}(S,A)=H(S)-\sum_{v\in\text{values}(A)}\frac{|S_v|}{|S|}\,H(S_v)
$$

- $A$: the attribute (or threshold test) being split on
- $S_v$: subset of $S$ where $A$ takes value $v$
- $\tfrac{|S_v|}{|S|}$: weight: fraction of the parent's points sent to that child

The second term is the **weighted child entropy** (the "remainder"). Information gain is how many bits of uncertainty about the label the question removes, on average. With Gini, the same recipe gives the **Gini decrease** $G(S)-\sum_v \tfrac{|S_v|}{|S|}G(S_v)$. The greedy rule is simply: **pick the split with the largest gain**.

> **Where cross-entropy comes in:** Suppose each leaf predicts the class *probabilities* $\hat p$ of its training points. The average log-loss (cross-entropy) of those predictions on the leaf's own points is exactly $-\sum_c \hat p_c\log \hat p_c = H(\text{leaf})$. So the weighted child entropy *is* the tree's training cross-entropy, and maximizing information gain means choosing the split that most reduces cross-entropy loss. Gini plays the same role for the squared (Brier) loss.

> **Gain is biased toward many-valued attributes:** An attribute like *customer ID* puts every row in its own pure child, so its gain equals $H(S)$ — the maximum — while being useless for new data. C4.5 fixes this with the **gain ratio** $\text{IG}(S,A)/\text{SplitInfo}(A)$, where $\text{SplitInfo}(A)=-\sum_v \tfrac{|S_v|}{|S|}\log_2\tfrac{|S_v|}{|S|}$ penalizes splitting into many small pieces. CART avoids the problem by only ever making binary splits.

## Worked example: should we play tennis?

The classic dataset from Quinlan's ID3 paper: 14 days, four categorical features, and whether tennis was played. 9 days are **Yes** and 5 are **No**, so the root entropy is $H(S)=0.940$ bits.

Play-tennis data (Quinlan, 1986). Highlighted: the 5 Sunny days, which the tree will split again.

| Day | Outlook | Temp | Humidity | Wind | Play |
| --- | --- | --- | --- | --- | --- |
| 1 | Sunny | Hot | High | Weak | No |
| 2 | Sunny | Hot | High | Strong | No |
| 3 | Overcast | Hot | High | Weak | Yes |
| 4 | Rain | Mild | High | Weak | Yes |
| 5 | Rain | Cool | Normal | Weak | Yes |
| 6 | Rain | Cool | Normal | Strong | No |
| 7 | Overcast | Cool | Normal | Strong | Yes |
| 8 | Sunny | Mild | High | Weak | No |
| 9 | Sunny | Cool | Normal | Weak | Yes |
| 10 | Rain | Mild | Normal | Weak | Yes |
| 11 | Sunny | Mild | Normal | Strong | Yes |
| 12 | Overcast | Mild | High | Strong | Yes |
| 13 | Overcast | Hot | Normal | Weak | Yes |
| 14 | Rain | Mild | High | Strong | No |

**Gain of Outlook at the root**

1. Split by value: **Sunny** 2 Yes / 3 No, **Overcast** 4 Yes / 0 No, **Rain** 3 Yes / 2 No.
2. Child entropies: $H(\text{Sunny})=H(\text{Rain})=-\tfrac25\log_2\tfrac25-\tfrac35\log_2\tfrac35=0.971$; $H(\text{Overcast})=0$ — a **pure node**.
3. Weighted child entropy: $\tfrac{5}{14}(0.971)+\tfrac{4}{14}(0)+\tfrac{5}{14}(0.971)=0.694$.
4. Information gain: $0.940-0.694=0.247$ bits.

Every attribute scored at the root. Outlook wins on both criteria; Temperature barely helps.

| Attribute | Children (Yes/No) | Weighted entropy | Information gain | Gini decrease |
| --- | --- | --- | --- | --- |
| **Outlook** | Sunny 2/3 · Overcast 4/0 · Rain 3/2 | 0.694 | **0.247** | **0.116** |
| Humidity | High 3/4 · Normal 6/1 | 0.789 | 0.152 | 0.092 |
| Wind | Weak 6/2 · Strong 3/3 | 0.892 | 0.048 | 0.031 |
| Temp | Hot 2/2 · Mild 4/2 · Cool 3/1 | 0.911 | 0.029 | 0.019 |

So the root asks about **Outlook**. The Overcast branch is pure and becomes a *Yes* leaf. The other two branches recurse on their own subsets, with Outlook removed from the candidates:

**The recursion**

- **Sunny (5 days):** $H=0.971$. Humidity: High 0/3, Normal 2/0 — both children pure, gain $=0.971$ (the maximum possible). Temp gains 0.571, Wind 0.020. → split on **Humidity**.
- **Rain (5 days):** $H=0.971$. Wind: Weak 3/0, Strong 0/2 — both pure, gain $=0.971$. Temp and Humidity each gain only 0.020. → split on **Wind**.
- **Result:** 5 leaves, all pure, using 3 of the 4 features. Temperature is never asked.

> Figure: The tree growing from the table. Each dot is one day. At every node, each attribute is tried as a dashed preview split (its table column lights up in the branch colours) and scored by information gain; the winner becomes the node and the dots flow into its branches. Pure branches turn into leaves. Finally a new day — Sunny, Cool, High humidity, Strong wind — walks down to a No leaf.

Read off the rules: *if Outlook = Overcast → play*; *if Sunny and Humidity = Normal → play*; *if Rain and Wind = Weak → play*; otherwise don't. Each one is a root-to-leaf path.

## Numeric features: choosing a threshold

For a numeric feature the question is $x_j\le t$. Only thresholds *between* consecutive sorted values can change the split, so CART sorts the values and tries every midpoint — $n-1$ candidates per feature — keeping the one with the best gain. With pre-sorting, one feature is scanned in $O(n)$ by moving points from right to left one at a time and updating class counts.

> Figure: 16 students, hours studied → passed or failed. Drag the split or switch criterion. The best threshold is x ≤ 4.40 (gain 0.447); x ≤ 5.75 makes the right child pure but scores lower (0.438), because its left child stays badly mixed.

> **Pure is not the goal of one split:** The best split is the one with the lowest *weighted* impurity of both children, not the one that makes one child pure. A split that isolates a few points perfectly while leaving a large mixed child is usually worse.

## The algorithm, step by step

**Grow(node)**

1. **Stop?** If the node is pure, has fewer than `min_samples_split` points, or is at `max_depth`, make it a leaf: predict the majority class (and store the class proportions).
2. **Search.** For every feature and every candidate threshold (or category), compute the weighted child impurity.
3. **Choose.** Keep the split with the largest impurity decrease. If even the best one decreases impurity by less than `min_impurity_decrease`, make a leaf instead.
4. **Recurse** on each child with the subset of points routed to it.

> Figure: CART on 2-D points: at every node it scores thresholds on both features by weighted Gini and keeps the lowest. Each split carves an axis-aligned rectangle, so the decision regions are boxes. Root: Gini 0.50 → 0.31 after the first split.

This is **greedy**: each split is the best one *now*, not necessarily the best for the final tree — finding the optimal tree is NP-hard. Greedy works well in practice, and ensembles fix most of its weaknesses.

## Regression trees

For a numeric target, a leaf predicts the **mean** of its points, and impurity is their **variance** (mean squared error around that mean). The split criterion becomes variance reduction:

$$
\Delta=\operatorname{Var}(S)-\frac{|L|}{|S|}\operatorname{Var}(L)-\frac{|R|}{|S|}\operatorname{Var}(R)
$$

Six points: $x=1\ldots6$, $y = 5, 6, 5, 20, 22, 21$. Parent mean 13.17, variance 61.81. Splitting at 3.5 removes 99% of the variance.

| Split | Left mean (var) | Right mean (var) | Weighted var | Reduction |
| --- | --- | --- | --- | --- |
| x ≤ 1.5 | 5.00 (0.00) | 14.80 (58.16) | 48.47 | 13.34 |
| x ≤ 2.5 | 5.50 (0.25) | 17.00 (48.50) | 32.42 | 29.39 |
| **x ≤ 3.5** | **5.33 (0.22)** | **21.00 (0.67)** | **0.44** | **61.36** |
| x ≤ 4.5 | 9.00 (40.50) | 21.50 (0.25) | 27.08 | 34.72 |
| x ≤ 5.5 | 11.60 (59.44) | 21.00 (0.00) | 49.53 | 12.27 |

The fitted function is a **step function**: constant within each leaf. More depth means more, narrower steps.

## Overfitting and pruning

Left alone, a tree keeps splitting until every leaf is pure — 100% training accuracy, with the last splits fitting noise. Two remedies:

**Controlling complexity**

- **Pre-pruning:** stop early: `max_depth`, `min_samples_leaf`, `min_samples_split`, `max_leaf_nodes`, `min_impurity_decrease`. Cheap, but may stop before a split that would have enabled a great one below it.
- **Post-pruning:** grow the full tree, then cut back subtrees that don't pay for themselves on held-out data.

$$
R_\alpha(T)=R(T)+\alpha\,|T|
$$

- $R(T)$: training error (or impurity) of tree T
- $|T|$: number of leaves
- $\alpha$: price per leaf; larger α → smaller tree

**Cost-complexity pruning** (CART) charges $\alpha$ per leaf. As $\alpha$ grows from 0, the subtree whose removal costs the least error per leaf saved is pruned first, giving a nested sequence of ever-smaller trees. Pick $\alpha$ by cross-validation — scikit-learn exposes it as `ccp_alpha`.

## In code

```python
import numpy as np

def entropy(y):
  p = np.bincount(y) / len(y)
  p = p[p > 0]
  return -(p * np.log2(p)).sum()

def gini(y):
  p = np.bincount(y) / len(y)
  return 1 - (p ** 2).sum()

def best_split(X, y, impurity):
  parent, best = impurity(y), (0.0, None, None)       # (gain, feature, threshold)
  for j in range(X.shape[1]):
      v = np.unique(X[:, j])
      for t in (v[:-1] + v[1:]) / 2:                    # midpoints
          L = X[:, j] <= t
          child = (L.sum() * impurity(y[L]) + (~L).sum() * impurity(y[~L])) / len(y)
          if parent - child > best[0]:
              best = (parent - child, j, t)
  return best

def grow(X, y, impurity=entropy, depth=0, max_depth=3, min_leaf=1):
  gain, j, t = best_split(X, y, impurity)
  if depth == max_depth or impurity(y) == 0 or j is None or len(y) < 2 * min_leaf:
      return {"leaf": np.bincount(y).argmax(), "n": len(y)}
  L = X[:, j] <= t
  return {"feature": j, "threshold": t, "gain": gain,
          "left":  grow(X[L],  y[L],  impurity, depth + 1, max_depth, min_leaf),
          "right": grow(X[~L], y[~L], impurity, depth + 1, max_depth, min_leaf)}

def predict(node, x):
  while "leaf" not in node:
      node = node["left"] if x[node["feature"]] <= node["threshold"] else node["right"]
  return node["leaf"]
```

From scratch: both criteria, numeric features, majority-class leaves.

```python
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text

df = pd.DataFrame({
  "Outlook":  "Sunny Sunny Overcast Rain Rain Rain Overcast Sunny Sunny Rain Sunny Overcast Overcast Rain".split(),
  "Temp":     "Hot Hot Hot Mild Cool Cool Cool Mild Cool Mild Mild Mild Hot Mild".split(),
  "Humidity": "High High High High Normal Normal Normal High Normal Normal Normal High Normal High".split(),
  "Wind":     "Weak Strong Weak Weak Weak Strong Strong Weak Weak Weak Strong Strong Weak Strong".split(),
  "Play":     "No No Yes Yes Yes No Yes No Yes Yes Yes Yes Yes No".split(),
})
X = pd.get_dummies(df.drop(columns="Play"))
tree = DecisionTreeClassifier(criterion="entropy", random_state=0).fit(X, df.Play)
print(export_text(tree, feature_names=list(X.columns)))

# Choosing the pruning strength on real data:
# path = DecisionTreeClassifier().cost_complexity_pruning_path(X_train, y_train)
# then cross-validate over path.ccp_alphas
```

The play-tennis tree with scikit-learn (one-hot features, entropy criterion) — and printed rules.

> **Why the sklearn tree looks different:** CART makes only binary splits, so the three-way Outlook question becomes two yes/no questions on one-hot columns (e.g. *Outlook_Overcast ≤ 0.5?*). The rules it learns are equivalent.

**Strengths**

- Every prediction must be explainable — the path is a readable rule.
- Mixed numeric and categorical features; no scaling needed; thresholds and interactions found automatically.
- You need a fast baseline, or the building block for random forests and gradient boosting.

**Limitations**

- You need accuracy from a single model: a deep tree overfits, a shallow one underfits.
- Stability matters: a small change in the data can produce a completely different tree.
- The true boundary is smooth or diagonal: axis-aligned splits approximate it with a staircase.
- You need to extrapolate: a regression tree can never predict outside the range of its training targets.

- **Medical triage & credit policy:** Rules that must be audited and explained to regulators or patients.
- **Feature exploration:** The first few splits reveal which variables matter most, and at which thresholds.
- **Business rules:** Turn historical decisions into explicit if-then logic.
- **Inside ensembles:** Random forests, XGBoost, LightGBM and CatBoost are all built from trees.

> **Unlimited depth memorizes:** With default settings a tree splits until every leaf is pure. Always limit `max_depth` / `min_samples_leaf`, or prune with `ccp_alpha`, chosen by cross-validation — and compare train vs validation accuracy.

> **Biased importances:** Impurity-based feature importances (summed gain per feature) favour high-cardinality features such as IDs and timestamps. Use permutation importance on held-out data.

**Question:** A node holds 8 points, 4 of each class. Its entropy and Gini impurity are…

- A. 0 and 0
- B. 1 bit and 0.5
- C. 0.5 bits and 0.25
- D. 1 bit and 1

**Answer:** B. 1 bit and 0.5 — $H=-2\cdot\tfrac12\log_2\tfrac12=1$ bit and $G=1-(0.5^2+0.5^2)=0.5$ — both are the maximum for two classes.

**Question:** A parent has entropy 1.0. A split sends 6 points to a pure child and 2 points to a 50/50 child. The information gain is…

- A. 0
- B. 0.25
- C. 0.75
- D. 1.0

**Answer:** C. 0.75 — Weighted child entropy $=\tfrac68\cdot0+\tfrac28\cdot1=0.25$, so the gain is $1-0.25=0.75$ bits.

**Question:** Why does C4.5 use the gain ratio instead of raw information gain?

- A. It is faster to compute
- B. Raw gain favours attributes with many distinct values, like an ID column
- C. Gain ratio works for regression
- D. Raw gain can be negative

**Answer:** B. Raw gain favours attributes with many distinct values, like an ID column — An ID splits every row into its own pure child, maximizing gain while generalizing to nothing. Dividing by the split information penalizes such fragmenting splits.

**Question:** Which preprocessing does a decision tree require?

- A. Standardize features
- B. Log-transform skewed features
- C. None — splits depend only on the order of values
- D. PCA

**Answer:** C. None — splits depend only on the order of values — A threshold split is unchanged by any monotonic transform of a feature.

**Key points**

- Impurity measures how mixed a node is: entropy (bits), Gini, or variance for regression. A pure node has impurity 0 and becomes a leaf.
- Information gain = parent impurity − size-weighted child impurity; greedily split on the largest gain.
- Weighted child entropy equals the tree's training cross-entropy, so maximizing gain minimizes log-loss.
- Numeric features: try midpoints between sorted values. Categorical: one branch per value (ID3) or binary groupings (CART).
- Limit depth / leaf size or prune with cost-complexity α; use ensembles when you need accuracy.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
