Chapter 5: Decision Trees

A tree is built from three kinds of nodes. The root is the first test, applied to every sample. Internal nodes apply further tests to the samples routed to them, and leaves hold the final predictions. Every root-to-leaf path is a conjunction of conditions, so the whole tree is a set of mutually exclusive rules. Depth is the number of edges on the longest path; a binary tree of depth $d$ has at most $2^d$ leaves and $2^{d+1}-1$ nodes. Depth controls both capacity and readability: depth 3 gives at most 8 rules a person can follow, while depth 20 allows over a million leaves.

Trees are grown top-down and greedily. Starting with all training samples at the root, the algorithm chooses the single feature and threshold whose split most improves purity, sends samples to the left or right child, and repeats the same procedure independently inside each child. Growth stops when a node is pure, too small, or a depth limit is reached. Each split cuts a region with a line perpendicular to one feature axis, so the final partition is a set of axis-aligned boxes. Greedy means each split is chosen without looking ahead, so the resulting tree is good but not guaranteed optimal; finding the optimal tree is NP-hard.

At each node the tree must choose one feature and one threshold. For a numeric feature with $n$ distinct sorted values, only $n-1$ thresholds can produce different partitions, so candidates are the midpoints between consecutive values. For each candidate the algorithm computes the impurity of the two children, weighted by their sizes, and keeps the split with the largest reduction from the parent. Sorting once and scanning with running counts makes each feature cost about $O(n \log n)$. The search is exhaustive over features and thresholds but myopic over depth, which is why a split with little immediate gain can be overlooked.

In a classification tree each leaf stores the class counts of the training samples that reached it. The predicted class is the majority class, which minimizes misclassification on those samples, and the predicted probabilities are the class proportions, which are maximum likelihood estimates for that region. Probabilities from small leaves are unreliable: a leaf with 3 samples can only output multiples of one third, and a pure leaf outputs probability 1 even when the true rate is lower. Deep trees therefore tend to give overconfident, poorly calibrated probabilities, which is one reason min_samples_leaf and ensembles help.

A regression tree uses the same partitioning, but each leaf predicts a number: the mean of the training targets in that region. The mean is the constant that minimizes squared error within the leaf, so it pairs naturally with the variance-reduction split criterion covered next. The resulting model is a step function: constant inside each region and jumping at the boundaries. A leaf's prediction has variance proportional to the noise variance divided by the number of samples it holds, so deep trees with tiny leaves give noisy, overfitted predictions. A later topic in this chapter treats regression trees in depth.

Trees need little preprocessing. A split compares a feature with a threshold, so any monotonic transformation of a feature, such as scaling or taking logs, yields the same partitions; no standardization is required. Trees model interactions automatically, because a split on one feature followed by a split on another creates a rule involving both. They handle mixed feature types, ignore irrelevant features that are never chosen, and predict in time proportional to depth. Above all, a shallow tree is readable. Some caveats apply: scikit-learn's implementation needs categorical features encoded as numbers, and its support for missing values depends on the version.

The main weakness of a single tree is high variance. Because splits are chosen greedily, a small change in the training data can change the root split, and every split below it changes too, giving a very different tree with similar accuracy. Trees also draw only axis-aligned boundaries, so a diagonal boundary such as $x_1 + x_2 = c$ must be approximated by a staircase of many splits. Grown fully, they memorize the training set. Finally, regression trees cannot extrapolate beyond the target range seen in training. Pruning reduces overfitting, and ensembles such as random forests, in the next chapter, average away much of the variance.

Gini impurity is the probability that two samples drawn at random from a node, with replacement, have different classes. Here $p_k$ is the fraction of samples in class $k$ and $K$ is the number of classes, so $\sum p_k^2$ is the chance both draws match. Gini is 0 for a pure node and reaches its maximum, $1 - 1/K$, when all classes are equally frequent: 0.5 for two classes, 0.667 for three. For binary problems it simplifies to $2p(1-p)$. Because Gini is concave, the weighted impurity of the children can never exceed the parent's, so every split has a non-negative decrease. It needs no logarithm, which makes it cheap.

