Decision Tree

A decision tree is a tree-structured model used in supervised learning. It predicts an outcome by routing an input from a root node through a sequence of tests to a terminal leaf. A classification tree returns a class or class scores; a regression tree returns a numeric value. The path to a leaf is a conjunction of conditions, such as age <= 30 followed by income > 50000. ^[6][13]

Trees can represent nonlinear effects and interactions without specifying those forms in advance. A small tree can also expose a prediction as a short rule path. These properties do not make every fitted tree accurate or easy to understand: deep trees can be unstable, large trees can be difficult to inspect, and the behavior of categorical features, missing values, probabilities, and pruning differs among algorithms and software implementations. ^{[6][11][12][13]}

Structure

A conventional decision tree contains:

• a root node, where all training observations begin;
• internal nodes, each of which applies a test and sends observations to child nodes;
• branches, which represent the possible outcomes of a test; and
• leaf nodes, which store the final prediction.

For an axis-aligned binary tree, an internal test often has the form x_j <= s, where x_j is one input feature and s is a threshold. The test partitions the node's observations into left and right children. Other tree families can use multiway categorical tests, statistical-significance tests, or linear combinations of several features. ^[2][6][10]

Tree depth is the largest number of splits on a root-to-leaf path. Tree size may refer to the number of nodes or leaves, so the convention should be stated. Increasing depth or leaf count expands the set of patterns a tree can fit, but also increases estimation variance and the number of rules a person must inspect. ^[6][12][23]

Classification and regression

Scroll sideways for more →

These are common choices rather than universal definitions. For example, scikit-learn 1.9 offers Gini, entropy, or log loss for DecisionTreeClassifier, and squared error, absolute error, or Poisson deviance for DecisionTreeRegressor; that release deprecates the older friedman_mse criterion name. Its class probabilities are the weighted class fractions among training observations in a leaf. ^[14][15]

Historical development

Recursive partitioning developed through several partly independent lines of statistical and machine-learning research. Historical surveys trace both statistical and machine-learning approaches to constructing trees from data. Loh's review identifies Morgan and Sonquist's 1963 Automatic Interaction Detection (AID) procedure as the first regression tree in the published literature. AID repeatedly forms binary groups that reduce residual sums of squares and predicts a constant within a terminal group. ^[1][6][9]

Messenger and Mandell's classification extension, THAID, appeared in 1972. Gordon Kass introduced Chi-squared Automatic Interaction Detection (CHAID) in 1980. CHAID uses significance tests in choosing and merging categories and can create multiway rather than only binary splits. ^[2][6]

The 1984 book Classification and Regression Trees by Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone presented CART. CART grows binary classification or regression trees and introduced a systematic cost-complexity pruning procedure that produces a nested sequence of subtrees. Its treatment also includes surrogate splits for missing data and extensions beyond simple univariate tests. ^[3][6]

Ross Quinlan's 1986 ID3 work described top-down induction using information gain and discussed modifications for noisy or incomplete information. Quinlan's 1993 C4.5 system added continuous attributes, unknown-value handling, gain-ratio selection, and pruning procedures. Describing ID3 as categorically incapable of any noisy or incomplete data treatment, or describing every implementation descended from CART as having identical facilities, is therefore too broad. ^[4][5][6]

Scroll sideways for more →

Learning a tree

Recursive partitioning

Most widely taught tree learners use top-down recursive partitioning:

1. Start with the training observations at the root.
2. Enumerate candidate tests allowed by the implementation.
3. Score each candidate using a node objective.
4. Apply the selected test and send observations to its children.
5. Repeat within each child until a stopping rule is met.
6. Optionally prune the resulting tree or select a subtree with validation data. ^[4][6][13]

For a node t divided into children t_1, ..., t_m, an impurity-reduction score can be written as

$$\Delta I = I(t) - \sum_{j=1}^{m}\frac{N_j}{N}I(t_j),$$

where I is the node impurity, N is the weighted number of observations at the parent, and N_j is the corresponding number at child j. A greedy learner selects a candidate with a large local reduction. The exact candidate set, tie-breaking, weight treatment, and stopping rules are implementation details. ^[6][13]

Classification criteria

For class proportions p_1, ..., p_K at a node, Gini impurity is

$$G(t)=1-\sum_{k=1}^{K}p_k^2.$$

