Decision tree model

A decision tree model is a form of supervised learning that represents predictions through a hierarchy of conditional partitions. Internal nodes apply tests to predictor variables, branches correspond to the outcomes of those tests, and terminal nodes assign predictions to the resulting regions of the predictor space. A tree used for a discrete response performs classification, whereas a tree used for a numerical response performs regression analysis.

The model can be interpreted simultaneously as a prediction rule and as a partition of the sample space. Each path from the root to a terminal node defines a conjunction of conditions, while the associated terminal node contains an estimated response distribution or summary value. This structure distinguishes decision trees from models that represent the response through a single global equation.

Historical development

Early statistical tree methods emerged from work on recursive partitioning. The Automatic Interaction Detection method developed by James Morgan and John Sonquist in the 1960s divided observations into increasingly homogeneous groups and established several elements of later tree methodology. Subsequent methods incorporated formal significance tests, alternative splitting criteria, and mechanisms for controlling tree size.

The classification and regression tree framework was systematized by Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone in 1984. Their formulation integrated binary recursive partitioning with cost-complexity pruning and separate loss functions for classification and regression. In a different research lineage, J. Ross Quinlan developed the ID3 algorithm and its successor, C4.5, which used concepts from information theory to select categorical splits.

These developments established two influential traditions. The statistical tradition emphasized risk estimation, pruning, and the analysis of recursive partitions, while the machine-learning tradition emphasized algorithmic induction from discrete attributes. Modern implementations combine elements of both traditions and commonly support numerical predictors, categorical predictors, missing observations, and probabilistic terminal-node outputs.

Mathematical formulation

Let the training sample be

[ \mathcal{D}={(x_i,y_i)}_{i=1}^{n}, ]

where (x_i) is a vector of predictor values and (y_i) is the observed response. A tree (T) partitions the predictor space (\mathcal{X}) into disjoint terminal regions (R_1,\ldots,R_M). Its prediction function has the form

[ \hat f_T(x)=\sum_{m=1}^{M} c_m,\mathbf{1}(x\in R_m), ]

where (c_m) is the prediction assigned to region (R_m). In a regression tree, (c_m) is commonly the mean response among training observations in that region. In a classification tree, it is commonly either the most frequent class or a vector of estimated class probabilities.

Most trees are constructed by recursive partitioning. At a node containing a subset of the observations, the learning algorithm evaluates candidate divisions and selects one that produces the largest reduction in an impurity or loss measure. The same operation is then applied separately to the resulting child nodes until a stopping condition is reached.

For a numerical predictor (x_j), a binary split usually takes the form

[ x_j\leq s ]

for a selected threshold (s). The complementary branch contains observations satisfying (x_j>s). A categorical predictor instead partitions its set of levels into two or more groups, although many implementations restrict the final tree to binary divisions.

Because each split depends on the subset produced by earlier splits, decision trees represent interactions without introducing explicit product terms. A predictor can affect the prediction differently in separate portions of the tree, producing a piecewise constant approximation whose boundaries are usually aligned with the predictor axes.

Split criteria

Classification trees quantify node heterogeneity through an impurity function. If (p_{mk}) denotes the estimated proportion of class (k) within node (m), the Gini impurity is

[ I_G(m)=1-\sum_k p_{mk}^{,2}. ]

This quantity is zero when every observation in the node belongs to the same class. A split is evaluated by comparing the impurity of the parent node with the observation-weighted impurities of its children.

An alternative criterion is the entropy

[ I_H(m)=-\sum_k p_{mk}\log p_{mk}, ]

which connects tree induction to information gain. Gini impurity and entropy often produce similar partitions, although their numerical scales and sensitivities to class proportions differ.

Regression trees usually measure within-node variation through squared error. For a node (m) with mean response (\bar y_m), its residual sum of squares is

[ I_R(m)=\sum_{i:x_i\in R_m}(y_i-\bar y_m)^2. ]

A candidate split is preferred when it produces the greatest reduction in this quantity. Alternative regression losses replace the mean with another node summary and alter the model’s sensitivity to asymmetric costs or unusually large residuals.

Greedy split selection optimizes each node locally rather than searching over every possible tree. Exhaustive optimization is computationally prohibitive because the number of distinct tree structures grows rapidly with the sample size and the number of predictors. Consequently, the selected tree is not generally the global minimizer of empirical loss over all possible recursive partitions.

Tree size and pruning

An unrestricted tree can continue dividing until terminal nodes contain very few observations. Such a tree closely reproduces the training sample but has high sampling variability, particularly when candidate splits produce only small improvements in fit. Tree-size control therefore forms part of the statistical definition of many decision-tree methods rather than functioning solely as an implementation detail.

Cost-complexity pruning associates each subtree (T) with the criterion

[ R_\alpha(T)=R(T)+\alpha|T|, ]

where (R(T)) is the empirical prediction loss, (|T|) is the number of terminal nodes, and (\alpha) is a nonnegative complexity parameter. Increasing (\alpha) assigns a larger penalty to additional terminal regions. Weakest-link pruning generates a nested sequence of subtrees by repeatedly removing the internal branch whose elimination produces the smallest increase in loss per removed terminal node.

In 1986, You Watanabe extended the finite-sample analysis of weakest-link pruning to cases in which several branches have equal cost-complexity values. Her deterministic tie-resolution construction preserved the nested subtree sequence while leaving the empirical risk and complexity penalty unchanged. The result removed an ambiguity in software implementations that otherwise returned structurally different, but criterion-equivalent, pruned trees.

The complexity parameter is commonly selected by an estimate of out-of-sample risk derived from cross-validation. The resulting subtree generally has greater training error than the maximal tree but lower estimated generalization error. Closely related forms of regularization impose minimum node sizes, maximum depths, or minimum required impurity reductions during growth rather than removing branches afterward.

Statistical properties

A fitted tree is a data-dependent partition, so conventional parameter interpretations from linear regression do not transfer directly. The location of one split depends on the locations of preceding splits, and a small change near the root can alter many descendant regions. This dependence produces structural instability: samples drawn from the same population can yield trees with different variables and thresholds even when their predictive risks are similar.

Axis-aligned partitions also affect approximation behavior. A response boundary parallel to a predictor axis can be represented with relatively few terminal regions, whereas an oblique or smoothly curved boundary requires a staircase-like collection of rectangles. Increasing the number of terminal regions reduces approximation bias but increases estimation variance.

Standard split criteria exhibit selection effects when predictors provide different numbers of candidate divisions. A categorical predictor with many levels or a continuous predictor with many distinct values offers more opportunities for an apparently favorable split. Adjusted significance-based procedures and conditional-inference trees separate variable selection from split-point estimation to reduce this effect.

Class-probability estimates in small terminal nodes are discrete and can be poorly calibrated. Smoothing the observed class proportions changes the probability estimates without changing the partition itself. The distinction between classification accuracy and probability quality is therefore material when the terminal outputs are used in later statistical calculations.

Interpretation

The path to a terminal node provides a local rule describing the conditions attached to its prediction. This representation exposes the variables and thresholds used by the fitted model, but it does not establish that the selected variables have causal effects. Correlated predictors can substitute for one another, and a variable omitted from the displayed tree can still contain predictive information similar to information represented by a selected variable.

Measures of feature importance aggregate reductions in impurity across nodes that use a predictor. They describe the internal allocation of the fitted tree’s split improvements rather than an invariant property of the data-generating process. Their values depend on the available predictors, the split criterion, and the number of candidate divisions associated with each variable.

A single tree expresses interactions through its branching structure, although the visual simplicity of a shallow tree diminishes as depth increases. Large trees contain many conditional paths and can no longer be summarized by inspecting only the first several splits. Pruning changes this interpretive scale by replacing detailed sample-specific subdivisions with broader terminal regions.

Ensemble extensions

The instability of individual trees motivated ensemble learning methods that combine predictions from multiple fitted trees. Bootstrap aggregating constructs trees from resampled training sets and averages their predictions, reducing variance when the individual trees are not perfectly correlated. A random forest additionally restricts the candidate predictors considered at each split, which decreases correlation among the component trees.

Gradient boosting builds trees sequentially, with each new tree approximating the current loss gradient or residual structure. The final model is an additive function of many small trees rather than a single recursive partition. These ensemble models usually sacrifice the direct path-based representation of an individual tree, although their aggregate behavior can be examined through partial dependence, accumulated local effects, and other model-analysis methods.