In class we have seen the importance of separating the variant from the invariant. Now you'll have a chance to use the invariant part, by writing code that implements a decision tree.
A decision tree is a binary tree first introduced in artificial intelligence for creating expert systems. It works like this: Non-leaf nodes hold a yes or no question. If the user selects yes, then the algorithm moves to the left subtree, if the user selects no, the algorithm moves to the right subtree. Leaf nodes contain answers.
In the sample run below we see a decision tree that has been loaded with questions to play an animal guessing game. If the computer is wrong, it will learn from the user and save the new information.
This is a sample run using the simplesample.txt file
as the load file. Your output should be formatted the same. Note: that the driver
class allows us to specify different input files, yours must work for any
valid input file.
Tree loaded
Is it a mammal?
a mouse
a robin
Making decision
Is it a mammal? n
Is it a robin? n
I give up, what are you thinking about? a nanday conure
Give me a yes/no question to distinguish a robin from a nanday conure.
Does it have a green feathers
For a nanday conure, Does it have a green feathers? y
I'll try to remember that.
Saving changes.
Rebuilding tree from save file.
Tree loaded
Is it a mammal?
a mouse
Does it have a green feathers?
a nanday conure
a robin
Making decision
Is it a mammal? n
Does it have a green feathers? y
Is it a nanday conure? y
I knew it!
First download the skeleton files. Unzip it to create the HW6 directory.
You are to implement the following:
DTBuilder - reads the data from an input file and builds the
DecisionTree. It must be able to read files formatted just as
sampledata.txt and simplesample.txt.ToStringAlgo - creates a printable representation of the tree
with the different levels indented (see above).MakeDecisionAlgo - runs through the tree either asking the
user questions or (finally) presenting the user with an answer. If that is
not the correct answer, then it must learn (as above). Notice the dialogue
that takes place when the user wasn't thinking of a robin. Learning causes
the tree to be changed.TreeSaveAlgo - saves the tree in the format read by DTBuilder,
see sampledata.txt and simplesample.txt for examples.Zip the entire HW6 directory, zip -r HW6.zip
HW6. Submit
it no later than 11:59:59pm Friday August 9,Saturday, August 10,
2002.