It is zero when all observations at the node belong to one class. For two classes its maximum is 0.5, but for K equally represented classes its maximum is 1 - 1/K; 0.5 is not a universal upper bound.

Entropy is

$$H(t)=-\sum_{k=1}^{K}p_k\log_2 p_k,$$

with zero-probability terms treated as zero. Information gain is the parent entropy minus the weighted child entropy. ID3 uses this criterion. A variable with many candidate values can receive an advantage because it offers more ways to partition the training data. C4.5 uses gain ratio, which divides information gain by the entropy of the branch proportions, together with algorithm-specific selection rules. ^{[4][5][6][11]}

CHAID follows a different logic. It merges statistically similar categories and chooses a split using significance testing rather than maximizing Gini or information gain. Its tests, multiplicity adjustments, stopping levels, and ability to make multiway splits distinguish it from ordinary binary CART. ^[2][6]

Regression criteria

For squared-error regression, a candidate split is commonly judged by the reduction in the within-node sum of squared deviations. A leaf then predicts the mean response among its weighted training observations. This produces a piecewise-constant fitted function. Other criteria can produce different leaf summaries: absolute-error methods commonly use a median, and Poisson criteria are intended for nonnegative count-like targets. ^[1][6][15]

The criterion determines the local objective, not the metric a deployment must use. A model selected by squared-error reduction can still be evaluated with absolute error or a domain-specific cost, but training, tuning, and final evaluation data must remain appropriately separated. ^[15][17]

Stopping and pruning

Pre-pruning limits growth while the tree is being fitted. Common controls include maximum depth, minimum observations in a node or leaf, maximum leaf count, and minimum impurity decrease. Such controls regularize the tree and reduce computation, but a locally weak split can sometimes enable useful splits below it.

Post-pruning first grows a larger tree and then removes branches. CART's minimal cost-complexity formulation associates a subtree T with

$$R_\alpha(T)=R(T)+\alpha |\widetilde{T}|,$$

where R(T) is its empirical leaf risk, |\widetilde{T}| is its number of terminal nodes, and alpha >= 0 penalizes size. Weakest-link pruning generates nested subtrees as alpha increases. The pruning parameter or subtree is then selected using cross-validation or separate validation data. The precise normalization of R(T) is software-specific; scikit-learn, for example, documents a sample-weighted impurity term. ^[3][6][13]

C4.5 uses error-based pruning rather than CART's exact cost-complexity procedure. Reduced-error pruning is another family of methods, replacing a subtree with a leaf when that replacement does not worsen performance on a pruning set. Calling all post-pruning "CART pruning" obscures these differences. ^[5][6]

Data and implementation choices

Numerical and categorical features

Axis-aligned trees do not require feature standardization merely to compare thresholds within one feature. A strictly increasing transformation preserves the ordering of finite values and therefore preserves the set of order-based threshold partitions, apart from numeric precision, ties, and implementation details. Scaling can still matter elsewhere in a pipeline or for oblique splits that combine features.

Categorical support is not a property of every decision-tree implementation. Classical CART can search binary partitions of categories; ID3 and C4.5 define their own categorical procedures. Other libraries require an encoding step. Scikit-learn 1.9 explicitly documents that its tree implementation does not support categorical variables. Integer-coding an unordered category can impose an artificial order, while one-hot encoding changes the candidate split space. ^[3][5][13]

Missing values

Missing-value behavior is likewise algorithm-specific. The original CART treatment uses surrogate tests when the primary split variable is unavailable. C4.5 fractionally distributes cases with unknown values during induction and uses weighted branch information. CHAID can treat a missing category within its category-merging framework. ^[3][5][6]

As of the cited scikit-learn 1.9 documentation, DecisionTreeClassifier and DecisionTreeRegressor support missing values with the best splitter for specified criteria. For each threshold, the learner evaluates sending missing observations left or right. If a feature had no missing values during training, a missing value at prediction follows the child with more training observations. This is current versioned behavior, not a universal definition of CART or decision trees. ^[13][14][15]

Imputation remains useful when an estimator lacks native handling, when missingness must be modeled consistently across several models, or when deployment semantics require an explicit policy. Any learned imputer or encoder must be fitted inside each training fold rather than on the full dataset, or evaluation can leak information. ^[17]

Weights and multiple outputs

