Java代写：CSE214 Decision Tree Classifier

发表于   |   分类于

练习ADT中Tree的用法，代写一个决策树分类器的应用程序。

Background

In this homework 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:

0;;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:

  • Classify (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:

Welcome to the DecisionTree Classifier
Menu:
        I)Import a tree from a file
        E)Edit current tree
        C)Classify a Description
        P)Show decision path for a Description
        Q) Quit.
Please select an option: E
Cursor is at root.
Current node keywords: tree is empty Root node is initialized with this value.
Please select an option:
        E)Edit Keywords
        C)Add Children Children are automatically leaves, can be edited later.
        D)Delete Children, and Make Leaf Ask user for new value for keyword(only one, no commas).
        N)Cursor to No Child
        Y)Cursor to Yes Child
        R)Cursor to Root
        P)Cursor to Parent Extra credit. May not use parent reference for extra credit.
M)Main Menu
Please select an Edit option:E
Please enter keywords for this node, separated by a comma:smelly,dim
Keywords updated to: smelly, dim.
//Edit menu not shown again in sample IO
Please select an Edit option: C
Please enter terminal text for the no leaf: tempNo
Please enter terminal text for the yes leaf: tempYes
Children are: yes - 'tempYes' and no - 'tempNo'
Please select an Edit option: Y
Cursor moved. Cursor is at leaf, message is 'tempYes'.
Please select an Edit option: A
Please enter terminal text for the no leaf: Javits
Please enter terminal text for the yes leaf: Old CS
Children are: yes - 'Old CS' and no - 'Javits'
Please select an Edit option:E
Please enter keywords for this node, separated by a comma:asbestos,broken
Keywords updated to: smelly, dim.
Please select an Edit option:R
Cursor moved. Cursor is at root.
Current node keywords: smelly, dim
Please select an Edit option:N
Cursor moved. Cursor is at leaf, message is 'tempNo'.
Please select an Edit option:E
Please enter keywords for this node, separated by a comma:sick,food,bad,activities
Keywords updated to: sick,food,bad,activities.
Please select an Edit option: A
Please enter terminal text for the no leaf: New CS
Please enter terminal text for the yes leaf: SAC
Children are: yes - 'New CS' and no - 'Javits'.
Please select an Edit option: M
//Main menu not shown in sample
Please select an option: C
Please enter some text: Where can I go if I want to sit in a broken chair in a dim room?
Your request is classified as: Old CS
Please select an option: P
Please enter some text: I would like to get sick before my test tomorrow. Where should I eat to increase my chances?
Decision path:NOT smelly, dim, IS sick, DECISION: SAC
Please select an option: E
Cursor is at root.
Current node keywords: smelly, dim
Please select an Edit option: D
Please enter a terminal text for this node: Chuck Norris
Current node is leaf. Text is: 'Chuck Norris'.
Please select an Edit option: M
Please select an option: C
Please enter some text: Who can kill two stones with one bird?
Your request is classified as: Chuck Norris
Please enter a menu option: Q
Goodbye!

Example 2 - Working with the following tree:

Welcome to the DecisionTree Classifier
Menu:
        I)Import a tree from a file
        E)Edit current tree
        C)Classify a Description
        P)Show decision path for a Description
        Q)Quit.
Please select an option: I
Please enter a filename: sampletree.txt
Tree Loaded.
Please select an option:P
Please enter some text:This Character is an orange cat who likes lasagna.
Decision path: NOT red, NOT coyote,wolf, IS cat, IS orange, DECISION: Garfield
Please select an option:C
Please enter some text:I'm looking for a plumber, but I insist that he wears a red hat, so I know how to tell  him apart from his brother.
Your request is classified as: Mario
Please select an option:C
Please enter some text: Who is the unlucky coyote who always tries to use ACME products to catch a bird?
Your request is classified as: Wile E. Coyote
Please enter a menu option: Q
Goodbye!

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.