Practical 3: Decision Tree Learning

rows      : 14
play = Yes: 9
play = No : 5
entropy of the whole set: 0.9403 bits

feature        values  remaining       gain
outlook             3     0.6935     0.2467
temperature         3     0.9111     0.0292
humidity            2     0.7885     0.1518
windy               2     0.8922     0.0481

root of the tree: outlook

  Overcast   4 rows  Yes 4  No 0  entropy 0.0000
  Rainy      5 rows  Yes 3  No 2  entropy 0.9710
  Sunny      5 rows  Yes 2  No 3  entropy 0.9710

outlook wins by a distance: it removes 0.2467 bits of uncertainty against humidity's 0.1518, and temperature removes almost nothing. So outlook is the root of the tree.

Look at the three groups it makes. Overcast is pure: four days, all Yes, entropy exactly 0. That branch is finished before it starts, and the tree will never ask another question about an overcast day. Rainy and Sunny both come out at 0.9710 bits, so both need another question.

Step 2: the whole algorithm

"""Practical 3: Decision Tree Learning (ID3) written from nothing."""
import csv
import math
from collections import Counter

TARGET = "play"

def entropy(rows):
    counts = Counter(r[TARGET] for r in rows)
    total = len(rows)
    return -sum((n / total) * math.log2(n / total) for n in counts.values())

def split_on(rows, feature):
    groups = {}
    for r in rows:
        groups.setdefault(r[feature], []).append(r)
    return groups

def gain(rows, feature):
    total = len(rows)
    after = sum(len(g) / total * entropy(g) for g in split_on(rows, feature).values())
    return entropy(rows) - after

def majority(rows):
    return Counter(r[TARGET] for r in rows).most_common(1)[0][0]

def id3(rows, features, values_of, depth=0, max_depth=None):
    labels = set(r[TARGET] for r in rows)
    if len(labels) == 1:                    # pure: nothing left to ask
        return labels.pop()
    if not features or (max_depth is not None and depth >= max_depth):
        return majority(rows)               # out of questions: vote
    best = max(features, key=lambda f: gain(rows, f))
    node = {"feature": best, "default": majority(rows), "branches": {}}
    rest = [f for f in features if f != best]
    groups = split_on(rows, best)
    for value in values_of[best]:
        group = groups.get(value)
        if not group:                       # a value no row here has
            node["branches"][value] = majority(rows)
        else:
            node["branches"][value] = id3(group, rest, values_of, depth + 1, max_depth)
    return node

def show(node, indent="", label=None):
    if not isinstance(node, dict):
        print("%s%s-> %s" % (indent, (label + " ") if label else "", node))
        return
    if label:
        print("%s%s" % (indent, label))
        indent += "    "
    print("%s[%s?]" % (indent, node["feature"]))
    for value, child in node["branches"].items():
        show(child, indent + "    ", "%s = %s" % (node["feature"], value))

def rules(node, sofar=()):
    if not isinstance(node, dict):
        return [(list(sofar), node)]
    out = []
    for value, child in node["branches"].items():
        out += rules(child, sofar + ("%s = %s" % (node["feature"], value),))
    return out

def classify(node, row):
    while isinstance(node, dict):
        node = node["branches"].get(row[node["feature"]], node["default"])
    return node

