notebooks/17_decision_trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision Trees\n",
    "\n",
    "*Adapted from Chapter 8 of [An Introduction to Statistical Learning](http://www-bcf.usc.edu/~gareth/ISL/)*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Why are we learning about decision trees?\n",
    "\n",
    "- Can be applied to both regression and classification problems\n",
    "- Many useful properties\n",
    "- Very popular\n",
    "- Basis for more sophisticated models\n",
    "- Have a different way of \"thinking\" than the other models we have studied"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Lesson objectives\n",
    "\n",
    "Students will be able to:\n",
    "\n",
    "- Explain how a decision tree is created\n",
    "- Build a decision tree model in scikit-learn\n",
    "- Tune a decision tree model and explain how tuning impacts the model\n",
    "- Interpret a tree diagram\n",
    "- Describe the key differences between regression and classification trees\n",
    "- Decide whether a decision tree is an appropriate model for a given problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 1: Regression trees\n",
    "\n",
    "Major League Baseball player data from 1986-87:\n",
    "\n",
    "- **Years** (x-axis): number of years playing in the major leagues\n",
    "- **Hits** (y-axis): number of hits in the previous year\n",
    "- **Salary** (color): low salary is blue/green, high salary is red/yellow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Salary data](images/salary_color.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Group exercise:\n",
    "\n",
    "- The data above is our **training data**.\n",
    "- We want to build a model that predicts the Salary of **future players** based on Years and Hits.\n",
    "- We are going to \"segment\" the feature space into regions, and then use the **mean Salary in each region** as the predicted Salary for future players.\n",
    "- Intuitively, you want to **maximize** the similarity (or \"homogeneity\") within a given region, and **minimize** the similarity between different regions.\n",
    "\n",
    "Rules for segmenting:\n",
    "\n",
    "- You can only use **straight lines**, drawn one at a time.\n",
    "- Your line must either be **vertical or horizontal**.\n",
    "- Your line **stops** when it hits an existing line."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Salary regions](images/salary_regions.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above are the regions created by a computer:\n",
    "\n",
    "- $R_1$: players with **less than 5 years** of experience, mean Salary of **\\$166,000 **\n",
    "- $R_2$: players with **5 or more years** of experience and **less than 118 hits**, mean Salary of **\\$403,000 **\n",
    "- $R_3$: players with **5 or more years** of experience and **118 hits or more**, mean Salary of **\\$846,000 **\n",
    "\n",
    "**Note:** Years and Hits are both integers, but the convention is to use the **midpoint** between adjacent values to label a split.\n",
    "\n",
    "These regions are used to make predictions on **out-of-sample data**. Thus, there are only three possible predictions! (Is this different from how **linear regression** makes predictions?)\n",
    "\n",
    "Below is the equivalent regression tree:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Salary tree](images/salary_tree.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first split is **Years < 4.5**, thus that split goes at the top of the tree. When a splitting rule is **True**, you follow the left branch. When a splitting rule is **False**, you follow the right branch.\n",
    "\n",
    "For players in the **left branch**, the mean Salary is \\$166,000, thus you label it with that value. (Salary has been divided by 1000 and log-transformed to 5.11.)\n",
    "\n",
    "For players in the **right branch**, there is a further split on **Hits < 117.5**, dividing players into two more Salary regions: \\$403,000 (transformed to 6.00), and \\$846,000 (transformed to 6.74)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Salary tree annotated](images/salary_tree_annotated.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**What does this tree tell you about your data?**\n",
    "\n",
    "- Years is the most important factor determining Salary, with a lower number of Years corresponding to a lower Salary.\n",
    "- For a player with a lower number of Years, Hits is not an important factor determining Salary.\n",
    "- For a player with a higher number of Years, Hits is an important factor determining Salary, with a greater number of Hits corresponding to a higher Salary.\n",
    "\n",
    "**Question:** What do you like and dislike about decision trees so far?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building a regression tree by hand\n",
    "\n",
    "Your **training data** is a tiny dataset of [used vehicle sale prices](https://raw.githubusercontent.com/justmarkham/DAT8/master/data/vehicles_train.csv). Your goal is to **predict price** for testing data.\n",
    "\n",
    "1. Read the data into a Pandas DataFrame.\n",
    "2. Explore the data by sorting, plotting, or split-apply-combine (aka `group_by`).\n",
    "3. Decide which feature is the most important predictor, and use that to create your first splitting rule.\n",
    "    - Only binary splits are allowed.\n",
    "4. After making your first split, split your DataFrame into two parts, and then explore each part to figure out what other splits to make.\n",
    "5. Stop making splits once you are convinced that it strikes a good balance between underfitting and overfitting.\n",
    "    - Your goal is to build a model that generalizes well.\n",
    "    - You are allowed to split on the same variable multiple times!\n",
    "6. Draw your tree, labeling the leaves with the mean price for the observations in that region.\n",
    "    - Make sure nothing is backwards: You follow the **left branch** if the rule is true, and the **right branch** if the rule is false."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How does a computer build a regression tree?\n",
    "\n",
    "**Ideal approach:** Consider every possible partition of the feature space (computationally infeasible)\n",
    "\n",
    "**\"Good enough\" approach:** recursive binary splitting\n",
    "\n",
    "1. Begin at the top of the tree.\n",
    "2. For **every feature**, examine **every possible cutpoint**, and choose the feature and cutpoint such that the resulting tree has the lowest possible mean squared error (MSE). Make that split.\n",
    "3. Examine the two resulting regions, and again make a **single split** (in one of the regions) to minimize the MSE.\n",
    "4. Keep repeating step 3 until a **stopping criterion** is met:\n",
    "    - maximum tree depth (maximum number of splits required to arrive at a leaf)\n",
    "    - minimum number of observations in a leaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Demo: Choosing the ideal cutpoint for a given feature"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# vehicle data\n",
    "import pandas as pd\n",
    "url = 'https://raw.githubusercontent.com/justmarkham/DAT8/master/data/vehicles_train.csv'\n",
    "train = pd.read_csv(url)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>price</th>\n",
       "      <th>year</th>\n",
       "      <th>miles</th>\n",
       "      <th>doors</th>\n",
       "      <th>vtype</th>\n",
       "      <th>prediction</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>22000</td>\n",
       "      <td>2012</td>\n",
       "      <td>13000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>14000</td>\n",
       "      <td>2010</td>\n",
       "      <td>30000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>13000</td>\n",
       "      <td>2010</td>\n",
       "      <td>73500</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>9500</td>\n",
       "      <td>2009</td>\n",
       "      <td>78000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>9000</td>\n",
       "      <td>2007</td>\n",
       "      <td>47000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>4000</td>\n",
       "      <td>2006</td>\n",
       "      <td>124000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>3000</td>\n",
       "      <td>2004</td>\n",
       "      <td>177000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2000</td>\n",
       "      <td>2004</td>\n",
       "      <td>209000</td>\n",
       "      <td>4</td>\n",
       "      <td>truck</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>3000</td>\n",
       "      <td>2003</td>\n",
       "      <td>138000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>1900</td>\n",
       "      <td>2003</td>\n",
       "      <td>160000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>2500</td>\n",
       "      <td>2003</td>\n",
       "      <td>190000</td>\n",
       "      <td>2</td>\n",
       "      <td>truck</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>5000</td>\n",
       "      <td>2001</td>\n",
       "      <td>62000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>1800</td>\n",
       "      <td>1999</td>\n",
       "      <td>163000</td>\n",
       "      <td>2</td>\n",
       "      <td>truck</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>1300</td>\n",
       "      <td>1997</td>\n",
       "      <td>138000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>6571.428571</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    price  year   miles  doors  vtype   prediction\n",
       "0   22000  2012   13000      2    car  6571.428571\n",
       "1   14000  2010   30000      2    car  6571.428571\n",
       "2   13000  2010   73500      4    car  6571.428571\n",
       "3    9500  2009   78000      4    car  6571.428571\n",
       "4    9000  2007   47000      4    car  6571.428571\n",
       "5    4000  2006  124000      2    car  6571.428571\n",
       "6    3000  2004  177000      4    car  6571.428571\n",
       "7    2000  2004  209000      4  truck  6571.428571\n",
       "8    3000  2003  138000      2    car  6571.428571\n",
       "9    1900  2003  160000      4    car  6571.428571\n",
       "10   2500  2003  190000      2  truck  6571.428571\n",
       "11   5000  2001   62000      4    car  6571.428571\n",
       "12   1800  1999  163000      2  truck  6571.428571\n",
       "13   1300  1997  138000      4    car  6571.428571"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# before splitting anything, just predict the mean of the entire dataset\n",
    "train['prediction'] = train.price.mean()\n",
    "train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5936.9819859959835"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# calculate RMSE for those predictions\n",
    "from sklearn import metrics\n",
    "import numpy as np\n",
    "np.sqrt(metrics.mean_squared_error(train.price, train.prediction))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# define a function that calculates the RMSE for a given split of miles\n",
    "def mileage_split(miles):\n",
    "    lower_mileage_price = train[train.miles < miles].price.mean()\n",
    "    higher_mileage_price = train[train.miles >= miles].price.mean()\n",
    "    train['prediction'] = np.where(train.miles < miles, lower_mileage_price, higher_mileage_price)\n",
    "    return np.sqrt(metrics.mean_squared_error(train.price, train.prediction))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RMSE: 3984.09174254\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>price</th>\n",
       "      <th>year</th>\n",
       "      <th>miles</th>\n",
       "      <th>doors</th>\n",
       "      <th>vtype</th>\n",
       "      <th>prediction</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>22000</td>\n",
       "      <td>2012</td>\n",
       "      <td>13000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>15000.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>14000</td>\n",
       "      <td>2010</td>\n",
       "      <td>30000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>15000.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>13000</td>\n",
       "      <td>2010</td>\n",
       "      <td>73500</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>9500</td>\n",
       "      <td>2009</td>\n",
       "      <td>78000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>9000</td>\n",
       "      <td>2007</td>\n",
       "      <td>47000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>15000.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>4000</td>\n",
       "      <td>2006</td>\n",
       "      <td>124000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>3000</td>\n",
       "      <td>2004</td>\n",
       "      <td>177000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2000</td>\n",
       "      <td>2004</td>\n",
       "      <td>209000</td>\n",
       "      <td>4</td>\n",
       "      <td>truck</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>3000</td>\n",
       "      <td>2003</td>\n",
       "      <td>138000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>1900</td>\n",
       "      <td>2003</td>\n",
       "      <td>160000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>2500</td>\n",
       "      <td>2003</td>\n",
       "      <td>190000</td>\n",
       "      <td>2</td>\n",
       "      <td>truck</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>5000</td>\n",
       "      <td>2001</td>\n",
       "      <td>62000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>1800</td>\n",
       "      <td>1999</td>\n",
       "      <td>163000</td>\n",
       "      <td>2</td>\n",
       "      <td>truck</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>1300</td>\n",
       "      <td>1997</td>\n",
       "      <td>138000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>4272.727273</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    price  year   miles  doors  vtype    prediction\n",
       "0   22000  2012   13000      2    car  15000.000000\n",
       "1   14000  2010   30000      2    car  15000.000000\n",
       "2   13000  2010   73500      4    car   4272.727273\n",
       "3    9500  2009   78000      4    car   4272.727273\n",
       "4    9000  2007   47000      4    car  15000.000000\n",
       "5    4000  2006  124000      2    car   4272.727273\n",
       "6    3000  2004  177000      4    car   4272.727273\n",
       "7    2000  2004  209000      4  truck   4272.727273\n",
       "8    3000  2003  138000      2    car   4272.727273\n",
       "9    1900  2003  160000      4    car   4272.727273\n",
       "10   2500  2003  190000      2  truck   4272.727273\n",
       "11   5000  2001   62000      4    car   4272.727273\n",
       "12   1800  1999  163000      2  truck   4272.727273\n",
       "13   1300  1997  138000      4    car   4272.727273"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# calculate RMSE for tree which splits on miles < 50000\n",
    "print 'RMSE:', mileage_split(50000)\n",
    "train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "RMSE: 3530.14653008\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>price</th>\n",
       "      <th>year</th>\n",
       "      <th>miles</th>\n",
       "      <th>doors</th>\n",
       "      <th>vtype</th>\n",
       "      <th>prediction</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>22000</td>\n",
       "      <td>2012</td>\n",
       "      <td>13000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>12083.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>14000</td>\n",
       "      <td>2010</td>\n",
       "      <td>30000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>12083.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>13000</td>\n",
       "      <td>2010</td>\n",
       "      <td>73500</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>12083.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>9500</td>\n",
       "      <td>2009</td>\n",
       "      <td>78000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>12083.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>9000</td>\n",
       "      <td>2007</td>\n",
       "      <td>47000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>12083.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>4000</td>\n",
       "      <td>2006</td>\n",
       "      <td>124000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6</th>\n",
       "      <td>3000</td>\n",
       "      <td>2004</td>\n",
       "      <td>177000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>2000</td>\n",
       "      <td>2004</td>\n",
       "      <td>209000</td>\n",
       "      <td>4</td>\n",
       "      <td>truck</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>3000</td>\n",
       "      <td>2003</td>\n",
       "      <td>138000</td>\n",
       "      <td>2</td>\n",
       "      <td>car</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9</th>\n",
       "      <td>1900</td>\n",
       "      <td>2003</td>\n",
       "      <td>160000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>2500</td>\n",
       "      <td>2003</td>\n",
       "      <td>190000</td>\n",
       "      <td>2</td>\n",
       "      <td>truck</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>5000</td>\n",
       "      <td>2001</td>\n",
       "      <td>62000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>12083.333333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>1800</td>\n",
       "      <td>1999</td>\n",
       "      <td>163000</td>\n",
       "      <td>2</td>\n",
       "      <td>truck</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>1300</td>\n",
       "      <td>1997</td>\n",
       "      <td>138000</td>\n",
       "      <td>4</td>\n",
       "      <td>car</td>\n",
       "      <td>2437.500000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    price  year   miles  doors  vtype    prediction\n",
       "0   22000  2012   13000      2    car  12083.333333\n",
       "1   14000  2010   30000      2    car  12083.333333\n",
       "2   13000  2010   73500      4    car  12083.333333\n",
       "3    9500  2009   78000      4    car  12083.333333\n",
       "4    9000  2007   47000      4    car  12083.333333\n",
       "5    4000  2006  124000      2    car   2437.500000\n",
       "6    3000  2004  177000      4    car   2437.500000\n",
       "7    2000  2004  209000      4  truck   2437.500000\n",
       "8    3000  2003  138000      2    car   2437.500000\n",
       "9    1900  2003  160000      4    car   2437.500000\n",
       "10   2500  2003  190000      2  truck   2437.500000\n",
       "11   5000  2001   62000      4    car  12083.333333\n",
       "12   1800  1999  163000      2  truck   2437.500000\n",
       "13   1300  1997  138000      4    car   2437.500000"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# calculate RMSE for tree which splits on miles < 100000\n",
    "print 'RMSE:', mileage_split(100000)\n",
    "train"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# check all possible mileage splits\n",
    "mileage_range = range(train.miles.min(), train.miles.max(), 1000)\n",
    "RMSE = [mileage_split(miles) for miles in mileage_range]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# allow plots to appear in the notebook\n",
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "plt.rcParams['figure.figsize'] = (6, 4)\n",
    "plt.rcParams['font.size'] = 14"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x172f5b70>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAa8AAAEZCAYAAAAg+KppAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XucHFWd9/HPNyGQC4abECSIgC4QYFclshIu7oAsoCy7\nLuuyyIIgiry8IeJdUZLn5aoLqCiPuw94WQSFBfVhEVYh3AaQBFiDAnL3AQIBknBLyARCLvyeP041\nqWlmuntmurq7ur/v16tfma46XXWqKeY759SpU4oIzMzMymRcuytgZmY2Ug4vMzMrHYeXmZmVjsPL\nzMxKx+FlZmal4/AyM7PScXiZmVnptDy8JL1O0k8kLZX0oqS7Jb2jqsxsSY9LekHS9ZJ2rVq/kaSz\nJT0laUDSZZKmV5XZTNIFkpZlr/MlbdKKYzQzs2K1NLwkbQrcDATwbmAX4OPA0lyZzwOnZMv3zNZd\nLWnj3KbOAg4HjgT2A6YCV0jKH8+FwFuAg4FDgD2ACwo5MDMzaym1coYNSV8H9ouI/YZZL+AJ4HsR\n8Y1s2URSgH0mIs7NWk9LgeMi4qKszLbAQuBdETFX0gzgbmCfiJifldkHuAnYJSIeKPRAzcysUK3u\nNnwPcJukiyUtkfR7SR/Lrd8BmAbMrSyIiFXAjcDe2aKZwISqMouAe4FZ2aJZwEAluDLzgJW5MmZm\nVlKtDq8dgY8CfwIOAr4LfDMXYFtn/y6p+tzS3LqtgXUR8UxVmSVVZZ7Kr4zUxMxvx8zMSmqDFu9v\nHHBbRHw5e3+HpD8DPgZ8v85n6/VvaqyVMzOzcmh1eD0B3FO17D5gu+znxdm/04BFuTLTcusWA+Ml\nbVHV+poG3JArs2V+J9n1tK1y26ks97T6ZmajEBFtazS0utvwZtIIw7ydgEeynx8mhctBlZXZgI19\nSdesABYAa6rKbJttt1JmPrCxpPz1rVnAlFyZV0SEXxGcdtppba9Dp7z8Xfi78HdR+9VurW55fQeY\nJ+lLwCXAW4FPAF+EdF1K0lnAlyTdBzwInAqsIA19JyKWS/oRcLqkpcCzwLeBO4BrsjL3SroSOEfS\nh0ldiucAl0fEgy07WjMzK0RLwysififpPcDXga+QhrefGhH/nitzuqRJpGtgmwG3AAdFxMrcpk4G\n1gIXA5NIoXV0DP5z4CjgbOCq7P1lpHvHzMys5Frd8iIifg38uk6ZOcCcGutXAydlr+HKLAOOGWU1\nG/byy3DNNXDQQfXLdrq+vr52V6Fj+LtYz9/Fev4uOkdLb1LuRJJiLN/B2rUwcWL618ysV0giemjA\nRtcZNy61vszMrHUcXmMkQUR6mZlZazi8xkhKL7e+zMxax+HVBOPHO7zMzFrJ4dUEvu5lZtZaDq8m\ncHiZmbWWw6sJHF5mZq3l8GoCh5eZWWs5vJrA4WVm1loOryZweJmZtVbL5zbsRg4vs/JZtw5efLG4\n7U+enH43WDEcXk0wblz6H8HMyuPEE+GnP4UNCvot+Mc/wvbbF7Ntc3g1hVteZuVz//1w1VXwV3/V\n7prYaLhR2wSeYcOsfB57DF7/+nbXwkbL4dUEbnmZlcu6dfDkkzB9ertrYqPl8GoCh5dZuSxeDJtv\nDhtt1O6a2Gg5vJrA4WVWLu4yLD+HVxM4vMzK5dFHYbvt2l0LGwuHVxM4vMzKxS2v8nN4NYHDy6xc\nHF7l5/BqAoeXWbk4vMrP4dUEnmHDrFx8zav8PMNGE/gmZbPW+s1vYGBg9J9/6CG3vMrO4dUE7jY0\na50lS+Af/gEOPXT02/j7v4ett25enaz1HF5N4PAya52FC2G33eDnP293TaydfM2rCRxeZq2zcKGv\nV5nDqykcXmats3AhvOEN7a6FtZvDqwkcXmat45GCBiO45iVpa+DPgE2AZcCfImJxURUrE4eXWess\nXAj779/uWli71QwvSdsCHwLeRwqu6vUPAhcBP4yIRYXUsAQcXmat42teBjW6DSV9B7gHeBtwJrAH\n8Fpgw+zfmcC3gT2BeyR9u/DadijfpGzWOo8+6mteVrvlFcBOw3QNPpu9fg+cI+l1wGcKqF8p+CZl\ns9ZYsQJeegm22KLdNbF2Gza8IuIUAEnjgF2ARyNiyHvaI+JJ4NOF1LAE3G1o1hqVwRpSu2ti7dbo\ngI07gBnAn8ayM0mzga9WLV4cEdtk688D3l+1/paI2Du3jY1I3ZhHApOAa4GPRsTjuTKbAd8DDssW\n/Qr4REQsH0v9h+PwMqvv+edh2bKxbWPBAl/vsqRueEXEy5LuB7ZkjOGVuQ/oy73PXy0K4GrgmNyy\n1VWfPwv4W1J4PUu67naFpJkRUYmQC4FtgYMBAT8ELsg+13QOL7P6DjoIHnkENtxwbNv58IebUh0r\nuUZbXp8FzpT0ceAPERFj2Oe6iFg6zDoBq4dbL2kT4HjguIi4Nlt2DLAQOBCYK2kGKbT2iYhbszIn\nAjdJ2ikiHhhD3Yfk8DKrb+lSuPlmeOMb210T6waN3qR8CfCXwALgJUkrcq/nR7jPHSU9LukhSRdJ\n2iG3LoB9JS2RdL+kcyVtmVs/E5gAzH3lA2mI/r3ArGzRLGAgIubnPjcPWJkr01QOL7P6li2DTTZp\ndy2sWzTa8vpEk/Z3C3AsqetwGnAqME/SbhHxLHAl8EvgYWAH4GvAdVmX4Gpga1LL7Zmq7S7J1pH9\n+1R+ZUSEpKW5Mk3l8DKrLSJd83J4WbM0FF4RcV4zdhYRV+be/lHSfFJQHQt8JyIuzq2/W9ICUpfg\nocClNTY9prFHs2fPfuXnvr4++vr6RvR5h5dZbQMDsNFGMGFCu2tio9Xf309/f3+7q/GKkU4PdQyw\nI/CViHha0r7A4xHx8Gh2HhEvSLobeNMw65+UtCi3fjEwXtIWVa2vacANuTL5rkYkCdgqW/cq+fAa\nDd+kbFbb8uWw6abtroWNRfUf9nPmzGlfZWjwmpekmcD9wFGk6aKmZqv+GviX0e5c0kTSEPwnh1m/\nJTA9t34BsAY4KFdmW9J9aPOyRfOBjSXlr2/NAqbkyjSVb1I2q83Xu6zZGh2w8S3guxHxVmBVbvmV\nwL6N7kzSmZLeIWkHSW8HfkG6V+snkqZk6/eStL2kPtL9WUvIugyz+7R+BJwu6Z2S3koaAn8HcE1W\n5t6sXudk25oFnANcHhEPNlrXkXC3oVltbnlZszXabbgHaYh6tcWkLrtGTSdN5Pta0qCK+cBeEfFY\n1grbndQ1uSmptXUd8N6IWJnbxsnAWuBiUvBdAxxdNXz/KOBs4Krs/WXAx0dQzxFxeJnVtny5W17W\nXI2G14vA5sBDVct3Boa7Z+tVIuJ9NdatAg5pYBurgZOy13BlljH4RudCObzMalu2zC0va65Guw0v\nA07LWkcAZPdnnU4a2t7THF5mtbnlZc3WaHh9FtiM1NU3GfgtaaqoZaR7tXqaw8usNre8rNkavc9r\nuaT9gP1Js1yMAxZExDVFVq4sHF5mtbnlZc3WUHhJej9wSURcRxpEUVm+IXBkRJxfUP1KweFlVtuy\nZX6ApDVXo92G57H+3q68qdm6nuablM1qc8vLmq3R8BrO60nXvXqab1I2q803KVuz1ew2lHRX7u0N\nktbm3o8H3gD8uoiKlYm7Dc1q803K1mz1rnlVhsHvBlxBeqxIxWrSpLoeKu/wMqvJ3YbWbDXDKyJm\nA0h6GLg4u5HYqji8zGrzUHlrtkavec0mTWw7iKTNJFXPutFzHF5mtbnlZc3WaHi9gXSNq9pGwLbN\nq045ObzMhrdmDaxaBRtv3O6aWDepN2DjcNY/6PFvJOVHFo4HDgQeKaZq5eHwMhve88/D1KmgMT0y\n1mywegM2fpH7+YdV69aQguuUZlaojBxeZq922GFw443p/43ttmt3bazb1BuwMQ5A0iPA2yLi6VZU\nqmx8k7LZq91zD/T3w447wsSJdYubjUijcxtuX3A9Ss0tL7NXGxiA173OAzWsGA0N2FDyMUl3S3pR\n0o7Z8i9IOqLYKnY+z7Bh9moDAx6kYcVpdLThJ0mPPvlB1fInKPAJxWXhlpfZYOvWpRGGkye3uybW\nrRoNr48AJ0TEWUB+iqjbgd2bXquScXiZDbZyZQqucWOdPdVsGI2eWtsBdw2xfA0wqXnVKSeHl9lg\n7jK0ojUaXg+THkJZ7V3APc2rTjk5vMwGGxiA17ym3bWwbtbQaEPgDOB/S5pECry9swdUfg44vqjK\nlYXDy2ywFSvc8rJiNTpU/j8kbQB8g9RNeD5psMYnIuI/C6xfKTi8zAZzt6EVrdGWFxHxA+AHkrYE\nxkXEkuKqVS6+SdlsMIeXFa3h8AKQ9EZgRvbzvRHx/wqpVcm45WU2mK95WdEaCi9JWwA/Bg4DKr+m\nx0m6AvhARDxTUP1KwTcpmw3ma15WtEZHG/4QeCOwH+ma16Ts5x149YS9PcctL7PB3G1oRWu02/Bg\n4MCImJdbdrOkDwPXNr9a5eLwMhvM3YZWtEZbXk8DK4dY/kK2rqc5vMwGc7ehFa3R8PpfwHckvfLU\n5Oznb2freprDy2wwdxta0YbtNpRUPR3U9sAjkh7P3k8HXgS2pMevezm8zAZzeFnRal3z+mWD24hm\nVKTMHF5mg61Y4WteVqxhwysiZrewHqXm8DIbzC0vK5ofWNAEnmHDbDCHlxWtpeElabakl6teTwxR\n5nFJL0i6XtKuVes3knS2pKckDUi6TNL0qjKbSbpA0rLsdb6kwh5G7puUzQbzUHkrWjtaXvcBW+de\nf15ZIenzwCmkpzPvCSwFrpaU/xvuLOBw4EjSjdJTgSsk5Y/lQuAtpPvTDgH2AC4o6HjcbWhWxUPl\nrWgjmtuwSdZFxNLqhZIEnAx8IyIuzZYdSwqwo4Bzs9bT8cBxEXFtVuYYYCFwIDBX0gxSaO0TEbdm\nZU4EbpK0U0Q80OwDcniZDeZuQyvaqFtekiaM8qM7Zt2CD0m6SNIO2fIdgGnA3ErBiFgF3AjsnS2a\nCUyoKrMIuBeYlS2aBQxExPzcPueRbrKeRQEcXmaDudvQitZQeEn6pKT35t7/GFgl6QFJO49gf7cA\nx5JaRieQug3nSdo8+xmg+lErS3Prtia13KonAl5SVeap/MqIiKrtNJXDy2y9tWth9WqYOLHdNbFu\n1mjL6ySyQJD0DuAfSV15vwe+1ejOIuLKiPhFRPwx6/Y7NKvDsfU+Wme9Gq1DERxeZutVugzV1v8r\nrds1es1rG+Ch7OfDgF9ExMWS7gR+O9qdR8QLku4G3gT8V7Z4GrAoV2wasDj7eTEwXtIWVa2vacAN\nuTJb5veTXU/bKredQWbPnv3Kz319ffT19Y3oOBxe1ukGBlp3ji5e7Otd3ai/v5/+/v52V+MVjYbX\n86SAeAz4a+DMbPlaYNSdA5Imkh5ueV1EPCxpMXAQsCC3fl/gM9lHFgBrsjIXZWW2BXYhXdcCmA9s\nLGlW7rrXLGBKrswg+fAaDYeXdbLf/hb6+mDy5Nbtc889W7cva43qP+znzJnTvsrQeHjNBX4g6XZS\nK+k32fJdgYcb3ZmkM4FfkUJwK+ArpGeD/SQrchbwJUn3AQ8CpwIrSEPfiYjlkn4EnC5pKfAsaXLg\nO4BrsjL3SroSOCd7ZIuAc4DLI+LBRus6Er5J2TrZsmVwyCFwxRXtrolZ8zQaXh8HvgZsB7w312U3\nkyxYGjSd1GJ6Leka2nxgr4h4DCAiTpc0Cfg+sBlpgMdBEZF/HMvJpBbfxaTguwY4OhuUUXEUcDZw\nVfb+suwYCuGblK2TrV0LG7TjphizAjV0SkfEcuATQyz/6kh2FhHva6DMHGDY9mhErCYNIDmpRpll\nwDEjqdtYuNvQOpnDy7pRrUeibB4Rz1Z+rrWRSrle5fCyTubwsm5U65R+WtLW2WwYtZ6WHMD45lar\nXBxe1skcXtaNap3SBwDP5X62YTi8rJM5vKwb1XqeV/9QP9urObyskzm8rBv5eV5N4PCyTubwsm7k\n8GoCh5d1MoeXdSOHVxP4JmXrZA4v60YOrybwTcrWyRxe1o3qhpekDSUtlrRbKypURu42tE7m8LJu\nVDe8shkt1lL/sSQ9y+FlnczhZd2o0W7Ds4EvjuHpyV3N4WWdzOFl3ajRU3pf4K+ARZL+CLyQWxcR\n8bdNr1mJOLysk61d66caW/dpNLyeAf7vMOt6vjvR4WWdzC0v60aNzip/XMH1KDWHl3WyNWscXtZ9\nGh4qr+Rtkv5J0sbZso19HczhZZ3NLS/rRg2d0pKmkR7o+JekbsI/AwaAbwGrgE8WVcEy8E3K1snW\nroUJPf8npnWbRlte3wGWAlsweLDGz4GDm12psnHLyzqZW17WjRo9pd8JvDMinpOUX/4QsF3Ta1Uy\nnmHDOpnDy7pRoy2vScCaIZa/ltRt2NPc8rJO5vCybtRoeN0EHJdfIGkD4PPAtU2uU+k4vKyTObys\nGzV6Sn8WuFHSnsBGwJnA7sAmwD4F1a00HF7WyRxe1o0aanlFxD3AnwPzgKuBicAlwFsi4k/FVa8c\nHF7WyRxe1o0aPqUj4kngqwXWpbQcXtbJHF7WjRq9z+tq4HqgH7gtItYWWamycXhZJ3N4WTdqdMDG\nrcC7geuAZZLmSvqSpL2zgRs9zTcpWydzeFk3anRuw1MBJE0G9ibNMP8uYA5pqPxriqpgGbjlZZ3M\n4WXdqOG5DTOvId3btRWwNekhlb9rdqXKxjcpWydzeFk3avSa178DfcAbSF2I/cCHgFsjwjcpu+Vl\nHczhZd2o0VP6ROBp4JvAb4AFEeFf1xmHl3Uyh5d1o0ZP6Z1ILa8+UotrqqSbyEYgRsTthdSuJBxe\n6z34ILzwQv1yeRLMmOGZz4vi8LJu1OiAjT8BfwJ+CCBpF+BzpJbY+OzVsxxeyYoVKYR2221kn1u4\nEH78Yzj88GLq1escXtaNGr3mNQ54G3AAqfW1D2maqAWk6189zeGVvPgibL453HHHyD539NEjb61Z\n4xxe1o0aPaWXkaaEqoTVWcBvI2KgoHqVisMrWb0aNtxw5J+bMCF91orh8LJu1OgpfQQOq2H5JuVk\nLOG1ZqgH7lhTOLysGzU6Me+VETEgaaKk3SXtJmniWHYs6YuSXpZ0dm7Zedmy/Gte1ec2knS2pKck\nDUi6TNL0qjKbSbpA0rLsdb6kTcZS31rGjYOI9OplL700uvDacEOHV5EcXtaNGgovSRMknUnqPrwT\nuIs0TdQZkkY8RkzSXsAJ2bbyv/KDNGv91rnXu6s+fhZwOHAksB8wFbgiuy5XcSHwFuBg4BBgD+CC\nkdazUVJ69Xp4ueXVmdascXhZ92n0lP5X4H2k+71uzpbtC3yDFICfbnSHWQvop8AHgNnVq4HVEbG0\nxmePB46LiGuzZccAC4EDgbmSZpBCa5+IuDUrcyJwk6SdIuKBRus6EpXrXuNGOmdJF1m9GjbaaOSf\n8zWvYrnlZd2o0V+1RwEfioifRMSfstd5pHu+/nmE+zwX+HlE3EAKq7wA9pW0RNL9ks6VtGVu/Uxg\nAjD3lQ9ELALuBWZli2YBAxExP/e5ecDKXJmm86CN0be83G1YrLVrfQ+ddZ9G/x7bhHSfV7WHgE0b\n3ZmkE4AdSWEIg7sMAa4Efgk8DOwAfA24TtLMiFhN6kZcFxHPVH1uSbaO7N+n8isjIiQtzZVpOoeX\nuw07lVte1o0aPaXvBD4JfLSyQJKAk4A/NLIBSTsD/wLsGxGVsXki1/qKiItzH7lb0gJSl+ChwKW1\nNt9IHYrk8Br9gI0JE9INzlYMh5d1o0ZP6c8Cv5H0TuAWUljsBWxDejRKI2aRZqS/O+UekGbm2C+7\nJjUlIgb9/R0RT0paBLwpW7QYGC9pi6rW1zTghlyZfFdjJWi3yta9yuzZs1/5ua+vj76+vgYPaT2H\n1+ivebnbsFgOL2uG/v5++vv7212NVzQ6PdSNknYitbxmkLr7LgH+LSKeaHBflwK35d4L+A/gAeDr\n1cEFkF3vmg48mS1aAKwBDgIuyspsC+xCuq4FMB/YWNKs3HWvWcCUXJlB8uE1Wg4vdxt2KoeXNUP1\nH/Zz5sxpX2VovOVFRDwOfHm0O4qI5cDy/DJJLwDPRcQ9kjYmjT78BamFtD1pNOMSsi7DiFgu6UfA\n6dk1rGeBbwN3ANdkZe6VdCVwjqQPk0LyHODyiHhwtPWvx+HlGTY6UeWc7OVRsNadhg0vSXs0upEx\nzCofrB+0sRbYHTiGNAjkSeA64L0RsTL3mZOzshcDk0ihdXTEoLusjgLOBq7K3l8GfHyUdWyIZ9kY\n2zUvt7yK4VaXdatap3WjT0gORjmrfETsn/t5FemG4nqfWU0aKHJSjTLLSCHYMn6asofKdyKHl3Wr\nWqf1ji2rRRdwt6FvUu5EDi/rVsOe1hHxSAvrUXoOLw/Y6EQOL+tWw17GlTSiltdIy3cbh5e7DTuR\nw8u6Va0xSPMk/VTSO5W7MStPyYGSfsYww9B7hcPLAzY6kcPLulWt03pn0s3JFwKTJN0OPAoMAK8B\ntgPeCqwizVe4c7FV7WwOr9TymjJl5J/zNa/iOLysWw3b8oqI5RFxKvB60uNHbiHd6Psm0lOV52XL\nt42IU7P7uHqWw8szbHQih5d1q7qndTY0/dfZy4bh8PKAjU7k8LJu5fvum8Q3KXuGjU7k8LJu5fBq\nEt+kPPoBG+42LI7Dy7qVw6tJ3G3obsNO5PCybuXwahKHl2fY6EQOL+tWDq8mcXj5JuVO5PCyblUz\nvCR9XdKU3Pt3S5qcez9V0vlFVrAsHF7uNuxEa9Y4vKw71Wt5fYF0b1fFxcDWufeTgaObXakycniN\nbYYNdxsWwy0v61buNmwSh5dbXp1o7dr0/Zp1G4dXkzi8PMNGJ3LLy7qVw6tJfJOyW16dyOFl3aqR\n0/ojklYAAiYAH5T0TLZuamE1Kxm3vEYfXhtskH7JRsDQzy+w0XJ4Wbeqd1o/ChyXe78YOCr3XsDC\nJteplDzDxugHbEjrW1+j+bwNz+Fl3armaR0R27eoHqXnltfoW17g8CqKw8u6la95NYnDa/QDNsDD\n5Yvi8LJuVe8m5bdIOqBq2dGSHpa0VNI5kvy3Mg4vGFvLyyMOi+Hwsm5Vr+X1NWDfyhtJuwI/Bh4A\n/pN0/esLhdWuRBxezek2tOZyeFm3qhdebwXm5t4fCdwbEQdHxEnAycARRVWuTBxeox+wAe42LIrD\ny7pVvfDaAng89/4dwOW59zcAb2h2pcqo18Nr3bp0/KP9Reluw2I4vKxb1Quvp4DpAJI2AGYCt+bW\nbwj08K/s9Xr9JuXKSMHR3qflbsNiOLysW9ULrxuA0yTtCJxCuq/r+tz6GcAjxVStXHq95TWW613g\nbsOiOLysW9U7rb8CXA38idTCOikiBnLr3w9cW1DdSqXXb1Iey/UucMurKA4v61b1blJ+WNIMYDfg\nqYh4vKrIacBjRVWuTMaPh299Cy65pLnb3Wcf+NjHmrvNIoy15eVrXsVweFm3qntaR8Qa4A/DrBty\neS+aMwfuvLO523zwQfjZz8oTXqO9QRnc8irK2rWetcS6U83wkvRpIOptJCK+3bQaldTuu6dXM91+\nO1x2WXO3WRRf8+pMa9fC5Mn1y5mVTb2W1xnA08DKOuV6PryKMGkSvPhiu2vRGHcbdiZ3G1q3qnda\n/w/petevgR9FxE3FV8kqJk4sT3h5wEZncnhZt6o5VD4i3g7sBTwH/FLS/ZI+L2nrltSux02aBKtW\ntbsWjXG3YWdyeFm3qjurfET8MSI+BWwLfBnoAx6R9CtJE0e7Y0lflPSypLOrls+W9LikFyRdn82n\nmF+/kaSzJT0laUDSZZKmV5XZTNIFkpZlr/MlbTLaurZL2boNxzJgw92GxVizxuFl3anh0zoiVkv6\nJfA8MBk4FJgIjLhtIGkv4ATgTnIDQiR9nnQz9LGkyX+/Clwtaefc/WVnAX9LmmfxWdL1tiskzYyI\nyp1WF5LC9mDSjdU/BC7IPlcaZeo2bEbLy+E12G23wfPPj20bjz4KM2c2pz5mnaSh8JK0A/ABUqgI\n+AlwXEQsG+kOsxbQT7Ptzc4tF2mi329ExKXZsmOBpaTZ68/NPnt8tu9rszLHkJ7mfCAwN7sv7WBg\nn4i4NStzInCTpJ0i4oGR1rldNtwwdfusW5fuI+tk7jZsrlWrYO+9oa9v7Nv6i78Y+zbMOk29ofJH\nk8JiFmlC3hOBqyKi7vD5Gs4Ffh4RN2SBVbEDMI3cLPYRsUrSjcDe2edmAhOqyiySdG9Wx7nZvwMR\nMT+37XmkEZOzSC26UpDWX/eaMqXdtaltrAM23G042KpVsPHGcM017a6JWWeq1/I6nzSDxlmkIfO7\nAruqavbVRu/zknQCsCOpJQWD7yGrDAJZUvWxpcA2uTLrIuKZqjJLcp/fmjShcL5+IWlprkxpTJxY\njvByt2FzrVqV/tub2dDqhdejpIA5sk65uuElaWfgX4B9I6Iy/7qyVz31WnqjnMs8mT179is/9/X1\n0deMvpomKcugjWbMsOFuw/VWrRrb92nWbP39/fT397e7Gq+oN7fh9k3c1yzgtcDduZbbeGC/7JpU\nZX6KacCi3OemAYuznxcD4yVtUdX6mkaaAb9SZsv8jrPuya1y2xkkH16dpshBG4sXp4v5zQiNF1+E\n448f/efd8hrspZfc8rLOUv2H/Zw5c9pXGUYw2nA4knaIiIcbKHopcFv+o8B/kK5BfR14kBQuBwEL\nsm1PBPYFPpN9ZgGwJitzUVZmW2AX0nUtgPnAxpJm5a57zQKm5MqURpH3ej35JGy2GVx/ff2yjdh0\n09F/1te8BnO3oVltow4vSW8DPgf8PWkQRU0RsRxYXrWNF4DnIuKe7P1ZwJck3UcKs1OBFaSh70TE\nckk/Ak7PrmFVhsrfAVyTlblX0pXAOZI+TArJc4DLI+LB0R5vuxTZbbhiRQqvLbesX7ZoEybAynqT\nkPUQdxua1VbzJmVJr5N0taQVkq6TtLmkGZLmklpRO5Ke6TVaQe56VkScDnwH+D5paqppwEERkf+1\ndjKpFXcx8FvSfWeHVY2APIoUaFcBVwK/B44ZQz3bpshuw4GBNKKtE7jbcDB3G5rVVq/l9U1gZ9Iw\n9UNI93cfcYRnAAAQW0lEQVT9FfA7YP+IuKHGZ+uKiP2HWDYHGLYzNSJWAydlr+HKLKOkYVWtyG7D\nTgovdxsO5m5Ds9rqhdc7gQ9ExNWSvk96ovLZEfHJ4qtmUGy34cAAvOY1xWx7pNzyGszdhma11Zvb\ncBpwN0BEPESaCuoHRVfK1iuy23DFis5peXmo/GDuNjSrrV54jQfW5t6vA14orjpWzd2Gvcndhma1\nNTLa8AJJL5FG7U0kzTGYbwtERJRqwtsyKXrAhrsNO9NLL7nb0KyWRqaHCtbPYPGzIcqMZZ5Dq6Po\na17bbFO/XCtsuCHceCMcWTWXy9Sp8H/+D4yr+/Ce7uKWl1lt9WbYOK5F9bBhFNlt2EnXvA4+GM48\nE6qnfP7gB+GMM2CT0j2NbWw8YMOsNj+mrsP1yn1eU6fCP/3Tq5efckq6ebnXwssDNsxq67HOmPLp\nlaHyw5kypTdn3nC3oVltDq8O1yvdhsPp5fByt6HZ8BxeHa5Xug2H06vh5W5Ds9ocXh2u6G7DTg+v\nyZN7M7zcbWhWm8Orw1WepFwEX/PqXO42NKvN4dXhin4kSqe3vHo1vNxtaFabw6vDFRVe69alX5CT\nJzd/283Uq+HlbkOz2hxeHa6obsOVK1MwSPXLtlOvhpenhzKrzeHV4YpqeZWhyxB6N7zc8jKrzeHV\n4YoKrzKMNITeDi+3vMyG5/DqcEV1Gzq8OpsHbJjV5vDqcEW2vDp9mDz0bni529CsNodXh/M1r94N\nL3cbmg3P4dXhKt2G1Y8KGSt3G3Y2dxua1ebw6nAbbJAexNjspwy727CzudvQrDaHVwkUMTmvW16d\nzd2GZrX5YZQlMH06bLpp87d7xhnN32az9WJ4RfgmZbN6HF4lcN997a5B+/RieK1dm7qKN/D/nWbD\ncrehdbReDC+3uszqc3hZR+vF8PJgDbP6HF7W0SZNSr/MX3653TVpHQ/WMKvP4WUdbdy4FGAvvNDu\nmrSO7/Eyq8/hZR1v8uTe6jp0t6FZfQ4v63i9dt3L3YZm9Tm8rOP1Wni529CsPoeXdbxeCy93G5rV\n19LwkvQxSXdIWp695kl6d279eZJernrNq9rGRpLOlvSUpAFJl0maXlVmM0kXSFqWvc6XtEmrjtOa\nqxfDy92GZrW1uuX1GPA54K3ATOA64L8kvTlbH8DVwNa517urtnEWcDhwJLAfMBW4QlL+WC4E3gIc\nDBwC7AFcUMDxWAv0Wni529CsvpZOQBMRv6padKqkjwB/CdwBCFgdEUuH+nzWejoeOC4irs2WHQMs\nBA4E5kqaQQqtfSLi1qzMicBNknaKiAcKOLSu0N/fT19fX7ur8SpTpsB//zcsHfKsKMb99/ez8859\nrdthzm23dVZ4dep50Q7+LjpH22ZPkzQe+EdgInBjtjiAfSUtAZYBNwBfjoinsvUzgQnA3Mp2ImKR\npHuBWdnyWcBARMzP7W4esDJb5/AaRqf+j/m+98EVV8Att7Run7ff3s9zz/W1bodVjjiibbt+lU49\nL9rB30XnaHl4SfpzYD6wEfAicERE3J+tvhL4JfAwsAPwNeA6STMjYjWpG3FdRDxTtdkl2Tqyf5/K\nr4yIkLQ0V8ZK5D3vSa9Wmj07vcysM7Wj5XUf8BfAJqSW139K2j8ifhcRF+fK3S1pAalL8FDg0hrb\nVGG1NTOzjqNo9vPlR1oB6WpgUUR8YJj1DwH/HhFnSDoAuAbYMt/6knQ3cElEzJF0PHBWREzNrRfw\nPPDxiPhJ1fbb+wWYmZVURLSt4dAJTwwazzCjHiVtCUwHnswWLQDWAAcBF2VltgV2IV3XgtQlubGk\nWbnrXrOAKbkyr2jnl29mZqPT0paXpG8CVwCLgNcAR5GGzh9CCpY5wC+AxcD2wDdI4TUjIlZm2/g3\n4DDgOOBZ4NukLsiZkR2MpF8D2wIfJnUpngs8FBF/14LDNDOzgrW65TUN+Clp4MRy0vD4QyLiakkT\ngd2BY4BNSa2t64D3VoIrczKwFrgYmETqRjw6BqfwUcDZwFXZ+8uAjxd1UGZm1lptv+ZlZmY2Uj09\nt6Gkj0p6WNKLkn4nad9216lRkmYPMZXWE0OUeVzSC5Kul7Rr1fqmTLUlaTtJl2fbeErSdyVNKPDY\n3yHpV5IWZcd97BBlOubYJf25pBuyuiyS9JVWfRetnHKtnd+FpC9K+h+laeeWZt/JbkOU6/rzopHv\noivOi4joyRfwT8Bq4IPAzsD3gBXA69tdtwbrPxu4B9gq99oit/7zpBGWfw/sRupmfRzYOFfm37Nl\n7yRN2XU98HtgXK7Mb4C7gLcDewF/BH6VWz8+W38daUquA7Ntfq/AY38X6R7AfyDdfP7+qvUdc+yk\n6csWA/8J7JrV+XnglBZ9F/9B6j7PnyebVpUp/XdBukf02Gy7uwP/l3TpYbNeOy8a/C5Kf1609Bdu\nJ72AW4FzqpY9AHy93XVrsP6zgbuGWafsZP1ibtnE7IT4cPZ+E+Al4H25MtsC64CDsvczgJeBWbky\n+2TL/ix7/67sM9NzZf6ZdAP6xmM9zga+hxXkfmF32rEDHyHNFrNRrsyXSbeHFPpdZMvOAy6v8Zlu\n/S6mkK6NH+rzYvB30S3nRU92G0rakDRZ79yqVXOBvVtfo1HbMesCeUjSRZJ2yJbvQBock59GaxVp\nGq7K8Q051RZQmWoLak+1tXeuzD0R8XiuzFzSDCozx36II9Zpxz4LuCkiXqoqs42kN4zyGEfilSnX\nJN0v6VylW1AquvW7mEq6LPJc9r6Xz4vq7wK64LzoyfACXktqzi6pWl6mKaRuIXUNHAycQKr3PEmb\ns/4Yah3fqKfaGmI71ft5mvTXVju+y0479qHKLMmtK9qVpBG8BwCfJk2CfV32B1ylDt34XXyX1MVV\n+cXay+dF9XcBXXBedMJNyjYKEXFl7u0fJc0nzQl5LKlLdNiP1tn0aG7aLsuN3u049rYO543WTrnW\nEd+FpG+T/vLfN/tlWk/XnhfDfRfdcF70asurkvzTqpZPY/1sHqUSES8AdwNvYv0xDHV8i7OfFwPj\nJW1Rp0y+K6Ey1dZWVWWq91Np2S6m9Sr77JRjX8yr/3qcllvXUhHxJGmSgDfl6tA134Wk75AGYx0Q\nEY/kVvXceVHju3iVMp4XPRlekWaoX0CaZirvrxliCqkyULrJewbwZEQ8TPqPflDV+n1Zf3z5qbYq\nZYadaiu3q+qptuYBM6qG0P416WLvgqYc3Mh02rHPB/aTtFFVmccjYuEoj3HUVHvKtUqZUn4Xkr7L\n+l/W1Y8+6qnzos53MVT58p0XzR7ZUpYXcET2BX6Q9Ev/u6SRR2UZKn8m8A7Shei3k6bdWlapP2na\nrWWkYcG7k4ahLgKm5Lbxb6SnW+eHwt5OdvN6VubXwJ2kYbCzSMNeL8utH5etv5b1Q2EXAd8t8Nin\nZPt6C+ni8Feynzvu2EkXy58kzcW5G+kp4MuBTxX9XWTrzszqvz3QR/pF8Wi3fRfA97Nt7c/gJ7Hn\nj7Mnzot630W3nBdt/yXczhdpiObDwCrgf0j9wm2vV4N1v4h0v8RL2cnwc2CXqjKnAU+QhqVeD+xa\ntX5D0v1tT5N+8V1GbkhrVmZT4ILsZFoOnA9MrSrzeuDybBtPA2cBEwo89j7ScNyXSd2/lZ9/3InH\nTvpFeUNWl8eBr7TiuyANBb+SdPH7JeCRbHn1cZb+uxji+Cuvr3bq/xPt+i665bzw9FBmZlY6PXnN\ny8zMys3hZWZmpePwMjOz0nF4mZlZ6Ti8zMysdBxeZmZWOg4vMzMrHYeX9QSlJ+jeNdx7Gz1J/ZK+\n1+56WG9xeFkp5R5j/sMh1v1rtu7y3OIzSNNp9aQsYM4uaPPvAb44wvq8LOnwgupjPcDhZWUVpHnX\njpA0ubJQ0gbA+0nztOUfAbEyIp571VZszCJiWUSsHMVHy/IoHetADi8rszuBB0mTLFccSpofrZ/c\nL8dGugklfUDSPZJezJ4ue3L2iIfK+lMk3SFpQNIiST+QtEnVNo6X9KiklZIulfQRSS9XlTlM0oJs\nPw9J+pqkCXXqtpek67J9L5N0raTXZete1arKWqaXV34mtTo/lrV41knaTlJf9v5QSX/I6vM7SXtU\nbetwSXdJWpUd25eq1g/av6RHJH1Z0jmSlkt6TNJn8uuzH3+e7f+hWsduNhSHl5Xdj4Djc++PJ00y\nOqJJOyWdAPwLcCrpsQ+fBj4PfDRXbB3wSWBX4CjS02fzv7RnAT/Ilr0Z+G9gTr4ukg4Gfkqa8HTX\nrL7vBb5eo25vJk0i+wDpwYJvBy5k/cNkY4jjzS87iTRr+I9Js4u/jjSZc8WZwGeBtwEPAVdImpTt\neyZwCfAL0uSpXwC+KOnjw+yr4lPAHaTZyP8VOF3SXtm6t2X/fiirz57DHbvZsJo1u7VffrXyBZwH\n/Io0q/ULwBtJvwhXAdtm6y/PlZ8N3FXj/aPAP1ft42Tg7hp1OARYlXt/EfDrqjLnAC/n3t8IfLmq\nzHuAFTX28zPg5hrrrwe+N8T3c3mdMn2k2cbfl1s2BXgO+GBu39dUfe404LHhtk2apfxnVZ95IH/c\n2X4Pb/d55Fd5X255WalFxDLSY8s/CBwLXB8Ri2p/arDsQXzbAudKWlF5Ad8AdsyVO0DS1Vk32PPA\nL4EJkipPgd0ZuK1q89XvZwKnVu3nZ8BkSdVPnK14C3DdSI5phOZXfoh07eou0jPuyP69uar8zcB0\nSRsPs70gdenmPUHVU3fNxmKD+kXMOt6PSc8RWkF6GONIVf6IO5FhnqQt6Q2kbsBzSF2Lz5CC6CLS\nc48aJVKr7+dDrHu6zueG8/IQ62teQ6sjv62ose9aXbNrhijrP5ataRxeVmYCiIhrJb0EbAH810g3\nEhFLJD0BvCkifjpMsbeRAuFTEREAkv62qsx9pOtgedXvbwdmRMRIBin8HjigxvqngG2qlr2ZdP2q\nYjXD//8+i9TVh6QppKfZnpetuxfYp6r8vqRuw9GMMKxYA4wfw+etxzm8rFv8BUBEVP/F36jTgLMl\nLQN+QwqqPYBtIuKbpFGN44BPSbqU9NjzT1Zt43vAb7ORdZeRRvi9h8EtlP9FGhCxkNT6WksaCLFn\nRHx+mLqdAdwi6RzSI95fAvYDroqIx0hdimdJOox0belEUjdoPrweAf4ya0GuJLUcK74s6SnSo9i/\nmm3/wmzdt4D/kXQaqZW5J3AKg+/rEvWHvVeXeQQ4UNJNwEvh2xhshNyMt7IaNMItIgYiYmC49fXe\nR0Rl1OIxwB9IAys+RBYAEXEnKaxOAe7Oyn6mahu3ACeQRvfdAfwdcDopDCpl5pKG8+8P3Jq9Pgcs\nHPZAI+4ADiSNgrwlex1Bak1B6jatvH5Lehz7pVWbOTMrfw/p8e+vz637AimkFpAGvvxNRLyY7fv3\nwD8C/0C6FvZ14BsR8f18FandhThUmU+TvoNHs/2ajYiyHhAzK4Ck7wAHRMSb212XapL6SK2210bE\ns22ujtmIuNvQrIkkfRa4GhggtZZOZIRTJ5lZfQ4vs+aaSeoS24TU5fiFiOjkSWvd9WKl5G5DMzMr\nHQ/YMDOz0nF4mZlZ6Ti8zMysdBxeZmZWOg4vMzMrHYeXmZmVzv8HGwguFRNCXX8AAAAASUVORK5C\nYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x172ddef0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plot mileage cutpoint (x-axis) versus RMSE (y-axis)\n",
    "plt.plot(mileage_range, RMSE)\n",
    "plt.xlabel('Mileage cutpoint')\n",
    "plt.ylabel('RMSE (lower is better)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Recap:** Before every split, this process is repeated for every feature, and the feature and cutpoint that produces the lowest MSE is chosen."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building a regression tree in scikit-learn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# encode car as 0 and truck as 1\n",
    "train['vtype'] = train.vtype.map({'car':0, 'truck':1})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# define X and y\n",
    "feature_cols = ['year', 'miles', 'doors', 'vtype']\n",
    "X = train[feature_cols]\n",
    "y = train.price"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DecisionTreeRegressor(criterion='mse', max_depth=None, max_features=None,\n",
       "           max_leaf_nodes=None, min_samples_leaf=1, min_samples_split=2,\n",
       "           min_weight_fraction_leaf=0.0, random_state=1, splitter='best')"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# instantiate a DecisionTreeRegressor (with random_state=1)\n",
    "from sklearn.tree import DecisionTreeRegressor\n",
    "treereg = DecisionTreeRegressor(random_state=1)\n",
    "treereg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2928.5714285714284"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# use leave-one-out cross-validation (LOOCV) to estimate the RMSE for this model\n",
    "from sklearn.cross_validation import cross_val_score\n",
    "scores = cross_val_score(treereg, X, y, cv=14, scoring='mean_squared_error')\n",
    "np.mean(np.sqrt(-scores))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What happens when we grow a tree too deep?\n",
    "\n",
    "- Left: Regression tree for Salary **grown deeper**\n",
    "- Right: Comparison of the **training, testing, and cross-validation errors** for trees with different numbers of leaves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Salary tree grown deep](images/salary_tree_deep.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **training error** continues to go down as the tree size increases (due to overfitting), but the lowest **cross-validation error** occurs for a tree with 3 leaves."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tuning a regression tree\n",
    "\n",
    "Let's try to reduce the RMSE by tuning the **max_depth** parameter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3757.936507936508"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# try different values one-by-one\n",
    "treereg = DecisionTreeRegressor(max_depth=1, random_state=1)\n",
    "scores = cross_val_score(treereg, X, y, cv=14, scoring='mean_squared_error')\n",
    "np.mean(np.sqrt(-scores))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or, we could write a loop to try a range of values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# list of values to try\n",
    "max_depth_range = range(1, 8)\n",
    "\n",
    "# list to store the average RMSE for each value of max_depth\n",
    "RMSE_scores = []\n",
    "\n",
    "# use LOOCV with each value of max_depth\n",
    "for depth in max_depth_range:\n",
    "    treereg = DecisionTreeRegressor(max_depth=depth, random_state=1)\n",
    "    MSE_scores = cross_val_score(treereg, X, y, cv=14, scoring='mean_squared_error')\n",
    "    RMSE_scores.append(np.mean(np.sqrt(-MSE_scores)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x17514c88>"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAZkAAAEZCAYAAABFFVgWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3XeclNXZ//HPV0SwYYwFCxasWFAUjSBqsMSgseQxttj1\nsYToz2jioz4aI5qisWIw9opG0cQoERvw6NrAqAQbig0QSxRsKHbg+v1x7tFxsuzOsjN7z85+36/X\nvHbmvs/cc00we+25zznXUURgZmZWDQvlHYCZmdUvJxkzM6saJxkzM6saJxkzM6saJxkzM6saJxkz\nM6saJxkzM6uaNksyko6W9LSkWdljnKSdi853k3SJpNclfSppsqTjSq7RRdIwSTMlzZY0UtLKJW2W\nlnSDpA+zx3BJS7XV9zQzs2+0ZU/mdeBEYBOgL3A/cIekjbPzQ4EfAgcAvYDfA2dLOqDoGkOBPYB9\nga2BbsAoScXf4yagT3atQcCmwA1V+k5mZtYE5bniX9J7wMkRcaWkZ4G/RcQZRecbgGci4tisNzID\nOCQibs7O9wBeA3aKiNGS1gMmAQMiYnzWZgDwMNArIl5qy+9nZtbR5TImI6mTpH2BrsBD2eF7gN2y\nxIGkLUk9knuz832BzsDownUi4g3gBaB/dqg/MLuQYDLjgE+K2piZWRtZuC0/TFJvYDzQBfgM2Dsi\nXsxOnwQMB6ZLmpMdOyYi7s6erwDMjYj3Si77Tnau0GZm8cmICEkzitqYmVkbadMkA0wGNgKWAvYC\nRkjaNiKeBM4DtgB2Jd0C+z5wvqTXIuK+Jq6p1gQkyRVCzcwWQEQ0+/u3TW+XRcRXETElIiZGxCnA\nY8DRkhYDfgH8KiLuiojnIuLPwAjghOztbwOdJC1Tctnu2blCm+WKT0oSsHxRm8biqtvH6aefnnsM\n/m7+fv5+9fcoV97rZDplMSh7zCs5P49veioTgK+AHQsns/GbXqRxF0i34paQVDz+0h9YvKiNmZm1\nkTa7XSbpbGAU8AawJLAf6ZbYoIj4RNL/kaYszwamZ+cOBP4HICJmSboaOCcbY3kfuAB4GhibtXlB\n0r3A5ZKOJCWoy4E7I+LltvquZmaWtOWYTHfgRtIA/CxSchgUEWOy8/sDZ2VtlgGmAb+OdNus4Dhg\nDnALsCgpuRwQ3+677QcMAwrjOCOBY6rwfdqFgQMH5h1C1dTzdwN/v/au3r9fuXJdJ1MLJEVH/9/A\nzKylJBG1NvBvZmYdi5OMmZlVjZOMmZlVjZOMmZlVjZOMmZlVjZMM8NVXeUdgZlafnGSAkSPzjsDM\nrD45yQCXXpp3BGZm9clJBpg0CV58sfl2ZmbWMk4ywGGHwWWX5R2FmVn9cVkZKaZODTbbDKZPh8UW\nyzsiM7Pa57IyLbD66tCvH4wYkXckZmb1xUkmM3iwJwCYmVWak0xm0CCYOROefDLvSMzM6oeTTKZT\nJzjqKPdmzMwqyQP/RfvJzJgB664LU6bA0kvnHJiZWQ3zwP8CWH75dNts+PC8IzEzqw9OMiUGD05r\nZjp4B8/MrCKcZEpsvXUan2loyDsSM7P2z0mmhOTpzGZmleKB/6KB/4KPPoLVVoPnn4cVV8wpMDOz\nGuaB/1bo1g323huuvjrvSMzM2jf3ZBrpyQA89RTsthtMnZrGaMzM7BvuybRSnz6w8spw1115R2Jm\n1n45yTTBEwDMzFrHt8vmc7sM4PPPYZVV4LHHYM012zgwM7Ma5ttlFdC1Kxx8MFx+ed6RmJm1T+7J\nNNGTAXj5ZRgwIG1o1rVrGwZmZlbD3JOpkLXXTpMA/va3vCMxM2t/yk4yklaQtLWkXSRtJWmFagZW\nSzwBwMxswTR5u0xSD+Bw4KfA2o00eRm4GbgqIt6oSoRV1tztMoA5c9IWzXffDRtt1DZxmZnVslbf\nLpN0IfA8sBlwHrApsCywSPazL3ABsDnwvKQLKhB3TVp4YTjiCPdmzMxaar49mSxpnBMRbzd7EWlF\n4ISI+FWF46u6cnoyAG++CRtumCYALLlkGwRmZlbDyu3JNDu7TNJCQC9gekTMrlB8NaPcJAOw556w\n/fZpjMbMrCOr9Oyyp4FWDfRLOlrS05JmZY9xknYuabOOpL9L+kDSJ5ImSOpVdL6LpGGSZkqaLWmk\npJVLrrG0pBskfZg9hktaqjWxFxQmAHTwWd9mZmVrNslExDzgRWC5Vn7W68CJwCak8Zz7gTskbQwg\nqSfwKPAqsC2wAXAqUNx7GgrsAewLbA10A0Zlva2Cm4A+wA+BQaSxpBtaGTsA220HX3wB48ZV4mpm\nZvWvrMWYknYCfg0cAzxV9v2l5q/7HnByRFwp6SZgbkQcOJ+2SwEzgEMi4ubsWA/gNWCniBgtaT1g\nEjAgIsZnbQYADwO9IuKlRq7boq9z4YUwYQLceGOLvqqZWV2p9O2yW4HvAROALyR9XPT4aAGC6yRp\nX6Ar8FDWE9kFeEHSvZJmSHpc0t5Fb+sLdAZGFw5k06ZfAPpnh/oDswsJJjMO+KSoTascfHCqzDxz\nZiWuZmZW3xYus93/q8SHSeoNjAe6AJ8Be0fEi9nCziWAU0g9phOB7YG/SJodEXeTxoTmRsR7JZd9\nh2/Gi1YAvvXrPyJC0gxaOaZU8N3vwo9/DNdeCyeeWIkrmpnVr7KSTERcV6HPmwxsBCwF7AWMkLQt\n8FZ2/o6IGJo9f0bSZqRbdHc3cc1mu2vNGTJkyNfPBw4cyMCBA5tsP3gw7LsvnHACLOTCPGbWATQ0\nNNDQ0NDi95VdIDPrbRwIrAGcFhHvStoKeDMiprb4k9M1xwBvAEeSbmkNiYg/FJ0/DdgnIjaUtB0w\nFliuuDcjaRJwa0ScIekwYGhEdCs6L+Aj4JiIuL6RGFo8xBQBm20Gv/sd7LRTi95qZlYXKjomI6kv\naYbZfqQyM4Vf4j8Afr+gQQKdgIUi4ivgCdJ6nGLrANOy5xOAr4Adi+Lqkb2nMN9rPLCEpOLxl/7A\n4kVtWk1yPTMzs3KUO7usAXgoIn4j6WNg44iYkv0yvyUiVi3jGmcDo0g9lyVJCetEYFBEjJG0O2mC\nwTHAA6RpzH8Gdo+Ie7JrXALsChwCvE8qa7MU0LfQHZF0N9CD1DsScAUwJSJ2n09cCzRZ7pNPYNVV\nYeLE9NPMrCOp9OyyTYHrGjn+NtC9zGt0B24kjcuMJc0WGxQRYwAiYiQpMZwAPAMcDRxYSDCZ44Db\ngVuAR0i3wXYtyRL7kRaP3gfcC0wk3earqMUXh/33hyuuqPSVzczqR7k9mXeAH0XEkyU9mUHAlRGx\nSrUDrZYF7ckAPP98KjPz2muwyCIVDszMrIZVuiczEjhd0td7Q2Yr9M8BbluwENu/9deHddeFO+7I\nOxIzs9pUbpL5H2Bp0hqUxUi3ql4BPiSta+mwPAHAzGz+WjKFWaTB+L6k5DQhIsZWMbY20ZrbZQBf\nfgmrrQb33w/rrVfBwMzMaljFSv1nFzuItBbl85LjiwD7RsTwBY40Z61NMgC//jV8/DFcdFGFgjIz\nq3GVTjLzgBUiYkbJ8WWBGRHRbte9VyLJTJ8Om2ySfi6+eIUCMzOrYZUe+J+fVUjjMh3aqqvCgAEw\nYkTekZiZ1ZYmezKSns2ebkBa8T+n6HQnYDXg7ojYq2oRVlklejIA99wDp50GTz5ZgaDMzGpcRW6X\nSRqSPf0NcD6pvljBl8BU4LaI+HLBQ81XpZLMvHmw1lpwyy2w+eYVCMzMrIZVekzmYFL5mM+bbdzO\nVCrJAPzxj/Dii3DNNRW5nJlZzap0kpkKbFa6l4ukpUlTmddY4EhzVskkM3MmrLMOTJkCSy9dkUua\nmdWkSg/8r0YagynVhVSM0oDlloOdd4brrss7EjOz2tDcmMwepErGfyWV+C+eSdYJ2AHYNiLWqWaQ\n1VTJngzAI4/Af/83TJ6ctgQwM6tHlRr4n9fEe78i7fXyq4gY1eIIa0Slk0wEbLQRDB2aimeamdWj\nitwui4iFsoWW04HlC6+zR5eIWLc9J5hq8IZmZmbfKLt2Wb2qdE8G4KOPUj2zSZNgpZUqemkzs5pQ\n6e2XJeloSZMkfSZpjez4yZL2bm2w9aZbN9hnH7jqqrwjMTPLV7mzy35BKul/Zcnxt0jbJVuJwYPh\nyithzpzm25qZ1atyk8xg4IiIGMq3S8v8C9iw4lHVgY03TjXNRnnEysw6sHKTzKrAs40c/wpYtHLh\n1BdPADCzjq7cJDOVtFlZqZ2A5ysXTn3Zc0+YOBFeeSXvSMzM8lFukjkXuFjS/tl7tsyKZ/4hO2eN\n6NoVDjkELr8870jMzPLRku2XjwBO45syMm8Bp0fE1VWKrU1UYwpzsVdfhX794PXXU9IxM6sHFS2Q\nWXLh5YCFIuKdBQ2ullQ7yQAMGgT77w8HHljVjzEzazNV2RlT0prAFsDm2XMrgycAmFlHVW6p/2WA\na4BdgUI9s4WAUcChpVsAtCdt0ZOZMwd69oQ774Q+far6UWZmbaLSPZmrgDWBrUlTlhfNnvfMzlkT\nFl4YjjzSvRkz63jK7cl8CuwQEeNKjvcH/i8iFqtSfFXXFj0ZgH//G9ZfH157LZWdMTNrzyrdk3kX\n+KSR459m56wZK64IO+wAN9yQdyRmZm2n3CRzJnChpK93wcyeX5CdszIUJgB08MLXZtaBzPd2maTS\nMjKrk8Zi3sxerwx8BkyNiI2qFWC1tdXtMkjJZb31UuHMrbduk480M6uKcm+XLdzEudvK/Cz/XV4m\nCX72s9SbcZIxs47Am5a1YU8G4IMPYI014MUXYfnl2+xjzcwqqiqLMa31ll4a9tgDrrkm70jMzKqv\nzZJMtrPm05JmZY9xknaeT9vLJc2T9KuS410kDZM0U9JsSSMlrVzSZmlJN0j6MHsMl7RUNb9bSw0e\nnIpmzp2bdyRmZtXVlj2Z14ETgU1I2wbcD9whaePiRpL2BDYnFeAsvY81FNgD2Je0GLQbMEpS8fe4\nCegD/BAYBGwK1NTE4c02g2WXhfvuyzsSM7PqynVMRtJ7wMkRcWX2ejXgUWB74F5gWERckJ1bCpgB\nHBIRN2fHegCvATtFxGhJ6wGTgAERMT5rMwB4GOgVES81EkObjskUXHMN3H57KjVjZtbeVH1MRlLn\nVry3k6R9ga7AQ9mxhYGbgd9GxIuNvK0v0BkYXTgQEW8ALwD9s0P9gdmFBJMZR1pI2p8asu++MH58\nqgBgZlavykoykn6R3cYqvL4G+FzSS5LWLffDJPWWNBv4HLgC2LsooZwBzIiI+W3xtQIwt5FinO9k\n5wptZhafzLopM4ra1ITFFoMDDoArrsg7EjOz6im3J3Ms2S9vSdsAewH7AROB81vweZOBjYDvARcD\nIyRtJmkgcDBweEn7ZrtiZbapST/7GVx9NXz5Zd6RmJlVR1OLMYutBEzJnu8K/C0ibpH0DPBIuR8W\nEV8VXWeipM2Bo4FpwIrAv6Wvc0Yn4I+SfhERqwJvA50kLVPSm+kOPJg9fxtYrvgzlS64fHauUUOG\nDPn6+cCBAxk4cGC5X6lVevVKRTNvvx322adNPtLMbIE0NDTQ0NDQ4veVW4X5HeBHEfGkpKeA8yLi\nRklrA09FxOIt/uR03ftJs85+RUoEX58C7iPNFLsyIl5uZuB/UESMmc/A/5akRLhuRLzcSAy5DPwX\n/PWvcPHF8OCDzbc1M6sVlSgrU2w0cKWkfwFrAfdkx9cHppYZ0NmkTc7eAJYk3W77PilBvEtJNWdJ\nXwFvFxJDRMySdDVwjqQZwPukAp1PA2OzNi9Iuhe4XNKRpGR1OXBnYwmmFvz4x3DssTBpEmywQd7R\nmJlVVrljMseQegPLAnsW3a7qS+ptlKM7cCNpXGZs9t5BETGm/HA5DrgduCWL5yNg15KuyH6kxHMf\naRr0RODAFnxGm+rcGQ4/HC67LO9IzMwqz7XLcr5dBvD667DxxjB9OiyxRK6hmJmVpdXrZCR9t/h5\nU49KBd1RrbJKqsp88815R2JmVllN7SczD1ghImZkz+cnIqJTVaJrA7XQkwG491445RSYMCFtCWBm\nVsvK7ck0lWQGAo9GxFfZ8/mKiIYFiLEm1EqSmTcP1l4bbroJttgi72jMzJrW6iTTUdRKkgE499w0\ny+y66/KOxMysaU4yZaqlJPPuu6k38+qr8F2PdJlZDfOmZe3QssvCLru4J2Nm9cM9mRrqyQCMGweH\nHAKTJ8NC/hPAzGqUezLtVP/+sOiicP/9eUdiZtZ6zSYZSYtIeluSi560ASltz3zppXlHYmbWes0m\nmYj4EpjDf26FbFWy//7wwAPw5pt5R2Jm1jrl3i4bBvxva3bDtPItuWTaOfPKK/OOxMysdcot9X8n\nqWLyZ8BzwKdFpyMidqtOeNVXawP/Bc8+C4MGwbRpqYimmVktqXSp//eAv8/nXO39hq4DvXtDz55w\n552wxx55R2NmtmA8hblGezIAf/lLWjMzpiWbIZiZtYGKr/jPtjHuC6wJ3BURsyUtAXyRbavcLtVy\nkvnii1Sh+dFHUyUAM7NaUdF1MpK6A+OBx0mblBW2Sj4fOG9Bg7SmdekChx7qDc3MrP0qd3bZhcAM\nYBm+Pej/V+CHlQ7KvnHUUTB8OHz2Wd6RmJm1XLlJZnvglIj4oOT4FGDVyoZkxdZYAzbfHG69Ne9I\nzMxartwksyjQ2LjLssDnlQvHGuMKAGbWXpWbZB4GDik+IGlh4CTg/yock5XYeWf4979h4sS8IzEz\na5lyF2OuDzwEPAVsA4wCNgSWAgZExCvVDLKaanl2WbHf/x5eew2uuCLvSMzMqjOFeUVgMGkas4B/\nAX+OiH+3JtC8tZck8/bbsN56qQLAUkvlHY2ZdXTeGbNM7SXJAOyzD2y9NRxzTN6RmFlHV+l1MmMk\nnSJpy2wsxnJQmADQTnKimVnZA///BHYG7gc+lDTaSaftff/7KcE8/HDekZiZladFt8skLQZsSarI\nPBDoB3weEUtWJbo20J5ulwH86U9pi+YRI/KOxMw6smptv7wkaW3M8sAKpM3Mnmx5eLagDjoI7rsP\n3nkn70jMzJpX7pjMpZJeAKYCRwFvAYcDS0fEtlWMz0p85zvwk5/A1VfnHYmZWfPKXSczD3gXuBi4\nB5gQEfOqHFubaG+3ywAmTEh7zEyZAp065R2NmXVElb5dtg5wSvbzNuB9SXdK+qWkTVsRpy2Avn2h\ne3e45568IzEza9oCrZOR1As4ETgA6BQR7fbv6fbYk4G0mdlf/wp33ZV3JGbWEVV0MaakhYDNgO1I\ns8oGAF2ACUBDRPxvq6LNUXtNMp99ljY0e+KJtE2zmVlbqnSS+QjoSpZUgAeBRyJidivjzF17TTIA\nv/xl2tjsrLPyjsTMOppKJ5lB1ElSKdWek8xLL6UyM9Onp2RjZtZWKjrwHxH3RsRsSV0lbShpA0ld\nWxjQ0ZKeljQre4yTtHN2bmFJf8zOz5b0lqS/SFql5BpdJA2TNDNrN1LSyiVtlpZ0g6QPs8dwSXVZ\nUnKddaB3b/j73/OOxMysceWuk+ks6TzgQ+AZ4FlSeZlzJXUu87NeJ00W2IRUyfl+4A5JGwOLZcd/\nl/3cHVgFuFdS8aSCocAewL7A1kA3YFQ2ZlRwE9CHtC30IGBT4IYyY2x3vKGZmdWycm+XXQD8FDgZ\neDQ7vBVwFnBTRPxqgT5ceg84OSKubOTcesAkoHdETMp6IzOAQyLi5qxND+A1YKeIGF30ngERMT5r\nM4C06VqviHipkc9pt7fLAL76ClZfPVUB2HDDvKMxs46i0utk9gMOj4jrI+KV7HEdadX//gsQXCdJ\n+5ImEzw0n2aFW1wfZD/7Ap2B0YUGEfEG8ALQPzvUH5hdSDCZccAnRW3qSufOcPjhcNlleUdiZvaf\nyk0ySwGN7X45BfhOuR8mqbek2cDnwBXA3hHxYiPtFgHOB/4REW9lh1cA5kbEeyXN38nOFdrMLD6Z\ndVNmFLWpO0ccATfdBLPrblqGmbV35Zbpfwb4BfDzwgFJAo4lbclcrsnARqSktRcwQtK2EfF1kc1s\n64AbSeMtu5RxzWa7a80ZMmTI188HDhzIwIEDW3vJNtWjR9oG4Kab4Mgj847GzOpRQ0MDDQ0NLX5f\nuWMy25Bqlr0BPEb6xd4PWIk0HrJAO5xIGgO8ERGHZq8XBm4GNgAGRsSMorbbAWOB5Yp7M5ImAbdG\nxBmSDgOGRkS3ovMCPgKOiYjrG4mhXY/JFIweDSeeCBMnglqdds3MmlbpKcwPkeqW/Y1U7n9x4FZg\nnQVNMJlOhRiyWWq3ABsC2xYnmMwE4Ctgx8KBbOC/F2ncBWA8sISk4vGX/lm846hjO+yQbpc99lje\nkZiZfWOBapct0AdJZwOjSL2hJUmTCU4kTTO+n1R4czNgV+DfRW/9MCI+z65xSXb+EOB94ALSrbe+\nhe6IpLuBHsCRpB7XFcCUiNh9PnHVRU8G4Lzz4JlnYPjwvCMxs3rX6hX/LamuHBH/KiOga4FtSQPw\ns4CngXMjYoyk1UmTCIL/HGM5JCKGZ9dYBDiPlKAWJd0++3lEvFn0Od8BhgG7ZYdGkm6VfTSfuOom\nybz3Hqy5Jrz6KiyzTN7RmFk9q0SSKXe/mHAV5tpx0EGw0UZwwgl5R2Jm9awSSWb1cj8sIqaV27bW\n1FuSeewxOOCAVNdsoZZurm1mVqZyk8x8pzC358TRkW2xBSy5JIwdCzvu2Hx7M7Nqmu/fupLWaMmF\nWtreqkNyPTMzqx1N3S57mzSwfi1wf2P3lLI1KNsDhwLbR0S7W1Vfb7fLIE1lXnXVNNOsR4+8ozGz\nelSJdTLrAtNIVY1nSWrIyuZfkpXSf5A0S+wmYGrW3mrAEkvAfvvBlf9RdtTMrG01u04mmza8A7AN\nsDZpjcssUi2zh4GxEfFlleOsmnrsyQBMmgQ/+AFMngzdujXf3sysJSq6M2Y9q9ckA/Czn8H778Mt\nt7jUjJlVVqVL/Vs7NHRoWpj5pz/lHYmZdVTuydRxTwZg6lTo1w9uvx223DLvaMysXrgnYwD07AnX\nXAP77AMzSkuOmplVmXsydd6TKTj1VPjnP9M2zZ3abREgM6sV7snYt5x5JkRA0f5sZmZV12SSkfQH\nSYsXvd5Z0mJFr7tJcmH5dqBTp7Rz5rXXwt135x2NmXUUTd4uyyoxr1DYQEzSx8DGETEle70C8FZE\ntNseUUe5XVbwyCPwk5+kW2err553NGbWXvl2mTVqq63gpJNgr73giy/yjsbM6p2TTAd0/PGw2mrp\np5lZNTnJdEBSmtY8diz85S95R2Nm9Wy++8kUGZyNxQjoDPy3pPeyc66K1U516wa33QbbbQd9+sAG\nG+QdkZnVo+YG/qcBxQ3U2OuI6FmV6NpARxv4LzV8OPzhD/DEE2mzMzOzcrhAZpk6epIBOOoo+OAD\nF9I0s/J5dpmV7aKLXEjTzKqjucWYfSRtV3LsAElTJc2QdHm234y1Y127wt/+lm6bjRuXdzRmVk+a\n68n8Dtiq8ELS+sA1wEvACGA/4OSqRWdtxoU0zawamksymwCji17vC7wQET+MiGOB44C9qxWcta0f\n/QgOOiht3Tx3bt7RmFk9aC7JLAO8WfR6G+DOotcPAqtVOijLzxlnwLx5LqRpZpXRXJKZCawMIGlh\noC/wz6LziwDzqhOa5WHhheHmm11I08wqo7kk8yBwuqQ1gF+S1sU8UHR+PWBadUKzvHTvDiNGwKGH\nwrRpeUdjZu1Zc4sxewJjgDVIPZZjI+KSovMjgVcj4pfVDrRavE5m/i64IPVqHnkEunTJOxozqyUV\nW4wpqTOwATAzIt4sOdcHeD0i3mv0ze2Ak8z8RaRqzcsvD5dc0nx7M+s4vOK/TE4yTfvoI9hsMzj9\ndNh//7yjMbNaUZEkI+lXfLtWWaMi4oKWhVc7nGSa9+yzqZBmQ4MLaZpZUqkkMw94F/ikqYu4QGb9\ncyFNMytWqSTzT9J4zN+AqyPi4cqFWBucZMrnQppmVlCRApkRsQXQD/gAuE3Si5JOkrRCheK0dsSF\nNM2spZqtwhwRz0XE8UAP4FRgIDBN0j8kdS33gyQdLelpSbOyxzhJO5e0GSLpTUmfSnogq5VWfL6L\npGGSZkqaLWmkpJVL2iwt6QZJH2aP4ZKWKjdOmz8X0jSzliq71H9EfAncBlxIWvX/I6DsJAO8DpxI\nqofWF7gfuEPSxgCSTiIt+DwG2ByYAYyRtETRNYYCe5BqqG1N2plzlKTi73ET0Af4ITAI2BS4oQVx\nWhN69oSrr3YhTTMrT1lTmLNFmYcCB5NW/V8PXBMRU1v14Wkb55OBq4C3gD9FxFnZua6kRHNCRFyR\n9UZmAIdExM1Zmx7Aa8BOETFa0nrAJGBARIzP2gwAHgZ6RcRLjcTgMZkFcMop8PjjcN990KlT3tGY\nWVuryJhMtnfM/cDzQC/gKGC1iDitNQlGUidJ+5J6Qg8BPYHuFFV8jojPs3NbZof6Ap1L2rwBvAD0\nzw71B2YXEkxmHGl2XH+sYs4804U0zax5CzdzfjjpNtdQ0lTm9YH1VTK1qNx1MpJ6A+OBLsBnwN4R\n8aKkQiJ5p+QtM4CVsucrAHMbqS7wTnau0GZmSWwhaUZRG6uAQiHNvn2hf3/Yeefm32NmHU9zSWY6\naTHmvs20K3cx5mRgI2ApYC9ghKRtm3lPc/eyWj2ZdkjRn+MDBw5k4MCBrb1kh1AopPmTn8A//wmr\nr553RGZWLQ0NDTQ0NLT4fbmWlZE0BngDOBN4Fdg8IiYUnb8LmBERh2bbQI8FlivuzUiaBNwaEWdI\nOgwYGhHdis4L+Ag4JiKubyQGj8m0kgtpmnU8FRmTKfODWrPavxOwUDa+8zawY9F1u5K2fi5Mlp0A\nfFXSpgdprKjQZjywhKTi8Zf+wOJFbazCjj8eVlst/TQzK7bASUbSZpJuBf5jxtZ82p8taStJq0vq\nLeks4PvAjVmTocBJkv5L0obAdcDHpCnJRMQs4GrgHEnbS9qENDX5aVIPh4h4AbgXuFxSvyzZXA7c\nGREvL+h3taZJcM01MHYs/OUveUdjZrWkyTEZSSuSBv/7AU8Ae5JmgV0E7AD8CziozM/qTkooKwCz\nSMlhUESLrQS5AAAPlElEQVSMAYiIcyQtCvwZWBp4DNgxIorrph0HzAFuARYlJZcDSu537QcMA+7L\nXo8krb2xKurWDW67LRXS7NPHhTTNLGmudtn1wLbAX0kLG6eQeh9PAmdExINtEWQ1eUymslxI06xj\nqFSBzDeAQyNiTLYF8yvAsIj4ReVCzZeTTOW5kKZZ/avUwH930gp6ImIK8DlwZevDs3rmQppmVtDc\nOplOpDGQgrnAp9ULx+pBoZBmv36w+eaw5ZbNv8fM6lM5m5aNAb4gLXocBDxIWq1fEBGxWzWDrCbf\nLqueUaNg8GCYMAGWXz7vaMyskio1JnMdacV9UxeKiDi0xRHWCCeZ6nIhTbP6VJEk0xE4yVTXnDmw\n444wYAD89rd5R9M+RMA996Tk/N3vwjLLpJ+FxzLLwFJLOWlbvpxkyuQkU33vvJMKaV5xhQtpNiUC\n/vGPlIy//BJ22w1mzYL33oP330+PwvOPP05rkxpLQI09d3KySnOSKZOTTNt45BEX0pyfefPg739P\nyaVTJzjtNNh9d1ioibmfc+fChx82noAae+3kZJXmJFMmJ5m240Ka3zZ3Ltx6K/zud7DEEim5/OhH\n1V1b5ORkleIkUyYnmbYTAXvtlWaaXXJJ3tHkZ84cuOkm+P3vYdll4Te/SeNWtbxwtbHkNL+EVPy6\nqeTUtSWbt1vNOffc8pJMc+tkzCqmUEhzs81SIc399887orb15Zdwww1w1lnQowdceilsu21tJ5eC\nTp1SYlhmmZa9r6nk9MUX1YnVaot7Mu7JtLlnn02FNBsaOkYhzS++gGuvhbPPhrXXTrfFttkm76jM\nWqfN9pMxa6neveH889NEgI8/zjua6vnsMxg2DNZaK80au/lmGDPGCcY6Fvdk3JPJTb0W0vzkE7j8\ncjjvvFRW59e/Tj/N6ol7Mlbz6q2Q5scfwznnwJprwrhxcPfdMHKkE4x1bB74t9zUSyHNWbPg4otT\n0tx++7RD6IYb5h2VWW1wT8Zy1bMnXH017LMPzJiRdzQt88EHMGRI6rlMngwPPZTGXZxgzL7hJGO5\n22UXOPBA2G+/NOW11r37Lpx6ahrQnz4dHnssTU3u1SvvyMxqj5OM1YQzz0zlVYYMyTuS+XvnHTjx\nRFhnnZRonnwyrftZa628IzOrXU4yVhMWXjjdarr22jRgXkveeguOPx7WWw8+/RSefjrNHuvZM+/I\nzGqfk4zVjO7dYcQIOPRQmDYt72jg9dfhmGO+GWN57rk0wL/KKvnGZdaeOMlYTdlqKzjppFTjLK+y\nI9OmpTU8G28Miy0GL7wAF14IK62UTzxm7ZmTjNWc44+H1VZLP9vSK6/AYYelvW+WXRZeeimte+ne\nvW3jMKsnTjJWcwqFNMeOTYU0q23y5DS7rV8/WHVVePnlbyokm1nrOMlYTerWDW67DY47DiZNqs5n\nPPcc/PSnqZZYr16p+sCQIakUvZlVhpOM1azevVP9r0oX0nzqKdhzT9hhB9hkk5RcTj01bbBlZpXl\nApkukFnzjjwy7UnS2kKaTz6Ztjh+4gk44YQ0uL/44pWL06wjcYFMqxt/+lPrCmmOHw877wz/9V+p\n9/Lqq/DLXzrBmLUF92Tck2kXpk5NA/O3315+Ic2HH06VBF5+GU4+Oa2/6dKlunGadRTl9mScZJxk\n2o1Ro2DwYJgwAZZfvvE2EfDAA+m22PTpcMopaebYIou0baxm9c5JpkxOMu3LKafA44/DffelfecL\nImD06JRcZs5MA/n77ZfK1ZhZ5TnJlMlJpn2ZMwd23BEGDEgJJQLuuis9nz077UK5997fTkBmVnnl\nJhn/nWftSqGQZt++0Lkz3HFH2h7gtNNgjz1gIU9lMaspbfZ/SUn/K+kJSbMkzZD0D0kblLTpJukS\nSa9L+lTSZEnHlbTpImmYpJmSZksaKWnlkjZLS7pB0ofZY7gkr4KoE927p+nMDz4Ip58OEyemdS9O\nMGa1p81ul0m6F7gZeIKU3M4E+gPrR8QHWZtrgO8DhwFTs+dXAodHxI1Zm0uB3YCDgPeBC4DvAH0j\nYl7W5h6gB3A4IOAqYEpE7NZIXL5dZmbWQjW3TiYiBkXE9RHxfEQ8BxwILAcUT0jdHBgeEQ9GxPSI\nuAF4DPgeQNYbOQw4ISL+LyImZtfZCNgha7Me8EPgyIj4Z0Q8BhwF7CJpnbb5trWjoaEh7xCqpp6/\nG/j7tXf1/v3KlecNhm7Z539QdOweYDdJPQAkbQn0Ae7NzvcFOgOjC2+IiDeAF0i9IrKfsyNifNF1\nxwGfFLXpMOr5P/R6/m7g79fe1fv3K1eeA/8XAROB4mRwEjAcmC5pTnbsmIgo7JW4AjA3It4rudY7\n2blCm5nFJyMiJM0oamNmZm0glyQj6QLSbbKtSgZEzgO2AHYFXiONyZwv6bWIuK+pS1YtWDMzW3AR\n0aYP4ELgTWCdkuOLA3OAXUuOXwmMyZ5vB8wDlilpMwk4PXt+GPBRyXkBHwMHNxJP+OGHH3740fJH\nOb/z27QnI+kiYC9g24h4qfR09phXcnwe3/RUJgBfATuSZqqRjd/0Io27QLr9toSk/kXjMv1JSazQ\n5mvlzI4wM7MF05ZTmP8MHAD8mDRQX/BxRHyStRkNrAgcA0wn3S67BPifiPhz1uYS0u20Q/hmCvNS\npCnMkbW5mzSF+UhSgrqCNIV59+p+SzMzK9aWSWYeqYtV2nMYEhFnZm2WA84iTUFeBpgGXBURFxRd\nZxHS2M1+wKLAWODnEfFmUZvvAMNI62kARpImEHxU+W9mZmbz0+Frl5mZWfV0yEIckrbJytq8IWme\npIPzjqlSyinf055JOlrS09n3myVpnKSd846rGrJ/y3mShuUdS6VIGpJ9p+LHW3nHVSmSVpR0ffb/\nvc8kTZK0Td5xVYKkaY38282TNKqp93XIJEOaBPAM8AvgM9JtvHrxfeBi0mSH7Ugz9sZKWjrXqCrn\ndeBEYBPS4tz7gTskbZxrVBUmqR9wBOm/03r67xNgMmnNWuHRO99wKiO7Tf8o6d9rZ9KEpGOAGXnG\nVUF9+fa/26ak73pLU2/qkFWYI+IeUnUBJF2XbzSVFRGDil9LOhCYRVqXdFcuQVVQRPyj5NCvJQ0m\nlR56OoeQKi4rn3QjcCgwJN9oqmJuRNTLL95iJwJvRsQhRcdeyymWiitdBC/pCNLvllubel9H7cl0\nJI2V76kLkjpJ2hfoCjyUdzwVdAXw14h4kPpcaLyGpDclTZF0s6SeeQdUIT8GHpd0i6R3JE2UdHTe\nQVWDJAH/DdwYEV801dZJpv41Vr6nXZPUW9Js4HPSL+S9I+LFnMOqiOyvwzWAX2eH6u1W2WPAwaQZ\npEeQbruMk/TdXKOqjDWAnwOvkNbyXQScXaeJ5gfA6qTF8k3qkLfLOoomyve0d5NJlbeXIi3uHSFp\n24h4Mt+wWkfSusDvSf9ecwuHqaPeTETcW/TyOUnjSdt6HEyqBtKeLQQ8HhGnZq+flrQ2cDTw5/zC\nqoojSN/12eYaOsnUKUkXAnuTqitMyzmcioqIr4Ap2cuJkjYn/R/50Pyiqoj+wLLApHQ3AoBOwNaS\njgIWz7573YiITyVNAtbKO5YKeAt4vuTYZGDVHGKpGknLk9Yg/ryc9k4ydaiZ8j31qBP1cev3duDx\notcCrgVeAv5QbwkGQFJXYD3SLMH27lHSjLJi65AWldeTQ0i3qm8up3GHTDKSFgfWzl4uBKwmqQ/w\nXkS8nl9krVdSvmeWpML2Bl+X72nPJJ0NjALeAJYkVX74PjCoqfe1BxExizRb52uSPgU+iIjSv5Db\nJUnnAf8gTUVfHjiNVLnj+jzjqpALSeNLp5BmXG0C/D/gf3ONqoKyAf/DgRER8WlZ76mvW/XlkTSQ\nb/5yKi51c11EHJZLUBVSTvme9kzStcC2pAHjWaRpy+dGxJhcA6sSSQ8Az0bEsXnHUgmSbga2Id0W\nnEmakHJaREzONbAKyRYG/wFYlzR9+eKIuDjfqCpH0rakUl5blDsG2iGTjJmZtY16uI9tZmY1yknG\nzMyqxknGzMyqxknGzMyqxknGzMyqxknGzMyqxknGzMyqxknGzMyqxknGrB2QtFm21W3Viy1KOkTS\nx9X+HOsYnGTMOrBs3/Zf5R2H1S8nGbOOzXWlrKqcZKzDk9Qg6RJJ50t6T9IMScdK6irpMkkfSnpN\n0k+L3nO2pMmSPpU0VdIfJXUpOj9G0pii10tIelnSsDJjGpRd/zNJD5FKxpe22VLSg5I+kfRG9h2W\nLPlel0q6SNL72eOcrJIukhqA1YBzs1txc0uuv52k5yTNlnS/pNXL/d/UrMBJxizZn1TV+XvA2cBQ\nYCQwCdiUVIr+mmzDJoDZpE3SepE2b9oXOLXoegcBfSSdkL3+E2kPjhNohqRVgDuA+4CNgWHAORT1\nOiT1zs7fQdoldA+gD3BNI98LoB9wFHAkcFx27L9IWyacQapqvWLR+7oAJ5P2DukPfAe4rLnYzf5D\nRPjhR4d+AA3AoyXHZgB3FL1eGPgC2GM+1/gZ8HLJsd1JieW32c/eZcbzB2ByybFTgXnAqtnr4cBV\nJW36ZG2WLfpejV3n9aLXU4FflrQ5JLvO2kXH9gM+z/vfyo/29+iQm5aZlQjgmZJjM4Cv9y+PiDmS\nPiBttIWkPUk9gjWBJWhkd86IGJntn3Iq8D9Rxn7omfWAx0qOlb7uC6wpaZ+iY8q+y5rAu/N532PA\nbyUtERGzm4jhi4h4uej1v4FFJH0nIj4s50uYQQfdGdOsEaVbG8d8ji0kqR9p69khwL3Ah6Rey3nF\njbOthTcH5vDNTqzlaGzTuVICriTtxljqrRZcZ37mNBIT+Ba7tZCTjFnLDQDejIjfFw7MZ1D8XKAz\nsCNwn6S7IuLOMq7/AvCTkmP9Sl7/C9gwIqY0cR0BWzRynTeLejFfknphZlXhv0rM0i/j0r/4m+oB\nvAisLGk/SWtIGkwa+P/mzdJOpEH2AyKigdTruUpS9zLiuQxYXdJQSetmt+aOKmnzR+B72eyxTSSt\nJWkXSaWD8yuVXOcEvt37mQZsI2klScuWEZtZizjJmKVbQaXrRea7fiQiRpF6KUOBp4Htgd8U3iNp\nOdIsr99GxBPZ284m9VBKZ381dv3XSbPFBgFPAb8gzfSKojbPAtsAq5MG+J8iTRh4u+Q73EjqqTwG\nXAFcxbeTzG+AVYBXgXea+f5eU2Mtpgj/d2NWjyQ9ADwbEcfmHYt1XO7JmNWvxm4DmrUpJxmzNpZV\nEfh4Po9LKvhRjd0GNGtTvl1m1sayMZsl53P6o4h4dz7nzNodJxkzM6sa3y4zM7OqcZIxM7OqcZIx\nM7OqcZIxM7Oq+f9Z53yMSSa72AAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x175065f8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# plot max_depth (x-axis) versus RMSE (y-axis)\n",
    "plt.plot(max_depth_range, RMSE_scores)\n",
    "plt.xlabel('max_depth')\n",
    "plt.ylabel('RMSE (lower is better)')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DecisionTreeRegressor(criterion='mse', max_depth=3, max_features=None,\n",
       "           max_leaf_nodes=None, min_samples_leaf=1, min_samples_split=2,\n",
       "           min_weight_fraction_leaf=0.0, random_state=1, splitter='best')"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# max_depth=3 was best, so fit a tree using that parameter\n",
    "treereg = DecisionTreeRegressor(max_depth=3, random_state=1)\n",
    "treereg.fit(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>feature</th>\n",
       "      <th>importance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>year</td>\n",
       "      <td>0.798744</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>miles</td>\n",
       "      <td>0.201256</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>doors</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>vtype</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  feature  importance\n",
       "0    year    0.798744\n",
       "1   miles    0.201256\n",
       "2   doors    0.000000\n",
       "3   vtype    0.000000"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# \"Gini importance\" of each feature: the (normalized) total reduction of error brought by that feature\n",
    "pd.DataFrame({'feature':feature_cols, 'importance':treereg.feature_importances_})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating a tree diagram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# create a Graphviz file\n",
    "from sklearn.tree import export_graphviz\n",
    "export_graphviz(treereg, out_file='tree_vehicles.dot', feature_names=feature_cols)\n",
    "\n",
    "# At the command line, run this to convert to PNG:\n",
    "#   dot -Tpng tree_vehicles.dot -o tree_vehicles.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Tree for vehicle data](images/tree_vehicles.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reading the internal nodes:\n",
    "\n",
    "- **samples:** number of observations in that node before splitting\n",
    "- **mse:** MSE calculated by comparing the actual response values in that node against the mean response value in that node\n",
    "- **rule:** rule used to split that node (go left if true, go right if false)\n",
    "\n",
    "Reading the leaves:\n",
    "\n",
    "- **samples:** number of observations in that node\n",
    "- **value:** mean response value in that node\n",
    "- **mse:** MSE calculated by comparing the actual response values in that node against \"value\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Making predictions for the testing data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>price</th>\n",
       "      <th>year</th>\n",
       "      <th>miles</th>\n",
       "      <th>doors</th>\n",
       "      <th>vtype</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>3000</td>\n",
       "      <td>2003</td>\n",
       "      <td>130000</td>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>6000</td>\n",
       "      <td>2005</td>\n",
       "      <td>82500</td>\n",
       "      <td>4</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>12000</td>\n",
       "      <td>2010</td>\n",
       "      <td>60000</td>\n",
       "      <td>2</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   price  year   miles  doors  vtype\n",
       "0   3000  2003  130000      4      1\n",
       "1   6000  2005   82500      4      0\n",
       "2  12000  2010   60000      2      0"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# read the testing data\n",
    "url = 'https://raw.githubusercontent.com/justmarkham/DAT8/master/data/vehicles_test.csv'\n",
    "test = pd.read_csv(url)\n",
    "test['vtype'] = test.vtype.map({'car':0, 'truck':1})\n",
    "test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question:** Using the tree diagram above, what predictions will the model make for each observation?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  4000.,   5000.,  13500.])"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# use fitted model to make predictions on testing data\n",
    "X_test = test[feature_cols]\n",
    "y_test = test.price\n",
    "y_pred = treereg.predict(X_test)\n",
    "y_pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1190.2380714238084"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# calculate RMSE\n",
    "np.sqrt(metrics.mean_squared_error(y_test, y_pred))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7937.2539331937714"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# calculate RMSE for your own tree!\n",
    "y_test = [3000, 6000, 12000]\n",
    "y_pred = [0, 0, 0]\n",
    "from sklearn import metrics\n",
    "np.sqrt(metrics.mean_squared_error(y_test, y_pred))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Classification trees\n",
    "\n",
    "**Example:** Predict whether Barack Obama or Hillary Clinton will win the Democratic primary in a particular county in 2008:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Obama-Clinton decision tree](images/obama_clinton_tree.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Questions:**\n",
    "\n",
    "- What are the observations? How many observations are there?\n",
    "- What is the response variable?\n",
    "- What are the features?\n",
    "- What is the most predictive feature?\n",
    "- Why does the tree split on high school graduation rate twice in a row?\n",
    "- What is the class prediction for the following county: 15% African-American, 90% high school graduation rate, located in the South, high poverty, high population density?\n",
    "- What is the predicted probability for that same county?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparing regression trees and classification trees\n",
    "\n",
    "|regression trees|classification trees|\n",
    "|---|---|\n",
    "|predict a continuous response|predict a categorical response|\n",
    "|predict using mean response of each leaf|predict using most commonly occuring class of each leaf|\n",
    "|splits are chosen to minimize MSE|splits are chosen to minimize Gini index (discussed below)|"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Splitting criteria for classification trees\n",
    "\n",
    "Common options for the splitting criteria:\n",
    "\n",
    "- **classification error rate:** fraction of training observations in a region that don't belong to the most common class\n",
    "- **Gini index:** measure of total variance across classes in a region"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example of classification error rate\n",
    "\n",
    "Pretend we are predicting whether someone buys an iPhone or an Android:\n",
    "\n",
    "- At a particular node, there are **25 observations** (phone buyers), of whom **10 bought iPhones and 15 bought Androids**.\n",
    "- Since the majority class is **Android**, that's our prediction for all 25 observations, and thus the classification error rate is **10/25 = 40%**.\n",
    "\n",
    "Our goal in making splits is to **reduce the classification error rate**. Let's try splitting on gender:\n",
    "\n",
    "- **Males:** 2 iPhones and 12 Androids, thus the predicted class is Android\n",
    "- **Females:** 8 iPhones and 3 Androids, thus the predicted class is iPhone\n",
    "- Classification error rate after this split would be **5/25 = 20%**\n",
    "\n",
    "Compare that with a split on age:\n",
    "\n",
    "- **30 or younger:** 4 iPhones and 8 Androids, thus the predicted class is Android\n",
    "- **31 or older:** 6 iPhones and 7 Androids, thus the predicted class is Android\n",
    "- Classification error rate after this split would be **10/25 = 40%**\n",
    "\n",
    "The decision tree algorithm will try **every possible split across all features**, and choose the split that **reduces the error rate the most.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Example of Gini index\n",
    "\n",
    "Calculate the Gini index before making a split:\n",
    "\n",
    "$$1 - \\left(\\frac {iPhone} {Total}\\right)^2 - \\left(\\frac {Android} {Total}\\right)^2 = 1 - \\left(\\frac {10} {25}\\right)^2 - \\left(\\frac {15} {25}\\right)^2 = 0.48$$\n",
    "\n",
    "- The **maximum value** of the Gini index is 0.5, and occurs when the classes are perfectly balanced in a node.\n",
    "- The **minimum value** of the Gini index is 0, and occurs when there is only one class represented in a node.\n",
    "- A node with a lower Gini index is said to be more \"pure\".\n",
    "\n",
    "Evaluating the split on **gender** using Gini index:\n",
    "\n",
    "$$\\text{Males: } 1 - \\left(\\frac {2} {14}\\right)^2 - \\left(\\frac {12} {14}\\right)^2 = 0.24$$\n",
    "$$\\text{Females: } 1 - \\left(\\frac {8} {11}\\right)^2 - \\left(\\frac {3} {11}\\right)^2 = 0.40$$\n",
    "$$\\text{Weighted Average: } 0.24 \\left(\\frac {14} {25}\\right) + 0.40 \\left(\\frac {11} {25}\\right) = 0.31$$\n",
    "\n",
    "Evaluating the split on **age** using Gini index:\n",
    "\n",
    "$$\\text{30 or younger: } 1 - \\left(\\frac {4} {12}\\right)^2 - \\left(\\frac {8} {12}\\right)^2 = 0.44$$\n",
    "$$\\text{31 or older: } 1 - \\left(\\frac {6} {13}\\right)^2 - \\left(\\frac {7} {13}\\right)^2 = 0.50$$\n",
    "$$\\text{Weighted Average: } 0.44 \\left(\\frac {12} {25}\\right) + 0.50 \\left(\\frac {13} {25}\\right) = 0.47$$\n",
    "\n",
    "Again, the decision tree algorithm will try **every possible split**, and will choose the split that **reduces the Gini index (and thus increases the \"node purity\") the most.**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Comparing classification error rate and Gini index\n",
    "\n",
    "- Gini index is generally preferred because it will make splits that **increase node purity**, even if that split does not change the classification error rate.\n",
    "- Node purity is important because we're interested in the **class proportions** in each region, since that's how we calculate the **predicted probability** of each class.\n",
    "- scikit-learn's default splitting criteria for classification trees is Gini index.\n",
    "\n",
    "Note: There is another common splitting criteria called **cross-entropy**. It's numerically similar to Gini index, but slower to compute, thus it's not as popular as Gini index."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Building a classification tree in scikit-learn"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll build a classification tree using the Titanic data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>PassengerId</th>\n",
       "      <th>Survived</th>\n",
       "      <th>Pclass</th>\n",
       "      <th>Name</th>\n",
       "      <th>Sex</th>\n",
       "      <th>Age</th>\n",
       "      <th>SibSp</th>\n",
       "      <th>Parch</th>\n",
       "      <th>Ticket</th>\n",
       "      <th>Fare</th>\n",
       "      <th>Cabin</th>\n",
       "      <th>Embarked</th>\n",
       "      <th>Embarked_Q</th>\n",
       "      <th>Embarked_S</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>3</td>\n",
       "      <td>Braund, Mr. Owen Harris</td>\n",
       "      <td>1</td>\n",
       "      <td>22</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>A/5 21171</td>\n",
       "      <td>7.2500</td>\n",
       "      <td>NaN</td>\n",
       "      <td>S</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>2</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Cumings, Mrs. John Bradley (Florence Briggs Th...</td>\n",
       "      <td>0</td>\n",
       "      <td>38</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>PC 17599</td>\n",
       "      <td>71.2833</td>\n",
       "      <td>C85</td>\n",
       "      <td>C</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>3</td>\n",
       "      <td>1</td>\n",
       "      <td>3</td>\n",
       "      <td>Heikkinen, Miss. Laina</td>\n",
       "      <td>0</td>\n",
       "      <td>26</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>STON/O2. 3101282</td>\n",
       "      <td>7.9250</td>\n",
       "      <td>NaN</td>\n",
       "      <td>S</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4</td>\n",
       "      <td>1</td>\n",
       "      <td>1</td>\n",
       "      <td>Futrelle, Mrs. Jacques Heath (Lily May Peel)</td>\n",
       "      <td>0</td>\n",
       "      <td>35</td>\n",
       "      <td>1</td>\n",
       "      <td>0</td>\n",
       "      <td>113803</td>\n",
       "      <td>53.1000</td>\n",
       "      <td>C123</td>\n",
       "      <td>S</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5</td>\n",
       "      <td>0</td>\n",
       "      <td>3</td>\n",
       "      <td>Allen, Mr. William Henry</td>\n",
       "      <td>1</td>\n",
       "      <td>35</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>373450</td>\n",
       "      <td>8.0500</td>\n",
       "      <td>NaN</td>\n",
       "      <td>S</td>\n",
       "      <td>0</td>\n",
       "      <td>1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   PassengerId  Survived  Pclass  \\\n",
       "0            1         0       3   \n",
       "1            2         1       1   \n",
       "2            3         1       3   \n",
       "3            4         1       1   \n",
       "4            5         0       3   \n",
       "\n",
       "                                                Name  Sex  Age  SibSp  Parch  \\\n",
       "0                            Braund, Mr. Owen Harris    1   22      1      0   \n",
       "1  Cumings, Mrs. John Bradley (Florence Briggs Th...    0   38      1      0   \n",
       "2                             Heikkinen, Miss. Laina    0   26      0      0   \n",
       "3       Futrelle, Mrs. Jacques Heath (Lily May Peel)    0   35      1      0   \n",
       "4                           Allen, Mr. William Henry    1   35      0      0   \n",
       "\n",
       "             Ticket     Fare Cabin Embarked  Embarked_Q  Embarked_S  \n",
       "0         A/5 21171   7.2500   NaN        S           0           1  \n",
       "1          PC 17599  71.2833   C85        C           0           0  \n",
       "2  STON/O2. 3101282   7.9250   NaN        S           0           1  \n",
       "3            113803  53.1000  C123        S           0           1  \n",
       "4            373450   8.0500   NaN        S           0           1  "
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# read in the data\n",
    "url = 'https://raw.githubusercontent.com/justmarkham/DAT8/master/data/titanic.csv'\n",
    "titanic = pd.read_csv(url)\n",
    "\n",
    "# encode female as 0 and male as 1\n",
    "titanic['Sex'] = titanic.Sex.map({'female':0, 'male':1})\n",
    "\n",
    "# fill in the missing values for age with the median age\n",
    "titanic.Age.fillna(titanic.Age.median(), inplace=True)\n",
    "\n",
    "# create a DataFrame of dummy variables for Embarked\n",
    "embarked_dummies = pd.get_dummies(titanic.Embarked, prefix='Embarked')\n",
    "embarked_dummies.drop(embarked_dummies.columns[0], axis=1, inplace=True)\n",
    "\n",
    "# concatenate the original DataFrame and the dummy DataFrame\n",
    "titanic = pd.concat([titanic, embarked_dummies], axis=1)\n",
    "\n",
    "# print the updated DataFrame\n",
    "titanic.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Survived:** 0=died, 1=survived (response variable)\n",
    "- **Pclass:** 1=first class, 2=second class, 3=third class\n",
    "    - What will happen if the tree splits on this feature?\n",
    "- **Sex:** 0=female, 1=male\n",
    "- **Age:** numeric value\n",
    "- **Embarked:** C or Q or S"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# define X and y\n",
    "feature_cols = ['Pclass', 'Sex', 'Age', 'Embarked_Q', 'Embarked_S']\n",
    "X = titanic[feature_cols]\n",
    "y = titanic.Survived"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DecisionTreeClassifier(class_weight=None, criterion='gini', max_depth=3,\n",
       "            max_features=None, max_leaf_nodes=None, min_samples_leaf=1,\n",
       "            min_samples_split=2, min_weight_fraction_leaf=0.0,\n",
       "            random_state=1, splitter='best')"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# fit a classification tree with max_depth=3 on all data\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "treeclf = DecisionTreeClassifier(max_depth=3, random_state=1)\n",
    "treeclf.fit(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# create a Graphviz file\n",
    "export_graphviz(treeclf, out_file='tree_titanic.dot', feature_names=feature_cols)\n",
    "\n",
    "# At the command line, run this to convert to PNG:\n",
    "#   dot -Tpng tree_titanic.dot -o tree_titanic.png"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Tree for Titanic data](images/tree_titanic.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice the split in the bottom right: the **same class** is predicted in both of its leaves. That split didn't affect the **classification error rate**, though it did increase the **node purity**, which is important because it increases the accuracy of our predicted probabilities."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>feature</th>\n",
       "      <th>importance</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>Pclass</td>\n",
       "      <td>0.242664</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>Sex</td>\n",
       "      <td>0.655584</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>Age</td>\n",
       "      <td>0.064494</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>Embarked_Q</td>\n",
       "      <td>0.000000</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>Embarked_S</td>\n",
       "      <td>0.037258</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "      feature  importance\n",
       "0      Pclass    0.242664\n",
       "1         Sex    0.655584\n",
       "2         Age    0.064494\n",
       "3  Embarked_Q    0.000000\n",
       "4  Embarked_S    0.037258"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# compute the feature importances\n",
    "pd.DataFrame({'feature':feature_cols, 'importance':treeclf.feature_importances_})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 3: Comparing decision trees with other models\n",
    "\n",
    "**Advantages of decision trees:**\n",
    "\n",
    "- Can be used for regression or classification\n",
    "- Can be displayed graphically\n",
    "- Highly interpretable\n",
    "- Can be specified as a series of rules, and more closely approximate human decision-making than other models\n",
    "- Prediction is fast\n",
    "- Features don't need scaling\n",
    "- Automatically learns feature interactions\n",
    "- Tends to ignore irrelevant features\n",
    "- Non-parametric (will outperform linear models if relationship between features and response is highly non-linear)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Trees versus linear models](images/tree_vs_linear.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Disadvantages of decision trees:**\n",
    "\n",
    "- Performance is (generally) not competitive with the best supervised learning methods\n",
    "- Can easily overfit the training data (tuning is required)\n",
    "- Small variations in the data can result in a completely different tree (high variance)\n",
    "- Recursive binary splitting makes \"locally optimal\" decisions that may not result in a globally optimal tree\n",
    "- Doesn't tend to work well if the classes are highly unbalanced\n",
    "- Doesn't tend to work well with very small datasets"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}