Many implementations accept sample or class weights, which alter node counts, impurity calculations, and leaf predictions. Weights can express unequal sampling or error costs, but their meaning depends on how they were constructed and on the final decision rule.

A multi-output tree uses one shared partition for several target columns. Scikit-learn's tree estimators support multiple outputs and average an impurity reduction across outputs. A shared tree can exploit common partition structure, but it also forces the outputs to share splits and should not be assumed superior to separate models. ^[13][14][15]

Optimization and statistical behavior

Greedy induction is popular because it converts a large tree-search problem into manageable node-level searches. It does not guarantee the globally best tree for a chosen objective and size. The exact complexity claim must name the optimization problem: Hyafil and Rivest proved NP-completeness for constructing a binary identification tree that minimizes expected tests, expressed as external path length. That result should not be paraphrased as a proof that every predictive-tree objective on every dataset is NP-complete. ^[7]

Modern optimal-tree methods formulate other objectives explicitly. Bertsimas and Dunn used mixed-integer optimization to search for classification trees under their stated loss and complexity penalty, including axis-aligned and multivariate variants. Such methods broaden the available search strategies, but their guarantees and computational costs attach to the particular formulation; they do not establish one universally optimal tree for all metrics or distributions. ^[8]

Greedy split selection can also be statistically biased. When predictors differ in the number of possible split points, exhaustive selection gives some predictors more opportunities to appear favorable by chance. Hothorn, Hornik, and Zeileis proposed conditional-inference trees that separate variable selection from split-point selection to address this problem under their testing framework. ^[11]

Small changes in training data can change an upper-level split and thereby reorganize much of a tree. This instability is a central reason for bagging and random forests, which aggregate trees fitted with randomized training information. Regularization and pruning can reduce instability, but they do not eliminate the need for resampling-based evaluation. ^[19][20]

Regression-tree predictions are normally piecewise constant. A standard mean-valued leaf does not extrapolate a trend beyond response values represented by its training leaves. Curved or diagonal boundaries may require many axis-aligned partitions, and a fully grown tree can isolate noise. These behaviors motivate regularization, oblique trees, model trees, and ensembles, depending on the task. ^[6][10][15]

Interpretation and feature importance

A root-to-leaf path supplies a local rule for how one tree produced a prediction. For a small tree, the complete node diagram can reveal interactions and decision thresholds. Interpretability decreases as the number and complexity of paths grow. In a controlled user study, Huysmans and colleagues found that comprehensibility depended on representation and model size; binary trees were not automatically the easiest representation for every task. Interpretability is therefore a property of a model, audience, presentation, and question rather than a guaranteed label attached to the algorithm family. ^[12][23]

Impurity-based importance

An impurity-based importance sums the weighted impurity reductions attributed to a feature across nodes. It is inexpensive because it reuses fitting statistics. It can, however, favor variables with many possible split points, reflect overfit training reductions, and distribute or concentrate credit unpredictably among correlated variables. A large score is not a causal effect and does not show that changing the feature would change the outcome. ^[11][16][22]

Permutation importance

Permutation importance measures how a chosen evaluation score changes after one feature is shuffled. It can be computed on held-out data and applied to any fitted model. It describes the model's reliance on the shuffled information for that dataset and metric, not the feature's intrinsic or causal importance. Correlated features can substitute for one another, so marginal shuffling may make each appear less important than the group. The model should first demonstrate useful held-out performance; otherwise an importance ranking explains a poorly generalizing model. ^[16]

Probability estimates and evaluation

The class fractions in a leaf are empirical proportions among the training observations routed there, possibly with weights. They are not guaranteed to be calibrated probabilities for new observations. Small leaves can yield extreme estimates, pruning changes the grouping, and sampling or distribution shift changes their interpretation. Niculescu-Mizil and Caruana's empirical calibration study found characteristic distortions for several learning methods, including decision trees and boosted trees. Calibration should be evaluated on data not used to fit the tree or tune its hyperparameters. ^[14][18]

Evaluation must match the prediction problem:

• for classification, report metrics suited to class imbalance and error costs rather than accuracy alone;
• for probabilistic outputs, use proper scoring rules and calibration diagnostics as well as thresholded decisions;
• for regression, choose losses that reflect the deployment cost and inspect residual behavior; and
• for temporal, grouped, spatial, or repeated-entity data, construct splits that prevent related observations from leaking across training and evaluation sets. ^[17]

