Dictionary of Applied Machine Learning: 107 machine-learning terms, each with a definition, a figure, citations and a Python demo · All terms · Demos · Start here

decision tree

Updated on 2026-10-22

Readiness 100/100

▶ Run the Python demo Open in Colab Typeset PDF LaTeX source Cite this entry

See also classification random forest feature importance interpretable machine learning

A decision tree is a flowchart-like representation of a hypothesis map: a root node reads in the feature vector of a data point and evaluates a basic test on it. The test result selects a child node, which applies a further test, and the forwarding continues until the feature vector reaches a leaf node. A leaf node has no children and represents one specific function value, i.e., a prediction. The tree partitions the feature space into decision regions, one per leaf node, on which the represented hypothesis is constant. A maximum depth and a family of node tests define the model, the hypothesis space of all such trees, which has no vector of model parameters of fixed length and is therefore searched greedily rather than by gradient methods. Decision trees serve as base models of the random forest and of gradient-boosted decision tree (GBDT) methods. Small decision trees yield interpretable machine learning (interpretable ML) if the user can comprehend the tests executed at their nodes.

Figure produced by the Python demo of the entry decision tree
Figure written by the entry's Python demo decisiontree.py, which recomputes what the entry states: the script block by block · open in Colab

Definition

A bank's loan approval can be written as a chain of simple tests on the applicant's features that ends in an "approve" or "reject" prediction. For example, is the income above a threshold? Is the credit score large enough? A decision tree is such a chain in general form: a flowchart-like representation of a hypothesis map $\hypothesis$.

More formally, a decision tree is a directed acyclic graph (DAG) containing a root node that reads in the feature vector $\featurevec$ of a data point. The root node then forwards the data point to one of its child nodes based on some elementary test on the features $\featurevec$. If the receiving child node is not a leaf node, i.e., it has child nodes itself, it represents another test. Based on the test result, the data point is forwarded to one of its descendants. This testing and forwarding of the data point is continued until the data point ends up in a leaf node without any children, which carries the prediction $\predictedlabel = \hypothesis(\featurevec)$ returned by the tree for this data point (Fig. 1). The leaf nodes partition the feature space into decision regions; in Fig. 1, each test compares an entry of $\featurevec$ with a threshold, so the decision regions are rectangles. Next to each node, Fig. 1 highlights the part of the feature space that contains the feature vectors reaching that node.

Figure 1 of the entry decisiontree
Figure 1: Decision tree as a flowchart-like representation of a piecewise constant hypothesis $\hypothesis: \featurespace \rightarrow \reals$ for feature vectors $\featurevec = (\feature_{1}, \feature_{2})^{\top}$. Each test compares a single feature with one of the thresholds $\varepsilon, \varepsilon' > 0$, which are marked on the axes of each square. Next to each node, the shaded part of the feature space (depicted as a square with the axes $\feature_{1}$ and $\feature_{2}$) contains the feature vectors that reach that node. The shaded parts at the leaf nodes are the decision regions $\decreg{\predictedlabel} \defeq \big\{ \featurevec \in \featurespace: \hypothesis(\featurevec) = \predictedlabel \big\}$: rectangles, since every test involves a single feature
Fixing a maximum depth $D$ and a family of allowed tests defines the model: the hypothesis space $\hypospace$ of all decision trees of depth at most $D$ whose node tests belong to the family, for instance all threshold tests $\feature_{\featureidx} \leq \varepsilon$ with $\featureidx \in \{1, \ldots, \featuredim\}$ and $\varepsilon \in \reals$ (Shalev-Shwartz and Ben-David, 2014, Sect. 18.1). A tree in $\hypospace$ is specified by its shape, by the index $\featureidx$ of the feature and the threshold $\varepsilon$ that each test node compares, and by the value of each leaf node.

This hypothesis space has no natural parametrization. The shape of the tree and the index $\featureidx$ of the feature tested at each node are discrete choices, and how many of them a tree has depends on its shape, so $\hypospace$ is not the image of a vector of model parameters of fixed length: there is no parameter space $\reals^{n}$ on which the training error is a function. The thresholds form a vector once the shape and the tested features are fixed, but the training error is piecewise constant in each of them, since a data point changes child only when the threshold crosses its feature value, so the gradient is zero wherever it exists. Empirical risk minimization (ERM) over $\hypospace$ can therefore not use gradient descent (GD), and a fixed point view of the training iteration does not apply: an iteration adds a node, it does not update a vector. Minimizing a bound that adds a size penalty to the training error is computationally hard, and the methods below search $\hypospace$ greedily (Shalev-Shwartz and Ben-David, 2014, Sect. 18.2).

Training a decision tree amounts to extending a leaf node by attaching another decision tree. In the simplest case, a leaf node is replaced with a test node whose children are new leaf nodes (Fig. 2).

