8. ID3 - Decision Tree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "a12b776b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "eps = np.finfo(float).eps\n",
    "from numpy import log2 as log"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1b72787e",
   "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>Outlook</th>\n",
       "      <th>Temperature</th>\n",
       "      <th>Humidity</th>\n",
       "      <th>Wind</th>\n",
       "      <th>Play</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>Strong</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Strong</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Strong</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Weak</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Mild</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Mild</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Strong</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Strong</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>Overcast</td>\n",
       "      <td>Hot</td>\n",
       "      <td>Normal</td>\n",
       "      <td>Weak</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>Rain</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>Strong</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     Outlook Temperature Humidity    Wind Play\n",
       "0      Sunny         Hot     High    Weak   No\n",
       "1      Sunny         Hot     High  Strong   No\n",
       "2   Overcast         Hot     High    Weak  Yes\n",
       "3       Rain        Mild     High    Weak  Yes\n",
       "4       Rain        Cool   Normal    Weak  Yes\n",
       "5       Rain        Cool   Normal  Strong   No\n",
       "6   Overcast        Cool   Normal  Strong  Yes\n",
       "7      Sunny        Mild     High    Weak   No\n",
       "8      Sunny        Cool   Normal    Weak  Yes\n",
       "9       Rain        Mild   Normal    Weak  Yes\n",
       "10     Sunny        Mild   Normal  Strong  Yes\n",
       "11  Overcast        Mild     High  Strong  Yes\n",
       "12  Overcast         Hot   Normal    Weak  Yes\n",
       "13      Rain        Mild     High  Strong   No"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = pd.read_csv(\"DecisionTree.csv\")\n",
    "data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fd6da6d7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_entropy(df):\n",
    "    Class = df.keys()[-1]   #To make the code generic, changing target variable class name\n",
    "    entropy = 0\n",
    "    values = df[Class].unique()\n",
    "    for value in values:\n",
    "        fraction = df[Class].value_counts()[value]/len(df[Class])\n",
    "        entropy += -fraction*np.log2(fraction)\n",
    "    return entropy\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "5e457004",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_entropy_attribute(df,attribute):\n",
    "    Class = df.keys()[-1] \n",
    "    target_variables = df[Class].unique() \n",
    "    variables = df[attribute].unique()\n",
    "    entropy2 = 0\n",
    "    for variable in variables:\n",
    "        entropy = 0\n",
    "        for target_variable in target_variables:\n",
    "            num = len(df[attribute][df[attribute]==variable][df[Class] ==target_variable])\n",
    "            den = len(df[attribute][df[attribute]==variable])\n",
    "            fraction = num/(den+eps)\n",
    "            entropy += -fraction*log(fraction+eps)\n",
    "        fraction2 = den/len(df)\n",
    "        entropy2 += -fraction2*entropy\n",
    "    return abs(entropy2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "40f3190d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_winner(df):\n",
    "    Entropy_att = []\n",
    "    IG = []\n",
    "    for key in df.keys()[:-1]:\n",
    "        IG.append(find_entropy(df)-find_entropy_attribute(df,key))\n",
    "    return df.keys()[:-1][np.argmax(IG)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6ce9f193",
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_subtable(df, node,value):\n",
    "    return df[df[node] == value].reset_index(drop=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "478aeb33",
   "metadata": {},
   "outputs": [],
   "source": [
    "def buildTree(df,tree=None): \n",
    "    Class = df.keys()[-1]\n",
    "    \n",
    "    #Get attribute with maximum information gain\n",
    "    node = find_winner(df)\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",
    "    for value in attValue:\n",
    "        subtable = get_subtable(df,node,value)\n",
    "        print(subtable)\n",
    "        clValue,counts = np.unique(subtable['Play'],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) #Calling the function recursively \n",
    "\n",
    "    return tree\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a5fb5cb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "    Outlook Temperature Humidity    Wind Play\n",
      "0  Overcast         Hot     High    Weak  Yes\n",
      "1  Overcast        Cool   Normal  Strong  Yes\n",
      "2  Overcast        Mild     High  Strong  Yes\n",
      "3  Overcast         Hot   Normal    Weak  Yes\n",
      "  Outlook Temperature Humidity    Wind Play\n",
      "0    Rain        Mild     High    Weak  Yes\n",
      "1    Rain        Cool   Normal    Weak  Yes\n",
      "2    Rain        Cool   Normal  Strong   No\n",
      "3    Rain        Mild   Normal    Weak  Yes\n",
      "4    Rain        Mild     High  Strong   No\n",
      "  Outlook Temperature Humidity    Wind Play\n",
      "0    Rain        Cool   Normal  Strong   No\n",
      "1    Rain        Mild     High  Strong   No\n",
      "  Outlook Temperature Humidity  Wind Play\n",
      "0    Rain        Mild     High  Weak  Yes\n",
      "1    Rain        Cool   Normal  Weak  Yes\n",
      "2    Rain        Mild   Normal  Weak  Yes\n",
      "  Outlook Temperature Humidity    Wind Play\n",
      "0   Sunny         Hot     High    Weak   No\n",
      "1   Sunny         Hot     High  Strong   No\n",
      "2   Sunny        Mild     High    Weak   No\n",
      "3   Sunny        Cool   Normal    Weak  Yes\n",
      "4   Sunny        Mild   Normal  Strong  Yes\n",
      "  Outlook Temperature Humidity    Wind Play\n",
      "0   Sunny         Hot     High    Weak   No\n",
      "1   Sunny         Hot     High  Strong   No\n",
      "2   Sunny        Mild     High    Weak   No\n",
      "  Outlook Temperature Humidity    Wind Play\n",
      "0   Sunny        Cool   Normal    Weak  Yes\n",
      "1   Sunny        Mild   Normal  Strong  Yes\n"
     ]
    }
   ],
   "source": [
    "tree = buildTree(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "2754fd51",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Outlook': {'Overcast': 'Yes',\n",
      "             'Rain': {'Wind': {'Strong': 'No', 'Weak': 'Yes'}},\n",
      "             'Sunny': {'Humidity': {'High': 'No', 'Normal': 'Yes'}}}}\n"
     ]
    }
   ],
   "source": [
    "import pprint\n",
    "pprint.pprint(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "2376c413",
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(test, tree, default=None):\n",
    "    attribute = next(iter(tree))\n",
    "    print(attribute)\n",
    "\n",
    "    if test[attribute] in tree[attribute].keys():\n",
    "        print(tree[attribute].keys())\n",
    "        print(test[attribute])\n",
    "        result = tree[attribute][test[attribute]]\n",
    "        if isinstance(result, dict):\n",
    "            return predict(test, result)\n",
    "        else:\n",
    "            return result\n",
    "    else:\n",
    "        return default\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "2b7d944a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Outlook\n",
      "dict_keys(['Overcast', 'Rain', 'Sunny'])\n",
      "Sunny\n",
      "Humidity\n",
      "dict_keys(['High', 'Normal'])\n",
      "Normal\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "\n",
    "test = {'Outlook':'Sunny', 'Temperature':'Mild', 'Humidity':'Normal', 'Wind':'Strong'}\n",
    "ans = predict(test, tree)\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0992462b",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}