AIspace

Practice Exercise 7.A

Decision Trees

Back to practice exercises.

1: Background Reading

7.3.1 Learning Decision Trees

2: Learning Goals

Classify examples using a decision tree.
Build a decision tree using training examples.

3: Directed Questions

What does an arc represent in a decision tree? [solution]
What does a non-leaf node represent in a decision tree? [solution]
What does a leaf node represent in a decision tree? [solution]
Describe at least one way to overcome the problem of overfitting when constructing decision trees. [solution]
Describe one way to avoid predicting a probability of zero for test data using a decision tree. [solution]

4: Exercise: Jane's Pizza Party

Jane is planning a surprise pizza party for her friends. She doesn't know what pizza toppings her friends like and she doesn't want to ruin the surprise by asking them. Instead she decides to survey random people about their pizza preferences. After examining the survey results, she manually decides on what pizzas to order. Unfortunately some of the people at the party complained about her pizza choices. She recorded all of the complaints and compliments about the pizza.

The following file contains all the data Jane recorded: survey.txt. The training data contains Jane's survey results. The test data contains the pizza complaints and compliments from the party. Use the decision tree tool to create a decision tree predicting people's pizza preference based on the data Jane collected.

How many errors did Jane make on the test set? [solution] You should be able to create a decision tree which does better. Try adjusting the splitting function and stopping conditions to minimize the test error. You can also try solving this problem using the neural network tool (as seen in Exercise 7.B).

Consider the following decision tree:

pizza

As described in section 7.3.1, any deterministic decision tree in which all of the leaves are classes can be mapped into a set of rules. What set of rules represents the decision tree shown above? [solution] How many mistakes would this decision tree make on the data from Jane's party? [solution]

5: Learning Goals Revisited

Classify examples using a decision tree.
Build a decision tree using training examples.