Week9 - Decision trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision Trees"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#importing libraries\n",
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.220446049250313e-16"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "eps = np.finfo(float).eps\n",
    "eps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here `eps` is the smallest representable number. At times we get $log(0)$ or $0$. We will use `eps` to avoid underflow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = {'Outlook': ['Sunny', 'Sunny', 'Overcast', 'Rain', 'Rain', 'Rain', 'Overcast', 'Sunny', 'Sunny', 'Rain', 'Sunny', 'Overcast', 'Overcast', 'Rain' ],\n",
    "        'Temperature': ['Hot', 'Hot', 'Hot', 'Mild', 'Cool', 'Cool', 'Cool', 'Mild', 'Cool', 'Mild', 'Mild', 'Mild', 'Hot', 'Mild'],\n",
    "        'Humidity': ['High', 'High', 'High', 'High', 'Normal', 'Normal', 'Normal', 'High', 'Normal', 'Normal', 'Normal', 'High', 'Normal', 'High'],\n",
    "        'Wind': ['Weak', 'Strong', 'Weak', 'Weak', 'Weak', 'Strong', 'Strong', 'Weak', 'Weak', 'Weak',  'Strong', 'Strong', 'Weak', 'Strong'],\n",
    "        'Play': ['No', 'No', 'Yes', 'Yes', 'Yes', 'No', 'Yes', 'No',  'Yes', 'Yes',  'Yes', 'Yes', 'Yes', 'No' ]}\n",
    "df = pd.DataFrame(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(14, 5)"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([['Sunny', 'Hot', 'High', 'Weak', 'No'],\n",
       "       ['Sunny', 'Hot', 'High', 'Strong', 'No'],\n",
       "       ['Overcast', 'Hot', 'High', 'Weak', 'Yes'],\n",
       "       ['Rain', 'Mild', 'High', 'Weak', 'Yes'],\n",
       "       ['Rain', 'Cool', 'Normal', 'Weak', 'Yes'],\n",
       "       ['Rain', 'Cool', 'Normal', 'Strong', 'No'],\n",
       "       ['Overcast', 'Cool', 'Normal', 'Strong', 'Yes'],\n",
       "       ['Sunny', 'Mild', 'High', 'Weak', 'No'],\n",
       "       ['Sunny', 'Cool', 'Normal', 'Weak', 'Yes'],\n",
       "       ['Rain', 'Mild', 'Normal', 'Weak', 'Yes'],\n",
       "       ['Sunny', 'Mild', 'Normal', 'Strong', 'Yes'],\n",
       "       ['Overcast', 'Mild', 'High', 'Strong', 'Yes'],\n",
       "       ['Overcast', 'Hot', 'Normal', 'Weak', 'Yes'],\n",
       "       ['Rain', 'Mild', 'High', 'Strong', 'No']], dtype=object)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Index(['Outlook', 'Temperature', 'Humidity', 'Wind', 'Play'], dtype='object')"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Play'"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "target = df.keys()[-1]\n",
    "target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array(['No', 'Yes'], dtype=object)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df[target].unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Yes    9\n",
       "No     5\n",
       "Name: Play, dtype: int64"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df[target].value_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating entropy of the whole dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9402859586706311"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def find_entropy_whole(df):\n",
    "    #last column in the dataframe is the target variable\n",
    "    target = df.keys()[-1]\n",
    "\n",
    "    #initialisation\n",
    "    overall_entropy = 0\n",
    "\n",
    "    #possible values of target\n",
    "    values_in_target = df[target].unique()\n",
    "\n",
    "    for value in values_in_target:\n",
    "        p = df[target].value_counts()[value] / len(df[target])\n",
    "        overall_entropy += -p*np.log2(p)\n",
    "    \n",
    "    return overall_entropy\n",
    "\n",
    "find_entropy_whole(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Calculating entropy of an attribute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_entropy_of_attribute(df, attribute):\n",
    "    target = df.keys()[-1]\n",
    "    values_in_target = df[target].unique()\n",
    "    values_in_attribute = df[attribute].unique()\n",
    "\n",
    "    entropy_attribute = 0\n",
    "\n",
    "    for attribute_value in values_in_attribute:\n",
    "        overall_entropy = 0\n",
    "\n",
    "        for target_value in values_in_target:\n",
    "            num = len(df[attribute][df[attribute] == attribute_value][df[target] == target_value])\n",
    "            den = len(df[attribute][df[attribute] == attribute_value])\n",
    "\n",
    "            p = num/(den + eps)\n",
    "            overall_entropy += -p * np.log2(p + eps) \n",
    "        p2 = den / len(df)\n",
    "        entropy_attribute += -p2 * overall_entropy\n",
    "\n",
    "    return abs(entropy_attribute) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Entropy of attribute 'Outlook' is : 0.6935361388961914\n",
      "Entropy of attribute 'Temperature' is : 0.9110633930116756\n",
      "Entropy of attribute 'Humidity' is : 0.7884504573082889\n",
      "Entropy of attribute 'Wind' is : 0.892158928262361\n"
     ]
    }
   ],
   "source": [
    "for i in df.keys()[:-1]:\n",
    "    print(f'Entropy of attribute \\'{i}\\' is :', find_entropy_of_attribute(df, i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finding the best attribute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best_attribute_to_divide(df):\n",
    "    #Information gain\n",
    "    IG = []\n",
    "\n",
    "    all_attribute_names = df.keys()[:-1]\n",
    "\n",
    "    for attr in all_attribute_names:\n",
    "        IG.append(find_entropy_whole(df) - find_entropy_of_attribute(df, attr))\n",
    "    \n",
    "    index_of_attr_with_max_IG = np.argmax(IG)\n",
    "\n",
    "    best_attribute = all_attribute_names[index_of_attr_with_max_IG]\n",
    "\n",
    "    return best_attribute"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Outlook'"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_best_attribute_to_divide(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Building decision tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Outlook': {'Overcast': 'Yes',\n",
       "  'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}},\n",
       "  'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def buildTree(df, tree=None):\n",
    "\n",
    "    target = df.keys()[-1]\n",
    "\n",
    "    #Get attribute with mximum information gain\n",
    "    node = find_best_attribute_to_divide(df)\n",
    "\n",
    "    # get distinct value of that attribute\n",
    "    attValue = np.unique(df[node])\n",
    "\n",
    "    # Create an empty dictionary to create tree\n",
    "    if tree is None:\n",
    "        tree = {}\n",
    "        tree[node] = {}\n",
    "\n",
    "    # We make loop to construct a tree by calling this function recursively\n",
    "    for value in attValue:\n",
    "\n",
    "        subtable = df[df[node] == value].reset_index(drop=True)\n",
    "        clValue, counts = np.unique(subtable[target], return_counts=True)\n",
    "\n",
    "        if len(counts) == 1: #Checking purity of subset\n",
    "            tree[node][value] = clValue[0]\n",
    "        else:\n",
    "            tree[node][value] = buildTree(subtable) #recursive function call\n",
    "\n",
    "    return tree\n",
    "\n",
    "buildTree(df)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ID3 in its pure form performs no backtracking in its search. Once it selects an attribute to test at a particular level in the tree, it ever back tracks to reconsider this choice. Therefore it is susceptible to the usual risks of hill-climbing search without backtracking: converging to a locally optimal solutions that are not globally optimal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.2 64-bit",
   "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.10.2"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "369f2c481f4da34e4445cda3fffd2e751bd1c4d706f27375911949ba6bb62e1c"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}