Decision Trees

Background

Decision tree algorithms (ID3, C4.5, CART) emerged 1979-1984, Breiman formalized CART in 1984
Mirrors human decision-making: a sequence of yes/no questions
The building block for random forests and gradient boosting - the most-used algorithms in tabular ML

The Concept

A decision tree recursively splits data by the feature that best separates the target classes, creating a binary tree of if-then rules. Each leaf assigns a class (or value for regression). The splitting criterion (Gini impurity, information gain) measures how pure the resulting groups are.

How it Links

Directly generalized by random forests (bagging of trees) and gradient boosting (sequential trees)
Feature importance scores from trees are widely used for feature selection
The recursive binary split connects to CART, CHAID, and oblique tree variants

Concrete Example

A loan approval tree: first split on income > $50k, then on credit score > 650, then on debt-to-income ratio. Each path through the tree corresponds to a rule like: high income AND good credit AND low debt -> approve. Easy to explain to a regulator.

Prerequisites

Math you need: probability and linear algebra basics, Bias, variance, over/under-fitting, Evaluation metrics

Learning outcomes

Describe the recursive top-down greedy splitting algorithm used by CART, ID3, and C4.5.
Derive Gini impurity, entropy, information gain, and variance reduction as splitting criteria.
Explain cost-complexity pruning and how it trades training fit against tree size.
Recognize why decision trees are scale-invariant, handle mixed feature types, and yet have high variance.
Implement a CART classifier from scratch in NumPy and contrast it with sklearn DecisionTreeClassifier and DecisionTreeRegressor.

TL;DR

A decision tree splits the feature space into axis-aligned rectangles by greedily choosing the split that most reduces an impurity measure: Gini $G = 1 - \sum_k p_k^{2}$ or entropy $H = -\sum_k p_k \log p_k$ for classification, variance for regression. The classical algorithms are CART [1], ID3 [2], and C4.5 [3]. Trees are scale-invariant and natively handle mixed numeric and categorical features, but they overfit aggressively and are unstable under tiny data perturbations. Cost-complexity pruning $R_{\alpha}(T) = R(T) + \alpha |T|$ collapses subtrees whose error reduction does not justify their size [4].

Intuition

A decision tree is a flowchart. At each internal node, ask one question of the form “is feature $j$ at most $\tau$ ?” and route the example left or right. At each leaf, store a class label (classification) or a real value (regression). Training is simple: start at the root, look at every feature and every candidate threshold, pick the split that most “purifies” the children, and recurse.

What a tree really represents

Every fully-grown decision tree corresponds to a partition of $\mathbb{R}^{d}$ into axis-aligned rectangles, one per leaf. The model itself is a piecewise constant function on that partition: it predicts the majority class (or mean) inside each rectangle. That is the entire conceptual content - everything else (splitting criteria, pruning, ensembles) is about choosing the partition.

Tree

Induced partition of feature space

x1 at most 0.4 ?yesnopredict Ax2 at most 0.5 ?yesnopredict Bpredict CABCx1 = 0x1 = 1x2 = 1x2 = 0

Figure 1. Each internal node tests one feature against a threshold, so the tree partitions feature space into axis-aligned rectangles. Predictions are constant inside each leaf rectangle.

A short history

1963
1984
1986
1993
1996
2001

Math

Math: splitting criteria, information gain, and pruning

Setup

Let $S$ be the set of training examples reaching a node, with class labels in $\{1, \dots, K\}$ . Let $p_k = \tfrac{1}{|S|}\sum_{i \in S}\mathbb{1}[y_i = k]$ be the empirical class distribution at the node. A candidate split partitions $S$ into $\{S_v\}_v$ on the values of feature $A$ (binary in CART, multi-way in ID3 / C4.5).

Gini impurity

G(S) = \sum_{k=1}^{K} p_k (1 - p_k) = 1 - \sum_{k=1}^{K} p_k^{2}.

$G(S) \in [0, 1 - 1/K]$ , with $G = 0$ iff $S$ is pure. Geometrically, Gini is the probability that two independently drawn samples from $S$ have different labels.

