Background
In this request you will be implementing a decision tree classifier. A decision tree classifier is used in rule-based machine learning to classify data based on a predefined set of attributes. In our case, we will be classifying text based on the terms it contains (or does not contain). Decision trees can be used for real-life applications ranging from answering FAQs to classifying a piece of data.
In order to be able to make decisions using the decision tree classifier, we must first build the decision tree. Your program will be able to import existing decision trees from text files, and edit them in the program. Additionally, it will have to read input text and classify it based on the decision tree, printing the decisions that were made in order to reach the final verdict.
NOTE: All exceptions explicitly thrown in Required Classes except for IllegalArgumentException are custom exceptions that need to be made by you.
Required Classes
TreeNode
private String[] keywords
This field holds the message only if it is a leaf, otherwise this is a list of words to trigger going down this path.
These keywords are joined as if OR’ed together:
Example: {“Fat”; “Orange”}: if text contains Fat or text contains Orange, then go down “yes” path, otherwise “no” path.
private TreeNode left
private TreeNode right
These two fields hold the left and right subtrees respectively.
You should have getters/setters for the three fields above.
public Boolean isLeaf():
function that returns true if the node is a leaf and its left and right subtrees are null, otherwise false.
Preconditions: This node is initialized
Postconditions: The tree remains unchanged
TreeNavigator
private TreeNode root
A reference to the root TreeNode of this tree.
private TreeNode cursor
A reference to the currently selected TreeNode in the tree.
The cursor should select the root node by default.
public static TreeNavigator buildTree(String treeFile)
Reads in a text file describing a TreeNavigator. See sample input for an example.
Preconditions: treeFile is a non-null, non-empty String that points to a file that exists that is readable and valid.
Returns a new TreeNavigator generated by the passed in text file.
public String classify(String text)
Classifies the text with the given tree and returns the classification as a String.
public String getPath()
Gets the current path of the cursor. For example, if cursor referred to a TreeNode at position “Garfield” in the example below, this method should return “NOT red, NOT coyote,wolf, IS cat, IS orange, DECISION: Garfield”
Note the comma above: This is how you can show multiple keywords.
public void resetCursor()
Resets the cursor to the root node.
Postconditions: Cursor references root node. Cursor contents are printed.
public void cursorLeft()
Moves cursor to its left child.
Postconditions: Cursor contents are printed.
public void cursorRight()
Moves cursor to its right child.
Postconditions: Cursor contents are printed.
public TreeNode getCursor()
This gets the Cursor so you can modify the keywords or the Left or the Right child links.
Precondition: Cursor is not null (return null if it is null)
Postcondition: Cursor is returned to the caller.
public void editCursor(String text)
Sets the keywords for the current cursor.
DecisionTreeClassifier (Driver)
public static void main (String args[])
This will drive the program and present a menu like shown below.
You can and should write helper functions for each menu option if not already present in the TreeNavigator.
General Recommendations
You might want to implement a toString() method for classes to make debugging and printing easier. You do not have to do this, but it will help you.
You can feel free to add any extra methods and variables as you see fit (public and private).
Text file format
The input file will be formatted like the following example:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
170;;Red;nonleaf
0-0;Coyote,Wolf;nonleaf
0-0-0;Cat;nonleaf
0-0-0-0;snoopy;leaf
0-0-0-1;fat,orange;nonleaf
0-0-0-1-0;tom;leaf
0-0-0-1-1;garfield;leaf
0-0-1;big,bad,evil,mean;nonleaf
0-0-1-0;Wolf Blitzer;leaf
0-0-1-1;ACME;nonleaf
0-0-1-1-0;Big Bad Wolf;leaf
0-0-1-1-1;Wile E. Coyote;leaf
0-1;Dog;nonleaf
0-1-0;plumber;nonleaf
0-1-0-0;Little Red Riding Hood;leaf
0-1-0-1;Mario;leaf
0-1-1;Clifford;leaf
UI Required Functions
Menu:1
2
3
4
5
6
7
8
9Classify (Sentence)
Path (Sentence)
Import (file)
Cursor To Root (print cursor)
Cursor Left (print cursor)
Cursor right (print cursor)
Edit Cursor (print cursor)
Add Left Child (doesn’t move cursor)
Add Right Child (doesn’t move cursor)
Sample IO
Example 1 - Working with the following tree:
1 | Welcome to the DecisionTree Classifier |
Example 2 - Working with the following tree:
1 | Welcome to the DecisionTree Classifier |
Extra Credit: GUI OR Android – NOT BOTH – Requirements
You must make a nice visualization of all the components. For example this can include a graphical representation of the tree and what each node contains, along with connecting lines to each node.
All the menu options should be buttons, and all inputs should be graphical (ie: in a TextField in JavaFX) for any extra credit.
Extra Credit: Child to Parent (can be done with or without a GUI for credit)
Implement a Cursor to Parent function as in the sample WITHOUT putting a parent reference in the TreeNode class.