Decision trees: splitting data with a sequence of yes or no questions
A decision tree is a non-parametric supervised learning model that makes predictions by routing an example through a hierarchy of conditions. Each internal node asks a question about a feature, and the answer leads to a child node until a leaf node provides the final prediction. Training selects splits that maximize the purity of the resulting subsets.
Structure and inference
A decision tree is a hierarchical model composed of a root node, internal decision nodes, and leaf nodes. Each non-leaf node holds a condition on a feature, and each leaf node holds a prediction, either a class label or a numerical value. The Google for Developers decision tree page describes this structure and explains how an example is routed from the root to a leaf.
During inference, the model evaluates the condition at each node and follows the corresponding branch. The path traversed is called the inference path, and the value in the reached leaf is the prediction. Decision trees can perform classification by predicting discrete categories or regression by predicting numerical values.
Splitting and impurity measures
Training builds the tree by splitting the data recursively. The greedy search selects the split that most improves the homogeneity of the resulting child nodes. The Cornell University lecture on decision trees states that finding the smallest consistent tree is NP-hard, so practical algorithms rely on locally optimal decisions.
Impurity functions measure how mixed the classes are in a node. Entropy, rooted in information theory, is zero when a node contains only one class and maximal when classes are evenly distributed. Information gain is the reduction in entropy after a split, and the split with the highest information gain is selected. The MLU Explain article on decision trees illustrates this process with an interactive example.
Common algorithms and splitting criteria
Several classic algorithms implement decision tree learning. The IBM What is a decision tree page identifies ID3, C4.5, and CART. ID3 uses entropy and information gain, C4.5 is a later version that can use gain ratios, and CART uses Gini impurity.
Gini impurity measures how often a randomly chosen sample would be misclassified if it were labeled randomly according to the class distribution in the node. Lower Gini values indicate purer nodes. These criteria are applied at each split to choose the best feature and threshold.
Strengths, limitations, and overfitting safeguards
Decision trees are interpretable white-box models because the decision path can be explained as boolean logic. The scikit-learn user guide on decision trees lists advantages such as handling both numerical and categorical data, requiring little data preparation, and performing well even when assumptions are somewhat violated.
The same guide also notes that trees can become over-complex and unstable. Small variations in the data can produce entirely different trees, and predictions are piecewise constant, making extrapolation difficult. Pruning, limiting tree depth, and setting minimum samples per leaf help prevent overfitting, as does combining many trees into an ensemble.
Ensemble methods such as random forests mitigate instability and improve accuracy. The Google for Developers introduction to decision forests explains that decision forests handle noisy data well and often give good results with minimal configuration.
| Algorithm | Splitting criterion | Notes |
|---|---|---|
| ID3 | Entropy and information gain | Developed by Ross Quinlan |
| C4.5 | Gain ratios | Later iteration of ID3 by Quinlan |
| CART | Gini impurity | Introduced by Leo Breiman |
Frequently asked questions
What is a decision tree?
A decision tree is a supervised learning model that predicts outcomes by applying a series of conditions on features, arranged in a tree structure. Each leaf provides the final prediction.
How does a decision tree make predictions?
An input example is passed from the root to a leaf, evaluating the condition at each node. The leaf's value or class label is the prediction.
What is information gain?
Information gain measures the reduction in entropy after a split. The split that maximizes information gain is chosen because it best separates classes.
What is overfitting in decision trees?
Overfitting occurs when a tree becomes too deep and captures noise instead of general patterns. Pruning and other constraints can reduce complexity.
What are the main splitting criteria?
Common criteria include entropy (used by ID3) and Gini impurity (used by CART). Both measure class impurity and help choose the best feature to split on.