Problem

Our textbook describes in its Section 8.2.1 a basic algorithm for inducing a decision tree from training

tuples. The algorithm follows a top down approach, similar t

o how decision trees are constructed by

algorithms such as ID3, C4.5 and CART.

Part 1

The execution of algorithm given in Section 8.2.1 is illustrated in Section 8.2.2, in Figure 8.5. The

illustration only shows the first two levels of the tree. Complete the example to show the entire

resulting decision tree. Include all nodes, branches and partitions.

Part 2

Write a Java program that implements the basic algorithm for inducing a decision tree.

Note

the following requirements:

-You are not required to fully implement the algorithm as given in pages 332 335, but to implement

the partition that occurs at the root node, i.e. the generation of the first level after the root. Use the

description in Figure 8.3 for the algorithm steps, page 333, and theillustration in Figure 8.5 as a

reference of the expected output.

-Consider the splitting attribute to be discrete-valued and use information gain as the attribute selection measure.

- Your implementation should use the training tuples given in Table 8.1, page 338 of the textbook. When run, the program should

output the information given in Figure 8.5 (the output does not need to look exactly in the way shown there, but must convey the same meaning).

Part 3

Test the implementation in Part 2 by asking the user to enter a tuple and letting the model determine the class label for the tuple.