Entropy, from information theory, measures the average number of bits needed to encode the class of a sample drawn from the node. With class fractions $p_k$, each class contributes $-p_k \log_2 p_k$, using the convention that a zero fraction contributes 0. Entropy is 0 for a pure node and $\log_2 K$ when all $K$ classes are equally likely: 1 bit for two classes, about 1.585 bits for three. Like Gini it is concave, so splits never increase weighted entropy. Its logarithm penalizes small minority fractions more sharply than Gini does. ID3 and C4.5 use entropy; scikit-learn offers it as criterion='entropy'.

Information gain is the reduction in entropy produced by a split. Here $H(\text{parent})$ is the parent's entropy, $n$ its sample count, and $n_c$ the number of samples sent to child $c$; each child's entropy is weighted by $n_c / n$, so a pure but tiny child earns little credit. The tree evaluates the gain of every candidate split and keeps the largest. Information gain equals the mutual information between the class label and the split outcome, so it measures how much the question tells us about the answer. Its weakness is a bias toward features with many distinct values, which can split data into many small, accidentally pure children.

C4.5 corrects information gain's bias by dividing it by the split information, the entropy of the partition sizes themselves, $-\sum_c (n_c/n) \log_2(n_c/n)$. A split into two equal halves has split information 1 bit; a split into 100 equal groups has $\log_2 100$, about 6.64 bits. A feature such as a customer ID can create many tiny, pure children and so a large raw gain, but its huge split information shrinks the ratio. One caveat: a very lopsided split has split information near zero, which can inflate the ratio, so C4.5 only considers splits whose gain is at least average.

Gini and entropy are both concave, zero for pure nodes, and maximized at the uniform distribution, so they rank splits almost identically; studies find they disagree on only a few percent of splits. Their raw values differ in scale, with binary maxima of 0.5 and 1.0, but only the ranking of candidate splits matters, never the absolute number. Gini avoids a logarithm and is slightly faster, which is why it is scikit-learn's default. Entropy weights rare classes a little more heavily, sometimes producing slightly more balanced trees. In practice, the choice of criterion matters far less than depth and pruning.

For regression, impurity becomes the mean squared error around the node mean, $\frac{1}{n}\sum(y_i - \bar{y})^2$, where $\bar{y}$ is the node mean and $n$ its sample count. That is just the variance of the targets in the node. A split is scored by the parent's MSE minus the size-weighted MSE of the children, so the best split separates low targets from high ones. The reduction equals $n_L n_R (\bar{y}_L - \bar{y}_R)^2 / n^2$, which rewards balanced children with very different means. Running sums of $y$ and $y^2$ make every threshold cheap to score. Squaring makes the criterion sensitive to outliers.

Mean absolute error as an impurity uses absolute deviations from the median, $\frac{1}{n}\sum |y_i - \text{median}|$. Because the median minimizes absolute error, leaves under this criterion predict the median rather than the mean. Absolute deviations grow linearly, not quadratically, so one extreme target cannot dominate split choices, and the median ignores how far an outlier sits. The cost is speed: medians cannot be updated with running sums, so evaluating thresholds is much slower than with MSE. In scikit-learn, criterion='absolute_error' selects it; it pays off when targets have heavy tails.

Pre-pruning stops growing a branch as soon as a stopping rule fires. The main rules in scikit-learn are max_depth, min_samples_split, min_samples_leaf, max_leaf_nodes, and min_impurity_decrease. Pre-pruning is cheap, because unneeded subtrees are never built, and easy to tune. Its weakness is the horizon effect: a split with little immediate gain may enable strong splits below it. The classic case is XOR, where the label depends on two features together; neither alone reduces impurity, so a minimum-gain rule stops before the useful pair of splits is found.

