What you’ll learn

• how a tree turns a dataset into a list of if-statements you can read aloud
• Gini impurity and entropy — the formulas, and the real difference between them
• both computed by hand on the actual iris tree, matching scikit-learn to six decimals
• how CART searches for a split, and why the result is only locally optimal
• why an unpruned tree always reaches 100% training accuracy, and every control that prevents it
• why trees are unstable, and what that instability sets up for Phase 5

Intuition

A decision tree asks a sequence of yes/no questions about one feature at a time, and each answer narrows the possibilities until only one class remains plausible. It is the only model in this phase whose reasoning you can print and hand to a domain expert:

if petal width <= 0.80:
    setosa
else:
    if petal width <= 1.75:
        versicolor
    else:
        virginica

if petal width <= 0.80:
    setosa
else:
    if petal width <= 1.75:
        versicolor
    else:
        virginica

Two questions, three answers, 96% accurate on the full iris dataset. No scaling, no distance metric, no kernel, no probability calibration — just thresholds.

The whole design problem is: which question, in which order? That is what impurity measures answer.

  flowchart TD
  A["150 samples
50 / 50 / 50
gini 0.667"] -->|"petal width ≤ 0.8"| B["50 samples
all setosa
gini 0.000"]
  A -->|"petal width > 0.8"| C["100 samples
0 / 50 / 50
gini 0.500"]
  C -->|"petal width ≤ 1.75"| D["54 samples
0 / 49 / 5
gini 0.168"]
  C -->|"petal width > 1.75"| E["46 samples
0 / 1 / 45
gini 0.043"]

The math

Measuring impurity

A node is pure if every sample in it shares a label. Impurity measures how far from that a node is. With $p_c$ the proportion of class $c$ in the node:

Both are zero for a pure node and maximal for a uniform one. Their maxima differ: for $K$ classes, Gini tops out at $1 - 1/K$ while entropy tops out at $\log_2 K$. With three classes that is 0.667 against 1.585.

figureThree impurity measures over a binary nodematplotlib

Reading the plot

• Gini and entropy agree almost everywhere. After rescaling, the two curves are close enough that they select the same split the overwhelming majority of the time. Gini is marginally faster because it avoids a logarithm; that is the entire practical difference.
• Entropy is slightly more aggressive at the extremes, so it can prefer a split that isolates a small pure group where Gini would not.
• Misclassification error is flat over wide ranges. Two candidate splits often score identically, so it gives the search nothing to descend. It is used for pruning, not for growing.

Choosing a split

CART evaluates every (feature, threshold) pair and picks the one minimising the weighted impurity of the two children:

The information gain is the parent’s impurity minus that weighted average. Split, then recurse on each child, stopping when a node is pure or a limit is reached.

Two properties follow directly:

• It is greedy. Each split is chosen to be locally best; nothing looks two moves ahead. Finding the globally optimal tree is NP-complete, so every practical tree is a good local solution.
• It is invariant to monotone transformations. Only the ordering of a feature’s values matters, never the spacing. Log-transform a feature, or standardise it, and the tree is unchanged. This is why trees never need scaling.

Worked example by hand

The iris tree above, computed from scratch.

Step 1 — root impurity. 150 samples, 50 of each class:

Step 2 — evaluate the split at petal width ≤ 0.80. The left child gets 50 setosa and nothing else; the right child gets 50 versicolor and 50 virginica:

No other threshold on either feature beats that, so CART takes it.

Step 3 — split the right child at petal width ≤ 1.75. The 100 remaining samples divide into 54 (49 versicolor, 5 virginica) and 46 (1 versicolor, 45 virginica):

Every one of these numbers is available from the fitted estimator as tree_.impuritytree_.impurity, and they agree to six decimal places.

The same tree by entropy. $H_{\text{root}} = \log_2 3 = 1.5850$, the right child is $H = 1.0000$, and the two leaves are 0.4451 and 0.1511. Different scale, identical thresholds: 0.80 and 1.75.

figureThe same tree, drawn in feature spacematplotlib

See it move

From scratch

import numpy as np
 
 
def gini(labels):
    if len(labels) == 0:
        return 0.0
    _, counts = np.unique(labels, return_counts=True)
    p = counts / counts.sum()
    return float(1 - (p**2).sum())
 
 
def entropy(labels):
    if len(labels) == 0:
        return 0.0
    _, counts = np.unique(labels, return_counts=True)
    p = counts / counts.sum()
    return float(-(p * np.log2(p)).sum())
 
 
def best_split(X, y, impurity=gini):
    """Exhaustive search over every feature and every midpoint threshold."""
    best = (None, None, impurity(y))
    m = len(y)
    for feature in range(X.shape[1]):
        values = np.unique(X[:, feature])
        thresholds = (values[:-1] + values[1:]) / 2      # midpoints
        for t in thresholds:
            mask = X[:, feature] <= t
            if mask.sum() == 0 or (~mask).sum() == 0:
                continue
            weighted = (mask.sum() * impurity(y[mask])
                        + (~mask).sum() * impurity(y[~mask])) / m
            if weighted < best[2]:
                best = (feature, float(t), weighted)
    return best
 
 
from sklearn.datasets import load_iris
 
iris = load_iris()
X = iris.data[:, (2, 3)]          # petal length, petal width
y = iris.target
 
print(f"root gini = {gini(y):.6f}")                  # root gini = 0.666667
feature, threshold, weighted = best_split(X, y)
print(f"split on feature {feature} at {threshold:.2f}")   # feature 1 at 0.80
print(f"weighted impurity = {weighted:.6f}")              # 0.333333
print(f"information gain  = {gini(y) - weighted:.6f}")    # 0.333333

import numpy as np
 
 
def gini(labels):
    if len(labels) == 0:
        return 0.0
    _, counts = np.unique(labels, return_counts=True)
    p = counts / counts.sum()
    return float(1 - (p**2).sum())
 
 
def entropy(labels):
    if len(labels) == 0:
        return 0.0
    _, counts = np.unique(labels, return_counts=True)
    p = counts / counts.sum()
    return float(-(p * np.log2(p)).sum())
 
 
def best_split(X, y, impurity=gini):
    """Exhaustive search over every feature and every midpoint threshold."""
    best = (None, None, impurity(y))
    m = len(y)
    for feature in range(X.shape[1]):
        values = np.unique(X[:, feature])
        thresholds = (values[:-1] + values[1:]) / 2      # midpoints
        for t in thresholds:
            mask = X[:, feature] <= t
            if mask.sum() == 0 or (~mask).sum() == 0:
                continue
            weighted = (mask.sum() * impurity(y[mask])
                        + (~mask).sum() * impurity(y[~mask])) / m
            if weighted < best[2]:
                best = (feature, float(t), weighted)
    return best
 
 
from sklearn.datasets import load_iris
 
iris = load_iris()
X = iris.data[:, (2, 3)]          # petal length, petal width
y = iris.target
 
print(f"root gini = {gini(y):.6f}")                  # root gini = 0.666667
feature, threshold, weighted = best_split(X, y)
print(f"split on feature {feature} at {threshold:.2f}")   # feature 1 at 0.80
print(f"weighted impurity = {weighted:.6f}")              # 0.333333
print(f"information gain  = {gini(y) - weighted:.6f}")    # 0.333333

Forty lines reproduce scikit-learn’s first split exactly, threshold included.

Trees overfit, aggressively

figuremax_depth = 1, 4 and unlimitedmatplotlib

figureWhere learning stops and memorising startsmatplotlib

An unpruned tree will always reach 100% training accuracy on data with no duplicated rows, because it can keep splitting until each leaf holds one sample. That is not a bug in the implementation; it is what “grow until pure” means. The controls that prevent it:

min_samples_leafmin_samples_leaf is the most reliable single knob: it directly forbids the “one leaf per noisy point” failure, whatever the depth.

from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier
 
iris = load_iris()
X, y = iris.data[:, (2, 3)], iris.target
 
for depth in (1, 2, 3, 5, None):
    model = DecisionTreeClassifier(max_depth=depth, random_state=0)
    train = model.fit(X, y).score(X, y)
    cv = cross_val_score(model, X, y, cv=5).mean()
    print(f"depth={str(depth):<5} leaves {model.get_n_leaves():2d}"
          f"  train {train:.4f}  cv {cv:.4f}")
 
# depth=1     leaves  2  train 0.6667  cv 0.6667
# depth=2     leaves  3  train 0.9600  cv 0.9600
# depth=3     leaves  5  train 0.9733  cv 0.9600
# depth=5     leaves  8  train 0.9933  cv 0.9533
# depth=None  leaves  8  train 0.9933  cv 0.9467

from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier
 
iris = load_iris()
X, y = iris.data[:, (2, 3)], iris.target
 
for depth in (1, 2, 3, 5, None):
    model = DecisionTreeClassifier(max_depth=depth, random_state=0)
    train = model.fit(X, y).score(X, y)
    cv = cross_val_score(model, X, y, cv=5).mean()
    print(f"depth={str(depth):<5} leaves {model.get_n_leaves():2d}"
          f"  train {train:.4f}  cv {cv:.4f}")
 
# depth=1     leaves  2  train 0.6667  cv 0.6667
# depth=2     leaves  3  train 0.9600  cv 0.9600
# depth=3     leaves  5  train 0.9733  cv 0.9600
# depth=5     leaves  8  train 0.9933  cv 0.9533
# depth=None  leaves  8  train 0.9933  cv 0.9467

Depth 2 already achieves the best cross-validated score. Everything past it buys training accuracy and loses generalisation — three extra splits to gain 0.033 on training data and lose 0.013 on held-out data.

Instability

Trees are high variance: resample the training data slightly and you can get a completely different tree. The cause is the greedy search — if two candidate splits score almost equally at the root, a handful of different rows flips which one wins, and every subsequent split changes.

This is a genuine weakness, and it is also the opening for Phase 5. If a model’s errors change substantially with the training sample, averaging many of them cancels the variance out. That single observation is what a random forest is.

Pitfalls

Compare

🧪 Try It Yourself

Exercise 1 – Compute Gini impurity

Exercise 2 – Compute the information gain

Exercise 3 – Read the tree’s own numbers

Exercise 4 – Print the rules

Exercise 5 – Find where depth stops helping

Recap

• A tree is a sequence of single-feature threshold tests, readable as plain if-statements.
• Gini is $1 - \sum p_c^2$, entropy is $-\sum p_c \log_2 p_c$; after rescaling they nearly coincide, and they almost always choose the same split.
• Hand-worked on iris: root Gini 0.6667, first split gains 0.3333, second gains 0.3897 — matching tree_.impuritytree_.impurity exactly.
• CART is greedy and only locally optimal; the globally best tree is NP-complete to find.
• Splits depend only on value ordering, so trees never need scaling.
• Unpruned trees always reach 100% training accuracy. On iris, depth 2 is the best cross-validated choice and depth 5 is already worse.
• Trees are unstable, and that instability is precisely what ensembles exploit.

Exercise 6 – Which hyperparameter actually matters?

Next

Continue to Naive Bayes Classifier — a probabilistic classifier that trains in one pass over the data and, despite an assumption that is essentially always false, remains hard to beat on text.