I5 · Machine Learning Foundations

Decision Trees

A decision tree is a model that predicts by asking a series of yes-or-no questions about the features, following a path from the root to a leaf. It learns which questions to ask by choosing, at each step, the split that best separates the classes, using measures such as Gini impurity or information gain.

12 min Intermediate · Sublevel Intermediate

What you need: The earlier topics of this module.

Definition

A decision tree is a model that predicts by asking a series of yes-or-no questions about the features, following a path from the root to a leaf. It learns which questions to ask by choosing, at each step, the split that best separates the classes, using measures such as Gini impurity or information gain.

In simple words

It's a game of 20 Questions. Is income above 50,000? If yes, is the loan under 5 lakhs? If yes, approve. Each question splits people into smaller, more similar groups. Training is just finding the best questions and the best order.

Overview

  • A decision tree predicts by asking a sequence of yes/no questions about features.
  • Internal nodes test a feature, branches are answers and leaves hold predictions.
  • Splits are chosen to make groups as pure as possible, measured by Gini impurity or entropy (classification) or variance (regression).
  • Trees need no scaling and handle mixed feature types and non-linear patterns.
  • Deep trees overfit; limits such as max_depth and min_samples_leaf, or pruning, control them.
  • Their readable rules make them popular where decisions must be explained.

Why it matters

Trees are easy to explain, work with little preparation, and handle both numbers and categories without scaling. They're also the building block of random forests and XGBoost, which are among the best methods for tabular data.

Key terms

Node and leaf
A node asks a question about a feature; a leaf gives a prediction.
Split
Dividing the data at a node by a rule such as area > 1,200.
Gini impurity
A measure of how mixed the classes are in a node; 0 means pure.
Entropy and information gain
Entropy measures uncertainty; information gain is how much a split reduces it.
Maximum depth
A limit on how many questions a path can ask, controlling complexity.
Ensemble
Combining many models, such as many trees in a random forest, for better predictions.

Types

Decision trees come in several types and algorithms, and they are controlled by a few types of setting.

1. Classification trees

Trees whose leaves predict a class.

  • How it works: Each split maximises the drop in Gini impurity or entropy; a leaf predicts the majority class of its training examples and its class proportions as probabilities.
  • Example: A tree deciding loan approval from income, credit history and existing debts.
  • When to use it: Use them for explainable classification and as building blocks of forests and boosting.

2. Regression trees

Trees whose leaves predict a number.

  • How it works: Splits minimise the squared error within groups; each leaf predicts the mean target of its examples, giving a step-shaped function.
  • Example: Predicting delivery time from distance bands, time of day and weather.
  • When to use it: Use them for non-linear numeric prediction, usually inside ensembles.

3. Tree algorithms: ID3, C4.5 and CART

Classic methods for growing trees.

  • How it works: ID3 (Quinlan, 1986) uses information gain on categorical features; C4.5 adds gain ratio, numeric features and pruning; CART (Breiman et al., 1984) makes binary splits with Gini or squared error and is what scikit-learn uses.
  • Example: scikit-learn's DecisionTreeClassifier implements an optimised version of CART.
  • When to use it: Know them to read the literature and understand why trees split the way they do.

4. Pre-pruning (growth limits)

Stopping a tree from growing too far.

  • How it works: max_depth, min_samples_split, min_samples_leaf and max_leaf_nodes stop splitting early; values are tuned by cross-validation.
  • Example: Limiting a tree to depth 4 so that its rules fit on one page for doctors to review.
  • When to use it: Use them to prevent overfitting and to keep trees readable.

5. Post-pruning (cost-complexity pruning)

Growing a full tree and then cutting back branches that do not help.

  • How it works: ccp_alpha trades tree size against training error; larger values remove more branches; the best value is chosen on validation data.
  • Example: Pruning a 40-leaf tree to 9 leaves with almost no loss in test accuracy.
  • When to use it: Use it when you want the simplest tree that performs well.

Explained in detail

How a tree chooses its questions

