decision_trees.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# arff used to read arff file\n",
    "import arff\n",
    "# numpy used for turning list into np array\n",
    "import numpy as np\n",
    "# pandas for creating and manipulating dataframes\n",
    "import pandas as pd\n",
    "# math for basic calculations\n",
    "import math"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def prepare_data(filename):\n",
    "    \"\"\"\n",
    "    Function to transform arff file to pandas dataframe that can be manipulated easily\n",
    "    Only parameter needed is the accessible file name\n",
    "    \"\"\"\n",
    "    # load arff file\n",
    "    data = arff.load(open(filename))\n",
    "    # store arff data as numpy array\n",
    "    data_array = np.array(data['data'])\n",
    "    # create dataframe\n",
    "    dataset = pd.DataFrame(data_array)\n",
    "    # add column names\n",
    "    dataset.columns = ['cap shape', 'cap surface', 'cap color', 'bruises', 'odor', 'gill attachment', 'gill spacing', 'gill size', 'gill color',\n",
    "             'stalk shape', 'stalk root', 'stalk surface above ring', 'stalk surface below ring', 'stalk color above ring',\n",
    "              'stalk color below ring', 'veil type', 'veil color', 'ring number', 'ring type', 'spore print color', 'population','habitat', 'mushroom class']\n",
    "\n",
    "    return dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_unique_count(target_column, return_counts = False):\n",
    "    \"\"\"\n",
    "    Get unique count of an element in first parameter target column\n",
    "    If return_count is true then return the count of each unique element\n",
    "    Sort of copies numpy's unique() function but not as elegantly \n",
    "    \"\"\"\n",
    "    # empty list for unique elements\n",
    "    unique_elements = []\n",
    "    # append unique elements found in target_column into list\n",
    "    for i in target_column:\n",
    "        if i not in unique_elements:\n",
    "            unique_elements.append(i)\n",
    "    \n",
    "    # store as numpy array\n",
    "    unique_elements = np.array(unique_elements)\n",
    "    \n",
    "    # check if we should return element count as well\n",
    "    if return_counts == True:\n",
    "        counter = 0\n",
    "        counts = [0] * len(unique_elements)\n",
    "        \n",
    "        # count elements\n",
    "        for z in unique_elements:\n",
    "            for i in target_column:\n",
    "                if i == z:\n",
    "                    counts[counter] += 1\n",
    "            counter += 1\n",
    "\n",
    "        counts = np.array(counts)\n",
    "        return unique_elements, counts\n",
    "    else:\n",
    "        return unique_elements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_max(array):\n",
    "    \"\"\"\n",
    "    Find index of highest number in array\n",
    "    \"\"\"\n",
    "    current_max = -10000\n",
    "    max_index = 0;\n",
    "    \n",
    "    for i in range(len(array)):\n",
    "        if array[i] > current_max:\n",
    "            max_index = i\n",
    "            current_max = array[i]\n",
    "            \n",
    "    return max_index"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_sum(array):\n",
    "    \"\"\"\n",
    "    Return the sum of an array\n",
    "    \"\"\"\n",
    "    sum = 0\n",
    "    for item in array:\n",
    "        sum += item\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_entropy(feature_column):\n",
    "    \"\"\"\n",
    "    Calculate the entropy of a particular feature column.\n",
    "    Only parameter is a feature column \n",
    "    \"\"\"\n",
    "    # return the unique elements in target column and return the count of them, both come back as numpy array\n",
    "    unique_values, value_counts = get_unique_count(feature_column, return_counts = True)\n",
    "    # incase of 'mushroom class' feature it will return:\n",
    "    # unique_values = [e, p]\n",
    "    # value_counts   = [3916, 4208]    \n",
    "        \n",
    "    # calculate entropy\n",
    "    # loops over all the elements i and sequentially adds them in formula\n",
    "    entropy = 0\n",
    "    for i in range(len(unique_values)):\n",
    "        item_count = (value_counts[i] / get_sum(value_counts))\n",
    "        entropy += (-item_count) * math.log(item_count, 2) \n",
    "    return entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_information_gain(dataset, split_feature_name, target_feature_name = \"mushroom class\"):\n",
    "    \"\"\"\n",
    "    Calculate the information gain of a dataset. This function takes a few parameters:\n",
    "    - dataset = The dataset needed to calculate the information gain of the feature\n",
    "    - split_feature_name = The name of the feature needed to calculate information gain for.\n",
    "    - target_feature_name = The name of the target feature. The default for this is \"mushroom class\"\n",
    "      because that is what i named the column.\n",
    "    \"\"\"\n",
    "    \n",
    "    # first we get the entropy of the total target feature\n",
    "    total_target_entropy = calculate_entropy(dataset[target_feature_name])\n",
    "    \n",
    "    # next we get the values and the value_counts for the split attributes\n",
    "    # as well as dropping any rows which are empty so count is not effected\n",
    "    values, value_counts = get_unique_count(dataset[split_feature_name].dropna(), return_counts = True)\n",
    "    \n",
    "    # calculate the total entropy of the split feature\n",
    "    total_split_entropy = 0\n",
    "    for i in range(len(values)):\n",
    "        # get item count   \n",
    "        item_count = (value_counts[i] / get_sum(value_counts))\n",
    "        \n",
    "        # find next value in feature to calculate while removing the feature being selected\n",
    "        # so it doesnt stay in our feature space\n",
    "        next_feature_value = dataset.where(dataset[split_feature_name] == values[i]).dropna()[target_feature_name]\n",
    "\n",
    "        # add entropy of feature value to total \n",
    "        total_split_entropy += item_count * calculate_entropy(next_feature_value)\n",
    "    \n",
    "    # get the information gain\n",
    "    information_gain = total_target_entropy - total_split_entropy\n",
    "    \n",
    "    return information_gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_tree(dataset, original_dataset, feature_space, target_feature_name = \"mushroom class\", root_node = None):\n",
    "    \"\"\"\n",
    "    Main function to build tree using ID3 algorithm. It has several parameters:\n",
    "    - dataset = the dataset which the ID3 algorithm will run on, at program start it will be the entire\n",
    "        training dataset, but later on it could empty\n",
    "    - original_dataset = Needed to get the mode of the target feature value of the original dataset in\n",
    "        case the dataset delivered by the first parameter is empty (entire training dataset)\n",
    "    - features = The feature space of the dataset. This will be used for the recursive call since during\n",
    "        the tree growing process we have to remove features from our dataset when splitting nodes\n",
    "    - target_feature_name = the name of the target attribute\n",
    "    - parent_node = The parent node when running recursive calls to grow the tree\n",
    "    \"\"\"\n",
    "    \n",
    "    ## Creating Leaf Nodes:\n",
    "    \n",
    "    # only one unique value so we simply return it\n",
    "    unique_target_values = get_unique_count(dataset[target_feature_name])\n",
    "    if len(unique_target_values) == 1:\n",
    "        return unique_target_values[0]\n",
    "    \n",
    "    # when the dataset is empty, we find the mode value in the target feature of the original dataset and return it  \n",
    "    elif len(dataset) == 0:\n",
    "        # get unique values from target column in original dataset\n",
    "        unique_original_data, unique_counts = get_unique_count(original_dataset[target_feature_name], return_counts = True)\n",
    "        # find index of highest unique value\n",
    "        index_of_target_mode = get_max(unique_counts)\n",
    "        # index_of_target_mode = get_max(get_unique_count(original_dataset[target_feature_name], return_counts = True)[1])\n",
    "        return unique_original_data[index_of_target_mode]\n",
    "    \n",
    "    # when there are no features in the feature space simply return the current parent node\n",
    "    elif len(feature_space) == 0:\n",
    "        return root_node\n",
    "    \n",
    "    else:\n",
    "        # set the parent node as the highest count value from the target feature \n",
    "        unique_data_elements = get_unique_count(dataset[target_feature_name])\n",
    "        index_of_target_mode = get_max(get_unique_count(dataset[target_feature_name], return_counts = True)[1])\n",
    "        root_node = unique_data_elements[index_of_target_mode]\n",
    "        # parent node will equal to 'e' from 'mushroom class' in first run\n",
    "\n",
    "        # store information gain of each feature in current feature space \n",
    "        info_gain_values = []\n",
    "        for feature in feature_space:\n",
    "            info_gain_values.append(calculate_information_gain(dataset, feature, target_feature_name))\n",
    "        \n",
    "        \n",
    "        # locate highest valued feature stored in info_gain_values\n",
    "        best_gain_feature_index = get_max(info_gain_values)\n",
    "        best_gain_feature = feature_space[best_gain_feature_index]\n",
    "        \n",
    "        # create the tree structure. The root gets the name of the feature (best_gain_feature) with\n",
    "        # the maximum information gain in the first run ---> 'odor'\n",
    "\n",
    "        current_tree = {best_gain_feature: {} }\n",
    "\n",
    "        # remove the feature with the best information gain from the feature space\n",
    "        features = []\n",
    "        for feature in feature_space:\n",
    "            if feature != best_gain_feature:\n",
    "                features.append(feature)\n",
    "\n",
    "\n",
    "        # create a node for each of the unique values avialable in our best feature\n",
    "        for value in get_unique_count(dataset[best_gain_feature]):\n",
    "            # split the dataset along the value of the feature with the largest information gain \n",
    "            # and there we create sub_datasets to continue building our tree\n",
    "            # we also remove any rows with missing values\n",
    "            unique_value = value\n",
    "            split_dataset = dataset.where(dataset[best_gain_feature] == unique_value).dropna()\n",
    "            \n",
    "            # call the ID3 algorithm for each of those sub_datasets with the new parameters --> here the recursion comes in\n",
    "            split_tree = build_tree(split_dataset, dataset, features, target_feature_name, root_node)\n",
    "            \n",
    "            # add the split tree, grown from the sub_dataset to the tree under the root node\n",
    "            current_tree[best_gain_feature][unique_value] = split_tree\n",
    "\n",
    "            # print(current_tree)\n",
    "            \n",
    "        return current_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(observation, tree):\n",
    "    \"\"\"\n",
    "    \n",
    "    \"\"\"\n",
    "    # the key here is feature name\n",
    "    for key in list(observation.keys()):\n",
    "        # if we find that both our tree and observation contain this key\n",
    "        if key in list(tree.keys()):\n",
    "            # we try to store the resulting key value combo  \n",
    "            try:\n",
    "                result = tree[key][observation[key]] \n",
    "            # otherwise return a one\n",
    "            except:\n",
    "                return 1.0\n",
    "            \n",
    "            result = tree[key][observation[key]]\n",
    "            # check to see if result is a dictionary\n",
    "            if isinstance(result, dict):\n",
    "                # if so we run it again so we can find the value\n",
    "                return predict(observation,result)\n",
    "            else:\n",
    "                return result\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_test_split(dataset):\n",
    "    # using around ~30% (2500) of the data as training data gives a ~75% accuracy measure\n",
    "    # while using ~80% (6500) will give ~55% accuracy\n",
    "    # this looks like overfitting so i might try to find a solution for it\n",
    "    # i chose to stick to 75% accuracy!\n",
    "    \n",
    "    # by resetting the index and dropping the old index we make sure the old index\n",
    "    # doesn't transfer to the new datasets we create and we guarantee no troublesome errors\n",
    "    train_data = dataset.iloc[:2500].reset_index(drop=True)\n",
    "    test_data = dataset.iloc[2500:].reset_index(drop=True)\n",
    "    \n",
    "    return train_data, test_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def k_fold(dataset, index, k):\n",
    "    length = len(dataset)\n",
    "    return dataset[length*(index-1)//k:length*index//k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_accuracy(testing_data, tree):\n",
    "    # remove mushroom class and form new list like observations\n",
    "    observations = testing_data.iloc[:,:-1].to_dict(orient = \"records\")\n",
    "\n",
    "    #Create an empty DataFrame in whose columns the prediction of the tree are stored\n",
    "    predicted = pd.DataFrame(columns=[\"predicted\"]) \n",
    "    \n",
    "    #Calculate the prediction accuracy\n",
    "    for i in range(len(testing_data)):\n",
    "        predicted.loc[i,\"predicted\"] = predict(observations[i],tree) \n",
    "    \n",
    "    # check correctly predicted column with mushroom class column then multiply \n",
    "    accuracy = (get_sum(predicted['predicted'] == testing_data['mushroom class']) / len(testing_data))\n",
    "    return accuracy\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Final Tree:\n",
      "{'odor': {'p': 'p', 'a': 'e', 'l': 'e', 'n': 'e', 'f': 'p', 'c': 'p'}}\n",
      "\n",
      "Accuracy:\n",
      "76.7425 %\n"
     ]
    }
   ],
   "source": [
    "# store data in dataframe\n",
    "dataset = prepare_data('mushroom.arff')\n",
    "\n",
    "# split the dataset into training and testing\n",
    "training_data, testing_data = train_test_split(dataset)\n",
    "\n",
    "# we remove the 'mushroom class' feature when adding the feature space\n",
    "without_mushroom_class = training_data.columns[:-1]\n",
    "\n",
    "# create tree\n",
    "tree = build_tree(training_data, training_data, without_mushroom_class)\n",
    "\n",
    "print(\"\\nFinal Tree:\")\n",
    "print(tree)\n",
    "\n",
    "# test accuracy of tree built\n",
    "print(\"\\nAccuracy:\")\n",
    "accuracy = get_accuracy(testing_data,tree)\n",
    "print(round(accuracy * 100, 4), \"%\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "folds = []\n",
    "folds.append(k_fold(dataset, 1, 3))\n",
    "folds.append(k_fold(dataset, 2, 3))\n",
    "folds.append(k_fold(dataset, 3, 3))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "By using Cross Validation we can improve our accuracy by 20%!\n",
      "\n",
      "{'odor': {'p': 'p', 'a': 'e', 'l': 'e', 'n': {'spore print color': {'n': 'e', 'k': 'e', 'r': 'p', 'w': {'cap color': {'c': 'e', 'w': 'p', 'n': 'e', 'y': 'p', 'p': 'e', 'g': 'e'}}}}, 'f': 'p', 'c': 'p', 'y': 'e', 's': 'e', 'm': 'p'}}\n",
      "\n",
      "\n",
      "95.1625 %\n"
     ]
    }
   ],
   "source": [
    "# fold 1 = training\n",
    "# fold 2 = testing\n",
    "foldsOne = folds[0].reset_index(drop=True)\n",
    "foldsTwo = folds[1].reset_index(drop=True)\n",
    "foldsThree = folds[2].reset_index(drop=True)\n",
    "\n",
    "foldsOneTwo = foldsOne.append(foldsTwo, ignore_index=True)\n",
    "foldsOneThree = foldsOne.append(foldsThree, ignore_index=True)\n",
    "foldsTwoThree = foldsTwo.append(foldsThree, ignore_index=True)\n",
    "\n",
    "# treeOne = build_tree(foldsOneTwo, foldsOneTwo, foldsOneTwo.columns[:-1])\n",
    "treeTwo = build_tree(foldsOneThree, foldsOneThree, foldsOneThree.columns[:-1])\n",
    "# treeThree = build_tree(foldsTwoThree, foldsTwoThree, foldsTwoThree.columns[:-1])\n",
    "\n",
    "# accuracyOne = get_accuracy(foldsThree, treeOne)\n",
    "accuracyTwo = get_accuracy(foldsTwo, treeTwo)\n",
    "# accuracyThree = get_accuracy(foldsOne, treeThree)\n",
    "\n",
    "\n",
    "print(\"By using Cross Validation we can improve our accuracy by 20%!\\n\")\n",
    "print(treeTwo)\n",
    "print(\"\\n\")\n",
    "# print(round(accuracyOne * 100, 4), \"%\")\n",
    "print(round(accuracyTwo * 100, 4), \"%\")\n",
    "# print(round(accuracyThree * 100, 4), \"%\")"
   ]
  },
  {
   "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.7.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}