Decision trees

The learning problem#

A decision tree partitions the feature space into axis-aligned rectangles R_1, ..., R_M and fits a constant in each:

f(x) = SUM_m  c_m * 1[ x in R_m ]

• R_m — the region reached by one leaf, an intersection of half-spaces of the form x_j <= t
• c_m — the constant fitted in region m: the mean of y for regression, the majority or class frequencies for classification
• 1[.] — the indicator function

Finding the partition that minimises training error subject to a size limit is NP-complete (Hyafil & Rivest, 1976). Practical algorithms are therefore greedy: choose the locally best split, recurse, never reconsider.

Split criteria#

At a node with class proportions p_1, ..., p_K:

Gini        H(node) = 1 - SUM_k p_k^2       = SUM_k p_k (1 - p_k)
Entropy     H(node) = - SUM_k p_k log2 p_k
Misclass.   H(node) = 1 - max_k p_k

• p_k — proportion of node samples belonging to class k
• K — number of classes

A candidate split into left and right children is scored by the weighted impurity decrease:

Delta = H(parent) - ( n_L / n ) * H(L) - ( n_R / n ) * H(R)

• n, n_L, n_R — sample counts at the parent and the two children

Gini has an alternative reading: it is the expected error rate if you labelled each item by drawing a label from the node's own class distribution. It is also the training error of the node under squared loss on the one-hot encoding, which is why regression and classification trees share one implementation.

Misclassification error is not used for growing. It is insufficiently sensitive — it can score two candidate splits equally when one produces measurably purer children — though it is appropriate for pruning. Gini and entropy rarely disagree in practice; Raileanu & Stoffel (2004) find they differ on roughly 2% of splits.

A worked split, checkable by hand#

Using the 16-row dataset from the Developer section: 10 scams, 6 safe.

Root Gini      = 1 - (10/16)^2 - (6/16)^2  = 1 - 0.390625 - 0.140625 = 0.46875

Split on asks_for_otp:
  right (otp=1): 8 rows, all scam   -> Gini = 0
  left  (otp=0): 8 rows, 2 scam     -> Gini = 1 - (2/8)^2 - (6/8)^2 = 0.375

Weighted child impurity = (8/16)(0) + (8/16)(0.375) = 0.1875
Delta                   = 0.46875 - 0.1875          = 0.28125

scikit-learn's tree_.impurity array returns exactly 0.468750, 0.375000, 0.500000 for the root, the left child and its right grandchild. The arithmetic is fully reproducible.

Impurity-based importance (MDI) is the sum of (n_node / n_total) * Delta over nodes splitting on that feature, normalised to sum to one:

asks_for_otp   : (16/16)(0.28125) = 0.28125   ->  0.28125 / 0.46875 = 0.600
has_link       : ( 8/16)(0.125)   = 0.0625    ->  0.0625  / 0.46875 = 0.133
unknown_sender : ( 4/16)(0.500)   = 0.125     ->  0.125   / 0.46875 = 0.267
says_urgent    : never used                   ->  0.000

These match feature_importances_ to the printed precision.

Cost-complexity pruning#

Breiman et al. (1984) define, for a subtree T:

R_alpha(T) = R(T) + alpha * |leaves(T)|

• R(T) — resubstitution error of the tree
• |leaves(T)| — number of terminal nodes
• alpha >= 0 — complexity cost charged per leaf

The key structural result: as alpha increases from 0, the minimising subtrees form a finite nested sequence T_0 ⊃ T_1 ⊃ ... ⊃ {root}. So the entire one-dimensional model-selection problem is solved by a finite list of candidates, obtainable in one pass. cost_complexity_pruning_path returns exactly the alpha values at which the sequence changes.

This is why pruning dominates depth-capping. max_depth imposes a uniform constraint; alpha selects branches by their individual contribution.

Complexity#

Build (balanced, presorted)   O(d n log^2 n),  or O(d n log n) with sorted feature caches
Build (depth h, worst case)   O(d n h)
Prediction                    O(h),  typically O(log n)
Memory                        O(number of nodes)

