07-decision-tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Entropy Application: Decision Tree Classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Source"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See the excellent article here: https://www.python-course.eu/Decision_Trees.php"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "from pprint import pprint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = pd.read_csv('data/zoo.data',\n",
    "                      names=['animal_name','hair','feathers','eggs','milk',\n",
    "                             'airbone','aquatic','predator','toothed','backbone',\n",
    "                             'breathes','venomous','fins','legs','tail','domestic','catsize','class',])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>animal_name</th>\n",
       "      <th>hair</th>\n",
       "      <th>feathers</th>\n",
       "      <th>eggs</th>\n",
       "      <th>milk</th>\n",
       "      <th>airbone</th>\n",
       "      <th>aquatic</th>\n",
       "      <th>predator</th>\n",
       "      <th>toothed</th>\n",
       "      <th>backbone</th>\n",
       "      <th>breathes</th>\n",
       "      <th>venomous</th>\n",
       "      <th>fins</th>\n",
       "      <th>legs</th>\n",
       "      <th>tail</th>\n",
       "      <th>domestic</th>\n",
       "      <th>catsize</th>\n",
       "      <th>class</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>aardvark</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>antelope</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>bass</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>bear</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>boar</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>...</th>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "      <td>...</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>96</th>\n",
       "      <td>wallaby</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>97</th>\n",
       "      <td>wasp</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>6</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>6</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>98</th>\n",
       "      <td>wolf</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>99</th>\n",
       "      <td>worm</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>7</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>100</th>\n",
       "      <td>wren</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>2</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "<p>101 rows × 18 columns</p>\n",
       "</div>"
      ],
      "text/plain": [
       "    animal_name  hair  feathers  eggs  milk  airbone  aquatic  predator  \\\n",
       "0      aardvark     1         0     0     1        0        0         1   \n",
       "1      antelope     1         0     0     1        0        0         0   \n",
       "2          bass     0         0     1     0        0        1         1   \n",
       "3          bear     1         0     0     1        0        0         1   \n",
       "4          boar     1         0     0     1        0        0         1   \n",
       "..          ...   ...       ...   ...   ...      ...      ...       ...   \n",
       "96      wallaby     1         0     0     1        0        0         0   \n",
       "97         wasp     1         0     1     0        1        0         0   \n",
       "98         wolf     1         0     0     1        0        0         1   \n",
       "99         worm     0         0     1     0        0        0         0   \n",
       "100        wren     0         1     1     0        1        0         0   \n",
       "\n",
       "     toothed  backbone  breathes  venomous  fins  legs  tail  domestic  \\\n",
       "0          1         1         1         0     0     4     0         0   \n",
       "1          1         1         1         0     0     4     1         0   \n",
       "2          1         1         0         0     1     0     1         0   \n",
       "3          1         1         1         0     0     4     0         0   \n",
       "4          1         1         1         0     0     4     1         0   \n",
       "..       ...       ...       ...       ...   ...   ...   ...       ...   \n",
       "96         1         1         1         0     0     2     1         0   \n",
       "97         0         0         1         1     0     6     0         0   \n",
       "98         1         1         1         0     0     4     1         0   \n",
       "99         0         0         1         0     0     0     0         0   \n",
       "100        0         1         1         0     0     2     1         0   \n",
       "\n",
       "     catsize  class  \n",
       "0          1      1  \n",
       "1          1      1  \n",
       "2          0      4  \n",
       "3          1      1  \n",
       "4          1      1  \n",
       "..       ...    ...  \n",
       "96         1      1  \n",
       "97         0      6  \n",
       "98         1      1  \n",
       "99         0      7  \n",
       "100        0      2  \n",
       "\n",
       "[101 rows x 18 columns]"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = dataset.drop('animal_name',axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(target_col):\n",
    "    elements, counts = np.unique(target_col,return_counts = True)\n",
    "    \n",
    "    \n",
    "    # entropy = np.sum([(-counts[i]/np.sum(counts))*np.log2(counts[i]/np.sum(counts)) for i in range(len(elements))])\n",
    "    \n",
    "    \n",
    "    entropy = np.sum(  \n",
    "                      [ \n",
    "                         \n",
    "                        ( - counts[i] / np.sum(counts))    \n",
    "                         * np.log2( counts[i] / np.sum(counts)  \n",
    "                        )        \n",
    "                        ## Above two lines are just:  -p * lg(p)\n",
    "                         \n",
    "                        for i in range(len(elements))\n",
    "                         \n",
    "                        ## Do this for all elements \n",
    "                      ]     \n",
    "                    )\n",
    "    return entropy\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "def InfoGain(data,split_attribute_name,target_name=\"class\"): \n",
    "    #Calculate the entropy of the total dataset\n",
    "    total_entropy = entropy(data[target_name])\n",
    "    \n",
    "    ##Calculate the entropy of the dataset\n",
    "    \n",
    "    #Calculate the values and the corresponding counts for the split attribute \n",
    "    vals, counts= np.unique(data[split_attribute_name],return_counts=True)\n",
    "    \n",
    "    #Calculate the weighted entropy\n",
    "    Weighted_Entropy = np.sum([(counts[i]/np.sum(counts))*entropy(data.where(data[split_attribute_name]==vals[i]).dropna()[target_name]) for i in range(len(vals))])\n",
    "    \n",
    "    #Calculate the information gain\n",
    "    Information_Gain = total_entropy - Weighted_Entropy\n",
    "    return Information_Gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max   : 27\n",
      "Argmax: 2\n"
     ]
    }
   ],
   "source": [
    "dummy_vals = [1, 3, 27, 5, 6, 1, 2, 5 , 7, 12, 4]\n",
    "print(\"Max   :\", max(dummy_vals))\n",
    "print(\"Argmax:\", np.argmax(dummy_vals))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ID3(data,originaldata,features,target_attribute_name=\"class\",parent_node_class = None):   \n",
    "    #If all target_values have the same value, return this value\n",
    "    if len(np.unique(data[target_attribute_name])) <= 1:\n",
    "        return np.unique(data[target_attribute_name])[0]\n",
    "    \n",
    "    #If the dataset is empty, return the mode target feature value in the original dataset\n",
    "    elif len(data)==0:\n",
    "        return np.unique(originaldata[target_attribute_name])[np.argmax(np.unique(originaldata[target_attribute_name],return_counts=True)[1])]\n",
    "    \n",
    "  \n",
    "    elif len(features) ==0:\n",
    "        return parent_node_class\n",
    "    \n",
    "    #If none of the above holds true, grow the tree!\n",
    "    \n",
    "    else:\n",
    "        #Set the default value for this node --> The mode target feature value of the current node\n",
    "        parent_node_class = np.unique(data[target_attribute_name])[np.argmax(np.unique(data[target_attribute_name],return_counts=True)[1])]\n",
    "        \n",
    "        #Select the feature which best splits the dataset\n",
    "        item_values = [InfoGain(data,feature,target_attribute_name) for feature in features] #Return the information gain values for the features in the dataset\n",
    "        best_feature_index = np.argmax(item_values)\n",
    "        best_feature = features[best_feature_index]\n",
    "        \n",
    "        #Create the tree structure. The root gets the name of the feature (best_feature) with the maximum information\n",
    "        #gain in the first run\n",
    "        tree = {best_feature:{}}\n",
    "        \n",
    "        \n",
    "        #Remove the feature with the best inforamtion gain from the feature space\n",
    "        features = [i for i in features if i != best_feature]\n",
    "        \n",
    "        #Grow a branch under the root node for each possible value of the root node feature\n",
    "        \n",
    "        for value in np.unique(data[best_feature]):\n",
    "            value = value\n",
    "            #Split the dataset along the value of the feature with the largest information gain and therwith create sub_datasets\n",
    "            sub_data = data.where(data[best_feature] == value).dropna()\n",
    "            \n",
    "            #Call the ID3 algorithm for each of those sub_datasets with the new parameters --> Here the recursion comes in!\n",
    "            subtree = ID3(sub_data,dataset,features,target_attribute_name,parent_node_class)\n",
    "            \n",
    "            #Add the sub tree, grown from the sub_dataset to the tree under the root node\n",
    "            tree[best_feature][value] = subtree\n",
    "            \n",
    "        return(tree)    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(query,tree,default = 1):\n",
    "    for key in list(query.keys()):\n",
    "        if key in list(tree.keys()):\n",
    "            #2.\n",
    "            try:\n",
    "                result = tree[key][query[key]] \n",
    "            except:\n",
    "                return default\n",
    "  \n",
    "            #3.\n",
    "            result = tree[key][query[key]]\n",
    "            #4.\n",
    "            if isinstance(result,dict):\n",
    "                return predict(query,result)\n",
    "\n",
    "            else:\n",
    "                return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_test_split(dataset):\n",
    "    training_data = dataset.iloc[:80].reset_index(drop=True)    #We drop the index respectively relabel the index\n",
    "\n",
    "    testing_data = dataset.iloc[80:].reset_index(drop=True)\n",
    "    return training_data,testing_data\n",
    "\n",
    "training_data = train_test_split(dataset)[0]\n",
    "testing_data = train_test_split(dataset)[1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def test(data,tree):\n",
    "    #Create new query instances by simply removing the target feature column from the original dataset and \n",
    "    #convert it to a dictionary\n",
    "    \n",
    "    queries = data.iloc[:,:-1].to_dict(orient = \"records\")\n",
    "    \n",
    "    #Create a 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(data)):\n",
    "        predicted.loc[i,\"predicted\"] = predict(queries[i],tree,1.0) \n",
    "    print('The prediction accuracy is: ',(np.sum(predicted[\"predicted\"] == data[\"class\"])/len(data))*100,'%')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'legs': {0: {'fins': {0.0: {'toothed': {0.0: 7.0, 1.0: 3.0}},\n",
      "                       1.0: {'eggs': {0.0: 1.0, 1.0: 4.0}}}},\n",
      "          2: {'hair': {0.0: 2.0, 1.0: 1.0}},\n",
      "          4: {'hair': {0.0: {'toothed': {0.0: 7.0, 1.0: 5.0}}, 1.0: 1.0}},\n",
      "          6: {'aquatic': {0.0: 6.0, 1.0: 7.0}},\n",
      "          8: 7.0}}\n",
      "The prediction accuracy is:  85.71428571428571 %\n"
     ]
    }
   ],
   "source": [
    "tree = ID3(training_data, training_data, training_data.columns[:-1])\n",
    "pprint(tree)\n",
    "test(testing_data,tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}