Decision trees

A model made of questions

A decision tree predicts by asking a sequence of yes/no questions about the features: is age < 30? is income > 50k? Each internal node tests one feature against a threshold, each branch is an answer, and each leaf holds a prediction (a class or a number). Geometrically a tree carves the feature space into axis-aligned rectangles, one per leaf, and predicts a constant inside each rectangle. That makes trees piecewise-constant models: flexible (enough rectangles approximate anything), interpretable (every prediction is a readable rule), and completely indifferent to feature scaling (a monotone transform of a feature changes no split).

Intuition. Playing "20 questions", you ask the question whose answer tells you the most. Tree learning formalizes "tells you the most" with impurity.

Measuring impurity

For a node containing samples with class proportions $p_1,\dots,p_K$, three impurity measures are standard:

All three are zero for a pure node and maximal for a uniform node. Gini is the probability that two samples drawn from the node disagree in class; entropy is the expected surprise in bits (1.9 Information theory: entropy, cross-entropy and KL divergence). In practice Gini and entropy give almost identical trees; Gini avoids the logarithm and is scikit-learn's default.

A split sends the $n$ samples of a node into children with sizes $n_j$. Its quality is the information gain (impurity decrease):

Worked example

A node holds 10 samples: 6 "yes" and 4 "no". Its entropy is

Split A sends 4 samples left (4 yes, 0 no) and 6 right (2 yes, 4 no). The left child is pure ($H=0$); the right child has $H(\tfrac13,\tfrac23) = \tfrac13(1.585)+\tfrac23(0.585) = 0.918$. The weighted child entropy is $0.4\cdot 0 + 0.6\cdot 0.918 = 0.551$, so $\text{IG}_A = 0.971 - 0.551 = 0.420$ bits.

Split B sends 5 left (3 yes, 2 no) and 5 right (3 yes, 2 no). Both children have the parent's proportions, so $H = 0.971$ each and $\text{IG}_B = 0$: the question told us nothing.

With Gini instead: parent $1-(0.36+0.16)=0.48$; Split A children $0$ and $1-(\tfrac19+\tfrac49)=0.444$, weighted $0.267$, decrease $0.213$. Same ranking.

Math check. Information gain is never negative, because entropy is concave and the weighted child entropy is an average of entropies of distributions whose mixture is the parent (Jensen's inequality). A useless split gives exactly zero.

Growing a tree: CART

The classic algorithm (CART; ID3 and C4.5 are relatives) is greedy, top-down recursive partitioning:

1. For every feature, and for every candidate threshold (for a numeric feature: midpoints between consecutive sorted distinct values), compute the impurity decrease of the split.
2. Take the best split, create two children, and recurse into each child.
3. Stop when a node is pure, too small, or a depth limit is hit; the leaf predicts the majority class (classification) or the mean target (regression).

For regression trees the impurity is the within-node sum of squared errors, so a split is chosen to minimize

and the prediction inside each leaf is the leaf mean — exactly the constant that minimizes squared error. Evaluating all thresholds of one feature at a node costs $O(n\log n)$ after sorting, so one level costs roughly $O(d\,n\log n)$ for $d$ features. Greedy means the tree never revisits a split: the globally optimal tree is NP-hard to find, and the greedy one is usually good enough once we ensemble.

Stopping and pruning

A tree grown until every leaf is pure has zero training error and memorizes noise: it is the archetypal high-variance, low-bias model (3.5 Evaluating models: metrics, validation and the bias–variance trade-off). Two remedies:

• Pre-pruning (early stopping): max_depth, min_samples_leaf, min_samples_split, min_impurity_decrease, max_leaf_nodes. Cheap and effective; tune by cross-validation.
• Post-pruning (cost-complexity pruning): grow a full tree $T_0$, then minimize $R_\alpha(T) = R(T) + \alpha\,|T|$ where $R(T)$ is the training error and $|T|$ the number of leaves. Increasing $\alpha$ collapses the weakest subtrees one by one; pick $\alpha$ by cross-validation (ccp_alpha in scikit-learn).

Categorical features and missing values

Numeric features split on a threshold. Categorical features can be one-hot encoded (each dummy becomes a binary split), or handled natively: C4.5 makes a multi-way split, LightGBM searches optimal category groupings, CatBoost uses ordered target statistics (3.9 Ensembles: bagging, random forests and gradient boosting). Missing values are handled gracefully by trees in two ways: surrogate splits (CART finds a backup feature that mimics the chosen split) or a learned default direction (XGBoost/LightGBM send missing values to whichever child reduces loss more). Because trees only compare values to thresholds, they are invariant to monotone transforms: no standardization, no log-transforms needed.

Interpretability, instability and the shape of the boundary

Every path from root to leaf is a rule you can read aloud, which is why trees are popular in medicine and credit scoring. Scikit-learn's default feature importance (total impurity decrease attributed to a feature, "MDI") is biased toward high-cardinality and continuous features; permutation importance and SHAP values (3.13 Feature engineering, data quality and data-centric ML) are more trustworthy.

The price of flexibility is instability: changing a handful of training points can change the root split and therefore the whole tree — high variance in the bias–variance sense. And because splits are axis-aligned, a tree represents a diagonal boundary only as a staircase of many splits, whereas logistic regression (3.3 Logistic regression and softmax classification) or an SVM (3.10 Support vector machines and kernels) draws it with one line. Both weaknesses are exactly what bagging and boosting fix next.

Where this shows up later

• Averaging many trees kills their variance (random forests) and adding them sequentially fixes their bias (gradient boosting) — 3.9 Ensembles: bagging, random forests and gradient boosting.
• Permutation importance and SHAP for trees — 3.13 Feature engineering, data quality and data-centric ML; the end-to-end tabular project uses GBDTs built from these trees — 3.14 Project: end-to-end tabular ML with scikit-learn.
• Compare the staircase boundary with the smooth boundaries a neural network learns — 4.1 From perceptron to MLP; universal approximation; routing inputs to experts in MoE layers is a learned, soft "split" — 7.11 Mixture of Experts; routing patterns in agent systems are if/else at the LLM level — 10.5 Agentic workflow patterns.