Decision Trees

7.1What is a decision tree?

You already use decision trees without thinking about it. Deciding whether to take a coat: Is it raining? If yes, take it. If no: Is it below 10°C? And so on. Each question splits the possibilities until you reach a decision.

Banks have used this kind of logic for loan decisions for decades:

The difference in machine learning is that nobody writes these questions by hand. The algorithm looks at past data (for example, thousands of previous loans and whether they were repaid) and works out which questions to ask, in which order, and where to draw each line, such as "£30k" rather than "£25k".

7.2The parts of a tree

Data scientists draw trees upside down: the "root" is at the top and the "leaves" are at the bottom.

Every question in a standard decision tree is about one feature at a time, with a simple "above or below this number" (or "is it this category") rule.

7.3How a tree learns: finding the best question

At every node, the tree tries every feature and every possible split point, and picks the one that separates the classes best. But what does "best" mean?

The goal is to make each group as pure as possible. A pure group contains only one class, for example, only customers who left. A mixed group is "impure".

Gini impurity

The most common way to measure impurity is the Gini impurity. In plain English: if you picked a customer from the group at random and guessed their label based on the group's mix, how likely are you to be wrong?

When a split creates two groups, the tree works out a weighted average of their Gini scores (bigger groups count more). It chooses the split with the lowest weighted Gini. Try it yourself with 12 broadband customers.

Once the best first question is found, the tree repeats the same process inside each group, finding the best question for that smaller group, and so on. This is called recursive splitting. It stops when a group is pure, or when it hits a limit you've set.

Entropy: another way to measure impurity

Some trees use entropy instead of Gini. It comes from information theory, but the idea is the same: 0 means pure, and higher means more mixed. The drop in entropy after a split is called information gain. In practice, Gini and entropy give very similar trees. scikit-learn uses Gini by default; you can switch with criterion="entropy".

7.4What a tree's decision boundary looks like

Because every question is "is this one feature above or below a number?", every split is a straight line parallel to an axis. The result is that trees carve the data into rectangles.

Compare this with earlier modules: logistic regression drew one straight diagonal line, and KNN drew smooth curvy regions. Trees draw staircases of boxes. This lets them capture patterns that a single straight line can't, such as "customers with lots of calls leave, unless they've been with us for years".

7.5Overfitting and pruning

Left alone, a tree will keep asking questions until every leaf is pure. On training data, that means close to 100% accuracy. But as you learned in Module 5, a perfect training score is a warning sign. The tree has memorised the noise, as the right panel of Figure 2 shows.

In the Python example later, a tree with no limits grows 15 levels deep with 187 leaves. It scores 99.8% on training data but only 73% on test data. Classic overfitting.

The fix is to limit how much the tree can grow. This is called pruning. scikit-learn gives you several settings (hyperparameters) to do this:

7.6Regression trees

Trees can predict numbers too. The only change is what goes in the leaves: instead of a class, each leaf holds the average value of the training examples that end up there. Instead of Gini, splits are chosen to make each group's values as close together as possible (lowest squared error, like in Module 3).

This staircase shape has an important consequence: a tree can't predict beyond the values it has seen. For a 300 m² house, it would still predict about £278k, the average of its top step. Linear regression would keep the line going up. In scikit-learn, use DecisionTreeRegressor.

7.7Feature importance

A useful bonus: trees tell you which features mattered most. Every time a feature is used for a split, it reduces impurity. Add up those reductions for each feature, and you get its feature importance. The scores always add up to 1.

7.8Decision trees in Python

Let's return to the 1,000 broadband customers from Module 4 and build a churn tree. Notice one nice thing: no scaling is needed. A tree only ever asks "is this value above or below a number?", so the size of the numbers doesn't matter.

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.tree import DecisionTreeClassifier, export_text

# 1. The same 1,000 broadband customers from Module 4
rng = np.random.default_rng(7)
n = 1000
df = pd.DataFrame({
    "support_calls":    rng.poisson(3, n),
    "months":           rng.integers(1, 60, n),
    "monthly_bill":     rng.integers(20, 70, n),
    "monthly_contract": rng.integers(0, 2, n),
})
z = (-4.5 + 1.0 * df["support_calls"] - 0.08 * df["months"]
     + 0.04 * df["monthly_bill"] + 1.5 * df["monthly_contract"])
