Assignment2_Final.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Assignment 2: Practical data mining project - Implementing ID3 with an Interactive console#\n",
    "by Luke Crawford (12617306) and Jonathan Rau (13112750)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import torch\n",
    "import numpy as np\n",
    "from skimage import io, transform\n",
    "from math import log\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.preprocessing import LabelEncoder\n",
    "from decimal import Decimal\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction #\n",
    "\n",
    "We decided to implement the Iterative Dichotomiser 3 (ID3) algorithm to create decision tree classifiers. Decision Trees are generally easier to understand for laymen and can be stored in simple data structures. Our goal is to create a simple means to correctly identify if a given mushroom is poisonous or edible, as well as create a readable and simple design for our ID3 algorithm so others can easily understand our code.\n",
    "\n",
    "## Methodology\n",
    "We split our work areas into two: 'Assignment2_Final' (this document) & 'Assignment2_Exploration'. In our Exploration, we explored the data, constructed our algorithm, compared to other methods, ran tests and attempted to build a dictionary for users to easily interact with the data. Assignment2_Final (this document) is the final product which we have developed, including this report, our most recent up to date version of the ID3 algorithm and an interactive console which users can use to build ID3 Decision trees and use their own datasets if they so wish.\n",
    "\n",
    "## The ID3 Algorithm\n",
    "\n",
    "### Data Structure\n",
    "\n",
    "The decision tree is designed using the object-oriented programming methodology. Nodes are objects of the decision tree, where each node holds references to its children. As we never traverse the tree from a leaf to the top, we don't store the reference of the parent for each node, which creates spatial efficiency in the tree compared to other ID3 algorithms. Additionally, it is not necessary to retrieve a certain node without traversing the tree beginning from the root. Therefore, we did not need to use a datastructure like an array to store all nodes, which would provide random element reading with O(1) complexity.\n",
    "However, the lookup time complexity to get a specific child of a node is important to make a fast prediction. Hence, we store all children of a node in a dictionary as a member of the node with the branch value as a key.\n",
    "\n",
    "\n",
    "## Video Presentation\n",
    "Please see the video presentation linked here:\n",
    "https://www.youtube.com/watch?v=1C7Dq4cbfsg\n",
    "\n",
    "If there are any problems viewing the video presentation, contact luke.crawford@student.uts.edu.au\n",
    "\n",
    "## GitHub\n",
    "Please see our GitHub page linked here for the resources used:\n",
    "https://github.com/badookey/MushroomID3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision Tree Classifier Source Code\n",
    "## Node class"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeNode:\n",
    "    def __init__(self):\n",
    "        self.children= dict()\n",
    "    \n",
    "    def add_child(self, child_key, child_value):\n",
    "        self.children[child_key] = child_value\n",
    "        \n",
    "    def get_children(self):\n",
    "        return self.children\n",
    "    \n",
    "    def get_attribute(self):\n",
    "        return self.attribute\n",
    "    \n",
    "    def set_attribute(self, attribute):\n",
    "        self.attribute = attribute\n",
    "        \n",
    "    def set_label(self, label):\n",
    "        self.label=label\n",
    "    \n",
    "    def get_label(self):\n",
    "        return self.label\n",
    "    \n",
    "    def __str__(self, level=1):\n",
    "        text=\"\"\n",
    "        if hasattr(self, 'label'):\n",
    "            text += \"leaf: label = {}\".format(self.label)\n",
    "        else:\n",
    "            text += \"split {}, descendants(\".format(self.attribute)\n",
    "            for value, child in self.children.items():\n",
    "                text += \"\\n\"+\"   \"*level+\"branch = {}, child node:{}\".format(value, child.__str__(level+1))\n",
    "            \n",
    "            text += \")\"\n",
    "        return text"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Representation of the dataset\n",
    "\n",
    "We are using the Pandas library to represent the dataset in collections of dataframes and series. For our usage, the biggest advantage of pandas is the ease of data column labelling. This allows us to easily access certain values and present the results in human readable format (no column indexes) without implementing a column-header list to map an index to a name.\n",
    "\n",
    "Pandas provides a simple method to load the data from a csv file. Additionally, we are splitting the data into training and testing datasets using the train_test_split method from the sklearn package."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def load_data(path, header_included_):\n",
    "    if header_included_:\n",
    "        data = pd.read_csv(path)\n",
    "    else:\n",
    "        data = pd.read_csv(path, header=None)\n",
    "        add_default = read_Bool(\"Do you want to add the default mushroom header? (True/False)\")\n",
    "        if add_default:\n",
    "            assign_mushroom_header(data)\n",
    "        \n",
    "        \n",
    "    return data\n",
    "\n",
    "def assign_mushroom_header(dataframe_):\n",
    "    #Input column names from Mushroom Attributes.txt\n",
    "    columns=['class','cap-shape','cap-surface','cap-color','bruises','odor','gill-attachment','gill-spacing','gill-size','gill-color','stalk-shape','stalk-root','stalk-surface-above-ring','stalk-surface-below-ring','stalk-color-above-ring','stalk-color-below-ring','veil-type','veil-color','ring-number','ring-type','spore-print-color','population','habitat']\n",
    "\n",
    "    #Rename columns according to their real attributes\n",
    "    dataframe_.set_axis(columns, axis='columns', inplace=True)\n",
    "    \n",
    "def split_data(dataframe_, test_size_, label_position):\n",
    "    \n",
    "    indexes = extract_attribute_set(dataframe_, label_position)\n",
    "    #y is our target class\n",
    "    #y = dataframe_.iloc[:,label_position]\n",
    "    #indexes = [i for i in range(dataframe_.columns.size) if i != label_position]\n",
    "    #x is our attributes\n",
    "    #x = dataframe_.iloc[:,indexes]\n",
    "    \n",
    "    #x_train_, x_test_, y_train_, y_test_ = train_test_split(x,y,test_size = test_size_)\n",
    "    train_, test_ = train_test_split(dataframe_, test_size = test_size_)\n",
    "    \n",
    "    \n",
    "    y_train_ = train_.iloc[:,label_position]\n",
    "    y_test_ = test_.iloc[:,label_position]\n",
    "    x_train_ = train_.loc[:,indexes]\n",
    "    x_test_ = test_.loc[:,indexes]\n",
    "    return y_train_, x_train_, y_test_, x_test_\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def extract_attribute_set(dataframe_, label_position_):\n",
    "    indexes = [i for i in range(dataframe_.columns.size) if i != label_position_]\n",
    "    x = dataframe_.iloc[:,indexes]\n",
    "    return set(x.columns.values.tolist())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Performance of Statistical methods\n",
    "\n",
    "As the dataset is divided into subsets to calculate the information gain very often, keeping the target value separate from the attribute values would lead to a large decrease in performance. The subset of the attribute values would have to be joined with the target values for each computation of the information gain for a split attribute. This would be a computational overkill due to it's high time and space complexity. Keeping the attribute and target values together enables us to create subsets of the data based on the attributes in one shot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(target_):\n",
    "    h = 0\n",
    "    for label_ in target_.unique():\n",
    "        h += -((target_[target_==label_].size / target_.size)* log(target_[target_==label_].size / target_.size, 2))\n",
    "    return h\n",
    "\n",
    "def determine_split_attribute(data_, label_position_, attributes_):\n",
    "    best_attribute_ = None\n",
    "    best_gain_ = 0\n",
    "    base_entropy_ = entropy(data_.iloc[:,label_position_])\n",
    "    for attribute_ in attributes_:\n",
    "        x_select_ = data_.loc[:,[attribute_, data_.columns[label_position_]]]\n",
    "        information_gain_ = base_entropy_\n",
    "        for value_ in x_select_.loc[:,attribute_].unique():\n",
    "            #split_ = pd.concat([x_select_[x_select_==value_], target_], axis=1, join='inner')\n",
    "            split_entropy_ = entropy(x_select_.iloc[:,label_position_])\n",
    "            information_gain_ -= split_entropy_ * (x_select_.size / data_.size)\n",
    "        \n",
    "        if information_gain_ >= best_gain_:\n",
    "            best_attribute_ = attribute_\n",
    "            best_gain = information_gain_\n",
    "            \n",
    "    return best_attribute_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Structure of the ID3 algorithm\n",
    "\n",
    "We implemented the ID3 algorithm in an recursive approach. The algorithm splits the data based on the attribute which leads to the highest information gain and performs a recursive call to create the child nodes. The Terminate condition for the recursion is reached when the subset contains one or less categories of target values. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#param attributes_ should be a set of attributes\n",
    "#param target_ should be a series (like y_train)\n",
    "#param data_ should be a dataframe (like x_train)\n",
    "def build_decision_tree(data_, attributes_, label_position_):\n",
    "    node_ = DecisionTreeNode()\n",
    "    if data_.iloc[:,label_position_].unique().size==1:\n",
    "        node_.set_label(data_.iloc[0,label_position_])\n",
    "        return node_\n",
    "        \n",
    "    if len(attributes_) == 0:\n",
    "        node_.set_label(data_.iloc[:,label_position_].value_counts().head(1).last_valid_index())\n",
    "        return node_\n",
    "        \n",
    "    else:\n",
    "        split_attribute_ = determine_split_attribute(data_, label_position_, attributes_)\n",
    "        print('splitting on: {}'.format(split_attribute_))\n",
    "        node_.set_attribute(split_attribute_)\n",
    "        split_select_ = data_.loc[:,split_attribute_]\n",
    "        for split_value_ in split_select_.unique():\n",
    "            child_data_ = data_[data_[split_attribute_] == split_value_]\n",
    "            child_attributes_ = attributes_\n",
    "            child_attributes_.remove(split_attribute_)\n",
    "            #print('child_attributes: {}'.format(child_attributes_))\n",
    "            node_.add_child(split_value_, build_decision_tree(child_data_,child_attributes_, label_position_))\n",
    "            #print('currend subtree: {}'.format(node_))\n",
    "            \n",
    "            #as we are handling references, we have to add the attribut again\n",
    "            child_attributes_.add(split_attribute_)\n",
    "            \n",
    "    return node_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Predicting Data\n",
    "\n",
    "Making predictions is done by traversing the tree, deciding which path to follow based on the attribute values until finding an end leaf.  There is one edge case on the mushroom dataset, where an attribute's value was not present in the training set. We simply choose the children on a pseudorandom basis (which makes the ordering of the data structure not always the same on multiple run-throughs).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "#data should be a dataframe (like x_train)\n",
    "#root should be a a DecisionTreeNode (returned from build_decision_tree)\n",
    "def make_prediction(root, data):\n",
    "    predictions = dict()\n",
    "    for i, point in data.iterrows():\n",
    "        current_node_ = root\n",
    "        not_predicted = True\n",
    "        while not_predicted:\n",
    "            if(hasattr(current_node_, 'label')):\n",
    "                predictions[i]=current_node_.get_label()\n",
    "                not_predicted = False\n",
    "            else:\n",
    "                split_value = point[current_node_.get_attribute()]\n",
    "                try:\n",
    "                    current_node_ = current_node_.get_children()[split_value]\n",
    "                except KeyError:\n",
    "                    current_node_ = list(current_node_.get_children().values())[0]\n",
    "    #wrap the result in a Series to make the calculation of the accuracy easier\n",
    "    result = pd.Series(predictions)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Creating an interface\n",
    "\n",
    "We wrap the methods build_decision_tree and make_predictions in a class to provide an interface, which provides methods with a standard method signature."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DecisionTreeClassifier:\n",
    "    def fit(self, label_, values_, label_position_):\n",
    "        data_ = pd.concat([label_,values_], axis=1)\n",
    "        self.tree=build_decision_tree(data_, extract_attribute_set(data_, label_position_), label_position_)\n",
    "        \n",
    "    def predict(self, data_):\n",
    "        return make_prediction(self.tree, data_)\n",
    "    \n",
    "    def print_model(self):\n",
    "        print(self.tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_accuracy(real_values, predicted_values):\n",
    "    stats= pd.crosstab(index = predicted_values, columns=real_values, margins=True, rownames= ['predicted'], colnames=['actual'])\n",
    "    accuracy = np.sum(real_values == predicted_values) / predicted_values.size\n",
    "    print(stats)\n",
    "    print(\"The accuracy is: {}\".format(accuracy))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Command Line Interface Functions ##\n",
    "The following code is simply to provide a command line to end users in order to construct their own ID3 Decision Trees and provide their own datasets to use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def read_Bool(msg):\n",
    "    text = input(msg)\n",
    "    if text == \"True\":\n",
    "        text = True\n",
    "    elif text == \"False\":\n",
    "        text = False\n",
    "    else:\n",
    "        return read_Bool(msg)\n",
    "    return text\n",
    "def read_float(msg):\n",
    "    try:\n",
    "        d = float(input(msg))\n",
    "    except:\n",
    "        print(\"invalid input, please try again\")\n",
    "        read_float(msg)\n",
    "    if 0<d<1:\n",
    "        return d\n",
    "    print(\"the relative size has to be between 0.0 and 1.0\")\n",
    "    read_float(msg)\n",
    "    \n",
    "def read_int(msg):\n",
    "    try:\n",
    "        i = int(input(msg))\n",
    "    except:\n",
    "        print(\"invalid input, please try again\")\n",
    "        read_int(msg)\n",
    "    return i\n",
    "    \n",
    "def main():\n",
    "    path = input(\"enter the absolute path of the dataset: \")\n",
    "    header_included = read_Bool(\"is the header included in the dataset?: (True/False)\")\n",
    "    data = load_data(path, header_included)\n",
    "    split_size = read_float(\"enter the relative size of the test set: \")\n",
    "    model = DecisionTreeClassifier()\n",
    "    label_position = read_int(\"enter the position of the class label in the dataset: \")\n",
    "    y_train, x_train, y_test, x_test = split_data(data, split_size, label_position)\n",
    "    print(\"Training the model\")\n",
    "    model.fit(y_train, x_train, label_position)\n",
    "    print('your model: \\n\\n')\n",
    "    model.print_model()\n",
    "    print(\"\\n\\nevaluating on test set:\")\n",
    "    predict = model.predict(x_test)\n",
    "    print('\\n\\n')\n",
    "    print_accuracy(y_test, predict)\n",
    "    \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Command Line Interface ##\n",
    "Simply type main() in order to access the command line.\n",
    "\n",
    "Please note the example (In [13]), which has an accuracy of 99.87%\n",
    "\n",
    "|          | Exploration (Neural Network) | Final (ID3) |\n",
    "|----------|------------------|-------------|\n",
    "| Accuracy | 93%              | 99.8%       |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "enter the absolute path of the dataset: Data/Mushrooms.txt\n",
      "is the header included in the dataset?: (True/False)False\n",
      "Do you want to add the default mushroom header? (True/False)True\n",
      "enter the relative size of the test set: 0.4\n",
      "enter the position of the class label in the dataset: 0\n",
      "Training the model\n",
      "splitting on: cap-shape\n",
      "splitting on: ring-type\n",
      "splitting on: stalk-root\n",
      "splitting on: habitat\n",
      "splitting on: stalk-surface-above-ring\n",
      "splitting on: gill-attachment\n",
      "splitting on: stalk-surface-below-ring\n",
      "splitting on: veil-color\n",
      "splitting on: ring-number\n",
      "splitting on: spore-print-color\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: gill-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: gill-color\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: habitat\n",
      "splitting on: stalk-root\n",
      "splitting on: stalk-surface-above-ring\n",
      "splitting on: habitat\n",
      "splitting on: ring-type\n",
      "splitting on: stalk-root\n",
      "splitting on: habitat\n",
      "splitting on: stalk-surface-above-ring\n",
      "splitting on: gill-attachment\n",
      "splitting on: stalk-surface-below-ring\n",
      "splitting on: veil-color\n",
      "splitting on: ring-number\n",
      "splitting on: spore-print-color\n",
      "splitting on: gill-size\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: habitat\n",
      "splitting on: stalk-surface-above-ring\n",
      "splitting on: gill-attachment\n",
      "splitting on: stalk-surface-below-ring\n",
      "splitting on: veil-color\n",
      "splitting on: ring-number\n",
      "splitting on: spore-print-color\n",
      "splitting on: gill-color\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: gill-size\n",
      "splitting on: cap-color\n",
      "splitting on: gill-color\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: stalk-shape\n",
      "splitting on: odor\n",
      "splitting on: stalk-root\n",
      "splitting on: stalk-surface-above-ring\n",
      "splitting on: gill-color\n",
      "splitting on: ring-type\n",
      "splitting on: stalk-root\n",
      "splitting on: stalk-surface-above-ring\n",
      "splitting on: habitat\n",
      "splitting on: stalk-root\n",
      "splitting on: habitat\n",
      "splitting on: ring-type\n",
      "splitting on: stalk-root\n",
      "splitting on: stalk-surface-above-ring\n",
      "your model: \n",
      "\n",
      "\n",
      "split cap-shape, descendants(\n",
      "   branch = f, child node:split ring-type, descendants(\n",
      "      branch = p, child node:split stalk-root, descendants(\n",
      "         branch = e, child node:split habitat, descendants(\n",
      "            branch = u, child node:split stalk-surface-above-ring, descendants(\n",
      "               branch = s, child node:split gill-attachment, descendants(\n",
      "                  branch = f, child node:split stalk-surface-below-ring, descendants(\n",
      "                     branch = s, child node:split veil-color, descendants(\n",
      "                        branch = w, child node:split ring-number, descendants(\n",
      "                           branch = o, child node:split spore-print-color, descendants(\n",
      "                              branch = k, child node:split gill-size, descendants(\n",
      "                                 branch = n, child node:split cap-color, descendants(\n",
      "                                    branch = n, child node:split gill-color, descendants(\n",
      "                                       branch = p, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = p, child node:leaf: label = p\n",
      "                                             branch = n, child node:leaf: label = e))\n",
      "                                       branch = k, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = n, child node:leaf: label = e\n",
      "                                             branch = p, child node:leaf: label = p))\n",
      "                                       branch = g, child node:leaf: label = e\n",
      "                                       branch = w, child node:leaf: label = p\n",
      "                                       branch = n, child node:leaf: label = p)\n",
      "                                    branch = w, child node:leaf: label = p\n",
      "                                    branch = g, child node:leaf: label = e))\n",
      "                              branch = n, child node:split gill-color, descendants(\n",
      "                                 branch = n, child node:split gill-size, descendants(\n",
      "                                    branch = n, child node:split cap-color, descendants(\n",
      "                                       branch = g, child node:leaf: label = e\n",
      "                                       branch = w, child node:leaf: label = p\n",
      "                                       branch = n, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = p, child node:leaf: label = p\n",
      "                                             branch = n, child node:leaf: label = e))))\n",
      "                                 branch = w, child node:leaf: label = p\n",
      "                                 branch = g, child node:leaf: label = e\n",
      "                                 branch = p, child node:split gill-size, descendants(\n",
      "                                    branch = n, child node:split cap-color, descendants(\n",
      "                                       branch = n, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = p, child node:leaf: label = p\n",
      "                                             branch = n, child node:leaf: label = e))\n",
      "                                       branch = w, child node:leaf: label = p))\n",
      "                                 branch = k, child node:split gill-size, descendants(\n",
      "                                    branch = n, child node:split cap-color, descendants(\n",
      "                                       branch = w, child node:leaf: label = p\n",
      "                                       branch = n, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = n, child node:leaf: label = e\n",
      "                                             branch = p, child node:leaf: label = p))\n",
      "                                       branch = g, child node:leaf: label = e)))))))))\n",
      "            branch = g, child node:leaf: label = p)\n",
      "         branch = b, child node:split habitat, descendants(\n",
      "            branch = d, child node:leaf: label = e\n",
      "            branch = p, child node:leaf: label = e\n",
      "            branch = g, child node:leaf: label = p\n",
      "            branch = u, child node:leaf: label = p\n",
      "            branch = l, child node:leaf: label = p\n",
      "            branch = m, child node:leaf: label = p)\n",
      "         branch = ?, child node:leaf: label = e\n",
      "         branch = r, child node:leaf: label = e)\n",
      "      branch = e, child node:split stalk-root, descendants(\n",
      "         branch = ?, child node:split stalk-surface-above-ring, descendants(\n",
      "            branch = s, child node:split habitat, descendants(\n",
      "               branch = d, child node:leaf: label = p\n",
      "               branch = w, child node:leaf: label = e\n",
      "               branch = p, child node:leaf: label = p\n",
      "               branch = l, child node:leaf: label = p)\n",
      "            branch = k, child node:leaf: label = p)\n",
      "         branch = e, child node:leaf: label = e\n",
      "         branch = b, child node:leaf: label = e\n",
      "         branch = c, child node:leaf: label = p)\n",
      "      branch = l, child node:leaf: label = p\n",
      "      branch = f, child node:leaf: label = e\n",
      "      branch = n, child node:leaf: label = p)\n",
      "   branch = x, child node:split ring-type, descendants(\n",
      "      branch = p, child node:split stalk-root, descendants(\n",
      "         branch = b, child node:split habitat, descendants(\n",
      "            branch = d, child node:split stalk-surface-above-ring, descendants(\n",
      "               branch = s, child node:split gill-attachment, descendants(\n",
      "                  branch = f, child node:split stalk-surface-below-ring, descendants(\n",
      "                     branch = s, child node:split veil-color, descendants(\n",
      "                        branch = w, child node:split ring-number, descendants(\n",
      "                           branch = o, child node:split spore-print-color, descendants(\n",
      "                              branch = k, child node:split gill-size, descendants(\n",
      "                                 branch = b, child node:leaf: label = e\n",
      "                                 branch = n, child node:leaf: label = p)\n",
      "                              branch = n, child node:split gill-size, descendants(\n",
      "                                 branch = b, child node:leaf: label = e\n",
      "                                 branch = n, child node:split cap-color, descendants(\n",
      "                                    branch = w, child node:split stalk-shape, descendants(\n",
      "                                       branch = e, child node:leaf: label = p\n",
      "                                       branch = t, child node:leaf: label = e)\n",
      "                                    branch = g, child node:leaf: label = p\n",
      "                                    branch = p, child node:leaf: label = p\n",
      "                                    branch = y, child node:leaf: label = e))\n",
      "                              branch = u, child node:leaf: label = e)))))\n",
      "               branch = y, child node:leaf: label = e)\n",
      "            branch = g, child node:leaf: label = p\n",
      "            branch = u, child node:leaf: label = p\n",
      "            branch = p, child node:leaf: label = e)\n",
      "         branch = c, child node:leaf: label = e\n",
      "         branch = e, child node:split habitat, descendants(\n",
      "            branch = u, child node:split stalk-surface-above-ring, descendants(\n",
      "               branch = s, child node:split gill-attachment, descendants(\n",
      "                  branch = f, child node:split stalk-surface-below-ring, descendants(\n",
      "                     branch = s, child node:split veil-color, descendants(\n",
      "                        branch = w, child node:split ring-number, descendants(\n",
      "                           branch = o, child node:split spore-print-color, descendants(\n",
      "                              branch = n, child node:split gill-color, descendants(\n",
      "                                 branch = n, child node:split gill-size, descendants(\n",
      "                                    branch = n, child node:split cap-color, descendants(\n",
      "                                       branch = w, child node:leaf: label = p\n",
      "                                       branch = n, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = n, child node:leaf: label = e\n",
      "                                             branch = p, child node:leaf: label = p))\n",
      "                                       branch = g, child node:leaf: label = e))\n",
      "                                 branch = p, child node:split gill-size, descendants(\n",
      "                                    branch = n, child node:split cap-color, descendants(\n",
      "                                       branch = g, child node:leaf: label = e\n",
      "                                       branch = n, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = n, child node:leaf: label = e\n",
      "                                             branch = p, child node:leaf: label = p))\n",
      "                                       branch = w, child node:leaf: label = p))\n",
      "                                 branch = g, child node:leaf: label = e\n",
      "                                 branch = k, child node:split gill-size, descendants(\n",
      "                                    branch = n, child node:split cap-color, descendants(\n",
      "                                       branch = n, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = p, child node:leaf: label = p\n",
      "                                             branch = n, child node:leaf: label = e))\n",
      "                                       branch = g, child node:leaf: label = e\n",
      "                                       branch = w, child node:leaf: label = p))\n",
      "                                 branch = w, child node:leaf: label = p)\n",
      "                              branch = k, child node:split gill-size, descendants(\n",
      "                                 branch = n, child node:split cap-color, descendants(\n",
      "                                    branch = g, child node:leaf: label = e\n",
      "                                    branch = w, child node:leaf: label = p\n",
      "                                    branch = n, child node:split gill-color, descendants(\n",
      "                                       branch = p, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = p, child node:leaf: label = p\n",
      "                                             branch = n, child node:leaf: label = e))\n",
      "                                       branch = w, child node:leaf: label = p\n",
      "                                       branch = n, child node:split stalk-shape, descendants(\n",
      "                                          branch = e, child node:split odor, descendants(\n",
      "                                             branch = p, child node:leaf: label = p\n",
      "                                             branch = n, child node:leaf: label = e))\n",
      "                                       branch = g, child node:leaf: label = e\n",
      "                                       branch = k, child node:leaf: label = p)))))))))\n",
      "            branch = g, child node:leaf: label = p)\n",
      "         branch = ?, child node:leaf: label = e\n",
      "         branch = r, child node:leaf: label = e)\n",
      "      branch = e, child node:split stalk-root, descendants(\n",
      "         branch = ?, child node:split stalk-surface-above-ring, descendants(\n",
      "            branch = k, child node:leaf: label = p\n",
      "            branch = s, child node:split gill-color, descendants(\n",
      "               branch = b, child node:leaf: label = p\n",
      "               branch = e, child node:leaf: label = e\n",
      "               branch = w, child node:leaf: label = e))\n",
      "         branch = e, child node:leaf: label = e\n",
      "         branch = b, child node:leaf: label = e)\n",
      "      branch = l, child node:leaf: label = p\n",
      "      branch = f, child node:leaf: label = e\n",
      "      branch = n, child node:leaf: label = p)\n",
      "   branch = k, child node:split ring-type, descendants(\n",
      "      branch = e, child node:split stalk-root, descendants(\n",
      "         branch = ?, child node:split stalk-surface-above-ring, descendants(\n",
      "            branch = k, child node:leaf: label = p\n",
      "            branch = s, child node:split habitat, descendants(\n",
      "               branch = l, child node:leaf: label = p\n",
      "               branch = p, child node:leaf: label = p\n",
      "               branch = d, child node:leaf: label = p\n",
      "               branch = w, child node:leaf: label = e))\n",
      "         branch = b, child node:leaf: label = e\n",
      "         branch = c, child node:leaf: label = p)\n",
      "      branch = p, child node:split stalk-root, descendants(\n",
      "         branch = b, child node:split habitat, descendants(\n",
      "            branch = d, child node:leaf: label = e\n",
      "            branch = l, child node:leaf: label = p)\n",
      "         branch = ?, child node:leaf: label = e)\n",
      "      branch = n, child node:leaf: label = p)\n",
      "   branch = b, child node:split ring-type, descendants(\n",
      "      branch = p, child node:split stalk-root, descendants(\n",
      "         branch = c, child node:leaf: label = e\n",
      "         branch = ?, child node:leaf: label = e\n",
      "         branch = b, child node:split stalk-surface-above-ring, descendants(\n",
      "            branch = s, child node:leaf: label = p\n",
      "            branch = y, child node:leaf: label = e))\n",
      "      branch = e, child node:leaf: label = p)\n",
      "   branch = s, child node:leaf: label = e\n",
      "   branch = c, child node:leaf: label = p)\n",
      "\n",
      "\n",
      "evaluating on test set:\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "\n",
      "actual        e     p   All\n",
      "predicted                  \n",
      "e          1713     0  1713\n",
      "p             4  1533  1537\n",
      "All        1717  1533  3250\n",
      "The accuracy is: 0.9987692307692307\n"
     ]
    }
   ],
   "source": [
    "main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "main()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusion \n",
    "In conclusion, the above ID3 implementation is a concise and simple interactive program which allows anyone to classify data efficiently and easily. The design of the code and command-line make it so anyone can modify the algorithm to their particular needs with ease. This is due to the object oriented design of the code and the simple, but powerful commands of the interface. Anyone can use any"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}