Post-pruning grows the tree fully, then removes structure bottom-up. In reduced-error pruning each internal node is tentatively replaced by a leaf, and the replacement is kept if accuracy on a separate validation set does not drop. Pruning repeats until no replacement helps. Because the full tree already contains every split, post-pruning avoids the horizon effect: a weak split is kept if the subtree beneath it pays off. The costs are growing a large tree first and, for reduced-error pruning, holding out validation data. Cost-complexity pruning, next, avoids the holdout by using cross-validation to set its single parameter.

Cost-complexity pruning, from CART, scores a tree $T$ by $R_\alpha(T) = R(T) + \alpha |T|$, where $R(T)$ is its training error (or total impurity), $|T|$ its number of leaves, and $\alpha \geq 0$ the price per leaf. At $\alpha = 0$ the full tree wins; as $\alpha$ grows, subtrees whose error reduction per leaf is below $\alpha$ are collapsed. Each internal node has a critical value, the error increase from collapsing it divided by the leaves removed, and pruning the weakest link first yields a nested sequence of subtrees. In scikit-learn this is the ccp_alpha parameter.

Cost-complexity pruning turns tree selection into choosing one number. Scikit-learn's cost_complexity_pruning_path returns the critical alphas at which each successive subtree is pruned, so only those values need testing. Each candidate alpha is scored with K-fold cross-validation, and the one with the best mean score wins. CART also proposed the one-standard-error rule: choose the largest alpha whose score is within one standard error of the best, giving a simpler tree with statistically similar accuracy. The validation curve is U-shaped: alpha near zero overfits, very large alpha underfits, and the sweet spot is in between.

max_depth caps the length of every root-to-leaf path, so a tree of depth $d$ has at most $2^d$ leaves. It is the most commonly tuned pre-pruning parameter because it controls capacity directly and is easy to explain: depth 3 means at most three questions per prediction. Shallow trees, depth 2 to 5, are readable and stable but can underfit; deep trees capture fine interactions but overfit. Because the effect depends on the data, tune it with cross-validation over a range such as 2 to 15. A depth limit cuts all branches equally, even where one branch would benefit from going deeper.

These parameters require statistical support for every decision. min_samples_split is the smallest node that may be split; min_samples_leaf is the smallest number of samples any child may hold, so a split leaving fewer in one child is rejected. Leaf estimates average fewer points as leaves shrink, so their variance rises: a leaf of 2 samples gives an unreliable mean or class proportion. Raising min_samples_leaf to 5 to 50 smooths regression outputs and calibrates probabilities better. The parameters also accept fractions of the dataset, such as 0.01 for 1 percent, which scale with dataset size.

min_impurity_decrease rejects any split whose weighted impurity reduction falls below a threshold. In scikit-learn the reduction is weighted by the node's share of all training samples, $N_t / N$, so a split deep in the tree, which touches few samples, must be correspondingly purer to qualify. The rule removes splits that barely improve purity and are likely to reflect noise. The right threshold depends on the criterion, because Gini and entropy have different scales, and on the data, so tune it with cross-validation. Like other pre-pruning rules it can stop before splits that only pay off deeper down.

To predict for a new input, the tree routes it from the root to a leaf by applying each split test, then returns that leaf's stored value. Here $R_m$ is the region of feature space covered by leaf $m$, $|R_m|$ the number of training samples in it, and $\hat{y}$ the average of their targets. The mean is the constant that minimizes squared error over the leaf's samples. Every input in a region gets the same prediction, so the tree cannot rank two houses in the same leaf. A leaf's mean is estimated from $|R_m|$ samples, so its variance falls as leaves grow, the reason min_samples_leaf matters.

For each candidate split, the tree computes the sum of squared deviations of the targets from their own child means, $\bar{y}_L$ and $\bar{y}_R$, and picks the split with the smallest total. Equivalently, it maximizes the reduction in variance from the parent. The reduction depends on the gap between the child means and on the balance of the split, so the best split separates the targets into two groups with distant means. Because the criterion is squared, outliers pull splits toward isolating them. With targets sorted along a feature, running sums score every threshold in one pass.

