Skip to content
mlmentorship

Decision trees

Recursively split the feature space along axis-aligned thresholds chosen to maximize a purity criterion. The base learner of GBDT and random forests.

Published · 5 min read ·Core ·Foundation

Visual quick review

Visual first · depth when needed

Map each root-to-leaf rule path to one axis-aligned region of feature space and its constant leaf prediction.

Preparing the visual…

Summary

A decision tree partitions the feature space by a sequence of axis-aligned threshold tests on individual features, assigning a constant prediction (class probability for classification, mean target for regression) to each leaf. Trained greedily by choosing splits that maximize information gain or equivalently minimize a purity / impurity criterion.

Single trees are rarely the production model. Variance is too high. But they are the building block of the dominant tabular learners: gradient boosting (xgboost, lightgbm, catboost) and random forests. Understanding tree training is the prerequisite for using or tuning either.

Trees naturally handle missing values, mixed-type features, non-linear interactions, and require essentially no feature scaling. This is why they remain the strongest baseline on heterogeneous tabular data.

The algorithm (CART, Breiman et al., 1984)

For each node:

  1. For each feature and each candidate threshold :
    • Split data into (left child) and (right child).
    • Compute the impurity of each child (Gini, entropy, or MSE).
    • Compute the weighted impurity reduction.
  2. Pick the with maximum reduction.
  3. Recurse on each child until a stopping criterion (max depth, min samples per leaf, no further reduction).

The greedy choice is locally optimal but not globally; finding the globally optimal tree is NP-hard.

Learning objective: map each root-to-leaf rule path to one axis-aligned region of feature space and its constant leaf prediction.

Rules become regions

A child split cuts only the region that reaches it.

A decision tree and its matching feature-space partition The upper plot contains four circle samples and four triangle samples. A full-height vertical root split at feature one equal to four sends four points left and four right. Only the right region receives a horizontal child split at feature two equal to three. The matching tree below has a root test feature one less than or equal to four. Its yes branch ends at a leaf with triangle probability one quarter. Its no branch tests feature two less than or equal to three, producing a pure triangle leaf below and a pure circle leaf above. A highlighted new point follows the no then yes path to the triangle leaf. feature 1 feature 2 root: x1 ≤ 4 child: x2 ≤ 3 new point 8 TRAINING POINTS: ○ CLASS 0, △ CLASS 1 THE SAME PARTITION, WRITTEN AS RULES x1 ≤ 4? yes no leaf L P(△) = 1/4 x2 ≤ 3? yes no leaf R1: P(△)=1 R2: P(△)=0
Read it this way: begin with the solid vertical root split: every point goes left or right. The dashed horizontal test belongs only to the right child, so it cuts only that half-plane. A root-to-leaf path is therefore an intersection of threshold rules, forming a rectangle here, and every point in that rectangle receives the leaf's constant class probability. The highlighted triangle follows “no, then yes” to leaf R1. Original schematic checked against the scikit-learn tree formulation and The Elements of Statistical Learning.

Split criteria

For classification at a node with class proportions :

  • Gini impurity: . Equals expected error of random labeling proportional to .
  • Entropy: . Information gain = parent entropy minus weighted child entropies.

Gini and entropy give nearly identical splits in practice; Gini is slightly cheaper.

For regression: variance of the target within the node, equivalent to MSE under constant prediction.

Stopping and pruning

Stop splitting when:

  • Max depth reached.
  • Number of samples at the node falls below a threshold.
  • Best impurity reduction is below a threshold.
  • All samples have the same target.

Pruning: train deep, then collapse branches that don’t reduce held-out error. Cost-complexity pruning (CCP) trades depth against penalty .

In practice with ensembles (boosting, forests), individual trees are kept shallow (depth 6–8 for boosting, depth limited or full for forests with bagging variance averaging).

Strengths and weaknesses

Strengths:

  • Handles non-linear interactions for free.
  • No feature scaling needed.
  • Handles missing values (with surrogate splits or built-in handling in xgboost/lightgbm).
  • Handles mixed numeric / categorical (with appropriate encoding).
  • Interpretable: every prediction is a path of explicit rules.

Weaknesses:

  • High variance: small data perturbations change splits dramatically.
  • Greedy: locally optimal, not globally.
  • Axis-aligned splits make it hard to capture rotated decision boundaries (need oblique trees or feature engineering).
  • Single trees are weak. Usually combined into ensembles.

Categorical features

Two main approaches:

  • One-hot: each level becomes a binary feature. Slow; trees grow many useless branches.
  • Native handling (lightgbm, catboost): pre-sort levels by target mean, then split as if the feature were numeric. Much faster and often more accurate.

Common pitfalls

  • Letting trees grow unbounded on small data. Memorizes training set; high variance.
  • Treating categorical features as numeric without one-hot or native handling. Tree splits are ordered; “encoding” a categorical with arbitrary integer codes imposes a meaningless order.
  • Comparing single trees against ensembles unfairly. Single trees should not beat boosted forests; check you are evaluating the right model class.
  • Reading feature importance from a single split. Importance from a single tree is noisy; use ensemble averages or permutation importance.

Found an error or stale claim? Report a correction or send a private note.