Shannon entropy

H(S) = -\sum_{k=1}^{K} p_k \log p_k,

with the convention $0 \log 0 = 0$ . Like Gini, $H(S) \ge 0$ with equality iff $S$ is pure. Maximum at the uniform distribution, where $H = \log K$ .

Information gain (used by ID3 and C4.5)

The information gain of split $A$ is the expected entropy reduction:

\mathrm{IG}(S, A) = H(S) - \sum_{v} \frac{|S_v|}{|S|} \, H(S_v).

ID3 picks the split with the largest information gain. C4.5 normalizes by the split information $-\sum_v \tfrac{|S_v|}{|S|}\log\tfrac{|S_v|}{|S|}$ to get gain ratio, which corrects ID3’s bias toward features with many values [3].

Variance reduction (regression trees)

For a continuous target $y$ , replace impurity with variance:

\mathrm{Var}(S) = \frac{1}{|S|} \sum_{i \in S} (y_i - \bar{y}_S)^{2},

and pick the split that maximises

\Delta_{\mathrm{var}}(S, A) = \mathrm{Var}(S) - \sum_{v} \frac{|S_v|}{|S|}\,\mathrm{Var}(S_v).

Equivalently, this is the split that minimises the within-children sum of squared residuals - exactly the stagewise OLS objective with a piecewise-constant model, leaf by leaf [1].

Why all three criteria pick similar splits

Gini, entropy, and the misclassification rate $1 - \max_k p_k$ are all strictly concave in $p$ , so the Jensen-style argument

\Phi(S) - \sum_{v}\frac{|S_v|}{|S|}\Phi(S_v) \ge 0

holds for any concave $\Phi$ , with equality iff the children inherit the parent distribution. The three measures rank candidate splits very similarly in practice; CART defaults to Gini because it is cheap (no logarithms) and slightly less sensitive to the tail of the class distribution [4].

Cost-complexity pruning

A fully-grown CART tree $T_0$ memorizes the training set. To control overfitting, define for any subtree $T \subseteq T_0$ the cost-complexity functional

R_{\alpha}(T) = R(T) + \alpha\, |T|,

where $R(T)$ is the training error (or sum of squared residuals for regression) and $|T|$ is the number of leaves. Walking $\alpha$ from $0$ upward yields a finite, nested sequence of subtrees $T_0 \supset T_1 \supset \dots \supset T_m$ , each minimizing $R_{\alpha}(T)$ on a corresponding $\alpha$ interval. Pick $\alpha$ by cross-validation; the resulting subtree is the cost-complexity-pruned tree [1].

Reduced-error pruning

A simpler post-hoc method: hold out a validation set, then for every internal node check whether collapsing it to a leaf increases validation error. If it does not, collapse. Iterate bottom-up. This is the original C4.5-era heuristic, slightly less principled than cost-complexity pruning but very fast [3].

Why trees are scale-invariant and how axis-alignment hurts

Scale invariance

Each split tests “is feature $j$ at most $\tau$ ?”. The truth value of that test is unchanged if you transform $x_j$ by any strictly monotonic function: $x_j \mapsto x_j + c$ , $x_j \mapsto a x_j$ for $a > 0$ , $x_j \mapsto \log x_j$ , or any rank transform. Consequence: trees do not need feature scaling, do not need standardization, and are robust to outliers in feature space (an outlier just becomes its own thin leaf at one end of the partition).

Native handling of mixed types

Continuous features get sorted and tested at midpoints; categorical features get partitioned by subset (CART) or one branch per value (ID3). No one-hot encoding required. We will see in a moment why one-hot encoding actually hurts tree quality.

The axis-alignment limitation

Each split is a hyperplane perpendicular to one feature axis, so the resulting decision boundary is a union of axis-aligned rectangles. Diagonal boundaries in the underlying problem are approximated by stair-steps, requiring many splits to achieve modest accuracy. This is the core reason why trees benefit from feature engineering (rotations, sums, products) and why oblique-split variants (e.g. CART with linear combination splits) exist - but those break both the speed and the interpretability that make trees attractive to begin with [5].

