Which question tells you the most?
A decision tree is a model that predicts by asking a chain of yes-or-no questions about a record. Banks, hospitals and colleges use trees because every answer can be read and explained.
The hard part is choosing the questions. You will learn how a tree picks the question that sorts the data best, using entropy and information gain.
By the end of this lesson
Note
I can choose the best question to split a data set using information gain.
Key words
| Word | What it means |
|---|---|
| Decision tree | a model that predicts by asking a chain of questions |
| Split | dividing the rows by the answer to one question |
| Entropy | how mixed the labels in a group are |
| Information gain | how far a split lowers the entropy |
| Leaf | the end of a branch, holding a prediction |
The cells students fill in are left blank in this preview.
Entropy measures how mixed a group is
Suppose a tutor has the results of a weekly quiz and wants to predict pass or fail. A group where everyone passed is easy to predict. A group split half and half is hard.
Entropy puts a number on this. It is 0 for a group with one label and 1 for an even split of two labels. Between them it rises as the labels mix.
Worked example: entropy of four groups
| Group | Pass | Fail | Entropy |
|---|---|---|---|
| All pass | 4 | 0 | 0.0 |
| Mostly pass | 3 | 1 | 0.811 |
| Mostly fail | 1 | 3 | 0.811 |
| An even split | 4 | 4 | 1.0 |
The cells students fill in are left blank in this preview.
Entropy of 3 passes and 1 fail
docker exec jupyter python3 -c "import math; print(round(-0.75 * math.log2(0.75) - 0.25 * math.log2(0.25), 3))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Information gain is the entropy a split removes
A split asks one question and divides the rows into groups. Work out the entropy of each group, then average them, weighting each group by its size.
Information gain is the entropy before the split minus that weighted average. The best question is the one with the biggest gain.
Worked example: eight quiz students
| Student | Attended the class? | Revised? | Result |
|---|---|---|---|
| 1 | yes | yes | pass |
| 2 | yes | no | pass |
| 3 | yes | no | pass |
| 4 | yes | yes | fail |
| 5 | no | yes | pass |
| 6 | no | no | fail |
| 7 | no | yes | fail |
| 8 | no | no | fail |
The cells students fill in are left blank in this preview.
Work out the gain of each question
import math
# Each student is [attended, revised, result].
students = [
["yes", "yes", "pass"], ["yes", "no", "pass"], ["yes", "no", "pass"], ["yes", "yes", "fail"],
["no", "yes", "pass"], ["no", "no", "fail"], ["no", "yes", "fail"], ["no", "no", "fail"],
]
def entropy(labels):
total = 0
for label in set(labels):
share = labels.count(label) / len(labels)
total = total - share * math.log2(share)
return total
def gain(rows, column):
after = 0
for value in set([row[column] for row in rows]):
group = [row[2] for row in rows if row[column] == value]
after = after + len(group) / len(rows) * entropy(group)
return entropy([row[2] for row in rows]) - after
print("entropy of all:", round(entropy([row[2] for row in students]), 3))
print("gain from attended:", round(gain(students, 0), 3))
print("gain from revised:", round(gain(students, 1), 3))
# Add a line for a group of 4 passes: entropy(["pass"] * 4) is 0.
A tree repeats the best split
A tree builder picks the split with the best gain and divides the rows. It then repeats the same step inside each group, and stops when a group is pure, too small, or the tree is deep enough.
Each end of a branch is a leaf, and it predicts the commonest label of the rows that reached it.
A common mistake
Warning
Many people think a deeper tree is a better tree. A tree grown until every leaf is pure learns the noise as well, and does worse on new rows. Limit the depth, then check the tree on rows it has not seen.
Entropy of the lab's busy and quiet days
docker exec jupyter python3 -c "import csv, math; days = list(csv.DictReader(open('hires.csv'))); p = sum(int(d['hires']) >= 300 for d in days) / len(days); print(round(-p * math.log2(p) - (1 - p) * math.log2(1 - p), 3))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
In your notebook: grow a small tree
import pandas as pd
from sklearn.tree import DecisionTreeClassifier, export_text
hires = pd.read_csv("hires.csv")
hires["weekend"] = hires["weekday"].isin(["Sat", "Sun"]).astype(int)
X = hires[["temp_c", "rain_mm", "weekend"]]
y = hires["hires"] >= 300
tree = DecisionTreeClassifier(criterion="entropy", max_depth=2, random_state=0).fit(X, y)
print(export_text(tree, feature_names=list(X.columns)))
Going further
Run the notebook cell and read the printed tree. Which question does it ask first? Then change max_depth to 1 and to 5 and watch the tree shrink and grow.
Explain in one sentence why a first question about the weekend might beat one about rain.