Description
1 Inductive Construction
Given the dataset in Table 1 construct a decision tree by hand using the top-down algorithm presented in the lecture. Your stop criteria are zero entropy or a depth of 2 (the root node is at depth 0, the rst layer of inner nodes are at depth 1, …).
Draw your nal decision tree and provide your computation steps (information gain per relevant attribute for each split, class frequencies for each node, . . . ). Compute the error rate of your decision tree on the training data.
2 Minimal Error Pruning
Figure 1 shows a decision tree for classi ying mushrooms as either edible or poisonous. We used the same dataset as shown in the lecture and constructed it with scikit-learn with a maximum depth of 4. Because the implementation of scikit-learn uses a slightly di erent algorithm (CART, in the lecture: ID3), which allows continuous data, we have to apply one-hot encoding to each variable resulting in a binary decision tree.
Prune two decisions (inner nodes) of the decision tree based on the error rate. First, compute the overall error rate of the original tree. Second, consider the removal of each viable node by computing the error rate after removing it from the tree. Third, identify the node with the lowest error rate and prune it. Repeat this process to remove a second inner node.
Draw the decision tree after each pruning step. Provide your calculations for the pruning step.
Note: A node is viable for pruning, if all its children are leaf nodes. After pruning the chosen inner node turns into a leaf node. We de ne the overall error rate as (slide 44):
number of misclassi ed samples in each leaf
total number of samples
-
Table 1: Dataset consists of 4
categorical
features
(F1 2 f0; 1g, F2 2 f0; 1g, F3 2
f0; 1; 2g, F4 2 f0; 1g) and a binary classi cation target with labels f ; +g.
F1
F2
F3
F4
Instances
+
0
0
0
0
0
10
0
0
0
1
5
5
0
0
1
0
10
0
0
0
1
1
10
0
0
0
2
0
0
10
0
0
2
1
0
10
0
1
0
0
10
0
0
1
0
1
10
0
0
1
1
0
5
5
0
1
1
1
0
10
0
1
2
0
10
0
0
1
2
1
0
10
1
0
0
0
0
10
1
0
0
1
10
0
1
0
1
0
5
5
1
0
1
1
0
10
1
0
2
0
0
10
1
0
2
1
0
10
1
1
0
0
10
0
1
1
0
1
10
0
1
1
1
0
10
0
1
1
1
1
10
0
1
1
2
0
0
10
1
1
2
1
0
10
-
3