Tree depth, pruning strength, minimum leaf size, criterion, class weights, and preprocessing choices should be selected within the training data. An untouched test set is used once for the final estimate when such an estimate is required. Repeatedly choosing settings from test performance turns the test set into training information. ^[17]

Variants and ensembles

Oblique decision trees test a linear combination of features, such as

$$w_1x_1+\cdots+w_px_p \le s.$$

They can represent some diagonal boundaries with fewer nodes than an axis-aligned tree. Searching the continuous coefficient space is harder, and a split involving many weighted variables can be harder to explain. The OC1 system combines deterministic coordinate changes with randomized perturbations to search for oblique splits. Its empirical results are dataset-specific rather than a guarantee that oblique trees always use fewer nodes or predict better. ^[10]

Model trees place a fitted model, often a linear regression, in a leaf rather than a constant. Conditional-inference trees use hypothesis tests to control variable selection and stopping. Multiway trees allow more than two children. These variants answer different design questions and should not be evaluated as interchangeable merely because all have a tree-shaped representation. ^[6][11]

Single trees are also base learners for ensemble methods:

Scroll sideways for more →

Ensembles often improve predictive performance relative to one untuned tree, but they sacrifice the global simplicity of a single small tree. Bagging, random forests, and gradient boosting are substantial model families with their own sampling, optimization, probability, and interpretation questions; they are related methods rather than synonyms for a decision tree. ^[19][20][21]

Computational characteristics

Training cost depends on the split search, data representation, stopping rules, feature types, and tree shape. A balanced axis-aligned tree implementation that sorts or presorts numerical values can have very different behavior from one that repeatedly scans unsorted data, enumerates category subsets, searches oblique hyperplanes, or solves a global optimization problem. A single universal formula such as "O(p n log n) at every node" is misleading because sorting and partitioning costs are not necessarily repeated independently at each node. ^[6][8][13]

Prediction for one ordinary tree follows one root-to-leaf path, so its number of tests is proportional to the reached leaf's depth. Memory use is proportional to the stored node data and any auxiliary statistics. Worst-case depth can grow linearly with the number of training observations, while a balanced tree has logarithmic depth. Practical latency and memory depend on pruning, numeric representation, sparse support, and implementation.

Software

Scikit-learn provides DecisionTreeClassifier, DecisionTreeRegressor, text and graphical export utilities, multi-output support, sample weights, and minimal cost-complexity pruning through ccp_alpha. Its documentation describes an optimized CART-derived implementation, but version 1.9 still excludes direct categorical-variable support and documents restricted native missing-value behavior. ^[13][14][15]

Other statistical and machine-learning systems implement CART, C4.5-derived, CHAID, conditional-inference, oblique, model-tree, and ensemble variants. Shared names do not imply identical defaults. Reproducible reporting should record the library and version, target definition, feature encoding, missing-data policy, criterion, stopping and pruning settings, random seed where applicable, and validation design.

Strengths and limitations

Common strengths of a single decision tree include:

• a prediction procedure made of explicit tests;
• support for nonlinear effects and interactions;
• application to classification and regression;
• little need for numerical feature scaling for ordinary axis-aligned thresholds;
• fast path-based prediction; and
• a compact representation when the fitted tree remains small. ^[6][13]

Important limitations include:

• instability under changes to the training sample;
• overfitting when growth is insufficiently regularized;
• greedy-search and split-selection bias;
• piecewise-constant regression and weak extrapolation;
• staircase approximations to some diagonal or curved boundaries;
• interpretability that deteriorates with tree size;
• importance scores that are not causal and can be biased or correlation-sensitive;
• leaf class fractions that may be poorly calibrated; and
• implementation-dependent treatment of categories and missing values. ^{[6][10][11][12][16][18][19]}

A decision tree is therefore best treated as a transparent modeling form whose actual reliability depends on its fitted size, objective, implementation, and evaluation. It can be a useful standalone model or baseline when a compact rule system is valuable. When predictive performance is the main objective, a comparison with regularized linear models, tree ensembles, and other appropriate baselines should use the same leakage-safe validation design.

See also

• Machine learning
• Classification
• Regression
• Pruning
• Random forest
• Gradient boosting
• Interpretability

References

