ID3.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "4kT6qMIWUXiw"
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "eps = np.finfo(float).eps\n",
    "from numpy import log2 as log\n",
    "import pprint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "7uA8a1tFa_c7"
   },
   "outputs": [],
   "source": [
    "df = pd.read_csv('weather.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 204
    },
    "colab_type": "code",
    "id": "cwkAsrpjbJQZ",
    "outputId": "75f53255-4366-4f14-e3c8-2c6688edafb2"
   },
   "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>windy</th>\n",
       "      <th>play</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>overcast</td>\n",
       "      <td>hot</td>\n",
       "      <td>high</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>overcast</td>\n",
       "      <td>cool</td>\n",
       "      <td>normal</td>\n",
       "      <td>True</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>overcast</td>\n",
       "      <td>mild</td>\n",
       "      <td>high</td>\n",
       "      <td>True</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>overcast</td>\n",
       "      <td>hot</td>\n",
       "      <td>normal</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>rainy</td>\n",
       "      <td>mild</td>\n",
       "      <td>high</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>rainy</td>\n",
       "      <td>cool</td>\n",
       "      <td>normal</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>rainy</td>\n",
       "      <td>cool</td>\n",
       "      <td>normal</td>\n",
       "      <td>True</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>rainy</td>\n",
       "      <td>mild</td>\n",
       "      <td>normal</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>rainy</td>\n",
       "      <td>mild</td>\n",
       "      <td>high</td>\n",
       "      <td>True</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>sunny</td>\n",
       "      <td>hot</td>\n",
       "      <td>high</td>\n",
       "      <td>False</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>sunny</td>\n",
       "      <td>hot</td>\n",
       "      <td>high</td>\n",
       "      <td>True</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>sunny</td>\n",
       "      <td>mild</td>\n",
       "      <td>high</td>\n",
       "      <td>False</td>\n",
       "      <td>no</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>sunny</td>\n",
       "      <td>cool</td>\n",
       "      <td>normal</td>\n",
       "      <td>False</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>sunny</td>\n",
       "      <td>mild</td>\n",
       "      <td>normal</td>\n",
       "      <td>True</td>\n",
       "      <td>yes</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     outlook temperature humidity  windy play\n",
       "0   overcast         hot     high  False  yes\n",
       "1   overcast        cool   normal   True  yes\n",
       "2   overcast        mild     high   True  yes\n",
       "3   overcast         hot   normal  False  yes\n",
       "4      rainy        mild     high  False  yes\n",
       "5      rainy        cool   normal  False  yes\n",
       "6      rainy        cool   normal   True   no\n",
       "7      rainy        mild   normal  False  yes\n",
       "8      rainy        mild     high   True   no\n",
       "9      sunny         hot     high  False   no\n",
       "10     sunny         hot     high   True   no\n",
       "11     sunny        mild     high  False   no\n",
       "12     sunny        cool   normal  False  yes\n",
       "13     sunny        mild   normal   True  yes"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df.head(15)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "SYOCF2vi_M7i"
   },
   "source": [
    "**Get Information/Entropy (Info(D))**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JIXCNKcl_Q-P"
   },
   "source": [
    "![image.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAREAAAA9CAYAAACKjV13AAAZdklEQVR4Ae3dBbQ1VdkHcEIapEEJAekURToFkUakXkpUSkpCukGQkO4OQbq7BCWkJCQVkAZJ6Qadb/328rnfvMOce/Le97znzl5rrzl3Zs+OZz/7/9SefUfJqlRRoA4F/vOf/2T33XdfdvbZZ2ePP/54+r3SSitlY445ZrbBBhtkDzzwQLbGGmtkY489drbaaqtln376aZ0aq8e9RIFRemkw1VgGhgKff/559qtf/SobY4wxsq222ipbc801s7XWWitbdtlls+9///vZT37yk2yLLbbIVl999WzllVeuQGRgpqFra61ApGunpns69t///jd79913syWWWCLlZZZZJtt9990TeHzta1/Lttxyy+yDDz7INt544wpEumfaBq0nFYgMGqlH7oa++OKLbPnll8+AxjbbbJNMmBVXXDHbcMMNszfeeCN74YUXkoYCSD777LORe7BV75uiQAUiTZFraBamiTz99NMZDeSXv/xl9vrrr2e/+MUvkv/j3//+d/bll18mYGHeeKZ8lYYOBUpBBBNUuaJB8ABH6brrrpvym2++mTQN/o9hw4YlPqGlAJUFFlggaSTxXnXtfR4ClaUgMnQwtBppPQoAAqYKgNh0001TcY5W0Zh11lkn/U0T2WijjbLRRx89aSSeV2noUKAURCoJ0vsSpNE5pmUwYcYaa6zs17/+ddI8XnvtteRABSrqASLbbrtt9oMf/CD75z//WWmxQ0iTB5WlIDJ0MLQaaT0KAIknnngiu/7665NGYs/ITjvtlK233nrJT+J9ZZ577rnsqaeeSr/r1Vk97y0KVCDSW/M5KKP5xz/+kQAEoFSpokAFIhUPVBSoKNAWBSoQaYt81csVBSoKVCBS8cBXKGCz2IcfftixXG0++wqJe+pGBSI9NZ3tD0Z4VqRlzjnnLM1zzTVX1kjOv++7GxGcKvUmBUpBpNHw30CUI7VsbpL9brUNoUmOv1bfz79nAcj5e7362zjPO++8bKqppspGGWWU4fKss86a7bnnntnee+/db95rr72y733ve33vzj///G3NZa/Sujgu/Ipvi/c78Tfh0Il6inWAxVIQGRF4qXN///vfM99jLLrooimvssoq2YsvvthUd9Tz/vvvp69N77zzzqbeLStsUR1//PHZcccd1zfBZeV66R5G/sMf/pBNOeWUfUAAUCaZZJLstNNOqwuoFsMdd9yRffe7303v26g2Ijag4YVYPN0+P2h23XXXpfB5p82/V199NX0cKVSPJp1OpSCiof6yAZucYm5HWvs2Y9VVV81+9rOfZVtvvXX24x//OBtvvPGyv/71r/32pdjPd955JwGIfQyPPfbYcO/qX7HPxb+NLV+nd6688sr08dmJJ57YByT5Mr3427hPP/30bIopphgOSGxvR7NGxvznP/85m3vuubPB1kSAoD5aPEwpwqmR/o6oMnjuxhtvTEcrHHXUUQ3Tt9H++r5phx12SGvqySef7CgtAFIpiNRDqmuuuSZ1iKaQz7/5zW9aOksCMW666aZs8sknzx599NEk6V5++eVs//33Tx901etPPP/oo48SAPmuIwAknn3yySeZ/uX7W/wNxC677LLUvomN5PeFF16Y/ehHP0qSOP8syvTilXN1qaWWGg5EvvnNb2bnnHNOn6nY37jRaeedd05b5i3qwUh209pJa24dXTDOOONk11577WA03XIbf/zjH7PlllsuO+ywwzJ8aj10MqnPN08A1VkwdhV3MrUEIjfccEPasTjzzDMnBvv617+eDqT53e9+1xKIPPvss0nSTzjhhOnkrFYGiFC+IMXkv//9779Shck54IADElOFrT/LLLOkj8h8A+JbEOr6dNNNl6299toJTPJgQbqtv/766cvVwVoQXxnEIN8wZqYcugTNXKeeeurs/PPPT2DbX5fMCQl77LHHJtDpr2ynnuEBRxUAfN/yOH2tm0EEjQg3jmhCcCCTTYKTTTZZ2n2s3U6llkDE4sJgDqZxJB5HGgKEOdNs526++eY02TQIZ1O0kvhBOPxWWGGFdNZFsQ5EI1k5B2NBcBICBGP5+OOPs0MPPTQbf/zx0/MZZ5wxu/rqq/uY39jOOuuspHI2soCK7Y+Mf6MZ+hxyyCEZQRF0cwW2l1xySd1h4RW0G6ykz+bz4YcfzgilbgYRfb3rrrsyR03uscceA34OC23kpz/9aco+quxUaglEDJ7Tcp555kleeAuwncSUgZAcP62m559/Ppt22mmzc889t2YVtJHZZ589LYZvf/vbSUIZSyQMf/DBByfms1DY/8UF4ExRqvJQ0UbQxqI8/PDDs4kmmmg4IImjAIJ+3XR1Fqz+1gMR85/PtcaQL5PnmVrlG7mvHgLYEZPvvfdeI6+0XYZ/6Bvf+EZy4rZd2f8qaBlEaCEWmlBeOyDC98FMMOGtgoj2DzzwwPQVKUdsrZQHEVpLESC855i/H/7wh2lstBb2ap5pgMi3vvWt7PLLLx/ufq02e+G+8Qu5MwdDUzP3gNiHeXmzr1vG2wiI4IcTTjgh23HHHVPebbfdSs1pfCLsHeX4eToR+XP4tfNp1acvg5GACIHNhH/ppZc60mTLILLrrruWggiG01FOUaeDYz73fOX529/+Npkcp5xySvqAi9R34O9oo42Wjt3jELO4jz766EyUxXtvv/12+jv2JjA5OM/y6ZVXXknoKixZi6GFzfhKQi23IMqSyXQMoEUi//znPx+uzmOOOSabeOKJkwo6lLQRc8FkpXoHbVwBLR+Z5+0mvjF8Y66Fkn0VHDzjnjA7k7SR1B+IEDrq9zXyIosskhy/8847bzqI2ult+hACjRZGuyW9Of7nm2++5FcTvg6e3GeffbLbb7+9kW71lUEvWoh6jKk/+qELIak9awddrJ1on9+KOd9fHdGwiBX+pqEJKXcilYKIzvSXLdRddtklMRMiYK4oH6HaYDB2GPvLKeGcnu7byHTVVVdlCy+8cDbNNNP0MSU/BBPJMXuiNCElTLD7nnOWqYvvRJsYQlhs3HHHTc6+6EfxCpTUo31IfOmll/b1OV9WfTzlyslsSJIoygAZ2sgMM8yQIkpoEc96/WpB7bvvvsM5p9GIifinP/0pgW07NLC3JPgB2DOXhIjNPWeuM034Z2iL9doRneMTcUK9aGK+vIXE9OXXYUqrj2DiUHeGrDHhKe/gbftcJp100hTyJtQ4bvkClaOZfec730kAl2+j3m/9W2yxxRJPhqCt9Q664Dft4XOnzKGJjF4iUIRiI3TRRtDGebhoUavdRu4DoVIQqYdOKgciJojfIDbHCB1tttlmfd580ZuHHnoo22677VJI+IgjjshGHXXUhOo0E+gpdKqeCSaYILv33nuTbQiZ77nnnqQ1mKAHH3ww3WeqmDzlmRkSXwgGAy4XXHBBza4DEUQ3EeFQLStc1EQcRJzXbgAK4qtHSDjGXqwLjQAqKUF7aTZTnwFaNyVjQh8SHOOiQWQaZS1aNDoGtCU48Ajt1CFHzF3+AnNrgdu3QtONpE9lqZYmov8nn3xyApiTTjqpz6RVD4EnSqdt//rCngrCzqY7+yxonso5+X7xxRdPYydQ9K+ZsauDFoJ2hHC9d9FFn9FFpi3RTrR78cUXp/Uggqa/kvojl9HmmWeeSe6DANiyMs3cKwWR6ECtq1ARvwF/SGgEytpjYZMXNctEkCJAhiOSyWFhWOxLLrlk33siICSMDUlsNPUgDolDAgCQkPaYB/OqO1RoxDTJ7oma1OozCaI/Jo6KHHUWy+c1EW1RI/NlSWNHAaqHWlhLinjnoosuSuo+DarZbH9GHHpc7OOI/hvI8w+ENEYLIUp+gnb7JgIWgsZ8R334BIhYLADCfXwifFsmgUPaxkKJeoAS6Y1fmLdxP67/+te/splmmin1Yb/99ks8aHyiJ1EGEAE49wmUuN/oFW+EO4B2XIuH8vVxDaALjSgOf/KcSWKMNLegV9AlTJx8PX4T9rQ0a/GKK65ouv/5+oBNKYjUQyEENaAFF1xwOBsVMQyA1KVZkE5MA+AAbOxEjQ1lCClRNRHm7rvvTovVwPk9mBy33nprn6RQFnhR5wze/gOJRsNe7U8T0RZmC3MKMCBEMbmnH3PMMUdiEOqt/uRTXhMRTq4lRdSFHoCglWyXYdAo337+N1XbuIBzMxm4hRqbr6/R38aGLvEPrSwmWYgefVpNNAGaLN4i6fPhfnxiseCV8FdwTNJCabvFVEsTwYv4AL9YmMWEf5ln+sDXET47mgmtN+Z16aWXTmPeZJNNilWkMha0Ofnb3/72FV5TBycumjWiieAf/9sH8Flzb731Vl+bHNv8G0DB+pDuv//+mnTxPDQRoGw3drupJRAhhRCgCCI6gzlpHyaB2sUfgmi0BJ224MMrTC1kWmCMIABpxs605R0x8ilABBMwfaRGQMRii9AucDvzzDO/MrHqsgDCqUo7Yv8XF0WjIJLv90D9poUJD6JpM5kvgJpuXtpJ5o9JhxcscL6qesDXX3sc4/iGtsEUjLq0Q3BZRMxbi1mibfjOKngnX3cnQITzEj/TsowRP+RBhCaWd9B7BjyANPAxJwQN/16MRR+VawZEQoOncefrQhdaP0DUx9j7Yey16KL9rgcR35cACyqjyQ3iUR0N1mfkkFXi1DIRwrvBCL63YEYUQYRUB0Se2XYdGkCjICIciREAYJk33MTqQ2ghtgebJPfzqVEQ8R5JSpviv2k2k7L1oj9MK4CMKZrJaNauv8X4tMk5aOEzY2Ne8/Rq5vcZZ5yR5ojfIy9t8Qlpa+5tzgpgZ8bQSM1nMXUKRJguPgrFOzQtfSH9aUp8fXgkkvkgQPWVyQsIHW4NaPFW8JJrMyBi7aCxNcUci4Sn0IRg5NjWvoQu+llGF8+7BkQMyj9vLjKjTUkkBiQMUwCh2YCQVCjMbkIDpqIq2wiIkDpMHAzG6RqpHohgOAuSGYUR+FqKyaQ+8sgjffYvEOT4iknPl28GRKjLtCyqZrOZE5gU7MaELhhRFI1g4FzkcyqjVzP9DxAx9liceIj5ae74lfjWJNolzUXI1WItplogIgpDm8F3eDLaiffDnLE4Tz311CQECQLCL+YQv9onZbHmE56mgdBmmaOS/ovwMYeCPq6tgAgfZAC1tmlKxuHzDetAsh6FpJXlOylLIxREDJ6E4CsgsXUmCBOdBSI2Y7FTQwvhQWYeUFMtTk4p9m+AiPJUcyk0EWiOGDQOEpmKyHmE0WglkSCzvQqYuSw6g7kXWmihxIRlIKKP2hZuNiE0I3au/hXHps0AESBq8YRGFP2Jq3cxJMBkFzebedpDskSd3XKlNnOWo7lFY2GX0arR/nrXYrMwCZq//OUviXcAhT1DtFI8Qtqiv/knnW0VoBWUaWy1QMT76gfu5ppQCWGHF8wXwOAPATDME05/+2OAiuzr5oiE5Mdovvxjcznmztj4efhQgkauvjNDv3o+EWBhzRCghKf+o4soFrqgQWghtCZrRviar6MWbwaIcBvccsstfUNQN42JG6EIkH2FSn407BMBHiIlm2++eRo8HwO/RPg81I3oVDyL2uKNxONuAcsmyHs6DESgu0hLEN0zBFPWpi7AwH6ffvrp0/3whUTd6qHdkA5FEMEUwsKIGu1zUAG4yCaGlEBQk/3AAw/UBBBtao9Hnj8oP/boTy9fMT/AACC0NSZfOw7aoJV6Mb9FDUQAg/mxYAke88dXFjxCa+QXUx5Y5JOFY+HbOhBOeFsL+BJCaybNReq8Lx900EGJt7UhKkbC42XlgSSBEQJGeVqKjZHBQyFwjIOmI/stuZaBiPXh2It6IGIc2kQHJkrQhUZuTdCS8nRBK+O2VmslIKI+AZCgibK0J74V4ATkAlxr1RP3S0HEwIvZRAR6YyCONIvcxhcTp7xFDBQgd+w4dZ8WQRMhTSCfQbsvbAcw8iErgyJlaB3aYe8hDGeoBe95sW8mTVjO16LQOJ5DbM5dfVWXjAEQMLIx2Tx022239S2IeL/simFsGZZjHGXlevGe8Gfso0BXKnQnxgns+dIC6M29+SGo8IgFkac1HjDXgJ+Zm++DBcIcCv4x58pZcPwpyqqLxuHTBZu4LBrtMXntVg3TTL9okOFPCx5yxc/akIEEIZvvR/y2DviLbG9XX9x3BVZCvCGM8s/iNyAFYmgTdLHQbadAl9i7ojy6oKM1SBhGHfmrscemPmsx/8wYQqsHRAAs/7zsNyApBZFAmLh6mdmg0aKDkCRAHMkCo1qRFCR2JIRkphiYQUiAB1iY3DBlojxiUDmjLb/dq5XUSZuZbbbZkhSLcsEEUU/ZFZI3I01ttOILoM6iy1BJaMxpSCJjahpdzGU9GqATJ18stGJ5z238Ui9+wLzmilpd1oaFw0SmjRTNCkJEmL4417TVomTFoyR7lMW74cvQR/1ysh7/gs8fopwrhy4TmICSbb4s8gP+E320p0pYuvic8KPZc7zWcoLano/mQtnGrG10KTPh3AOMHLA0r7IE+IEsLaRosqCHNerrbKBqg1sjqRREDHagM1DhV7H9PDSZdtoEchxMbEU2czt11XqXj4N6SwvJS4Ba5XvpPgEhEkMi2vtjw1JRstYar3J27jJ/yubawnemBpOUyl6PtiQwLYV2KjoFaGq13c59AMJJynQJv0/UZ0wEqD7QZmJnczx3ZRL5uBTPlI1bHbQRIBV7UPLvowtTi7bOpK83zqALv6G+F8sDCSYbkCE8823Fb31iGQBzQj7u17oCmVIQaQR9WimDOSxEV5EL+xUi5t9Kffl3TBLVF8qyqTudTAipgqmowog6FJJxUu9JYhK3llTtjxbqQDuLxTwVk12TVHDSltZaL9EYSEofozGrmDCdTkxhJgjnpy3vFnQk4yHFAQsnKtOGSRM84ep9e1uEh2vxi3JAkCNfW/k2tMU5apzWCVOyXiKY0ZEGYZ6KJ5gBFq4GzmQAV0z6Yz0SEvpOU2okDSqIQD+mgH0etrTbRFMkXCOdrlWGugxBaSOAqpMJ+IlKhS+kk3V3a12YCrNxAPIDiKqVqeW1+u9984sZ/RuKMhABKqQtDYezMCRyrTrdZ9PzbfGVUfdrmQL91VHvGdPHRj4mFr8cHwyHrEzrBRokOp4gEMPBa8z6I6LCYR9HU6AD4PG8mCxqfg50iuf4185tdBGB4SyOZ8X3429aBl8G3yPzMG+u0DBsdbABLh+RiXdd8bgolNB3hJLzz2v9HlQQYetiRr4LKlcnAcQAMSSAEjlhsyJcJ5IJFfIjVdjb9SazE212Qx2kKd+HcDsJZux8U41m7wN0zjpOQYsyr4mgI+0RY1ssFqwDuvORvTI60FZE/ER0BgJAtEnzxEMclfwHTDkflMqc+EwzC5WWkU/BK6I8NAM0kIWq+dPy44/37HMR8bNlAGijC21apApd+ERowGXaQ9Thii4ADV3y/h/10Ur0idlI2JYlffMtDpBsJg0qiFDJ2MaiOPm9Hs10uF5Z9SKicyI4odpNmMkHe6SKRdQpYGq3XwP5PqYjxfgCgD5GJuHY/iIVzWSRj5CmnH55+mmHo4+Ut79I5iMbKN5olWZ8CXw10ccjjzwyBQ+K9SlnYxzzBvDm6USLY4YpU5aYZHa5AhLCVcQGeEWbnKplAFRWV/Eek0n7tu3nHcfFcq3+Pagg0monm32PNLBFvmgTNluP8pje5PPuY/qhkEjO7bffPu1PAACdyEA9r173Ih3xCu1DmLiYSfh6/MNUFBkhuDqZmCk0lPwHjZ2svydBxGRF7gSxOllXJ/ozkHUAYGq3DU6dAI+ogznQ6yBiXoJXal37m7v8O/2Va/bZQNUb/SgFkXyj1e//B6ShQAvqttAeR2gnM0kIoIYCDYfSGAFJKYgEwlTXoUkBavlAZIurSr1HgVIQGUpIWo11aGla1Xx3dr5BYimI9B5WViMaERSIBUurqVLvUqACkd6d25ZHFou/5Qr+9yLwENmyJ6gCknap2b3vVyDSvXMzQnrGsWoncSc21flw0leqznPhVK1Sb1KgApHenNeWR2Wjk08SnLxFI2klec8WbLtPfV6vvgpEWqHkyPFOBSIjxzwNWi8tdueCOnqwVRBhutiW7vN4J8JXIDJo0zdCGqpAZISQvXsbBQBOnCv7VweN9hr42HVp+7r/M1uBSKOUGznLlYIIJqjy0KNBfHTmOwsbzgBKO3zgfSDi4z3ffbRTV/Vud/Ij2CsFkZETD6tet0MBC/7mm29OJ6r7txq0CE5WZ9r6MrqR7FAciz2S30yaShMJivTmtRREKtTvTtQfyHmhKTgL1GfnTl3Xlnv+a6HDghrJtI689lJpIr3PR2CxFER6Ey+rUfVHAaDh83OH4zjVSnLP2R4OCmokF08l836lifRH9d54VoFIb8xj26OgNTiFi+nhfA/JPf+HxFkaDuiplx2uAzgiVSASlOjtawUivT2/DY/OaWVOvvLlrpPCHV7DnHHiVvxrhHpX4VzAE6kCkaBEb18rEOnt+W14dA4i8u8lnU7uHFzHGgIE534637ORHIfeAA+//Z8gZ9I6hd+5qE7vymsqDXeuKtjVFKhApKunZ/A6RxPxT6odg8hBGv/VrZUeAB9HCPpXBw43ckq8f3Q2bNiwaudqKwTt8ncqEOnyCRqs7oX/w3b10ChabZu24R+CqcuxkpGH2j/8apV+I9t7FYiMbDNW9beiQJdRoAKRLpuQqjsVBUY2CvwfVU8GM/OoCBgAAAAASUVORK5CYII=)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "UAygbf_gAeoP"
   },
   "source": [
    "\n",
    "***Info(D)*** is just the average amount of information needed to identify the class label of a tuple in D. Also known as ***entropy*** of D. \n",
    "\n",
    "*pi* is the probability that an arbitrary tuple in D belongs to class Ci (number of values in D belonging to Ci) and is estimated by |Ci,D|/|D|."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "dnCNZLVXyhIR"
   },
   "outputs": [],
   "source": [
    "## CALCULATE INFORMATION/ENTROPY NEEDED TO CLASSIFY NEW TUPLE\n",
    "\n",
    "def info_d(df):\n",
    "    target = df.keys()[-1]   #Get target variable column name\n",
    "    uvalues = df[target].unique()  #Unique values in the target: 'Yes', 'No'\n",
    "\n",
    "    entropy = 0 #Initialize Info(D) to 0\n",
    "    for value in uvalues:\n",
    "        weight = df[target].value_counts()[value]/len(df[target])\n",
    "        entropy += -weight*np.log2(weight)\n",
    "    return entropy\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "KfNXmz9DfoBq"
   },
   "source": [
    "### **Function to get InfoGain from a particular attribute**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "P4aqBLPPyM_w"
   },
   "source": [
    "### ![image.png](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAToAAABZCAYAAACuVegcAAAgAElEQVR4Ae3dBZT0thEH8BRTZua0KTNzm74ypMzMzMyUclNmZmZmZmZuU2Zmrvt++jL3FMXywq3X+13k93xa26IZjf6aGcHt0VWu//3vf9067//+97+pvKnCsWidip5W7vbkaSx5mCrfkIepyl9HuWh091179L30bh0Vy8uIhpgqzOuyyt9T0dPKbUCXy3HIQ/5up/1Go7vvqgJdX+Qx32G6a6pwLNqmoqeVuz15Gksepso35GGq8tdRLhprdDagOxBgx2qIYHwLdwGPEfd73/te95Of/CSxfN18+f3vf9997Wtf6/75z38Olj+WPEyVb/B5qvLXUS4aa3RWgS4SrSsM1XqqcCw6p6JnmXJ1/q9//evdn//85wQE3/jGN7o//elPSXiWyQ9Py3T/+te/uvvd737ds571rJXmW5ZTe/74xz/eXf/61+9+85vfDJY/ljxMlW/wY6ry11EuGt19VxXo+iKP+Q4jXFOFY9E2FT2LlvuPf/yj++QnP9nd/e537771rW91v/jFL7rrXOc63Wc/+9mVtgugu/Od79w98YlPPEi+BPTHP/5x96lPfSrd6uJ3GR5wwAFb4LmMvHzoQx/qrnjFK3a//vWvD1J+ya/0cQf9Cfp2EEkHIwWNNTob0DXTNWlvH/7wh7t99923E9Lsfv7zn3eXutSlupe97GVJwwsB2m5YA7r//Oc/3Yte9KLunOc8Z3fCE54w3Wc961m7S1/60t1lL3vZ7jKXuUx37nOfu7vZzW7WfeYzn+l+8IMfLAV4DegOhg875kUDujk0xbFae7vAsI70zLib3vSm3T777NO94x3v6P76178mjee6171ud7aznS1pVauqRw3o5M9/dre73a071KEOle7b3e523Q9/+MPupz/9adL2nvGMZ3SnP/3pEwje6EY36mh3ANI1b/0a0I0l6dPnSwZCDsraVDW6SLSuMHwIU4Vj0TkVPYuU++9//7v72c9+1n3xi1/srnWta3Vf+MIXOqbs+9///u7a17520qAWyQ8va/Fpi3e60526JzzhCUko83jq8aAHPSiB3LGPfezusY99bAcYI78//vGP3dOf/vQEdEc5ylG6u971rt3f/va3re8Rbyj84Ac/mDTXX/3qV4Pp5LGT7uDzTqKppAWN7r6rCnR9kcd8p9KuqcKxaJuKnmXK5ZdjInLYAz2+NBrQ3//+95W1y5BGRzt78IMf3B3mMIfpbnvb23a//e1vtwQXPW5g94hHPKI7/OEP313lKldJM7jRieeRn6bRjSXp0+cbMtJXkwZ0zUeX5IKQALpLXOIS3Ytf/OIEcu9973uTxiSC76sIa0AHrEwQ0PYOfehDd/e+9723tMK8XPGYsHvuuWd31KMeNdWTljhv/RrQpWbckX+WArpItK4wRuWpwrHonIqeZco1AcHhf/GLX3xLk1smH7yspauZrszWxz/+8d1xjnOc7ljHOlb3mMc8JuVR5kPrY77S6PbYY4+OH5GZXcarPTfTdWeZ5Hm/1ebuvquq0eUZrON3TTDX9X4sGtdV/1WUQ6Pik3vTm960sO9r3vJrQEfTs77usIc9bHerW90qTUBokzLfBnTLAVXwcSw534R80ejuu6pA1xd5zHcY5ZoqHIu2qehZplxalVnOcPCP0R4101XZ97///bvDHe5wKfTcVz5BDtP1yEc+cneHO9xha8Iij2/m2IRDOSvbTNfE1h35h8yH3JcEVoEuEq0rjBFnqnAsOqeiZ1PLrWl0f/jDH7q73OUuSaOj2QFEbVLS8Ze//CWZtUzXK13pSmlxc188JqrFz3Z55N+b6bqcRjhW/1hlvmTF3XdVga4v8pjvEOyaKhyLtqno2dRy+zQ6WteTn/zk7vjHP353tKMdrXvUox7V9Wl0aHrVq17VnexkJ+toc2aFzQiXciPeu9/97u4Wt7hF2sKWf28a3ViSPn2+2j3kvqxNA7o265pkIgRk7LAGdLQ4s60WLseuBxXL68Mc3X///dPykytc4QpJmytN04hvBvlzn/tc0gzzfBrQlRCwc561fbR/SVUV6CLRusLSRFn381h0rpuOWnk0JDsgAMAvf/nLbYf8X4vMdka9+kxXa+NoZ4DuAQ94QPKrRfwImazPfe5zu1Od6lTdEY94xC3fXHzPQ1ree97znu7hD394J522je/NdG2mawmCa30mjK6pwrGInYqestwf/ehH3U1ucpPuIhe5SHfhC1+4u9CFLpRCz/aSXu5yl+suf/nLD4bi2CYmvYXFH/vYxxZur1KjA8AmF5ijgO6BD3zgFiiFPAAua/vOeMYzdsc4xjHS7o2vfOUrB4snPiB9+9vf3t3+9rdPOzxKE7hpdGNJ+vT5kvmQ+7I2VY2ujDjmM+G3z/F3v/tdWg1vhK+ZJEHIdkMjfBxHtF3a1MVMZT5bGXlut56rSs/se/Ob35w0IoBiDZr7uMc9bveUpzyl+8AHPpA29AMCG/v7wne+850JIC0B4Ut761vfuiVY89YzBzppHANlkXDsb73HPe6RNE+7IkIeXv7yl3fnOc950vFKtqV9+9vfrsoH8D3f+c6XTijJ2yPqt5OBDo1oxre4tbv3QX/I5azQgKF/6CfruKI/ko9lryE6Jwc6gPb5z38+CbFZNL6X29zmNjOP0YmGWyaUBrDut99+aR/nsoyNdLSGl7zkJZ0OmW+X8n2Z+o2VjtBz5u+9994JWADdEY5whKTRff/730/kDNWXEDL9LnjBC3bHPOYxtw102v4FL3hB0tRMLrjPdKYzJZBylBJ5cNPy3vWud3XOx5s1ADLNbSO72tWudpCBJ+jaqUCHPq4Emq+tcfhGU6cta7egP2R2KCTPBrtHP/rRiYdDcVf1TX986EMfmrTwaONF80Zjjc4q0EWiPMRI2lZ556NGHn+e31/+8peTv+UNb3hDEuanPe1pSdBtMpc+fCurDPmoHvKQh6RjgWJzd5SFlpK+8tlol9Ombs5wswcT4OX8WGW9o47bCY3Sr33ta9PG+NDqzHZ++tOfTjOds+qLdp3gYhe7WPeWt7xl4faRPjb1K+ub3/xmanfaIjArwxzg5qX7Na95TXeNa1wjtUNJzyb46NSJ77CUK88BSrl8zfMbODhSi4+T6e4UGmsMTfLgefBhVl7K17624NnzDPQijd99dc7fhRYYaeYNYcv73ve+7p73vGdSfPJy580Dje6+qwp0ZWQZYKDDGI2Wzi4zcjjt4qlPferWcoAy3dCzxuE0psUBHBeV+xOf+MTWSIJI16pCAuaEDCfcBsilAroulWkb0pWvfOVEHxrRisa4r3rVq3ZvfOMbk6CGUEb9vvrVr6a8aXbB8FXVe5X5mNU8wxnOsKXV2TeKLkeMx2g6VB7Bvt71rpc601C84Ese4lnfwZuL5jMUH5Bf85rX3FiNzkD4yEc+MtWR5hVyhqe53zPkclaIF0xWIOcOkPjud7/bkUmyGPyalZfyHZX10Y9+dGvGOtKQjxvf+MZbfUPd8Tn6hsGFb5R8qU/0gUg/K2QNWRbkVBo+2EUvNNbonBvoZIBxNK9b3vKWaVM15/XrXve6dArtokTJDzEc3BzbAXTRKFHhVYbyps1d/epX72xYl3fkj6k6Yfh4aDtW6d/xjndMNAM3mgKTyuGQwFCHMhJFHtIzh6ng4R+Kb5sUAvuXvvSl3alPfeotsGPCos1R6sBuqL7odPqvvbFD8fC0/D420Mn/Fa94RXeDG9xgqw3yemyC6aqOtCX15Hvk77zvfe+btt45ZTl4Nm9HJ9csCWcHkj1AFzRHXhEO5aleXBvO+ovZ6jy+PsqcVV/9g/y88IUvTAO//uHUaOcFOizV6TPcIYvggjoqA2BSgIKOvA5Dv6Wv0VkFukhUhtRgBLH/gUIOTGXcoWfpOMA5joFn+LYivzFCmoglB7S56KRRTtRVPWiqGtLpGAQo4gAAJh5gdpQQwLMvNL4LgTezmBCLn39TxqY8mwRg6pz85CffAjuanRH6O9/5zmj1zE3XMfgRx8GbtNBRSn5vgukasmbChcXAXDMrHu8XDckZPyaA4AoKmvN8+t7l3/3GO5NBeAf0yu+e9VlnBZo8MnNPcYh4rDHW3QlOcILu6Ec/elqwHf0s4swK9T+TXOph0J0VP/+ORnfftTDQqYRRCGIHOOWFzftb41BTw2yNhhgzdFItE42wl+VEvQPoABkTy3+sim9C6ZjWwI7Gxy+n80Yc3znD+TjkVZazSc9GbSOytWkEF7gT0o985CNbWt2q6zsG0AE0+Qpp3bQ5vqJorzxcBujwgOYevIi2LkPf1YNsl9/KZxq/QZdWxDIovy/yrG40QmZrrY6191FO8O6GN7zh1j9Eim95GECn3nhdYgCwM4vvFJrTnva0CaxmlZ3n77cJJeY8q2seXkZ65bj7rirQ9UX2zsmwOjigw+C4VCiETcEuhXqXv493X/rSl5L5x6kNgORlFImKRjzvI48gSN5RxryhTs0vYsSJUSbPJ36LxyxFI60s8vc9LvVh0lqmQasD/lFv8ZkPzAhmAL64Ip9NC2l2/lfDiU50ogR0TFhanSUcaFp1fbUxH4wtX6viC8viOc95TloS42AATm3l9OXP0U5jX+Sf4/jXjEw2YfAjZZ798Z7Z5VRkLp5ZF+tCZzbTDOjyS14B3rn8xDvy571ngEnO/H8NYBf9xbeoq7jxPu+LeZkG7/vc5z4JXMTpu8gD8KHRXeACF0iA1BePVmldJBPXCgrAtchFS/T/SriY+AXnvdAbNJdpqkAXicqQs946KgQEmmOkkdLewmc+85mJqd4x8wCihaoAkhNWxc26aWQbs8348Qnw+wEi08wYTVior967NYKZ2Oh8i4aYF6MEmsr03hEao5FG0uEJUMTL+UBozGjRgIAd4UZvxPHPW3QmdRa3r7zIdxNCA81ZznKWLa2OCcsxHss5Vll/fNKpOMlXlS9Tm3yZYTRLq5PX+EqGWBIhu7V40ZZCfGDFkNvwoeXf/Qac2tsAp/3L7+WzQwxYM0c60pGSZpR/J4f6kf7Ep6iO6svV4J8D6U8mBgGkOOc4xzmSLJ797GdPR1w55ur1r399kj3p+Lu8c9/85jfvnv3sZ2/JpXK1CReNs/3yFQN5nfzGB6a2vmGhOQAr43imxJz0pCdNdTrNaU6T+nJfvNq7AO/znve8qT2jjWrx47147r5rKaADUGZXdGIZG1EveclLJr+VWVlmA5DjN8BcHcekg8bli3je856XTqqwlYfZZP+i9T4aBxACOKM+0PFePqc85SlTmvAJBPHzhEbPhz3sYWm9VkxClOkwi3ZjFKHNEQgdKJiYhznQMfkcEpkDnY5Gq3OIJfXet7K8ePZNfBrIMmHks52QFqtj8dcBb7e2Ifhhum8nf7wbO722Ck1uFeXl7c0cM5P+pCc9KU02xdKniAPkyAAlgHZcA4CILwyg4wc2oRffABPtFECQQ7/JG5Az0WVnisFVn9HvHEKqb5FDfnPt6DaYAH0KCS033hvAzLg///nP3+q/+qoJBCA2BHTMVusn9dlyGVXUX5gDHRO31o/Ie54u/227ogNg9UdLkPJvtd9kzN13VYGujCxznRKDmZuEyrPZIz4p/xRYw+gczAPvrLN69atf3flHJrQpgCMflQE4mGZkoPLLy62Bzn/+86cJA8DjHVVYJzzd6U6XmKZu8pk3BI62LVG51bsvnXcAGmN1crOSNabROJmuhIt2+7jHPe4gcdWZUOIHR3M0aFkuGtBrOl9+NIZFQpNCQKrMd9Fn9cBrnYo2G2DnpF/LDPBhEX4vWv4q4kcdV1VPdYpLnvIHeBY488syY70DcjFQA7ioR6TtC+VnIoLWz+IBBC6DHaAkOwZJmhMgA7KsHYcU+M9o5IoGS87IYpzjx0fnnTrIC/ACsPB1eU9xoKjQCgPUXvnKV6Z3XDa0qdoVQMds1WeD12X8MF3JkVnYPlMe/dxIFJ++y3eTHQYC5c5zqU+tTnMDHSYxT4EcZuu8LkRRjY0QAMoaNYwHckYi6rVGYwZ6jgvg8G8RHAyXP+2BJmR1N9BxqTgzZ2ygU45R1qjGnDCC1phm1KXRGlktyWCqqH9ciwCdWVr+KkJJeBcJCWgIZtR1OyHQtGA7NDuauNNECOp28sUP8rKpIdpK+qIty5CMGBCAHbk0yAEjg+m8F/nR5mc+85nT0owoG48smPaPiaxXM4uqL5m0oCXpP+QOIPnH4mROGhYPrc4kkrzwmTanL+qz4kQZNLtlgE56gGmvsZ0x4eMsaRbPf5EzYB7veMdL/OGOKi8Ap852RfVdawM6Fc5vzKNBGE1ufetbpxEjvvsG6PgIOEStqTHSAEGNZWFhaHORhp+ElkdF9c6aG2buRS960a3R0nuNCQx0Pip3qMHex/dZoZHW6EBDqZmuRkBCwGSggcaiX3nnt3KBNloJTOmfE5dgAWzaHjNc3kP19Q0PlwmH8p3Fl77v2knHjckJPlQdaNly0M58v9e97pVmojct5B6JgTbnh9+1WyckK0AIYMXkVi1++R6PdXJyZmlV8FY8v9XH7CdTFKACA3xk4lIayFyk0c9ocpY0hZxZHsLE5f4JkIv4NLoYwIJuk276tX7qXVlfzyangC8tk3UE6Pri8feyTExE5P21jIsHBuoa7+ACQMUj9JTp+57R6O67FtLoAF1MRGBgXFRqmg2nKA0O81WEz40ZyOkaGpo0wIrqzK/HHHAxgY0A5zrXudKkg/QuFQeYtD/qOyFzxfc8zAnN389jutKM1JOWZnIEuEYeqcADyyRMJkeo5WhW75K5QGse0zXok35ZoIs6rjI0MABymq3O4nj1ZfMnJ7R7Wombr3STQgN0dO5crqLNyxAfdHJ9wWDGNzc0G1um96yTAzGdmFIQvPWNfBlkzaJSEmhH5EOfos0BJKayNN6/7W1vS8CjLnhNjswQx/KokE3x3QYxlpf1n8rybh7TldXG1XSKU5wimb/hMsnpkxdQPslJTpIOi9Bfo3+X8cINABj7rrVpdGXhGBYaHb9CDnRMTdqNiQiAgWDxgZ5ZKJMP1HXvXaEC888FI2pAp9PRAiwsZkLlDScvebrlox4cxfE+wllAJ72Gs9ODIPErKifqG/kQNoIJdAEiUxMf8njizgt00hEMnZ9P06i8SKiTrtJ0VR+mGfOZZqtjBcgFjcuEeBmdcBNDNJV0acfyEoemQYvTF+xvpiHh1yJgF0DH/1QCnX5iHSAFwfl7IYfhLiGjoWGTM32DzM4DdFwsBmcTbczgoHsW0InHFGa20ub0yeBX8Mgz0GLB0OYczpC7PPJ4QIx/Tv+h0fVdawO6YEKEmKpBjQbUbc/xzaJT2pyRKDo+/wX1m88Lg4FegJ3RwcppZiqC5GMGyZFBQCQcvd7T5oAlEABm0fB56L2RVVrAIV3+HdABVZMRfaarRjf5EDNdTK2gLUJ00VAtMyBY+XlsESdCcQmeeCYjwqTwPa+X37RhtDE/+FoWCfmKQhvJ8y3LmffZhASzCB8slo6TfudNv5PioSW/8Zcmp4PqB9HZ+Z/4NXOwy9P1/ZaGmQjQytX/Bi79xsJ2fjjp9TUamEkA5fDjmcQiZ+SLlcWC8Ox2FL2B2MSWZ3moP3ObxWQgz98DOuZszXTlO7eMJcxW/amkC8ipCzDk7lCf6Nt5XLTT9PRVfsf8W/47TFegaTIi/4aWkPe+933AWTVdywxoXBiBeWHbRxwTCux35mm8AxZGLHa6Dmw2KQc6iA/Ro6PKH4NOfOITpxHTqAftOVSBa4wOQWCENBBbuvgFACLgUIf4LlQvZVkr1gd08jADZhY11+ikddPkLArmMzCLZdcDJ28O9kG3kBABOn5BZpt4eX3y+vkGCJWxaKicWr6LvscDmoqZbT5YIJfXc9H8Nim+uixan7w9ARwZ00GZjQFyEUenBID4p8PH+zJUB0DG8tDR+dxKGdIfuHVo6/GNbFgmAtD0QQMjrU770+gM4pQH8d1hupJX78kVZYMpzO0SfS7qZ/LDBIcVB+U3dZYHAOOuCY0ueCpkRVnDaCeEeuJRzMpGGRFSSlgt+uosoPPP1LmRou/LAy8AtTL4DSNfYdRpIaATWWIAJFP+K3Y/Qo0YiMdolbU2B9CFGSWtylj1bR0N9T5Azjdgo8HCoeldTEZIY7EhzYZgaUjamtHBpU4R+q1D0q74KoAQjS6+RygeYaS2B9BFPoSANuf0Wg2JRiMqzSZu5QNrdbHcIgeYVFjxx3cjmsaXv7KivE0MaXI0BZqcGfUAueDfmKGOaTkSDWUMPh1wwAHJPCR/i9CRIh/4h9ZFk7cgOEAu/67eOrB1du5wn+Rx9A2TWOTCYEKDAmhhAotLVlgN3DQUg5AV703UkU07Bmg40alN/gE+fHR5z3kP/MRnNemv4jArKSDyyy/lWGUQC4bzb/hHuaHN6R/WswKq6BtCEyb6BpzQT9Uh6p7n5bf38tRXWWt9lzhlf414lBbmO5yg5ebl+J0/RxrhTI0ujk1BrE5gRwCzJhgGCDmsjVLQNgqjWfn3dUCO/yveC4GkESRXbTWUSQraEt8QDU0DAUMNE8zLQ1oIbZLwOE0D8/o0OmUaqQiVDm11e+SjzuqILvS5lY3GuP3bPAAnrnrmtPT91mkJgxN9o5xNDWnOTBqaNI06li2sq77a1uyltlbmqsvlW3KMECDSVvPmn7cry8LsbG2GMOLqnDS/GCjivTCW7pCpkDVyxtyjUYmDF9xA4thgH+kNnNxC0lmW5dk3sgjoyH/Q5b3vdk6I75YfxQPYRtrIO0IaH+WCBZL3YyAffVLf0DejX0QI7PRl9Y/8hkJKDcCuaXT6qkGBNVcuFjZgmVBRdpk+5CcHuPg9E+gicV8YxMS3eI6w7z3nNjPSyJcDoLjSaTy/I4z3fSHfAW2OPxB4DQGd9HwLNMkYEZXn/Tx30DQrlJfRkzZHqDxHOZsYGl2Z9GZYaRixxWmeeusQDniUxzzx++jXOWhKZmKjzSMe0CXUfGBMw77QQFymi/RC9eMnjkF13npKm9+RLn/X93sonm99d55PfM/f+V2+RzMlAxiwZmrxI52wjFM+M6VpdQa//FueR+13Hn/W71lAR2vWT21/68sr6lB+i/cBbnlYBbo80nZ/5xUimAQvN1vlL868obgaQyfg6zOiUZv9phkYWfvyY6KJp9OY8MjLSw/b/IPROiegIzSe++qRlzvVd3VjBtDmuBeAHI1aB5q3ftLrGDTXZekwGNBKmD85v/wGUkwwM/puSy44xfkQmXIWrzPNaFGxU6esB8c93xONbl66UsQN/IO2uA0Q4d7JF+LXqh18qX33nuwadPBd/mNc+iAzmRZvUC0vWqe+QybMai9yBW/60qwF6Ghx/AY0MA5bq8mpp/kVDTFPyGTlV6NK66A2OlvB79QNvrYwBeSf5+e3WR9mM5PGc3zP67Lsb8JhhI2p/jz/KGcTQnXAQ8sXgByHb34eWsm32jOh5eDOfSWL0lcDOvkAXf5Rk0Ruy5rIjTR4TTO3H5KT3gZwg2h00KjHTgI64M+k5dviHiFrJslicBqS2+DHUBz5Wx1h8DKIrepSdty0OWsIw+zMyxDHJAZtzmTfPHUu09fSVIEuKraKkGpt9CW0QA7YlPnGaD5PaLbF5IhFvQTfKCCkkViEHIsslVHmJx7tgVbH5xLfy/os+iwfEyGEj7BEvpsYEmIgZ0YcyOGnztLHr776M1kNXGYGzewBur548+QHmGqmqzz5fzjBAbLyxI98AR5NTh1ofPZbhzsk6rMq03VReRgjPnrtizbxxwdsDV7wY1Z5wY9Z8fi6TSzga+6rm5Vu6Dvry6BkRpqvkM8vX58ZafVjPkLll8tuIs5QiEZ331UFur7Iy74zQUDzYlbSAlS2vOLdrBDTOGZ1jjhFQl7S0Ur46QDdUD60GaBrEiJM2LI+izwDCWUyoandoVVEvTYlxBP8Axi2eNkSp01ox8wJfJ0ntADc8gAzcfjNkT3E7yH6hzQ6eXI10OYsW4iOl+eH9+ixwNZsZfjsoj47SaMLWq2/o8nlcoYnQ1fwYyiOb4DCaSb6V64hz0o39J1CYdUCvzyT1WRNCUhAzoDJZHUcVPl9KP/4hsYanWsBOsJspM2XmETlIowKDoVA0rQ7M4VfRqcVX95GIFqKDmhmlRYZmqMy8nz9DrCL5ShRj2VC9Fl0aSY6VpxHPnm5ZT3W/YxPZvX22muvBB40JWBlImKRG6hYkCoNYEf/snTWgI6g89EYINXTbF9onSXfzPirk+UU3Bd5G+wkoMNjtGnH0ORCzmaF0T6z4vmuTUx0WKUAgLZ7aUvgZsIp392U56uvUj6Y5dp5mQuNNTqrQBeJ1hVihrKGQs5LAm9xL/8cVVh8dj2Vnr+I/03Ib8cnOJQfYYnOs106CUd0+DyvofJn0bvK7wYFZ4jFZn3gsd0b0DE1tlNPbdBnumoXgr/nnnumtVsmTbzr46fBL9Z58e8YUCPeTjJdc7la9HfwY950eB1gOm+aWfHkN1SPWd9n5S9vd99VBbq+yGO+Q4RrKMR8Wp1OK/QsvpDfyXuaWvl9Vr5T0zVP/Yb4Mk96Jjrzz3Ic5qZ1TNsNgQqfzjzl1+o/pNFZMG6nikmIcHn05RMaHeA20O1UjS4xesk/wbclk+8WydBYo3O3AjrcDkJWHY7Vkquu57L5GQxMxAAMg8IqwjChttMu8wCdhedG+1o5AXT+sQ9fUO7L20mm63ZkNORmO3lselo01uhsQNczMbLKBg3Gt7BfY+8DOryyCNmaOX63IaAzIcWBbdaVSyO2aAW/G9Dtkubgxyple9PyQmONzirQRaJ1hWG7TxWORedU9Owu5dLUSh+duluGxO9m37PtV+Jpo5Iuk0AOj3DyDW2O8zyP13x0uzp/8G0sOd+EfNHo7ruqQNcXecx3GOWaKhyLtqnoWUe5zGEzo7G9apn261dGgpwAAAXHSURBVNPoCKu1jrGshJkdApzTRXuznozWx19oR0wZr2l0uyQ7+DaWnG9Cvmis0VkFuki0rpCAKmuqcCw6p6KnVi6Nx2LMUvOpxa+9p2FZO8hctIG8Fm/W+z6NznpIExAmF5itALXMx75lO1AcH+ScQYtQ+ebKeE2jaxodEG5AdyDAHlKAzjoma80svVl2YKGFWe9kiY+jta3QLwFm3ucS6ICaRcIOZq0BHZAzI7v33nundZNOlwnfXFluA7oGdINAt25VVKdzTRWORe9U9NTKtXDTMhNbcJblt9lbu0CcneaMv1XtdQVy1kratG9BMqBz1qGdFzac22EjtKPFHldbhdBhsSmA66Onma6JLVv9atfTzvxL5kPuSwqrGl0ZceznqOBU4Vj0TUVPrVxLS6x9szTEVYs39B6oOH3GQm3a4aqAjqZoO5q9q06icdvWZe2f22ZwN/+dWVm+wRrARf0b0O2S7ODHWHK+CfmisUZnFegi0brC0uRY9/NYdK6bjqHyLKR1gKhdJBYQo3ko/qzvJgnsQlml6Uo7o6XRPPtC7wLgZtXP92a6NtMVCFeBbt0ITShdU4Vj0TsVPWW5AXLOAvSPiDju+cf46pziaiP1UOiEE1pgni/tcJUaXYDuKuWgaXS7JDvabSw534R80VijswHdIWTBME2I9uW/w8fx1ExP5/jZDuZ4q6EQQJanwjSg24TuPV8dagAwX+rdI1YDujk0xbGaMgRs6pBG5zBDJ/IG0C2i0Tnrr2l0Y0nJ+PmG/I1f0nQlLAV0kWhdYZgtU4Vj0TkVPX3lWlriX8jFeV+c/3x1/GFOfh0KaYTW3uX5juGjy/PXJtt9bj665qMDvc10PYSYrkCDP46JGhod09VxVnGiyVDo/y6MZbo6/NM2rwA1gqm+qwidbOt/mZrkWCS/FHkH/Ql+7iCSDkYKGmt0NqA7hAAdM9Uho3xtzFACYULCLgn/YwOIDYUWCNPgpANItlvREPfdd990mKdTZGO3BQkMgZsVysvG/FjwOyv+ot8d2UVbpb0uUq+D9aLd/EXwbTcnY7D6aKzRWQW6SLSuMEbzqcKx6JyKnrJc6878rwH/Qi4/mLKMN88zX52N+Mxg//TaWjcLh/0j6nnS4/WmxxtLHqbKN/g9VfnrKBeN7r6rAd0O3gJGi2Gy0dzsLgBGfG2ELgR/mdAOBpqg/0jlv1EJ/Z+BRda3LVPuduu9SPp1dMx1lhH8XmeZ6y4Lje6+qwp0fZHHfIcprqnCsWibih7lmlxwVpv/2OU/m/u/GrS5Kfk8JT8WoXsseZgq3+D7VOWvo1w01uisAl0kWlcYI85U4Vh0TkWPcpmY/rm0/7MB5OxRnbI+eLy7lD+WPEyVb/B9qvLXUS4a3X1XFej6Io/5DiNcU4Vj0TYVPVGuRb0mGZomt5h8jSUPU+Ub8jBV+esoF401OhvQHUJmXUMAWjgf4K2jY66zjGj3dZa57rLQWKOzAV0DuiSPISAt3AWE6+6kY5cX7Tp2OVPmj8YanVWgi0TrCsOHMFU4Fp1T0dPK3d6J1WPJw1T5hjxMVf46ykWju++qAl1f5DHfYYRrqnAs2qaip5W7PXkaSx6myjfkYary11EuGmt0NqBrpmuSwRCQFjbTdR2gNEYZuwXQjUF4y7NxoHGgcQAHNkaja83RONA40DgwFgca0I3F2ZZv40DjwMZwoAHdxjRFq0jjQOPAWBxoQDcWZ1u+jQONAxvDgQZ0G9MUrSKNA40DY3GgAd1YnG35Ng40DmwMBxrQbUxTtIo0DjQOjMWBBnRjcbbl2zjQOLAxHGhAtzFN0SrSONA4MBYHGtCNxdmWb+NA48DGcKAB3cY0RatI40DjwFgcaEA3Fmdbvo0DjQMbw4EGdBvTFK0ijQONA2NxoAHdWJxt+TYONA5sDAca0G1MU7SKNA40DozFgQZ0Y3G25ds40DiwMRxoQLcxTdEq0jjQODAWB/4PskEK34vGIkcAAAAASUVORK5CYII=)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "q0CXRqxf_WSf"
   },
   "source": [
    "Using the formula shown above, we get the info gain for each attribute in the dataset. Using that we get the entropy for each atribute needed to decide the node of every level in the decision tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "EyD848EKylVP"
   },
   "outputs": [],
   "source": [
    "def info_a(df,attribute):\n",
    "  target = df.keys()[-1]   #Get target variable class name\n",
    "  target_classes = df[target].unique()  #Target Classes: 'Yes' and 'No' here\n",
    "  values = df[attribute].unique()    #Get all unique values from the particular attribute/column\n",
    "  info_a = 0\n",
    "\n",
    "  for val in values:\n",
    "      entropy = 0\n",
    "      den = len(df[attribute][df[attribute]==val])\n",
    "      for class_ in target_classes:\n",
    "          fraction = len(df[attribute][df[attribute]==val][df[target] ==class_])/(den+eps) #Info(Dj) from the formula shown above\n",
    "          #eps adds a infinitesmal small value to avoid NaN or infinity\n",
    "          entropy += -fraction*log(fraction+eps)\n",
    "      fraction2 = abs(den/len(df)) #|Dj|/|D|\n",
    "      info_a += -fraction2*entropy #Get InfoA(D)\n",
    "  return abs(info_a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "KbejaH_BBYt7"
   },
   "source": [
    "### **Choose the attribute with the highest Info gain**###"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Q6lGXodNBjhr"
   },
   "source": [
    "***Information gain*** is defined as the difference between the original information requirement (Info(D)) and the new requirement (InfoA(Dj) after partitioning on A).\n",
    "\n",
    "The attribute A with the highest information gain is chosen as the splitting attribute at a given node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZJ1zpbZRU1Sk"
   },
   "outputs": [],
   "source": [
    "def info_gain(df):\n",
    "    InfoGain = []\n",
    "    for key in df.keys()[:-1]:\n",
    "        InfoGain.append(info_d(df)-info_a(df,key))\n",
    "    print(InfoGain)\n",
    "    return df.keys()[:-1][np.argmax(InfoGain)]\n",
    "  \n",
    "def find_subset(df, node,value):\n",
    "  return df[df[node] == value].reset_index(drop=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "v3U6pnOEDulc"
   },
   "source": [
    "### **Recursive Function to Build Tree**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "4hzhzC_rD9LQ"
   },
   "source": [
    "Build tree until all subsets are classified or info gain is minimal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "DZQ0LAt0wleD"
   },
   "outputs": [],
   "source": [
    "def buildTree(df,tree=None): \n",
    "\n",
    "  #Get max information gain attribute to select the node to split at\n",
    "  node = info_gain(df)\n",
    "  print(node)\n",
    "  atr = np.unique(df[node]) #Values to build the tree branches (sub-tree) below\n",
    "  #These attributes decide which of them to split on further\n",
    "  \n",
    "  #Initialize or create an empty tree    \n",
    "  if tree is None:                    \n",
    "    tree={}\n",
    "    tree[node] = {}\n",
    "  \n",
    "  #Check purity of subset and stop recursion when minimum purity\n",
    "  for value in atr:\n",
    "    subset = find_subset(df,node,value)\n",
    "    clValue, count = np.unique(subset['play'], return_counts=True)                        \n",
    "    \n",
    "    if len(count)==1:\n",
    "        tree[node][value] = clValue[0]                                                    \n",
    "    else:        \n",
    "        tree[node][value] = buildTree(subset) #Recursive call\n",
    "                  \n",
    "  return tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Vuqcg2L1VGwO"
   },
   "outputs": [],
   "source": [
    "tree = buildTree(df)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "WMLLuBN_VTn6",
    "outputId": "123a1e9a-2e26-4099-bbea-0d63c963fb6b"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'outlook': {'overcast': 'yes',\n",
      "             'rainy': {'windy': {False: 'yes', True: 'no'}},\n",
      "             'sunny': {'humidity': {'high': 'no', 'normal': 'yes'}}}}\n"
     ]
    }
   ],
   "source": [
    "pprint.pprint(tree)"
   ]
  }
 ],
 "metadata": {
  "colab": {
   "name": "ID3.ipynb",
   "provenance": []
  },
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}