Decision tree learning · aiwiki.page

Decision tree learning is a supervised learning method that builds a predictive model by recursively dividing training data into subsets. The resulting tree contains internal nodes that test input features, branches representing test outcomes, and leaves that supply predictions. It supports both classification, which predicts categories, and regression, which predicts numerical values. Within machine learning, trees provide a nonparametric approach: they do not require a predefined linear relationship between inputs and outputs. (scikit-learn.org)

Representation and prediction

A decision tree represents a sequence of conditional decisions. A numerical test commonly compares one feature with a threshold, such as whether a measurement exceeds a specified value. Categorical tests can distinguish individual categories or groups of categories. Prediction begins at the root and follows the applicable branches until reaching a leaf. Each root-to-leaf path can therefore be expressed as an if–then rule whose conditions are jointly satisfied. (storm.cis.fordham.edu)

For classification, a leaf commonly predicts its most frequent training class. It can also estimate class probabilities from the proportions of classes among samples reaching that leaf, with sample weights incorporated when applicable. For regression using mean squared error, the leaf predicts the mean target value; under absolute-error loss, it predicts the median. The prediction rule consequently depends on the chosen loss function. (sklearn.org)

Learning and split criteria

Most established tree-building methods use recursive, greedy partitioning. At each node, an algorithm evaluates candidate tests, selects a locally favorable split, and repeats the process in the resulting subsets. This local search does not generally produce a globally optimal tree. Construction stops when a stopping condition is met, such as a depth limit, insufficient samples, or sufficiently homogeneous targets. (scikit-learn.org)

Classification splits are often evaluated using impurity measures. For a node containing class proportions $p_1,\ldots,p_K$ , common measures are:

G=1-\sum_{k=1}^{K}p_k^2, \qquad H=-\sum_{k=1}^{K}p_k\log_2 p_k.

Here, $G$ is Gini impurity and $H$ is information entropy, with $0\log 0$ interpreted as zero. Both vanish when a node contains only one class. A candidate split is evaluated by comparing the parent’s impurity with the sample-weighted impurities of its children. The reduction in entropy is called information gain. (scikit-learn.org)

Regression trees instead evaluate how well a partition reduces numerical prediction error. Under squared-error loss, choosing a split that reduces within-node target variance is equivalent to reducing squared deviations from the child-node means. Other criteria permit different objectives, including absolute error and Poisson deviance. (scikit-learn.org)

Major algorithm families

ID3, associated with J. Ross Quinlan, selects categorical attributes using information gain and can create multiway branches. Quinlan’s 1986 paper Induction of Decision Trees described ID3 in detail and examined extensions for noisy and incomplete information. It also discussed information gain’s tendency to favor tests with many possible outcomes. (doi.org)

C4.5 extended the ID3 approach, notably by supporting continuous-valued attributes through threshold tests. Classification and Regression Trees (CART) supports both categorical and numerical targets and constructs binary trees. These families differ in their treatment of candidate splits, target types, and simplification procedures; “decision tree” therefore describes a model family rather than one uniquely specified learning algorithm. (scikit-learn.org)

Complexity control and evaluation

Trees grown with few restrictions can fit noise and small irregularities in their training examples, producing overfitting. Pre-pruning restricts growth through limits such as maximum depth, minimum leaf size, or minimum impurity reduction. Post-pruning removes branches after a larger tree has been constructed. Both approaches act as regularization by limiting model complexity. (scikit-learn.org)

Cost-complexity pruning balances fit against tree size through an objective of the form

R_\alpha(T)=R(T)+\alpha L(T),

where $R(T)$ measures training error or weighted leaf impurity, $L(T)$ counts leaves, and $\alpha\geq0$ controls the complexity penalty. Larger penalties favor smaller trees. Pruning generates candidate subtrees that can be compared using held-out performance rather than training fit alone. (scikit-learn.org)

Depth, leaf-size limits, and pruning strength are hyperparameters. Their selection commonly uses a validation set or cross-validation, while a separate test set estimates performance after model selection. This distinction matters because repeatedly selecting configurations using test results allows information from the evaluation data to influence the model. Preprocessing and feature selection can also introduce data leakage when fitted before the evaluation split rather than within the training portion. (scikit-learn.org)

Strengths, limitations, and ensembles

Small trees can be inspected directly and translated into rules. Numerical trees generally do not require feature scaling, because their tests depend on feature ordering rather than distances. However, large trees are harder to interpret, and small changes in training examples can produce substantially different structures. Conventional regression trees give piecewise-constant predictions and do not naturally extrapolate continuous trends beyond the observed target range. (scikit-learn.org)

Tree instability motivates ensemble methods. Bootstrap aggregating combines models trained on resampled datasets. A random forest additionally considers randomized subsets of features during tree construction, reducing dependence between trees and often lowering prediction variance. Gradient boosting builds trees sequentially to improve an additive model according to a loss function. These methods retain trees as component learners, but their combined predictions are less directly represented by a single readable rule path. (scikit-learn.org)