1. ^James N. Morgan and John A. Sonquist, "Problems in the Analysis of Survey Data, and a Proposal," *Journal of the American Statistical Association* 58(302), 415-434 (1963). doi.org/...01621459.1963.10500855
2. ^Gordon V. Kass, "An Exploratory Technique for Investigating Large Quantities of Categorical Data," *Applied Statistics* 29(2), 119-127 (1980). doi.org/...2986296
3. ^Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone, *Classification and Regression Trees* (Wadsworth, 1984). books.google.com/books
4. ^J. Ross Quinlan, "Induction of Decision Trees," *Machine Learning* 1, 81-106 (1986). doi.org/...BF00116251
5. ^J. Ross Quinlan, *C4.5: Programs for Machine Learning* (Morgan Kaufmann, 1993). doi.org/...C2009-0-27846-9
6. ^Wei-Yin Loh, "Fifty Years of Classification and Regression Trees," *International Statistical Review* 82(3), 329-348 (2014). doi.org/...insr.12016
7. ^Laurent Hyafil and Ronald L. Rivest, "Constructing Optimal Binary Decision Trees is NP-Complete," *Information Processing Letters* 5(1), 15-17 (1976). doi.org/...0020-0190(76)90095-8
8. ^Dimitris Bertsimas and Jack Dunn, "Optimal Classification Trees," *Machine Learning* 106, 1039-1082 (2017). doi.org/...s10994-017-5633-9
9. ^Sreerama K. Murthy, "Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey," *Data Mining and Knowledge Discovery* 2, 345-389 (1998). doi.org/...A:1009744630224
10. ^Sreerama K. Murthy, Simon Kasif, and Steven Salzberg, "A System for Induction of Oblique Decision Trees," *Journal of Artificial Intelligence Research* 2, 1-32 (1994). doi.org/...jair.63
11. ^Torsten Hothorn, Kurt Hornik, and Achim Zeileis, "Unbiased Recursive Partitioning: A Conditional Inference Framework," *Journal of Computational and Graphical Statistics* 15(3), 651-674 (2006). doi.org/...106186006X133933
12. ^Johan Huysmans, Kris Dejaeger, Christophe Mues, Jan Vanthienen, and Bart Baesens, "An Empirical Evaluation of the Comprehensibility of Decision Table, Tree and Rule Based Predictive Models," *Decision Support Systems* 51(1), 141-154 (2011). doi.org/...j.dss.2010.12.003
13. ^Scikit-learn developers, "Decision Trees," scikit-learn 1.9 User Guide. scikit-learn.org/...tree
14. ^Scikit-learn developers, "DecisionTreeClassifier," scikit-learn 1.9 API Reference. scikit-learn.org/...rn.tree.DecisionTreeClassifier
15. ^Scikit-learn developers, "DecisionTreeRegressor," scikit-learn 1.9 API Reference. scikit-learn.org/...arn.tree.DecisionTreeRegressor
16. ^Scikit-learn developers, "Permutation Feature Importance," scikit-learn 1.9 User Guide. scikit-learn.org/...permutation_importance
17. ^Scikit-learn developers, "Common Pitfalls and Recommended Practices," scikit-learn 1.9 User Guide. scikit-learn.org/...common_pitfalls
18. ^Alexandru Niculescu-Mizil and Rich Caruana, "Predicting Good Probabilities with Supervised Learning," *Proceedings of ICML 2005*, 625-632. doi.org/...1102351.1102430
19. ^Leo Breiman, "Bagging Predictors," *Machine Learning* 24, 123-140 (1996). doi.org/...BF00058655
20. ^Leo Breiman, "Random Forests," *Machine Learning* 45, 5-32 (2001). doi.org/...A:1010933404324
21. ^Jerome H. Friedman, "Greedy Function Approximation: A Gradient Boosting Machine," *The Annals of Statistics* 29(5), 1189-1232 (2001). doi.org/...1013203451
22. ^Carolin Strobl, Anne-Laure Boulesteix, Achim Zeileis, and Torsten Hothorn, "Bias in Random Forest Variable Importance Measures: Illustrations, Sources and a Solution," *BMC Bioinformatics* 8, 25 (2007). doi.org/...1471-2105-8-25
23. ^Maria-Florina Balcan and Dravyansh Sharma, "Learning Accurate and Interpretable Decision Trees," *Proceedings of Machine Learning Research* 244, 1113-1140 (2024). proceedings.mlr.press/...balcan24a