A regression tree's output is a step function: constant inside each leaf region and jumping at the split thresholds. A smooth curve is approximated by a staircase, and more leaves give finer steps and a closer fit. In one dimension with $M$ leaves, a function with bounded slope can be approximated to within about the slope times the step width. In $p$ dimensions the steps must shrink along every axis, so the needed leaves grow exponentially, a form of the curse of dimensionality. Steps also mean that small input changes produce no output change until a boundary is crossed, then a jump.

Replacing squared error with absolute error changes both the leaf value and the split choice. The constant minimizing absolute error is the median, so leaves predict medians, and splits minimize the sum of absolute deviations from each child's median. The median is robust: up to half of a leaf's values can be arbitrarily extreme without moving it far. This suits heavy-tailed targets such as prices or incomes. The costs are slower training, since medians lack cheap running updates, and predictions that track the typical value rather than the average, which matters if the goal is total revenue. In scikit-learn, use criterion='absolute_error'.

A tree can only output values stored in its leaves, and every leaf value is an average of training targets. Predictions are therefore bounded by the smallest and largest training targets, whatever the input. For an input beyond the training range, the tree applies its split tests as usual, lands in the outermost leaf, and returns that leaf's mean: the prediction flattens instead of following the trend. This matters for data with growth or drift, such as prices rising over time or sizes beyond those observed. Remedies include linear models, linear-tree hybrids, or modeling the trend first and fitting the tree to the residuals.

Linear regression fits one global equation with $p + 1$ parameters, so it is stable, extrapolates along its trend, and gives coefficients with a clear per-unit meaning, but misses thresholds and interactions unless engineered. A regression tree fits a local constant per region, so it captures thresholds, interactions, and nonlinear shapes automatically, needs no scaling, and grows its capacity with the data. It is unstable, predicts in steps, and cannot extrapolate. A smooth, roughly linear relationship favors linear regression; an irregular one with interactions favors trees. When unsure, cross-validate both.

Every split on feature $f$ reduces impurity by some $\Delta$ for the $n$ samples at that node. Impurity-based importance, also called mean decrease in impurity, sums $n \cdot \Delta$ over all splits on $f$ and normalizes so all features sum to 1. Splits near the root touch many samples and dominate; a feature never used scores 0. It is free to compute during training and available as feature_importances_. Its flaw is that it is measured on training data, so it rewards features that helped the tree fit noise as well as signal. The next concepts show the consequences.

An importance score says how much the model used a feature, not how the feature affects the outcome. It has no sign: a large importance for age is consistent with older customers churning more, less, or with a U-shaped effect. It describes the model, not the world, so a feature can be truly causal yet unimportant because a correlated feature carried its signal. Scores are relative within one model and sum to 1, so comparing them across models or datasets is not meaningful. For direction, inspect the splits, plot partial dependence, or use SHAP values.

A feature with many distinct values, such as a customer ID or timestamp, offers many candidate thresholds, while a binary feature offers one. More candidates mean more chances for a threshold to separate the training labels by accident, so deep trees will happily split on IDs to purify small nodes. Those splits fit noise, yet impurity-based importance credits them in full, because it is computed on training data. The result is that meaningless high-cardinality features appear important. Fixes: drop identifiers before training, limit depth, or measure importance with permutation on held-out data, which exposes such features as useless.

When two features carry the same information, such as height in centimeters and in inches, any split on one could be made just as well on the other. The tree picks whichever is marginally better, or the first one examined when they tie, and the other receives little or no credit. Importance is then concentrated on one feature or split between them arbitrarily, so a zero score does not mean a feature is uninformative. Permutation importance has a related weakness: shuffling one copy barely hurts, since the other remains. Group correlated features, or drop and refit to measure their joint value.

