Assignment 3

Decision-Tree Learning (DTL)

Jeroen van Dijk, Marius Bulacu, en Lambert Schomaker

Implement the DTL algorithm from Russel & Norvig(Figure 18.7, page 537) (or from a decision tree article) in Java. The Javadoc is provided for the interface, as well as the following code:

Restaurant.java - the restaurant example from the book
And.java – boolean AND function, requiring no information theory
Tree.java – general tree class with formatted output
Example.java – data structure for representing examples
AttrTable.java – class wich implements an attribute table

You should write DTL.java following the interface provided. Note that you must also implement the constructor for this class, as well as a test function, to make decisions on novel examples. Your restaurant decision tree should look like the one in Figure 18.8, and should give the right answer for the novel examples. Initially, you should just write your CHOOSE-ATTRIBUTE function to return the first attribute in attributes. Then you can modify the function to use information theory, as described in Section 18.4. You may find the Vector, Hashtable, HashSet, and Iterator class of the java.util package useful in writing your DTL class.

Show your DTL.java on the practicum or send the file to Jeroen van Dijk with subject: "[KI2] assignment 3 - yourname". In the body you can write your name and student number. Put the DTL.java in the attachment. The DTL.java file must run under Linux with the other files I've provided you. The deadline is 30 januari.

Here is an output example with the gain values. Note that the tree isn't exactly like the one in the book. It's another solution to the problem. If you have any doubts compare the gain values.

You have to work alone.

Programs in other languages than Java like C are permitted if it's well documented and provided with a manual. I will ask you to explain the code. Note that you have to build the whole algorithm yourself; I won't give you any help-files like the provided files in Java. When you do this you've to implement the "letters-naar-klinkers" example. I've you have any doubts contact Jeroen van Dijk.

(This assignment is (partly) copied from http://cs.wlu.edu/~levy/courses/cs315-03/ps5/ps5.pdf )