Decision Trees

Remember the game twenty questions? Is it alive? Is it bigger than a cat? Each answer cuts the possibilities down. A decision tree plays that game with your data. It is the model that you could draw on a napkin, and explain to anyone, and it is the foundation of the most powerful models for tables of data.

• Like twenty questions
• You could draw it on a napkin
• The foundation of the champions

Slicing the space

Watch how a tree thinks. It looks at all the data, and asks, which single question best separates the classes? Here, is the age above fifty? That cuts the plane in two, with a straight line. Then each side asks its own question, and cuts again. Slice by slice, the space breaks into boxes, and each box gets its own answer. On the right, you can see the same thing as a tree. To predict, a new example simply follows the path from the top, down to a leaf.

A tree for house prices

Here is a small tree for California prices, with a maximum depth of two. Export text prints the rules in plain language. Look at this. The first question is about med inc. The tree found by itself that income matters most. Each leaf gives a predicted price. A loan officer, a doctor, or a judge can read this. Very few models can say that. But the score is modest, because two questions are not enough.

from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor, export_text

data = fetch_california_housing()
X_tr, X_te, y_tr, y_te = train_test_split(
    data.data, data.target, random_state=0)

tree = DecisionTreeRegressor(max_depth=2, random_state=0).fit(X_tr, y_tr)

print(export_text(tree, feature_names=data.feature_names))
print("Test R2:", round(tree.score(X_te, y_te), 3))

|--- MedInc <= 5.03
|   |--- MedInc <= 3.07
|   |   |--- value: [1.35]
|   |--- MedInc >  3.07
|   |   |--- value: [2.09]
|--- MedInc >  5.03
|   |--- MedInc <= 6.82
|   |   |--- value: [2.92]
|   |--- MedInc >  6.82
|   |   |--- value: [4.22]

Test R2: 0.429

Pure and impure

How does the tree choose the best question? It measures impurity. Gini impurity is zero when a group is pure, all one class, and at its highest when it is a perfect mix. Here is a fully mixed group, with a gini of point five. A perfect split makes two pure groups, each with a gini of zero. The tree simply tries many possible questions, and picks the one that lowers impurity the most. For regression, it uses variance instead.

import numpy as np

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

mixed = [0, 0, 0, 1, 1, 1]
left, right = [0, 0, 0], [1, 1, 1]

print("Before the split:", round(gini(mixed), 3))
print("Left side:       ", round(gini(left), 3))
print("Right side:      ", round(gini(right), 3))

Before the split: 0.5
Left side:        0.0
Right side:       0.0

The memorising tree

Now the danger. What if we let the tree keep asking? We try increasing depths. Run it. With no limit, the tree has around fifteen thousand leaves, close to one for each house. The training score is a perfect one. And the test score? It has fallen well below the medium tree. It has memorised everything. Controlling depth, or the smallest size of a leaf, is how we regularise a tree.

from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor

X, y = fetch_california_housing(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, random_state=0)

for depth in [2, 5, 8, 12, None]:
    t = DecisionTreeRegressor(max_depth=depth, random_state=0).fit(X_tr, y_tr)
    print(f"depth {str(depth):<5} leaves {t.get_n_leaves():>6}"
          f"  train {t.score(X_tr, y_tr):.3f}  test {t.score(X_te, y_te):.3f}")

depth 2     leaves      4  train 0.453  test 0.429
depth 5     leaves     32  train 0.639  test 0.592
depth 8     leaves    242  train 0.758  test 0.668
depth 12    leaves   1953  train 0.902  test 0.660
depth None  leaves  14863  train 1.000  test 0.579

Summary