implementing-binary-decision-trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementing binary decision trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The goal of this notebook is to implement binary decision tree classifier. We will:\n",
    "    \n",
    "* Use SFrames to do some feature engineering.\n",
    "* Transform categorical variables into binary variables.\n",
    "* Write a function to compute the number of misclassified examples in an intermediate node.\n",
    "* Write a function to find the best feature to split on.\n",
    "* Build a binary decision tree from scratch.\n",
    "* Make predictions using the decision tree.\n",
    "* Evaluate the accuracy of the decision tree.\n",
    "* Visualize the decision at the root node.\n",
    "\n",
    "**Important Note**: We will focus on building decision trees where the data contain **only binary (0 or 1) features**. This allows us to avoid dealing with:\n",
    "* Multiple intermediate nodes in a split\n",
    "* The thresholding issues of real-valued features."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fire up GraphLab Create"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "import graphlab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Load the lending club dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This non-commercial license of GraphLab Create for academic use is assigned to nanlee_89@yahoo.com and will expire on December 07, 2018.\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[INFO] graphlab.cython.cy_server: GraphLab Create v2.1 started. Logging: /tmp/graphlab_server_1530202671.log\n"
     ]
    }
   ],
   "source": [
    "loans = graphlab.SFrame('lending-club-data.gl/')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We reassign the labels to have +1 for a safe loan, and -1 for a risky (bad) loan."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "loans['safe_loans'] = loans['bad_loans'].apply(lambda x : +1 if x==0 else -1)\n",
    "loans = loans.remove_column('bad_loans')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook, we will just be using 4 categorical features: \n",
    "\n",
    "1. grade of the loan \n",
    "2. the length of the loan term\n",
    "3. the home ownership status: own, mortgage, rent\n",
    "4. number of years of employment.\n",
    "\n",
    "Since we are building a binary decision tree, we will have to convert these categorical features to a binary representation in a subsequent section using 1-hot encoding."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "features = ['grade',              # grade of the loan\n",
    "            'term',               # the term of the loan\n",
    "            'home_ownership',     # home_ownership status: own, mortgage or rent\n",
    "            'emp_length',         # number of years of employment\n",
    "           ]\n",
    "target = 'safe_loans'\n",
    "loans = loans[features + [target]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Explore what the dataset looks like."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\"><table frame=\"box\" rules=\"cols\">\n",
       "    <tr>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">grade</th>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">term</th>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">home_ownership</th>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">emp_length</th>\n",
       "        <th style=\"padding-left: 1em; padding-right: 1em; text-align: center\">safe_loans</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">B</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 36 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">RENT</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">10+ years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">C</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 60 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">RENT</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">&lt; 1 year</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">C</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 36 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">RENT</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">10+ years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">C</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 36 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">RENT</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">10+ years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">A</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 36 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">RENT</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">3 years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">E</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 36 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">RENT</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">9 years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">F</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 60 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">OWN</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">4 years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">B</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 60 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">RENT</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">&lt; 1 year</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">-1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">C</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 60 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">OWN</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">5 years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">B</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\"> 36 months</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">OWN</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">10+ years</td>\n",
       "        <td style=\"padding-left: 1em; padding-right: 1em; text-align: center; vertical-align: top\">1</td>\n",
       "    </tr>\n",
       "</table>\n",
       "[122607 rows x 5 columns]<br/>Note: Only the head of the SFrame is printed.<br/>You can use print_rows(num_rows=m, num_columns=n) to print more rows and columns.\n",
       "</div>"
      ],
      "text/plain": [
       "Columns:\n",
       "\tgrade\tstr\n",
       "\tterm\tstr\n",
       "\thome_ownership\tstr\n",
       "\temp_length\tstr\n",
       "\tsafe_loans\tint\n",
       "\n",
       "Rows: 122607\n",
       "\n",
       "Data:\n",
       "+-------+------------+----------------+------------+------------+\n",
       "| grade |    term    | home_ownership | emp_length | safe_loans |\n",
       "+-------+------------+----------------+------------+------------+\n",
       "|   B   |  36 months |      RENT      | 10+ years  |     1      |\n",
       "|   C   |  60 months |      RENT      |  < 1 year  |     -1     |\n",
       "|   C   |  36 months |      RENT      | 10+ years  |     1      |\n",
       "|   C   |  36 months |      RENT      | 10+ years  |     1      |\n",
       "|   A   |  36 months |      RENT      |  3 years   |     1      |\n",
       "|   E   |  36 months |      RENT      |  9 years   |     1      |\n",
       "|   F   |  60 months |      OWN       |  4 years   |     -1     |\n",
       "|   B   |  60 months |      RENT      |  < 1 year  |     -1     |\n",
       "|   C   |  60 months |      OWN       |  5 years   |     1      |\n",
       "|   B   |  36 months |      OWN       | 10+ years  |     1      |\n",
       "+-------+------------+----------------+------------+------------+\n",
       "[122607 rows x 5 columns]\n",
       "Note: Only the head of the SFrame is printed.\n",
       "You can use print_rows(num_rows=m, num_columns=n) to print more rows and columns."
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "loans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Subsample dataset to make sure classes are balanced"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to balance out our dataset, we will undersample the larger class (safe loans) . This means we are throwing away many data points. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Percentage of safe loans                 : 0.502236174422\n",
      "Percentage of risky loans                : 0.497763825578\n",
      "Total number of loans in our new dataset : 46508\n"
     ]
    }
   ],
   "source": [
    "safe_loans_raw = loans[loans[target] == 1]\n",
    "risky_loans_raw = loans[loans[target] == -1]\n",
    "\n",
    "# Since there are less risky loans than safe loans, find the ratio of the sizes\n",
    "# and use that percentage to undersample the safe loans.\n",
    "percentage = len(risky_loans_raw)/float(len(safe_loans_raw))\n",
    "safe_loans = safe_loans_raw.sample(percentage, seed = 1)\n",
    "risky_loans = risky_loans_raw\n",
    "loans_data = risky_loans.append(safe_loans)\n",
    "\n",
    "print \"Percentage of safe loans                 :\", len(safe_loans) / float(len(loans_data))\n",
    "print \"Percentage of risky loans                :\", len(risky_loans) / float(len(loans_data))\n",
    "print \"Total number of loans in our new dataset :\", len(loans_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Transform categorical data into binary features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook, we will implement **binary decision trees** (decision trees for binary features, a specific case of categorical variables taking on two values, e.g., true/false). Since all of our features are currently categorical features, we want to turn them into binary features. \n",
    "\n",
    "For instance, the **home_ownership** feature represents the home ownership status of the loanee, which is either `own`, `mortgage` or `rent`. For example, if a data point has the feature \n",
    "```\n",
    "   {'home_ownership': 'RENT'}\n",
    "```\n",
    "we want to turn this into three features: \n",
    "```\n",
    " { \n",
    "   'home_ownership = OWN'      : 0, \n",
    "   'home_ownership = MORTGAGE' : 0, \n",
    "   'home_ownership = RENT'     : 1\n",
    " }\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "loans_data = risky_loans.append(safe_loans)\n",
    "for feature in features:\n",
    "    loans_data_one_hot_encoded = loans_data[feature].apply(lambda x: {x: 1})    \n",
    "    loans_data_unpacked = loans_data_one_hot_encoded.unpack(column_name_prefix=feature)\n",
    "    \n",
    "    # Change None's to 0's\n",
    "    for column in loans_data_unpacked.column_names():\n",
    "        loans_data_unpacked[column] = loans_data_unpacked[column].fillna(0)\n",
    "\n",
    "    loans_data.remove_column(feature)\n",
    "    loans_data.add_columns(loans_data_unpacked)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check what the feature columns look like now:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['grade.A',\n",
       " 'grade.B',\n",
       " 'grade.C',\n",
       " 'grade.D',\n",
       " 'grade.E',\n",
       " 'grade.F',\n",
       " 'grade.G',\n",
       " 'term. 36 months',\n",
       " 'term. 60 months',\n",
       " 'home_ownership.MORTGAGE',\n",
       " 'home_ownership.OTHER',\n",
       " 'home_ownership.OWN',\n",
       " 'home_ownership.RENT',\n",
       " 'emp_length.1 year',\n",
       " 'emp_length.10+ years',\n",
       " 'emp_length.2 years',\n",
       " 'emp_length.3 years',\n",
       " 'emp_length.4 years',\n",
       " 'emp_length.5 years',\n",
       " 'emp_length.6 years',\n",
       " 'emp_length.7 years',\n",
       " 'emp_length.8 years',\n",
       " 'emp_length.9 years',\n",
       " 'emp_length.< 1 year',\n",
       " 'emp_length.n/a']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "features = loans_data.column_names()\n",
    "features.remove('safe_loans')  # Remove the response variable\n",
    "features"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of features (after binarizing categorical variables) = 25\n"
     ]
    }
   ],
   "source": [
    "print \"Number of features (after binarizing categorical variables) = %s\" % len(features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's explore what one of these columns looks like:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dtype: int\n",
       "Rows: 46508\n",
       "[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, ... ]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "loans_data['grade.A']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Train-test split\n",
    "\n",
    "We split the data into a train test split with 80% of the data in the training set and 20% of the data in the test set. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "train_data, test_data = loans_data.random_split(.8, seed=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision tree implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Function to count number of mistakes while predicting majority class\n",
    "\n",
    "Prediction at an intermediate node works by predicting the **majority class** for all data points that belong to this node.\n",
    "\n",
    "Now, we will write a function that calculates the number of **misclassified examples** when predicting the **majority class**. This will be used to help determine which feature is the best to split on at a given node of the tree.\n",
    "\n",
    "**Note**: Keep in mind that in order to compute the number of mistakes for a majority classifier, we only need the label (y values) of the data points in the node. \n",
    "\n",
    "** Steps to follow **:\n",
    "* ** Step 1:** Calculate the number of safe loans and risky loans.\n",
    "* ** Step 2:** Since we are assuming majority class prediction, all the data points that are **not** in the majority class are considered **mistakes**.\n",
    "* ** Step 3:** Return the number of **mistakes**.\n",
    "\n",
    "\n",
    "The following function `intermediate_node_num_mistakes` computes the number of misclassified examples of an intermediate node given the set of labels (y values) of the data points contained in the node. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def intermediate_node_num_mistakes(labels_in_node):\n",
    "    # Corner case: If labels_in_node is empty, return 0\n",
    "    if len(labels_in_node) == 0:\n",
    "        return 0\n",
    "    \n",
    "    # Count the number of 1's (safe loans)\n",
    "    safe_loans = (labels_in_node == 1).sum()\n",
    "    \n",
    "    # Count the number of -1's (risky loans)\n",
    "    risky_loans = (labels_in_node == -1).sum()\n",
    "                \n",
    "    # Return the number of mistakes that the majority classifier makes.\n",
    "    if safe_loans > risky_loans:\n",
    "        return risky_loans\n",
    "    else:\n",
    "        return safe_loans\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Function to pick best feature to split on"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function **best_splitting_feature** takes 3 arguments: \n",
    "1. The data (SFrame of data which includes all of the feature columns and label column)\n",
    "2. The features to consider for splits (a list of strings of column names to consider for splits)\n",
    "3. The name of the target/label column (string)\n",
    "\n",
    "The function will loop through the list of possible features, and consider splitting on each of them. It will calculate the classification error of each split and return the feature that had the smallest classification error when split on.\n",
    "\n",
    "Recall that the **classification error** is defined as follows:\n",
    "$$\n",
    "\\mbox{classification error} = \\frac{\\mbox{# mistakes}}{\\mbox{# total examples}}\n",
    "$$\n",
    "\n",
    "Follow these steps: \n",
    "* **Step 1:** Loop over each feature in the feature list\n",
    "* **Step 2:** Within the loop, split the data into two groups: one group where all of the data has feature value 0 or False (we will call this the **left** split), and one group where all of the data has feature value 1 or True (we will call this the **right** split). Make sure the **left** split corresponds with 0 and the **right** split corresponds with 1 to ensure your implementation fits with our implementation of the tree building process.\n",
    "* **Step 3:** Calculate the number of misclassified examples in both groups of data and use the above formula to compute the **classification error**.\n",
    "* **Step 4:** If the computed error is smaller than the best error found so far, store this **feature and its error**.\n",
    "\n",
    "**Note:** Remember that since we are only dealing with binary features, we do not have to consider thresholds for real-valued features. This makes the implementation of this function much easier.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def best_splitting_feature(data, features, target):\n",
    "    \n",
    "    best_feature = None # Keep track of the best feature \n",
    "    best_error = 10     # Keep track of the best error so far \n",
    "    # Note: Since error is always <= 1, we should intialize it with something larger than 1.\n",
    "\n",
    "    # Convert to float to make sure error gets computed correctly.\n",
    "    num_data_points = float(len(data))  \n",
    "    \n",
    "    # Loop through each feature to consider splitting on that feature\n",
    "    for feature in features:\n",
    "        \n",
    "        # The left split will have all data points where the feature value is 0\n",
    "        left_split = data[data[feature] == 0]\n",
    "        \n",
    "        # The right split will have all data points where the feature value is 1\n",
    "        right_split =  data[data[feature]==1]\n",
    "            \n",
    "        # Calculate the number of misclassified examples in the left split.\n",
    "        # Remember that we implemented a function for this! (It was called intermediate_node_num_mistakes)\n",
    "        left_mistakes = intermediate_node_num_mistakes(left_split[target])\n",
    "\n",
    "        # Calculate the number of misclassified examples in the right split.\n",
    "        right_mistakes = intermediate_node_num_mistakes(right_split[target])\n",
    "            \n",
    "        # Compute the classification error of this split.\n",
    "        # Error = (# of mistakes (left) + # of mistakes (right)) / (# of data points)\n",
    "        error = (left_mistakes + right_mistakes) / num_data_points\n",
    "\n",
    "        # If this is the best error we have found so far, store the feature as best_feature and the error as best_error\n",
    "        if error < best_error:\n",
    "            best_error = error\n",
    "            best_feature = feature\n",
    "        \n",
    "    \n",
    "    return best_feature # Return the best feature we found"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building the tree\n",
    "\n",
    "Each node in the decision tree is represented as a dictionary which contains the following keys and possible values:\n",
    "\n",
    "    { \n",
    "       'is_leaf'            : True/False.\n",
    "       'prediction'         : Prediction at the leaf node.\n",
    "       'left'               : (dictionary corresponding to the left tree).\n",
    "       'right'              : (dictionary corresponding to the right tree).\n",
    "       'splitting_feature'  : The feature that this node splits on.\n",
    "    }\n",
    "\n",
    "First, we will write a function that creates a leaf node given a set of target values. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def create_leaf(target_values):\n",
    "    \n",
    "    # Create a leaf node\n",
    "    leaf = {'splitting_feature' : None,\n",
    "            'left' : None,\n",
    "            'right' : None,\n",
    "            'is_leaf':  True   }   \n",
    "    \n",
    "    # Count the number of data points that are +1 and -1 in this node.\n",
    "    num_ones = len(target_values[target_values == +1])\n",
    "    num_minus_ones = len(target_values[target_values == -1])\n",
    "    \n",
    "    # For the leaf node, set the prediction to be the majority class.\n",
    "    # Store the predicted class (1 or -1) in leaf['prediction']\n",
    "    if num_ones > num_minus_ones:\n",
    "        leaf['prediction'] =  +1        \n",
    "    else:\n",
    "        leaf['prediction'] = -1       \n",
    "        \n",
    "    # Return the leaf node        \n",
    "    return leaf "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Following function learns the decision tree recursively and implements 3 stopping conditions:\n",
    "1. **Stopping condition 1:** All data points in a node are from the same class.\n",
    "2. **Stopping condition 2:** No more features to split on.\n",
    "3. **Additional stopping condition:** In addition to the above two stopping conditions covered in lecture, in this assignment we will also consider a stopping condition based on the **max_depth** of the tree. By not letting the tree grow too deep, we will save computational effort in the learning process. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def decision_tree_create(data, features, target, current_depth = 0, max_depth = 10):\n",
    "    remaining_features = features[:] # Make a copy of the features.\n",
    "    \n",
    "    target_values = data[target]\n",
    "    print \"--------------------------------------------------------------------\"\n",
    "    print \"Subtree, depth = %s (%s data points).\" % (current_depth, len(target_values))\n",
    "    \n",
    "\n",
    "    # Stopping condition 1\n",
    "    # (Check if there are mistakes at current node.\n",
    "    # Recall you wrote a function intermediate_node_num_mistakes to compute this.)\n",
    "    if  intermediate_node_num_mistakes(target_values)== 0:  \n",
    "        print \"Stopping condition 1 reached.\"     \n",
    "        # If not mistakes at current node, make current node a leaf node\n",
    "        return create_leaf(target_values)\n",
    "    \n",
    "    # Stopping condition 2 (check if there are remaining features to consider splitting on)\n",
    "    if remaining_features == []:   \n",
    "        print \"Stopping condition 2 reached.\"    \n",
    "        # If there are no remaining features to consider, make current node a leaf node\n",
    "        return create_leaf(target_values)    \n",
    "    \n",
    "    # Additional stopping condition (limit tree depth)\n",
    "    if current_depth >= max_depth:  \n",
    "        print \"Reached maximum depth. Stopping for now.\"\n",
    "        # If the max tree depth has been reached, make current node a leaf node\n",
    "        return create_leaf(target_values)\n",
    "\n",
    "    # Find the best splitting feature (recall the function best_splitting_feature implemented above)\n",
    "    splitting_feature = best_splitting_feature(data, features, target)\n",
    "\n",
    "    \n",
    "    # Split on the best feature that we found. \n",
    "    left_split = data[data[splitting_feature] == 0]\n",
    "    right_split = data[data[splitting_feature]==1]      \n",
    "    remaining_features.remove(splitting_feature)\n",
    "    print \"Split on feature %s. (%s, %s)\" % (\\\n",
    "                      splitting_feature, len(left_split), len(right_split))\n",
    "    \n",
    "    # Create a leaf node if the split is \"perfect\"\n",
    "    if len(left_split) == len(data):\n",
    "        print \"Creating leaf node.\"\n",
    "        return create_leaf(left_split[target])\n",
    "    if len(right_split) == len(data):\n",
    "        print \"Creating leaf node.\"\n",
    "        return create_leaf(right_split[target])\n",
    "        \n",
    "    # Repeat (recurse) on left and right subtrees\n",
    "    left_tree = decision_tree_create(left_split, remaining_features, target, current_depth + 1, max_depth)        \n",
    "    right_tree = decision_tree_create(right_split, remaining_features, target, current_depth+1, max_depth)\n",
    "\n",
    "    return {'is_leaf'          : False, \n",
    "            'prediction'       : None,\n",
    "            'splitting_feature': splitting_feature,\n",
    "            'left'             : left_tree, \n",
    "            'right'            : right_tree}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a recursive function to count the nodes in a tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def count_nodes(tree):\n",
    "    if tree['is_leaf']:\n",
    "        return 1\n",
    "    return 1 + count_nodes(tree['left']) + count_nodes(tree['right'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Build the tree!\n",
    "\n",
    "Now that we will train a tree model on the **train_data**. Limit the depth to 6 (**max_depth = 6**) to make sure the algorithm doesn't run for too long. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 0 (37224 data points).\n",
      "Split on feature term. 36 months. (9223, 28001)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 1 (9223 data points).\n",
      "Split on feature grade.A. (9122, 101)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 2 (9122 data points).\n",
      "Split on feature grade.B. (8074, 1048)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 3 (8074 data points).\n",
      "Split on feature grade.C. (5884, 2190)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (5884 data points).\n",
      "Split on feature grade.D. (3826, 2058)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (3826 data points).\n",
      "Split on feature grade.E. (1693, 2133)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (1693 data points).\n",
      "Reached maximum depth. Stopping for now.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (2133 data points).\n",
      "Reached maximum depth. Stopping for now.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (2058 data points).\n",
      "Split on feature grade.E. (2058, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (2190 data points).\n",
      "Split on feature grade.D. (2190, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 3 (1048 data points).\n",
      "Split on feature emp_length.5 years. (969, 79)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (969 data points).\n",
      "Split on feature grade.C. (969, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (79 data points).\n",
      "Split on feature home_ownership.MORTGAGE. (34, 45)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (34 data points).\n",
      "Split on feature grade.C. (34, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (45 data points).\n",
      "Split on feature grade.C. (45, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 2 (101 data points).\n",
      "Split on feature emp_length.n/a. (96, 5)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 3 (96 data points).\n",
      "Split on feature emp_length.< 1 year. (85, 11)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (85 data points).\n",
      "Split on feature grade.B. (85, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (11 data points).\n",
      "Split on feature grade.B. (11, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 3 (5 data points).\n",
      "Split on feature grade.B. (5, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 1 (28001 data points).\n",
      "Split on feature grade.D. (23300, 4701)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 2 (23300 data points).\n",
      "Split on feature grade.E. (22024, 1276)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 3 (22024 data points).\n",
      "Split on feature grade.F. (21666, 358)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (21666 data points).\n",
      "Split on feature emp_length.n/a. (20734, 932)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (20734 data points).\n",
      "Split on feature grade.G. (20638, 96)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (20638 data points).\n",
      "Reached maximum depth. Stopping for now.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (96 data points).\n",
      "Reached maximum depth. Stopping for now.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (932 data points).\n",
      "Split on feature grade.A. (702, 230)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (702 data points).\n",
      "Reached maximum depth. Stopping for now.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (230 data points).\n",
      "Reached maximum depth. Stopping for now.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 4 (358 data points).\n",
      "Split on feature emp_length.8 years. (347, 11)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (347 data points).\n",
      "Split on feature grade.A. (347, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 5 (11 data points).\n",
      "Split on feature home_ownership.OWN. (9, 2)\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (9 data points).\n",
      "Reached maximum depth. Stopping for now.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 6 (2 data points).\n",
      "Stopping condition 1 reached.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 3 (1276 data points).\n",
      "Split on feature grade.A. (1276, 0)\n",
      "Creating leaf node.\n",
      "--------------------------------------------------------------------\n",
      "Subtree, depth = 2 (4701 data points).\n",
      "Split on feature grade.A. (4701, 0)\n",
      "Creating leaf node.\n"
     ]
    }
   ],
   "source": [
    "# Make sure to cap the depth at 6 by using max_depth = 6\n",
    "my_decision_tree = decision_tree_create(train_data, features, 'safe_loans', max_depth = 6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Making predictions with a decision tree\n",
    "\n",
    "The following recursive function `classify`, which takes in a learned `tree` and a test point `x` to classify.  We include an option `annotate` that describes the prediction path when set to `True`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def classify(tree, x, annotate = False):   \n",
    "    # if the node is a leaf node.\n",
    "    if tree['is_leaf']:\n",
    "        if annotate: \n",
    "            print \"At leaf, predicting %s\" % tree['prediction']\n",
    "        return tree['prediction'] \n",
    "    else:\n",
    "        # split on feature.\n",
    "        split_feature_value = x[tree['splitting_feature']]\n",
    "        if annotate: \n",
    "            print \"Split on %s = %s\" % (tree['splitting_feature'], split_feature_value)\n",
    "        if split_feature_value == 0:\n",
    "            return classify(tree['left'], x, annotate)\n",
    "        else:\n",
    "            return classify(tree['right'], x, annotate)\n",
    "                "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's consider the first example of the test set and see what `my_decision_tree` model predicts for this data point."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'emp_length.1 year': 0,\n",
       " 'emp_length.10+ years': 0,\n",
       " 'emp_length.2 years': 1,\n",
       " 'emp_length.3 years': 0,\n",
       " 'emp_length.4 years': 0,\n",
       " 'emp_length.5 years': 0,\n",
       " 'emp_length.6 years': 0,\n",
       " 'emp_length.7 years': 0,\n",
       " 'emp_length.8 years': 0,\n",
       " 'emp_length.9 years': 0,\n",
       " 'emp_length.< 1 year': 0,\n",
       " 'emp_length.n/a': 0,\n",
       " 'grade.A': 0,\n",
       " 'grade.B': 0,\n",
       " 'grade.C': 0,\n",
       " 'grade.D': 1,\n",
       " 'grade.E': 0,\n",
       " 'grade.F': 0,\n",
       " 'grade.G': 0,\n",
       " 'home_ownership.MORTGAGE': 0,\n",
       " 'home_ownership.OTHER': 0,\n",
       " 'home_ownership.OWN': 0,\n",
       " 'home_ownership.RENT': 1,\n",
       " 'safe_loans': -1,\n",
       " 'term. 36 months': 0,\n",
       " 'term. 60 months': 1}"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_data[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Predicted class: -1 \n"
     ]
    }
   ],
   "source": [
    "print 'Predicted class: %s ' % classify(my_decision_tree, test_data[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's add some annotations to our prediction to see what the prediction path was that lead to this predicted class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Split on term. 36 months = 0\n",
      "Split on grade.A = 0\n",
      "Split on grade.B = 0\n",
      "Split on grade.C = 0\n",
      "Split on grade.D = 1\n",
      "At leaf, predicting -1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "classify(my_decision_tree, test_data[0], annotate=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluating decision tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we will write a function to evaluate a decision tree by computing the classification error of the tree on the given dataset.\n",
    "\n",
    "Again, recall that the **classification error** is defined as follows:\n",
    "$$\n",
    "\\mbox{classification error} = \\frac{\\mbox{# mistakes}}{\\mbox{# total examples}}\n",
    "$$\n",
    "\n",
    "Now, function `evaluate_classification_error` that takes in as input:\n",
    "1. `tree` (as described above)\n",
    "2. `data` (an SFrame)\n",
    "3. `target` (a string - the name of the target/label column)\n",
    "\n",
    "This function should calculate a prediction (class label) for each row in `data` using the decision `tree` and return the classification error computed using the above formula."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def evaluate_classification_error(tree, data, target):\n",
    "    # Apply the classify(tree, x) to each row in your data\n",
    "    prediction = data.apply(lambda x: classify(tree, x))\n",
    "    \n",
    "    # Once you've made the predictions, calculate the classification error and return it\n",
    "    return (prediction != data[target]).sum()/float(len(data))\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's use this function to evaluate the classification error on the test set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.3837785437311504"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "evaluate_classification_error(my_decision_tree, test_data, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Printing out a decision stump"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def print_stump(tree, name = 'root'):\n",
    "    split_name = tree['splitting_feature'] # split_name is something like 'term. 36 months'\n",
    "    if split_name is None:\n",
    "        print \"(leaf, label: %s)\" % tree['prediction']\n",
    "        return None\n",
    "    split_feature, split_value = split_name.split('.')\n",
    "    print '                       %s' % name\n",
    "    print '         |---------------|----------------|'\n",
    "    print '         |                                |'\n",
    "    print '         |                                |'\n",
    "    print '         |                                |'\n",
    "    print '  [{0} == 0]               [{0} == 1]    '.format(split_name)\n",
    "    print '         |                                |'\n",
    "    print '         |                                |'\n",
    "    print '         |                                |'\n",
    "    print '    (%s)                         (%s)' \\\n",
    "        % (('leaf, label: ' + str(tree['left']['prediction']) if tree['left']['is_leaf'] else 'subtree'),\n",
    "           ('leaf, label: ' + str(tree['right']['prediction']) if tree['right']['is_leaf'] else 'subtree'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                       root\n",
      "         |---------------|----------------|\n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "  [term. 36 months == 0]               [term. 36 months == 1]    \n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "    (subtree)                         (subtree)\n"
     ]
    }
   ],
   "source": [
    "print_stump(my_decision_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Exploring the intermediate left subtree\n",
    "\n",
    "The tree is a recursive dictionary, so we do have access to all the nodes! We can use\n",
    "* `my_decision_tree['left']` to go left\n",
    "* `my_decision_tree['right']` to go right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                       term. 36 months\n",
      "         |---------------|----------------|\n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "  [grade.A == 0]               [grade.A == 1]    \n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "    (subtree)                         (subtree)\n"
     ]
    }
   ],
   "source": [
    "print_stump(my_decision_tree['left'], my_decision_tree['splitting_feature'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exploring the left subtree of the left subtree\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                       grade.A\n",
      "         |---------------|----------------|\n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "  [grade.B == 0]               [grade.B == 1]    \n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "    (subtree)                         (subtree)\n"
     ]
    }
   ],
   "source": [
    "print_stump(my_decision_tree['left']['left'], my_decision_tree['left']['splitting_feature'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                       grade.A\n",
      "         |---------------|----------------|\n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "  [grade.B == 0]               [grade.B == 1]    \n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "    (subtree)                         (subtree)\n"
     ]
    }
   ],
   "source": [
    "print_stump(my_decision_tree['left']['left'], my_decision_tree['left']['splitting_feature'])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "                       term. 36 months\n",
      "         |---------------|----------------|\n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "  [grade.D == 0]               [grade.D == 1]    \n",
      "         |                                |\n",
      "         |                                |\n",
      "         |                                |\n",
      "    (subtree)                         (leaf, label: -1)\n"
     ]
    }
   ],
   "source": [
    "print_stump(my_decision_tree['right'], my_decision_tree['splitting_feature'])\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}