df["left"] = (rng.random(n) < 1 / (1 + np.exp(-z))).astype(int)

X = df.drop(columns="left")
y = df["left"]
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y)
# No scaling needed: trees only ask "is this value above or below a number?"

# 2. A tree with no limits grows until every leaf is pure
deep = DecisionTreeClassifier(random_state=42)
deep.fit(X_train, y_train)
print(f"No limits:  depth={deep.get_depth()}, leaves={deep.get_n_leaves()}, "
      f"train={deep.score(X_train, y_train):.3f}, test={deep.score(X_test, y_test):.3f}")

# 3. Tune max_depth and min_samples_leaf with cross-validation
grid = GridSearchCV(
    DecisionTreeClassifier(random_state=42),
    param_grid={"max_depth": [2, 3, 4, 5, 6, 8],
                "min_samples_leaf": [1, 10, 20, 40]},
    cv=5)
grid.fit(X_train, y_train)
best = grid.best_estimator_
print("Best settings:", grid.best_params_)
print(f"Tuned tree: depth={best.get_depth()}, leaves={best.get_n_leaves()}, "
      f"train={best.score(X_train, y_train):.3f}, test={best.score(X_test, y_test):.3f}")

# 4. Which features matter most?
for name, imp in sorted(zip(X.columns, best.feature_importances_), key=lambda t: -t[1]):
    print(f"{name:17} {imp:.2f}")

# 5. Print the top of the tree as readable rules
small = DecisionTreeClassifier(max_depth=2, random_state=42).fit(X_train, y_train)
print(export_text(small, feature_names=list(X.columns)))

No limits:  depth=15, leaves=187, train=0.998, test=0.730
Best settings: {'max_depth': 4, 'min_samples_leaf': 1}
Tuned tree: depth=4, leaves=16, train=0.829, test=0.790
support_calls     0.48
months            0.30
monthly_contract  0.16
monthly_bill      0.05
|--- support_calls <= 3.50
|   |--- months <= 21.50
|   |   |--- class: 0
|   |--- months >  21.50
|   |   |--- class: 0
|--- support_calls >  3.50
|   |--- months <= 31.50
|   |   |--- class: 1
|   |--- months >  31.50
|   |   |--- class: 0

What the output tells us

• The unlimited tree overfits badly: 99.8% on training data, 73% on test data, with 187 leaves. That's almost one leaf for every four customers.
• The tuned tree is much healthier: just 4 levels and 16 leaves, 82.9% on training and 79% on test. The small gap between the two means it has learned general rules, not memorised the data.
• Feature importance matches what we built into the data: support calls and months with us matter most.
• The printed rules are the tree itself, in plain text. The first question is "support calls ≤ 3.5?". Customers with 4 or more calls and fewer than 32 months with us are predicted to leave. You could paste these rules into an email to a manager.
• Notice that on the left side, both leaves say "class 0" (stay). That split still made the groups purer, just not enough to change the final answer. With deeper trees, those groups would be split further.

7.9Strengths, weaknesses and real-world uses

The biggest impact of decision trees, though, is as a building block. The Random Forest and Gradient Boosting models in Module 8, which win a huge share of real-world machine learning projects on table-shaped data, are made entirely of decision trees.

SummaryKey takeaways

Check your understanding

Your machine learning roadmap

1. 01
   Introduction to Machine LearningWhat ML is and how it works
2. 02
   Preparing Data for Machine LearningFeatures, encoding, scaling, train/test split
3. 03
   Linear RegressionPredicting numbers
4. 04
   Logistic RegressionPredicting yes or no
5. 05
   Evaluating ModelsAccuracy, precision, recall, overfitting, cross-validation
6. 06
   K-Nearest NeighboursLearning from similar examples
7. 07
   Decision TreesYou are here
8. 08
   Random Forest and Gradient BoostingMany models working together
9. 09
   Support Vector MachinesFinding the best boundary
10. 10
    Naive BayesProbability-based classification
11. 11
    Clustering with K-MeansFinding groups without labels
12. 12
    Dimensionality Reduction with PCASimplifying big datasets
13. 13
    Capstone ProjectBuild and present a full ML project