Decision trees
Decision trees learn a sequence of if-then splits on features to make predictions. Learn how splits are chosen, how to prevent overfitting and why they power ensembles.
Overview
A decision tree makes a prediction by asking a series of simple questions about an example. Is the contract monthly? Is income above 50,000? Has the customer called support more than twice? Each answer sends the example down one branch, and the next question depends on the previous answer. At the end of the path is a leaf, which holds the prediction: a class with its probability, or a number.
The questions are not written by hand. A learning algorithm looks at the training data and, at each step, picks the question that best separates the examples. It keeps splitting until the groups are pure enough or a stopping rule is reached. The result can be drawn as a flowchart that a person can read and check.
An everyday picture is the troubleshooting script a support agent follows: "Is the light on? If not, is the cable plugged in?" A decision tree is that script, except the computer writes it by finding the most useful questions in past cases.
What it is
| Part | What it means |
|---|---|
| Root node | The first question, applied to all examples |
| Internal node | A question on one feature, such as "age ≤ 35" |
| Branch | One outcome of a question |
| Leaf | An end point that gives the prediction |
| Depth | The number of questions on the longest path |
| Split criterion | The measure used to choose questions, such as Gini impurity or entropy |
| Pruning | Removing branches that do not generalise |
There are two main kinds. Classification trees predict a class and store class proportions in each leaf. Regression trees predict a number and store the average target value of the training examples in each leaf. Both are built the same way; only the split criterion differs.
Trees matter well beyond their own use. They are the building blocks of the two most successful families of tabular models: random forests, which average many trees, and gradient boosting, which adds trees one after another.
Where it came from
Tree-based learning has a clear lineage. AID, by Morgan and Sonquist in 1963, was the first regression tree algorithm, splitting survey data recursively. THAID, by Messenger and Mandell in 1972, brought the idea to classification. CHAID, by Kass in 1980, used statistical significance tests to choose splits.
The landmark was CART (Classification and Regression Trees), published in 1984 by Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone. CART added cost-complexity pruning, cross-validation to choose tree size and surrogate splits for missing values, and it is the basis of many modern implementations. In parallel, Ross Quinlan developed ID3 in 1986, using an entropy-based criterion from information theory, and its successor C4.5 in 1993, which added better pruning and handling of missing values.
In the 1990s and 2000s it became clear that single trees are unstable, but that combining many of them is extremely powerful. Bagging, random forests and gradient boosting followed, and they remain standard tools for tabular data today.
How it works
Step 1: consider every possible split
At a node, the algorithm looks at each feature. For a numeric feature it tries thresholds between sorted values; for a categorical feature it tries groupings of categories.
Step 2: score each split
For classification the usual score is Gini impurity, which is the chance that two randomly drawn examples from a node belong to different classes, or entropy, which measures uncertainty in bits. The best split gives the largest drop in impurity, weighted by the size of each child. For regression the score is usually the drop in squared error.
Step 3: split and repeat
The data are divided by the best question and the same procedure runs on each child. This is called recursive partitioning, and it is greedy: each choice is the best one locally, with no look-ahead.
Step 4: stop
Growth stops when a node is pure, when it is too small to split, when a maximum depth is reached, or when no split improves the score enough. In scikit-learn these controls are parameters such as max_depth, min_samples_leaf and min_impurity_decrease.
Step 5: prune
A fully grown tree memorises noise. Cost-complexity pruning, from CART, trades tree size against training error with a penalty parameter, usually chosen by cross-validation. Simpler stopping rules, such as a minimum leaf size, act as pre-pruning.
Step 6: predict
A new example is dropped down from the root, following the answers, until it reaches a leaf. The leaf's value is the prediction.
Key concepts and terms
| Term | Meaning |
|---|---|
| Gini impurity | Probability of misclassifying a random example if labelled by the node's class mix |
| Entropy | A measure of uncertainty in a node's class distribution |
| Information gain | Reduction in entropy produced by a split |
| Recursive partitioning | Splitting the data, then splitting each part again |
| Greedy search | Choosing the best split at each step without planning ahead |
| Max depth | The limit on how many questions can be chained |
| Minimum leaf size | The smallest number of examples allowed in a leaf |
| Cost-complexity pruning | Removing branches using a size penalty |
| Surrogate split | A backup question used when the main feature is missing |
| Feature importance | Total impurity reduction attributed to a feature |
| Overfitting | Learning noise that does not repeat in new data |
A worked example
This scenario is illustrative. A telecom team wants simple rules for which customers are at high risk of leaving. It has 10,000 customers, 20 per cent of whom left. The team trains a classification tree with max_depth 3 and min_samples_leaf 200.
The root split is "contract is monthly". Among monthly customers the next split is "tenure ≤ 6 months", and for those the third split is "support calls ≥ 3". The highest-risk leaf, monthly customers in their first six months with three or more support calls, has 620 customers, and 58 per cent of them left. The lowest-risk leaf, annual customers with tenure over 24 months, has a churn rate of 4 per cent.
On a held-out set the tree reaches ROC AUC 0.76. A gradient boosting model reaches 0.84, but the tree's three rules fit on one slide, and the retention team adopts them as a first targeting policy while the boosted model is evaluated.
Strengths and limitations
Strengths:
- Easy to read, draw and explain when shallow.
- Handles numeric and categorical features without scaling.
- Captures non-linear effects and interactions automatically.
- Fast to train and very fast to predict.
- The basis for powerful ensembles.
Limitations:
- Single deep trees overfit badly.
- Unstable: a small change in data can produce a very different tree.
- Predictions are step functions, so they cannot extrapolate smooth trends.
- Greedy splitting can miss better overall structures.
- Impurity-based feature importance can favour features with many distinct values.
How it compares with alternatives
| Method | Accuracy on tabular data | Interpretability | Stability |
|---|---|---|---|
| Single decision tree | Moderate | High when shallow | Low |
| Random forest | High | Medium | High |
| Gradient boosting | Very high | Medium | High with tuning |
| Logistic regression | Moderate | High | High |
| k-nearest neighbors | Moderate | Low | Medium |
Practical guidance and best practices
- Limit depth and leaf size from the start; do not grow trees fully unless they are part of an ensemble.
- Choose depth or pruning strength with cross-validation.
- Use a shallow tree to communicate rules and an ensemble for accuracy.
- Check feature importance with permutation importance or SHAP, not only impurity importance.
- Use class weights or balanced leaf sizes when classes are imbalanced.
- Inspect the largest leaves to make sure the rules make domain sense.
- Keep the training data and the tree version together so rules can be audited later.
Common mistakes
- Training an unconstrained tree and celebrating near-perfect training accuracy.
- Reading a single tree's structure as stable truth; retrain on a different sample and it may change.
- Using a tree to forecast values beyond the range seen in training.
- Including identifiers or leaked post-outcome fields, which trees exploit eagerly.
- Treating impurity importance as a causal ranking of drivers.
Frequently asked questions
Do decision trees need feature scaling?
No. Splits compare a feature with a threshold, so multiplying a feature by a constant does not change which split is best. This is one reason trees are convenient for messy tabular data.
Gini or entropy: which should I use?
In practice they usually give very similar trees. Gini is slightly cheaper to compute and is the scikit-learn default. Choose by cross-validation if you care, but the depth and leaf-size settings matter far more.
How do trees handle missing values?
It depends on the implementation. CART introduced surrogate splits, C4.5 distributes examples with missing values across branches, and some modern libraries learn a default direction for missing values at each split. Recent scikit-learn versions support missing values in some tree estimators, but check your version's documentation.
Why are trees unstable?
Because each split depends on the ones above it. If a small change in data alters the root split, the whole tree below it changes. Ensembles fix this by averaging many trees, which is why random forests and boosting are more reliable.
When is a single tree the right choice?
When people must understand and trust the rules, when data are small, or when the model must be implemented as a simple policy. If accuracy is the main goal, an ensemble almost always does better.
Glossary
- Node: a point in the tree where a question is asked.
- Leaf: a terminal node that outputs a prediction.
- Split: a question that divides examples into groups.
- Impurity: how mixed the classes are in a node.
- Pruning: cutting back branches to reduce overfitting.
- CART: the 1984 Classification and Regression Trees method.
- ID3 and C4.5: Quinlan's entropy-based tree algorithms.
- Ensemble: a model made of many trees combined.
Summary
A decision tree learns a flowchart of if-then questions that split data into increasingly pure groups, with leaves that give class probabilities or numbers. The method grew from AID in 1963 through CART in 1984 and Quinlan's ID3 and C4.5. Trees are readable, need no scaling and capture interactions, but single trees overfit and are unstable. Keep them shallow for explanation, prune with cross-validation, and use random forests or gradient boosting when accuracy matters most.
Related
It belongs to ML foundations in my stack, under Machine learning. Others in the same group: