Advanced Learning Algorithms/C2_W4_Decision_Tree_with_Markdown.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Practice Lab: Decision Trees\n",
    "\n",
    "In this exercise, you will implement a decision tree from scratch and apply it to the task of classifying whether a mushroom is edible or poisonous.\n",
    "\n",
    "# Outline\n",
    "- [ 1 - Packages ](#1)\n",
    "- [ 2 -  Problem Statement](#2)\n",
    "- [ 3 - Dataset](#3)\n",
    "  - [ 3.1 One hot encoded dataset](#3.1)\n",
    "- [ 4 - Decision Tree Refresher](#4)\n",
    "  - [ 4.1  Calculate entropy](#4.1)\n",
    "    - [ Exercise 1](#ex01)\n",
    "  - [ 4.2  Split dataset](#4.2)\n",
    "    - [ Exercise 2](#ex02)\n",
    "  - [ 4.3  Calculate information gain](#4.3)\n",
    "    - [ Exercise 3](#ex03)\n",
    "  - [ 4.4  Get best split](#4.4)\n",
    "    - [ Exercise 4](#ex04)\n",
    "- [ 5 - Building the tree](#5)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"1\"></a>\n",
    "## 1 - Packages \n",
    "\n",
    "First, let's run the cell below to import all the packages that you will need during this assignment.\n",
    "- [numpy](https://www.numpy.org) is the fundamental package for working with matrices in Python.\n",
    "- [matplotlib](https://matplotlib.org) is a famous library to plot graphs in Python.\n",
    "- ``utils.py`` contains helper functions for this assignment. You do not need to modify code in this file.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from public_tests import *\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"2\"></a>\n",
    "## 2 -  Problem Statement\n",
    "\n",
    "Suppose you are starting a company that grows and sells wild mushrooms. \n",
    "- Since not all mushrooms are edible, you'd like to be able to tell whether a given mushroom is edible or poisonous based on it's physical attributes\n",
    "- You have some existing data that you can use for this task. \n",
    "\n",
    "Can you use the data to help you identify which mushrooms can be sold safely? \n",
    "\n",
    "Note: The dataset used is for illustrative purposes only. It is not meant to be a guide on identifying edible mushrooms.\n",
    "\n",
    "\n",
    "\n",
    "<a name=\"3\"></a>\n",
    "## 3 - Dataset\n",
    "\n",
    "You will start by loading the dataset for this task. The dataset you have collected is as follows:\n",
    "\n",
    "| Cap Color | Stalk Shape | Solitary | Edible |\n",
    "|:---------:|:-----------:|:--------:|:------:|\n",
    "|   Brown   |   Tapering  |    Yes   |    1   |\n",
    "|   Brown   |  Enlarging  |    Yes   |    1   |\n",
    "|   Brown   |  Enlarging  |    No    |    0   |\n",
    "|   Brown   |  Enlarging  |    No    |    0   |\n",
    "|   Brown   |   Tapering  |    Yes   |    1   |\n",
    "|    Red    |   Tapering  |    Yes   |    0   |\n",
    "|    Red    |  Enlarging  |    No    |    0   |\n",
    "|   Brown   |  Enlarging  |    Yes   |    1   |\n",
    "|    Red    |   Tapering  |    No    |    1   |\n",
    "|   Brown   |  Enlarging  |    No    |    0   |\n",
    "\n",
    "\n",
    "-  You have 10 examples of mushrooms. For each example, you have\n",
    "    - Three features\n",
    "        - Cap Color (`Brown` or `Red`),\n",
    "        - Stalk Shape (`Tapering` or `Enlarging`), and\n",
    "        - Solitary (`Yes` or `No`)\n",
    "    - Label\n",
    "        - Edible (`1` indicating yes or `0` indicating poisonous)\n",
    "\n",
    "<a name=\"3.1\"></a>\n",
    "### 3.1 One hot encoded dataset\n",
    "For ease of implementation, we have one-hot encoded the features (turned them into 0 or 1 valued features)\n",
    "\n",
    "| Brown Cap | Tapering Stalk Shape | Solitary | Edible |\n",
    "|:---------:|:--------------------:|:--------:|:------:|\n",
    "|     1     |           1          |     1    |    1   |\n",
    "|     1     |           0          |     1    |    1   |\n",
    "|     1     |           0          |     0    |    0   |\n",
    "|     1     |           0          |     0    |    0   |\n",
    "|     1     |           1          |     1    |    1   |\n",
    "|     0     |           1          |     1    |    0   |\n",
    "|     0     |           0          |     0    |    0   |\n",
    "|     1     |           0          |     1    |    1   |\n",
    "|     0     |           1          |     0    |    1   |\n",
    "|     1     |           0          |     0    |    0   |\n",
    "\n",
    "Therefore,\n",
    "- `X_train` contains three features for each example \n",
    "    - Brown Color (A value of `1` indicates \"Brown\" cap color and `0` indicates \"Red\" cap color)\n",
    "    - Tapering Shape (A value of `1` indicates \"Tapering Stalk Shape\" and `0` indicates \"Enlarging\" stalk shape)\n",
    "    - Solitary  (A value of `1` indicates \"Yes\" and `0` indicates \"No\")\n",
    "\n",
    "- `y_train` is whether the mushroom is edible \n",
    "    - `y = 1` indicates edible\n",
    "    - `y = 0` indicates poisonous"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "X_train = np.array([[1,1,1],[1,0,1],[1,0,0],[1,0,0],[1,1,1],[0,1,1],[0,0,0],[1,0,1],[0,1,0],[1,0,0]])\n",
    "y_train = np.array([1,1,0,0,1,0,0,1,1,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### View the variables\n",
    "Let's get more familiar with your dataset.  \n",
    "- A good place to start is to just print out each variable and see what it contains.\n",
    "\n",
    "The code below prints the first few elements of `X_train` and the type of the variable."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First few elements of X_train:\n",
      " [[1 1 1]\n",
      " [1 0 1]\n",
      " [1 0 0]\n",
      " [1 0 0]\n",
      " [1 1 1]]\n",
      "Type of X_train: <class 'numpy.ndarray'>\n"
     ]
    }
   ],
   "source": [
    "print(\"First few elements of X_train:\\n\", X_train[:5])\n",
    "print(\"Type of X_train:\",type(X_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's do the same for `y_train`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First few elements of y_train: [1 1 0 0 1]\n",
      "Type of y_train: <class 'numpy.ndarray'>\n"
     ]
    }
   ],
   "source": [
    "print(\"First few elements of y_train:\", y_train[:5])\n",
    "print(\"Type of y_train:\",type(y_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Check the dimensions of your variables\n",
    "\n",
    "Another useful way to get familiar with your data is to view its dimensions.\n",
    "\n",
    "Please print the shape of `X_train` and `y_train` and see how many training examples you have in your dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The shape of X_train is: (10, 3)\n",
      "The shape of y_train is:  (10,)\n",
      "Number of training examples (m): 10\n"
     ]
    }
   ],
   "source": [
    "print ('The shape of X_train is:', X_train.shape)\n",
    "print ('The shape of y_train is: ', y_train.shape)\n",
    "print ('Number of training examples (m):', len(X_train))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4\"></a>\n",
    "## 4 - Decision Tree Refresher\n",
    "\n",
    "In this practice lab, you will build a decision tree based on the dataset provided.\n",
    "\n",
    "- Recall that the steps for building a decision tree are as follows:\n",
    "    - Start with all examples at the root node\n",
    "    - Calculate information gain for splitting on all possible features, and pick the one with the highest information gain\n",
    "    - Split dataset according to the selected feature, and create left and right branches of the tree\n",
    "    - Keep repeating splitting process until stopping criteria is met\n",
    "  \n",
    "  \n",
    "- In this lab, you'll implement the following functions, which will let you split a node into left and right branches using the feature with the highest information gain\n",
    "    - Calculate the entropy at a node \n",
    "    - Split the dataset at a node into left and right branches based on a given feature\n",
    "    - Calculate the information gain from splitting on a given feature\n",
    "    - Choose the feature that maximizes information gain\n",
    "    \n",
    "- We'll then use the helper functions you've implemented to build a decision tree by repeating the splitting process until the stopping criteria is met \n",
    "    - For this lab, the stopping criteria we've chosen is setting a maximum depth of 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4.1\"></a>\n",
    "### 4.1  Calculate entropy\n",
    "\n",
    "First, you'll write a helper function called `compute_entropy` that computes the entropy (measure of impurity) at a node. \n",
    "- The function takes in a numpy array (`y`) that indicates whether the examples in that node are edible (`1`) or poisonous(`0`) \n",
    "\n",
    "Complete the `compute_entropy()` function below to:\n",
    "* Compute $p_1$, which is the fraction of examples that are edible (i.e. have value = `1` in `y`)\n",
    "* The entropy is then calculated as \n",
    "\n",
    "$$H(p_1) = -p_1 \\text{log}_2(p_1) - (1- p_1) \\text{log}_2(1- p_1)$$\n",
    "* Note \n",
    "    * The log is calculated with base $2$\n",
    "    * For implementation purposes, $0\\text{log}_2(0) = 0$. That is, if `p_1 = 0` or `p_1 = 1`, set the entropy to `0`\n",
    "    * Make sure to check that the data at a node is not empty (i.e. `len(y) != 0`). Return `0` if it is\n",
    "    \n",
    "<a name=\"ex01\"></a>\n",
    "### Exercise 1\n",
    "\n",
    "Please complete the `compute_entropy()` function using the previous instructions.\n",
    "    \n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C1\n",
    "# GRADED FUNCTION: compute_entropy\n",
    "import math\n",
    "\n",
    "def compute_entropy(y):\n",
    "    \"\"\"\n",
    "    Computes the entropy for \n",
    "    \n",
    "    Args:\n",
    "       y (ndarray): Numpy array indicating whether each example at a node is\n",
    "           edible (`1`) or poisonous (`0`)\n",
    "       \n",
    "    Returns:\n",
    "        entropy (float): Entropy at that node\n",
    "        \n",
    "    \"\"\"\n",
    "    # You need to return the following variables correctly\n",
    "    entropy = 0.\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    m = len(y)\n",
    "    p_1 = 0\n",
    "    p_0 = 0\n",
    "    for i in range(m):\n",
    "        if y[i]==1:\n",
    "            p_1+=1\n",
    "    if m!=0:\n",
    "        p_1 = p_1 / m\n",
    "        p_0 = 1.0 - p_1\n",
    "    \n",
    "    if p_1!=1.0 and p_1!=0.0:\n",
    "        entropy = -p_1 * math.log2(p_1) - p_0 * math.log2(p_0)\n",
    "    ### END CODE HERE ###        \n",
    "    \n",
    "    return entropy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "    \n",
    "    \n",
    "   * To calculate `p1`\n",
    "       * You can get the subset of examples in `y` that have the value `1` as `y[y == 1]`\n",
    "       * You can use `len(y)` to get the number of examples in `y`\n",
    "   * To calculate `entropy`\n",
    "       * <a href=\"https://numpy.org/doc/stable/reference/generated/numpy.log2.html\">np.log2</a> let's you calculate the logarithm to base 2 for a numpy array\n",
    "       * If the value of `p1` is 0 or 1, make sure to set the entropy to `0` \n",
    "     \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b> Click for more hints</b></font></summary>\n",
    "        \n",
    "    * Here's how you can structure the overall implementation for this function\n",
    "    ```python \n",
    "    def compute_entropy(y):\n",
    "        \n",
    "        # You need to return the following variables correctly\n",
    "        entropy = 0.\n",
    "\n",
    "        ### START CODE HERE ###\n",
    "        if len(y) != 0:\n",
    "            # Your code here to calculate the fraction of edible examples (i.e with value = 1 in y)\n",
    "            p1 =\n",
    "\n",
    "            # For p1 = 0 and 1, set the entropy to 0 (to handle 0log0)\n",
    "            if p1 != 0 and p1 != 1:\n",
    "                # Your code here to calculate the entropy using the formula provided above\n",
    "                entropy = \n",
    "            else:\n",
    "                entropy = 0. \n",
    "        ### END CODE HERE ###        \n",
    "\n",
    "        return entropy\n",
    "    ```\n",
    "    \n",
    "    If you're still stuck, you can check the hints presented below to figure out how to calculate `p1` and `entropy`.\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate p1</b></font></summary>\n",
    "           &emsp; &emsp; You can compute p1 as <code>p1 = len(y[y == 1]) / len(y) </code>\n",
    "    </details>\n",
    "\n",
    "     <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate entropy</b></font></summary>\n",
    "          &emsp; &emsp; You can compute entropy as <code>entropy = -p1 * np.log2(p1) - (1 - p1) * np.log2(1 - p1)</code>\n",
    "    </details>\n",
    "        \n",
    "    </details>\n",
    "\n",
    "</details>\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can check if your implementation was correct by running the following test code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Entropy at root node:  1.0\n",
      "\u001b[92m All tests passed.\n"
     ]
    }
   ],
   "source": [
    "# Compute entropy at the root node (i.e. with all examples)\n",
    "# Since we have 5 edible and 5 non-edible mushrooms, the entropy should be 1\"\n",
    "\n",
    "print(\"Entropy at root node: \", compute_entropy(y_train)) \n",
    "\n",
    "# UNIT TESTS\n",
    "compute_entropy_test(compute_entropy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "<table>\n",
    "  <tr>\n",
    "    <td> <b>Entropy at root node:<b> 1.0 </td> \n",
    "  </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4.2\"></a>\n",
    "### 4.2  Split dataset\n",
    "\n",
    "Next, you'll write a helper function called `split_dataset` that takes in the data at a node and a feature to split on and splits it into left and right branches. Later in the lab, you'll implement code to calculate how good the split is.\n",
    "\n",
    "- The function takes in the training data, the list of indices of data points at that node, along with the feature to split on. \n",
    "- It splits the data and returns the subset of indices at the left and the right branch.\n",
    "- For example, say we're starting at the root node (so `node_indices = [0,1,2,3,4,5,6,7,8,9]`), and we chose to split on feature `0`, which is whether or not the example has a brown cap.\n",
    "    - The output of the function is then, `left_indices = [0,1,2,3,4,7,9]` and `right_indices = [5,6,8]`\n",
    "    \n",
    "| Index | Brown Cap | Tapering Stalk Shape | Solitary | Edible |\n",
    "|:-----:|:---------:|:--------------------:|:--------:|:------:|\n",
    "|   0   |     1     |           1          |     1    |    1   |\n",
    "|   1   |     1     |           0          |     1    |    1   |\n",
    "|   2   |     1     |           0          |     0    |    0   |\n",
    "|   3   |     1     |           0          |     0    |    0   |\n",
    "|   4   |     1     |           1          |     1    |    1   |\n",
    "|   5   |     0     |           1          |     1    |    0   |\n",
    "|   6   |     0     |           0          |     0    |    0   |\n",
    "|   7   |     1     |           0          |     1    |    1   |\n",
    "|   8   |     0     |           1          |     0    |    1   |\n",
    "|   9   |     1     |           0          |     0    |    0   |\n",
    "\n",
    "<a name=\"ex02\"></a>\n",
    "### Exercise 2\n",
    "\n",
    "Please complete the `split_dataset()` function shown below\n",
    "\n",
    "- For each index in `node_indices`\n",
    "    - If the value of `X` at that index for that feature is `1`, add the index to `left_indices`\n",
    "    - If the value of `X` at that index for that feature is `0`, add the index to `right_indices`\n",
    "\n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C2\n",
    "# GRADED FUNCTION: split_dataset\n",
    "\n",
    "def split_dataset(X, node_indices, feature):\n",
    "    \"\"\"\n",
    "    Splits the data at the given node into\n",
    "    left and right branches\n",
    "    \n",
    "    Args:\n",
    "        X (ndarray):             Data matrix of shape(n_samples, n_features)\n",
    "        node_indices (list):  List containing the active indices. I.e, the samples being considered at this step.\n",
    "        feature (int):           Index of feature to split on\n",
    "    \n",
    "    Returns:\n",
    "        left_indices (list): Indices with feature value == 1\n",
    "        right_indices (list): Indices with feature value == 0\n",
    "    \"\"\"\n",
    "    \n",
    "    # You need to return the following variables correctly\n",
    "    left_indices = []\n",
    "    right_indices = []\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    for i in node_indices:\n",
    "        if X[i][feature] == 1:\n",
    "            left_indices.append(i)\n",
    "        else:\n",
    "            right_indices.append(i)\n",
    "    ### END CODE HERE ###\n",
    "        \n",
    "    return left_indices, right_indices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "    \n",
    "    \n",
    "   * Here's how you can structure the overall implementation for this function\n",
    "    ```python \n",
    "    def split_dataset(X, node_indices, feature):\n",
    "    \n",
    "        # You need to return the following variables correctly\n",
    "        left_indices = []\n",
    "        right_indices = []\n",
    "\n",
    "        ### START CODE HERE ###\n",
    "        # Go through the indices of examples at that node\n",
    "        for i in node_indices:   \n",
    "            if # Your code here to check if the value of X at that index for the feature is 1\n",
    "                left_indices.append(i)\n",
    "            else:\n",
    "                right_indices.append(i)\n",
    "        ### END CODE HERE ###\n",
    "        \n",
    "    return left_indices, right_indices\n",
    "    ```\n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b> Click for more hints</b></font></summary>\n",
    "        \n",
    "    The condition is <code> if X[i][feature] == 1:</code>.\n",
    "        \n",
    "    </details>\n",
    "\n",
    "</details>\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's check your implementation using the code blocks below. Let's try splitting the dataset at the root node, which contains all examples at feature 0 (Brown Cap) as we'd discussed above"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Left indices:  [0, 1, 2, 3, 4, 7, 9]\n",
      "Right indices:  [5, 6, 8]\n",
      "\u001b[92m All tests passed.\n"
     ]
    }
   ],
   "source": [
    "root_indices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "\n",
    "# Feel free to play around with these variables\n",
    "# The dataset only has three features, so this value can be 0 (Brown Cap), 1 (Tapering Stalk Shape) or 2 (Solitary)\n",
    "feature = 0\n",
    "\n",
    "left_indices, right_indices = split_dataset(X_train, root_indices, feature)\n",
    "\n",
    "print(\"Left indices: \", left_indices)\n",
    "print(\"Right indices: \", right_indices)\n",
    "\n",
    "# UNIT TESTS    \n",
    "split_dataset_test(split_dataset)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "```\n",
    "Left indices:  [0, 1, 2, 3, 4, 7, 9]\n",
    "Right indices:  [5, 6, 8]\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4.3\"></a>\n",
    "### 4.3  Calculate information gain\n",
    "\n",
    "Next, you'll write a function called `information_gain` that takes in the training data, the indices at a node and a feature to split on and returns the information gain from the split.\n",
    "\n",
    "<a name=\"ex03\"></a>\n",
    "### Exercise 3\n",
    "\n",
    "Please complete the `compute_information_gain()` function shown below to compute\n",
    "\n",
    "$$\\text{Information Gain} = H(p_1^\\text{node})- (w^{\\text{left}}H(p_1^\\text{left}) + w^{\\text{right}}H(p_1^\\text{right}))$$\n",
    "\n",
    "where \n",
    "- $H(p_1^\\text{node})$ is entropy at the node \n",
    "- $H(p_1^\\text{left})$ and $H(p_1^\\text{right})$ are the entropies at the left and the right branches resulting from the split\n",
    "- $w^{\\text{left}}$ and $w^{\\text{right}}$ are the proportion of examples at the left and right branch, respectively\n",
    "\n",
    "Note:\n",
    "- You can use the `compute_entropy()` function that you implemented above to calculate the entropy\n",
    "- We've provided some starter code that uses the `split_dataset()` function you implemented above to split the dataset \n",
    "\n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C3\n",
    "# GRADED FUNCTION: compute_information_gain\n",
    "\n",
    "def compute_information_gain(X, y, node_indices, feature):\n",
    "    \n",
    "    \"\"\"\n",
    "    Compute the information of splitting the node on a given feature\n",
    "    \n",
    "    Args:\n",
    "        X (ndarray):            Data matrix of shape(n_samples, n_features)\n",
    "        y (array like):         list or ndarray with n_samples containing the target variable\n",
    "        node_indices (ndarray): List containing the active indices. I.e, the samples being considered in this step.\n",
    "   \n",
    "    Returns:\n",
    "        cost (float):        Cost computed\n",
    "    \n",
    "    \"\"\"    \n",
    "    # Split dataset\n",
    "    left_indices, right_indices = split_dataset(X, node_indices, feature)\n",
    "    \n",
    "    # Some useful variables\n",
    "    X_node, y_node = X[node_indices], y[node_indices]\n",
    "    X_left, y_left = X[left_indices], y[left_indices]\n",
    "    X_right, y_right = X[right_indices], y[right_indices]\n",
    "    \n",
    "    # You need to return the following variables correctly\n",
    "    information_gain = 0\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    root_entropy = compute_entropy(y_node)\n",
    "    left_entropy = compute_entropy(y_left)\n",
    "    right_entropy = compute_entropy(y_right)\n",
    "    # Weights \n",
    "    w_left = len(X_left) / len(X_node)\n",
    "    w_right = len(X_right) / len(X_node)\n",
    "    #Weighted entropy\n",
    "    weighted_entropy = w_left * left_entropy + w_right * right_entropy\n",
    "    #Information gain                                                   \n",
    "    information_gain = root_entropy - weighted_entropy\n",
    "    ### END CODE HERE ###  \n",
    "    \n",
    "    return information_gain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "    \n",
    "    \n",
    "   * Here's how you can structure the overall implementation for this function\n",
    "    ```python \n",
    "    def compute_information_gain(X, y, node_indices, feature):\n",
    "        # Split dataset\n",
    "        left_indices, right_indices = split_dataset(X, node_indices, feature)\n",
    "\n",
    "        # Some useful variables\n",
    "        X_node, y_node = X[node_indices], y[node_indices]\n",
    "        X_left, y_left = X[left_indices], y[left_indices]\n",
    "        X_right, y_right = X[right_indices], y[right_indices]\n",
    "\n",
    "        # You need to return the following variables correctly\n",
    "        information_gain = 0\n",
    "\n",
    "        ### START CODE HERE ###\n",
    "        # Your code here to compute the entropy at the node using compute_entropy()\n",
    "        node_entropy = \n",
    "        # Your code here to compute the entropy at the left branch\n",
    "        left_entropy = \n",
    "        # Your code here to compute the entropy at the right branch\n",
    "        right_entropy = \n",
    "\n",
    "        # Your code here to compute the proportion of examples at the left branch\n",
    "        w_left = \n",
    "        \n",
    "        # Your code here to compute the proportion of examples at the right branch\n",
    "        w_right = \n",
    "\n",
    "        # Your code here to compute weighted entropy from the split using \n",
    "        # w_left, w_right, left_entropy and right_entropy\n",
    "        weighted_entropy = \n",
    "\n",
    "        # Your code here to compute the information gain as the entropy at the node\n",
    "        # minus the weighted entropy\n",
    "        information_gain = \n",
    "        ### END CODE HERE ###  \n",
    "\n",
    "        return information_gain\n",
    "    ```\n",
    "    If you're still stuck, check out the hints below.\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b> Hint to calculate the entropies</b></font></summary>\n",
    "        \n",
    "    <code>node_entropy = compute_entropy(y_node)</code><br>\n",
    "    <code>left_entropy = compute_entropy(y_left)</code><br>\n",
    "    <code>right_entropy = compute_entropy(y_right)</code>\n",
    "        \n",
    "    </details>\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate w_left and w_right</b></font></summary>\n",
    "           <code>w_left = len(X_left) / len(X_node)</code><br>\n",
    "           <code>w_right = len(X_right) / len(X_node)</code>\n",
    "    </details>\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate weighted_entropy</b></font></summary>\n",
    "           <code>weighted_entropy = w_left * left_entropy + w_right * right_entropy</code>\n",
    "    </details>\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to calculate information_gain</b></font></summary>\n",
    "           <code> information_gain = node_entropy - weighted_entropy</code>\n",
    "    </details>\n",
    "\n",
    "\n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can now check your implementation using the cell below and calculate what the information gain would be from splitting on each of the featues"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Information Gain from splitting the root on brown cap:  0.034851554559677034\n",
      "Information Gain from splitting the root on tapering stalk shape:  0.12451124978365313\n",
      "Information Gain from splitting the root on solitary:  0.2780719051126377\n",
      "\u001b[92m All tests passed.\n"
     ]
    }
   ],
   "source": [
    "info_gain0 = compute_information_gain(X_train, y_train, root_indices, feature=0)\n",
    "print(\"Information Gain from splitting the root on brown cap: \", info_gain0)\n",
    "    \n",
    "info_gain1 = compute_information_gain(X_train, y_train, root_indices, feature=1)\n",
    "print(\"Information Gain from splitting the root on tapering stalk shape: \", info_gain1)\n",
    "\n",
    "info_gain2 = compute_information_gain(X_train, y_train, root_indices, feature=2)\n",
    "print(\"Information Gain from splitting the root on solitary: \", info_gain2)\n",
    "\n",
    "# UNIT TESTS\n",
    "compute_information_gain_test(compute_information_gain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Expected Output**:\n",
    "```\n",
    "Information Gain from splitting the root on brown cap:  0.034851554559677034\n",
    "Information Gain from splitting the root on tapering stalk shape:  0.12451124978365313\n",
    "Information Gain from splitting the root on solitary:  0.2780719051126377\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Splitting on \"Solitary\" (feature = 2) at the root node gives the maximum information gain. Therefore, it's the best feature to split on at the root node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"4.4\"></a>\n",
    "### 4.4  Get best split\n",
    "Now let's write a function to get the best feature to split on by computing the information gain from each feature as we did above and returning the feature that gives the maximum information gain\n",
    "\n",
    "<a name=\"ex04\"></a>\n",
    "### Exercise 4\n",
    "Please complete the `get_best_split()` function shown below.\n",
    "- The function takes in the training data, along with the indices of datapoint at that node\n",
    "- The output of the function is the feature that gives the maximum information gain \n",
    "    - You can use the `compute_information_gain()` function to iterate through the features and calculate the information for each feature\n",
    "If you get stuck, you can check out the hints presented after the cell below to help you with the implementation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "# UNQ_C4\n",
    "# GRADED FUNCTION: get_best_split\n",
    "\n",
    "def get_best_split(X, y, node_indices):   \n",
    "    \"\"\"\n",
    "    Returns the optimal feature and threshold value\n",
    "    to split the node data \n",
    "    \n",
    "    Args:\n",
    "        X (ndarray):            Data matrix of shape(n_samples, n_features)\n",
    "        y (array like):         list or ndarray with n_samples containing the target variable\n",
    "        node_indices (ndarray): List containing the active indices. I.e, the samples being considered in this step.\n",
    "\n",
    "    Returns:\n",
    "        best_feature (int):     The index of the best feature to split\n",
    "    \"\"\"    \n",
    "    \n",
    "    # Some useful variables\n",
    "    num_features = X.shape[1]\n",
    "    \n",
    "    # You need to return the following variables correctly\n",
    "    best_feature = -1\n",
    "    \n",
    "    ### START CODE HERE ###\n",
    "    max_ = 0\n",
    "    for i in range(num_features):\n",
    "        information_gain = compute_information_gain(X,y,node_indices,i)\n",
    "        if information_gain > max_:\n",
    "            max_ = information_gain\n",
    "            best_feature = i\n",
    "    ### END CODE HERE ##    \n",
    "   \n",
    "    return best_feature"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary><font size=\"3\" color=\"darkgreen\"><b>Click for hints</b></font></summary>\n",
    "    \n",
    "    \n",
    "   * Here's how you can structure the overall implementation for this function\n",
    "    \n",
    "    ```python \n",
    "    def get_best_split(X, y, node_indices):   \n",
    "\n",
    "        # Some useful variables\n",
    "        num_features = X.shape[1]\n",
    "\n",
    "        # You need to return the following variables correctly\n",
    "        best_feature = -1\n",
    "\n",
    "        ### START CODE HERE ###\n",
    "        max_info_gain = 0\n",
    "\n",
    "        # Iterate through all features\n",
    "        for feature in range(num_features): \n",
    "            \n",
    "            # Your code here to compute the information gain from splitting on this feature\n",
    "            info_gain = \n",
    "            \n",
    "            # If the information gain is larger than the max seen so far\n",
    "            if info_gain > max_info_gain:  \n",
    "                # Your code here to set the max_info_gain and best_feature\n",
    "                max_info_gain = \n",
    "                best_feature = \n",
    "        ### END CODE HERE ##    \n",
    "   \n",
    "    return best_feature\n",
    "    ```\n",
    "    If you're still stuck, check out the hints below.\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b> Hint to calculate info_gain</b></font></summary>\n",
    "        \n",
    "    <code>info_gain = compute_information_gain(X, y, node_indices, feature)</code>\n",
    "    </details>\n",
    "    \n",
    "    <details>\n",
    "          <summary><font size=\"2\" color=\"darkblue\"><b>Hint to update the max_info_gain and best_feature</b></font></summary>\n",
    "           <code>max_info_gain = info_gain</code><br>\n",
    "           <code>best_feature = feature</code>\n",
    "    </details>\n",
    "</details>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's check the implementation of your function using the cell below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Best feature to split on: 2\n",
      "\u001b[92m All tests passed.\n"
     ]
    }
   ],
   "source": [
    "best_feature = get_best_split(X_train, y_train, root_indices)\n",
    "print(\"Best feature to split on: %d\" % best_feature)\n",
    "\n",
    "# UNIT TESTS\n",
    "get_best_split_test(get_best_split)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we saw above, the function returns that the best feature to split on at the root node is feature 2 (\"Solitary\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a name=\"5\"></a>\n",
    "## 5 - Building the tree\n",
    "\n",
    "In this section, we use the functions you implemented above to generate a decision tree by successively picking the best feature to split on until we reach the stopping criteria (maximum depth is 2).\n",
    "\n",
    "You do not need to implement anything for this part."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Not graded\n",
    "tree = []\n",
    "\n",
    "def build_tree_recursive(X, y, node_indices, branch_name, max_depth, current_depth):\n",
    "    \"\"\"\n",
    "    Build a tree using the recursive algorithm that split the dataset into 2 subgroups at each node.\n",
    "    This function just prints the tree.\n",
    "    \n",
    "    Args:\n",
    "        X (ndarray):            Data matrix of shape(n_samples, n_features)\n",
    "        y (array like):         list or ndarray with n_samples containing the target variable\n",
    "        node_indices (ndarray): List containing the active indices. I.e, the samples being considered in this step.\n",
    "        branch_name (string):   Name of the branch. ['Root', 'Left', 'Right']\n",
    "        max_depth (int):        Max depth of the resulting tree. \n",
    "        current_depth (int):    Current depth. Parameter used during recursive call.\n",
    "   \n",
    "    \"\"\" \n",
    "\n",
    "    # Maximum depth reached - stop splitting\n",
    "    if current_depth == max_depth:\n",
    "        formatting = \" \"*current_depth + \"-\"*current_depth\n",
    "        print(formatting, \"%s leaf node with indices\" % branch_name, node_indices)\n",
    "        return\n",
    "   \n",
    "    # Otherwise, get best split and split the data\n",
    "    # Get the best feature and threshold at this node\n",
    "    best_feature = get_best_split(X, y, node_indices) \n",
    "    tree.append((current_depth, branch_name, best_feature, node_indices))\n",
    "    \n",
    "    formatting = \"-\"*current_depth\n",
    "    print(\"%s Depth %d, %s: Split on feature: %d\" % (formatting, current_depth, branch_name, best_feature))\n",
    "    \n",
    "    # Split the dataset at the best feature\n",
    "    left_indices, right_indices = split_dataset(X, node_indices, best_feature)\n",
    "    \n",
    "    # continue splitting the left and the right child. Increment current depth\n",
    "    build_tree_recursive(X, y, left_indices, \"Left\", max_depth, current_depth+1)\n",
    "    build_tree_recursive(X, y, right_indices, \"Right\", max_depth, current_depth+1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Depth 0, Root: Split on feature: 2\n",
      "- Depth 1, Left: Split on feature: 0\n",
      "  -- Left leaf node with indices [0, 1, 4, 7]\n",
      "  -- Right leaf node with indices [5]\n",
      "- Depth 1, Right: Split on feature: 1\n",
      "  -- Left leaf node with indices [8]\n",
      "  -- Right leaf node with indices [2, 3, 6, 9]\n"
     ]
    }
   ],
   "source": [
    "build_tree_recursive(X_train, y_train, root_indices, \"Root\", max_depth=2, current_depth=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}