At each node the algorithm considers every feature and many possible thresholds, and picks the split that makes the resulting groups as pure as possible. Gini impurity for a node is 1 minus the sum of the squared class proportions. A node with 50 per cent of each class has Gini 0.5; a node with only one class has Gini 0. The algorithm picks the split that reduces the weighted impurity of the children the most, then repeats on each child. This greedy, top-down procedure is the CART algorithm, published by Leo Breiman and colleagues in 1984; the ID3 and C4.5 algorithms of Ross Quinlan use entropy instead.

Strengths and weaknesses

StrengthsWeaknesses
Easy to read and explain as a set of if-then rulesA deep tree overfits, memorising noise in the training data
No need to scale featuresUnstable: small changes in data can produce a very different tree
Handles numbers and categories, and non-linear patternsPredictions are step-like rather than smooth for regression
Shows which features matter through feature importanceBiased towards features with many possible split points

Controlling overfitting

  • max_depth limits how many questions a path can ask; depths of 3 to 10 are common starting points.
  • min_samples_leaf requires each leaf to contain enough examples, so it cannot be built around one odd case.
  • Pruning grows a large tree and then removes branches that do not improve validation performance.
  • Choose these settings by comparing validation or cross-validation scores.

Forests and boosting

A single tree is rarely the most accurate model, but combinations of trees are among the most powerful methods for tabular data. A random forest, introduced by Breiman in 2001, trains hundreds of trees, each on a random sample of rows and with a random subset of features at each split, and averages their votes; the randomness makes the trees disagree in useful ways and the average is far more stable. Gradient boosting builds trees one after another, each correcting the errors of the previous ones. Libraries such as XGBoost, LightGBM and CatBoost implement boosting very efficiently and are frequent winners of machine-learning competitions on spreadsheet-style data.

How it works

  1. Start with all the data at the root.
  2. Try every possible split of every feature.
  3. Choose the split that makes the child groups purest.
  4. Repeat on each child, until a stopping rule applies, such as a maximum depth.
  5. Each leaf predicts its majority class, or its average for regression.
AlgorithmSplit measureNote
ID3Information gainCategorical features
C4.5Gain ratioHandles numbers and missing values
CARTGini (or variance for regression)Used by scikit-learn

The maths

Gini impurity
The share of class k in this group
Entropy
Information gain

A group has 6 "yes" and 4 "no". One split gives left: 5 yes, 0 no. Right: 1 yes, 4 no.

Parent Gini = 1 − (0.6² + 0.4²) = 1 − 0.52 = 0.48
Left Gini   = 1 − (1² + 0²) = 0
Right Gini  = 1 − (0.2² + 0.8²) = 1 − 0.68 = 0.32
Weighted    = (5/10)(0) + (5/10)(0.32) = 0.16
Impurity falls from 0.48 to 0.16, so this is a good split.

In code

scikit-learn can print the learned tree as readable rules. That's the great strength of this model.

tree.py
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, export_text

iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=0)

tree = DecisionTreeClassifier(max_depth=2, random_state=0).fit(X_train, y_train)
print(export_text(tree, feature_names=list(iris.feature_names)))
print("Test accuracy:", round(tree.score(X_test, y_test), 3))

Output

|--- petal width (cm) <= 0.80
|   |--- class: 0
|--- petal width (cm) >  0.80
|   |--- petal length (cm) <= 4.95
|   |   |--- class: 1
|   |--- petal length (cm) >  4.95
|   |   |--- class: 2

Test accuracy: 0.895

Common mistakes

  • Leaving depth unlimited, which leads to overfitting.
  • Trusting one tree too much. Small data changes can produce a very different tree, so forests are more stable.
  • Scaling features for a tree. It isn't needed, because trees only compare values with thresholds.

Check yourself

Question 1

1. What is the Gini impurity of a pure group?

Question 2

2. A tree is 100% on training and 70% on test. What should you do?

Summary

  • A tree predicts through a series of yes-or-no questions.
  • It picks splits that make groups purest (Gini or entropy).
  • It's easy to read and easy to overfit, so limit its depth.

Finished reading?

Sources: scikit-learn user guide