Decision Tree Learning
Chapter Fifty-Six
Syllabus topic Module 2, "Decision Trees"
Pages 308 to 313 of 591
In one line
A decision tree asks the most informative question first, splits the data on the answer, and repeats on each part until the answers agree.
In the wording a student can write in an examination: decision tree learning constructs a tree in which each internal node tests one attribute, each branch corresponds to a value of that attribute, and each leaf carries a class label. The standard algorithm, ID3, is greedy and recursive: at each node it selects the attribute of highest information gain, partitions the instances by that attribute's values, and recurses on each partition, stopping when the instances at a node all share a class, when no attributes remain, or when the partition is empty.
The algorithm
ID3(examples, attributes):
if every example has the same class: return a LEAF with that class
if attributes is empty: return a LEAF with the MAJORITY class
A = the attribute of greatest information gain; make a node testing A
for each value v of A: part = the examples with A = v
if part is empty: attach a LEAF with examples' majority class
else attach ID3(part, attributes without A)
return the nodeThree stopping conditions, and all three are examinable. The examples agree, so nothing is left to ask. The attributes are exhausted, so no question remains and the majority is the best available answer. Or the partition is empty, which happens when a value of A occurs nowhere in this branch, and the parent's majority is used.
The attribute used at a node is removed from the list. Splitting on it again in the same branch would gain nothing, since every example in the branch now shares its value. That is true only for a categorical attribute; a continuous one tested as x <= t may be tested again with a different threshold.
Building it, with the gain at every node
# ID3: build the whole tree from the 14 rows, printing the gain at every node,
# and then turn the tree into rules. Read against Quinlan 1986.
import math
ROWS = [
("rain", "far", "no", "yes", "no"),
("rain", "far", "no", "no", "no"),
("clear", "far", "no", "yes", "yes"),
("humid", "near", "no", "yes", "yes"),
("humid", "near", "yes", "yes", "yes"),
("humid", "near", "yes", "no", "no"),
("clear", "near", "yes", "no", "yes"),
("rain", "near", "no", "yes", "no"),
("rain", "near", "yes", "yes", "yes"),
("humid", "far", "yes", "yes", "yes"),
("rain", "far", "yes", "no", "yes"),
("clear", "far", "yes", "no", "yes"),
("clear", "near", "no", "no", "yes"),
("humid", "far", "no", "no", "no"),
]
COLS = ["weather", "distance", "friend", "early"]
TARGET = 4
def entropy(rows):
if not rows:
return 0.0
out = 0.0
for label in set(r[TARGET] for r in rows):
p = sum(1 for r in rows if r[TARGET] == label) / len(rows)
out -= p * math.log2(p)
return out
def split(rows, col):
d = {}
for r in rows:
d.setdefault(r[col], []).append(r)
return d
def gain(rows, col):
return entropy(rows) - sum(len(p) / len(rows) * entropy(p)
for p in split(rows, col).values())
def majority(rows):
counts = {}
for r in rows:
counts[r[TARGET]] = counts.get(r[TARGET], 0) + 1
return max(sorted(counts), key=lambda k: counts[k])
def build(rows, available, depth=0, why=""):
pad = " " + " " * depth
labels = set(r[TARGET] for r in rows)
if len(labels) == 1: # STOP: the rows agree
leaf = labels.pop()
print("%s%s-> LEAF %s (%d rows, all agree)" % (pad, why, leaf, len(rows)))
return leaf
if not available: # STOP: no attributes left
leaf = majority(rows)
print("%s%s-> LEAF %s (%d rows, no attributes left, majority)"
% (pad, why, leaf, len(rows)))
return leaf
best = max(available, key=lambda c: gain(rows, c))
g = gain(rows, best)
print("%s%ssplit on %-9s gain %.4f (%d rows, entropy %.4f)"
% (pad, why, COLS[best], g, len(rows), entropy(rows)))
tree = {}
rest = [c for c in available if c != best]
for value in sorted(split(rows, best)):
part = split(rows, best)[value]
tree[value] = build(part, rest, depth + 1, "%s = %s " % (COLS[best], value))
return (COLS[best], tree)
print("building the tree from %d rows, entropy %.4f" % (len(ROWS), entropy(ROWS)))
print()
tree = build(ROWS, list(range(len(COLS))))
print()
def rules(node, path=None):
"""Every root-to-leaf path, as an IF ... THEN rule."""
path = path or []
if isinstance(node, str):
return [(" and ".join(path) if path else "always", node)]
col, branches = node
out = []
for value in sorted(branches):
out += rules(branches[value], path + ["%s is %s" % (col, value)])
return out
print("THE SAME TREE AS RULES, which is how it is read aloud:")
for cond, then in rules(tree):
print(" IF %-46s THEN attend = %s" % (cond, then))
print()
def classify(node, row):
while not isinstance(node, str):
col, branches = node
node = branches[row[COLS.index(col)]]
return node
wrong = sum(1 for r in ROWS if classify(tree, r) != r[TARGET])
print("the tree gets %d of %d training rows right." % (len(ROWS) - wrong, len(ROWS)))
leaves = len(rules(tree))
print("it has %d leaves, for %d training rows." % (leaves, len(ROWS)))Decision Tree Learning
building the tree from 14 rows, entropy 0.9403
split on weather gain 0.2467 (14 rows, entropy 0.9403)
weather = clear -> LEAF yes (4 rows, all agree)
weather = humid split on early gain 0.9710 (5 rows, entropy 0.9710)
early = no -> LEAF no (2 rows, all agree)
early = yes -> LEAF yes (3 rows, all agree)
weather = rain split on friend gain 0.9710 (5 rows, entropy 0.9710)
friend = no -> LEAF no (3 rows, all agree)
friend = yes -> LEAF yes (2 rows, all agree)
THE SAME TREE AS RULES, which is how it is read aloud:
IF weather is clear THEN attend = yes
IF weather is humid and early is no THEN attend = no
IF weather is humid and early is yes THEN attend = yes
IF weather is rain and friend is no THEN attend = no
IF weather is rain and friend is yes THEN attend = yes
the tree gets 14 of 14 training rows right.
it has 5 leaves, for 14 training rows.Decision Tree Learning
Follow the three levels.
The root splits on weather, gain 0.2467, the largest of the four as Entropy and Information Gain computed.
The clear branch stops immediately. All four of those students attend, so the first stopping condition fires: a leaf, with no further question.
The humid branch splits on early with a gain of 0.9710, which is the whole of that branch's entropy, so both of its parts are pure. The rain branch does the same on friend.
The tree is three levels deep with five leaves and it classifies all fourteen training rows correctly, and neither distance nor one of the other attributes appears at all. ID3 uses an attribute only where it is the most informative question available, and two of the four are never worth asking.
Why the greedy choice is not guaranteed best
ID3 takes the attribute of highest gain at each node, without looking ahead, and never revisits a choice. That is what greedy means, and it has two consequences a paper can ask about.
The tree found may not be the smallest tree that fits. A pair of attributes that are individually uninformative can be jointly decisive: the exclusive-or of two attributes has zero gain on each of them separately, so ID3 will not choose either first, although splitting on one and then the other classifies the data perfectly.
Finding the smallest consistent tree is NP-hard, which is why every practical algorithm is greedy. So the greediness is not laziness; it is the only tractable option, and the price is that the tree is a good one rather than the best one.
ID3 also performs no backtracking: once a split is made it is never undone. A poor early choice is carried by every branch beneath it.
The tree as rules
Read the second block of output. Every root-to-leaf path is an IF ... THEN rule, and the five paths give five rules that cover every case exactly once.
That correspondence is the reason decision trees are the most interpretable model in MU's list, and it is the answer to any question about why they are preferred where an explanation is needed. Rule-Based Systems and Expert Systems had to be given its rules by an expert; a decision tree learns the same kind of rules from data. It is the direct answer to the knowledge acquisition bottleneck that chapter records.
Decision Tree Learning
The rules are mutually exclusive and exhaustive by construction, so unlike a hand-written rule base there is no conflict set and no need for a conflict-resolution strategy.
What ID3 cannot do, and what came after it
Quinlan's own 1986 paper is explicit about the limitations, and naming the successor is worth a mark.
| Limitation of ID3 | What C4.5 and CART do |
|---|---|
| Only categorical attributes | C4.5 handles continuous ones with x <= t thresholds |
| Gain is biased towards many-valued attributes | C4.5 uses gain ratio; CART uses Gini |
| No handling of missing values | C4.5 sends a fraction of the instance down each branch, weighted by how common that value is |
| No pruning, so it overfits noisy data | C4.5 prunes; CART uses cost-complexity pruning |
| Only classification | CART also does regression, with the mean at each leaf and variance in place of entropy |
CART produces strictly binary trees, splitting on A = v against A != v even for categorical attributes, where ID3 gives a branch per value. That difference matters: a many-valued attribute fragments an ID3 tree into small parts very quickly, and CART does not.
The fragmentation problem
Worth its own paragraph because it is the practical failure of the method and it explains why the next chapter is about pruning.
Every split divides the data. After three splits on three-valued attributes, 14 rows have become 27 potential parts, most of them holding one row or none. A decision made on one or two rows is not a decision, it is an accident, and the tree will assert it with complete confidence.
That is why practical implementations impose a minimum number of instances at a node before a split is allowed, and why Reading, Drawing and Pruning a Decision Tree is a chapter rather than a remark.
Distinctions
| Internal node | Leaf | |
|---|---|---|
| Holds | a test on one attribute | a class label |
| Has children | one per value of the attribute | none |
| Created when | some attribute has positive gain and the rows disagree | the rows agree, or no attribute is left |
| ID3 | C4.5 | CART | |
|---|---|---|---|
| Split measure | information gain | gain ratio | Gini |
| Continuous attributes | no | yes | yes |
| Missing values | no | yes, fractionally | yes, by surrogate splits |
| Pruning | no | yes | yes, cost-complexity |
| Branches per node | one per value | one per value | always two |
| Regression | no | no | yes |
| A decision tree | A hand-written rule base | |
|---|---|---|
| Rules come from | data | an expert |
| Conflict resolution | not needed, the rules are exclusive | required |
| Answers the knowledge acquisition bottleneck | yes | it is the bottleneck |
Decision Tree Learning
What it does not mean
ID3 does not find the smallest tree. It is greedy, and finding the smallest consistent tree is NP-hard.
An attribute absent from the tree is not irrelevant. It was simply never the best question at any node where it remained available.
A pure leaf is not evidence that the tree is right. Purity on two rows is easily an accident, which is what fragmentation means.
Removing an attribute after use is not always correct. It is correct for a categorical attribute, whose value is fixed in the branch, and not for a continuous one tested by a threshold.
The tree's perfect training accuracy is not a result. Overfitting and Underfitting settled that, and the next chapter measures what it costs.
Decision trees are not restricted to classification. CART fits regression trees, with the mean at each leaf and variance reduction in place of information gain.
Quick revision
- ID3: at each node choose the attribute of greatest information gain, split on its values, recurse. Greedy, recursive, no backtracking.
- Three stopping conditions: the rows agree; no attributes remain, so take the majority; or the partition is empty, so take the parent's majority.
- A used categorical attribute is removed from the branch; a continuous one may be reused with a different threshold.
- The 14-row tree: root weather (gain 0.2467),
cleara pure leaf,humidsplit on early andrainon friend, both with gain 0.9710. Five leaves, 14 of 14 correct, and two attributes never used. - Greedy is not optimal: exclusive-or gives zero gain on each attribute alone, and finding the smallest consistent tree is NP-hard.
- Every root-to-leaf path is an IF ... THEN rule, mutually exclusive and exhaustive, needing no conflict resolution. That is why trees are the most interpretable model in MU's list, and it answers the knowledge acquisition bottleneck.
- ID3's limits: categorical only, gain biased, no missing values, no pruning, classification only. C4.5 adds thresholds, gain ratio, missing values and pruning; CART uses Gini, is always binary, and does regression.
- Fragmentation: each split divides the data, so deep nodes decide on one or two rows, which is why a minimum node size and pruning are needed.
Test yourself
1. Give the ID3 algorithm. If every example has the same class, return a leaf with it. If no attributes remain, return a leaf with the majority class. Otherwise select the attribute of greatest information gain, make a node testing it, and for each of its values recurse on the examples with that value, using the remaining attributes; an empty partition becomes a leaf with the parent's majority class.
Decision Tree Learning
2. Name the three stopping conditions. All the examples at the node share one class; the list of attributes is exhausted, so the majority class is used; or the partition for some value is empty, in which case the parent's majority class is used.
3. Describe the tree built from the 14 rows. The root splits on weather with a gain of 0.2467. The clear branch is a pure leaf predicting attend. The humid branch splits on early with a gain of 0.9710, giving two pure leaves, and the rain branch splits on friend, also with gain 0.9710, giving two more. The tree has five leaves and classifies all fourteen training rows correctly, without ever using distance.
4. Why is a greedy algorithm used when it is not guaranteed to find the best tree? Because finding the smallest tree consistent with the data is NP-hard, so no tractable algorithm can guarantee optimality. Greedy selection gives a good tree at reasonable cost, and the price is illustrated by the exclusive-or of two attributes, on which each attribute alone has zero gain although the pair is decisive.
5. Explain the relationship between a decision tree and a rule base. Each root-to-leaf path is an IF-THEN rule whose conditions are the tests along the path. The resulting rules are mutually exclusive and exhaustive, so unlike a hand-written rule base no conflict-resolution strategy is needed. The important difference is that the rules are learned from data rather than supplied by an expert, which answers the knowledge acquisition bottleneck.
6. Give four limitations of ID3 and say how its successors address them. It handles only categorical attributes, which C4.5 fixes with threshold tests. Its gain measure is biased towards many-valued attributes, which C4.5 addresses with gain ratio and CART with the Gini index. It has no treatment of missing values, which C4.5 handles by sending fractions of an instance down several branches. And it does not prune, so it overfits noisy data, which both successors correct.
7. What is fragmentation, and what follows from it? Every split divides the data among its branches, so after a few splits the parts contain very few instances. A decision made on one or two rows is an accident rather than evidence, yet the tree asserts it with full confidence. It follows that practical implementations require a minimum number of instances before allowing a split, and that the tree must be pruned.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.