DecisionTreeAlgorithms_Scratch.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import math\n",
    "from IPython.display import display\n",
    "filename='C:/Users/Madhu/Desktop/whether.csv'\n",
    "data=pd.read_csv(filename)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\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>Rainy</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>False</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Rainy</td>\n",
       "      <td>Hot</td>\n",
       "      <td>High</td>\n",
       "      <td>True</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>False</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>False</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</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>5</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Cool</td>\n",
       "      <td>Normal</td>\n",
       "      <td>True</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>True</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>Rainy</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>False</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</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>9</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Mild</td>\n",
       "      <td>Normal</td>\n",
       "      <td>False</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>Rainy</td>\n",
       "      <td>Mild</td>\n",
       "      <td>Normal</td>\n",
       "      <td>True</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>True</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>False</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>Sunny</td>\n",
       "      <td>Mild</td>\n",
       "      <td>High</td>\n",
       "      <td>True</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     Outlook Temperature Humidity  Windy Play\n",
       "0      Rainy         Hot     High  False   No\n",
       "1      Rainy         Hot     High   True   No\n",
       "2   Overcast         Hot     High  False  Yes\n",
       "3      Sunny        Mild     High  False  Yes\n",
       "4      Sunny        Cool   Normal  False  Yes\n",
       "5      Sunny        Cool   Normal   True   No\n",
       "6   Overcast        Cool   Normal   True  Yes\n",
       "7      Rainy        Mild     High  False   No\n",
       "8      Rainy        Cool   Normal  False  Yes\n",
       "9      Sunny        Mild   Normal  False  Yes\n",
       "10     Rainy        Mild   Normal   True  Yes\n",
       "11  Overcast        Mild     High   True  Yes\n",
       "12  Overcast         Hot   Normal  False  Yes\n",
       "13     Sunny        Mild     High   True   No"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(data)\n",
    "total_examples=data.shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "features=data\n",
    "features=features.drop('Play',axis=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_entropy(data):\n",
    "    shape=data.shape\n",
    "    pyes=0\n",
    "    pno=0\n",
    "    counts=data['Play'].value_counts()\n",
    "    if 'Yes' in counts:\n",
    "        pyes=-counts['Yes']/shape[0] * math.log((counts['Yes']/shape[0]),2)\n",
    "    if 'No' in counts:\n",
    "        pno=-counts['No']/shape[0] * math.log((counts['No']/shape[0]),2)\n",
    "\n",
    "    entropy = pyes+pno\n",
    "    return entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_average_entropy(attribute,data):\n",
    "    total_examples=data.shape[0]\n",
    "    average_entropy_info=0\n",
    "    for value in attribute.unique():\n",
    "        value_df=data.loc[attribute==value]\n",
    "        #display(value_df)\n",
    "        average_entropy_info+=(value_df.shape[0]/total_examples)*get_entropy(value_df)\n",
    "    return average_entropy_info"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_gain(data_entropy,attribute,data):\n",
    "    info=get_average_entropy(attribute,data)\n",
    "    gain=data_entropy-info\n",
    "    return gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "\n",
    "def construct_tree(tree,curr_split,features,tree_order):\n",
    "    global root\n",
    "    for value in tree:\n",
    "\n",
    "        max = 0\n",
    "        if root != None:\n",
    "            new_data = data.loc[data[curr_split] == value]\n",
    "            data_entropy = get_entropy(new_data)\n",
    "\n",
    "        else:\n",
    "            data_entropy = get_entropy(data)\n",
    "            new_data = data\n",
    "\n",
    "        for attribute in features:\n",
    "            gain = get_gain(data_entropy, new_data[attribute], new_data)\n",
    "            if gain > max:\n",
    "                max = gain\n",
    "                split_attribute = attribute\n",
    "\n",
    "        if max == 0:\n",
    "            split_attribute = None\n",
    "            print(\"Reached leaves at {} \".format(curr_split))\n",
    "            continue\n",
    "\n",
    "        else:\n",
    "            root=split_attribute\n",
    "            #print(\"Split attribute is \",split_attribute)\n",
    "            tree_order.append(split_attribute)\n",
    "            print(\"Tree order at {} = {}\".format(curr_split, tree_order))\n",
    "            construct_tree(data[split_attribute].unique(),split_attribute,features.drop(split_attribute, axis=1),tree_order)\n",
    "            tree_order=[]\n",
    "    print()\n",
    "    return\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tree order at None = ['Outlook']\n",
      "Tree order at Outlook = ['Outlook', 'Humidity']\n",
      "Tree order at Humidity = ['Outlook', 'Humidity', 'Temperature']\n",
      "Tree order at Temperature = ['Outlook', 'Humidity', 'Temperature', 'Windy']\n",
      "Reached leaves at Windy \n",
      "Reached leaves at Windy \n",
      "\n",
      "Reached leaves at Temperature \n",
      "Tree order at Temperature = ['Windy']\n",
      "Reached leaves at Windy \n",
      "Reached leaves at Windy \n",
      "\n",
      "\n",
      "Tree order at Humidity = ['Windy']\n",
      "Tree order at Windy = ['Windy', 'Temperature']\n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "\n",
      "Tree order at Windy = ['Temperature']\n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "\n",
      "\n",
      "\n",
      "Reached leaves at Outlook \n",
      "Tree order at Outlook = ['Windy']\n",
      "Tree order at Windy = ['Windy', 'Humidity']\n",
      "Tree order at Humidity = ['Windy', 'Humidity', 'Temperature']\n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "\n",
      "Tree order at Humidity = ['Temperature']\n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "Reached leaves at Temperature \n",
      "\n",
      "\n",
      "Tree order at Windy = ['Temperature']\n",
      "Tree order at Temperature = ['Temperature', 'Humidity']\n",
      "Reached leaves at Humidity \n",
      "Reached leaves at Humidity \n",
      "\n",
      "Tree order at Temperature = ['Humidity']\n",
      "Reached leaves at Humidity \n",
      "Reached leaves at Humidity \n",
      "\n",
      "Reached leaves at Temperature \n",
      "\n",
      "\n",
      "\n",
      "\n"
     ]
    }
   ],
   "source": [
    "root=None\n",
    "construct_tree([1],None,features,[])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Tree visualization coding is not done yet, will be done later."
   ]
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}