Figure 2 of the entry decisiontree
Figure 2: Training grows a decision tree. The tree on the right is obtained from the tree on the left by replacing the leaf node with prediction $\predictedlabel_2$ with a test node whose children are two new leaf nodes (dashed edges)
Widely used training methods for decision trees include classification and regression trees (CART) (Breiman et al., 1984), iterative dichotomiser 3 (ID3) (Quinlan, 1986), and C4.5 (Quinlan, 1993). Starting from a single leaf node, CART repeatedly replaces a leaf node with a test node. An impurity measure assigns a nonnegative number to a set of labels: it is zero when the labels agree, and it grows as they spread out. Among candidate tests that compare a single feature with a threshold, CART scores each test by the impurity of the two children, weighted by the fraction of data points routed to each of them, and greedily selects the test with the smallest score, i.e., with the largest reduction against the impurity of the parent node. Common impurity measures are the Gini index and the entropy for classification, and the squared error around the mean label for regression (Hastie et al., 2009, Sects. 9.2.2 and 9.2.3). This selection is a combinatorial search over candidate tests rather than a gradient-based update of continuous model parameters. The growth stops only when a leaf node contains too few data points, not when no candidate test reduces the impurity much, since a test that reduces the impurity little can enable a strong test below it (Hastie et al., 2009, Sect. 9.2.2). The large tree is then pruned back by cost-complexity pruning, which removes the subtrees whose impurity reduction does not pay for the leaf nodes they add (Hastie et al., 2009, Sect. 9.2.2). The depth of a decision tree is the number of tests on the longest path from the root node to a leaf node; the tree in Fig. 1 has depth two.

B-treeFig. 3 shows, as a scatterplot, the result of this training on real data. Each day of $2024$ at the Finnish Meteorological Institute (FMI) weather station Helsinki Kaisaniemi (Finnish Meteorological Institute, 2024) is a data point, with the minimum temperature of the day as its feature and the maximum temperature as its label. The learned depth-$2$ tree is a piecewise constant hypothesis with four pieces, one per leaf node, each equal to the mean label of the days routed there. The tree was grown to depth two rather than until the stopping rule above fired, so that each of its four pieces is visible in the picture.

Figure 3 of the entry decisiontree
Figure 3: Each of the $366$ days of $2024$ at the FMI station Helsinki Kaisaniemi is a data point, drawn as an open circle: its feature is the minimum temperature of the day (horizontal axis) and its label the maximum temperature of the day (vertical axis). The thick solid step function is the piecewise constant hypothesis $\learnthypothesis$ learned by a regression tree of depth two. The three thresholds of its test nodes, at $-10.35\,^{\circ}$C, $6.20\,^{\circ}$C, and $10.55\,^{\circ}$C (dotted verticals), are the positions of the three jumps and split the feature axis into four intervals. On each interval, the step function is flat at the mean label of the data points routed to that leaf node. Data generated by pythondemos/decisiontree.py
Decision trees serve as base models of the random forest and of gradient-boosted decision tree (GBDT) methods (Hastie et al., 2009, Chs. 10 and 15). A decision tree with a small number of nodes is often considered interpretable: its computation can be traced by following the data point from the root node to a leaf node (Molnar, 2025). This makes small decision trees a common choice in interpretable machine learning (interpretable ML).

See also: decision region, decision rule, classification, random forest, gradient-boosted decision tree, feature importance, interpretable machine learning.

References

  1. Shalev-Shwartz and Ben-David (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge Univ. Press. doi.org/10.1017/cbo9781107298019
  2. Breiman et al. (1984). Classification and Regression Trees. Wadsworth.
  3. Quinlan (1986). Induction of decision trees. Machine Learning. doi.org/10.1023/A:1022643204877
  4. Quinlan (1993). C4.5: Programs for Machine Learning. Morgan Kaufmann.
  5. Hastie et al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer Science+Business Media. doi.org/10.1007/978-0-387-84858-7
  6. Finnish Meteorological Institute (2024). The Finnish Meteorological Institute's open data. opendata.fmi.fi/wfs
  7. Molnar (2025). Interpretable Machine Learning: A Guide for Making Black Box Models Explainable. Ebook. christophm.github.io/interpretable-ml-book/

Cite this entry

@misc{dictml_decisiontree,
  author = {Jung, Alexander},
  editor = {Olioumtsevits, Konstantina and Schnoor, Ekkehard},
  title = {decision tree},
  howpublished = {Dictionary of Applied Machine Learning (course edition)},
  year = {2026},
  doi = {10.5281/zenodo.21569296},
  note = {ISBN 978-952-64-3013-3, CC BY 4.0, retrieved 2026-10-27},
  url = {https://dictionaryofml.org/terms/decisiontree.html}
}