Permutation importance measures how much a fitted model's score drops when one feature's values are randomly shuffled, breaking its link with the target while keeping its distribution. A large drop means the model relied on the feature. Computed on a held-out set, it reveals reliance that generalizes, so noise features such as IDs score near zero. It works for any model, needs no retraining, and should be repeated over several shuffles to show variance. Costs and caveats: one prediction pass per feature per repeat, and shuffling creates unrealistic combinations when features are correlated. Scikit-learn provides permutation_importance.

SHAP values explain a single prediction by assigning each feature a signed contribution, based on Shapley values from cooperative game theory. A feature's value $\phi_j$ is its average marginal effect on the prediction across all orders of adding features. The contributions add up exactly: base value plus the sum of all $\phi_j$ equals the prediction, where the base value is the average prediction over the data. Signs show direction, so SHAP answers what importance cannot. For trees, the TreeSHAP algorithm computes them exactly in polynomial time. Averaging absolute SHAP values over many samples gives a global importance ranking.

Scikit-learn offers three main ways to view a tree. plot_tree draws it with matplotlib, export_graphviz writes a Graphviz file for higher-quality layouts, and export_text prints indented if-then rules that fit in a log or document. Each node shows its split test, impurity, sample count, and class counts or mean value; filled=True colors nodes by majority class and purity. Readability limits what is useful: a diagram of more than about 15 to 30 nodes overwhelms a reader. Use max_depth in plot_tree to show only the top levels, or prune the model itself if the whole tree must be explained.

Every prediction a tree makes follows one root-to-leaf path, and the conditions along it are a complete explanation of that prediction: no other features or weights are involved. In scikit-learn, decision_path returns the nodes visited by each sample and apply returns the leaf it reached, so explanations can be generated automatically. Because each condition names a feature, a threshold, and a direction, the explanation is concrete and checkable. Two caveats: a path shows what the model did, not what would change the decision, and features tested near the root apply to everyone in that branch, not just this applicant.

Each root-to-leaf path converts directly into an if-then rule: the conjunction of the conditions on the path, followed by the leaf's prediction. A tree with $M$ leaves yields $M$ rules that are mutually exclusive and exhaustive, so every input matches exactly one rule. Rules can be reviewed by domain experts, checked against policy, or translated into SQL, spreadsheet logic, or a business rules engine, with no ML library at prediction time. The rule list grows with leaves, so prune first. Thresholds are midpoints chosen from training data, so round them sensibly before presenting them as policy.

Each node in a scikit-learn diagram lists four things. The split test, such as age <= 35, sends samples where it is true to the left child. The impurity, gini or entropy, gives the node's purity. Samples counts the training rows reaching the node, and value lists their class counts, or the mean for regression. Leaves show the same statistics without a test, and their predicted class is the majority in value. Reading down a path, impurity should fall and samples shrink; a leaf with few samples or high impurity is a weak rule. With class_weight set, value may show weighted totals, not raw counts.

Interpretability questions come in two kinds. Global questions ask how the model behaves overall: which features matter most, what thresholds it uses, and how complex it is. Tools are feature importance, the top levels of the diagram, and partial dependence plots. Local questions ask why the model made one prediction: tools are the decision path for trees, or SHAP values for any model. The two can disagree: a feature with low global importance can decide a particular case, and vice versa. Match the tool to the question; regulatory explanations of individual decisions require local explanations.

A single tree is the right model when transparency is a requirement, not a preference: credit decisions, medical triage, and other settings where each decision must be explained, audited, or legally justified. It also fits when the true structure is a handful of thresholds and interactions, when a fast baseline is needed, and when the model will be handed to non-engineers as rules. Elsewhere, single trees usually lose to ensembles in accuracy because of their high variance. Rudin argues that for high-stakes decisions an interpretable model is preferable to explaining a black box after the fact, especially when the accuracy gap is small.