No extrapolation

Because predictions are constants inside leaves, a regression tree predicts the leaf mean for any test point in the leaf’s rectangle - including points far outside the training range along that rectangle’s open sides. Trees cannot extrapolate; they only interpolate. This is a hard limit, not a tuning issue.

Algorithm

Step	Operation
1	Start at the root with the full training set S.
2	If S is pure, max_depth reached, or \|S\| below min_samples_split, make a leaf with the majority class (classification) or the mean target (regression).
3	Otherwise: for every feature and every candidate threshold, compute the splitting criterion gain.
4	Pick the (feature, threshold) pair with the largest gain. Split S into S_left and S_right.
5	Recurse on S_left and S_right.
6	Optionally: post-prune via cost-complexity (CART) or reduced-error pruning (C4.5).

# Recursive CART pseudocode
def build_tree(S, depth=0):
    if pure(S) or depth >= max_depth or len(S) < min_samples_split:
        return Leaf(majority_class(S))
    feature, threshold, gain = best_split(S)
    if gain <= 0:
        return Leaf(majority_class(S))
    S_left, S_right = partition(S, feature, threshold)
    return Node(feature, threshold,
                build_tree(S_left,  depth + 1),
                build_tree(S_right, depth + 1))

Three classic algorithms compared

Algorithm	Splitting criterion	Continuous features?	Missing values?	Regression?	Pruning
ID3 (Quinlan 1986)	Information gain (entropy)	No - assumes categorical	No	No - classification only	None (grows to purity)
C4.5 (Quinlan 1993)	Gain ratio (normalized info gain)	Yes - sort + threshold	Yes - probabilistic routing	No - C4.5 is classification; M5 is the regression variant	Reduced-error / pessimistic
CART (Breiman 1984)	Gini (clf) or variance reduction (reg)	Yes	Surrogate splits	Yes	Cost-complexity (alpha)

Implementations

The from-scratch NumPy version recurses through _build_tree, returning a plain dict so the structure is easy to inspect. The sklearn versions are the production one-liners and include plot_tree for visualization.

python

import numpy as np

def gini(y):
  if len(y) == 0:
      return 0.0
  _, counts = np.unique(y, return_counts=True)
  p = counts / counts.sum()
  return 1.0 - np.sum(p * p)

def best_split(X, y):
  n, d = X.shape
  best = (None, None, 0.0)        # (feature, threshold, gain)
  parent = gini(y)
  for j in range(d):
      order = np.argsort(X[:, j])
      xs, ys = X[order, j], y[order]
      for k in range(1, n):
          if xs[k] == xs[k - 1]:
              continue
          t = 0.5 * (xs[k] + xs[k - 1])
          left_y, right_y = ys[:k], ys[k:]
          child = (k / n) * gini(left_y) + ((n - k) / n) * gini(right_y)
          gain = parent - child
          if gain > best[2]:
              best = (j, t, gain)
  return best

def build_tree(X, y, depth=0, max_depth=4, min_samples=2):
  if len(set(y.tolist())) == 1 or depth >= max_depth or len(y) < min_samples:
      vals, counts = np.unique(y, return_counts=True)
      return {"leaf": True, "pred": int(vals[np.argmax(counts)])}
  j, t, gain = best_split(X, y)
  if j is None or gain <= 0:
      vals, counts = np.unique(y, return_counts=True)
      return {"leaf": True, "pred": int(vals[np.argmax(counts)])}
  mask = X[:, j] <= t
  return {
      "leaf": False, "feature": j, "threshold": float(t),
      "left":  build_tree(X[mask],  y[mask],  depth + 1, max_depth, min_samples),
      "right": build_tree(X[~mask], y[~mask], depth + 1, max_depth, min_samples),
  }

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

# tiny dataset
rng = np.random.default_rng(0)
X = rng.normal(size=(40, 2))
y = (X[:, 0] + X[:, 1] > 0).astype(int)
tree = build_tree(X, y, max_depth=3)
preds = np.array([predict_one(tree, x) for x in X])
print("train acc:", float((preds == y).mean()))

