Summary Sheet 2: Decision Tree Learning

Machine Learning – Summer 2006 – Exercises
Steffen Hölldobler and Axel Großmann


Sheet 2: Decision Tree Learning

Solution to Exercise 3 to be handed in on 16th May 2006

Exercise 1

Exercise 3.1 in Mitchell’s book.


Exercise 2

Given the following training examples for the target concept EnjoySport.
Example Sky AirTemp Humidity Wind Water Forecast EnjoySport
1 Sunny Warm Normal Strong Warm Same Yes
2 Sunny Warm High Strong Warm Same Yes
3 Rainy Cold High Strong Cool Change No
4 Sunny Warm High Strong Cool Change Yes
5 Sunny Warm Normal Weak Warm Same No
Draw the decision tree that will be learnt by ID3 based on the training examples. Show the value for
information gain for each of the candidate attributes for each step in the growing tree.


Exercise 3

Exercise 3.4 in Mitchell’s book.


Exercise 4

Discuss the merits and drawbacks of each of the following two schemes for handling multi-class data
sets:
(a) Form a single decision tree for all classes.
(b) Form one decision tree for each class. To train a decision tree for class Ci convert the data into
a two-class problem using the following rule to relabel each instance: if the class is equal to Ci
then set label to +, else set label to – . To classify an instance using this scheme you use each
class’s tree to classify it and then output all class names whose corresponding tree predicted
a +.