Decision_Trees_InfoGain_Computation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Information Gain Computation in Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tutorial illustrates how impurity and information gain can be calculated in Python using the `NumPy` and `Pandas` modules for information-based machine learning. The impurity calculation methods described in here are as follows:\n",
    "- Entropy\n",
    "- Gini index\n",
    "\n",
    "We start off with a simple example, which is followed by the Vegetation example in the \"Information-Based Learning\" Chapter in the textbook."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A Simple Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose you are going out for a picnic and you are preparing a basket of some delicious fruits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import warnings\n",
    "warnings.filterwarnings(\"ignore\")\n",
    "\n",
    "import pandas as pd\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0     apple\n",
      "1     apple\n",
      "2     apple\n",
      "3    orange\n",
      "4    orange\n",
      "5    banana\n",
      "6    banana\n",
      "dtype: object\n"
     ]
    }
   ],
   "source": [
    "lst = ['apple']*3 + ['orange']*2 + ['banana']*2\n",
    "fruits = pd.Series(lst)\n",
    "print(fruits)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is the relative frequency of each fruit in the basket, which can be considered as the probability distribution of the fruits."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "apple     0.428571\n",
       "orange    0.285714\n",
       "banana    0.285714\n",
       "Name: proportion, dtype: float64"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "probs = fruits.value_counts(normalize=True)\n",
    "probs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you like, you can define the probability distribution yourself as below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.42857142857142855, 0.2857142857142857, 0.2857142857142857]\n"
     ]
    }
   ],
   "source": [
    "probs_by_hand = [3/7, 2/7, 2/7]\n",
    "print(probs_by_hand)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that Shannon's model defines entropy as\n",
    "$$H(x) := - \\sum_{i=1}^{\\ell}(P(t=i) \\times \\log_{2}(P(t=i))$$\n",
    "The idea with entropy is that the more heterogenous and impure a feature is, the higher the entropy. Conversely, the more homogenous and pure a feature is, the lower the entropy.\n",
    "\n",
    "The following calculation shows how impurity of this fruit basket can be computed using the entropy criterion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "np.float64(1.5566567074628228)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy = -1 * np.sum(np.log2(probs) * probs)\n",
    "entropy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The gini impurity index is defined as follows:\n",
    "$$ \\mbox{Gini}(x) := 1 - \\sum_{i=1}^{\\ell}P(t=i)^{2}$$\n",
    "The idea with Gini index is the same as in entropy in the sense that the more heterogenous and impure a feature is, the higher the Gini index.\n",
    "\n",
    "A nice property of the Gini index is that it is always between 0 and 1, and this may make it easier to compare Gini indices across different features.\n",
    "\n",
    "The impurity of our fruit basket using Gini index is calculated as below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "np.float64(0.653061224489796)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini_index = 1 - np.sum(np.square(probs))\n",
    "gini_index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In comparison, let's compute impurity of another fruit basket with 7 different fruits with equal frequency."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0         apple\n",
      "1        orange\n",
      "2        banana\n",
      "3         mango\n",
      "4     blueberry\n",
      "5    watermelon\n",
      "6          pear\n",
      "dtype: object\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "apple         0.142857\n",
       "orange        0.142857\n",
       "banana        0.142857\n",
       "mango         0.142857\n",
       "blueberry     0.142857\n",
       "watermelon    0.142857\n",
       "pear          0.142857\n",
       "Name: proportion, dtype: float64"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst2 = ['apple', 'orange', 'banana', 'mango', 'blueberry', 'watermelon', 'pear']\n",
    "fruits2 = pd.Series(lst2)\n",
    "print(fruits2)\n",
    "probs2 = fruits2.value_counts(normalize=True)\n",
    "probs2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "np.float64(2.807354922057604)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy = -1 * np.sum(np.log2(probs2) * probs2)\n",
    "entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "np.float64(0.8571428571428572)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini_index = 1 - np.sum(np.square(probs2))\n",
    "gini_index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, both entropy and Gini index of the second fruit basket is higher than those of the first fruit basket."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Vegetation Example"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now work out the details of the impurity calculations for the Vegetation dataset in Chapter 5 in the textbook.\n",
    "\n",
    "Let's first import the dataset from the Cloud."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "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>stream</th>\n",
       "      <th>slope</th>\n",
       "      <th>elevation</th>\n",
       "      <th>vegetation</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>False</td>\n",
       "      <td>steep</td>\n",
       "      <td>high</td>\n",
       "      <td>chapparal</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>True</td>\n",
       "      <td>moderate</td>\n",
       "      <td>low</td>\n",
       "      <td>riparian</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>True</td>\n",
       "      <td>steep</td>\n",
       "      <td>medium</td>\n",
       "      <td>riparian</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>False</td>\n",
       "      <td>steep</td>\n",
       "      <td>medium</td>\n",
       "      <td>chapparal</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>False</td>\n",
       "      <td>flat</td>\n",
       "      <td>high</td>\n",
       "      <td>conifer</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>True</td>\n",
       "      <td>steep</td>\n",
       "      <td>highest</td>\n",
       "      <td>conifer</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>True</td>\n",
       "      <td>steep</td>\n",
       "      <td>high</td>\n",
       "      <td>chapparal</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   stream     slope elevation vegetation\n",
       "0   False     steep      high  chapparal\n",
       "1    True  moderate       low   riparian\n",
       "2    True     steep    medium   riparian\n",
       "3   False     steep    medium  chapparal\n",
       "4   False      flat      high    conifer\n",
       "5    True     steep   highest    conifer\n",
       "6    True     steep      high  chapparal"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import pandas as pd\n",
    "import io\n",
    "import requests\n",
    "\n",
    "url_name = 'https://raw.githubusercontent.com/akmand/datasets/master/FMLPDA_Table4_3.csv'\n",
    "url_content = requests.get(url_name, verify=False).content\n",
    "df = pd.read_csv(io.StringIO(url_content.decode('utf-8')))\n",
    "df"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For convenience, we define a function called `compute_impurity()` that calculates impurity of a feature using either entropy or gini index."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "impurity using entropy: 1.557\n",
      "impurity using gini index: 0.653\n"
     ]
    }
   ],
   "source": [
    "def compute_impurity(feature, impurity_criterion):\n",
    "    \"\"\"\n",
    "    This function calculates impurity of a feature.\n",
    "    Supported impurity criteria: 'entropy', 'gini'\n",
    "    input: feature (this needs to be a Pandas series)\n",
    "    output: feature impurity\n",
    "    \"\"\"\n",
    "    probs = feature.value_counts(normalize=True)\n",
    "    \n",
    "    if impurity_criterion == 'entropy':\n",
    "        impurity = -1 * np.sum(np.log2(probs) * probs)\n",
    "    elif impurity_criterion == 'gini':\n",
    "        impurity = 1 - np.sum(np.square(probs))\n",
    "    else:\n",
    "        raise ValueError('Unknown impurity criterion')\n",
    "        \n",
    "    return(round(impurity, 3))\n",
    "\n",
    "\n",
    "# let's do two quick examples.\n",
    "print('impurity using entropy:', compute_impurity(fruits, 'entropy'))\n",
    "print('impurity using gini index:', compute_impurity(fruits, 'gini'))\n",
    "# how to test for an incorrect compute_impurity_criterion value:\n",
    "# print('impurity using gini index:', compute_impurity(df['stream'], 'foo'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's calculate entropy of the target feature \"vegetation\" using our new function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "np.float64(1.557)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "target_entropy = compute_impurity(df['vegetation'], 'entropy')\n",
    "target_entropy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compute the information gain for splitting based on a descriptive feature to figure out the best feature to split on. For this task, we do the following:\n",
    "1. Compute impurity of the target feature (using either entropy or gini index).\n",
    "2. Partition the dataset based on unique values of the descriptive feature.\n",
    "3. Compute impurity for each partition.\n",
    "4. Compute the remaining impurity as the weighted sum of impurity of each partition.\n",
    "5. Compute the information gain as the difference between the impurity of the target feature and the remaining impurity.\n",
    "\n",
    "We will define another function to achieve this, called `comp_feature_information_gain()`.\n",
    "\n",
    "As an example, let's have a look at the levels of the \"elevation\" feature."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "elevation\n",
       "high       3\n",
       "medium     2\n",
       "low        1\n",
       "highest    1\n",
       "Name: count, dtype: int64"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "df['elevation'].value_counts()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see how the partitions look like for this feature and what the corresponding calculations are using the entropy split criterion."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "level name: high\n",
      "corresponding data partition:\n",
      "   stream  slope elevation vegetation\n",
      "0   False  steep      high  chapparal\n",
      "4   False   flat      high    conifer\n",
      "6    True  steep      high  chapparal\n",
      "partition target feature impurity: 0.918\n",
      "partition weight: 3/7\n",
      "====================\n",
      "level name: low\n",
      "corresponding data partition:\n",
      "   stream     slope elevation vegetation\n",
      "1    True  moderate       low   riparian\n",
      "partition target feature impurity: -0.0\n",
      "partition weight: 1/7\n",
      "====================\n",
      "level name: medium\n",
      "corresponding data partition:\n",
      "   stream  slope elevation vegetation\n",
      "2    True  steep    medium   riparian\n",
      "3   False  steep    medium  chapparal\n",
      "partition target feature impurity: 1.0\n",
      "partition weight: 2/7\n",
      "====================\n",
      "level name: highest\n",
      "corresponding data partition:\n",
      "   stream  slope elevation vegetation\n",
      "5    True  steep   highest    conifer\n",
      "partition target feature impurity: -0.0\n",
      "partition weight: 1/7\n",
      "====================\n"
     ]
    }
   ],
   "source": [
    "for level in df['elevation'].unique():\n",
    "    print('level name:', level)\n",
    "    df_feature_level = df[df['elevation'] == level]\n",
    "    print('corresponding data partition:')\n",
    "    print(df_feature_level)\n",
    "    print('partition target feature impurity:', compute_impurity(df_feature_level['vegetation'], 'entropy'))\n",
    "    print('partition weight:', str(len(df_feature_level)) + '/' + str(len(df)))\n",
    "    print('====================')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The idea here is that, for each one of the 4 data partitions above, \n",
    "  1. We compute their impurity with respect to the target feature as a stand-alone dataset.\n",
    "  2. We weigh these impurities with the relative number of observations in each partition. The relative number of observations is calculated as the number of observations in the partition divided by the total number of observations in the entire dataset. For instance, the weight of the first partition is 3/7. \n",
    "  3. We add up these weighted impurities and call it the remaining impurity for this feature.\n",
    "\n",
    "For instance, remaining impurity as measured by entropy for the elevation feature is 0.918 x (3/7) + 1.0 x (2/7) = 0.679. \n",
    "\n",
    "Information gain is then calculated as 1.557 - 0.679 = 0.878.\n",
    "\n",
    "Now we are ready to define our function. There is a bit of coding in here, but we can assure you that trying to figure out how things work in here will be rewarding to improve your Python programming skills."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def comp_feature_information_gain(df, target, descriptive_feature, split_criterion):\n",
    "    \"\"\"\n",
    "    This function calculates information gain for splitting on \n",
    "    a particular descriptive feature for a given dataset\n",
    "    and a given impurity criteria.\n",
    "    Supported split criterion: 'entropy', 'gini'\n",
    "    \"\"\"\n",
    "    \n",
    "    print('target feature:', target)\n",
    "    print('descriptive_feature:', descriptive_feature)\n",
    "    print('split criterion:', split_criterion)\n",
    "            \n",
    "    target_entropy = compute_impurity(df[target], split_criterion)\n",
    "\n",
    "    # we define two lists below:\n",
    "    # entropy_list to store the entropy of each partition\n",
    "    # weight_list to store the relative number of observations in each partition\n",
    "    entropy_list = list()\n",
    "    weight_list = list()\n",
    "    \n",
    "    # loop over each level of the descriptive feature\n",
    "    # to partition the dataset with respect to that level\n",
    "    # and compute the entropy and the weight of the level's partition\n",
    "    for level in df[descriptive_feature].unique():\n",
    "        df_feature_level = df[df[descriptive_feature] == level]\n",
    "        entropy_level = compute_impurity(df_feature_level[target], split_criterion)\n",
    "        entropy_list.append(round(entropy_level, 3))\n",
    "        weight_level = len(df_feature_level) / len(df)\n",
    "        weight_list.append(round(weight_level, 3))\n",
    "\n",
    "    print('impurity of partitions:', entropy_list)\n",
    "    print('weights of partitions:', weight_list)\n",
    "\n",
    "    feature_remaining_impurity = np.sum(np.array(entropy_list) * np.array(weight_list))\n",
    "    print('remaining impurity:', feature_remaining_impurity)\n",
    "    \n",
    "    information_gain = target_entropy - feature_remaining_impurity\n",
    "    print('information gain:', information_gain)\n",
    "    \n",
    "    print('====================')\n",
    "\n",
    "    return(information_gain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that our function has been defined, we will call it for each descriptive feature in the dataset. First let's call it using the entropy split criteria."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "target feature: vegetation\n",
      "descriptive_feature: stream\n",
      "split criterion: entropy\n",
      "impurity of partitions: [np.float64(0.918), np.float64(1.5)]\n",
      "weights of partitions: [0.429, 0.571]\n",
      "remaining impurity: 1.250322\n",
      "information gain: 0.306678\n",
      "====================\n",
      "target feature: vegetation\n",
      "descriptive_feature: slope\n",
      "split criterion: entropy\n",
      "impurity of partitions: [np.float64(1.371), np.float64(-0.0), np.float64(-0.0)]\n",
      "weights of partitions: [0.714, 0.143, 0.143]\n",
      "remaining impurity: 0.9788939999999999\n",
      "information gain: 0.578106\n",
      "====================\n",
      "target feature: vegetation\n",
      "descriptive_feature: elevation\n",
      "split criterion: entropy\n",
      "impurity of partitions: [np.float64(0.918), np.float64(-0.0), np.float64(1.0), np.float64(-0.0)]\n",
      "weights of partitions: [0.429, 0.143, 0.286, 0.143]\n",
      "remaining impurity: 0.6798219999999999\n",
      "information gain: 0.877178\n",
      "====================\n"
     ]
    }
   ],
   "source": [
    "split_criterion = 'entropy'\n",
    "for feature in df.drop(columns='vegetation').columns:\n",
    "    feature_info_gain = comp_feature_information_gain(df, 'vegetation', feature, split_criterion)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's call it using the gini index split criteria."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "target feature: vegetation\n",
      "descriptive_feature: stream\n",
      "split criterion: gini\n",
      "impurity of partitions: [np.float64(0.444), np.float64(0.625)]\n",
      "weights of partitions: [0.429, 0.571]\n",
      "remaining impurity: 0.5473509999999999\n",
      "information gain: 0.1056490000000001\n",
      "====================\n",
      "target feature: vegetation\n",
      "descriptive_feature: slope\n",
      "split criterion: gini\n",
      "impurity of partitions: [np.float64(0.56), np.float64(0.0), np.float64(0.0)]\n",
      "weights of partitions: [0.714, 0.143, 0.143]\n",
      "remaining impurity: 0.39984000000000003\n",
      "information gain: 0.25316\n",
      "====================\n",
      "target feature: vegetation\n",
      "descriptive_feature: elevation\n",
      "split criterion: gini\n",
      "impurity of partitions: [np.float64(0.444), np.float64(0.0), np.float64(0.5), np.float64(0.0)]\n",
      "weights of partitions: [0.429, 0.143, 0.286, 0.143]\n",
      "remaining impurity: 0.333476\n",
      "information gain: 0.31952400000000003\n",
      "====================\n"
     ]
    }
   ],
   "source": [
    "split_criteria = 'gini'\n",
    "for feature in df.drop(columns='vegetation').columns:\n",
    "    feature_info_gain = comp_feature_information_gain(df, 'vegetation', feature, split_criteria)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We observe that, with both the entropy and gini index split criteria, the highest information gain occurs with the \"elevation\" feature. \n",
    "\n",
    "This is the for the split at the root node of the corresponding decision tree. In subsequent splits, the above procedure is repeated with the subset of the entire dataset in the current branch until the termination condition is reached."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}