Tree Pruning, Instability, and Missing Data

Two settings can produce trees of the same size and still cut the data in different places. The four dials below are not abstractions. The two most-used implementations ship them set against each other.

rpart 4.1.27 sets minsplit = 20, minbucket = round(minsplit/3), cp = 0.01 and maxdepth = 30, plus xval = 10, maxsurrogate = 5 and usesurrogate = 2. scikit-learn's DecisionTreeClassifier sets min_samples_split = 2, min_samples_leaf = 1, max_depth = None and ccp_alpha = 0.0.

Read them dial by dial. A minimum split size of 20 against a minimum split size of 2. A leaf floor of round(20/3) against a leaf floor of 1. A depth cap of 30 against no cap. A cost-complexity penalty of 0.01 against a penalty of exactly zero.

Nothing in either default is wrong. But a team that never touched a hyperparameter has already chosen a bias–variance position. In one of the two libraries that position is "grow until every leaf is pure and prune nothing".

A threshold selected at the root changes which rows reach every later node. Two candidate splits can have similar gain. A small resample can then replace the root and reorganize the entire tree.

Predictions may stay much the same while the visible rule set changes completely. Split stability and predictive stability are two different reports.

Greedy splitting is not a stylistic preference. It is forced, and the result that forces it is fifty years old: in 1976 Laurent Hyafil and Ronald L. Rivest proved that constructing an optimal binary decision tree is NP-complete. Lin and colleagues restated the consequence in 2020: “Full decision tree optimization is NP-hard, with no polynomial-time approximation (Laurent & Rivest, 1976), leading to challenges in proving optimality or bounding the optimality gap in a reasonable amount of time, even for small datasets.” (Their bibliography renders that citation as “Laurent, H. and Rivest, R. L.”, taking Laurent Hyafil's given name for a surname. Hyafil and Rivest is the correct form.)

Two things follow. Searching for the best whole tree, rather than the best next split, is not a computation anyone runs on real data. Every tree in this lesson is the output of a chain of locally optimal choices.

And the gap that chain leaves is not merely present, it is unmeasured. Of the heuristic splitting-and-pruning methods that dominate practice, the same authors write that greedy induction “tends to produce suboptimal trees with no way of knowing how suboptimal the solution is”. The first decision in the chain constrains all the others. A root that moves under resampling takes the diagram with it, and no version of the algorithm would have held it still.

Cost-complexity pruning is a published objective, not a preference for smaller pictures. Both mainstream implementations write down the same one. scikit-learn defines it as R_alpha(T) = R(T) + alpha*|T~|, where |T~| is the number of terminal nodes in T. The rpart vignette by Terry Therneau and Elizabeth Atkinson states the identical penalty in its own notation, R_alpha(T) = R(T) + alpha*|T|, with |T| the number of terminal nodes.

Both hand the credit to the same book. The scikit-learn user guide puts it in one line: “Minimal cost-complexity pruning is an algorithm used to prune a tree to avoid over-fitting, described in Chapter 3 of [BRE].” [BRE] is Classification and Regression Trees, the 1984 book by Breiman and colleagues.

Three properties from that book are what make the process below a path and not a sequence of guesses.

If R_alpha(T1) = R_alpha(T2) for subtrees of T, then one of T1 and T2 is a subtree of the other. The minimizers never sit sideways to each other.

If alpha > beta, then either T_alpha = T_beta or T_alpha is a strict subtree of T_beta. Raising the penalty can only shrink the chosen tree. It never regrows it somewhere else.

And all possible values of alpha group into at most |T| intervals — I1 = [0, alpha_1], I2 = (alpha_1, alpha_2], ..., Im = (alpha_{m-1}, infinity] — each sharing one minimizing subtree. A finite, nested sequence of candidates therefore exhausts a continuous parameter. That is why the validation step below has a short list to choose from.

One exported diagram is not enough evidence for a rule-based narrative. The report described here is not this lesson's invention either. Philipp and colleagues set out the framework in the Journal of Computational and Graphical Statistics in 2018, and it ships as the R package stablelearner, version 0.1-9. The same group had published the toolkit it grew from in 2016.

Their central finding is the one that stops the report being a formality: “In particular, we demonstrate that unstable algorithms (such as recursive partitioning) can produce stable results when the functional form of the relationship between the predictors and the response matches the algorithm.” Instability belongs jointly to the algorithm and the data-generating process. So it has to be measured on your data. It cannot be assumed from the method.

The scale such a report can uncover has been measured twice.

Marx and colleagues counted how many individuals receive conflicting predictions from models that are all within 1% of the best error rate: “For the 8 datasets we consider, we find that between 4% and 53% of individuals are assigned conflicting predictions in the 1%-level set.” On compas_arrest they report an ambiguity of 44% and a discrepancy of 17%. A model only 1% less accurate flips 17% of the predictions. Their models are linear classifiers.

Xin and colleagues did the tree-shaped counterpart in 2022. Trees of depth at most 4 over 10 binary features already span more than 9.338 x 10^20 possible models. On COMPAS, with regularization 0.005 and a threshold within 15% of optimal, the set of near-optimal trees reaches roughly 10^12 members. The single tree in your slide deck is one member of a set that size. The five columns below are how you find out whether the other members would have told the same story.

A missing feature can mean not measured, not applicable, delayed, failed, suppressed, or impossible. The libraries you would use route that absence by three different documented mechanisms. Worth knowing, before you decide the mechanism does not matter.

R rpart uses surrogate splits. An observation missing the split variable is sent by the first surrogate, then by the second if the first is also missing, and falls back to the majority direction when all of them are missing. A candidate surrogate has to send at least 2 observations each way before it is allowed to stand in.

XGBoost looks for no stand-in variable at all. It learns a default direction at each node, and its official documentation states it plainly: “XGBoost supports missing values by default. In tree algorithms, branch directions for missing values are learned during training.” Tianqi Chen and Carlos Guestrin named the mechanism sparsity-aware split finding in 2016, and gave the reason it is a default rather than an option. By visiting only the non-missing entries, “We find that the sparsity aware algorithm runs 50 times faster than the naive version.” That was measured on Allstate-10K.

scikit-learn's histogram gradient boosters learn the same left/right decision from the potential gain. Its plain DecisionTreeClassifier and DecisionTreeRegressor could not route a missing value at all until version 1.3.0, released 30 June 2023.

The routing strategy should be evaluated under realistic missingness patterns, including changes in measurement policy.

The comparison has been run at scale on real records. Perez-Lebel and colleagues benchmarked missing-value strategies with gradient-boosted trees, in GigaScience in April 2022. Their corpus was “4 electronic health record datasets, 1 population brain imaging database, 1 health survey, and 2 intensive care surveys”. Two of their conclusions bear directly on the routing decision. “Learning trees that model missing values—with missing incorporated attribute—leads to robust, fast, and well-performing predictive modeling”. And “native support for missing values in supervised machine learning predicts better than state-of-the-art imputation with much less computational cost”.

Where imputation is used anyway, they add the line teams cut first. “It is important to add indicator columns expressing which values have been imputed”. They read that result as evidence “that the data are missing not at random”.

Treat the structure as a tuned hypothesis. Start by writing down the defaults you inherited. In rpart, cp = 0.01 with xval = 10 already does part of steps 2 and 3 for you. In scikit-learn, ccp_alpha = 0.0 does none of it.

A high-variance learner produces meaningfully different predictions across bootstrap samples. Averaging many such trees can cancel part of that variation while preserving nonlinear partitions.

The next lessons use this property. An ensemble still does not make individual rules stable, and it does not make them causal.