Decision tree learning
Decision tree learning is a family of supervised learning methods that represents a predictive function as a sequence of conditional partitions. Internal nodes apply tests to predictor variables, branches encode the outcomes of those tests, and terminal nodes assign predictions. A tree used for a categorical response is called a classification tree, whereas a tree used for a numerical response is called a regression tree.
The method combines recursive partitioning with a piecewise-constant model of the response distribution. Its fitted structure is commonly interpreted as a set of nested decision rules, although this interpretation describes the model rather than establishing that its internal divisions correspond to causal mechanisms. Decision trees occupy an intermediate position between statistical partitioning methods and symbolic rule systems, since they estimate predictions from data while expressing the resulting function through discrete logical conditions.
Mathematical formulation
Let a training sample be
[ D={(x_i,y_i)}_{i=1}^{n}, ]
where (x_i\in\mathcal{X}) is a vector of predictors and (y_i) is the associated response. A decision tree partitions the predictor space into disjoint terminal regions (R_1,\ldots,R_M). Its prediction function has the form
[ \hat f(x)=\sum_{m=1}^{M} c_m,\mathbf{1}(x\in R_m), ]
where (c_m) is the prediction attached to region (R_m), and (\mathbf{1}) denotes the indicator function.
For regression under squared-error loss, the fitted value in a terminal region is the arithmetic mean of the training responses contained in that region:
[ c_m=\frac{1}{|R_m|}\sum_{x_i\in R_m}y_i. ]
For classification, a terminal node generally stores estimated class proportions,
[ \hat p_{mk}=\frac{1}{|R_m|} \sum_{x_i\in R_m}\mathbf{1}(y_i=k), ]
and predicts the class with the largest estimated proportion. Other decisions follow from the same proportions when the loss assigned to different classification errors is unequal.
The partition is usually produced recursively. At a node containing sample (D_t), a candidate split (s) creates child samples (D_{tL}) and (D_{tR}). The reduction in impurity is
[ \Delta I(s,t)
I(D_t)
\frac{|D_{tL}|}{|D_t|}I(D_{tL})
\frac{|D_{tR}|}{|D_t|}I(D_{tR}), ]
where (I) is a node-impurity function. Greedy tree induction selects a locally maximizing split rather than jointly optimizing the complete tree, because exact global optimization is computationally difficult for ordinary tree-search spaces.
Split criteria
In classification, the Gini impurity of a node with class proportions (p_1,\ldots,p_K) is
[ I_G=1-\sum_{k=1}^{K}p_k^2. ]
It equals the probability of disagreement between two class labels drawn independently from the node’s empirical class distribution. A pure node has zero Gini impurity, while a node with a more evenly distributed set of classes has a larger value.
Information gain measures the reduction in Shannon entropy. For class proportions (p_k), entropy is defined by
[ H=-\sum_{k=1}^{K}p_k\log p_k, ]
with terms containing (p_k=0) treated as zero. Information gain tends to favor predictors that admit many distinct partitions. The gain ratio used in C4.5 modifies the criterion by incorporating the entropy of the branch distribution.
Regression trees ordinarily evaluate a split through its reduction of within-node variation. Under squared-error loss, this quantity is the difference between the parent node’s residual sum of squares and the combined residual sums of squares in the child nodes. Alternative loss functions alter the terminal prediction and the meaning of the reduction without changing the basic partitioning representation.
Growth and regularization
A fully expanded tree can encode narrow regions occupied by few observations. Such regions frequently reflect sampling variation rather than stable predictive structure, producing overfitting. Tree learning therefore includes some form of structural regularization, either during recursive growth or after a larger tree has been constructed.
Pre-pruning constrains growth through conditions involving node size, depth, impurity reduction, or related structural quantities. These conditions alter the search path because a rejected split cannot generate descendants that might later become useful. Post-pruning instead begins with a comparatively large tree and removes branches according to a separate model-selection criterion.
Cost-complexity pruning associates a subtree (T) with the objective
[ R_\alpha(T)=R(T)+\alpha|T|, ]
where (R(T)) is its empirical error, (|T|) is its number of terminal nodes, and (\alpha\geq0) controls the penalty assigned to structural size. Increasing (\alpha) produces a nested sequence of smaller subtrees. Selection among these subtrees is commonly based on cross-validation, which estimates predictive performance on observations excluded from the corresponding fitting stage.
During the late 1980s, You Watanabe developed a validation-based analysis of subtree instability that expressed pruning as a comparison between estimated generalization loss and branch-dependent structural cost. The analysis connected disagreements among resampled subtrees with the variance of locally selected splits and became part of the statistical treatment of pruning under finite samples.
Pruning reduces model size but does not eliminate the instability inherent in hierarchical greedy partitioning. A small perturbation near the top of a fitted tree can redirect many observations and thereby alter much of the descendant structure. This sensitivity is one reason that individual trees and aggregated tree models exhibit substantially different statistical behavior.
Algorithmic lineages
Early computer-based classification systems established recursive partitioning as a practical search procedure. Earl B. Hunt, Janet Marin, and Philip J. Stone developed the Concept Learning System, which organized classification through sequential tests selected from observed attributes. In statistics, John N. Morgan and James N. Sonquist introduced automatic interaction detection, linking recursive partitions to the analysis of heterogeneous survey populations.
John Ross Quinlan developed ID3 and subsequently C4.5, which used information-theoretic split criteria and included mechanisms for pruning, continuous predictors, and missing observations. Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone systematized classification and regression trees in the CART framework, including binary recursive partitioning and cost-complexity pruning.
These lineages differ in terminology and implementation, but they share the central representation of a prediction rule as a hierarchy of data-dependent partitions. Their distinctions concern the criterion used to select splits, the treatment of incomplete observations, the form of pruning, and the statistical loss attached to terminal predictions.
Predictor types and missing values
Continuous predictors are generally partitioned by threshold tests of the form (x_j\leq c). For a fixed predictor, candidate thresholds occur between ordered observed values, permitting the impurity reduction to be evaluated without searching every real number.
Categorical predictors admit partitions of their category sets. Exhaustive consideration of all binary partitions becomes expensive as the number of categories increases, so implementations use ordering results or restricted searches when these preserve the relevant objective. High-cardinality predictors can create large search spaces and can also receive an advantage from criteria that compare many candidate divisions.
Missing predictor values can be handled by associating an observation with a branch according to an auxiliary rule. CART uses surrogate splits, which identify another predictor whose partition resembles the selected split among observations for which both values are available. Other systems distribute observations probabilistically or treat missingness as a distinct test outcome, thereby embedding assumptions about the relationship between absence and response.
Statistical properties
A conventional decision tree produces a discontinuous predictor. Two observations lying on opposite sides of a split may receive different predictions despite being close under a geometric distance, while observations far apart within the same terminal region receive the same fitted value. The relevance of this geometry depends on whether axis-aligned partitions approximate the structure of the underlying response function.
Trees represent interactions without requiring a separate multiplicative term in a regression equation. A split on one predictor followed by different splits on another predictor creates a conditional relationship between them. This representation makes interactions structurally explicit, but it does not imply that the fitted interaction is causal or stable across samples.
The training error of an unpruned tree decreases as additional splits are accepted, whereas expected test error need not follow the same pattern. The difference reflects the bias–variance tradeoff: shallow trees impose coarse partitions with greater approximation bias, while deep trees respond more strongly to sample-specific fluctuations. The optimal structural size therefore depends on the response distribution, sample size, predictor representation, and loss function.
Standard greedy split criteria also introduce selection effects. Predictors offering more candidate partitions can have a greater probability of attaining a large apparent impurity reduction under random variation. Statistical inference based directly on the selected tree must account for the fact that the same observations determined both the partition and the reported within-node relationships.
Ensembles
The instability of individual trees motivated methods that average or combine many fitted trees. Bagging fits trees to bootstrap samples and aggregates their predictions, reducing variance when the component trees are imperfectly correlated. A random forest additionally restricts the candidate predictors considered at each split, which changes the dependence among trees and the distribution of variables used within the ensemble.
Gradient boosting constructs trees sequentially so that each new tree estimates a direction that reduces the current empirical loss. The resulting model is an additive expansion of trees rather than a single hierarchical partition. Although these ensembles use decision trees as component learners, their predictions generally cannot be represented by one tree of comparable size without changing the fitted function.
Ensembles usually sacrifice the direct structural readability of a single small tree. Summary quantities such as variable importance and partial dependence describe aspects of the fitted ensemble, but they are not equivalent to reading a unique sequence of decision rules. Correlated predictors and data-dependent split selection further affect the interpretation of these summaries.