DT - DecisionTree with Example.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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>temp</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  temp 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": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df = pd.read_csv('tennis.csv').drop(['day'], axis = 1)\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "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>temp</th>\n",
       "      <th>humidity</th>\n",
       "      <th>wind</th>\n",
       "      <th>play</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\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>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>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>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>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>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>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>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  temp humidity    wind play\n",
       "4       Rain  Cool   Normal    Weak  Yes\n",
       "5       Rain  Cool   Normal  Strong   No\n",
       "6   Overcast  Cool   Normal  Strong  Yes\n",
       "8      Sunny  Cool   Normal    Weak  Yes\n",
       "0      Sunny   Hot     High    Weak   No\n",
       "1      Sunny   Hot     High  Strong   No\n",
       "2   Overcast   Hot     High    Weak  Yes\n",
       "12  Overcast   Hot   Normal    Weak  Yes\n",
       "3       Rain  Mild     High    Weak  Yes\n",
       "7      Sunny  Mild     High    Weak   No\n",
       "9       Rain  Mild   Normal    Weak  Yes\n",
       "10     Sunny  Mild   Normal  Strong  Yes\n",
       "11  Overcast  Mild     High  Strong  Yes\n",
       "13      Rain  Mild     High  Strong   No"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.sort_values(['temp'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Important formulas to note:\n",
    "### $Entropy = H_{D0}(y)= -\\sum_{i=0}^k p(yi)log_{2}p(yi)$\n",
    "### $Weighted\\ entropy = \\sum_{i=0}^k \\frac{|Di|}{|D|} * H_{Di}$\n",
    "where; k = no. of categories in yi\n",
    "### $Information\\ gain = Parent\\ entropy - Weighted\\ entropy$\n",
    "### $Gini\\ impurity = 1 -\\sum_{i=0}^k (p(yi))^2$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# How decision tree is created out of dataset\n",
    "1. Compute initial parent entropy i.e., entropy of yi without any split\n",
    "2. Compute weighted entropy for each feature\n",
    "3. compute Information gain for each feature\n",
    "4. Select a feature whichever gives highest Information gain\n",
    "5. Now, further split as follow: \n",
    "    1. 'selected_features' will have some categories in it, sort dataset on each category.\n",
    "    2. now consider sorted dataset as parent data and follow first 4 steps again\n",
    "    3. whichever feature gives highest Information gain select it for further split\n",
    "        4. keep doing all above steps for each category in 'selected_feature'.\n",
    "6. keep doing till further split is not possible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Information gain calculation for each feature with simulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 326,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     outlook  temp humidity    wind play\n",
      "2   Overcast   Hot     High    Weak  Yes\n",
      "6   Overcast  Cool   Normal  Strong  Yes\n",
      "11  Overcast  Mild     High  Strong  Yes\n",
      "12  Overcast   Hot   Normal    Weak  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 1.0\n",
      "p(yi=No): 0\n",
      "entropy: 0.0\n",
      "==================================================\n",
      "   outlook  temp humidity    wind play\n",
      "3     Rain  Mild     High    Weak  Yes\n",
      "4     Rain  Cool   Normal    Weak  Yes\n",
      "5     Rain  Cool   Normal  Strong   No\n",
      "9     Rain  Mild   Normal    Weak  Yes\n",
      "13    Rain  Mild     High  Strong   No\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.6\n",
      "p(yi=No): 0.4\n",
      "entropy: 0.97095\n",
      "==================================================\n",
      "   outlook  temp humidity    wind play\n",
      "0    Sunny   Hot     High    Weak   No\n",
      "1    Sunny   Hot     High  Strong   No\n",
      "7    Sunny  Mild     High    Weak   No\n",
      "8    Sunny  Cool   Normal    Weak  Yes\n",
      "10   Sunny  Mild   Normal  Strong  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.6\n",
      "p(yi=No): 0.4\n",
      "entropy: 0.97095\n",
      "==================================================\n",
      "Parent_entropy: 0.94029\n",
      "Weighted entropy: 0.69354\n",
      "Information gain: 0.24675\n"
     ]
    }
   ],
   "source": [
    "feat = 'outlook'\n",
    "target = 'play'\n",
    "df1 = df.sort_values([feat])\n",
    "cats = df1[feat].unique()\n",
    "classes = df1[target].unique()\n",
    "n = len(df)\n",
    "entropy_lst = []\n",
    "df2_len_lst = []    # to compute weighted entropy we need to store |Di| i.e., size of each Di\n",
    "\n",
    "# 1. initial Parent entropy \n",
    "parent_entropy = 0\n",
    "for i in range(len(classes)):\n",
    "    proba = df[target].value_counts()[i]/n\n",
    "    parent_entropy -= (proba)*np.log2(proba)\n",
    "\n",
    "# 2. sorting feature by each category\n",
    "for i in range(len(cats)):\n",
    "    proba_lst = []\n",
    "    df2 = df1[df1[feat] == cats[i]]\n",
    "    print(df2)\n",
    "    print('-'*40)\n",
    "    entropy = 0\n",
    "    # 3. computing probabilities for each (Di) for each class (yi)\n",
    "    for k in range(len(classes)):\n",
    "        try:\n",
    "            df2_len = len(df2)\n",
    "            proba_lst.append(df2[target].value_counts()[k]/len(df2))\n",
    "        except:\n",
    "            proba_lst.append(0)\n",
    "        print('p(yi={}):'.format(classes[k]), proba_lst[k])\n",
    "        \n",
    "    # 4. Computing child entropy for each (Di)\n",
    "        if proba_lst[k] != 0:\n",
    "            entropy -= proba_lst[k]*np.log2(proba_lst[k]) \n",
    "            \n",
    "    df2_len_lst.append(len(df2))\n",
    "    entropy_lst.append(np.round(entropy, 5))\n",
    "    print('entropy:', np.round(entropy, 5))\n",
    "    print(\"=\"*50)\n",
    "print('Parent_entropy:', np.round(parent_entropy, 5))\n",
    "# 4. Weighted Entropy \n",
    "weighted_entropy = 0\n",
    "for i in range(len(entropy_lst)):\n",
    "    weighted_entropy += np.round((df2_len_lst[i]/n) * entropy_lst[i],5)\n",
    "print('Weighted entropy:', weighted_entropy)\n",
    "\n",
    "# 5. Information Gain = (parent_entropy - child_weighted_entropy)\n",
    "IG = np.round(parent_entropy - weighted_entropy, 5)\n",
    "print('Information gain:', IG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 327,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0.0, 0.97095, 0.97095]"
      ]
     },
     "execution_count": 327,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy_lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Information gain calculation for each feature without simulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 555,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parent_entropy: 0.9402859586706311\n",
      "Information gain(outlook): 0.24675\n",
      "Information gain(temp): 0.02923\n",
      "Information gain(humidity): 0.15183\n",
      "Information gain(wind): 0.04813\n"
     ]
    }
   ],
   "source": [
    "target = 'play'\n",
    "classes = df1[target].unique()\n",
    "n = len(df)\n",
    "IG_lst = []\n",
    "# 1. initial Parent entropy \n",
    "parent_entropy = 0\n",
    "entropy_lst = []\n",
    "entropy_dict_lst = []\n",
    "for i in range(len(classes)):\n",
    "    proba = df[target].value_counts()[i]/n\n",
    "    parent_entropy -= (proba)*np.log2(proba)\n",
    "print('Parent_entropy:', parent_entropy)\n",
    "\n",
    "features = df.columns[:-1]\n",
    "for j in features:\n",
    "    feat = j\n",
    "    df1 = df.sort_values([feat])\n",
    "    cats = df1[feat].unique()\n",
    "    entropy_lst = []\n",
    "    df2_len_lst = []    # to compute weighted entropy we need to store |Di| i.e., size of each Di\n",
    "    \n",
    "    # 2. sorting feature by each category\n",
    "    for i in range(len(cats)):\n",
    "        proba_lst = []\n",
    "        df2 = df1[df1[feat] == cats[i]]\n",
    "        entropy = 0\n",
    "        \n",
    "        # 3. computing probabilities for each (Di) for each class (yi)\n",
    "        for k in range(len(classes)):\n",
    "            try:\n",
    "                df2_len = len(df2)\n",
    "                proba_lst.append(df2[target].value_counts()[k]/len(df2))\n",
    "            except:\n",
    "                proba_lst.append(0)\n",
    "\n",
    "        # 4. Computing child entropy for each (Di)\n",
    "            if proba_lst[k] != 0:\n",
    "                entropy -= proba_lst[k]*np.log2(proba_lst[k]) \n",
    "            \n",
    "        df2_len_lst.append(len(df2))\n",
    "        entropy_lst.append(np.round(entropy, 5))\n",
    "        entropy_dict = dict(zip(cats, entropy_lst))\n",
    "        \n",
    "    entropy_dict_lst.append(entropy_dict)\n",
    "#     lst.append(entropy_dict)\n",
    "    # 5. Weighted Entropy \n",
    "    weighted_entropy = 0\n",
    "    for i in range(len(entropy_lst)):\n",
    "        weighted_entropy += np.round((df2_len_lst[i]/n) * entropy_lst[i],5)\n",
    "\n",
    "    # 6. Information Gain = (parent_entropy - child_weighted_entropy)\n",
    "    IG = np.round(parent_entropy - weighted_entropy, 5)\n",
    "    print('Information gain({}):'.format(j), IG)\n",
    "    IG_lst.append(IG)\n",
    "IG_dict =dict(zip(features, IG_lst)) # storing IG values for further splitting\n",
    "entropy_dict_lst = dict(zip(features, entropy_dict_lst))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 556,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'outlook': 0.24675, 'temp': 0.02923, 'humidity': 0.15183, 'wind': 0.04813}"
      ]
     },
     "execution_count": 556,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IG_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 558,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'outlook': {'Overcast': 0.0, 'Rain': 0.97095, 'Sunny': 0.97095},\n",
       " 'temp': {'Cool': 0.81128, 'Hot': 1.0, 'Mild': 0.9183},\n",
       " 'humidity': {'High': 0.98523, 'Normal': 0.59167},\n",
       " 'wind': {'Strong': 1.0, 'Weak': 0.81128}}"
      ]
     },
     "execution_count": 558,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy_dict_lst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Further splitting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 559,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'outlook'"
      ]
     },
     "execution_count": 559,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# https://www.geeksforgeeks.org/python-get-key-with-maximum-value-in-dictionary/\n",
    "max(IG_dict, key=IG_dict.get) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 584,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "   outlook  temp humidity    wind play\n",
      "3     Rain  Mild     High    Weak  Yes\n",
      "4     Rain  Cool   Normal    Weak  Yes\n",
      "5     Rain  Cool   Normal  Strong   No\n",
      "9     Rain  Mild   Normal    Weak  Yes\n",
      "13    Rain  Mild     High  Strong   No\n",
      "----------------------------------------\n",
      "\n",
      "Splitting dataset on: temp\n",
      "   outlook  temp humidity    wind play\n",
      "3     Rain  Mild     High    Weak  Yes\n",
      "9     Rain  Mild   Normal    Weak  Yes\n",
      "13    Rain  Mild     High  Strong   No\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.6666666666666666\n",
      "p(yi=No): 0.3333333333333333\n",
      "entropy: 0.9183\n",
      "========================================\n",
      "  outlook  temp humidity    wind play\n",
      "4    Rain  Cool   Normal    Weak  Yes\n",
      "5    Rain  Cool   Normal  Strong   No\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.5\n",
      "p(yi=No): 0.5\n",
      "entropy: 1.0\n",
      "========================================\n",
      "**************************************************\n",
      "Parent_entropy(Cool): 0.87728\n",
      "Weighted entropy(temp): 0.95098\n",
      "Information gain(temp): -0.0737\n",
      "**************************************************\n",
      "\n",
      "Splitting dataset on: humidity\n",
      "   outlook  temp humidity    wind play\n",
      "3     Rain  Mild     High    Weak  Yes\n",
      "13    Rain  Mild     High  Strong   No\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.5\n",
      "p(yi=No): 0.5\n",
      "entropy: 1.0\n",
      "========================================\n",
      "  outlook  temp humidity    wind play\n",
      "4    Rain  Cool   Normal    Weak  Yes\n",
      "5    Rain  Cool   Normal  Strong   No\n",
      "9    Rain  Mild   Normal    Weak  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.6666666666666666\n",
      "p(yi=No): 0.3333333333333333\n",
      "entropy: 0.9183\n",
      "========================================\n",
      "**************************************************\n",
      "Parent_entropy(Normal): 0.87728\n",
      "Weighted entropy(humidity): 0.95098\n",
      "Information gain(humidity): -0.0737\n",
      "**************************************************\n",
      "\n",
      "Splitting dataset on: wind\n",
      "  outlook  temp humidity  wind play\n",
      "3    Rain  Mild     High  Weak  Yes\n",
      "4    Rain  Cool   Normal  Weak  Yes\n",
      "9    Rain  Mild   Normal  Weak  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 1.0\n",
      "p(yi=No): 0\n",
      "entropy: 0.0\n",
      "========================================\n",
      "   outlook  temp humidity    wind play\n",
      "5     Rain  Cool   Normal  Strong   No\n",
      "13    Rain  Mild     High  Strong   No\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0\n",
      "p(yi=No): 1.0\n",
      "entropy: 0.0\n",
      "========================================\n",
      "**************************************************\n",
      "Parent_entropy(Strong): 0.87728\n",
      "Weighted entropy(wind): 0.0\n",
      "Information gain(wind): 0.87728\n",
      "**************************************************\n",
      "   outlook  temp humidity    wind play\n",
      "0    Sunny   Hot     High    Weak   No\n",
      "1    Sunny   Hot     High  Strong   No\n",
      "7    Sunny  Mild     High    Weak   No\n",
      "8    Sunny  Cool   Normal    Weak  Yes\n",
      "10   Sunny  Mild   Normal  Strong  Yes\n",
      "----------------------------------------\n",
      "\n",
      "Splitting dataset on: temp\n",
      "  outlook temp humidity    wind play\n",
      "0   Sunny  Hot     High    Weak   No\n",
      "1   Sunny  Hot     High  Strong   No\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0\n",
      "p(yi=No): 1.0\n",
      "entropy: 0.0\n",
      "========================================\n",
      "   outlook  temp humidity    wind play\n",
      "7    Sunny  Mild     High    Weak   No\n",
      "10   Sunny  Mild   Normal  Strong  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.5\n",
      "p(yi=No): 0.5\n",
      "entropy: 1.0\n",
      "========================================\n",
      "  outlook  temp humidity  wind play\n",
      "8   Sunny  Cool   Normal  Weak  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 1.0\n",
      "p(yi=No): 0\n",
      "entropy: 0.0\n",
      "========================================\n",
      "**************************************************\n",
      "Parent_entropy(Cool): 0.87728\n",
      "Weighted entropy(temp): 0.4\n",
      "Information gain(temp): 0.47728\n",
      "**************************************************\n",
      "\n",
      "Splitting dataset on: humidity\n",
      "  outlook  temp humidity    wind play\n",
      "0   Sunny   Hot     High    Weak   No\n",
      "1   Sunny   Hot     High  Strong   No\n",
      "7   Sunny  Mild     High    Weak   No\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0\n",
      "p(yi=No): 1.0\n",
      "entropy: 0.0\n",
      "========================================\n",
      "   outlook  temp humidity    wind play\n",
      "8    Sunny  Cool   Normal    Weak  Yes\n",
      "10   Sunny  Mild   Normal  Strong  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 1.0\n",
      "p(yi=No): 0\n",
      "entropy: 0.0\n",
      "========================================\n",
      "**************************************************\n",
      "Parent_entropy(Normal): 0.87728\n",
      "Weighted entropy(humidity): 0.0\n",
      "Information gain(humidity): 0.87728\n",
      "**************************************************\n",
      "\n",
      "Splitting dataset on: wind\n",
      "  outlook  temp humidity  wind play\n",
      "0   Sunny   Hot     High  Weak   No\n",
      "7   Sunny  Mild     High  Weak   No\n",
      "8   Sunny  Cool   Normal  Weak  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.3333333333333333\n",
      "p(yi=No): 0.6666666666666666\n",
      "entropy: 0.9183\n",
      "========================================\n",
      "   outlook  temp humidity    wind play\n",
      "1    Sunny   Hot     High  Strong   No\n",
      "10   Sunny  Mild   Normal  Strong  Yes\n",
      "----------------------------------------\n",
      "p(yi=Yes): 0.5\n",
      "p(yi=No): 0.5\n",
      "entropy: 1.0\n",
      "========================================\n",
      "**************************************************\n",
      "Parent_entropy(Strong): 0.87728\n",
      "Weighted entropy(wind): 0.95098\n",
      "Information gain(wind): -0.0737\n",
      "**************************************************\n"
     ]
    }
   ],
   "source": [
    "feat = max(IG_dict, key=IG_dict.get) \n",
    "target = 'play'\n",
    "df1 = df.sort_values([feat])\n",
    "cats = df1[feat].unique()\n",
    "classes = df1[target].unique()\n",
    "n = len(df)\n",
    "entropy_lst = []\n",
    "df3_len_lst = []    # to compute weighted entropy we need to store |Di| i.e., size of each Di\n",
    "features = list(df.columns[:-1])\n",
    "features.remove(feat)\n",
    "IG_lst = []\n",
    "IG_dict_lst = []\n",
    "\n",
    "# 2. sorting feature by each category\n",
    "for i in range(len(cats)):\n",
    "    if entropy_dict_lst[feat][cats[i]] != 0:\n",
    "        proba_lst = []\n",
    "        IG_lst = []\n",
    "        df2 = df1[df1[feat] == cats[i]]\n",
    "        print(df2)\n",
    "        print('-'*40)\n",
    "        \n",
    "        # compute parent entropy\n",
    "        parent_entropy = 0\n",
    "        for c in range(len(classes)):\n",
    "            proba = df2[target].value_counts()[c]/n\n",
    "            parent_entropy -= (proba)*np.log2(proba)\n",
    "        \n",
    "        # 3. computing Entropy \n",
    "        for j in features:\n",
    "            \n",
    "            print('\\nSplitting dataset on:',j)\n",
    "#             entropy = 0\n",
    "#             print(df2.sort_values(j))\n",
    "\n",
    "            # 2. sorting feature by each category\n",
    "            cats1 = df2[j].unique()\n",
    "            entropy_lst = []\n",
    "            df3_len_lst = []\n",
    "            for i in range(len(cats1)):\n",
    "                entropy = 0\n",
    "                if entropy_dict_lst[j][cats1[i]] != 0:\n",
    "                    proba_lst = []\n",
    "                    df3 = df2[df2[j] == cats1[i]]\n",
    "                    print(df3)\n",
    "                    print('-'*40)\n",
    "            \n",
    "                # 4. computing probabilities for each (Di) for each class (yi)\n",
    "                for k in range(len(classes)):\n",
    "                    try:\n",
    "                        proba_lst.append(dict(df3[target].value_counts())[classes[k]]/len(df3))\n",
    "                    except:\n",
    "                        proba_lst.append(0)\n",
    "                    print('p(yi={}):'.format(classes[k]), proba_lst[k])\n",
    "                \n",
    "                    # 5. Computing child entropy for each (Di)\n",
    "                    if proba_lst[k] != 0:\n",
    "                        entropy -= proba_lst[k]*np.log2(proba_lst[k]) \n",
    "                df3_len_lst.append(len(df3))\n",
    "                entropy_lst.append(np.round(entropy, 5))\n",
    "                entropy_dict = dict(zip(cats, entropy_lst))\n",
    "                print('entropy:', np.round(entropy, 5))\n",
    "                print(\"=\"*40)\n",
    "            print('*'*50)\n",
    "            print('Parent_entropy({}):'.format(cats1[i]), np.round(parent_entropy, 5))\n",
    "                \n",
    "            # 4. Weighted Entropy \n",
    "            weighted_entropy = 0\n",
    "            for e in range(len(entropy_lst)):\n",
    "                weighted_entropy += np.round((df3_len_lst[e]/len(df2)) * entropy_lst[e],5)\n",
    "            print('Weighted entropy({}):'.format(j), weighted_entropy)\n",
    "\n",
    "            # 5. Information Gain = (parent_entropy - child_weighted_entropy)\n",
    "            IG = np.round(parent_entropy - weighted_entropy, 5)\n",
    "            print('Information gain({}):'.format(j), IG)\n",
    "            print('*'*50)\n",
    "            IG_lst.append(IG)\n",
    "    IG_dict_lst.append(dict(zip(features, IG_lst)))\n",
    "IG_final_dict = dict(zip(cats, IG_dict_lst))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 585,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Overcast': {},\n",
       " 'Rain': {'temp': -0.0737, 'humidity': -0.0737, 'wind': 0.87728},\n",
       " 'Sunny': {'temp': 0.47728, 'humidity': 0.87728, 'wind': -0.0737}}"
      ]
     },
     "execution_count": 585,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "IG_final_dict"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}