A decision tree can be viewed as a flow chart or diagram representing a classification system or predictive model. The tree is structured as a sequence of questions, the answers to which trace a path down the tree to a leaf containing the path's classification or prediction. The classification or prediction made by the model can be a qualitative judgment (e.g., these are responders) or a numerical forecast (e.g., sales will increase 15 percent). Decision trees can be used in many ways, from mining data contained in very large databases to making decisions in response to simple yes/no questions. Decision trees can also "learn" by being extended when an incorrect answer is found at the end of a path.
In this assignment you will have the opportunity to build, modify and use binary decision trees. In the tree that you maintain, each internal node is a yes/no question with two children. Leaves contain the results of traversing the various paths. You are to write a Java application that learns about the universe of your choice by asking the user yes/no questions. For example, the program might learn about animals by having the following dialog with its user (user responses are in uppercase; the actual project will communicate by using dialog boxes):
Think of an animal and I will guess it.
Does it have legs? YES
Is it a cat? YES
I win! Continue? YES
Think of an animal and I will guess it.
Does it have legs? NO
Is it a snake? YES
I win! Continue? YES
Think of an animal and I will guess it.
Does it have legs? NO
Is it a snake? NO
I give up. What is it? EARTHWORM
Please type a question whose answer is yes for an earthworm and no for a snake:
DOES IT LIVE UNDERGROUND?
Continue? NO
Good-bye
The next set of questions might lead to Is it a snake? To which the answer might be no and the question to learn next might be Does it live in water? resulting in another node being added to the tree:
It could also be the case that a result might need to be deleted from the tree. For example, if snake is deleted then fish replaces the question Does it live in water?
Finally, once a tree is built, it would be nice to have it persist between the times the application is run. Thus the tree should be able to be saved to a text file and rebuilt by reading that file when the application is launched again. In addition, it should be possible to save and load several different "knowledge bases" (decision trees).
The Guessing project has at least four classes:
- Driver: Contains the method main, which creates an instance of GuessingGUI and invokes its start method. Driver will be used to run the application stand-alone (not in the BlueJ environment) once you have completed the rest of the project. You should test as you go by using instances of GuessingGUI, Game and the other classes you write.
- GuessingGUI: Contains code that creates a Graphical User Interface with components that are used to accomplish interaction with the application(see below). You should study this module carefully as it contains calls to methods corresponding to each of the buttons in the GUI. It also contains methods used by Game: to open a file for reading and for writing.
- Game: Contains a minimal amount of uninteresting code corresponding to each of the buttons in the GUI.
- DTree: Is a class not yet written. It contains instance variables and methods corresponding to a decision tree class. The tree will have nodes with left and right child references, as well as a String item in which to store a question or a result. The left reference will correspond to the decision YES and the right to the decision NO. You will need to provide methods to: visit the next node (based on YES or NO decision), write a tree to a text file, read and create a tree from a text file, and add a question and a result to the tree (the result will be a leaf). You will receive extra credit if you also implement the delete method described above.
- You may choose to write or include additional classes or methods; a DTreeNode class, for example. For each such class and method make sure to provide complete documentation using JavaDoc format.
The Guessing project:
- The provided files can be copied from
I:\csc122\public\Guessing. - Implement the project using the test-driven implementation strategy: first build a test system and stubbed implementation of each class.
- One strategy for saving a tree to a file is to write each node's item field as a separate line, doing so using a preorder traversal of the tree (recursive or otherwise). You will need to mark each leaf so that you can recognize them when restoring the tree. One way to do this is to write an empty string as a line in the file prior to writing the item in the leaf node; another is to prefix each line of the file with a tag character, such as Q for question and L for leaf node. Don't forget to close the file when you are finished writing the tree.
- Restore a tree from a file by first reading the first line from the file (it will become the root) and building the rest of the tree knowing that it is in preorder in the file. If you use the first approach above, then when you encounter an empty string you know that the next line from the file corresponds to a leaf, and you can create a node without any children accordingly. If you use the second approach, you will need to strip off the first character of each line that is read. Using a recursive read method, the prototype for the helper method might be: DTreeNode readTree(BufferedReader reader)
Standards:
Your project should be well-written, neatly-formatted, modular, and well-documented.
Grading:
- Correctly handling decision tree operations (48 points)
- write a tree
- read a tree
- get next node
- add a question (and result)
- delete a node (extra credit)
- Correctly implementing each of the button actions in the GUI. This may
require some modification of GuessingGUI and will certainly require
modification of methods in Game. (40 points)
- Clear Questions
- Load File
- Save File
- Start Game
- Delete Item (extra credit)
- Documentation and style (12 points)
- Extra credit will not be awarded without the required items being completed.
