notebooks/16_decision_trees.ipynb

{
 "metadata": {
  "name": "",
  "signature": "sha256:87008866d7dcc97facb27ccb4d1630e237017383a6de66e047b039f143121da7"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Introduction to 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": [
      "## Motivation\n",
      "\n",
      "Why are we learning about decision trees?\n",
      "\n",
      "- They're useful for both regression and classification problems.\n",
      "- They're popular (for a variety of reasons).\n",
      "- They're the basis for more sophisticated modeling approaches.\n",
      "- They demonstrate a different way of \"thinking\" than the models we have studied so far."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Regression trees\n",
      "\n",
      "Let's look at a simple example to get started.\n",
      "\n",
      "Our goal is to **predict a baseball player's Salary** based on **Years** (number of years playing in the major leagues) and **Hits** (number of hits he made in the previous year). Here is the training data, represented visually (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": [
      "**How might you \"stratify\" or \"segment\" the feature space into regions, based on salary?** Here are the rules:\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.\n",
      "\n",
      "Intuitively, you want to **maximize** the similarity (or \"homogeneity\") within a given region, and **minimize** the similarity between different regions.\n",
      "\n",
      "*Let's take a minute and do this...*\n",
      "\n",
      "Below is a regression tree that has been fit to the data by a computer. (We will talk later about how the fitting algorithm actually works.) Note that  Salary is measured in thousands and has been log-transformed."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "![Salary tree](images/salary_tree.png)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**How do we make Salary predictions (for out-of-sample data) using a decision tree?**\n",
      "\n",
      "- Start at the top, and examine the first \"splitting rule\" (Years < 4.5).\n",
      "- If the rule is **True** for a given player, follow the **left branch**. If the rule is **False**, follow the **right branch**.\n",
      "- Continue until reaching the bottom. The predicted Salary is the number in that particular \"bucket\".\n",
      "- **Note:** Years and Hits are both integers, but the convention is to label these rules using the midpoint between adjacent values.\n",
      "\n",
      "Example predictions:\n",
      "\n",
      "- Years=3, then predict 5.11 ($\\$1000 \\times e^{5.11} \\approx \\$166000$)\n",
      "- Years=5 and Hits=100, then predict 6.00 ($\\$1000 \\times e^{6.00} \\approx \\$403000$)\n",
      "- Years=8 and Hits=120, then predict 6.74 ($\\$1000 \\times e^{6.74} \\approx \\$846000$)\n",
      "\n",
      "**How did we come up with the numbers at the bottom of the tree?** Each number is just the **mean Salary in the training data** of players who fit that criteria.\n",
      "\n",
      "Here's the same diagram as before, split into the three regions:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "![Salary regions](images/salary_regions.png)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This diagram is essentially a combination of the two previous diagrams. In $R_1$, the mean log Salary was 5.11. In $R_2$, the mean log Salary was 6.00. In $R_3$, the mean log Salary was 6.74. Thus, those values are used to predict out-of-sample data.\n",
      "\n",
      "Let's introduce some terminology:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "![Salary tree annotated](images/salary_tree_annotated.png)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "**How might you interpret the \"meaning\" of this tree?**\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",
      "What we have seen so far hints at the advantages and disadvantages of decision trees:\n",
      "\n",
      "**Advantages:**\n",
      "\n",
      "- Highly interpretable\n",
      "- Can be displayed graphically\n",
      "- Prediction is fast\n",
      "\n",
      "**Disadvantages:**\n",
      "\n",
      "- Predictive accuracy is not as high as some supervised learning methods\n",
      "- Can easily overfit the training data"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Building a regression tree by hand\n",
      "\n",
      "How do you build a decision tree? You're going to find out by building one in pairs!\n",
      "\n",
      "Your training data is a tiny dataset of [used vehicle sale prices](https://raw.githubusercontent.com/justmarkham/DAT5/master/data/vehicles_train.csv). Your goal is to predict **price** for testing data. Here are your instructions:\n",
      "\n",
      "- Read the data into Pandas.\n",
      "- Explore the data by sorting, plotting, or split-apply-combine (aka `group_by`).\n",
      "- Decide which feature is the most important predictor, and use that to make your first split. (Only binary splits are allowed!)\n",
      "- After making your first split, you should actually split your data in Pandas into two parts, and then explore each part to figure out what other splits to make.\n",
      "- Stop making splits once you are convinced that it strikes a good balance between underfitting and overfitting. (As always, your goal is to build a model that generalizes well!)\n",
      "- You are allowed to split on the same variable multiple times!\n",
      "- Draw your tree, making sure to label your leaves with the mean Price for the observations in that \"bucket\".\n",
      "- When you're finished, review your tree to make sure nothing is backwards. (Remember: follow the **left branch** if the rule is **true**, and follow the **right branch** if the rule is **false**.)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## How does a computer build a regression tree?\n",
      "\n",
      "The ideal approach would be for the computer to consider every possible partition of the feature space. However, this is computationally infeasible, so instead an approach is used called **recursive binary splitting:**\n",
      "\n",
      "- Begin at the top of the tree.\n",
      "- For every single predictor, examine every possible cutpoint, and choose the predictor and cutpoint such that the resulting tree has the **lowest possible mean squared error (MSE)**. Make that split.\n",
      "- Repeat the examination for the two resulting regions, and again make a single split (in one of the regions) to minimize the MSE.\n",
      "- Keep repeating this process until a stopping criterion is met, such as **maximum tree depth** or **minimum number of samples in a leaf**.\n",
      "\n",
      "Below is the regression tree for player salaries grown much deeper, and a comparison of the training, test, and cross-validation errors for trees with different numbers of leaves:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "![Salary unpruned](images/salary_unpruned.png)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "As you can see, the **training error** continues to go down as the tree size increases, but the lowest **cross-validation error** occurs for a tree with 3 leaves."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Building a regression tree in scikit-learn"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# read the training data into pandas and print it out\n",
      "import pandas as pd\n",
      "train = pd.read_csv('https://raw.githubusercontent.com/justmarkham/DAT5/master/data/vehicles_train.csv')\n",
      "train"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\">\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>type</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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </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",
        "    </tr>\n",
        "  </tbody>\n",
        "</table>\n",
        "</div>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 1,
       "text": [
        "    price  year   miles  doors   type\n",
        "0   22000  2012   13000      2    car\n",
        "1   14000  2010   30000      2    car\n",
        "2   13000  2010   73500      4    car\n",
        "3    9500  2009   78000      4    car\n",
        "4    9000  2007   47000      4    car\n",
        "5    4000  2006  124000      2    car\n",
        "6    3000  2004  177000      4    car\n",
        "7    2000  2004  209000      4  truck\n",
        "8    3000  2003  138000      2    car\n",
        "9    1900  2003  160000      4    car\n",
        "10   2500  2003  190000      2  truck\n",
        "11   5000  2001   62000      4    car\n",
        "12   1800  1999  163000      2  truck\n",
        "13   1300  1997  138000      4    car"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# encode car as 0 and truck as 1\n",
      "train['type'] = train.type.map({'car':0, 'truck':1})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# create a list of the feature columns (every column except for the 0th column)\n",
      "feature_cols = train.columns[1:]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# define X (features) and y (response)\n",
      "X = train[feature_cols]\n",
      "y = train.price"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# import the relevant class, and instantiate the model (with random_state=1)\n",
      "from sklearn.tree import DecisionTreeRegressor\n",
      "treereg = DecisionTreeRegressor(random_state=1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# print the model object to see the default arguments\n",
      "treereg"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "DecisionTreeRegressor(compute_importances=None, criterion='mse',\n",
        "           max_depth=None, max_features=None, max_leaf_nodes=None,\n",
        "           min_density=None, min_samples_leaf=1, min_samples_split=2,\n",
        "           random_state=1, splitter='best')"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# use 3-fold cross-validation to estimate the RMSE for this model\n",
      "from sklearn.cross_validation import cross_val_score\n",
      "import numpy as np\n",
      "scores = cross_val_score(treereg, X, y, cv=3, scoring='mean_squared_error')\n",
      "np.mean(np.sqrt(-scores))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "4707.2505884845632"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Tuning a regression tree\n",
      "\n",
      "Let's see if we can reduce the RMSE by tuning the **max_depth** parameter. One way to search for an optimal value would be to try different values, one by one:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# try max_depth=1\n",
      "treereg = DecisionTreeRegressor(max_depth=1, random_state=1)\n",
      "scores = cross_val_score(treereg, X, y, cv=3, scoring='mean_squared_error')\n",
      "np.mean(np.sqrt(-scores))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "4928.1374642038018"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Or, we could write a loop to try a range of values:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# define a range of values\n",
      "max_depth_range = range(1, 11)\n",
      "\n",
      "# create an empty list to store the average RMSE for each value of max_depth\n",
      "RMSE_scores = []\n",
      "\n",
      "# use cross-validation 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=3, scoring='mean_squared_error')\n",
      "    RMSE_scores.append(np.mean(np.sqrt(-MSE_scores)))\n",
      "\n",
      "# print the results\n",
      "RMSE_scores"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "[4928.1374642038018,\n",
        " 4804.3767888427128,\n",
        " 4592.1554255755254,\n",
        " 4704.0052694797387,\n",
        " 4707.2505884845632,\n",
        " 4707.2505884845632,\n",
        " 4707.2505884845632,\n",
        " 4707.2505884845632,\n",
        " 4707.2505884845632,\n",
        " 4707.2505884845632]"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# plot the max_depth (x-axis) versus the RMSE (y-axis)\n",
      "%matplotlib inline\n",
      "import matplotlib.pyplot as plt\n",
      "plt.plot(max_depth_range, RMSE_scores)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "[<matplotlib.lines.Line2D at 0x17112630>]"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAX4AAAEACAYAAAC08h1NAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X24VWWd//H3R5AnBUwxRcHAOiimlpJg+cDWLJVQwbLQ\nBptfzgxGppOGCXXlGZ1QKzO10blmzAcqndR8gELGCLbZTHpSj4qCCjo+gICOipjRCPr9/bHW0R2c\nh30O+5y19t6f13VxnbXvtfZa3y3y3ff5rvu+lyICMzOrH9tkHYCZmfUsJ34zszrjxG9mVmec+M3M\n6owTv5lZnXHiNzOrM2Ulfkm9JDVLmpe+/oikP0h6VNJcSQPT9hGSNqTHNku6quQcYyQtkbRc0uXd\n83HMzKwj5fb4zwKWAi2D/q8Bzo2I/YHbgRklx66IiAPSP9NL2q8GTouIBqBB0jFbGbuZmXVBh4lf\n0jBgAkmyV9rcEBH3ptsLgc92cI6hwMCIaEqb5gCTuhSxmZltlXJ6/JeR9OjfKWl7XNIJ6fZJwPCS\nfSPTMk9R0qFp2+7AypJjVqVtZmbWw9pN/JImAi9FRDPv9fYBvgxMl/QAsD3wVtr+IjA8Ig4AzgZu\nbKn/m5lZPvTuYP8ngOMlTQD6AYMkzYmIU4GjASSNAj4DEBFvkX4JRMRDkp4GGkh6+MNKzjssbduC\nJC8eZGbWSRGhjo9KtNvjj4hZETE8IkYCU4BFEXGqpJ0BJG0DfJvkxi2ShkjqlW7vSZL0n4mI1cB6\nSeMkCZgK3NHOdXP15/zzz888BsdUOzHlNS7HVL0xdVZnx/G3XOEUSU8Cy4CVEXF92n448IikZuAW\nYFpErEv3TSe5QbycZOTPgk5Ha2ZmW62jUs+7IuIe4J50+3Jgi7H4EXEbcFsb738Q2K9rYZqZWaV4\n5m4ZCoVC1iFswTGVJ48xQT7jckzlyWNMnaWu1Ie6k6TIW0xmZnkmiajUzV0zM6s9TvxmZnXGid/M\nrM448ZuZ1RknfjOzOuPEb2ZWZ5z4zczqTC4T/2uvZR2BmVntymXiv/jirCMwM6tduZy5u+OOwcMP\nw/DhHR9vZlbvamLm7rRp0NiYdRRmZrUplz3+114LRo2CYhH22SfriMzM8q0mevw77ADf/CbMmpV1\nJGZmtSeXPf6I4C9/gb32ghtvhEMOyToqM7P8qokeP0C/fnDBBUnPP2ffTWZmVS23iR/gb/4GXn8d\n5s3LOhIzs9qR68Tfq1cypn/mTNi0KetozMxqQ1mJX1IvSc2S5qWvPyLpD5IelTRX0sCSY2dKWi7p\nCUmfLmkfI2lJum+L5/W2ZcIEGDIE5szpzMcyM7O2lNvjPwtYCrRU268Bzo2I/YHbgRkAkvYBvgDs\nAxwDXCWp5YbD1cBpEdEANEg6ppwLS3DJJXD++bBhQ5nRmplZmzpM/JKGARNIkn1LEm+IiHvT7YXA\nZ9PtE4CbImJjRDwLrADGSRoKDIyIpvS4OcCkcoM8+GAYOxauvLLcd5iZWVvK6fFfRtKjf6ek7XFJ\nJ6TbJwEtiyvsBqwsOW4lsHsr7avS9rLNng3f/74XcDMz21rtJn5JE4GXIqKZ93r7AF8Gpkt6ANge\neKv7QkzstRdMnuwF3MzMtlbvDvZ/Ajhe0gSgHzBI0pyIOBU4GkDSKOAz6fGreK/3DzCMpKe/Kt0u\nbV/V1kUbSxbqKRQKFAoFIKnz778/nHGGF3Azs/pVLBYpFotdfn/ZM3cljQe+ERHHSdo5Il6WtA1w\nPbAoIq5Pb+7eCIwlKeUsBD4UESHpfuBMoAn4NXBFRCxo5TrRXkyzZsHatfCTn3Tqc5qZ1azunrnb\nkpFPkfQksAxYGRHXA0TEUuBmkhFAdwHTS7L4dJIbxMuBFa0l/XKce24yoevxx7vybjMzy+1aPe35\n4Q/hnnvgzjt7KCgzsxzrbI+/KhN/ywJuP/85HHpoDwVmZpZTNbNIW3v69YMLL/QCbmZmXVGViR/g\ni1+EN96AuXOzjsTMrLpUbeL3Am5mZl1TtYkf4Nhj4f3v9wJuZmadUZU3d0vddx+cdBI89RT079+N\ngZmZ5VRd3Nwt5QXczMw6p+p7/ABPPpkM63zySdhxx24KzMwsp+quxw/JmP4TT/QCbmZm5aiJHj/A\niy/CfvvBww97ATczqy91MXO3Ld/6FqxeDddeW+GgzMxyrK4T/+uvQ0MDLFoE++5b4cDMzHKqLmv8\nLQYPTiZ0zZqVdSRmZvlVUz1+gP/7v+Rm789+5gXczKw+1HWPH6BvX7jgAi/gZmbWlppL/OAF3MzM\n2lOTid8LuJmZta0mEz+8t4DbDTdkHYmZWb7U3M3dUvffD5/9bLKA24ABFTmlmVnudMvNXUm9JDVL\nmpe+HiupKW37o6SD0vYRkjak7c2Srio5xxhJSyQtl3R5Zz9YV4wblyzi5gXczMzeU1aPX9LZwBhg\nYEQcL6kIXBQR/ynpWODciDhC0ghgXkTs18o5moAzIqJJ0nzgiohY0MpxFevxgxdwM7PaV/Eev6Rh\nwATgGqDlxKuBwen2DsCqDs4xlORLoyltmgNMKjfIrbHXXkm556KLeuJqZmb5V06p5zJgBvBOSdt5\nwKWSnge+D8ws2TcyLfMUJbVMododWFlyzKq0rUecf36yfs/zz/fUFc3M8qt3ezslTQReiohmSYWS\nXT8BzoyI2yWdBFwLfAp4ERgeEa9JOhC4Q9KHOxtUY2Pju9uFQoFCodDmseUYOhS+8hVobPQCbmZW\n/YrFIsViscvvb7fGL2k2MBXYBPQDBgG3ASdExKD0GAHrImJwK+9fDJxDUhpaFBGj0/aTgfERcXor\n76lojb/F66/DqFHw2996ATczqy0VrfFHxKyIGB4RI4EpJMl7KrBC0vj0sCOBp9KLD5HUK93eE2gA\nnomI1cB6SePSL4qpwB2d/XBbY/BgOO88L+BmZtbZCVwtXfF/AL4n6WHgn9PXAIcDj0hqBm4BpkXE\nunTfdJIbxMuBFa2N6Olu06fDo4/Cvff29JXNzPKjpidwteanP4Wrr4b/+i9Q2b8YmZnlV92vztmR\nU06BN9+EO+/MOhIzs2zUXY8f4K674OyzYckS6N3uuCYzs/xzj78MxxwDu+4K11+fdSRmZj2vLnv8\nAE1NcOKJXsDNzKqfe/xlGjsWPv5xuOKKrCMxM+tZddvjh6S3f8ghXsDNzKqbe/ydMGqUF3Azs/pT\n1z1+gNWrkyUcmpthjz167LJmZhXT2R5/3Sd+gG9/G1atguuu69HLmplVhBN/F7Qs4LZwIey3xSNk\nzMzyzTX+Lhg8GGbO9AJuZlYfnPhTX/kKPPYY/O53WUdiZta9nPhTffvChRfCN78JOat+mZlVlBN/\niVNOgQ0b4I4efVKAmVnP8s3dzSxYAF//uhdwM7Pq4Zu7W+noo72Am5nVNvf4W+EF3MysmrjHXwFe\nwM3Mapl7/G146in4xCeSBdx22inraMzM2tYtPX5JvSQ1S5qXvh4rqSlt+6Okg0qOnSlpuaQnJH26\npH2MpCXpvss786GyMGoUnHSSF3Azs9pTVo9f0tnAGGBgRBwvqQhcFBH/KelY4NyIOELSPsCNwEHA\n7sBCoCEiQlITcEZENEmaD1wREQtauVYuevzw3gJujzwCw4ZlHY2ZWesq3uOXNAyYAFwDtJx4NTA4\n3d4BWJVunwDcFBEbI+JZYAUwTtJQki+NpvS4OcCkcoPMytChMGkS3Hpr1pGYmVVOOaWey4AZwDsl\nbecBl0p6Hvg+MDNt3w1YWXLcSpKe/+btq9L23Js8GW6/PesozMwqp90pSpImAi9FRLOkQsmunwBn\nRsTtkk4CrgU+VamgGhsb390uFAoUCoU2j+1un/wkfPGL8PLLsPPOmYVhZvauYrFIsVjs8vvbrfFL\nmg1MBTYB/YBBwG3ACRExKD1GwLqIGCzpPICIuDjdtwA4H3gOWBwRo9P2k4HxEXF6K9fMTY2/xec+\nBxMmwJe/nHUkZmZbqmiNPyJmRcTwiBgJTAEWRcRUYIWk8elhRwJPpdtzgSmS+kgaCTQATRGxBlgv\naVz6RTEVqJoVcSZP9vo9ZlY7OrsaTUtX/B+Af5HUF9iQviYilkq6GVhK8lvC9JLu+3TgeqA/ML+1\nET15NWFCsmzzn/4E22+fdTRmZlvHE7jK9OlPw7RpycPZzczyxEs2dJNJk1zuMbPa4B5/mVatSp7H\nu3YtbLtt1tGYmb3HPf5usvvu0NAA99yTdSRmZlvHib8TJk3yZC4zq34u9XTCE0/AUUfB88/DNv7K\nNLOccKmnG+29dzKc88EHs47EzKzrnPg7yWv3mFm1c+LvJA/rNLNq58TfSQcdBOvWJU/mMjOrRk78\nnbTNNu71m1l1c+LvAg/rNLNq5uGcXfDWW7DLLvD447DbbllHY2b1zsM5e0CfPsmKnXPnZh2JmVnn\nOfF3kcs9ZlatXOrpojfeSNbvef552GGHrKMxs3rmUk8PGTgQDj8c5s/POhIzs85x4t8KfiSjmVUj\nl3q2wksvwahRsGYN9OuXdTRmVq9c6ulB738/7L8//Pa3WUdiZla+shK/pF6SmiXNS1//In3dLOl/\nJDWn7SMkbSjZd1XJOcZIWiJpuaTLu+fj9DzP4jWzalNWqUfS2cAYYGBEHL/Zvh8A6yLinyWNAOZF\nxH6tnKMJOCMimiTNB66IiAWtHFc1pR6AZ56Bj38cXnwRevXKOhozq0cVL/VIGgZMAK4BtNk+AZ8H\nburgHENJvjSa0qY5wKRyg8yzPfeEXXeFP/wh60jMzMpTTqnnMmAG8E4r+w4D1kbE0yVtI9MyT1HS\noWnb7sDKkmNWpW01weUeM6smvdvbKWki8FJENEsqtHLIycCNJa9fBIZHxGuSDgTukPThzgbV2Nj4\n7nahUKBQaO3S+TF5Mnz2s/D974PK/mXLzKxrisUixWKxy+9vt8YvaTYwFdgE9AMGAb+MiFMl9Sbp\nxR8YES+28f7FwDnAamBRRIxO208GxkfE6a28p6pq/AARMHIkzJsH+21xd8PMrHtVtMYfEbMiYnhE\njASmkCTvU9PdRwHLSpO+pCGSeqXbewINwDMRsRpYL2lcel9gKlAzxRHJa/eYWfXo7Dj+0q74F9jy\npu7hwCPp8M5bgGkRsS7dN53kBvFyYEVrI3qqmWfxmlm18MzdCtm0CYYOhT/+EUaMyDoaM6snnrmb\nkd694bjj4M47s47EzKx9TvwV5GGdZlYNXOqpoA0bkslcTz8NQ4ZkHY2Z1QuXejLUvz8cdRT86ldZ\nR2Jm1jYn/grzsE4zyzuXeirstdfgAx+A1athu+2yjsbM6oFLPRl73/tg7Fi4++6sIzEza50TfzeY\nPNnlHjPLL5d6usELL8BHP5o8knHbbbOOxsxqnUs9OTB8eLJO/+9+l3UkZmZbcuLvJl67x8zyyqWe\nbrJ0KRx9NDz/vNfoN7Pu5VJPToweDQMGwIMPZh2Jmdlfc+LvJi1r9LvcY2Z548TfjTys08zyyIm/\nG40dC6++Ck89lXUkZmbvceLvRttsAyec4HKPmeWLE38387BOM8ub3lkHUOuOOAKmTEkWbRs6NOto\nasvGjfCnP8Ebb7T9c8OGrKM0y5+yEr+kXsADwMqIOE7SL4BR6e4dgHURcUB67Ezgy8DbwJkRcXfa\nPga4HugHzI+Isyr5QfKqTx849liYOxemTcs6muxEwJtvtp6gO0rebf18+20YOBC2377tn/37ex6F\n2ebKmsAl6WxgDDAwIo7fbN8PSBL/P0vaB7gROAjYHVgINERESGoCzoiIJknzgSsiYkEr16qJCVyl\nbr4ZrrsO7ror60i6zwMPwKWXJgm5tST95z9Dv35bJub2knZbP1u2+/Z1UjeDzk/g6jDxSxpG0lP/\nLnB2RBxXsk/Ac8AREfF02tt/JyIuSfcvABrTYxZFxOi0fQpQiIjTW7lezSX+9eth2LBk8bbBg7OO\npvI2bkwWpTvlFPjIR1pP1tttB716ZR2pWW3qbOIvp9RzGTADGNTKvsOAtRHxdPp6N+C+kv0rSXr+\nG9PtFqvS9rowaBAcdljS458yJetoKu/KK5Mvtlmz3AM3qwbtJn5JE4GXIqJZUqGVQ04mKe1UVGNj\n47vbhUKBQqG1S1eXllm8tZb4V6+G2bPhv//bSd+spxSLRYrFYpff326pR9JsYCqwieSm7CDglxFx\nqqTeJL34AyPixfT48wAi4uL09QLgfJJSz+KSUs/JwPh6KfUArF0Le+2V/OzbN+toKmfq1KS3f9FF\nWUdiVr8qukhbRMyKiOERMRKYQlKnPzXdfRSwrCXpp+YCUyT1kTQSaACaImINsF7SuPS+wFSgrka3\n77IL7LsvLFqUdSSVc++9UCzCt76VdSRm1hmdncBV2hX/AnDTX+2MWArcDCwF7gKml3TfpwPXAMuB\nFa2N6Kl1tbR2z6ZN8NWvJiN5tt8+62jMrDO8Hn8PWrECDj0UVq2q/hEuV16Z3LNYuNC1fbOseT3+\nHPvQh2DnneG++zo+Ns/WroULLkiSv5O+WfVx4u9htbB2z8yZ8KUvwT77ZB2JmXWFSz097KGH4POf\nh+XLq7O3/Ic/wOc+B8uWJfMTzCx7LvXk3AEHJDNdH38860g67+234Ywz4Hvfc9I3q2ZO/D2smh/J\n+O//niy9cMopWUdiZlvDiT8DkyZV37DO//1f+M534Mc/rs4SlZm9xzX+DGzaBLvumtT799gj62jK\nM21aMuP4iiuyjsTMNucafxXo3RsmToQ778w6kvI88EDyPIELLsg6EjOrBCf+jFTLLN533klm6F50\nEeywQ9bRmFklOPFn5FOfggcfhFdeyTqS9l13XfLQ+FNP7fhYM6sOTvwZGTAAPvlJ+NWvso6kba++\nmizA9i//kiR/M6sN/uecobwP6/zOd5KS1IEHZh2JmVWSR/Vk6NVXYcQIWLMm+Q0gTx5+GI4+Opmh\nu+OOWUdjZu3xqJ4qsuOOcNBBcPfdWUfy1yKSG7oXXuikb1aLnPgzlsdyz09/Cm+9BaedlnUkZtYd\nXOrJ2AsvJOv3rFmTjO/P2uuvw957J3MMxo7NOhozK4dLPVVm+PCkzn/vvVlHkmhshM98xknfrJbl\noI9pLWv3HHFEtnEsWQI/+xksXZptHGbWvVzqyYHHH4djj4XnnstuAbSI5IvnpJOSG7tmVj26pdQj\nqZekZknzStq+JmmZpMckXZK2jZC0IT22WdJVJcePkbRE0nJJl3fmQ9W6ffZJFkBrbs4uhv/4j6S+\nf/rp2cVgZj2j3FLPWcBSYCCApCOA44H9I2KjpJ1Ljl0REQe0co6rgdMioknSfEnHRMSCrQm+Vkjv\nrd2TxWSpN96AGTPgF7+o/ofAm1nHOuzxSxoGTACuAVp+lfgKcFFEbASIiJc7OMdQYGBENKVNc4BJ\nXQ26FmU5rPPCC5PlIw45JJvrm1nPKqfUcxkwA3inpK0BOFzSfZKKkj5Wsm9kWuYpSjo0bdsdWFly\nzKq0zVIHH5w87GTFip697rJlyUJsl1zSs9c1s+y0W+qRNBF4KSKaJRU2e9/7IuJgSQcBNwN7Ai8C\nwyPiNUkHAndI+nBng2psbHx3u1AoUCgU2jy2VmyzDRx/fNLr/8Y3euaaEXDmmclCbLvu2jPXNLOt\nVywWKRaLXX5/u6N6JM0GpgKbgH7AIOA2YAhwcUTckx63AhgXEa9s9v7FwDnAamBRRIxO208GxkfE\nFrcS63FUT4u77oLvfhd+//ueud6tt8I//VNyUzkPk8fMrGsqOqonImZFxPCIGAlMIUneU4E7gCPT\nC44C+kTEK5KGSOqVtu9JUhJ6JiJWA+sljZMkki+TnC1UkL0jj4THHoO1a7v/Wm++CWefnTxD10nf\nrL50duZuS1f8WmBPSUuAm4CWx3QcDjwiqRm4BZgWEevSfdNJbhAvJxn54xE9m+nbF445JnnMYXeb\nPRsOPRTGj+/+a5lZvngCV8784hdwww0wf373XWP5cvj4x+HRR2G33brvOmbWMzpb6nHiz5n162HY\nMFi5EgYNqvz5I2DChKSsNGNG5c9vZj3Pi7RVuUGDkvH0d93VPeefOxeefRbOOqt7zm9m+efEn0OT\nJ3fPZK4NG+Af/xGuvBL69Kn8+c2sOrjUk0Nr1sDo0cnPvn0rd97GxmRBuFtuqdw5zSx7LvXUgF13\nTRZuW7y4cud85pmkp3/ppZU7p5lVJyf+nKr02j1f/zqccw7ssUflzmlm1cmlnpxavhwOPxxWrUqW\nc9ga8+cnN3Mfe6yypSMzyweXempEQwPstBPcf//Wnecvf0nW47niCid9M0s48edYJco9l14K++6b\nPOHLzAxc6sm1Bx+Ek0+GJ5/s2iMZn3suebDLAw/AyJGVj8/M8sGlnhpy4IFJqWbZsq69/5xzkjKP\nk76ZlXLizzEpKffcfnvn3/ub38BDD8G551Y+LjOrbk78OdeVOv9bb8HXvgY/+hH07989cZlZ9XLi\nz7nDDksmX73wQvnv+dGP4IMfhOOO6764zKx6OfHn3LbbwsSJcOed5R2/ahV873tw+eVduyFsZrXP\nib8KdKbc841vwOmnw4c+1L0xmVn18nDOKvDnPyfr9zz7LOy4Y9vHLV4Mf/u3sHQpbLddT0VnZlnz\ncM4aNGBA8uCUX/+67WM2bkxu6P7wh076ZtY+J/4qMXly+8M6f/zj5DGKJ57YczGZWXUqK/FL6iWp\nWdK8kravSVom6TFJl5S0z5S0XNITkj5d0j5G0pJ03+WV/Ri1b+JEWLgwKftsbs0a+O53k/V4fEPX\nzDpSbo//LGApEACSjgCOB/aPiH2BH6Tt+wBfAPYBjgGukt5NRVcDp0VEA9Ag6ZiKfYo6sNNOMGZM\nkvw3d+65cNppsPfePR+XmVWfDhO/pGHABOAaoCWJfwW4KCI2AkTEy2n7CcBNEbExIp4FVgDjJA0F\nBkZEU3rcHGBSxT5FnWit3PP738OiRfDtb2cTk5lVn3J6/JcBM4B3StoagMMl3SepKOljaftuwMqS\n41YCu7fSviptt0444QT41a9g06bk9aZN8NWvwg9+AAMHZhubmVWP3u3tlDQReCkimiUVNnvf+yLi\nYEkHATcDe1YqqMbGxne3C4UChUKhzWPryQc+kDxB6/e/h0IB/vVfk+GdX/hC1pGZWU8qFosUi8Uu\nv7/dcfySZgNTgU1AP2AQcBswBLg4Iu5Jj1sBHAz8HUBEXJy2LwDOB54DFkfE6LT9ZGB8RJzeyjU9\njr8dF14Ir7wCs2bBhz+cjN3fd9+sozKzLFV0HH9EzIqI4RExEpgCLIqIqcAdwJHpBUcBfSLif4G5\nwBRJfSSNJCkJNUXEGmC9pHHpzd6Wc1gntczinTkTpk510jezzmu31NOKlq74tcC1kpYAbwGnAkTE\nUkk3k4wA2gRML+m+TweuB/oD8yNiwVbGXpf23Rd6906eo/vEE1lHY2bVyEs2VKFrrkmWcJg4MetI\nzCwPOlvqceI3M6tyXqvHzMza5cRvZlZnnPjNzOqME7+ZWZ1x4jczqzNO/GZmdcaJ38yszjjxm5nV\nGSd+M7M648RvZlZnnPjNzOqME7+ZWZ1x4jczqzNO/GZmdcaJ38yszjjxm5nVGSd+M7M6U1bil9RL\nUrOkeenrRkkr07ZmScek7SMkbShpv6rkHGMkLZG0XNLl3fNxzMysI+X2+M8ieYB6yzMRA/hhRByQ\n/il9cPqKkvbpJe1XA6dFRAPQ0PJlUQ2KxWLWIWzBMZUnjzFBPuNyTOXJY0yd1WHilzQMmABcA7Q8\n01El2x2SNBQYGBFNadMcYFLnQs1OHv+iHVN58hgT5DMux1SePMbUWeX0+C8DZgDvlLQF8DVJj0j6\niaQdSvaNTMs8RUmHpm27AytLjlmVtpmZWQ9rN/FLmgi8FBHN/HUP/2pgJPBRYDVwadr+IjA8Ig4A\nzgZulDSw4lGbmVmXKSLa3inNBqYCm4B+wCDglxFxaskxI4B5EbFfK+9fDJxD8uWwKCJGp+0nA+Mj\n4vRW3tN2QGZm1qqIKLv83ruDE80CZgFIGg98IyJOlTQ0Ilanh00GlqTHDAFei4i3Je0JNADPRMQ6\nSesljQOaSL5Mrtja4M3MrPPaTfybEe+N6vmepI+kr/8HmJa2Hw5cIGkjyT2BaRGxLt03Hbge6A/M\n32wkkJmZ9ZB2Sz1mZlZ7cjFzV9K1ktZKWpJ1LC0kDZe0WNLjkh6TdGbWMQFI6ifpfkkPS1oq6aKs\nY4ItJ/nlgaRnJT2axtXU8Tu6n6QdJN0qaVn693dwxvHsVTLhslnS63n4f13SzPTf3hJJN0rqm3VM\nAJLOSmN6TNJZGcWwRb6UtKOk30h6StLdm4203EIuEj9wHZC3CV0bga9HxIeBg4GvShqdcUxExF+A\nIyLio8D+wBElw2aztPkkvzwIoJBOJhybdTCpy0lKnaNJ/v6WZRlMRDzZMuESGAP8Gbg9y5jSASN/\nDxyYDhrpBUzJMiYASfsCfwccBHwEmCjpgxmE0lq+PA/4TUSMAn6bvm5TLhJ/RNwLvJZ1HKUiYk1E\nPJxu/4nkH+hu2UaViIg/p5t9SP5RvJphOG1N8suL3MQjaTBwWERcCxARmyLi9YzDKnUU8HREvJBx\nHOtJOl4DJPUGBpDM/cna3sD9EfGXiHgbuAc4saeDaCNfHg/ckG7fQAcTZHOR+PMu7YEcANyfbSQJ\nSdtIehhYCyyOiKUZh9TaJL88CGChpAck/X3WwZDMfXlZ0nWSHpL075IGZB1UiSnAjVkHERGvkswN\nep5kbtC6iFiYbVQAPAYclpZVBgCfAYZlHFOLXSJibbq9FtilvYOd+DsgaXvgVuCstOefuYh4Jy31\nDAMOl1TIKpZ2JvnlwSFpCeNYklLdYRnH0xs4ELgqIg4E3qSDX8l7iqQ+wHHALTmI5YPAPwIjSH7L\n3l7SFzMNCoiIJ4BLgLuBu4Bm8tfZIZIRO+2WXJ342yFpW+CXwM8i4o6s49lcWib4NfCxDMP4BHC8\npP8BbgKOlDQnw3je1TLXJCJeJqlbZ13nXwmsjIg/pq9vJfkiyINjgQfT/1ZZ+xjw3xHxSkRsAm4j\n+f8scxERVJ24AAABV0lEQVRxbUR8LCLGA+uAJ7OOKbVW0q7w7tpoL7V3sBN/GyQJ+AmwNCJ+lHU8\nLSQNabljL6k/8CmSnkcmImJWRAyPiJEkpYJFpTO7syJpQMtyIZK2Az5NOtEwKxGxBnhB0qi06Sjg\n8QxDKnUyyRd3HjwBHCypf/rv8CiSgQOZk/T+9OceJJNXMy+NpeYCX0q3vwS021HtzASubiPpJmA8\nsJOkF4DvRMR1GYd1CPA3wKOSWhLrzBxMPBsK3CBpG5Iv7p9GxG8zjqlUXkb17ALcnuQNegM/j4i7\nsw0JgK8BP09LK08D/y/jeFq+GI8iGUmTuYh4JP2t8QGSUspDwL9lG9W7bpW0E8nN5+kRsb6nAyjJ\nl0Na8iVwMXCzpNOAZ4HPt3sOT+AyM6svLvWYmdUZJ34zszrjxG9mVmec+M3M6owTv5lZnXHiNzOr\nM078ZmZ1xonfzKzO/H8umBBRSOlPfwAAAABJRU5ErkJggg==\n",
       "text": [
        "<matplotlib.figure.Figure at 0x16fd55f8>"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In a later class, we'll learn how to use scikit-learn's [GridSearchCV](http://scikit-learn.org/stable/modules/generated/sklearn.grid_search.GridSearchCV.html) to locate these optimal parameters more easily."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# 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)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "DecisionTreeRegressor(compute_importances=None, criterion='mse', max_depth=3,\n",
        "           max_features=None, max_leaf_nodes=None, min_density=None,\n",
        "           min_samples_leaf=1, min_samples_split=2, random_state=1,\n",
        "           splitter='best')"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# compute the \"Gini importance\" of each feature: the (normalized) total reduction of MSE brought by that feature\n",
      "pd.DataFrame({'feature':feature_cols, 'importance':treereg.feature_importances_})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\">\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>type</td>\n",
        "      <td>0.000000</td>\n",
        "    </tr>\n",
        "  </tbody>\n",
        "</table>\n",
        "</div>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "  feature  importance\n",
        "0    year    0.798744\n",
        "1   miles    0.201256\n",
        "2   doors    0.000000\n",
        "3    type    0.000000"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Creating a tree diagram"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# create a Graphviz file\n",
      "from sklearn.tree import export_graphviz\n",
      "with open(\"tree_vehicles.dot\", 'wb') as f:\n",
      "    f = export_graphviz(treereg, out_file=f, 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"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "![Tree for vehicle data](images/tree_vehicles.png)"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "How do we read this decision tree?\n",
      "\n",
      "**Internal nodes:**\n",
      "\n",
      "- \"samples\" is the number of observations in that node before splitting\n",
      "- \"mse\" is the mean squared error calculated by comparing the actual response values in that node against the mean response value in that node\n",
      "- first line is the condition used to split that node (go left if true, go right if false)\n",
      "\n",
      "**Leaves:**\n",
      "\n",
      "- \"samples\" is the number of observations in that node\n",
      "- \"value\" is the mean response value in that node\n",
      "- \"mse\" is the mean squared error calculated by comparing the actual response values in that node against \"value\""
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Predicting on test data\n",
      "\n",
      "How good is scikit-learn's regression tree at predicting the price for test observations?"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# read the test data\n",
      "test = pd.read_csv('https://raw.githubusercontent.com/justmarkham/DAT5/master/data/vehicles_test.csv')\n",
      "\n",
      "# encode car as 0 and truck as 1\n",
      "test['type'] = test.type.map({'car':0, 'truck':1})\n",
      "\n",
      "# print the data\n",
      "test"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\">\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>type</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>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "   price  year   miles  doors  type\n",
        "0   3000  2003  130000      4     1\n",
        "1   6000  2005   82500      4     0\n",
        "2  12000  2010   60000      2     0"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# define X and y\n",
      "X_test = test[feature_cols]\n",
      "y_test = test.price"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# make predictions on test data\n",
      "y_pred = treereg.predict(X_test)\n",
      "y_pred"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "array([  4000.,   5000.,  13500.])"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# calculate RMSE\n",
      "from sklearn import metrics\n",
      "np.sqrt(metrics.mean_squared_error(y_test, y_pred))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 17,
       "text": [
        "1190.2380714238084"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# calculate RMSE for your own tree!\n",
      "y_test = [3000, 6000, 12000]\n",
      "y_pred = [3057, 3057, 16333]\n",
      "np.sqrt(metrics.mean_squared_error(y_test, y_pred))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "3024.3118776563592"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Classification trees\n",
      "\n",
      "Classification trees are very similar to regression trees. Here is a quick comparison:\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)|\n",
      "\n",
      "Here's an **example of a classification tree**, which predicts whether Barack Obama or Hillary Clinton would 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": [
      "**A few questions:**\n",
      "\n",
      "- What is the response variable?\n",
      "- What are the features?\n",
      "- What is the most predictive feature?\n",
      "- How would we calculate the total number of counties?"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Splitting criteria for classification trees\n",
      "\n",
      "Here are 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\n",
      "- **cross-entropy:** numerically similar to Gini index\n",
      "\n",
      "The goal when splitting is to increase the \"node purity\", and it turns out that the **Gini index and cross-entropy** are better measures of purity than classification error rate. The Gini index is faster to compute than cross-entropy, so it is generally preferred (and is used by scikit-learn by default)."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Example calculations of Gini index\n",
      "\n",
      "Let's say that we are predicting survival on the Titanic. At a particular node, there are **25 individuals**, of whom 10 survived and 15 died. Here's how we calculate the Gini index before making a split:\n",
      "\n",
      "$$1 - \\left(\\frac {Survived} {Total}\\right)^2 - \\left(\\frac {Died} {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. The **minimum value** of the Gini index is 0, and occurs when there is only one class represented in a node. Thus, a node with a lower Gini index is said to be more \"pure\".\n",
      "\n",
      "**When deciding between splits**, the decision tree algorithm chooses the split that maximizes the resulting node purity. Let's pretend that gender was the split being considered, and the resulting nodes are as follows:\n",
      "\n",
      "- **Males:** 2 survived, 13 died\n",
      "- **Females:** 8 survived, 2 died\n",
      "\n",
      "To evaluate this split, we calculate the **weighted average of the Gini indices of the resulting nodes:**\n",
      "\n",
      "$$\\text{Males: } 1 - \\left(\\frac {2} {15}\\right)^2 - \\left(\\frac {13} {15}\\right)^2 = 0.23$$\n",
      "$$\\text{Females: } 1 - \\left(\\frac {8} {10}\\right)^2 - \\left(\\frac {2} {10}\\right)^2 = 0.32$$\n",
      "$$\\text{Weighted Average: } 0.23 \\left(\\frac {15} {25}\\right) + 0.32 \\left(\\frac {10} {25}\\right) = 0.27$$\n",
      "\n",
      "Thus, the decrease in Gini index (and gain in purity) from splitting on gender is **0.21**. The decision tree algorithm will choose this split if no other splits result in a larger gain in purity."
     ]
    },
    {
     "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](https://www.kaggle.com/c/titanic-gettingStarted/data) provided by Kaggle."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# read in the data\n",
      "titanic = pd.read_csv('https://raw.githubusercontent.com/justmarkham/DAT5/master/data/titanic_train.csv')\n",
      "titanic.head(10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\">\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",
        "    </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>male</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",
        "    </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>female</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",
        "    </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>female</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",
        "    </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>female</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",
        "    </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>male</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",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>5</th>\n",
        "      <td>6</td>\n",
        "      <td>0</td>\n",
        "      <td>3</td>\n",
        "      <td>Moran, Mr. James</td>\n",
        "      <td>male</td>\n",
        "      <td>NaN</td>\n",
        "      <td>0</td>\n",
        "      <td>0</td>\n",
        "      <td>330877</td>\n",
        "      <td>8.4583</td>\n",
        "      <td>NaN</td>\n",
        "      <td>Q</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>6</th>\n",
        "      <td>7</td>\n",
        "      <td>0</td>\n",
        "      <td>1</td>\n",
        "      <td>McCarthy, Mr. Timothy J</td>\n",
        "      <td>male</td>\n",
        "      <td>54</td>\n",
        "      <td>0</td>\n",
        "      <td>0</td>\n",
        "      <td>17463</td>\n",
        "      <td>51.8625</td>\n",
        "      <td>E46</td>\n",
        "      <td>S</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>7</th>\n",
        "      <td>8</td>\n",
        "      <td>0</td>\n",
        "      <td>3</td>\n",
        "      <td>Palsson, Master. Gosta Leonard</td>\n",
        "      <td>male</td>\n",
        "      <td>2</td>\n",
        "      <td>3</td>\n",
        "      <td>1</td>\n",
        "      <td>349909</td>\n",
        "      <td>21.0750</td>\n",
        "      <td>NaN</td>\n",
        "      <td>S</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>8</th>\n",
        "      <td>9</td>\n",
        "      <td>1</td>\n",
        "      <td>3</td>\n",
        "      <td>Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)</td>\n",
        "      <td>female</td>\n",
        "      <td>27</td>\n",
        "      <td>0</td>\n",
        "      <td>2</td>\n",
        "      <td>347742</td>\n",
        "      <td>11.1333</td>\n",
        "      <td>NaN</td>\n",
        "      <td>S</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>9</th>\n",
        "      <td>10</td>\n",
        "      <td>1</td>\n",
        "      <td>2</td>\n",
        "      <td>Nasser, Mrs. Nicholas (Adele Achem)</td>\n",
        "      <td>female</td>\n",
        "      <td>14</td>\n",
        "      <td>1</td>\n",
        "      <td>0</td>\n",
        "      <td>237736</td>\n",
        "      <td>30.0708</td>\n",
        "      <td>NaN</td>\n",
        "      <td>C</td>\n",
        "    </tr>\n",
        "  </tbody>\n",
        "</table>\n",
        "</div>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 19,
       "text": [
        "   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",
        "5            6         0       3   \n",
        "6            7         0       1   \n",
        "7            8         0       3   \n",
        "8            9         1       3   \n",
        "9           10         1       2   \n",
        "\n",
        "                                                Name     Sex  Age  SibSp  \\\n",
        "0                            Braund, Mr. Owen Harris    male   22      1   \n",
        "1  Cumings, Mrs. John Bradley (Florence Briggs Th...  female   38      1   \n",
        "2                             Heikkinen, Miss. Laina  female   26      0   \n",
        "3       Futrelle, Mrs. Jacques Heath (Lily May Peel)  female   35      1   \n",
        "4                           Allen, Mr. William Henry    male   35      0   \n",
        "5                                   Moran, Mr. James    male  NaN      0   \n",
        "6                            McCarthy, Mr. Timothy J    male   54      0   \n",
        "7                     Palsson, Master. Gosta Leonard    male    2      3   \n",
        "8  Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)  female   27      0   \n",
        "9                Nasser, Mrs. Nicholas (Adele Achem)  female   14      1   \n",
        "\n",
        "   Parch            Ticket     Fare Cabin Embarked  \n",
        "0      0         A/5 21171   7.2500   NaN        S  \n",
        "1      0          PC 17599  71.2833   C85        C  \n",
        "2      0  STON/O2. 3101282   7.9250   NaN        S  \n",
        "3      0            113803  53.1000  C123        S  \n",
        "4      0            373450   8.0500   NaN        S  \n",
        "5      0            330877   8.4583   NaN        Q  \n",
        "6      0             17463  51.8625   E46        S  \n",
        "7      1            349909  21.0750   NaN        S  \n",
        "8      2            347742  11.1333   NaN        S  \n",
        "9      0            237736  30.0708   NaN        C  "
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Let's choose our response variable and a few features, and review **how to handle categorical features**:\n",
      "\n",
      "- **Survived:** This is our response variable, and is already encoded as 0=died and 1=survived.\n",
      "- **Pclass:** These are the passenger class categories (1=first class, 2=second class, 3=third class). They are logically ordered, so we'll leave them as-is. (If the tree splits on this feature, the splits will occur at 1.5 or 2.5.)\n",
      "- **Sex:** This is a binary category, so we should encode it as 0=female and 1=male. (If the tree splits on this feature, the split will occur at 0.5.)\n",
      "- **Age:** This is a numeric feature, but we need to fill in the missing values.\n",
      "- **Embarked:** This is the port they embarked from. There are three unordered categories, so we should create dummy variables and drop one level as usual."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# 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 mean age\n",
      "titanic.Age.fillna(titanic.Age.mean(), inplace=True)\n",
      "\n",
      "# create three dummy variables, drop the first dummy variable, and store the two remaining columns as a DataFrame\n",
      "embarked_dummies = pd.get_dummies(titanic.Embarked, prefix='Embarked').iloc[:, 1:]\n",
      "\n",
      "# concatenate the two dummy variable columns onto the original DataFrame\n",
      "titanic = pd.concat([titanic, embarked_dummies], axis=1)\n",
      "\n",
      "# print the updated DataFrame\n",
      "titanic.head(10)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\">\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.000000</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.000000</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.000000</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.000000</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.000000</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",
        "    <tr>\n",
        "      <th>5</th>\n",
        "      <td>6</td>\n",
        "      <td>0</td>\n",
        "      <td>3</td>\n",
        "      <td>Moran, Mr. James</td>\n",
        "      <td>1</td>\n",
        "      <td>29.699118</td>\n",
        "      <td>0</td>\n",
        "      <td>0</td>\n",
        "      <td>330877</td>\n",
        "      <td>8.4583</td>\n",
        "      <td>NaN</td>\n",
        "      <td>Q</td>\n",
        "      <td>1</td>\n",
        "      <td>0</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>6</th>\n",
        "      <td>7</td>\n",
        "      <td>0</td>\n",
        "      <td>1</td>\n",
        "      <td>McCarthy, Mr. Timothy J</td>\n",
        "      <td>1</td>\n",
        "      <td>54.000000</td>\n",
        "      <td>0</td>\n",
        "      <td>0</td>\n",
        "      <td>17463</td>\n",
        "      <td>51.8625</td>\n",
        "      <td>E46</td>\n",
        "      <td>S</td>\n",
        "      <td>0</td>\n",
        "      <td>1</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>7</th>\n",
        "      <td>8</td>\n",
        "      <td>0</td>\n",
        "      <td>3</td>\n",
        "      <td>Palsson, Master. Gosta Leonard</td>\n",
        "      <td>1</td>\n",
        "      <td>2.000000</td>\n",
        "      <td>3</td>\n",
        "      <td>1</td>\n",
        "      <td>349909</td>\n",
        "      <td>21.0750</td>\n",
        "      <td>NaN</td>\n",
        "      <td>S</td>\n",
        "      <td>0</td>\n",
        "      <td>1</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>8</th>\n",
        "      <td>9</td>\n",
        "      <td>1</td>\n",
        "      <td>3</td>\n",
        "      <td>Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)</td>\n",
        "      <td>0</td>\n",
        "      <td>27.000000</td>\n",
        "      <td>0</td>\n",
        "      <td>2</td>\n",
        "      <td>347742</td>\n",
        "      <td>11.1333</td>\n",
        "      <td>NaN</td>\n",
        "      <td>S</td>\n",
        "      <td>0</td>\n",
        "      <td>1</td>\n",
        "    </tr>\n",
        "    <tr>\n",
        "      <th>9</th>\n",
        "      <td>10</td>\n",
        "      <td>1</td>\n",
        "      <td>2</td>\n",
        "      <td>Nasser, Mrs. Nicholas (Adele Achem)</td>\n",
        "      <td>0</td>\n",
        "      <td>14.000000</td>\n",
        "      <td>1</td>\n",
        "      <td>0</td>\n",
        "      <td>237736</td>\n",
        "      <td>30.0708</td>\n",
        "      <td>NaN</td>\n",
        "      <td>C</td>\n",
        "      <td>0</td>\n",
        "      <td>0</td>\n",
        "    </tr>\n",
        "  </tbody>\n",
        "</table>\n",
        "</div>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "   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",
        "5            6         0       3   \n",
        "6            7         0       1   \n",
        "7            8         0       3   \n",
        "8            9         1       3   \n",
        "9           10         1       2   \n",
        "\n",
        "                                                Name  Sex        Age  SibSp  \\\n",
        "0                            Braund, Mr. Owen Harris    1  22.000000      1   \n",
        "1  Cumings, Mrs. John Bradley (Florence Briggs Th...    0  38.000000      1   \n",
        "2                             Heikkinen, Miss. Laina    0  26.000000      0   \n",
        "3       Futrelle, Mrs. Jacques Heath (Lily May Peel)    0  35.000000      1   \n",
        "4                           Allen, Mr. William Henry    1  35.000000      0   \n",
        "5                                   Moran, Mr. James    1  29.699118      0   \n",
        "6                            McCarthy, Mr. Timothy J    1  54.000000      0   \n",
        "7                     Palsson, Master. Gosta Leonard    1   2.000000      3   \n",
        "8  Johnson, Mrs. Oscar W (Elisabeth Vilhelmina Berg)    0  27.000000      0   \n",
        "9                Nasser, Mrs. Nicholas (Adele Achem)    0  14.000000      1   \n",
        "\n",
        "   Parch            Ticket     Fare Cabin Embarked  Embarked_Q  Embarked_S  \n",
        "0      0         A/5 21171   7.2500   NaN        S           0           1  \n",
        "1      0          PC 17599  71.2833   C85        C           0           0  \n",
        "2      0  STON/O2. 3101282   7.9250   NaN        S           0           1  \n",
        "3      0            113803  53.1000  C123        S           0           1  \n",
        "4      0            373450   8.0500   NaN        S           0           1  \n",
        "5      0            330877   8.4583   NaN        Q           1           0  \n",
        "6      0             17463  51.8625   E46        S           0           1  \n",
        "7      1            349909  21.0750   NaN        S           0           1  \n",
        "8      2            347742  11.1333   NaN        S           0           1  \n",
        "9      0            237736  30.0708   NaN        C           0           0  "
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# create a list of the feature columns\n",
      "feature_cols = ['Pclass', 'Sex', 'Age', 'Embarked_Q', 'Embarked_S']"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# define X (features) and y (response)\n",
      "X = titanic[feature_cols]\n",
      "y = titanic.Survived"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# 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)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 23,
       "text": [
        "DecisionTreeClassifier(compute_importances=None, criterion='gini',\n",
        "            max_depth=3, max_features=None, max_leaf_nodes=None,\n",
        "            min_density=None, min_samples_leaf=1, min_samples_split=2,\n",
        "            random_state=1, splitter='best')"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# create a Graphviz file\n",
      "with open(\"tree_titanic.dot\", 'wb') as f:\n",
      "    f = export_graphviz(treeclf, out_file=f, 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"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 24
    },
    {
     "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! Why did this split occur?\n",
      "\n",
      "Although that split didn't affect the **classification error rate**, it did increase the **node purity**. Node purity is important because we're interested in the class proportions among the observations in each region."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "# compute the feature importances\n",
      "pd.DataFrame({'feature':feature_cols, 'importance':treeclf.feature_importances_})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "<div style=\"max-height:1000px;max-width:1500px;overflow:auto;\">\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>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 25,
       "text": [
        "      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"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Wrapping up decision trees\n",
      "\n",
      "Here are some advantages and disadvantages of decision trees that we haven't yet talked about:\n",
      "\n",
      "**Advantages:**\n",
      "\n",
      "- Can be specified as a series of rules, and are thought to more closely approximate human decision-making than other models\n",
      "- Non-parametric (will do better than 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:**\n",
      "\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",
      "- Can create biased trees if the classes are highly imbalanced\n",
      "\n",
      "Note that there is not just one decision tree algorithm; instead, there are many variations. A few common decision tree algorithms that are often referred to by name are C4.5, C5.0, and CART. (More details are available in the [scikit-learn documentation](http://scikit-learn.org/stable/modules/tree.html#tree-algorithms-id3-c4-5-c5-0-and-cart).) scikit-learn uses an \"optimized version\" of CART."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Resources\n",
      "\n",
      "- scikit-learn documentation: [Decision Trees](http://scikit-learn.org/stable/modules/tree.html)"
     ]
    }
   ],
   "metadata": {}
  }
 ]
}