About 50 lines: best_split + build_tree + predict_one. The tree itself is just a nested dict.

Run the from-scratch NumPy version live in the browser:

Idle (packages: numpy)

import numpy as np

def gini(y):
  if len(y) == 0:
      return 0.0
  _, counts = np.unique(y, return_counts=True)
  p = counts / counts.sum()
  return 1.0 - np.sum(p * p)

def best_split(X, y):
  n, d = X.shape
  best = (None, None, 0.0)
  parent = gini(y)
  for j in range(d):
      order = np.argsort(X[:, j])
      xs, ys = X[order, j], y[order]
      for k in range(1, n):
          if xs[k] == xs[k - 1]:
              continue
          t = 0.5 * (xs[k] + xs[k - 1])
          child = (k / n) * gini(ys[:k]) + ((n - k) / n) * gini(ys[k:])
          gain = parent - child
          if gain > best[2]:
              best = (j, t, gain)
  return best

def build_tree(X, y, depth=0, max_depth=4):
  if len(set(y.tolist())) == 1 or depth >= max_depth or len(y) < 2:
      vals, counts = np.unique(y, return_counts=True)
      return {"leaf": True, "pred": int(vals[np.argmax(counts)])}
  j, t, gain = best_split(X, y)
  if j is None or gain <= 0:
      vals, counts = np.unique(y, return_counts=True)
      return {"leaf": True, "pred": int(vals[np.argmax(counts)])}
  mask = X[:, j] <= t
  return {"leaf": False, "feature": int(j), "threshold": float(t),
          "left":  build_tree(X[mask],  y[mask],  depth + 1, max_depth),
          "right": build_tree(X[~mask], y[~mask], depth + 1, max_depth)}

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

rng = np.random.default_rng(0)
X = rng.normal(size=(60, 2))
y = (X[:, 0] + X[:, 1] > 0).astype(int)
tree = build_tree(X, y, max_depth=3)
preds = np.array([predict_one(tree, x) for x in X])
print("train acc:", round(float((preds == y).mean()), 4))
print("first split: feature", tree["feature"], "threshold", round(tree["threshold"], 3))

(no output yet)

Interactive demo: how the partition grows with depth

Drag the slider to increase max_depth. The shaded rectangles are the leaf regions; predictions are constant inside each rectangle. Notice how shallow trees underfit the diagonal-looking separation, and how deep trees produce many tiny rectangles that capture noise in the training set.

Decision tree (CART, Gini) on a toy 2D dataset

max_depth3leaves = 3train acc = 100.0%

class Aclass Bclass C

Real-world uses

Where decision trees still pay rent

Even after the rise of deep learning, single decision trees remain in production wherever interpretability is not optional:

Medical risk scores. SAPS / APACHE-style severity scores and FDA-cleared point-of-care models often boil down to a small handcrafted tree clinicians can read off the bedside chart.
Credit and insurance underwriting. Regulated decisions need an auditable rule, and a depth-3 tree fits in a one-page explanation document.
Kaggle and competition baselines. A DecisionTreeClassifier with default settings is the canonical “what does the data say at first glance?” model.
RuleFit and rule-extraction systems. Trees are mined for IF/THEN rules that are then aggregated into a sparse linear model with $\ell_1$ regularization, giving an interpretable hybrid.

Pitfalls

High variance and instability

Tiny perturbations of the training set (one extra example, a swap of two rows) can produce a completely different tree. The greedy top-down algorithm makes splits that are locally optimal but globally fragile, especially when several candidate splits have nearly identical gain. Bagging and random forests exist precisely to average this variance away.

One-hot encoding hurts trees

If you one-hot encode a high-cardinality categorical feature with $L$ levels, the tree sees $L$ binary features, each with at most $1/L$ of the rows flipping the bit. Gini gain on each binary feature is therefore tiny, and the splitter prefers a continuous feature even when the categorical feature is the truly informative one. The data also fragments: the same level can appear in many leaves and never accumulate enough mass to justify a split. Use native categorical handling (LightGBM, CatBoost, sklearn’s HistGradientBoosting with categorical_features), target encoding with leave-one-out, or ordinal codes if the order is meaningful.