Prediction is exceptionally cheap — a handful of comparisons, no arithmetic on the features. This, not accuracy, is why trees and their ensembles dominate latency-bound production ranking systems.

Known deficiencies#

Axis-aligned splits. A boundary at 45 degrees requires a staircase of many splits, and the sample cost grows accordingly. Oblique trees split on w^T x <= t — OC1 (Murthy et al., 1994) uses randomised hill-climbing, since the optimal oblique split is itself intractable. Trees are also not rotation invariant, which Grinsztajn et al. (2022) argue is a feature on tabular data, where individual columns carry meaning.

High variance. Trees are unstable in the sense of Breiman (1996): small perturbations of the training set produce large changes in the predictor. Since the greedy choice at the root determines everything below it, an error near the root propagates. This is precisely the property that makes bagging effective — see random forest.

MDI bias. Strobl et al. (2007) demonstrate that impurity importance is biased towards continuous and high-cardinality features, because such features offer more candidate split points and therefore more chances to fit noise. The bias exists even when the feature is independent of the target. Prefer permutation importance on held-out data, or SHAP values (Lundberg et al., 2020), whose TreeSHAP algorithm computes exact Shapley values for tree ensembles in O(TLD^2).

No extrapolation. Predictions are constant outside the convex hull of the training data, as demonstrated above. For targets with trend, model the trend explicitly or use a hybrid such as a linear model on the residuals.

Missing data#

CART's original answer is surrogate splits: at each node, store alternative variables ranked by how well they mimic the primary split, and use the best available one when the primary variable is missing. This is implemented in R's rpart, not in scikit-learn.

scikit-learn 1.3 introduced native NaN support for the best splitter. Missing values are sent to whichever child minimises impurity, evaluated during training. This is the same strategy LightGBM and XGBoost use, and it treats missingness as informative rather than as something to be repaired.

Optimal trees#

Advances in mixed-integer optimisation have made globally optimal small trees tractable. Bertsimas & Dunn (2017) formulate optimal classification trees as an MIO problem, reporting absolute out-of-sample gains of 1–5% over CART at equal depth. Hu et al. (2019) and the GOSDT line of work use branch-and-bound with analytical bounds, reaching optimality in seconds for depth-limited trees on modest datasets.

Rudin (2019) argues from this that for high-stakes decisions the choice is not between an accurate black box and an inaccurate interpretable model — an optimal sparse tree is frequently as accurate, and post-hoc explanations of black boxes are unreliable by construction.

Key references#

• Hyafil, L. & Rivest, R. (1976). Constructing Optimal Binary Decision Trees is NP-Complete. Information Processing Letters 5(1).
• Breiman, L., Friedman, J., Olshen, R. & Stone, C. (1984). Classification and Regression Trees. Wadsworth. The CART book.
• Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning 1(1). ID3.
• Quinlan, J. R. (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
• Murthy, S., Kasif, S. & Salzberg, S. (1994). A System for Induction of Oblique Decision Trees. JAIR 2.
• Strobl, C. et al. (2007). Bias in Random Forest Variable Importance Measures. BMC Bioinformatics 8(25).
• Bertsimas, D. & Dunn, J. (2017). Optimal Classification Trees. Machine Learning 106(7).
• Rudin, C. (2019). Stop Explaining Black Box Machine Learning Models for High Stakes Decisions. Nature Machine Intelligence 1.
• Lundberg, S. et al. (2020). From Local Explanations to Global Understanding with Explainable AI for Trees. Nature Machine Intelligence 2.

Current state#

Single trees are no longer competitive on accuracy and are not meant to be. Their two live roles are as the base learner inside ensembles, and as standalone models where an auditable decision rule is a hard requirement — credit adjudication, clinical protocols, and regulated underwriting.

Everything that made trees weak alone — instability, greedy myopia, high variance — is what the ensemble methods exploit. Bagging attacks the variance; boosting attacks the bias by fitting successive trees to residuals. Both start from the same greedy CART splitter described here.

What to learn next#

• Random forest — turning the twitchiness of one tree into the strength of many.
• Overfitting and underfitting — the depth sweep on this page, explained in full.
• Classification — where the staircase boundary came from.