Part 2: Decision Trees

Question 1

Decision tree

Answer 1

A decision tree is used to predict the outcome. There are as many splits as attributes. After determining which the possible splits are, the best splits have to be determined to end up with pure nodes. To make this possible, classes are used. To end up with pure nodes, information gain and entropy is used.

Question 2

Entropy (E)

Answer 2

Measures the uncertainty. When you have a pure node, E = 0. When there is a high uncertainty E = 1.

Question 3

Information gain (I)

Answer 3

Measures the increase/decrease in uncertainty given certain information.

Question 4

Theory regarding entropy

Answer 4

New entropy is always less than the original entropy, which causes an information gain.

Question 5

Split on attributes

Answer 5

• Number of variables - the splitting is.
  + Univariate - only one variable is tested.
  + Multivariate - more than one variable is tested at once.
• Type of splitting variable(s)
  + Nominal - e.g., temp.=cool, temp.=mild, temp.=hot
  + Numerical - e.g., temp.<30, temp. >30.
• Number of outcome splits
  + Two (binary) - trees with only binary splits are called binary trees.
  + Multiway split

Question 6

Decision boundary

Answer 6

Borderline between two neighbouring regions of different classes. Decision boundary is parallel to axes because test condition involves a single attribute at-a-time.

Question 7

Types of decision trees

Answer 7

Type of predicted variable (end node):

1. Nominal (class) = majority of label of instances in node Classification trees.
2. Numerical value = average value of instances in node Regression trees.
3. Equation = regression equation with least squares fir Model trees.

Question 8

Tree induction

Answer 8

• Strategy
  + Split the records based on an attribute test that optimizes certain criterion (information gain).
• Important issues
  + Determine how to split records
  + How to specify the attribute test condition?
  + How to determine the best split?
  + Determine when to stop splitting. This is also important to keep in mind when there is noice in the data. Data with noise doesn’t have pure nodes, so if you want to reach pure nodes, you’re modelling noise.

Question 9

Measures for node impurity (a.k.a. when to stop splitting)

Answer 9

1. Misclassification error.
2. Entropy (this is the preferred option because in general this provides the smallest trees).
3. Gini index

Question 10

Quality of a split

Answer 10

Objective: obtaining pure nodes, i.e., nodes that contain objects from a single class (if node is impure, take majority class as label).
- Measures for impurity
\+ Misclassification error - fraction of objects that are classified correctly and part incorrectly if we assign every object to the majority class in that node.

Question 11

Splitting based on classification error

Answer 11

Classification error at a node t:
- Error(t) = 1 - maxP(i|t)
Measures misclassification error made by a node
- Maximum (1-1/nc), when records are equally distributed among all classes.
- Minimum (0.0) when all records belong to one class pure node.

Question 12

For efficient computation

Answer 12

For each attribute:

• Sort the attribute on values.
• Linearly scan these values, each time updating the count matrix and computing entropy or index.
• Choose the split position that has the least entropy or index.

Question 13

Regression tree overfitting

Answer 13

Divide the x axis in parts in such a way that in each part the value of the node is equal to the average of the red points. By continuing splitting you can fit the red points arbitrarily well.

• 2 splits
• 4 splits
• 6 splits -> very sensitive to noise.

Question 14

Growing the tree

Answer 14

Using the training data:
- Split nodes base on impurity criterium.
- Until all leave nodes are pure (impurity = 0)
Problem: if the tree is too large, the model also contains noise of the training data.

Question 15

Underfitting

Answer 15

When model is too simple, both training and test errors are large.

Question 16

Overfitting

Answer 16

When model is too complex, training errors are small and test errors are large:
- Overfitting results in decision trees that are more complex than necessary.
- Training error no longer provides a good estimate of how well the tree will perform on previously unseen records.
- Solutions:
Occam’s Razor principle:
+ Given two models of similar generalization errors, one should prefer the simpler model over the more complex model.
+ For complex models, there is a greater chance that it was fitted accidentally by errors in data.
Possible solution:
- Include model complexity when evaluating a model.

Question 17

Stopping criteria

Answer 17

• Stop splitting if information gain is too low < threshold.
• Stop splitting if the error on the validation set goes up.
  Problem: in a later stage you might get higher gain or lower error.

2 systematic methods:

• Quinlan in C4.5: reduced error pruning
• Breiman in CART: cost complexity pruning

Question 18

Tree pruning

Answer 18

1. Reduced error pruning: Make inner node into leaf node if error on validation set decreases, continue until no decrease possible.
2. Cost complexity pruning: just grow the tree until impurity is zero, and then prune back using cost complexity measure.