Implement decision trees using information gain as the splitting criterion. Your implementation only needs to handle binary classication tasks (0 or 1). In addition, you may assume that all attributes have binary values (0 or 1) and that there are no missing values. A sample train (train.data) and test le (test.data) are provided in the course website. If you reach a leaf node and have examples that belong to dierent classes, choose the most frequent class among the instances at the leaf node (not necessarily the most frequent class in the entire training set). If you reach a leaf node and have no examples left or the examples are equally split among multiple classes, choose the class that is most frequent in the entire training set. Use the starter code provided. Do not modify the starter code, especially the main call to the program. Use logarithm base 2 when calculating entropy and set 0 log 0 to 0. Specically: 1. Build a decision tree using the training instances and print to stdout the tree in the following format: tea = 0 : | barclay = 0 : | | romulan = 0 : | | | wesley = 0 : | | | | honor = 0 : | | | | | poetry = 0 : 0 | | | | | poetry = 1 : 0 | | | | honor = 1 : | | | | | poetry = 0 : 0 | | | | | poetry = 1 : 0 ... 2. Use the learned decision tree to classify the training and test instances. Print the accuracy of the tree, calculated as percentage of instances correctly classied. For example (I just made up the numbers): Accuracy on training set (800 instances): 52.30% Accuracy on test set (203 instances): 48.19% 2 Starter code To make your job easier, a class for dealing with decision trees has already been implemented in decTree.py. Take a look at the implementation and execute the tiny test (it just creates an arbitrary decision tree and prints it): $ python decTree.py attr1 = 0 : | attr2 = 0 : | | attr3 = 0 : 0 | | attr3 = 1 : 1 | attr2 = 1 : 0 attr1 = 1 : | attr3 = 0 : 0 | attr3 = 1 : 1 A small program with a main method and a method to read data from les is also available in id3.py: $ python id3.py ../data/train.dat ../data/test.dat attr1 = 0 : | attr2 = 0 : | | attr3 = 0 : 0 | | attr3 = 1 : 1 | attr2 = 1 : 0 attr1 = 1 : | attr3 = 0 : 0 | attr3 = 1 : 1 Accuracy on training set (800 instances): 0.0% Accuracy on test set (203 instances): 0.0% Submit on canvas: A compressed le with all your code and a README le. A le named output.txt with the output of your implementation $ python id3.py ../data/train.dat ../data/test.dat > output.txt 3