Decision trees

Lesson 50 of 62, about 5 min

A decision tree learns a flowchart of yes/no questions from data. To predict, you start at the top, answer each question about the example, and follow the branches to a leaf that holds the answer. Trees are easy to read, need no scaling, and are the building block of random forests and gradient boosting.

What a tree looks like

output

petal length <= 2.45?
├── yes: setosa
└── no:  petal width <= 1.75?
         ├── yes: versicolor
         └── no:  virginica

Each internal node tests one feature against a threshold. Each leaf gives a class (or, for regression, a number).

How the tree is grown

The algorithm picks, at each node, the single question that best separates the classes, splits the data by the answer, and repeats on each side until the leaves are pure or a stopping rule kicks in. "Best" is measured with an impurity score.

Gini impurity

For a node with class proportions $p_1, p_2, \dots$ :

G = 1 - \sum_k p_k^2

A pure node (all one class) has $G = 0$ . A 50/50 binary node has $G = 0.5$ .

Entropy

H = -\sum_k p_k \log_2 p_k

Same idea, slightly different curve. Pure is 0; 50/50 is 1 bit.

Information gain

The quality of a split is the impurity of the parent minus the weighted impurity of the children. The tree chooses the split with the largest gain.

python

import numpy as np

def gini(labels):
    _, counts = np.unique(labels, return_counts=True)
    p = counts / counts.sum()
    return 1 - (p ** 2).sum()

def entropy(labels):
    _, counts = np.unique(labels, return_counts=True)
    p = counts / counts.sum()
    return -(p * np.log2(p)).sum()

parent = np.array([0, 0, 0, 0, 1, 1, 1, 1])
left, right = np.array([0, 0, 0, 1]), np.array([0, 1, 1, 1])
gain = gini(parent) - (len(left) * gini(left) + len(right) * gini(right)) / len(parent)
print(f"gini parent={gini(parent):.3f}  gain={gain:.3f}")
print(f"entropy parent={entropy(parent):.3f}")

With scikit-learn

python

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=3, random_state=0).fit(X_train, y_train)
print("test accuracy:", round(tree.score(X_test, y_test), 3))
print(export_text(tree, feature_names=list(iris.feature_names)))

export_text prints the learned rules. plot_tree draws them if you have matplotlib.

Controlling overfitting

An unrestricted tree keeps splitting until every leaf is pure, which means memorising the training data, noise included. Limit it:

max_depth: maximum number of questions from root to leaf.
min_samples_leaf: a leaf must contain at least this many training rows.
min_samples_split: do not split a node smaller than this.
ccp_alpha: cost complexity pruning; grow fully, then cut back branches that add little.

python

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier

X, y = load_breast_cancer(return_X_y=True)
for depth in (1, 2, 4, 8, None):
    tree = DecisionTreeClassifier(max_depth=depth, random_state=0)
    print(f"max_depth={str(depth):4s} cv accuracy={cross_val_score(tree, X, y, cv=5).mean():.3f}")

Feature importance

Trees record how much each feature reduced impurity across all its splits. This is a quick, if rough, view of what the model relies on.

python

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier

iris = load_iris()
tree = DecisionTreeClassifier(max_depth=3, random_state=0).fit(iris.data, iris.target)
for name, imp in sorted(zip(iris.feature_names, tree.feature_importances_), key=lambda t: -t[1]):
    print(f"{name:20s} {imp:.3f}")

Regression trees

Leaves hold the mean target of the training rows that reach them, and splits minimise the squared error instead of Gini.

python

import numpy as np
from sklearn.tree import DecisionTreeRegressor

X = np.arange(1, 11).reshape(-1, 1)
y = np.array([5, 6, 5, 7, 20, 22, 21, 23, 40, 41])
reg = DecisionTreeRegressor(max_depth=2).fit(X, y)
print(reg.predict([[2], [6], [9.5]]))

Strengths and weaknesses

No scaling or encoding of ordinal features needed; handles mixed feature types naturally.
Readable: you can show the rules to a domain expert.
Captures interactions and non linear boundaries automatically.
But: a single tree is unstable (a small change in data can change the whole tree) and prone to overfitting. Ensembles fix this, and are next.

Practice

Grow an unrestricted tree on the breast cancer data and compare train accuracy with cross-validated accuracy.
Print the rules of a depth 2 tree on iris and draw them by hand as a flowchart.
Change the criterion to entropy and see whether the chosen splits differ.