Decision Trees: Recursive Partitioning

Each internal node asks a threshold or category question, sends the row down one branch, and continues until a leaf produces a prediction. The tree learns the questions and their order from data.

This creates a piecewise-constant model: every row in one leaf receives the same class distribution or numeric estimate. One leaf, one answer.

That is not a classroom abstraction. Children who arrive at an emergency department after head trauma are sorted by exactly this object. The partition was grown from 42,412 children enrolled at 25 North American emergency departments, and each region carries one prediction: whether the child is at very low risk of clinically-important brain injuries. The Pediatric Emergency Care Applied Research Network published it. This lesson uses that tree, and the papers that later re-measured it, in place of hypothetical ones.

The same feature may appear at several nodes, because its useful threshold depends on the path already taken.

Size is not fixed by the vocabulary. Quinlan needed about 150 nodes to classify all 715 chess objects correctly. The PECARN rules examined later in this lesson reach their leaves in six conditions. Root, internal node, branch, leaf and path are the same five parts in both cases. How many of each there are is a modelling decision, not a property of the method.

Classification trees often choose splits that reduce impurity such as Gini or entropy. Regression trees reduce squared or absolute error. Either way the search is greedy: it takes the best split available now, without jointly optimizing the final tree. A locally attractive split can block a better later structure. Growth and pruning therefore work together.

Greed here is a decision, not an oversight. Hyafil and Rivest settled that in 1976, and their title is the result: “Constructing Optimal Binary Decision Trees is NP-Complete”. The exhaustive alternative is unavailable at any interesting size. That is still the reason production libraries give for how they grow trees. Listed under the disadvantages of decision trees, the scikit-learn documentation says: “The problem of learning an optimal decision tree is known to be NP-complete under several aspects of optimality and even for simple concepts. Consequently, practical decision-tree learning algorithms are based on heuristic algorithms such as the greedy algorithm where locally optimal decisions are made at each node.” Quinlan said as much about ID3 in 1986. It “has generally been found to construct simple decision trees, but the approach it uses cannot guarantee that better trees have not been overlooked”.

What the greedy step does to a tree has a mechanism. Hu and colleagues stated it in 2019: “CART and C4.5 grow decision trees from the top down without backtracking, which means that if a suboptimal split was introduced near the top of the tree, the algorithm could spend many extra splits trying to undo the mistake it made at the top, leading to less-accurate and less-interpretable trees.” The same paper then presented the first published optimal sparse binary-split trees for the COMPAS and FICO datasets. Note what is being claimed. Not that the greedy tree is wrong, but that it spends depth repairing an early choice. Depth is the thing that made the tree readable.

How much is overlooked has been measured. Bertsimas and Dunn built optimal classification trees in 2017, once mixed-integer solvers had caught up, and benchmarked them against CART “on a sample of 53 datasets from the UCI machine learning repository”. They report “average absolute improvements over CART of 1–2 and 3–5% for OCT and OCT-H, respectively, across all datasets depending on the depth of tree used”, and that “across all 53 datasets, OCT closes the gap between CART and Random Forests by about one-sixth, and OCT-H by about half”. The greedy step costs a point or two of accuracy for the univariate variant, three to five for the hyperplane one. That is a published number, not a suspicion.

Both partition space. Each then summarizes outcomes within its leaves.

The split objective is also where an asymmetric cost enters. PECARN did not ask its search to minimise total error. The rules were derived with a deliberate 500-to-1 relative misclassification cost, so the two kinds of mistake were never weighed the same. A class weight is not a post-hoc adjustment to the output. It changes which splits the search prefers while the tree is still being grown.

The tree in this section is not invented. Kuppermann and colleagues wrote down how they grew it, in the Methods of their 2009 Lancet paper: “We derived the rules with binary recursive partitioning (CART PRO 6.0; San Diego, CA, USA, Salford Systems).” Splits were scored on Gini. Structure was chosen by ten-fold cross-validation. The search ran under a 500-to-1 relative misclassification cost. Two rules came out — one for children aged 2 years and older, one for children under 2 years — each a short path of six conditions ending in a leaf.

Read the figures below for what they are. They say how children routed through this partition, and how often the leaf that received them was right. They do not say why a head injury occurs. No arrangement of the same numbers would.

Use constraints to learn structure without memorizing individual rows.

Each of these steps is a decision someone has already published a default for. PECARN fixed its structural limits by ten-fold cross-validation, and its split incentives by a 500-to-1 relative misclassification cost. The evaluation step is the one most often done wrongly. Ploton and colleagues put a number on the difference between slicing the held-out data at random and slicing it away from the training rows: R² = 0.53 became R² = 0.14 on the same model.

Some implementations require one-hot or ordinal encodings, while others search category partitions directly. The size of that difference is exact rather than rhetorical. For a nominal predictor with k categories the standard search evaluates all 2^(k−1)−1 two-way partitions. For binary classification and regression there is a shortcut, and it is not an approximation: order the categories by the outcome — by the proportion of 1s for a binary outcome, by the increasing outcome mean for regression — and treat them as ordinal. Exactly the same splits come out. Wright and König put the consequence in one line: “This reduces computational complexity because only k − 1 splits have to be considered for a nominal predictor with k categories.” The result is older than their 2019 paper, which credits Fisher 1958, Breiman et al. 1984 and Ripley 1996. LightGBM's official documentation implements it, and reports that it “often performs better than one-hot encoding”. One-hot encoding fragments a categorical decision across many nodes. Arbitrary ordinal codes impose an order the categories do not have.

Unknown categories at inference are not a documentation chore either. They are a named defect with a measured frequency. Au named it the absent levels problem in 2018 and defined it: “This problem occurs whenever there is an indeterminacy over how to handle an observation that has reached a categorical split which was determined when the observation in question's level was absent during training.” He showed that Breiman and Cutler's original random forests FORTRAN code and the randomForest R package systematically bias predictions in exactly that situation.

A separate group then measured how often it actually bites. On Campylobacter source-attribution data, 16% of individual tree predictions under PCO-encoding and 22% under CA and CA-unbiased encoding used at least one absent level. Average misclassification error ran from 23.2%±1.2% to 27.0%±1.2% across the three encodings. Roughly one tree vote in five was cast on an indeterminacy.

The alternative is to write the routing rule down where users can read it, as LightGBM does: “At predict() time, categories not seen during training will be treated as missing values.”

A regression tree predicts leaf summaries. It therefore does not extend a learned slope beyond the observed feature support. This can be safe in some bounded tasks and poor in forecasting trends. Unsupported feature combinations can still land in a leaf, because every path ends somewhere.

What that costs has been measured on forest-inventory data covering 11.8 million trees in central Africa. Ploton and colleagues trained a random forest there and scored it twice. Under conventional random cross-validation it reached R² = 0.53, with an RMSPE of 56.5 Mg ha⁻¹ (19%). Under spatial 44-fold cross-validation, which scores the model on blocks it was not trained on, the same model reached R² = 0.14, with an RMSPE of 77.5 Mg ha⁻¹ (26%). Their 2020 abstract in Nature Communications says it without hedging: “A standard nonspatial validation method suggests that the model predicts more than half of the forest biomass variation, while spatial validation methods accounting for SAC reveal quasi-null predictive power.”

This is not one group's unlucky dataset. Stock reached the same conclusion independently in 2025, on a marine remote sensing case study, finding that 10-fold cross-validation underestimated prediction errors by 5% to 54% depending on the model and metric. Add range and support checks around the tree. Then choose the validation split so that it asks the question deployment will ask.