Decision trees

Problem

A linear model draws one straight boundary and a nearest-neighbor model needs a distance that makes sense for every feature. Real tabular data is often neither: a rule such as "approve if income is high, or if debt is low and the account is old" is a handful of thresholds on different columns, with no obvious distance between a salary and an age. A decision tree learns rules of exactly that shape directly from labelled rows, and the finished model can be read aloud.

The difficulty is that the number of possible trees is astronomically large, and a tree allowed to grow without limit can always carve the training rows into single-row leaves. On the 12 rows used below it reaches 100% training accuracy with 6 leaves, which says almost nothing about new data. So there are two questions: how do you pick each question, and when do you stop asking?

Intuition

Play twenty questions. Each question should split the remaining possibilities into groups that are as pure as you can manage, ideally all one answer, so that the next question has less to do. A tree is built the same way: look at every question of the form "feature ≤ threshold", pick the one that leaves the two groups purest, and then repeat inside each group. This is greedy: it never looks ahead, so it can miss a pair of questions that are only good together.

Because every question looks at one feature at a time, the tree cuts the input space into boxes with sides parallel to the axes, and predicts a constant (the majority class, or the mean) in each box. A diagonal boundary has to be approximated by a staircase of boxes. More boxes fit the training data better, but past a point they fit its noise.

Each split is one axis-parallel line. The right region is already pure, so the tree stops there; the left region gets a second question.

Mechanics

Impurity: how mixed is a node?

For a node whose rows have class proportions p_k, two measures of mixing are in common use. Both are zero for a pure node and largest when the classes are evenly mixed.

Gini: G = 1 − Σ_k p_k²     Entropy: H = − Σ_k p_k log₂ p_k

For two classes at p = ½, G = 0.5 and H = 1 bit. Gini is the chance of mislabelling a random row if you label it by drawing from the node's own class mix. Entropy measures the information in the label. In practice they pick the same split on most data: here the best root split is x1 ≤ 5.5 under Gini and x1 ≤ 5.5 under entropy. In scikit-learn the entropy criterion takes its logarithm through a helper that divides by ln 2, so it is in bits, and "log_loss" is the same criterion under another name.

Gini is about half the height of entropy at the middle but has the same shape, so they rank splits almost identically.

Choosing a split

For each feature, sort the distinct values and consider a threshold halfway between each adjacent pair. Send rows with the feature at or below the threshold left, the rest right. Score the split by how much it reduces impurity, weighting each child by its share of the rows:

Δ = I(parent) − (n_L/n) I(left) − (n_R/n) I(right)

The best (feature, threshold) pair is the one with the largest Δ. Then the same procedure runs on each child, recursively. This is the CART algorithm (Breiman et al., 1984). scikit-learn's search sorts the node's rows by one feature, walks the sorted order and updates running class counts, so a feature costs O(n log n) at a node. Features are visited in a random order drawn from random_state, so exact ties between features can resolve differently from seed to seed.

When to stop

A node becomes a leaf when any of these holds: it is pure; its depth has reached max_depth; it has fewer than min_samples_split rows, or fewer than 2 × min_samples_leaf; or the best split improves impurity by less than min_impurity_decrease. Candidate splits that would leave fewer than min_samples_leaf rows on a side are skipped outright. With the defaults (max_depth=None, min_samples_split=2, min_samples_leaf=1) only purity stops the tree, which is why a default tree fits its training set perfectly unless two identical rows carry different labels. Setting max_leaf_nodes switches to best-first growth, which always splits the leaf with the largest improvement next.

Regression trees

The tree is unchanged except for the impurity and the leaf value. A leaf predicts the mean of its targets, and a node's impurity is the variance of its targets, so a split's score is the reduction in the weighted variance, equivalently the drop in the total sum of squared errors:

I(node) = (1/n) Σ (y_i − ȳ)²     prediction = ȳ     best split minimizes SSE_left + SSE_right

absolute_error uses the median and poisson a deviance, for count targets. Predictions are a staircase of constants, so a regression tree cannot extrapolate beyond the target range it saw.

Pruning: cost-complexity

Instead of stopping early, grow the full tree and cut back. Cost-complexity pruning trades training error against size. With R(T) the sum over leaves of (n_t/N) · I(t), it minimizes

R_α(T) = R(T) + α · |leaves(T)|     α_eff(t) = ( R(t) − R(T_t) ) / ( |leaves(T_t)| − 1 )

