CECS 375 Assignment 6: Learning a Decision Tree

Due Monday, Dec. 15 by 5 p.m., Email your work to Matt Williams at mgw5a2@mizzou.edu. As before, include a log file that illustrates your program execution. And always use meaningful variable names and helpful comments.

The assignment is worth 8% of your semester grade.

Refer to Chapter 18 in the text. You may use your language of choice.

· Implement the decision tree algorithm from the text (Fig. 18.5).

· Run the algorithm using the Monks-1 training set.

· Show the resulting decision tree.

(To test your implementation of the decision tree algorithm, all cases in the training set should be classified correctly using the learned decision tree.)

The Monks-1 set is based on an artificial robot domain where each “robot” has the following attributes:

Head_shape: round, square, octagon

Body_shape: round, square, octagon

Is_smiling: yes, no

Holding: sword, balloon, flag

Jacket_color: red, yellow, green, blue

Has_tie: yes, no

The format of the training set data file lists one “robot” per line. The attribute values are coded numerically in the order shown below:

Class: 0, 1

Head_shape: 1, 2, 3

Body_shape: 1, 2, 3

Is_Smiling: 1, 2

Holding: 1, 2, 3

Jacket_color: 1, 2, 3, 4

Has_tie: 1, 2

ID: (a unique symbol for each instance)

The Monks data set was used to test and compare several different machine learning algorithms. The resulting report can be found here.

You may want to compare your decision tree to the tree generated by the ID3 (no windowing) algorithm in Chapter 6 of the report.