decision_tree(classification and regression).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "**This notebook has been shamelessly copied from [Josh Gordon's github repo on decision tree](https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb) and have been modified by me for regression task as well.**\n",
    "\n",
    "Before you start please watch below video by Josh Gordon on decision trees [here](https://www.youtube.com/embed/LDRbO9a6XPU):\n",
    "<iframe width=\"700\" height=\"394\" src=\"https://www.youtube.com/embed/LDRbO9a6XPU\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen></iframe>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 530,
   "metadata": {},
   "outputs": [],
   "source": [
    "# For Python 2 / 3 compatability\n",
    "from __future__ import print_function\n",
    "import math\n",
    "from sklearn import datasets\n",
    "import numpy as np\n",
    "import seaborn as sns\n",
    "from sklearn.model_selection import train_test_split"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Toy dataset.\n",
    "# Format: each row is an example.\n",
    "# The last column is the label.\n",
    "# The first two columns are features.\n",
    "# Feel free to play with it by adding more features & examples.\n",
    "# Interesting note: I've written this so the 2nd and 5th examples\n",
    "# have the same features, but different labels - so we can see how the\n",
    "# tree handles this case.\n",
    "training_data = [\n",
    "    ['Green', 3, 'Apple'],\n",
    "    ['Yellow', 3, 'Apple'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 3, 'Lemon'],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Column labels.\n",
    "# These are used only to print the tree.\n",
    "header = [\"color\", \"diameter\", \"label\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unique_vals(rows, col):\n",
    "    \"\"\"Find the unique values for a column in a dataset.\"\"\"\n",
    "    return set([row[col] for row in rows])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Green', 'Red', 'Yellow'}"
      ]
     },
     "execution_count": 78,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "unique_vals(training_data, 0)\n",
    "# unique_vals(training_data, 1)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "metadata": {},
   "outputs": [],
   "source": [
    "def class_counts(rows):\n",
    "    \"\"\"Counts the number of each type of example in a dataset.\"\"\"\n",
    "    counts = {}  # a dictionary of label -> count.\n",
    "    for row in rows:\n",
    "        # in our dataset format, the label is always the last column\n",
    "        label = row[-1]\n",
    "        if label not in counts:\n",
    "            counts[label] = 0\n",
    "        counts[label] += 1\n",
    "    return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': 2, 'Grape': 2, 'Lemon': 1}"
      ]
     },
     "execution_count": 80,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "class_counts(training_data)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_numeric(value):\n",
    "    \"\"\"Test if a value is numeric.\"\"\"\n",
    "    return isinstance(value, int) or isinstance(value, float)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 342,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 342,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "is_numeric(7)\n",
    "# is_numeric(\"Red\")\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 406,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Question:\n",
    "    \"\"\"A Question is used to partition a dataset.\n",
    "\n",
    "    This class just records a 'column number' (e.g., 0 for Color) and a\n",
    "    'column value' (e.g., Green). The 'match' method is used to compare\n",
    "    the feature value in an example to the feature value stored in the\n",
    "    question. See the demo below.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, column, value):\n",
    "        self.column = column\n",
    "        self.value = value\n",
    "\n",
    "    def match(self, example):\n",
    "        # Compare the feature value in an example to the\n",
    "        # feature value in this question.\n",
    "        val = example[self.column]\n",
    "        if is_numeric(val):\n",
    "            return val >= self.value\n",
    "        else:\n",
    "            return val == self.value\n",
    "\n",
    "    def __repr__(self):\n",
    "        # This is just a helper method to print\n",
    "        # the question in a readable format.\n",
    "        condition = \"==\"\n",
    "        if is_numeric(self.value):\n",
    "            condition = \">=\"\n",
    "        return \"Is %s %s %s?\" % (\n",
    "            header[self.column], condition, str(self.value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 407,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Is diameter >= 3?"
      ]
     },
     "execution_count": 407,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Let's write a question for a numeric attribute\n",
    "Question(1, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 408,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Is color == Green?"
      ]
     },
     "execution_count": 408,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How about one for a categorical attribute\n",
    "q = Question(0, 'Green')\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 409,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 409,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let's pick an example from the training set...\n",
    "example = training_data[0]\n",
    "# ... and see if it matches the question\n",
    "q.match(example) # this will be true, since the first example is Green.\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 347,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(rows, question):\n",
    "    \"\"\"Partitions a dataset.\n",
    "\n",
    "    For each row in the dataset, check if it matches the question. If\n",
    "    so, add it to 'true rows', otherwise, add it to 'false rows'.\n",
    "    \"\"\"\n",
    "    true_rows, false_rows = [], []\n",
    "    for row in rows:\n",
    "        if question.match(row):\n",
    "            true_rows.append(row)\n",
    "        else:\n",
    "            false_rows.append(row)\n",
    "    return true_rows, false_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 348,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Red', 1, 'Grape'], ['Red', 1, 'Grape']]"
      ]
     },
     "execution_count": 348,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Let's partition the training data based on whether rows are Red.\n",
    "true_rows, false_rows = partition(training_data, Question(0, 'Red'))\n",
    "# This will contain all the 'Red' rows.\n",
    "true_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 349,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']]"
      ]
     },
     "execution_count": 349,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# This will contain everything else.\n",
    "false_rows\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 350,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(rows):\n",
    "    \"\"\"Calculate the Gini Impurity for a list of rows.\n",
    "\n",
    "    There are a few different ways to do this, I thought this one was\n",
    "    the most concise. See:\n",
    "    https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity\n",
    "    \"\"\"\n",
    "    counts = class_counts(rows)\n",
    "    impurity = 1\n",
    "    for lbl in counts:\n",
    "        prob_of_lbl = counts[lbl] / float(len(rows))\n",
    "        impurity -= prob_of_lbl**2\n",
    "    return impurity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 351,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 351,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Let's look at some example to understand how Gini Impurity works.\n",
    "#\n",
    "# First, we'll look at a dataset with no mixing.\n",
    "no_mixing = [['Apple'],\n",
    "              ['Apple']]\n",
    "# this will return 0\n",
    "gini(no_mixing)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 352,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 352,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now, we'll look at dataset with a 50:50 apples:oranges ratio\n",
    "some_mixing = [['Apple'],\n",
    "               ['Orange']]\n",
    "# this will return 0.5 - meaning, there's a 50% chance of misclassifying\n",
    "# a random example we draw from the dataset.\n",
    "gini(some_mixing)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 353,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7999999999999998"
      ]
     },
     "execution_count": 353,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now, we'll look at a dataset with many different labels\n",
    "lots_of_mixing = [['Apple'],\n",
    "                  ['Orange'],\n",
    "                  ['Grape'],\n",
    "                  ['Grapefruit'],\n",
    "                  ['Blueberry']]\n",
    "# This will return 0.8\n",
    "gini(lots_of_mixing)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 354,
   "metadata": {},
   "outputs": [],
   "source": [
    "def info_gain(left, right, current_uncertainty):\n",
    "    \"\"\"\n",
    "    Information Gain.\n",
    "\n",
    "    The uncertainty of the starting node, minus the weighted impurity of\n",
    "    two child nodes.\n",
    "    \"\"\"\n",
    "    p = float(len(left)) / (len(left) + len(right))\n",
    "    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)\n",
    "\n",
    "def mse(left, right):\n",
    "    \"\"\"\n",
    "    Compute MSE on both the subtree (left and right)\n",
    "    \"\"\"\n",
    "    # get the number of datapoints\n",
    "    n_left = len(left)\n",
    "    n_right = len(right)\n",
    "    \n",
    "    # mean of target on left and right split\n",
    "    left_mean_score = sum([row[-1] for row in left])/ n_left\n",
    "    right_mean_score = sum([row[-1] for row in right])/ n_right\n",
    "    \n",
    "    # compute mse of target on for left and right split\n",
    "    left_mse = sum([pow(left_mean_score - row[-1], 2) for row in left])/ n_left\n",
    "    right_mse = sum([pow(right_mean_score - row[-1], 2) for row in right])/ n_right\n",
    "    \n",
    "    # return sum of MSE\n",
    "    return left_mse + right_mse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 355,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6399999999999999"
      ]
     },
     "execution_count": 355,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Calculate the uncertainy of our training data.\n",
    "current_uncertainty = gini(training_data)\n",
    "current_uncertainty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 356,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.1399999999999999"
      ]
     },
     "execution_count": 356,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How much information do we gain by partioning on 'Green'?\n",
    "true_rows, false_rows = partition(training_data, Question(0, 'Green'))\n",
    "info_gain(true_rows, false_rows, current_uncertainty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 357,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.37333333333333324"
      ]
     },
     "execution_count": 357,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What about if we partioned on 'Red' instead?\n",
    "true_rows, false_rows = partition(training_data, Question(0,'Red'))\n",
    "info_gain(true_rows, false_rows, current_uncertainty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 358,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Red', 1, 'Grape'], ['Red', 1, 'Grape']]"
      ]
     },
     "execution_count": 358,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# It looks like we learned more using 'Red' (0.37), than 'Green' (0.14).\n",
    "# Why? Look at the different splits that result, and see which one\n",
    "# looks more 'unmixed' to you.\n",
    "true_rows, false_rows = partition(training_data, Question(0,'Red'))\n",
    "\n",
    "# Here, the true_rows contain only 'Grapes'.\n",
    "true_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 359,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']]"
      ]
     },
     "execution_count": 359,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# And the false rows contain two types of fruit. Not too bad.\n",
    "false_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 360,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Green', 3, 'Apple']]"
      ]
     },
     "execution_count": 360,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# On the other hand, partitioning by Green doesn't help so much.\n",
    "true_rows, false_rows = partition(training_data, Question(0,'Green'))\n",
    "\n",
    "# We've isolated one apple in the true rows.\n",
    "true_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 361,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Yellow', 3, 'Apple'],\n",
       " ['Red', 1, 'Grape'],\n",
       " ['Red', 1, 'Grape'],\n",
       " ['Yellow', 3, 'Lemon']]"
      ]
     },
     "execution_count": 361,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# But, the false-rows are badly mixed up.\n",
    "false_rows\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 362,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best_split(rows, p_type= \"classification\"):\n",
    "    \"\"\"Find the best question to ask by iterating over every feature / value\n",
    "    and calculating the information gain.\"\"\"\n",
    "    best_gain = 0  # keep track of the best information gain\n",
    "    best_mse = math.inf # best error so far (the smaller the better)\n",
    "    best_question = None  # keep train of the feature / value that produced it\n",
    "    n_features = len(rows[0]) - 1  # number of columns\n",
    "    \n",
    "    # if it is a classification task, compute gini impurity\n",
    "    if p_type == \"classification\":\n",
    "        current_uncertainty = gini(rows)\n",
    "        \n",
    "    for col in range(n_features):  # for each feature\n",
    "\n",
    "        values = set([row[col] for row in rows])  # unique values in the column\n",
    "\n",
    "        for val in values:  # for each value\n",
    "\n",
    "            question = Question(col, val)\n",
    "\n",
    "            # try splitting the dataset\n",
    "            true_rows, false_rows = partition(rows, question)\n",
    "\n",
    "            # Skip this split if it doesn't divide the\n",
    "            # dataset.\n",
    "            if len(true_rows) == 0 or len(false_rows) == 0:\n",
    "                continue\n",
    "\n",
    "            # Calculate the information gain from this split\n",
    "            if p_type == \"classification\":\n",
    "                gain = info_gain(true_rows, false_rows, current_uncertainty)\n",
    "                # You actually can use '>' instead of '>=' here\n",
    "                # but I wanted the tree to look a certain way for our\n",
    "                # toy dataset.\n",
    "                if gain >= best_gain:\n",
    "                    best_gain, best_question = gain, question\n",
    "            \n",
    "            # Calculate mse this split\n",
    "            else:\n",
    "                mse = mse(true_rows, false_rows, current_mse)\n",
    "                if mse <= best_mse:\n",
    "                    best_mse = mse\n",
    "                    \n",
    "        # return best_gain, best_question if p_type == \"classification\" else best_mse, best_question\n",
    "        if p_type == \"classification\":\n",
    "            return best_gain, best_question\n",
    "        else:\n",
    "            return best_mse, best_question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 363,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0.37333333333333324, Is color == Red?)\n"
     ]
    }
   ],
   "source": [
    "a = find_best_split(training_data)\n",
    "print(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 364,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Is color == Red?"
      ]
     },
     "execution_count": 364,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Find the best question to ask first for our toy dataset.\n",
    "best_gain, best_question = find_best_split(training_data)\n",
    "best_question\n",
    "# FYI: is color == Red is just as good. See the note in the code above\n",
    "# where I used '>='.\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 412,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Leaf:\n",
    "    \"\"\"A Leaf node classifies data.\n",
    "\n",
    "    This holds a dictionary of class (e.g., \"Apple\") -> number of times\n",
    "    it appears in the rows from the training data that reach this leaf.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, rows):\n",
    "        self.predictions = class_counts(rows)\n",
    "\n",
    "class LeafReg:\n",
    "    \"\"\"\n",
    "    A Leaf node predicts data.\n",
    "    It returns average of all the datapoints in the current leaf\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, rows):\n",
    "        # our predictions will be average target all the rows at leaf node\n",
    "        self.predictions = sum([row[-1] for row in rows])/ len(rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 505,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Decision_Node:\n",
    "    \"\"\"A Decision Node asks a question.\n",
    "\n",
    "    This holds a reference to the question, and to the two child nodes.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self,\n",
    "                 question,\n",
    "                 true_branch,\n",
    "                 false_branch):\n",
    "        self.question = question\n",
    "        self.true_branch = true_branch\n",
    "        self.false_branch = false_branch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 531,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_tree(rows, p_type= \"classification\", counter = 0, max_depth= 30):\n",
    "    \"\"\"Builds the tree.\n",
    "\n",
    "    Rules of recursion: 1) Believe that it works. 2) Start by checking\n",
    "    for the base case (no further information gain). 3) Prepare for\n",
    "    giant stack traces.\n",
    "    \"\"\"\n",
    "    \n",
    "\n",
    "    # Try partitioing the dataset on each of the unique attribute,\n",
    "    # calculate the information gain,\n",
    "    # and return the question that produces the highest gain.\n",
    "    gain, question = find_best_split(rows)\n",
    "\n",
    "    # Base case: no further info gain\n",
    "    # Since we can ask no further questions,\n",
    "    # we'll return a leaf.\n",
    "    # or current_depth > max_depth\n",
    "    '''\n",
    "    Different leaf node for classification and regression\n",
    "    '''\n",
    "    if (gain == 0 and p_type == \"classification\") :\n",
    "        return Leaf(rows)\n",
    "    elif gain == 0 and p_type == \"regression\":\n",
    "        return LeafReg(rows)\n",
    "\n",
    "    # If we reach here, we have found a useful feature / value\n",
    "    # to partition on.\n",
    "    true_rows, false_rows = partition(rows, question)\n",
    "\n",
    "    # Recursively build the true branch.\n",
    "    true_branch = build_tree(true_rows, p_type= p_type)\n",
    "\n",
    "    # Recursively build the false branch.\n",
    "    false_branch = build_tree(false_rows, p_type= p_type)\n",
    "\n",
    "    # Return a Question node.\n",
    "    # This records the best feature / value to ask at this point,\n",
    "    # as well as the branches to follow\n",
    "    # dependingo on the answer.\n",
    "    return Decision_Node(question, true_branch, false_branch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 507,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_tree(node, spacing=\"\"):\n",
    "    \"\"\"World's most elegant tree printing function. * Classification\"\"\"\n",
    "\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, Leaf):\n",
    "        print (spacing + \"Predict\", node.predictions)\n",
    "        return\n",
    "\n",
    "    # Print the question at this node\n",
    "    print (spacing + str(node.question))\n",
    "\n",
    "    # Call this function recursively on the true branch\n",
    "    print (spacing + '--> True:')\n",
    "    print_tree(node.true_branch, spacing + \"  \")\n",
    "\n",
    "    # Call this function recursively on the false branch\n",
    "    print (spacing + '--> False:')\n",
    "    print_tree(node.false_branch, spacing + \"  \")\n",
    "\n",
    "def print_tree_reg(node, spacing=\"\"):\n",
    "    \"\"\"World's most elegant tree printing function. * Regression\"\"\"\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, LeafReg):\n",
    "        print (spacing + \"Predict\", node.predictions)\n",
    "        return\n",
    "\n",
    "    # Print the question at this node\n",
    "    print (spacing + str(node.question))\n",
    "\n",
    "    # Call this function recursively on the true branch\n",
    "    print (spacing + '--> True:')\n",
    "    print_tree_reg(node.true_branch, spacing + \"  \")\n",
    "\n",
    "    # Call this function recursively on the false branch\n",
    "    print (spacing + '--> False:')\n",
    "    print_tree_reg(node.false_branch, spacing + \"  \")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classification Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 508,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_tree = build_tree(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 509,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is x == Red?\n",
      "--> True:\n",
      "  Predict {'Grape': 2}\n",
      "--> False:\n",
      "  Is x == Yellow?\n",
      "  --> True:\n",
      "    Predict {'Apple': 1, 'Lemon': 1}\n",
      "  --> False:\n",
      "    Predict {'Apple': 1}\n"
     ]
    }
   ],
   "source": [
    "print_tree(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 510,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify(row, node):\n",
    "    \"\"\"See the 'rules of recursion' above.\"\"\"\n",
    "\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, Leaf):\n",
    "        return node.predictions\n",
    "\n",
    "    # Decide whether to follow the true-branch or the false-branch.\n",
    "    # Compare the feature / value stored in the node,\n",
    "    # to the example we're considering.f\n",
    "    if node.question.match(row):\n",
    "        return classify(row, node.true_branch)\n",
    "    else:\n",
    "        return classify(row, node.false_branch)\n",
    "\n",
    "def predict(row, node):\n",
    "    \"\"\"See the 'rules of recursion' above.\"\"\"\n",
    "\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, LeafReg):\n",
    "        return node.predictions\n",
    "\n",
    "    # Decide whether to follow the true-branch or the false-branch.\n",
    "    # Compare the feature / value stored in the node,\n",
    "    # to the example we're considering.f\n",
    "    if node.question.match(row):\n",
    "        return predict(row, node.true_branch)\n",
    "    else:\n",
    "        return predict(row, node.false_branch)\n",
    "    \n",
    "    \n",
    "class Question:\n",
    "    \"\"\"A Question is used to partition a dataset.\n",
    "\n",
    "    This class just records a 'column number' (e.g., 0 for Color) and a\n",
    "    'column value' (e.g., Green). The 'match' method is used to compare\n",
    "    the feature value in an example to the feature value stored in the\n",
    "    question. See the demo below.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, column, value):\n",
    "        self.column = column\n",
    "        self.value = value\n",
    "\n",
    "    def match(self, example):\n",
    "        # Compare the feature value in an example to the\n",
    "        # feature value in this question.\n",
    "        val = example[self.column]\n",
    "        if is_numeric(val):\n",
    "            return val >= self.value\n",
    "        else:\n",
    "            return val == self.value\n",
    "\n",
    "    def __repr__(self):\n",
    "        # This is just a helper method to print\n",
    "        # the question in a readable format.\n",
    "        condition = \"==\"\n",
    "        if is_numeric(self.value):\n",
    "            condition = \">=\"\n",
    "        return \"Is %s %s %s?\" % (\n",
    "            header[self.column], condition, str(self.value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 511,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': 1}"
      ]
     },
     "execution_count": 511,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# The tree predicts the 1st row of our\n",
    "# training data is an apple with confidence 1.\n",
    "classify(training_data[0], my_tree)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 512,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_leaf(counts):\n",
    "    \"\"\"A nicer way to print the predictions at a leaf.\"\"\"\n",
    "    total = sum(counts.values()) * 1.0\n",
    "    probs = {}\n",
    "    for lbl in counts.keys():\n",
    "        probs[lbl] = str(int(counts[lbl] / total * 100)) + \"%\"\n",
    "    return probs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 513,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': '100%'}"
      ]
     },
     "execution_count": 513,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Printing that a bit nicer\n",
    "print_leaf(classify(training_data[0], my_tree))\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 514,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': '50%', 'Lemon': '50%'}"
      ]
     },
     "execution_count": 514,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# On the second example, the confidence is lower\n",
    "print_leaf(classify(training_data[1], my_tree))\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 515,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Evaluate\n",
    "testing_data = [\n",
    "    ['Green', 3, 'Apple'],\n",
    "    ['Yellow', 4, 'Apple'],\n",
    "    ['Red', 2, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 3, 'Lemon'],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 516,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Actual: Apple. Predicted: {'Apple': '100%'}\n",
      "Actual: Apple. Predicted: {'Apple': '50%', 'Lemon': '50%'}\n",
      "Actual: Grape. Predicted: {'Grape': '100%'}\n",
      "Actual: Grape. Predicted: {'Grape': '100%'}\n",
      "Actual: Lemon. Predicted: {'Apple': '50%', 'Lemon': '50%'}\n"
     ]
    }
   ],
   "source": [
    "for row in testing_data:\n",
    "    print (\"Actual: %s. Predicted: %s\" %\n",
    "           (row[-1], print_leaf(classify(row, my_tree))))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Regression Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 517,
   "metadata": {},
   "outputs": [],
   "source": [
    "# generating toy dataset\n",
    "x, y = datasets.make_regression(n_samples=100, n_features=1, n_informative=1, noise=5, random_state= 1)\n",
    "X_train, X_test, y_train, y_test = train_test_split(\n",
    "    x, y, test_size=0.2, random_state=42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 518,
   "metadata": {},
   "outputs": [],
   "source": [
    "# combine features and lables into one 2d array\n",
    "data = np.hstack([X_train, np.expand_dims(y_train, 1)])\n",
    "data_test = np.hstack([X_test, np.expand_dims(y_test, 1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 519,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Text(0.5, 1.0, 'Toy linear regression dataset')"
      ]
     },
     "execution_count": 519,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAX8AAAEICAYAAAC3Y/QeAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy8QZhcZAAAgAElEQVR4nO3df3xcZZn38c81SSadpKVJ07TQpqVYS9fiU4RGRLqrKAjostutpYoIRdGWWlxcdlXgQR53l2UXKMhLlp8FUaoiINgHFn+AsMvyLIiQWqxQDLT8sKE/EkJC0zTNJJnr+WPOhJlk8qPNTCaZ+b5fr3ll5pwzc+5M2mvuue/rXLe5OyIiUlhCuW6AiIiMPgV/EZECpOAvIlKAFPxFRAqQgr+ISAFS8BcRKUAK/pIxZnaamW1NerzNzD6cyzaNV2ZWamZ7zWzGKJzrHjP7VrbPI2OLgn8BCIJI4hYzs46kx5/P1nndfa67/yZbr5/P3L3T3Se6+45ctyWZmT1jZmfny3kKWXGuGyDZ5+4TE/fN7HXgy+7+WO5alD1mVuzu3SM9JtPnFBlr1PMXzCxiZjeZ2U4zazCztWZWEuzbamafSDp2gpm9Y2bvG8br7jKzPw/uX2VmPzazn5hZm5ltNrMPJB07y8weNLO3zOxVM1udtG+xmf02OO8OM7vezIqT2uNm9hUz2wa8kKYdf2Zm3Wa20sy2A78Itv9F8LqtZvY7M1uc9Jz3mtlTQVt/ZWa3mdkdI3i9lWb2evB6r5rZ8qTX+p/gd2sys/V9fq+a4PEUM7s7OOY1M/ummVmwb7WZPW5mNwTn3mZmJw/ydznOzH4ftOVHQDhpX7WZ/TI4z9vB3+SwYN91wAeBO4JvjdcF228J/t3sMbNnzez4Pn+7TcG+XWb2b0n70r5fA51HMszddSugG/A6cHKfbdcA/w+YCkwHngMuC/b9H+CupGM/Czw3wGufBmxNerwL+PPg/lXAPuATQBFwPfBEsK8I+ANwMfFAdCTwJ+Cjwf7jiAeDImAusBVYHeybADjwc6ACiKRp158Fx9wBlAERYA7QDJxMvBP0KaAJqAye8zvgyqA9JwLtwB0H83rBrRWYGzx/JvC+4P4G4OuABa+zuM/vVRM8vg/4KTAReC/wGvD5YN9qoAtYEbxHFwGvD/A3mgDsANYAJcDngW7gW8H+6cCSoC2TgQeBe5Ke/wxwdp/XXBH8jiXAZcB2oCTYtwlYHtyfBHwouD/U+9/vPLplOBbkugG6jfIfPH3wfxP4eNLjJcAfg/tzgHeAsuDxw8CFA7z2UMH/4aR9xwKtwf2PAq/0ea1/Am4Z4DyXAD8J7ieC5AmD/M6JYD0jadu3gdv7HPffxD/cjgQ6gNKkfffTP/gP9/USwX8JMKHPMfcBNwKH9dneG/yBUqAHeE/S/q8BvwrurwZeSNo3JXhuRZr34hTgtT7bfkcQ/NMcfzywM+nxoEGZ+IfYPmB+8PhZ4h8IVX2OG/D9Gs55dBv5TcM+BS4YOjgUeCNp8xvEe6e4++vEe29LzKwa+Dhwz0GeblfS/X3Ee7EAhwNzgq//rWbWCvx90C7MbEEwFLHbzPYQ/zYytc9rbx/i3DFPnTw9HDi7zzlrgRnBrcndOwd5/WG/nru3EO9hXwjsMrOHzOy9wfMuIv7tYVMwFJZukvNQ4r3jPyVt6/0bBfq+t/Du+5tsBtDQZ1vv397MJpnZnWb2p+C9fpT+73UKM7vUzOrN7B2ghfgHV+I55wILgZeDIZ5Tg+2Dvf8yChT8C5zHu1m7iP9nTJhN/NtAwl3A2cCZwH+6e2OGm7Gd+DeNiqTbJHdfGuy/nXjvdK67HwL8M/EeZsqvMsQ5+u7fTrwnn3zOcne/HtgJVJtZadLxs0bwerj7z939JOLB7U/ALcH2N939POAw4h8Od5rZ7D6vvQuIEf+7JPT9Gw3XTuLfJpIlv+4lwf4PBu/1KaS+1ym/t8Xng/4WWEp82G0K8W9NBuDuL7n7Z4FpwA3Az8wszBDvV9/zSOYp+AvAT4Bvm1mVmU0j/jX9R0n77wf+HPgKsD4L5/8fADP7u2Cis9jMFprZscH+ScA77r7XzI4CVmbgnHcBy83sJDMrsvik90lmdijwMvBH4FtmVmJmHyE+pHVQr2dmM83sL82sDOgE9hIfxsHMPmtmM4IP4dbgtVIyh4JvIBuAfzWzcjObS3zYJ/lvNFxPAhOCSeJiM/sc8Z55wiTi3xxazWwq0Df/fzfwnj7HdxEfrw8T/2CekNhpZivMrMrde4gPHzrxD7LB3v9055EMU/AXiA+jbAFeBJ4HniI+CQyAu7cB/0F8mOGhTJ/c3buIT/idQHwIool4zzgxbHER8GUz2wvcBNybgXO+CiwjPrfwVnDerwGhIBCfSXwysgX438QnWzvTv9rgr0d8EvZS4j34ZuKT138bPPXDwMbgd/spsMrT5/afH/x8A/hP4pPNPz6I37uDeC99TfC7/SXxv23CtcSHbJqJfyj/os9LXA+sMLMWM7smeO6TwDbg1eB3b0o6/nSg3szagH8DPuPu3UO8X+nOIxlm8X/nIoMzs38Fprn7l3PdllwwsweBZ9z934Y8WGQcUM9fhhRM9H4BWJfjpowaM/uQmc0xs5CZ/RXxYZ+Mf+sRyRUFfxmUmX2VeHroT9392Rw3ZzTVEB/22AusBc5z9xdz2ySRzNGwj4hIAVLPX0SkAI2bwm5Tp071OXPm5LoZIiLjxsaNG99y9+p0+8ZN8J8zZw51dXW5boaIyLhhZm8MtE/DPiIiBUjBX0SkACn4i4gUIAV/EZECpOAvIlKAxk22j4hIoYjFnOb2KNHuHsLFRVSVhwmF+lYxHxkFfxGRMSQWc+p3t7FyfR0NLR3UVEa4fUUt86dPyugHgIZ9RETGkOb2aG/gB2ho6WDl+jqa26MZPY+Cv4jIGBLt7ukN/AkNLR1Eu3syeh4FfxGRMSRcXERNZSRlW01lhHBxUUbPo+AvIpJDsZjT1NbJmy37aGrrpDJSwu0rans/ABJj/lXl4YyeVxO+IiI5MtDk7rzqiWxYszir2T7q+YuI5MhAk7stHV1UTyplZmUZ1ZNKMx74QcFfRCRnRmtyNx0FfxGRHBmtyd10FPxFRHKkqjw8KpO76WjCV0QkR0IhY/70SVmf3E1HwV9EJIdCIaN6Uunon3fUzygiIjmn4C8iUoAyEvzN7E4zazSzF5K2/aOZvWlmzwe3TyXtu9TMtppZvZmdmok2iIjI8GVqzP8HwI3A+j7br3f3a5M3mNkC4EzgKGAG8JiZHenu2U9sFREZwmjU0h8LMhL83f1JM5szzMOXAPe4eyfwmpltBY4DfpOJtoiIHKzRqqU/FmR7zP+rZrY5GBaqDLbNBLYnHdMQbOvHzFaZWZ2Z1TU1NWW5qSJS6Earlv5YkM3gfwswF/gAsBO4Ltie7uPT072Au69z91p3r62urs5OK0VEAunKLVRPLCXa3dNbdTMWSxuuxp2s5fm7++7EfTO7HXg4eNgAzEo6tAbYka12iIgMV6LcQuID4JhZFXzztPl8dt0zeTcMlLWev5kdlvRwKZDIBHoIONPMSs3sCGAe8Gy22iEiMlx9yy1ceNI8vnH/5rwcBspIz9/MfgKcCEw1swbg28CJZvYB4kM6rwPnA7j7i2Z2H7AF6AYuUKaPiORK3+ye5Fr6Pe45q7qZbZnK9vlcms3fG+T4K4ErM3FuEZGDNVR2T1NbZ8owEIxe1c1s0xW+IlKwkrN7jplVweWnL6C9s5tde/YTi3lOq25mmwq7iUjBSmT3HDOrgq+fOp+LH9jc7xtArqpuZpt6/iJSsBLZPatPnNsb+CF1YjdRdTObSyrmgnr+IpL3BirZkBjWae/sztuJ3YEo+ItIXhtqUnf+9Ens2rM/byd2B6JhHxHJa0OVbAiFjEMPmZC3E7sDUc9fRPJaupINfYd0crmcYq4o+ItIXutbsgHSD+nkajnFXNGwj4jktXzO1R8J9fxFJK8V4pDOcCj4i0jeSZfaWUhDOsOh4C8ieaWQVuMaCY35i0heKaTVuEZCwV9E8spwUjtFwV9E8kwitTNZvl+tezAU/EVkzIrFnKa2zgNaP1epncOjCV8RGZMOduJWqZ3Do56/iIxJI5m4zdcyzJmUkeBvZneaWaOZvZC0bYqZ/drMXgl+VgbbzcxuMLOtZrbZzI7NRBtEJL9o4ja7MtXz/wFwWp9tlwCPu/s84PHgMcAngXnBbRVwS4baICJ5RBO32ZWR4O/uTwJv99m8BLgruH8X8DdJ29d73DNAhZkdlol2iMj4ljzB6zjrzztOE7dZks0J3+nuvhPA3Xea2bRg+0xge9JxDcG2nX1fwMxWEf92wOzZs7PYVBEZbbGY09oRpSPaQ487E4qL2NvZzYo7n02Z4H3oq4vpiGriNtNyMeGb7i+XNn/L3de5e62711ZXV2e5WSIyWmIx5/Xmdup3tfHZdc/wkWue4NO3PE3z3k6qJ8Zr8CQmeHtiaOI2C7IZ/HcnhnOCn43B9gZgVtJxNcCOLLZDRMaY5vYobzTv4xv3py6aftF9v2f1iXN7j9MEb/ZkM/g/BJwb3D8XeDBp+4og6+d44J3E8JCIFIZodw9l4aK02TwVkZLex5rgzZ6MjPmb2U+AE4GpZtYAfBu4CrjPzL4E/AlYHhz+C+BTwFZgH/DFTLRBRMaPkuIQITO+/4UPUhYuorWji1uf2EbT3k72ReM9fU3wZpe5D3259FhQW1vrdXV1uW6GiCRJVzd/OOPyrfs62f52B1/58e96J3fXnrGQaZNKqSwPa4I3Q8xso7vXptunK3xF5KAkyi8svfkpFl/9Xyy9+Snqd7cNq/5Oe2dPb+CH+HDPN+7fTKSkiCnlujJ3NCj4i8hBGUn5hR73tOP93eNjICIvqLCbiAxb8jDPQAF8ONk5E0riV+8mP7+mMsKEEvVHR4veaREZlr7DPNsa2w+6/MLU8tK0ZZenlmud3dGinr+IDEvfYZ4bHn+FtWcs7M3VP5DsHJVdzj0FfxEZlr5VNjdtb+WaX9Vz76rjATAziiz+ITGcQJ4ouyy5oeAvIsOSqLKZ+AA4ZlYFF540j54gu+dffv4ij25pHPaiK5JbGvMXkX7SLZ+YvDziMbMq+OZp87n8wRf4yNonOOuO33LuCUdwzKyKA8r6kdxRz19EUgy2fOL86ZO47/wP09ndwznfezYlzfPiBzZz+ekLOP+HG1WTZxxQz19EUgyUv9/aEaW1I0pndw+NezoHrcujmjxjn3r+IpIi3fKJ1RNL2dm6n8a2zt5t6fL0Wzu6VJNnnFDPX0RSpFs+8cKT5nH+jzZSFi7ihsdfobK8hLVnLEzJ07/t7EV8oGYyG9Ys1mTvOKDgLyIpkid2IR7Yj5haTkNLB60dXTTt7eSfHtoCwA/PO47H//6jrD/vOL77+Mu8va9L+frjhKp6ikhK2YZIuIjuHmd/dw9FZvHHMefTNz9N9cRSvn7qfC5+4N0Lu65etpBrH6ln0/ZWaiojbFizWPn7Y8RgVT015i9S4JKze6onlvLN0+b3u2p3XvVEbl9Ry8r1dVz7SD1XLHk/c6aW82bLvt7AD1p5azxR8BcpEAPV3k/O7rn89AX9llZcub6udxw/uRxDUQjO+d4f+k36KstnfFDwFykAg+XuJ2f3VERKBqzU2bccQyzmvd8GDrS2j+Segr9IARgod3/DmsUpZRsSqZrD6c2rONv4lvVsHzN73cz+YGbPm1ldsG2Kmf3azF4JflZmux0ihSy5d3/MrApuO2cR1y0/mmh3D5WRkt7snluf2NYvhXOw3nzi24BW3hp/Rqvn/zF3fyvp8SXA4+5+lZldEjy+eJTaIlJwEr37dNk6iQndRA8+Ei7iZ2tOoKs7pt58Hst6qqeZvQ7UJgd/M6sHTnT3nWZ2GPCEu88f7HWU6ily8Lq7Y9Q3ttG4p5PLH3yh37CO0jPzU64XcHfgUTPbaGargm3T3X0nQPBzWronmtkqM6szs7qmpqZRaKpI/onFnFea9vLdx15m1pTIgBO6UlhGI/gvdvdjgU8CF5jZR4b7RHdf5+617l5bXV2dvRaK5LHEZO+jWxrZ1nTwSy9Kfsl68Hf3HcHPRmADcBywOxjuIfjZmO12iBSq5MneW5/YxtXLhj+hK/krqxO+ZlYOhNy9Lbh/CvDPwEPAucBVwc8Hs9kOkUISizlvtXeyvytenqGkKNSbvrlpe2vvFbpzp00kUqIJ3UKV7Wyf6cAGM0uc6253/5WZPQfcZ2ZfAv4ELM9yO0TyTrordoF+F3Nd/5mj+cEXP8gXvv8cDS0dNO3t5NDJE6ipiCjoFzAVdhMZh2Ix5/Xmdt5o3kdZuIh90R4OrypjclkxS258ul82z7XLj2b2lDLcXembBUSF3UTyTGtHlN179vembdZURlh7xkLKwuVps3kMcHdmVpblpsEy5qiev8g4klhYfV+0p18Btm/cv5muHu+dzE1cyXv/6g9TNbGUSFgZPfIuBX+RcSJRnG3pzU+xv6v/UosNLR1Ee2Jct/xoTlkwja+fOp8rHt7CGbf+hi98/1l27+kkFhsfw7ySfQr+ImNUopf/Zss+mto6ae14tzjbrnf2p83Xb2rr5Kpf/pGLP/m+3hIO8G4ht+b2aC5+FRmDFPxFxqDu7hgNLft4o7mdF3bs4bINm9nZup8T3lMFwHWPvsx1y49Ozdc/p5Zpk0pp2tvJW22dupJXBqUJX5ExJhZz6hvbOP+HG1OWSvzu4y9z6afexyuNe9m0vZWrfvnHfvn6QG+BtuGWZpbCpJ6/yBjT3B7tDfwQ77Ff/MBmli2aRfPeKBd/8s8AUvL1E+WUEyWWD5sc6bcIu67klWTq+YvkwEBLKkJqOYaEhpYOqsrDNLdHed+hk3jq4o8Nmq+vhVZkKAr+IqMkOeD3xJx/+fkWHt3SSE1lhNvOXsRhFROoiIRTVtZKqKmMMKU8zLont/HtvzpqWPn6fZddFEmm4C8yCtKtoXvd8qP54uIjCJnRGOTuT5zQybzqif3Wxr3prGO599k3+OLiI5SvLxmh8g4iWdB3WKcoBH9941P9evPXf+YDvL0vSlV5mGmHlNK6r4uKshImlhbT3eN0dPXQ1eN0RLt5a2+Uw6vKmFNVruEbGRaVdxAZRel6+bedvYjqiaUpwb96YikTSkJc8fCWlBIN337wRZr2dvYur9jS0UWkJMShkyMat5eMUbaPSIYlFk9JztY5/0cbufCkeSnHXXjSPL7y49/1K9FwzRkLqZ5Yysr1dbR0dGmBdMkKBX+RDBsoW+fwqrKU1MvZVWVpj3uno4uvnzqf6omluihLskbDPiIZNlC2zo7WDq5Y8n5mTYmw6539FJmlPa65PcoVD2/hiiXv10VZkjXq+YtkWGWkhFvPXpTSy7/588fy0PM7+OIPniNkRnu0h/94/s1+x129bCG3PrGNhpYOjpharouyJGvU8xfJsJaOLm54/GUuP30BFZESWju6uPE/X2HZolk8/WozrzTu5YqHt7D2jIUcNrmUe1cdz8539tPcHuXaR+rZtL2VmsoIZaVFGuOXrFHwF8mwaHcPj25p5NEtjSnbV31kLlcvW8i1j9T3Tu7+bM0JHDY5wp793fzdvc/3Zv3cvqKWqeW6QEuyJ2fB38xOA74LFAF3uPtVuWqLSCbZAGP5kyMlfPP+zWza3grEJ3e7umMqxSA5kZMxfzMrAm4CPgksAD5nZgty0RaRTCsyuHrZwpSx/JvOOpa1j/yxN/AnticmdBOlGJTSKaMlVz3/44Ct7v4qgJndAywBtuSoPSIZEwqFuOvp11LG/H+x+U2+dvKRbNnZljK0owldyZVcBf+ZwPakxw3Ah/oeZGargFUAs2fPHp2WiYxQVXmYiz4xP+UK38TVuhrakbEiV8E/3b/4fkWG3H0dsA7itX2y3SiRTBhsDF9VNmWsyFXwbwBmJT2uAXbkqC0iB6xv4bbKSAktHV0pwV6BXsayXAX/54B5ZnYE8CZwJnBWjtoikmKghVYGqsd/yoJpXHjSkaz+0caUYZ750ydpWEfGrJwEf3fvNrOvAo8QT/W8091fzEVbRJKlq8iZGK9/pWlvyvarly2kqS3KskWzegM/xFM4V66vY8Oaxer9y5iVs/IO7v4Ldz/S3ee6+5W5aodIsnQVOVeur6Nxb2e/7Rc/sJnVJ86lIlKStkCbirLJWKYrfEWSJFfkPGZWRW9w7+qJpQ3wiVTOdBd1qSibjGUq7CYFLxZzGtv286e32wE4ZcE0PrOohus+czRV5WFaO7po3NPZe9FWQk1lhNaOLh7YuL1fgTbl8MtYp2UcpaClG+O/8wu1dHbFehdaSay3O6EkxAV3b3p3da5zFjG1PEwoFEqb7aPJXsk1LeMoMoB0Y/xvtuzn8gdfSNn2Dz/9PVd9+n9x76rjAdIGeE3uynii4C8FKxZzot09XLf8aFo7urj1iW1s2t5KWbgo7fj+hJIiwsVFCvKSFxT8Ja8NlLPf3R2jvrGN83+4MSV189pH6tkX7Uk7gTttUqnG8SVvaMJX8lZiPP+yDZt5YcceGtv2s+OdDhpa9rGrbX9v4Id3UzcvPGkeleUlXLf86JQJ3NvOXsSMyRGN40veUM9f8lZze5Trf13PuSccwZP1u5k37XB2vbOf/V09zKiIpB3amT2ljK//9PcAXH76AqrKw0yOlHDIhGKKi9VXkvyhf82St6LdPSxbNIu7nn6NTy2cyYo7n+WMW3/DJT/7A0Da1M3iIqNpbyebtrdyxcNb6OyOsfaRPxIK6b+K5Bf1/CVvJcb4ly2axQV3/y5liOeqX77ETWcd27s9kbo545AJ3P3lD9HY1klze5S7nn6Niz4xX2P9kncU/CVvVZWH6Yh2A/Qb4nl0SyN/+/F5vQuuzKyIcOghEyguDlFTWUYkXMxhkydw7OyFytmXvKTgL+PeQBk9oZAxY3IEh7TZOzveiU/61lRG+NmaE3rH9FV3XwqBBjJlXEtk9Cy9+SkWX/1fLL35Kep3txGLxa9cLy4OMXNyPFsnOXtn7RkLufWJbUlX6irYS2FReQcZt2IxZ9ee/exo7aC5Pdp7kVZNZaRfOeXd73SwL9pDY1snXT0xikJGyIzWji4+UDOZ6ZMjg5xJZHxSeQcZ19IN6wD9avIkLtLatL21XznlUCjE681tKWUbgN4PCpFCo2EfGdMGGtZ5q33g+vrpyilXlYc5vKqMtWcsVPVNEdTzlzFuoMVV7l75obQXaVWVh9MG9FDImFNVTkVZCfeuOp4ehwklIaaWlyqTRwqSgr+MSYmhnn3R7rRBvsgsbQbPjCBlM11AD4WMKeWlUJ715ouMeVkb9jGzfzSzN83s+eD2qaR9l5rZVjOrN7NTs9UGGZ+Sh3rebu/k+1/4IPeuOp7bzlnEMbMqqKmMEAkXcfuK2n5DOAMFfhFJle2e//Xufm3yBjNbAJwJHAXMAB4zsyPdXQueCrGYs3vPfkqKQty76nhaO7q4/MHneyd1156xkOpJpRxSWkLF9DAb1izWAioiByEXE75LgHvcvdPdXwO2AsfloB2SY7GY09TWyZst+2hq64yXWd7dxvLbfsPJ3/lvXt69t1/lzW/cv5mikPFK014gvoDKzMoyqidp7F7kQGQ7+H/VzDab2Z1mVhlsmwlsTzqmIdjWj5mtMrM6M6tramrKclNlNKXN4mls4/pf1/cG+4EWVXGHlevraG6P5qLpInlhRMM+ZvYYcGiaXZcBtwBXAB78vA44D0jXPUt7pZm7rwPWQfwir5G0VcaWdFk85/9wI2vPWMiyRbOoiJQwpTycdlK3J+Y0tHT0y+UXkeEbUfB395OHc5yZ3Q48HDxsAGYl7a4BdoykHTL+RLt7aGjp4JhZFaw+cS4VkRK6emJMnRjmG/dvpqGlg1MWTOPmzx/LmqSF1G/+/LHc/uSraXP5RWT4sjbha2aHufvO4OFS4IXg/kPA3Wb2HeITvvOAZ7PVDhmbwsVFnLJgGueecAQXP7A5dUJ3YikNLR08uqURgHtWHk9ze5Qp5WH+/fFXePrVZl2cJTJC2Rzzv8bM/mBmm4GPARcBuPuLwH3AFuBXwAXK9Ck8VeVhvvWXC3oDP7w7obv6xLm9xz26pZGmvZ0suekpHPjayfPYsGYx86dP0gSvyAhkrefv7ucMsu9K4MpsnVvGvkTJ5XQTuhWRkt7HNZURGts647n9JUUqtSySIartIzkTCq7STVZTGWFftKf3/tXLFvLAxu0a5hHJMJV0lqwaaKEViJdZ3trUnjLmf93yo5lTVUZ3zDEziixekVMXcIkcOJV0lpzo7o5R39jWe6FWTWV8UZXDKiZQEQkTCoW46+nXepdSbO3o4nv/8ypXLl3IzMka3hHJJgV/yYpYzNnxTke/K3TP/9FGrljyfg6dPIF51RO56BPzU2rya3hHZHQo+EtWNLdHaWzrTDuhWxYuYuX6ut6sHdXnERl9mvCVjErU69kX7WZypIRTFkxL2V9TGaG1o6v3Ct3EYumqzyMyutTzl4xJ1OtJHsa5+fPHAvF8/eSlFnWFrkhuKdtHhmWwrJ2EprZOlt78VL9aPHeddxwGvNG8jxsef4WmvZ3cvqJWF2qJZJmyfWRE0vXo0wXvRL2eZA0tHZSEjIkTipk44RBuPOsYje2LjAEa85chDbSObt+SyuHiorQXbUXCxUwpL2XapAka2xcZIxT8ZUgD9ej7llROLJ7ed2lFpW6KjD0a9pEBJcb5e9z5/hc+yA2Pv8Km7a0AaSdsQyFT6qbIOKHgL2mluzp37RkLueZX9b0Ttul69InUTREZ2xT8pZ+Brs79xv2b+eGXjqPIjBmTI+rRi4xjGvOXfga7OrdxTydn3fFb3u7Q+rki45mCv/QT7e6huT2aNnMncXXu/q5YjlonIpmg4C/9hIuLeGDjdq5etjAlc+ems47l1ie2UVMZoUgjPiLjmsb8pZ+q8jAXfWI+1/+6nstPX0BVeZgp5WFufWIbTXs7WXvGQiJhlWYQGc9G1PM3s+Vm9qKZxcysts++S81sq5nVm9mpSdtPC7ZtNbNLRnJ+yY5EyuaVSxfy/hmHMP2QCTTvjbhs1AEAAAhgSURBVLJsUQ1XLHk/0w+J1+MXkfFrpD3/F4BPA7clbzSzBcCZwFHADOAxMzsy2H0T8AmgAXjOzB5y9y0jbIdkWHLKZizmTCgpUu6+SB4ZUfB395cAzPoFgiXAPe7eCbxmZluB44J9W9391eB59wTHKviPYcrdF8k/2ZrwnQlsT3rcEGwbaHtaZrbKzOrMrK6pqSkrDRURKURD9vzN7DHg0DS7LnP3Bwd6WpptTvoPmwFrSrv7OmAdxEs6D9FUEREZpiGDv7uffBCv2wDMSnpcA+wI7g+0XURERkm2hn0eAs40s1IzOwKYBzwLPAfMM7MjzCxMfFL4oSy1oWAlllJ8s2UfTW2dxGL60iQiqUY04WtmS4F/B6qBn5vZ8+5+qru/aGb3EZ/I7QYucPee4DlfBR4BioA73f3FEf0GkmK4C6+ISGHTMo55ZqClFDesWayMHZECM9gyjirvkGeGu/CKiBQ2Bf88kDzGb2acsmBayv50C6+ISGFTbZ9xLt0Y/61nLwLg0S2NWkpRRNLSmP84N9AY/33nfxh3VzkGkQI22Ji/ev7j3EBj/O7OzMqyHLVKRMY6jfmPc+HiorSLrmiMX0QGo+A/zlWVh7l9RW3Koisa4xeRoWjYZ5xL1N7fsGaxSi6LyLAp+OcBlVwWkQOlYR8RkQKk4C8iUoAU/EVECpCCv4hIAVLwFxEpQAr+IiIFSMFfRKQAKfiLiBQgBX8RkQI0ouBvZsvN7EUzi5lZbdL2OWbWYWbPB7dbk/YtMrM/mNlWM7vBzFSHQERklI205/8C8GngyTT7trn7B4Lb6qTttwCrgHnB7bQRtkFERA7QiIK/u7/k7vXDPd7MDgMOcfffeHwVmfXA34ykDSIicuCyOeZ/hJltMrP/NrO/CLbNBBqSjmkItomIyCgasqqnmT0GHJpm12Xu/uAAT9sJzHb3ZjNbBPxfMzsKSDe+P+A6kma2ivgQEbNnzx6qqSIiMkxDBn93P/lAX9TdO4HO4P5GM9sGHEm8p1+TdGgNsGOQ11kHrIP4Gr4H2g4REUkvK8M+ZlZtZkXB/fcQn9h91d13Am1mdnyQ5bMCGOjbg4iIZMlIUz2XmlkD8GHg52b2SLDrI8BmM/s9cD+w2t3fDvZ9BbgD2ApsA345kjaIiMiBs3jSzdhXW1vrdXV1uW6GiMi4YWYb3b023T5d4SsiUoAU/EVECpCCv4hIARoy1bPQxWJOc3uUaHcP4eIiqsrDhEIqRyQi45uC/yBiMad+dxsr19dRPbGUC0+axxFTyykrLWJqeak+BERk3FLwH0Rze7Q38H/91Plc/MBmGlo6qKmMcPuKWuZPn6QPABEZlzTmP4hodw8NLR2sPnFub+AHaGjpYOX6OprbozluoYjIwVHwH0S4uIiayggVkZLewJ/Q0NJBtLsnRy0TERkZBf9BVJWHuX1FLfuiPdRURlL21VRGCBcX5ahlIiIjo+A/iFDImD99EkfPmsxtZy/q/QBIjPlXlYdz3EIRkYOjCd8hhELGlPJSKiJhNqxZrJRPEckLCv7DFAoZ1ZNKc90MEZGMyOvgrwu0RETSy9vgn3yBlnLzRURS5e2Eb+ICLeXmi4j0l7fBP3GBVjLl5ouIxOVt8E9coJVMufkiInF5G/wTF2gpN19EpL+8nfBNXKCl3HwRkf5GuoD7WjP7o5ltNrMNZlaRtO9SM9tqZvVmdmrS9tOCbVvN7JKRnH8oidz8mZVlVE9SCWYRkYSRDvv8Gni/uy8EXgYuBTCzBcCZwFHAacDNZlZkZkXATcAngQXA54JjRURkFI0o+Lv7o+7eHTx8BqgJ7i8B7nH3Tnd/DdgKHBfctrr7q+4eBe4JjhURkVGUyQnf84BfBvdnAtuT9jUE2wbanpaZrTKzOjOra2pqymBTRUQK25ATvmb2GHBoml2XufuDwTGXAd3AjxNPS3O8k/7Dxgc6t7uvA9YB1NbWDniciIgcmCGDv7ufPNh+MzsXOB04yd0TAboBmJV0WA2wI7g/0HYRERkl9m68Pognm50GfAf4qLs3JW0/Crib+Bj/DOBxYB7xbwQvAycBbwLPAWe5+4vDOFcT8MZBNzbzpgJv5boRY4Tei1R6P96l9yLVaL8fh7t7dbodI83zvxEoBX5tZgDPuPtqd3/RzO4DthAfDrrA3XsAzOyrwCNAEXDncAI/wEC/QK6YWZ271+a6HWOB3otUej/epfci1Vh6P0YU/N39vYPsuxK4Ms32XwC/GMl5RURkZPK2vIOIiAxMwf/grct1A8YQvRep9H68S+9FqjHzfoxowldERMYn9fxFRAqQgr+ISAFS8B+BwaqaFhozW25mL5pZzMzGRCrbaBvNirVjnZndaWaNZvZCrtsyFpjZLDP7LzN7Kfh/8rVct0nBf2TSVjUtUC8AnwaezHVDckEVa/v5AfGKvhLXDfyDu78POB64INf/PhT8R2CQqqYFx91fcvf6XLcjh1SxNom7Pwm8net2jBXuvtPdfxfcbwNeYpCilqNBwT9zkquaSuE5oIq1UrjMbA5wDPDbXLYjb5dxzJSDrGqal4bzXhSwgSrZivQys4nAA8DfufueXLZFwX8IB1nVNC8N9V4UuMEq2YpgZiXEA/+P3f1nuW6Phn1GIKhqejHw1+6+L9ftkZx6DphnZkeYWZj4MqYP5bhNMkZYvPLl94CX3P07uW4PKPiP1I3AJOJVTZ83s1tz3aBcMbOlZtYAfBj4uZk9kus2jaZg4j9RsfYl4L7hVqzNR2b2E+A3wHwzazCzL+W6TTm2GDgH+HgQK543s0/lskEq7yAiUoDU8xcRKUAK/iIiBUjBX0SkACn4i4gUIAV/EZECpOAvIlKAFPxFRArQ/wdPpQ9ilvZLMAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# visiualizing our dataset\n",
    "sns.scatterplot(x[:, 0], y).set_title(\"Toy linear regression dataset\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 520,
   "metadata": {},
   "outputs": [],
   "source": [
    "# set the column names\n",
    "header = [\"x\", \"y\"]\n",
    "my_tree = build_tree(data, p_type= \"regression\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 521,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print_tree_reg(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 522,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Actual: -16.182613234884535. Predicted: -18.18887025551526\n",
      "Actual: 26.09466022796643. Predicted: 25.05706329397776\n",
      "Actual: -117.00095028113549. Predicted: -172.4027889081725\n",
      "Actual: 71.89195915308501. Predicted: 80.08688427823328\n",
      "Actual: -29.91077359578776. Predicted: -34.9051018763354\n",
      "Actual: 73.48810851438917. Predicted: 63.63323786561832\n",
      "Actual: 68.6566125560334. Predicted: 80.08688427823328\n",
      "Actual: 85.07599704822123. Predicted: 63.63323786561832\n",
      "Actual: -49.95635880438457. Predicted: -47.10421034116462\n",
      "Actual: -50.916031694204186. Predicted: -42.50633703712883\n",
      "Actual: -56.93218616888022. Predicted: -47.10421034116462\n",
      "Actual: -27.629542428678768. Predicted: -35.18305670310365\n",
      "Actual: 50.59174997785491. Predicted: 55.34407792157434\n",
      "Actual: 71.80446159598674. Predicted: 80.08688427823328\n",
      "Actual: 11.548262596296127. Predicted: 18.670733354404543\n",
      "Actual: 128.0832930454806. Predicted: 114.75571614295292\n",
      "Actual: -8.105391367162541. Predicted: -7.996226678425758\n",
      "Actual: -49.86073922301242. Predicted: -47.10421034116462\n",
      "Actual: -90.45251399891207. Predicted: -86.811131463367\n",
      "Actual: -68.9512568046342. Predicted: -74.54508619144238\n"
     ]
    }
   ],
   "source": [
    "# for each row in test set, make prediction\n",
    "for row in data_test:\n",
    "    print (\"Actual: %s. Predicted: %s\" %(row[-1], predict(row, my_tree)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 526,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute train MSE\n",
    "train_mse = 0\n",
    "for i, row in enumerate(data):\n",
    "    pred = predict(row, my_tree)\n",
    "    train_mse += pow(pred - row[-1] , 2)\n",
    "# finally divide the squared sum with number of datapoints\n",
    "else:\n",
    "    train_mse /= len(data)\n",
    "\n",
    "# compute test MSE\n",
    "test_mse = 0\n",
    "for i, row in enumerate(data_test):\n",
    "    pred = predict(row, my_tree)\n",
    "    test_mse += pow(pred - row[-1] , 2)\n",
    "# finally divide the squared sum with number of datapoints\n",
    "else:\n",
    "    test_mse /= len(data_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 529,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Train MSE: 0.0\r\n",
      "Test MSE: 222.91637127863788\n"
     ]
    }
   ],
   "source": [
    "print(f\"Train MSE: {train_mse}\\r\\nTest MSE: {test_mse}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are overfitting here but it is ok as the object is to learn and understand the concept better. Overfitting can be reduced by number of parameters like `max_depth`, `min_sample_split` etc.\n",
    "\n",
    "\n",
    "To learn more please check out sklearn's documentation on decision tree [here](https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}