Skip to content
Back to search results

Decision Tree

Introduced by
Breiman, Friedman, Olshen & Stone
Year
1984
Type
Recursive partitioning (if-then rules)
Font size

What does it do?

A Decision Tree is an interpretable classification and regression method, formalised by Breiman, Friedman, Olshen and Stone in their 1984 CART framework, that partitions the data with hierarchical if-then rules.

Each split sends observations down one branch or another until a prediction is read off the leaf.

The intuition behind the method

Think of a decision tree as a flowchart of yes/no questions. Starting from all the data, the tree repeatedly asks the single question about one feature that best separates the cases — for example, 'is age above 40?' — and splits the data into two groups. It keeps splitting each group until the cases inside are reasonably homogeneous, and the final groups (the leaves) give the prediction. The chain of questions from the root to a leaf is a rule any reader can follow.

History

Decision trees were placed on a rigorous footing by Leo Breiman, Jerome Friedman, Richard Olshen and Charles Stone in their 1984 monograph Classification and Regression Trees, which introduced the CART algorithm and its use of impurity measures such as the Gini index. The transparent if-then structure made trees a staple of applied analysis, and they later became the core building block of more powerful ensembles — bagged into Random Forests and boosted in Gradient Boosting — where many trees are combined to overcome the instability of any single one.

When to use it

Use a decision tree when you want an interpretable model for classification, prediction or explanation on cross-sectional tabular data with at least about 30 observations, mixing continuous, categorical, binary and ordinal features. No feature scaling is needed and the rules are easy to communicate. Below roughly 30 cases the tree overfits readily — leaves can hold a single observation — and a simpler, more stable model such as logistic regression or naive Bayes is safer.

Limitations and considerations

  • Prone to overfitting unless pruned via max_depth or min_samples_leaf.
  • On small samples (n below about 30) the tree overfits easily, with leaves that may contain a single observation.
  • After pruning a small-sample tree may retain too few splits to be useful, where logistic regression is more stable.
  • A single tree is unstable — small data changes can produce a very different structure.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Highly interpretable: the path from root to leaf is a plain if-then rule.
  • No feature scaling required; handles continuous, categorical, binary and ordinal features directly.
  • Low difficulty — suitable even for beginner users.
  • Serves as the building block of ensembles such as Random Forest and Gradient Boosting.

Applications

  • Interpretable classification of cross-sectional tabular data.
  • Prediction and risk segmentation where transparent rules are valued.
  • Explanatory analysis to surface which features and thresholds drive an outcome.
  • A base learner inside ensembles such as Random Forest and Gradient Boosting.

How it works

How it works

1

At each node the tree searches every feature and every possible threshold for the split that most improves purity — the CART algorithm typically uses the Gini index or information gain for classification. The split that yields the largest reduction in impurity is chosen, so each branch contains cases that are more alike than before.

Formula
\Delta i = i(t) - p_L\, i(t_L) - p_R\, i(t_R)
2

The chosen split is applied and the procedure recurses on each resulting branch, partitioning the data again and again. Because no feature scaling is required, continuous, categorical, binary and ordinal features can all be used directly. Left unchecked, the tree keeps growing until leaves are almost pure — which is exactly where overfitting creeps in.

3

To control overfitting the tree is restrained — by limiting depth (max_depth), requiring a minimum number of cases per leaf (min_samples_leaf), or pruning back branches that add little. The result is a compact set of readable rules: the path from root to leaf is a transparent decision rule, which is why decision trees are well suited even to beginners.

Common pitfalls

  • Growing the tree to full depth without limiting max_depth or min_samples_leaf.
  • Trusting a single deep tree on fewer than about 30 observations.
  • Reading a fragile small-sample tree as a stable explanation of the data.
  • Reporting in-sample accuracy without a train/test split or cross-validation.

Frequently asked questions

How is a split chosen?

The CART algorithm evaluates candidate splits across all features and thresholds and picks the one that most reduces node impurity, commonly measured by the Gini index or information gain for classification.

Why does a decision tree overfit, and how do I stop it?

Left to grow freely a tree keeps splitting until leaves are nearly pure, memorising noise. Restrain it by limiting depth (max_depth), requiring a minimum number of cases per leaf (min_samples_leaf), or pruning back branches that add little.

How much data do I need?

Aim for at least about 30 observations. Below that the tree overfits easily — leaves can contain a single case — and a simpler model such as logistic regression or naive Bayes is more stable.

How does a decision tree relate to Random Forest?

A single decision tree is the building block of ensembles: Random Forest grows many trees on resampled data and combines their votes, and Gradient Boosting builds trees sequentially — both trading the single tree's transparency for greater accuracy and stability.

Related methods

Sources

  1. Breiman, L., Friedman, J.H., Olshen, R.A. & Stone, C.J. (1984). Classification and Regression Trees. Wadsworth.

    Open DOI reference
    Copied.