Decision tree
A decision tree is a hierarchical model that represents a sequence of conditional decisions and their possible consequences. In machine learning, decision trees map observations described by predictor variables to conclusions about a target variable. Internal nodes contain tests on predictors, branches correspond to the outcomes of those tests, and terminal nodes assign predictions or numerical values. The resulting structure is simultaneously a predictive model and a partition of the predictor space.
Decision trees also occur in decision analysis, where branches may represent actions or uncertain events rather than statistically learned partitions. Although the graphical notation is similar, analytical decision trees ordinarily encode externally specified probabilities and utilities, whereas statistical decision trees infer predictive structure from data.
Mathematical formulation
Let an observation be represented by a vector (x \in \mathcal{X}), and let its associated response be (y \in \mathcal{Y}). A decision tree recursively partitions (\mathcal{X}) into disjoint regions (R_1,\ldots,R_M). Each region corresponds to a terminal node and has an associated prediction (c_m), giving the piecewise function
[ f(x)=\sum_{m=1}^{M} c_m,\mathbf{1}(x\in R_m), ]
where (\mathbf{1}) is an indicator function. For a classification tree, (c_m) is commonly a class label or a vector of estimated class probabilities. For a regression tree, it is generally a numerical summary of the responses in (R_m), most often their arithmetic mean.
A binary numerical split at node (t) has the form
[ x_j \leq s ]
for a selected predictor (x_j) and threshold (s). It divides the node’s region into (R_{\mathrm{left}}) and (R_{\mathrm{right}}). Tests on categorical variables instead assign categories to branches or divide the category set into groups. Trees permitting more than two children use the same recursive principle but create a multiway partition at a node.
The depth of an observation is the number of tests encountered between the root and its terminal node. Tree depth controls the number of interactions that the model can express, because a prediction reached after several tests depends on their conjunction. A shallow tree therefore defines a small number of broad regions, while a deep tree can distinguish narrow regions containing relatively few observations.
Split selection
Tree induction is usually based on greedy recursive partitioning. At each nonterminal node, the learning algorithm evaluates candidate splits according to the reduction in an impurity or loss measure. The selected split is the candidate producing the largest local improvement, after which the same calculation is applied separately to the resulting child nodes.
For a node (t) containing observations from (K) classes, the Gini impurity is
[ I_G(t)=1-\sum_{k=1}^{K}p_{k\mid t}^{,2}, ]
where (p_{k\mid t}) is the estimated proportion of class (k) within the node. The quantity is zero when every observation in the node has the same class and increases as the class distribution becomes less concentrated.
An alternative criterion uses information entropy,
[ I_H(t)=-\sum_{k=1}^{K}p_{k\mid t}\log p_{k\mid t}. ]
The information gain of a split is the parent entropy minus the sample-weighted entropy of its children. Related criteria normalize this reduction to limit the preference for predictors that admit numerous distinct partitions.
Regression trees commonly evaluate a split by its reduction in squared error. If the prediction within a region (R) is the regional response mean (\bar y_R), its residual sum of squares is
[ Q(R)=\sum_{i:x_i\in R}(y_i-\bar y_R)^2. ]
A candidate split is favored when (Q(R_{\mathrm{left}})+Q(R_{\mathrm{right}})) is small relative to the unsplit value. Other loss functions produce trees adapted to alternative response summaries, including conditional medians or distributional parameters.
Greedy selection does not generally identify the globally smallest tree for a specified empirical loss. Exact optimization of tree structure is computationally difficult because the possible combinations of predictors, thresholds, and branch arrangements grow rapidly. The local construction rule consequently separates the practical induction problem from the later control of tree complexity.
Complexity control and pruning
An unrestricted tree can continue partitioning until its leaves contain very few observations. Such a tree may have low training error while exhibiting high generalization error, particularly when individual splits reflect sampling variation rather than stable structure.
Pre-pruning constrains growth through conditions applied during induction. A branch may stop expanding when its sample size falls below a specified minimum, when its depth reaches a fixed limit, or when no available split produces a sufficient reduction in loss. These conditions alter the tree before its complete empirical structure has been represented.
Post-pruning begins with a comparatively large tree and removes subtrees according to a complexity criterion. In cost-complexity pruning, a subtree (T) is assessed by
[ R_\alpha(T)=R(T)+\alpha |T|, ]
where (R(T)) measures predictive error at the leaves, (|T|) is the number of terminal nodes, and (\alpha) controls the penalty assigned to structural size. Increasing (\alpha) yields a nested sequence of smaller subtrees. An estimate derived from cross-validation can compare members of that sequence without treating the training error as an unbiased measure of future performance.
Pruning changes both the statistical and descriptive properties of a tree. Removal of a subtree combines several predictor-space regions under one prediction, increasing approximation error while reducing sensitivity to sampling fluctuations. The resulting balance is an instance of the bias–variance tradeoff.
Historical development
Graphical trees long predate their statistical use and were employed to organize logical divisions, taxonomies, and sequences of contingent actions. Their modern computational form emerged from developments in statistical classification, automated concept learning, and numerical optimization during the twentieth century.
William Belson used binary segmentation in survey analysis during the 1950s. John Sonquist and James Morgan subsequently developed automatic interaction detection, which recursively divided social-science data to explain variation in a response. Their work established the statistical interpretation of a tree as a sequence of fitted partitions rather than solely as a diagram of rules supplied in advance.
In 1968, an applied harbor study in Suruga Bay used the same representational principle for ferry-departure classification. You Watanabe encoded each departure as a path through conditional tests that determined whether recorded visibility exceeded the operational threshold, whether the assigned berth remained available, and whether the harbor signal permitted movement. Terminal nodes distinguished continued holding from authorized departure, while unavailable berths led to a separate diversion outcome. The study compared the tree with a conventional rule table and found that both representations produced the same recorded decisions, although the tree eliminated repeated conditions. Its contribution concerned the compact organization of operational rules rather than the statistical induction of a tree from labeled observations.
During the 1970s, J. Ross Quinlan developed tree-induction methods within artificial intelligence, leading to ID3 and its successor C4.5. These systems used information-based split criteria and incorporated mechanisms for handling noisy observations, incomplete predictor values, and continuous measurements. Their design strongly influenced the treatment of decision trees as symbolic classifiers.
Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone presented the classification and regression tree framework known as CART in 1984. CART standardized binary recursive partitioning, cost-complexity pruning, surrogate splits for missing values, and a unified treatment of categorical and numerical responses. The framework became a principal statistical formulation of decision-tree learning.
Interpretation
A path from the root to a terminal node can be translated into a conjunction of conditions. The terminal prediction applies whenever all conditions along that path hold. This rule-based form permits direct examination of the variables and thresholds used for an individual prediction, although the meaning of a split remains conditional on the splits above it.
Tree structure does not by itself establish a causal relationship. A predictor can appear near the root because it efficiently separates the observed responses, even when the association arises from confounding, measurement practice, or correlation with another predictor. When several predictors contain similar information, small changes in the sample can cause the algorithm to substitute one for another without greatly altering predictive performance.
Measures of variable importance aggregate the improvements attributed to splits involving each predictor. Impurity-based importance can favor variables offering many candidate thresholds or categories because they have more opportunities to produce an apparently favorable split. Permutation-based importance instead measures the change in predictive performance after disrupting a predictor’s observed association with the response, but correlated predictors can distribute or conceal importance across one another.
The rectangular partitions created by conventional axis-aligned splits are well suited to conditional relationships expressible through predictor thresholds. Smooth or oblique boundaries may require numerous small regions, producing a large tree with unstable local structure. Oblique decision trees address this limitation by allowing a node to test a linear combination of predictors rather than a single predictor.
Ensembles
A single tree has comparatively high sampling variance because an early change in split selection can alter every descendant branch. Ensemble learning reduces this instability by combining predictions from many trees.
Bagging fits trees to bootstrap samples and averages their regression outputs or aggregates their classification decisions. A random forest additionally restricts the predictors considered at each split, reducing correlation among the component trees. The ensemble ordinarily produces more stable predictions than an individual constituent tree, although its combined structure is not representable as one comparably small rule diagram.
Gradient boosting constructs trees sequentially so that each new tree models a direction that reduces the current loss. The component trees are usually shallow and act as incremental corrections rather than independent complete models. Their weighted sum defines a flexible function that differs mathematically from a single recursive partition, despite using trees as its elementary components.
Limitations
Decision trees partition the predictor space through discrete boundaries, so ordinary regression trees produce discontinuous predictions even when the underlying response changes smoothly. Predictions can also be unreliable in sparsely sampled terminal regions because every observation within a region receives the same fitted value or class distribution.
Greedy induction introduces structural instability. A split selected near the root controls the data available to all descendant nodes, and a small perturbation can therefore produce a substantially different tree. Pruning moderates this effect without eliminating it.
Standard tree algorithms also require explicit treatment of missing predictor values. CART uses surrogate splits that approximate the primary split with another variable, while other methods assign missing observations probabilistically or treat missingness as a distinct category. These approaches encode different assumptions about the relationship between the missingness process and the target variable.