Will fit pure noise

A fully-grown tree achieves zero training error on any dataset because every leaf can be made to contain a single example. Without max_depth, min_samples_leaf, or post-pruning, the tree memorises the training labels, including their noise. Always cross-validate one of those regularizers.

Biased toward features with many distinct values

ID3’s information gain favours features with many splits because they mechanically reduce entropy more. C4.5 fixes this with the gain ratio, and CART’s binary-only splits sidestep it, but the same bias re-emerges when you let CART consider many candidate thresholds on a continuous feature relative to a coarse one. Always sanity-check feature importance against permutation importance.

Standardize is wasted effort

Trees are scale-invariant. Z-scoring, log-transforming, or min-max scaling features changes nothing about the resulting tree (up to ties). Save the preprocessing budget for the linear or distance-based models in your stack.

Interview Q&A

Derive information gain from entropy and explain why ID3 picks the largest-gain split.research

Let $S$ be the set of examples at a node and $p_k$ the empirical class proportion. Define Shannon entropy

H(S) = -\sum_{k=1}^{K} p_k \log p_k.

After splitting on feature $A$ with values indexed by $v$ ,

H(S \mid A) = \sum_{v} \frac{|S_v|}{|S|} H(S_v),

which is the expected entropy of the children weighted by their probabilities. Information gain is

\mathrm{IG}(S, A) = H(S) - H(S \mid A) = I(Y; A),

i.e. the mutual information between the label $Y$ and the feature $A$ . By the data-processing inequality, $\mathrm{IG} \ge 0$ with equality iff $Y \perp A$ , so a positive gain means the split tells us something about the label. ID3 greedily picks the largest gain at every node, which is locally optimal but globally suboptimal (the joint argmax over depth- $D$ trees is NP-hard in general) [2][4].

Why do decision trees overfit, and how does that relate to VC dimension?research

A binary tree with $L$ leaves can shatter any set of $L$ points whose feature vectors are pairwise distinguishable along axis-aligned splits: just keep splitting until each leaf holds exactly one training example. Hence the VC dimension of the class of decision trees with at most $L$ leaves is at least $L$ (and grows linearly in $L$ for axis-aligned trees). A fully-grown tree with $|T| \approx n$ leaves therefore has VC dimension on the order of $n$ , which is the worst case for a sample of size $n$ : the standard PAC bound

\mathrm{err}_{\mathrm{gen}} \le \mathrm{err}_{\mathrm{train}} + \mathcal{O}\!\left(\sqrt{\tfrac{\mathrm{VC} \cdot \log n}{n}}\right)

becomes vacuous. That is the formal reason fully-grown trees memorize and generalize poorly. Pruning (capping $|T|$ via cost-complexity), early stopping (max_depth, min_samples_leaf), and ensembling (bagging, boosting) are all variance-control mechanisms aimed at the same problem [4].

Why does one-hot encoding hurt trees on high-cardinality categorical features?onsite

Suppose a categorical feature has $L$ levels and one level alone is the truly informative one. After one-hot encoding, the tree sees $L$ binary features. Each binary feature has at most $1/L$ of the rows on its “1” side, so the maximum impurity decrease from any single one-hot feature is bounded by roughly $1/L$ of the parent impurity (Gini is concave with maximum slope $\propto p(1-p)$ , so a split that moves a $p \approx 1/L$ fraction of rows gains very little). Continuous or low-cardinality features routinely beat this, so the splitter ignores the actually-useful categorical feature.

A second problem is data fragmentation: the same level cannot be aggregated across multiple binary indicators, so each level’s training mass is split across many leaves and never accumulates the statistical power needed for a deep, confident split. Native categorical handling (LightGBM’s optimal categorical splits, CatBoost’s ordered target encoding, sklearn HistGradientBoosting with categorical_features) avoids both issues by treating the feature as one variable and considering subset partitions $S \subseteq \{1, \dots, L\}$ [4].

