A decision tree classifies an example by asking a sequence of questions about its features. Think of “21 Questions”: a useful question rules out many wrong answers, while a poor one barely narrows the possibilities. Each answer leads to another question or to a prediction. section 8.16
Classifying diamonds
Suppose a diamond dealer wants to predict whether a cut belongs to an Okay or Perfect group using Carat and Price. A question such as “Is Carat at least 0.5?” sends diamonds down two different paths. Carat alone may not settle the answer: some diamonds with small Carat values are Perfect. A later question about Price can narrow the group further. section 8.16 section 8.17
Table 8.15 The dataset used for the classification example
|
Carat |
Price |
Cut |
|
| 1 |
0.21 |
327 |
Okay |
| 2 |
0.39 |
897 |
Perfect |
| 3 |
0.50 |
1,122 |
Perfect |
| 4 |
0.76 |
907 |
Okay |
| 5 |
0.87 |
2,757 |
Okay |
| 6 |
0.98 |
2,865 |
Okay |
| 7 |
1.13 |
3,045 |
Perfect |
| 8 |
1.34 |
3,914 |
Perfect |
| 9 |
1.67 |
4,849 |
Perfect |
| 10 |
1.81 |
5,688 |
Perfect |
The small dataset shows the Carat and Price features alongside the Okay and Perfect labels the tree must learn to predict. section 8.16
A simple CART learning procedure builds the questions from labeled examples:
- Count the examples in each class. Their mix indicates uncertainty; the Python implementation calculates this with the Gini index. section 8.17
- Try a feature-and-value question, then separate examples according to whether they satisfy it. Compare the uncertainty before and after the split; the reduction is information gain. section 8.17
- Choose the question with the best gain and repeat on both groups. A decision node stores the question and its branches; when no gain remains, a leaf stores label counts. section 8.17
class ExamplesNode: #A
def __init__(self, examples):
self.predictions = find_unique_label_counts(examples)
def __repr__(self):
return f"Leaf: {self.predictions}"
class DecisionNode: #B
def __init__(self, question, true_branch, false_branch):
self.question = question
self.true_branch = true_branch
self.false_branch = false_branch
def __repr__(self):
return f"DecisionNode: {self.question}"
def build_tree(examples, feature_names):
gain, question = find_best_split(examples, feature_names)
if gain == 0:
return ExamplesNode(examples) #C
true_examples, false_examples = split_examples(examples, question) #D
true_branch = build_tree(true_examples, feature_names) #E
false_branch = build_tree(false_examples, feature_names) #E
return DecisionNode(question, true_branch, false_branch)
This Python listing shows how decision nodes, leaves, and recursive splitting fit together in a learning implementation. section 8.17
Training produces a tree of questions, but the test is how it handles new, labeled examples. Feed each example through the tree and compare its prediction with the known class. In the diamond test, 7 of 10 predictions are correct. A confusion matrix distinguishes correct predictions from the two kinds of misclassification; accuracy alone does not show which class is being mistaken for the other. section 8.18