with open("weather.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
FEATURES = ["outlook", "temperature", "humidity", "windy"]
values_of = {f: sorted(set(r[f] for r in rows)) for f in FEATURES}

tree = id3(rows, FEATURES, values_of)
print("the tree")
show(tree)
print()
print("as rules")
for conditions, answer in rules(tree):
    print("  IF %s THEN play = %s" % (" AND ".join(conditions), answer))
print()
right = sum(1 for r in rows if classify(tree, r) == r[TARGET])
print("on the 14 rows it learned from : %d of %d right" % (right, len(rows)))

TEST = [
    {"outlook": "Sunny", "temperature": "Cool", "humidity": "High", "windy": "Yes", "play": "No"},
    {"outlook": "Overcast", "temperature": "Mild", "humidity": "Normal", "windy": "Yes", "play": "Yes"},
    {"outlook": "Rainy", "temperature": "Hot", "humidity": "Normal", "windy": "No", "play": "Yes"},
    {"outlook": "Rainy", "temperature": "Cool", "humidity": "High", "windy": "Yes", "play": "No"},
    {"outlook": "Sunny", "temperature": "Hot", "humidity": "Normal", "windy": "No", "play": "Yes"},
]
print()
print("%-9s %-5s %-7s %-6s %-9s %s" % ("outlook", "temp", "humidity", "windy", "predicted", "actual"))
right = 0
for r in TEST:
    p = classify(tree, r)
    right += (p == r[TARGET])
    print("%-9s %-5s %-7s %-6s %-9s %s"
          % (r["outlook"], r["temperature"], r["humidity"], r["windy"], p, r[TARGET]))
print()
print("on 5 unseen rows              : %d of %d right, accuracy %.3f"
      % (right, len(TEST), right / len(TEST)))

Three questions, five leaves, and every one of the fourteen training days classified correctly. temperature never appears: on this data it carries almost no information, and the algorithm dropped it without being told to. That is worth a sentence in the journal, because "which features did the tree not need?" is a question an examiner asks.

Two details in id3 that a marker looks for:

values_of, not the values present in this group. Rainy days in this dataset are never Hot, so if the tree ever asked about temperature under Rainy, there would be no Hot branch, and a new Hot rainy day would fall off the tree. Building a branch for every value the whole dataset has, and putting the group's majority answer there, is what stops that.

default. Even with every value covered, a row can arrive with a value nobody has ever seen. classify falls back to the node's majority rather than raising an error, which is what a model has to do in an examination hall when the examiner types something unexpected.

Step 3: drawing the tree

MU says "visualize and interpret the generated decision tree". The text form above is a drawing; here is the same tree as a picture, and this is what goes in the journal.

Figure 6.1 The tree ID3 built. Overcast needs no second question because all four overcast days ended the same way.

Reading it out loud is the interpretation, and it is the part of this practical that carries marks:

• Overcast means play, always. Four days out of four, no exceptions in the data.
• On a rainy day the wind decides. Calm, play; windy, do not.
• On a sunny day the humidity decides. High, do not play; normal, play.
• Temperature never came up. It was available and the algorithm found it worthless.

That is what a decision tree gives you and a neural network does not: an answer you can read, argue with, and hand to somebody who has never heard of machine learning.

Step 4: measuring it properly

The output above says 14 of 14 on the rows it learned from, and chapter 3 says that figure is worth nothing. So split the fourteen days the way chapter 3 requires and measure on the ones held back.

"""The same tree, but measured the way chapter 30 requires: on rows it never saw."""
import csv, math, random
from collections import Counter
TARGET = "play"
FEATURES = ["outlook", "temperature", "humidity", "windy"]

def entropy(rows):
    c = Counter(r[TARGET] for r in rows); n = len(rows)
    return -sum((v/n) * math.log2(v/n) for v in c.values())
def split_on(rows, f):
    g = {}
    for r in rows: g.setdefault(r[f], []).append(r)
    return g
def gain(rows, f):
    n = len(rows)
    return entropy(rows) - sum(len(x)/n * entropy(x) for x in split_on(rows, f).values())
def majority(rows): return Counter(r[TARGET] for r in rows).most_common(1)[0][0]
def id3(rows, feats, values_of, depth=0, max_depth=None):
    labels = set(r[TARGET] for r in rows)
    if len(labels) == 1: return labels.pop()
    if not feats or (max_depth is not None and depth >= max_depth): return majority(rows)
    best = max(feats, key=lambda f: gain(rows, f))
    node = {"feature": best, "default": majority(rows), "branches": {}}
    rest = [f for f in feats if f != best]
    groups = split_on(rows, best)
    for v in values_of[best]:
        node["branches"][v] = (id3(groups[v], rest, values_of, depth+1, max_depth)
                               if groups.get(v) else majority(rows))
    return node
def classify(node, row):
    while isinstance(node, dict):
        node = node["branches"].get(row[node["feature"]], node["default"])
    return node
def leaves(node):
    if not isinstance(node, dict): return 1
    return sum(leaves(c) for c in node["branches"].values())
def depth_of(node):
    if not isinstance(node, dict): return 0
    return 1 + max(depth_of(c) for c in node["branches"].values())

with open("weather.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
values_of = {f: sorted(set(r[f] for r in rows)) for f in FEATURES}
random.seed(3)
order = list(range(len(rows))); random.shuffle(order)
train = [rows[i] for i in order[:10]]
test = [rows[i] for i in order[10:]]
print("training rows:", len(train), " test rows:", len(test))
print()
print("%-11s %6s %7s %10s %9s" % ("max depth", "leaves", "depth", "train acc", "test acc"))
for md in (1, 2, 3, None):
    t = id3(train, FEATURES, values_of, max_depth=md)
    tr = sum(1 for r in train if classify(t, r) == r[TARGET]) / len(train)
    te = sum(1 for r in test if classify(t, r) == r[TARGET]) / len(test)
    print("%-11s %6d %7d %10.3f %9.3f"
          % ("unlimited" if md is None else md, leaves(t), depth_of(t), tr, te))

training rows: 10  test rows: 4

max depth   leaves   depth  train acc  test acc
1                3       1      0.800     0.250
2                5       2      1.000     1.000
3                5       2      1.000     1.000
unlimited        5       2      1.000     1.000

Two useful things and one warning.

Depth 1 is not enough. A tree allowed only the root question scores 0.800 on the rows it learned from and 0.250 on the four it did not. It is underfitting: too simple to capture what is there.

Depth 2 is enough on this data, and growing further changes nothing: the unlimited tree has the same five leaves as the depth-2 tree, because the data runs out of disagreement before the algorithm runs out of questions.

The warning: four test rows. One row is 0.25 of the accuracy. A score of 1.000 on four rows is not proof of anything, and neither is 0.250. Say the size of the test set next to the score, always. The next section uses a larger one for exactly this reason.

Step 5: where a tree goes wrong, on data that has exceptions in it

The weather dataset has no contradictions in it: no two days agree on all four features and disagree on the answer. A tree grown on data like that cannot overfit, because there is nothing false to learn.

Real data is not like that. The thirty-student dataset from chapter 3 has two students who break the pattern: one with high attendance who failed and one with low attendance who passed. Watch what a tree does when it is allowed to grow far enough to memorise them.

name,attendance,practice,result
Aarav,50,22,Fail
Isha,48,16,Fail
Rohan,88,38,Pass
Sanya,97,39,Pass
Vikram,90,30,Fail
Meera,35,41,Fail
Farhan,45,9,Fail
Nikita,71,8,Fail
Omkar,92,2,Fail
Pooja,97,45,Pass
Rahul,75,15,Fail
Sneha,85,18,Pass
Tejas,79,24,Pass
Urmila,83,34,Pass
Varun,44,23,Fail
Yash,46,37,Pass
Zoya,72,20,Fail
Amit,44,9,Pass
Bhavna,74,3,Fail
Chirag,82,25,Pass
Deepa,94,29,Pass
Eshan,46,27,Fail
Gauri,98,9,Fail
Harsh,89,34,Pass
Ira,97,27,Pass
Jatin,68,28,Pass
Kavya,96,34,Pass
Lalit,38,38,Fail
Manav,63,10,Fail
Neha,41,35,Fail

"""Overfitting needs a dataset with exceptions in it. students.csv has two."""
import csv
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split

with open("students.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
X = [[int(r["attendance"]), int(r["practice"])] for r in rows]
y = [r["result"] for r in rows]
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.3, random_state=1, stratify=y)

print("training rows:", len(Xtr), " test rows:", len(Xte))
print()
print("%-11s %7s %7s %10s %9s" % ("max depth", "leaves", "depth", "train acc", "test acc"))
for md in (1, 2, 3, 4, 5, None):
    t = DecisionTreeClassifier(criterion="entropy", max_depth=md, random_state=0).fit(Xtr, ytr)
    print("%-11s %7d %7d %10.3f %9.3f"
          % ("unlimited" if md is None else md, t.get_n_leaves(), t.get_depth(),
             t.score(Xtr, ytr), t.score(Xte, yte)))

training rows: 21  test rows: 9

max depth    leaves   depth  train acc  test acc
1                 2       1      0.762     0.889
2                 4       2      0.810     1.000
3                 6       3      0.905     0.889
4                 8       4      1.000     0.778
5                 8       4      1.000     0.778
unlimited         8       4      1.000     0.778

That is overfitting, measured. Read the two right-hand columns together:

Training accuracy climbs all the way to a perfect 1.000 and never falls. Test accuracy peaks at depth 2 and then drops, to 0.778. The deep tree has grown extra leaves whose only job is to memorise the two students who break the pattern, and those leaves are wrong about everybody else.

The tree that scored perfectly is the worst tree on the page. A student who reports only the training accuracy will report 1.000 and will have measured nothing.

The cure is to stop growing: max_depth, or a minimum number of rows in a leaf, or growing the tree fully and then cutting branches back, which is called pruning. On this data max_depth=2 is the answer, and it was found by measuring rather than by choosing.

Step 6: the same tree from scikit-learn

outlook,temperature,humidity,windy,play
Sunny,Hot,High,No,No
Sunny,Hot,High,Yes,No
Overcast,Hot,High,No,Yes
Rainy,Mild,High,No,Yes
Rainy,Cool,Normal,No,Yes
Rainy,Cool,Normal,Yes,No
Overcast,Cool,Normal,Yes,Yes
Sunny,Mild,High,No,No
Sunny,Cool,Normal,No,Yes
Rainy,Mild,Normal,No,Yes
Sunny,Mild,Normal,Yes,Yes
Overcast,Mild,High,Yes,Yes
Overcast,Hot,Normal,No,Yes
Rainy,Mild,High,Yes,No

"""The same tree from scikit-learn, and the overfitting a noisy dataset shows."""
import csv
from sklearn.tree import DecisionTreeClassifier, export_text

with open("weather.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
FEATURES = ["outlook", "temperature", "humidity", "windy"]
codes = {f: {v: i for i, v in enumerate(sorted(set(r[f] for r in rows)))} for f in FEATURES}
for f in FEATURES:
    print("%-12s %s" % (f, codes[f]))
X = [[codes[f][r[f]] for f in FEATURES] for r in rows]
y = [r["play"] for r in rows]

tree = DecisionTreeClassifier(criterion="entropy", random_state=0).fit(X, y)
print()
print(export_text(tree, feature_names=FEATURES).rstrip())
print()
print("training accuracy: %.3f" % tree.score(X, y))
print("leaves           :", tree.get_n_leaves())
print("depth            :", tree.get_depth())

outlook      {'Overcast': 0, 'Rainy': 1, 'Sunny': 2}
temperature  {'Cool': 0, 'Hot': 1, 'Mild': 2}
humidity     {'High': 0, 'Normal': 1}
windy        {'No': 0, 'Yes': 1}

|--- outlook <= 0.50
|   |--- class: Yes
|--- outlook >  0.50
|   |--- humidity <= 0.50
|   |   |--- outlook <= 1.50
|   |   |   |--- windy <= 0.50
|   |   |   |   |--- class: Yes
|   |   |   |--- windy >  0.50
|   |   |   |   |--- class: No
|   |   |--- outlook >  1.50
|   |   |   |--- class: No
|   |--- humidity >  0.50
|   |   |--- windy <= 0.50
|   |   |   |--- class: Yes
|   |   |--- windy >  0.50
|   |   |   |--- temperature <= 1.00
|   |   |   |   |--- class: No
|   |   |   |--- temperature >  1.00
|   |   |   |   |--- class: Yes

training accuracy: 1.000
leaves           : 7
depth            : 4

That is not the tree ID3 built, and both are right. ID3 made five leaves and asked three questions; scikit-learn made seven leaves and went four deep. Two reasons, and both belong in the journal.

scikit-learn's tree is binary. Every node asks a yes-or-no question about one number. Our outlook has three values, and ID3 can branch three ways in one node; scikit-learn has to ask outlook <= 0.50, and then ask again inside the "no" branch. Same information, more nodes.

Integer codes invent an order that does not exist. Writing Overcast as 0, Rainy as 1, Sunny as 2 tells the model that Overcast is less than Rainy, which is meaningless, and lets it ask outlook <= 1.50, which groups Overcast with Rainy for no reason at all. The honest encoding is one-hot: one column per value, holding 1 or 0.

"""Ordinal codes tell the tree a lie. One-hot columns do not."""
import csv
from sklearn.tree import DecisionTreeClassifier, export_text

with open("weather.csv", newline="") as fh:
    rows = list(csv.DictReader(fh))
FEATURES = ["outlook", "temperature", "humidity", "windy"]
y = [r["play"] for r in rows]

# one column per (feature, value) pair, holding 1 or 0
pairs = [(f, v) for f in FEATURES for v in sorted(set(r[f] for r in rows))]
names = ["%s=%s" % (f, v) for f, v in pairs]
X = [[1 if r[f] == v else 0 for f, v in pairs] for r in rows]

print("columns:", len(names))
print(", ".join(names))
print()
tree = DecisionTreeClassifier(criterion="entropy", random_state=0).fit(X, y)
print(export_text(tree, feature_names=names).rstrip())
print()
print("training accuracy: %.3f" % tree.score(X, y))
print("leaves           :", tree.get_n_leaves())
print("depth            :", tree.get_depth())

columns: 10
outlook=Overcast, outlook=Rainy, outlook=Sunny, temperature=Cool, temperature=Hot, temperature=Mild, humidity=High, humidity=Normal, windy=No, windy=Yes

|--- outlook=Overcast <= 0.50
|   |--- humidity=Normal <= 0.50
|   |   |--- outlook=Rainy <= 0.50
|   |   |   |--- class: No
|   |   |--- outlook=Rainy >  0.50
|   |   |   |--- windy=No <= 0.50
|   |   |   |   |--- class: No
|   |   |   |--- windy=No >  0.50
|   |   |   |   |--- class: Yes
|   |--- humidity=Normal >  0.50
|   |   |--- windy=Yes <= 0.50
|   |   |   |--- class: Yes
|   |   |--- windy=Yes >  0.50
|   |   |   |--- temperature=Cool <= 0.50
|   |   |   |   |--- class: Yes
|   |   |   |--- temperature=Cool >  0.50
|   |   |   |   |--- class: No
|--- outlook=Overcast >  0.50
|   |--- class: Yes

training accuracy: 1.000
leaves           : 7
depth            : 4

On this dataset one-hot gave the same size of tree, seven leaves and depth four, and the same perfect training accuracy: the false ordering happened not to hurt here. It is still the encoding to use, because whether it hurts depends on the data and you cannot tell in advance, and because a tree that asks outlook=Overcast <= 0.50 can be read by a human while one that asks outlook <= 1.50 cannot.

criterion="entropy" is what makes scikit-learn use information gain. Its default is "gini", a different measure of mixture that usually builds a very similar tree. Say which you used.

Procedure

1. Save weather.csv. Count the Yes and No rows and compute the entropy of the whole set by hand, then confirm it with the program.
2. Compute the information gain of all four features. Confirm that outlook wins and write the four figures into the journal.
3. Implement entropy, split_on, gain and majority, then id3 with its two stopping rules.
4. Print the tree as text and read it out as rules.
5. Draw the tree.
6. Split the fourteen rows 10 to 4 with a seeded shuffle and measure the tree on the four it never saw. Vary max_depth and record training and test accuracy for each.
7. Repeat on students.csv, which has exceptions in it, and record the depth at which test accuracy starts to fall.
8. Build the same tree with DecisionTreeClassifier(criterion="entropy"), first with integer codes and then with one-hot columns, and explain why its tree differs from yours.

Observations

Result

The Decision Tree Learning algorithm was implemented from nothing and used to build a tree from the fourteen-day dataset. Entropy of the whole set was 0.9403 bits and outlook gave the largest information gain, 0.2467, so it became the root; the Overcast branch was pure and became a leaf immediately. The finished tree asked three questions, had five leaves, never used temperature, and classified all fourteen training rows correctly. Measured on four held-out rows it scored 1.000 at depth 2 and 0.250 at depth 1. On the thirty-student dataset, which contains two exceptions, training accuracy rose to 1.000 at depth 4 while test accuracy fell from 1.000 at depth 2 to 0.778, which is overfitting. scikit-learn built a seven-leaf binary tree from the same data, with the same perfect training accuracy, under both integer and one-hot encoding.

Where marks are lost

Reporting the training accuracy. 14 of 14 means the tree remembered. Split the data.

Growing the tree as far as it will go. On data with exceptions that is how test accuracy falls while training accuracy rises. Show the table of depths.

No branch for a value the group did not contain. Build every branch from the values the whole dataset has, or a new row falls off the tree.

Using log base e. Entropy in this subject is in bits, so it is math.log2. Natural logarithms give 0.6518 where the answer is 0.9403 and every gain comes out wrong by the same factor.

Encoding categories as 0, 1, 2 and saying nothing about it. It tells the model an order that is not there. Use one-hot, or say why you did not.

Not saying which criterion you used. scikit-learn's default is gini, not entropy.

Drawing the tree and not reading it. MU asks you to visualize and interpret. Write the rules out in English.

Dividing by zero in entropy. A group with one class has a single p of 1.0 and log2(1) is 0, which is fine; a group with no rows at all is the one to guard, and the if not group branch above is the guard.

For the journal

Aim; entropy and information gain defined with the formulas; the dataset; the entropy of the whole set worked by hand; the gain table for all four features and the root chosen; the ID3 program; the tree printed as text and drawn as a figure; the five rules in English; the train and test split with the accuracy at each depth; the overfitting table from students.csv; the scikit-learn tree and one sentence on why it differs; both observation tables; the result.

Quick revision

• Entropy is the mixture of labels in bits, 0 when pure and 1 when half and half.
• Information gain is the entropy before a split minus the weighted average entropy after.
• ID3 picks the highest-gain question at every node and repeats.
• Stop when the group is pure, when the questions run out, or at a depth limit.
• H of the 14-day set is 0.9403 bits. outlook gains 0.2467 and wins the root.
• The finished tree: 3 questions, 5 leaves, and temperature never used.
• A path from root to leaf is a rule. That readability is the tree's main advantage.
• A tree grown to purity on data with exceptions overfits: training 1.000, test 0.778 here.
• Cure it with max_depth, a minimum leaf size, or pruning, and choose the value by measuring.
• scikit-learn's tree is binary, so it needs more nodes than ID3 for a three-valued feature.
• Encode categories one-hot. Integer codes invent an ordering.
• criterion="entropy" for information gain; the default is gini.

Questions you must be able to answer

1. What is entropy, in one sentence, and what is it 0 for? A measure in bits of how mixed the labels in a set are. It is 0 for a set whose rows all carry the same label, because there is nothing left to learn.

2. Why was outlook chosen as the root? Because it had the highest information gain, 0.2467 bits against humidity's 0.1518, windy's 0.0481 and temperature's 0.0292.

3. What is information gain? The entropy of a set minus the average entropy of the groups a question splits it into, each weighted by its share of the rows. It is how many bits of uncertainty the question removes.

4. Why does the tree stop immediately on the Overcast branch? Because all four overcast days ended in Yes, so that group's entropy is 0 and no further question can tell you anything.

5. Your tree never uses temperature. Is that a bug? No. Its gain is 0.0292, the lowest of the four, and by the time the tree has split on outlook and then on windy or humidity, each group is pure. The algorithm used what it needed.

6. What is overfitting, and how did you show it? Learning the accidents of the training data instead of the pattern. On students.csv training accuracy rose to 1.000 at depth 4 while test accuracy fell from 1.000 at depth 2 to 0.778.

7. How do you stop a tree overfitting? Limit its depth, require a minimum number of rows in a leaf, or grow it fully and prune back. Choose the limit by measuring on held-out data, not by guessing.

8. Why does scikit-learn's tree look different from yours on the same data? Because it is binary: every node asks one yes-or-no question about a number, so a feature with three values takes two levels instead of one. Its seven leaves and your five describe the same rules.

9. What is wrong with coding Sunny, Overcast and Rainy as 0, 1 and 2? It tells the model they are ordered and evenly spaced, which they are not, and lets it split on a threshold that groups two of them for no reason. One-hot columns carry the same information without the false ordering.

10. A new row arrives with a value your tree has no branch for. What happens? classify falls back to that node's majority label. Without such a default the lookup raises an error, which in an examination is a program that crashed in front of the examiner.