What is the connection between a decision tree and nearest-neighbour learning?onsite

A decision tree is a piecewise constant nearest-leaf learner. Each leaf corresponds to a region $R_{\ell}$ of feature space, and the prediction at any test point $x$ is the majority class (or mean target) of the training points that fell into the same leaf. In other words, the tree’s prediction at $x$ is exactly the prediction of a 1-NN classifier whose distance metric is the “are we in the same leaf?” pseudo-metric.

This makes trees a kind of learned distance metric: the splitting algorithm chooses a partition of the input space, and “nearest neighbour” is then defined relative to that partition rather than to Euclidean distance. It also explains why trees handle mixed feature types so gracefully: the partition ignores feature scales, just as the 1-NN classifier under any monotone-invariant metric would.

Derive variance reduction as the splitting criterion for regression trees.research

For a regression target $y_i \in \mathbb{R}$ , the leaf prediction at a node $S$ is the empirical mean $\bar{y}_S = \tfrac{1}{|S|}\sum_{i \in S} y_i$ , which is the unique constant $c$ that minimises $\sum_{i \in S}(y_i - c)^{2}$ . The training cost of a leaf is therefore the within-node variance times $|S|$ :

\mathrm{SSE}(S) = \sum_{i \in S}(y_i - \bar{y}_S)^{2} = |S| \cdot \mathrm{Var}(S).

A binary split into $S_L, S_R$ replaces $\mathrm{SSE}(S)$ with $\mathrm{SSE}(S_L) + \mathrm{SSE}(S_R)$ . The reduction is

\Delta = \mathrm{SSE}(S) - \bigl[\mathrm{SSE}(S_L) + \mathrm{SSE}(S_R)\bigr] = |S| \mathrm{Var}(S) - |S_L|\mathrm{Var}(S_L) - |S_R|\mathrm{Var}(S_R),

which can be rewritten using the law of total variance as

\Delta = \frac{|S_L| |S_R|}{|S|} (\bar{y}_{S_L} - \bar{y}_{S_R})^{2} \ge 0.

So variance reduction is exactly the squared difference between child means, weighted by the harmonic-mean-style factor $|S_L||S_R|/|S|$ . The split that maximises $\Delta$ is the split whose children are most separated in target space, normalised by how balanced the split is. This recovers Friedman’s improvement criterion used in scikit-learn and gradient boosting [1].

Check yourself

Score: 0 / 5(0 answered)

1. Which expression is the Gini impurity at a node with class proportions p_1, ..., p_K?
2. Why does CART use cost-complexity pruning instead of stopping early on max_depth alone?
3. Which is NOT a property of decision trees?
4. On a high-cardinality categorical feature with L levels, one-hot encoding hurts trees because:
5. For a regression tree, the variance-reduction split corresponds to:

Build it yourself

A short evening project:

Implement the from-scratch CART above and verify on sklearn.datasets.load_iris that you match the sklearn DecisionTreeClassifier(criterion='gini', max_depth=3) accuracy to within a percentage point.
Add a regression mode using variance reduction. Test on a synthetic $y = \sin x + \varepsilon$ dataset.
Implement reduced-error pruning on a held-out validation split and plot validation accuracy vs $|T|$ .
Stretch: implement cost-complexity pruning. You will discover that the alpha sequence is exactly the breakpoints where some internal node’s $R(t) - R(T_t)$ ratio changes the argmin.

References

Breiman, L., Friedman, J. H., Olshen, R. A., and Stone, C. J. (1984). Classification and Regression Trees. Wadsworth & Brooks/Cole. ISBN 978-0-412-04841-8
Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning 1(1), 81-106. doi:10.1007/BF00116251
Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann. ISBN 978-1-55860-238-0
Hastie, T., Tibshirani, R., and Friedman, J. (2009). The Elements of Statistical Learning, 2nd ed.. Springer. https://hastie.su.domains/ElemStatLearn/
Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer. ISBN 978-0-387-31073-2

k-Nearest Neighbors Random Forests