The effective alpha of an internal node t is the price per leaf saved if you collapse its subtree T_t into one leaf. Repeatedly collapsing the node with the smallest effective alpha (the weakest link) gives a nested sequence of trees, one for each alpha. Set ccp_alpha to keep the largest tree whose effective alpha is at most that value; cost_complexity_pruning_path returns the whole sequence so you can choose alpha by cross-validation.

Feature importance, and its trap

A feature's impurity-based importance is the total impurity reduction over all the nodes that split on it, each weighted by its share of the training rows, then normalized to sum to 1 across features:

imp(f) ∝ Σ_{t splits on f} [ n_t I(t) − n_L I(L) − n_R I(R) ] / n

It is computed on the training data only and it rewards features that offer many candidate thresholds: a continuous column with a unique value per row can always carve out a pure-looking sliver by chance. Permutation importance on held-out data (sklearn.inspection.permutation_importance) measures what the fitted model actually relies on and is the usual alternative. Correlated features also split the credit between them, so a small importance does not mean a feature is uninformative.

The same tree as the lines in the scatter above. A leaf's class counts are its prediction: predict_proba returns their fractions.

Worked example

Implementation

from sklearn.tree import (
    DecisionTreeClassifier, DecisionTreeRegressor, export_text,
)
from sklearn.inspection import permutation_importance
from sklearn.model_selection import cross_val_score

clf = DecisionTreeClassifier(max_depth=3, min_samples_leaf=5, random_state=0)
clf.fit(X_train, y_train)
clf.predict_proba(X_test)                  # (n, n_classes): leaf class fractions
print(export_text(clf, feature_names=names))

# choose the pruning strength by cross-validation
path = DecisionTreeClassifier(random_state=0).cost_complexity_pruning_path(X_train, y_train)
scores = {a: cross_val_score(DecisionTreeClassifier(ccp_alpha=a, random_state=0),
                             X_train, y_train, cv=5).mean()
          for a in path.ccp_alphas}
best_alpha = max(scores, key=scores.get)

clf.feature_importances_                    # impurity-based, training data only
permutation_importance(clf, X_test, y_test, n_repeats=10, random_state=0)

reg = DecisionTreeRegressor(max_depth=4, min_samples_leaf=3).fit(X_train, y_reg)

fit grows the tree, _prune_tree applies ccp_alpha afterwards, and the fitted structure lives in the Cython Tree object as parallel arrays (feature, threshold, children, impurity, counts per node). Rows are never normalized or scaled: a tree only compares a feature with a threshold, so monotonic rescaling changes nothing. Recent scikit-learn versions can also route missing values (NaN) at each split, with the default splitter.

Tradeoffs

• Why use one. No feature scaling, mixed numeric and encoded categorical inputs, interactions found automatically, and a model a person can read, audit and explain. Fast to train and to predict.
• High variance. A small change in the data can change the root split and everything below it. Single trees are rarely the most accurate model; they are the building block of random forests and gradient boosting, which average or sum many of them.
• Overfitting by default. The default tree memorizes its training set. Always constrain it (max_depth, min_samples_leaf) or prune it (ccp_alpha), and choose the setting on validation data, not training accuracy.
• Axis-parallel boundaries. A diagonal or smooth boundary costs many splits. Rotating the features, or a different model family, can do much better.
• No extrapolation. Predictions are piecewise constant, so outside the training range a tree repeats its edge value; a linear trend is approximated by steps.
• Greedy search. Each split is chosen alone. Data like XOR, where neither feature helps by itself, can mislead the first split even though two splits together would solve it.
• Imbalanced classes. Majority-dominated leaves predict the majority; use class_weight, a sensible decision threshold on predict_proba, and a metric that is not accuracy (see classification metrics).
• Importances. Impurity-based importance favours high-cardinality columns and is measured on training data; confirm with permutation importance on held-out rows.
• Alternatives compared. Against logistic regression: trees capture interactions without engineering but lose smooth, extrapolating, well-calibrated scores. Against forests and boosting: a single tree is cheaper and readable, an ensemble is almost always more accurate.

Check yourself

Connections

References

• Breiman, Friedman, Olshen and Stone. Classification and Regression Trees. Wadsworth, 1984.
• Quinlan. Induction of Decision Trees. Machine Learning 1(1), 1986. doi:10.1007/BF00116251.
• Hastie, Tibshirani and Friedman. The Elements of Statistical Learning, chapter 9.2: tree-based methods, including cost-complexity pruning.
• Strobl, Boulesteix, Zeileis and Hothorn. Bias in random forest variable importance measures. BMC Bioinformatics, 2007. doi:10.1186/1471-2105-8-25.
• scikit-learn 1.9.1: DecisionTreeClassifier, Gini, _cost_complexity_prune.