Decision Trees Explained

What you will learn in this lesson:

• How a decision tree splits data step by step, choosing the best question at each branch
• What Gini impurity and entropy measure, and how information gain drives each split
• Why deep trees overfit, demonstrated directly in code
• How max_depth, min_samples_leaf, and pruning control complexity
• How to fit a decision tree with scikit-learn and read its feature importances

Asking the Best Question at Each Step

A decision tree makes predictions by asking a sequence of simple yes/no questions about your features, branching down a tree-like structure until it reaches a final answer. Imagine playing a game of twenty questions to guess whether a customer will churn: "Has their monthly spend dropped in the last 3 months?" If yes, "Have they contacted support more than twice this month?" And so on, each answer narrows down the group of similar customers until you're confident enough to make a prediction.

The structure that results, a root question, a branch for each possible answer, and further questions nested inside each branch, is exactly what a decision tree looks like once it's trained.

The key question is: out of all possible yes/no questions you could ask about your features (is age over 30? is income over $50,000? did spend drop by more than 10%?), which one should you ask first? A decision tree algorithm answers this by trying many candidate splits, for every feature, at many possible threshold values, and picking whichever one does the best job of separating the data into groups that are as "pure" as possible, meaning each resulting group is dominated by a single class.

It then repeats this process recursively within each resulting group, asking the next best question, and the next, until some stopping condition is reached. This greedy, recursive process is called recursive binary splitting.

Measuring "Purity": Gini Impurity and Entropy

To decide which question is "best," the algorithm needs a way to measure how mixed or pure a group of data points is. Two common measures are used:

Gini impurity roughly measures the probability that two randomly chosen points from a group would have different class labels. For a group with class proportions p₁, p₂, ..., pₖ, Gini impurity is 1 - Σ pᵢ². A group containing only one class has a Gini impurity of 0 (perfectly pure, any two points you pick are guaranteed to match). A group that's perfectly split 50/50 between two classes has Gini impurity of 0.5, the maximum possible for a two-class problem.

Entropy, borrowed from information theory, measures the amount of "surprise" or uncertainty in a group: -Σ pᵢ log₂(pᵢ). A pure group (all one class) has zero entropy, there's no uncertainty about what class a random member belongs to. A perfectly mixed two-class group has entropy of 1 (its maximum). Both Gini impurity and entropy behave very similarly in practice and tend to produce similar trees; Gini is slightly faster to compute (no logarithms) and is the default in many libraries, including scikit-learn.

A Worked Gini Calculation

Suppose you have 10 customers, 6 who stayed and 4 who churned. Before any split, the Gini impurity of this whole group is:

Gini = 1 − (0.6² + 0.4²) = 1 − (0.36 + 0.16) = 0.48

Now consider a candidate split on "more than 2 support contacts last month." It divides the 10 customers into two groups:

The split's overall impurity is the weighted average of the two groups, weighted by how many customers land in each: (7/10) × 0.245 + (3/10) × 0 ≈ 0.171. The impurity dropped from 0.48 to 0.171, a reduction of about 0.31. That reduction is exactly what the tree algorithm is comparing across every candidate split, at every threshold, for every feature, before picking whichever one reduces impurity the most.

At each step, the tree algorithm evaluates how much a candidate split would reduce impurity, weighted by how the data is divided between the two resulting branches (this reduction is called information gain when using entropy), and picks the split that achieves the largest reduction.

This process repeats at every branch, the tree is essentially being greedy, choosing the locally best question at each step rather than planning the whole tree's structure in advance, which means a decision tree is not guaranteed to find the globally optimal tree, only a good one built one locally-best decision at a time.

Why Deep Trees Overfit

If left unconstrained, a decision tree can keep splitting until every single leaf contains just one training example, achieving zero impurity, and therefore zero error, on the training data. This sounds great until you realize the tree has essentially memorized the training set rather than learning a generalizable pattern.

Each split made deep into the tree is often based on a tiny handful of data points, capturing noise and quirks specific to that sample rather than a real underlying signal. This is a textbook case of high variance: a slightly different training sample would produce a substantially different deep tree, even if drawn from the exact same underlying distribution.

The fix is to constrain the tree's growth. The most common parameter is max_depth, which caps how many questions deep the tree is allowed to go. Other useful constraints include min_samples_leaf (don't create a leaf with fewer than this many training examples) and min_samples_split (don't even consider splitting a group smaller than this). These are all forms of restricting the tree's complexity upfront, sometimes called pre-pruning.

An alternative strategy is post-pruning: grow the full, deep tree first, then go back and remove branches that don't meaningfully improve validation performance (scikit-learn's ccp_alpha parameter implements one form of this, called cost-complexity pruning). Either way, the goal is the same: trade a little bit of training accuracy for a model that generalizes much better to new data, the bias-variance tradeoff in action once again.

Watching Overfitting Happen in Code

The clearest way to see the depth-overfitting relationship is to train trees of increasing depth on the same data and watch train accuracy and test accuracy diverge:

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

np.random.seed(0)

# A moderately noisy synthetic dataset, 8 features, only 3 actually matter
n = 400
X = np.random.randn(n, 8)
y = ((X[:, 0] + 0.5 * X[:, 1] - X[:, 2] + np.random.randn(n) * 0.7) > 0).astype(int)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

print("max_depth | train_acc | test_acc")
for depth in [1, 2, 3, 4, 5, 8, None]:
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
    tree.fit(X_train, y_train)
    train_acc = tree.score(X_train, y_train)
    test_acc = tree.score(X_test, y_test)
    print("{!s:>9} | {:.3f}     | {:.3f}".format(depth, train_acc, test_acc))

Run this and watch the pattern: as max_depth grows (and especially once it's None, unlimited), train accuracy climbs steadily toward 1.0, while test accuracy typically peaks somewhere in the middle of the range and then flattens out or even drops slightly. That growing gap between train and test accuracy at high depth is the classic, visible signature of overfitting. Try changing the noise level in the synthetic data (the 0.7 multiplier) to see how a noisier dataset makes the overfitting at high depth even more dramatic.

Fitting a Decision Tree and Reading Feature Importances

Beyond predictions, a fitted tree also tells you which features it actually relied on, via feature_importances_, computed from how much each feature's splits reduced impurity across the whole tree, weighted by how many samples passed through each split:

import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

# Features: [monthly_spend_change_pct, support_contacts_last_month]
X = np.array([
    [-15, 3], [5, 0], [-20, 4], [2, 1], [-30, 5],
    [10, 0], [-5, 1], [-25, 3], [8, 0], [-18, 2],
])
y = np.array([1, 0, 1, 0, 1, 0, 0, 1, 0, 1])  # 1 = churned, 0 = stayed

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=0)

# Shallow tree to control overfitting
tree = DecisionTreeClassifier(max_depth=3, min_samples_leaf=1, random_state=0)
tree.fit(X_train, y_train)

print("Train accuracy:", tree.score(X_train, y_train))
print("Test accuracy:", tree.score(X_test, y_test))
print("Feature importances:", tree.feature_importances_)

Try removing max_depth=3 entirely and re-running this on a larger, noisier dataset, you'll typically see training accuracy climb toward 100% while test accuracy stagnates or drops, the same overfitting signature demonstrated more rigorously in the previous section. Decision trees are also the fundamental building block for the ensemble methods, random forests and gradient boosting, covered in the next two lessons, where many trees are combined to overcome the weaknesses of any single tree.