week9_p72_DecisionTree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "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>District</th>\n",
       "      <th>House Type</th>\n",
       "      <th>Income</th>\n",
       "      <th>Previous Customer</th>\n",
       "      <th>Outcome</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "      <td>Not Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>Yes</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>No</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "      <td>Not Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>Yes</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>No</td>\n",
       "      <td>Not Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>Yes</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "      <td>Not Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "      <td>Not Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>No</td>\n",
       "      <td>Responded</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    District     House Type Income Previous Customer        Outcome\n",
       "0   Suburban       Detached   High                No  Not Responded\n",
       "1   Suburban  Semi-detached   High               Yes      Responded\n",
       "2      Rural  Semi-detached    Low                No      Responded\n",
       "3      Urban       Detached    Low               Yes  Not Responded\n",
       "4   Suburban  Semi-detached   High                No      Responded\n",
       "5   Suburban  Semi-detached   High               Yes      Responded\n",
       "6   Suburban       Detached    Low                No  Not Responded\n",
       "7      Rural       Detached    Low               Yes      Responded\n",
       "8      Rural  Semi-detached   High                No      Responded\n",
       "9      Rural  Semi-detached   High               Yes      Responded\n",
       "10     Urban       Detached    Low               Yes  Not Responded\n",
       "11     Urban  Semi-detached    Low               Yes  Not Responded\n",
       "12     Urban  Semi-detached   High                No      Responded\n",
       "13     Urban       Detached    Low                No      Responded"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Dataset for Building a decision tree\n",
    "df = pd.DataFrame({\"District\": [\"Suburban\", \"Suburban\", \"Rural\", \"Urban\", \"Suburban\", \"Suburban\", \"Suburban\", \"Rural\",\n",
    "                                \"Rural\", \"Rural\", \"Urban\", \"Urban\", \"Urban\", \"Urban\"],\n",
    "                   \"House Type\": [\"Detached\", \"Semi-detached\", \"Semi-detached\", \"Detached\", \"Semi-detached\",\n",
    "                                  \"Semi-detached\", \"Detached\", \"Detached\", \"Semi-detached\", \"Semi-detached\", \"Detached\",\n",
    "                                  \"Semi-detached\", \"Semi-detached\", \"Detached\"],\n",
    "                   \"Income\": [\"High\", \"High\", \"Low\", \"Low\", \"High\", \"High\", \"Low\", \"Low\", \"High\", \"High\", \"Low\", \"Low\",\n",
    "                              \"High\", \"Low\"],\n",
    "                   \"Previous Customer\": [\"No\", \"Yes\", \"No\", \"Yes\", \"No\", \"Yes\", \"No\", \"Yes\", \"No\", \"Yes\", \"Yes\", \"Yes\",\n",
    "                                         \"No\", \"No\", ],\n",
    "                   \"Outcome\": [\"Not Responded\", \"Responded\", \"Responded\", \"Not Responded\", \"Responded\", \"Responded\",\n",
    "                               \"Not Responded\", \"Responded\",\n",
    "                               \"Responded\", \"Responded\", \"Not Responded\", \"Not Responded\", \"Responded\", \"Responded\"]},\n",
    "                  columns=[\"District\", \"House Type\", \"Income\", \"Previous Customer\", \"Outcome\"])\n",
    "\n",
    "df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "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>District</th>\n",
       "      <th>House Type</th>\n",
       "      <th>Income</th>\n",
       "      <th>Previous Customer</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>Suburban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>Rural</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>Yes</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Semi-detached</td>\n",
       "      <td>High</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>Urban</td>\n",
       "      <td>Detached</td>\n",
       "      <td>Low</td>\n",
       "      <td>No</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    District     House Type Income Previous Customer\n",
       "0   Suburban       Detached   High                No\n",
       "1   Suburban  Semi-detached   High               Yes\n",
       "2      Rural  Semi-detached    Low                No\n",
       "3      Urban       Detached    Low               Yes\n",
       "4   Suburban  Semi-detached   High                No\n",
       "5   Suburban  Semi-detached   High               Yes\n",
       "6   Suburban       Detached    Low                No\n",
       "7      Rural       Detached    Low               Yes\n",
       "8      Rural  Semi-detached   High                No\n",
       "9      Rural  Semi-detached   High               Yes\n",
       "10     Urban       Detached    Low               Yes\n",
       "11     Urban  Semi-detached    Low               Yes\n",
       "12     Urban  Semi-detached   High                No\n",
       "13     Urban       Detached    Low                No"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Features\n",
    "features_data = df[[\"District\", \"House Type\", \"Income\", \"Previous Customer\"]]\n",
    "\n",
    "features_data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0     Not Responded\n",
       "1         Responded\n",
       "2         Responded\n",
       "3     Not Responded\n",
       "4         Responded\n",
       "5         Responded\n",
       "6     Not Responded\n",
       "7         Responded\n",
       "8         Responded\n",
       "9         Responded\n",
       "10    Not Responded\n",
       "11    Not Responded\n",
       "12        Responded\n",
       "13        Responded\n",
       "Name: Outcome, dtype: object"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Target\n",
    "target = df[\"Outcome\"]\n",
    "\n",
    "target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "# Calculate entropy function\n",
    "def calculate_entropy(df_label):\n",
    "    # Count each type of value and value's counts\n",
    "    classes, classes_counts = np.unique(df_label, return_counts=True)\n",
    "    # Sum of entropy each type of value\n",
    "    entropy_value = - np.sum(\n",
    "        [(classes_counts[i] / np.sum(classes_counts)) * np.log2(classes_counts[i] / np.sum(classes_counts))\n",
    "         for i in range(len(classes))])\n",
    "    # Return entropy value\n",
    "    return entropy_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "# Calculate information gain function\n",
    "def calculate_information_gain(dataset, root_feature, target_feature):\n",
    "    # Count all entropy\n",
    "    dataset_entropy = calculate_entropy(df[target_feature])\n",
    "    # Count each feature from root feature\n",
    "    feature, feature_count = np.unique(dataset[root_feature], return_counts=True)\n",
    "\n",
    "    # Calculate the weighted features entropy\n",
    "    weight_feature_entropy = np.sum(\n",
    "        [(feature_count[i] / np.sum(feature_count) * calculate_entropy(dataset.where(dataset[root_feature] == feature[i]).dropna()[target_feature]))\n",
    "         for i in range(len(feature))]\n",
    "    )\n",
    "    # Calculates information gain from the parent node entropy and the sum of child nodes\n",
    "    feature_information_gain = dataset_entropy - weight_feature_entropy\n",
    "    return feature_information_gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [],
   "source": [
    "# Define decision tree\n",
    "def create_decision_tree(dataset, original_df, feature_list, label, parent = None):\n",
    "    data_feature = np.unique(original_df[label], return_counts=True)\n",
    "    unique_data = np.unique(dataset[label])\n",
    "\n",
    "    # If attribute is only one, return the attribute\n",
    "    if len(unique_data) <= 1:\n",
    "        return unique_data[0]\n",
    "\n",
    "    # If there is no data, return maximum value attribute\n",
    "    elif len(dataset) == 0:\n",
    "        return unique_data[np.argmax(data_feature(1))]\n",
    "\n",
    "    # If there is no feature, return parent node's attribute\n",
    "    elif len(feature_list) == 0:\n",
    "        return parent\n",
    "\n",
    "    else:\n",
    "        # Define parent nodes feature\n",
    "        parent = unique_data[np.argmax(data_feature[1])]\n",
    "        # Select feature\n",
    "        item_values = [calculate_information_gain(dataset, feature, label) for feature in feature_list]\n",
    "        optimum_feature_index = np.argmax(item_values)\n",
    "        optimum_feature = feature_list[optimum_feature_index]\n",
    "        # Make tree structure\n",
    "        decision_tree = {optimum_feature: {}}\n",
    "        # except the feature that gained most information\n",
    "        features = [i for i in feature_list if i != optimum_feature]\n",
    "\n",
    "        # Expand tree\n",
    "        for value in np.unique(dataset[optimum_feature]):\n",
    "            # drop row with missing data\n",
    "            min_data = dataset.where(dataset[optimum_feature] == value).dropna()\n",
    "            min_tree = create_decision_tree(min_data, df, features, label, parent)\n",
    "            decision_tree[optimum_feature][value] = min_tree\n",
    "        return decision_tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Information Gain for the \"District\" =  0.24675\n",
      "Information Gain for the \"House Type\" =  0.23612\n",
      "Information Gain for the \"Income\" =  0.15184\n",
      "Information Gain for the \"Previous Customer\" =  0.01611 \n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "{'District': {'Rural': 'Responded',\n",
       "  'Suburban': {'House Type': {'Detached': 'Not Responded',\n",
       "    'Semi-detached': 'Responded'}},\n",
       "  'Urban': {'Previous Customer': {'No': 'Responded', 'Yes': 'Not Responded'}}}}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print('Information Gain for the \"District\" = ', round(calculate_information_gain(df, \"District\", \"Outcome\"), 5))\n",
    "print('Information Gain for the \"House Type\" = ', round(calculate_information_gain(df, \"House Type\", \"Outcome\"), 5))\n",
    "print('Information Gain for the \"Income\" = ', round(calculate_information_gain(df, \"Income\", \"Outcome\"), 5))\n",
    "print('Information Gain for the \"Previous Customer\" = ', round(calculate_information_gain(df, \"Previous Customer\", \"Outcome\"), 5), '\\n')\n",
    "\n",
    "tree = create_decision_tree(df, df, [\"District\", \"House Type\", \"Income\", \"Previous Customer\"], \"Outcome\")\n",
    "tree"
   ]
  }
 ],
 "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.9.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}