L4.Tree-Based Models.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a href=\"https://colab.research.google.com/github/ML-Challenge/week3-supervised-learning/blob/master/L4.Tree-Based%20Models.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" /></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:18.466964Z",
     "start_time": "2020-02-11T09:27:18.464524Z"
    }
   },
   "outputs": [],
   "source": [
    "# Download lesson datasets\n",
    "# Required if you're using Google Colab\n",
    "!wget \"https://github.com/ML-Challenge/week3-supervised-learning/raw/master/datasets.zip\"\n",
    "!unzip -o datasets.zip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:19.370268Z",
     "start_time": "2020-02-11T09:27:18.469160Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import utils\n",
    "# We'll be using this module throughout the lesson\n",
    "import utils"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:19.374889Z",
     "start_time": "2020-02-11T09:27:19.371772Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import dependencies\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "# and setting the size of all plots.\n",
    "plt.rcParams['figure.figsize'] = [11, 7]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classification and Regression Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Decision trees are supervised learning models used for problems involving classification and regression. Tree models present a high flexibility that comes at a price: on one hand, trees are able to capture complex non-linear relationships; on the other hand, they are prone to memorizing the noise present in a dataset. By aggregating the predictions of trees that are trained differently, ensemble methods take advantage of the flexibility of trees while reducing their tendency to memorize noise. Ensemble methods are used across a variety of fields and have a proven track record of winning many machine learning competitions. In this lesson, we'll learn how to use Python to train decision trees and tree-based models with the user-friendly scikit-learn machine learning library. We'll see the advantages and shortcomings of trees and demonstrate how ensembling can alleviate these shortcomings, all while practicing on real-world datasets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Classification and Regression Trees (CART) are a set of supervised learning models used for problems involving classification and regression. In this lesson, we'll introduce the CART algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision tree for classification"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classification-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given a labeled dataset, a classification tree learns a sequence of if-else questions about individual features in order to infer the labels. In contrast to linear models, trees are able to capture non-linear relantionships between features and labels. In addition, trees don't require the features to be on the same scale through standardization for example."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Breast Cancer Dataset in 2D"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand trees more concretely, we'll try to predict whether a tumor is malignant or benign in the Wisconsing Breast Cancer dataset using only 2 features.\n",
    "\n",
    "![Breast Cancer](assets/breast_cancer.png)\n",
    "\n",
    "The figure here shows a scatterplot of two cancerous cell features with malignant-tumors in blue and benign-tumors in red."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decision-tree Diagram"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When a classification tree is trained on this dataset, the tree learns a sequence of if-else questions with each question involving one feature and one split-point. Take a look at the tree diagram:\n",
    "\n",
    "![Tree Diagram](assets/tree_diagram.png)\n",
    "\n",
    "At the top, the tree asks wheter the concave-points mean of an instance is smaller than 0.051. It it is, the instance traverses the `True` branch; otherwise, it traverses the `False` branch. Similarly, the instance keeps traversing the internal branches until it reaches an end. The label of the instance is then predicted to be that of the prevailing class at that end.\n",
    "\n",
    "The maximum number of branches separating the top from an extreme-end is known as the `maximum depth` which is equal to 2 here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decision Regions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A classification-model divides the feature-space into regions where all instances in one region are assigned to only one class-label. These regions are known as decision-regions. Decision-regions are separated by surfaces called decision-boundaries.\n",
    "\n",
    "![Linear classifier decision region](assets/linear_decision.png)\n",
    "\n",
    "The figure above shows the decision-regions of a linear-classifier. Note how the boundary is a straight-line."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decision Regions: CART vs. Linear Model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In contrast, as shown here on the right, a classification-tree produces rectangular decision-regions in the feature space.\n",
    "\n",
    "![CART vs Linear Model](assets/cart_vs_linear.png)\n",
    "\n",
    "This happens because at each split made by the tree, only one feature is involved."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train a classification tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example we'll work with the [Wisconsin Breast Cancer Dataset](https://www.kaggle.com/uciml/breast-cancer-wisconsin-data) from the UCI machine learning repository. We'll predict whether a tumor is malignant or benign based on two features: the mean radius of the tumor (`radius_mean`) and its mean number of concave points (`concave points_mean`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.121302Z",
     "start_time": "2020-02-11T09:27:20.099133Z"
    }
   },
   "outputs": [],
   "source": [
    "utils.wbc.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.127392Z",
     "start_time": "2020-02-11T09:27:20.123031Z"
    }
   },
   "outputs": [],
   "source": [
    "X = utils.wbc[['radius_mean', 'concave points_mean']]\n",
    "y = utils.wbc['diagnosis'].astype('category').cat.codes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.134798Z",
     "start_time": "2020-02-11T09:27:20.129466Z"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, stratify = y, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dataset is already loaded and is split into 80% train and 20% test. The feature matrices are assigned to `X_train` and `X_test`, while the arrays of labels are assigned to `y_train` and `y_test` where class 1 corresponds to a malignant tumor and class 0 corresponds to a benign tumor. To obtain reproducible results, we also defined a variable called `SEED` which is set to 42."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.194041Z",
     "start_time": "2020-02-11T09:27:20.191707Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import DecisionTreeClassifier from sklearn.tree\n",
    "from sklearn.tree import DecisionTreeClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.200220Z",
     "start_time": "2020-02-11T09:27:20.197938Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate a DecisionTreeClassifier 'dt' with a maximum depth of 6\n",
    "dt = DecisionTreeClassifier(max_depth=6, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.207929Z",
     "start_time": "2020-02-11T09:27:20.201855Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit dt to the training set\n",
    "dt.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.213897Z",
     "start_time": "2020-02-11T09:27:20.209416Z"
    }
   },
   "outputs": [],
   "source": [
    "# Predict test set labels\n",
    "y_pred = dt.predict(X_test)\n",
    "print(y_pred[0:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the classification tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've fit our first classification tree, it's time to evaluate its performance on the test set. We'll do so using the accuracy metric which corresponds to the fraction of correct predictions made on the test set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.379338Z",
     "start_time": "2020-02-11T09:27:20.376589Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import accuracy_score\n",
    "from sklearn.metrics import accuracy_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.387498Z",
     "start_time": "2020-02-11T09:27:20.383839Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute test set accuracy  \n",
    "acc = accuracy_score(y_test, y_pred)\n",
    "print(f\"Test set accuracy: {acc:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not bad! Using only two features, our tree was able to achieve an accuracy of 89%!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Logistic regression vs classification tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example we will compare logistic regression and the classification tree on trained on the same dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.721393Z",
     "start_time": "2020-02-11T09:27:20.719009Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import LogisticRegression from sklearn.linear_model\n",
    "from sklearn.linear_model import LogisticRegression"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.729142Z",
     "start_time": "2020-02-11T09:27:20.726286Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instatiate logreg\n",
    "logreg = LogisticRegression(solver='liblinear', random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.739086Z",
     "start_time": "2020-02-11T09:27:20.731139Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit logreg to the training set\n",
    "logreg.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.746413Z",
     "start_time": "2020-02-11T09:27:20.741262Z"
    }
   },
   "outputs": [],
   "source": [
    "# Predict test set labels\n",
    "logreg_pred = logreg.predict(X_test)\n",
    "print(logreg_pred[0:5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:20.752526Z",
     "start_time": "2020-02-11T09:27:20.747979Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute test set accuracy  \n",
    "logreg_acc = accuracy_score(y_test, logreg_pred)\n",
    "print(f\"Test set accuracy: {logreg_acc:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classification tree Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section we'll examine how a classification-tree learns from data. Let's start by defining some terms."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Building Blocks of a Decision-Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A `decision-tree` is a data-structure consisting of a hierarchy of individual units called nodes. A `node` is a point that involves either a question or a prediction. There are three kind of nodes:\n",
    "- The `Root` is the node at which the decision-tree starts growing. It has no parent node and involves a question that gives rise to 2 children nodes through two branches.\n",
    "- The `Internal node` is a node that has a parent. It also involves a question that gives rise to 2 children nodes.\n",
    "- The `Leaf` is a node that has one parent node and involves no questions. It's where a prediction is made.\n",
    "\n",
    "Recall that when a classifictaion tree is trainded on a labeled dataset, the tree learns patterns from the features in such a way to produce the purest leafs. In other words the tree is trained in such a way so that, in each leaf, one class-label is predominant.\n",
    "\n",
    "![Tree Diagram with Notes](assets/tree_diagram_notes.png)\n",
    "\n",
    "In the tree diagram shown above, consider the case where an instrance traverses the tree to reach the leaf on the left. In this leaf, there are 257 instances classified as benign and 7 instances classified as malignant. As a result, the tree's prediction for this instance whould be: `'benign'`.\n",
    "\n",
    "In order to understand how a classification tree produces the purest leafs possible, let's first define the concept of information gain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Information Gain (IG)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The nodes of a classification tree are grown recursively; in other words, the obtention of an internal node or a leaf depends on the state of its predecessors. To produce the purest leafs possible, at each node, a tree asks a question involving one feature `f` and a split-point `sp`. But how dows it know which feature and which split-point to pick? It does so by maximizing information gain!\n",
    "\n",
    "The tree considers that every node contains information and aims at maximizing the Information Gain obtained after each split. Consider the case where a node with N samples is split into a left-node with $N_{left}$ samples and a right-node with $N_{right}$ samples. The information gain for such split is given by the formular shown below:\n",
    "\n",
    "$$ IG(\\underbrace{f}_\\text{feature} , \\underbrace{sp}_\\text{split-point}) = I(parent) - [\\frac{N_{left}}{N} I(left) + \\frac{N_{right}}{N}I(right)] $$\n",
    "\n",
    "A question that you may have in mind here is: \"What criterion is used to measure the impurity of a node?\". Well there are different criteria we can use among which are the `gini-index` and `entropy`.\n",
    "\n",
    "Not what we know what is `Information gain`, let's describe how a classification tree learns."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Classification-Tree Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When an unconstrained tree is trained, the nodes are grown recursively. In other words, a node exists based on the state of its predecessors. At a non-lead node, the data is split based on feature `f` and split-point `sp` in such a way to maximize information gain. If the information gain obtained by splitting a node is null, the node is declared a leaf. \n",
    "\n",
    "Keep in mind that these rules are for unconstrained trees. If we constrain the `maximum depth` of a tree to 2 for example, all nodes having a depth of 2 will be declared leafs even if the information gain obtained by splitting such nodes is not null."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using entropy as a criterion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we'll train a classification tree on the Wisconsin Breast Cancer dataset using entropy as an information criterion. We'll do so using all the 30 features in the dataset, which we split into 80% train and 20% test."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.698635Z",
     "start_time": "2020-02-11T09:27:21.692542Z"
    }
   },
   "outputs": [],
   "source": [
    "X = utils.wbc.drop('diagnosis', axis=1)\n",
    "y = utils.wbc['diagnosis'].astype('category').cat.codes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.707895Z",
     "start_time": "2020-02-11T09:27:21.700223Z"
    }
   },
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, stratify = y, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.715296Z",
     "start_time": "2020-02-11T09:27:21.711350Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate dt_entropy, set 'entropy' as the information criterion\n",
    "dt_entropy = DecisionTreeClassifier(max_depth=8, criterion='entropy', random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.731518Z",
     "start_time": "2020-02-11T09:27:21.717315Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit dt_entropy to the training set\n",
    "dt_entropy.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Entropy vs Gini index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example we'll compare the test set accuracy of `dt_entropy` to the accuracy of another tree named `dt_gini`. The tree `dt_gini` was trained on the same dataset using the same parameters except for the information criterion which was set to the gini index using the keyword `'gini'`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.932156Z",
     "start_time": "2020-02-11T09:27:21.918401Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate dt_gini, set 'gini' as the information criterion\n",
    "dt_gini = DecisionTreeClassifier(max_depth=8, criterion='gini', random_state=utils.SEED)\n",
    "\n",
    "# Fit dt_gini to the training set\n",
    "dt_gini.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.940268Z",
     "start_time": "2020-02-11T09:27:21.933776Z"
    }
   },
   "outputs": [],
   "source": [
    "# Use dt_gini to predict test set labels\n",
    "y_pred_gini= dt_gini.predict(X_test)\n",
    "\n",
    "# Evaluate accuracy_entropy\n",
    "accuracy_gini = accuracy_score(y_test, y_pred_gini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.946171Z",
     "start_time": "2020-02-11T09:27:21.942391Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print accuracy_gini\n",
    "print('Accuracy achieved by using the gini index: ', accuracy_gini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.952305Z",
     "start_time": "2020-02-11T09:27:21.947602Z"
    }
   },
   "outputs": [],
   "source": [
    "# Use dt_entropy to predict test set labels\n",
    "y_pred_entropy= dt_entropy.predict(X_test)\n",
    "\n",
    "# Evaluate accuracy_entropy\n",
    "accuracy_entropy = accuracy_score(y_test, y_pred_entropy)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:21.957990Z",
     "start_time": "2020-02-11T09:27:21.954817Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print accuracy_entropy\n",
    "print('Accuracy achieved by using entropy: ', accuracy_entropy)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision tree for regression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section, we'll learn how to train a decision tree for a regression problem. Recall that in regression, the target variable is continous. In other words, the output of the model is a real value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Auto-mpg Dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's motivate our discussion of regression by introducing the automobile miles-per-galon dataset from the UCI Machine Learning Repository. This dataset consists of 6 features corresponding to the characteristics of a car and a continous target variable labeled `mpg` which stands for miles-per-galon. Our task is to predict the `mpg` consumption of a car given these six features.\n",
    "\n",
    "To simplify the problem, here the analysis is restricted to only one feature corresponding to the displacement of a car. This feature is denoted by `displ`.\n",
    "\n",
    "A 2D scatter plot of `mpg` versus `displ` shows that the mpg-consumption decreases nonlinearly with displacement. Note that linear models such as `linear regression` would not be able to capture such a non-linear trend.\n",
    "\n",
    "![Non-linear trend](assets/non_linear_trend.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Information Criterion for Regression-Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is important to note that, when a regression tree is trained on a dataset, the impurity of a node is measured using the mean-squared error of the targets in that node\n",
    "\n",
    "$$ I(node) = \\underbrace{MSE(node)}_\\text{mean-squared-error} = \\frac{1}{N_{node}} \\sum_{i\\in node} (y^{(i)} - \\hat{y}_{node})^2 $$\n",
    "\n",
    "$$ \\underbrace{\\hat{y}_{node}}_\\text{mean-target-value} = \\frac{1}{N_{node}} \\sum_{i\\in node} y^{(i)}  $$\n",
    "\n",
    "This means that the regression tree tries to find the splits that produce leafs where in each leaf the target values are on average, the closest possible to the mean-value of the labels in that particular leaf."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a new instance traverses the tree and reaches a certain leaf, its target-variable `'y'` is computed as the average of the target-variables contained in that leaf as shown in the formula below:\n",
    "\n",
    "$$ \\hat{y}_{pred}(leaf) = \\frac{1}{N_{leaf}} \\sum_{i \\in leaf} y^{(i)} $$\n",
    "\n",
    "To highlight the importance of the flexibility of regression trees, take a look at this figure:\n",
    "\n",
    "![Tree vs Linear Regression](assets/tree_vs_linear.png)\n",
    "\n",
    "On the left we have a scatter plot of the data in blue along with the predictions of a linear regression model shown in black. The linear model fails to capture the non-linear trend exhibited by the data. On the right, we have the same scatter plot along with a red line corresponding to the prediction of a regression tree. The regressiont tree shows a greater flexibility and is able to capture the non-linearity, though not fully.\n",
    "\n",
    "Later on, we'll aggregate the predictions of a set of trees that are trained differently to obtain better results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train a regression tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we'll train a regression tree to predict the `mpg` (miles per gallon) consumption of cars in the [auto-mpg dataset](https://www.kaggle.com/uciml/autompg-dataset) using all the six available features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.119727Z",
     "start_time": "2020-02-11T09:27:23.108527Z"
    }
   },
   "outputs": [],
   "source": [
    "utils.auto.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.125639Z",
     "start_time": "2020-02-11T09:27:23.121665Z"
    }
   },
   "outputs": [],
   "source": [
    "X = utils.auto.drop('mpg', axis=1)\n",
    "y = utils.auto['mpg']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.133277Z",
     "start_time": "2020-02-11T09:27:23.127960Z"
    }
   },
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.137211Z",
     "start_time": "2020-02-11T09:27:23.134832Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import DecisionTreeRegressor from sklearn.tree\n",
    "from sklearn.tree import DecisionTreeRegressor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.140818Z",
     "start_time": "2020-02-11T09:27:23.138572Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate dt\n",
    "dt = DecisionTreeRegressor(max_depth=8, min_samples_leaf=0.13, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.147543Z",
     "start_time": "2020-02-11T09:27:23.142170Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit dt to the training set\n",
    "dt.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the regression tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we will evaluate the test set performance of `dt` using the Root Mean Squared Error (RMSE) metric. The RMSE of a model measures, on average, how much the model's predictions differ from the actual labels. The RMSE of a model can be obtained by computing the square root of the model's Mean Squared Error (MSE)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.323809Z",
     "start_time": "2020-02-11T09:27:23.320565Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import mean_squared_error from sklearn.metrics as MSE\n",
    "from sklearn.metrics import mean_squared_error as MSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.330582Z",
     "start_time": "2020-02-11T09:27:23.327539Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute y_pred\n",
    "y_pred = dt.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.335284Z",
     "start_time": "2020-02-11T09:27:23.332233Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute mse_dt\n",
    "mse_dt = MSE(y_test, y_pred)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.338997Z",
     "start_time": "2020-02-11T09:27:23.336762Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute rmse_dt\n",
    "rmse_dt = mse_dt ** 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.343882Z",
     "start_time": "2020-02-11T09:27:23.341131Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print rmse_dt\n",
    "print(f\"Test set RMSE of dt: {rmse_dt:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Linear regression vs regression tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we'll compare the test set RMSE of `dt` to that achieved by a linear regression model. We have already instantiated a linear regression model lr and trained it on the same dataset as dt."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.535877Z",
     "start_time": "2020-02-11T09:27:23.533415Z"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LinearRegression\n",
    "linreg = LinearRegression()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.552208Z",
     "start_time": "2020-02-11T09:27:23.539954Z"
    }
   },
   "outputs": [],
   "source": [
    "linreg.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.558132Z",
     "start_time": "2020-02-11T09:27:23.554102Z"
    }
   },
   "outputs": [],
   "source": [
    "y_pred_lr = linreg.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.563903Z",
     "start_time": "2020-02-11T09:27:23.560603Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute mse_lr\n",
    "mse_lr = MSE(y_test, y_pred_lr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.568380Z",
     "start_time": "2020-02-11T09:27:23.566004Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute rmse_lr\n",
    "rmse_lr = mse_lr ** 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.573671Z",
     "start_time": "2020-02-11T09:27:23.570114Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print rmse_lr\n",
    "print(f'Linear Regression test set RMSE: {rmse_lr:.2f}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:23.578153Z",
     "start_time": "2020-02-11T09:27:23.575482Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print rmse_dt\n",
    "print(f'Regression Tree test set RMSE: {rmse_dt:.2f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc-hr-collapsed": false
   },
   "source": [
    "# The Bias-Variance Tradeoff"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The bias-variance tradeoff is one of the fundamental concepts in supervised machine learning. In this section, we'll diagnose the problems of overfitting and underfitting. We'll also introduce the concept of ensembling where the predictions of several models are aggregated to produce predictions that are more robust."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generalization Error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In supervised learning, we make the assumption that there's a mapping `f` between features and labels: `y = f(x)`. The function `f` shown in red below is an unknown function that we want to determine.\n",
    "\n",
    "![f function](assets/f_function.png) \n",
    "\n",
    "In reality, data generation is always accompanied with randomness or noise like the blue points shown here.\n",
    "\n",
    "Our goal is to find a model $ \\hat{f} $ that best approximates $f: \\hat{f} \\approx f $. When training $ \\hat{f} $, we want to make sure that noise is discarded as much as possible. At the end. $\\hat{f}$ should achieve a low predictive error on unseen datasets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can encounter two difficulties when approximating $f$: \n",
    "* The first is `overfitting`, it's when $\\hat{f}(x)$ fits the noise in the training set.\n",
    "* The second is `underfitting`, it's when $\\hat{f}$ is not flexible enough to approximate $f$.\n",
    "\n",
    "**Overfitting**\n",
    "\n",
    "When a model overfits the training set, its predictive power on unseen datasets is pretty low. This is illustrated by the predictions of the decision tree regressor shown below in red:\n",
    "\n",
    "![Overfitting tree](assets/overfitting_tree.png)\n",
    "\n",
    "The model clearly memorized the noise present in the training set. Such model achieves a low training set error and a high test set error.\n",
    "\n",
    "**Underfitting**\n",
    "\n",
    "When a model underfits the data, like regression tree whose predictions are shown below in red, the training set error is roughly equal to the test set error:\n",
    "\n",
    "![Underfitting tree](assets/underfitting_tree.png)\n",
    "\n",
    "However, both errors are relatively high. Now the trained model isn't flexible enough to capture the complex dependency between features and labels. In analogy, it's like teaching calculus to a 3-year old. The child does not ave the required mental abstraction level that enables him to understand calculus. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `generalization error` of a model tells us how much it generalizes on unseen data. It can be decomposed into 3 terms: bias, variance and irreducible error where the irreducible error is the error contribution of noise.\n",
    "$$ \\hat{f} = bias^2 + variance + irreducible\\_error $$\n",
    "\n",
    "The `Bias` term tells us, on average, how much $ \\hat{f} \\neq f $. To illustrate this consider the high bias model shown here in black:\n",
    "\n",
    "![Tree Bias](assets/tree_bias.png)\n",
    "\n",
    "This model is not flexible enough to approximate the true function $f$ shown in red. High bias models lead to underfitting.\n",
    "\n",
    "The `Variance` term tells us how much $\\hat{f}$ is inconsistent over different training sets. Conside the high variance model shown below in black:\n",
    "\n",
    "![Tree Variance](assets/tree_variance.png)\n",
    "\n",
    "In this case, $\\hat{f}$ follows the training data points so closely that is misses the true function $f$ shwon in red. High variance models lead to overfitting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The complexity of a model sets its flexiblity to approximate the true function $f$. For example: increasing the `maximum-tree-depth` increases the complexity of a decision tree. The diagram below shows how the best model complexity corresponds to the lowest generalization error:\n",
    "\n",
    "![Tree trade off](assets/tree_off.png)\n",
    "\n",
    "When the model complexity increases, the variance increases while the bias decreases. Conversely, when model complexity decreases, variance decreases and bias increases. Our goal is to find the model complexity that achieves the lowest generalization error. Since this error is the sum of three terms with the irreducible error being constant, we need to find a balance between bias and variance because as one increases the other decreases. This is known as the bias-variance trade-off.\n",
    "\n",
    "Visually, we can imagine approximating $\\hat{f}$ as aiming at the center of a shooting-target where the center is the true function $f$:\n",
    "\n",
    "![Bias-Variance Tradeoff](assets/target_practice.png)\n",
    "\n",
    "If $\\hat{f}$ is low bias and low variance, our shots will be closely clustered around the center. If $\\hat{f}$ is high variance and high bias, not only will our shots miss the target but they would also be spread all around the shooting target."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Diagnose bias and variance problems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Estimating the Generalization Error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given that we've trained a supervised machine learning model labeled $\\hat{f}$, how do we estimate $\\hat{f}$'s generalization error? This cannot be done directly because:\n",
    "\n",
    "* $f$ is unknown\n",
    "* usually we only have one dataset\n",
    "* we don't have access to the error term due to noise.\n",
    "\n",
    "A solution to this is to first split the data into a training and test set. The model $\\hat{f}$ can be then fit to the training set and its error can be evaluated on the test set. The generalization error of $\\hat{f}$ is roughly approxiamted by $\\hat{f}$ error on the test set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Better Model Evaluation with Cross-Validation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usually, the test set should be kept untouched until one is confident about $\\hat{f}$'s performance. It should only be used to evaluate $\\hat{f}$'s final performance or error. Now, evaluating $\\hat{f}$'s performance on the training set may produce an optimistic estimation of the error because $\\hat{f}$ was already exposed to the training set when it was fit.\n",
    "\n",
    "To obtain a reliable estimate of $\\hat{f}$'s performance, we use a technique called cross-validation or CV. CV can be performed using:\n",
    "\n",
    "* K-Fold CV\n",
    "* Hold-out CV\n",
    "\n",
    "We are going to go over K-fold CV. The diagram below illustrates this technique for K=10:\n",
    "\n",
    "![10 K-fold CV](assets/k_fold_10.png)\n",
    "\n",
    "* First the training set (T) is split randomly into 10 partitions or folds\n",
    "* The error of $\\hat{f}$ is evaluated 10 times on the 10 folds\n",
    "* Each time, one fold is picked for evaluation after training $\\hat{f}$ on the other 9 folds\n",
    "* At the end, we obtain a list of 10 errors\n",
    "\n",
    "Finally, as shown in this formula, the CV-error is computed as the mean of the 10 obtained errors:\n",
    "$$ CV_{error} = \\frac{\\sum_{i=1}^n E_i}{n} $$\n",
    "\n",
    "Once we have computed $\\hat{f}$'s cross-validation-error, we can check if it is greater than $\\hat{f}$'s training set error."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Diagnose Variance Problems**\n",
    "\n",
    "If $\\hat{f}$ suffers from `high variance`: CV error of $\\hat{f}$ > training set error of $\\hat{f}$. In such case $\\hat{f}$ has overfit the training set. To remedy this we can try the following:\n",
    "\n",
    "* decrease model complexity. For example, in a decision tree we can reduce the `maximum-tree-depth` or increase the `maximum-samples-per-leaf`.\n",
    "* gather more data to train $\\hat{f}$\n",
    "\n",
    "**Diagnose Bias Problems**\n",
    "\n",
    "On the other hand, $\\hat{f}$ is said to suffer from high bias if: CV error of $\\hat{f} \\approx$ training set error of $\\hat{f} >>$ desired error. In such case $\\hat{f}$ underfits the training set. To remedy this we can try the following:\n",
    "\n",
    "* increase model complexity. For example, in a decision tree increase max depth or decrease min samples per leaf\n",
    "* gather more relevant features for the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Instantiate the model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following set of examples, we'll diagnose the bias and variance problems of a regression tree. The regression tree we define in the following example will be used to predict the mpg consumption of cars from the auto dataset using all available features."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:25.432415Z",
     "start_time": "2020-02-11T09:27:25.428487Z"
    }
   },
   "outputs": [],
   "source": [
    "X = utils.auto.drop('mpg', axis=1)\n",
    "y = utils.auto['mpg']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:25.438306Z",
     "start_time": "2020-02-11T09:27:25.434010Z"
    }
   },
   "outputs": [],
   "source": [
    "# Split the data into 70% train and 30% test\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:25.446176Z",
     "start_time": "2020-02-11T09:27:25.443776Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate a DecisionTreeRegressor dt\n",
    "dt = DecisionTreeRegressor(max_depth=4, min_samples_leaf=0.26, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the 10-fold CV error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we'll evaluate the 10-fold CV Root Mean Squared Error (RMSE) achieved by the regression tree `dt` that we instantiated above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:25.638737Z",
     "start_time": "2020-02-11T09:27:25.636520Z"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.model_selection import cross_val_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.659181Z",
     "start_time": "2020-02-11T09:27:25.642328Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute the array containing the 10-folds CV MSEs\n",
    "MSE_CV_scores = - cross_val_score(dt, X_train, y_train, cv=10, scoring='neg_mean_squared_error', n_jobs=-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.666234Z",
     "start_time": "2020-02-11T09:27:32.662404Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute the 10-folds CV RMSE\n",
    "RMSE_CV = (MSE_CV_scores.mean())**0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.672814Z",
     "start_time": "2020-02-11T09:27:32.669022Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print RMSE_CV\n",
    "print(f'CV RMSE: {RMSE_CV:.2f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A very good practice is to keep the test set untouched until we are confident about our model's performance. CV is a great technique to get an estimate of a model's performance without affecting the test set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the training error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll now evaluate the training set RMSE achieved by the regression tree dt that we instantiated above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.684877Z",
     "start_time": "2020-02-11T09:27:32.675401Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit dt to the training set\n",
    "dt.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.690409Z",
     "start_time": "2020-02-11T09:27:32.686539Z"
    }
   },
   "outputs": [],
   "source": [
    "# Predict the labels of the training set\n",
    "y_pred_train = dt.predict(X_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.696375Z",
     "start_time": "2020-02-11T09:27:32.692652Z"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate the training set RMSE of dt\n",
    "RMSE_train = (MSE(y_train, y_pred_train))**(0.5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.701380Z",
     "start_time": "2020-02-11T09:27:32.698189Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print RMSE_train\n",
    "print(f'Train RMSE: {RMSE_train:.2f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ensemble Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section, we will look at a supervised learning technique known as ensemble learning. Let's first recap what we learned about CARTs.\n",
    "\n",
    "**Advantages of CARTs**\n",
    "\n",
    "CARTs present many advantages:\n",
    "\n",
    "* For example they are easy to understand and their output is easy to interpret. \n",
    "* In addition, CARTs are easy to use and their flexibility gives them an ability to describe nonlinear dependencies between features and labels. \n",
    "* Moreover, we don't need a lot of feature preprocessing to train a CART. \n",
    "* In contrast to other models, we don't have to standardize or normalize features before feeding them to a CART.\n",
    "\n",
    "**Limitations of CARTs**\n",
    "\n",
    "CARTs also have limitations:\n",
    "\n",
    "* A classification tree for example, is only able to produce orthogonal decision boundaries.\n",
    "* CARTs are also very sensitive to small variations in the training set. Sometimes, when a single point is removed from the training set, a CARTs learned parameters may change drastically.\n",
    "* CARTs also suffer from high variance when they are trained without constraints. In such case, they may overfit the training set.\n",
    "\n",
    "A solution that takes advantage of the flexibility of CARTs while reducing their tendency to memorize noise is ensemble learning."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ensemble learning can be summarized as follows:\n",
    "\n",
    "* Train different models on the same dataset.\n",
    "* Let each model make its predictions.\n",
    "* A meta-model aggregates predictions of individual models and outputs a final prediction\n",
    "\n",
    "The final prediction is more robust and less prone to errors than each individual model. The best results are obtained when the models are skillful but in different way meaning that if some models make predictions that are way off, the other models should compensate these errors. In such case, the meat-model's predictions are more robust."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take a look at the diagram below to visually understand how ensemble learning works for a classification problem:\n",
    "\n",
    "![Ensemble Learning](assets/ensemble.png)\n",
    "\n",
    "* First the training set is fed to different classifiers\n",
    "* Each classifier learns its parameters and makes predictions\n",
    "* The predictions are fed to a meta model which aggregates them and outputs a final prediction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Voting Classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's now take a look at an ensemble technique known as the voting classifier. More concretely, we'll consider a binary classification task. The ensemble here consists of N classifiers making the predictions $ P_0, P_1, ... , P_N $ with $P_i$ = 0 or 1. The meta-model outputs the final prediction by hard voting.\n",
    "\n",
    "To understand hard voting, consider a voting classifier that consists of 3 trained classifiers as shown in the diagram below:\n",
    "\n",
    "![Voting classifier](assets/voting_classifier.png)\n",
    "\n",
    "While classifiers 1 and 3 predict the label of 1 for a new data-point, classifier 2 predicts the label 0. In this case, 1 has 2 votes while 0 has 1 vote. As a result, the voting classifier predicts 1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define the ensemble"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following set of examples, we'll work with the [Indian Liver Patient Dataset](https://www.kaggle.com/jeevannagaraj/indian-liver-patient-dataset) from the UCI Machine learning repository."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we'll instantiate three classifiers to predict whether a patient suffers from a liver disease using all the features present in the dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.718171Z",
     "start_time": "2020-02-11T09:27:32.704092Z"
    }
   },
   "outputs": [],
   "source": [
    "utils.liver_patients.head()                           "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.723315Z",
     "start_time": "2020-02-11T09:27:32.720460Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import the classes used for the enesemble\n",
    "from sklearn.linear_model import LogisticRegression\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.neighbors import KNeighborsClassifier as KNN"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.727722Z",
     "start_time": "2020-02-11T09:27:32.725124Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate lr\n",
    "lr = LogisticRegression(solver='liblinear' ,random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.731376Z",
     "start_time": "2020-02-11T09:27:32.729087Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate knn\n",
    "knn = KNN(n_neighbors=27)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.735467Z",
     "start_time": "2020-02-11T09:27:32.733099Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate dt\n",
    "dt = DecisionTreeClassifier(min_samples_leaf=0.13, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.740260Z",
     "start_time": "2020-02-11T09:27:32.737490Z"
    }
   },
   "outputs": [],
   "source": [
    "# Define the list classifiers\n",
    "classifiers = [('Logistic Regression', lr), ('K Nearest Neighbours', knn), ('Classification Tree', dt)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate individual classifiers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example we'll evaluate the performance of the models in the list classifiers that we defined in the previous exercise. We'll do so by fitting each classifier on the training set and evaluating its test set accuracy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.745364Z",
     "start_time": "2020-02-11T09:27:32.741655Z"
    }
   },
   "outputs": [],
   "source": [
    "X = utils.liver_patients.drop('Liver_disease', axis=1)\n",
    "y = utils.liver_patients['Liver_disease']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.752106Z",
     "start_time": "2020-02-11T09:27:32.746968Z"
    }
   },
   "outputs": [],
   "source": [
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.773003Z",
     "start_time": "2020-02-11T09:27:32.753579Z"
    }
   },
   "outputs": [],
   "source": [
    "# Iterate over the pre-defined list of classifiers\n",
    "for clf_name, clf in classifiers:    \n",
    "    # Fit clf to the training set\n",
    "    clf.fit(X_train, y_train)    \n",
    "    \n",
    "    # Predict y_pred\n",
    "    y_pred = clf.predict(X_test)\n",
    "    \n",
    "    # Calculate accuracy\n",
    "    accuracy = accuracy_score(y_test, y_pred) \n",
    "    \n",
    "    # Evaluate clf's accuracy on the test set\n",
    "    print(f'{clf_name:s} : {accuracy:.3f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how `LogisticRegression` got the highest accuracy of 76.4%"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Better performance with a Voting Classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we'll evaluate the performance of a voting classifier that takes the outputs of the models defined in the list classifiers and assigns labels by majority voting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.776884Z",
     "start_time": "2020-02-11T09:27:32.774411Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import VotingClassifier from sklearn.ensemble\n",
    "from sklearn.ensemble import VotingClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.781009Z",
     "start_time": "2020-02-11T09:27:32.778298Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate a VotingClassifier vc\n",
    "vc = VotingClassifier(estimators=classifiers)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.797153Z",
     "start_time": "2020-02-11T09:27:32.782535Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit vc to the training set\n",
    "vc.fit(X_train, y_train) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.811044Z",
     "start_time": "2020-02-11T09:27:32.798603Z"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate the test set predictions\n",
    "y_pred = vc.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.816240Z",
     "start_time": "2020-02-11T09:27:32.813015Z"
    }
   },
   "outputs": [],
   "source": [
    "# Calculate accuracy score\n",
    "accuracy = accuracy_score(y_test, y_pred)\n",
    "print(f'Voting Classifier: {accuracy:.3f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice how the voting classifier achieves a test set accuracy of 77%. This value is greater than that achieved by LogisticRegression."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc-hr-collapsed": false
   },
   "source": [
    "# Bagging and Random Forests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bagging is an ensemble method involving training the same algorithm many times using different subsets sampled from the training data. In this section, we'll show how bagging can be used to create a tree ensemble. We'll also show how the random forests algorithm can lead to further ensemble diversity through randomization at the level of each split in the trees forming the ensemble."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bagging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this part of the lesson, we'll introduce an ensemble method known as Bootstrap aggregation or Bagging. In the last section we learned that the Voting Classifier is an ensemble of models that are fit to the same training set using different algorithms. We also say that the final predictions were obtained by majority voting. \n",
    "\n",
    "In `Bagging`, the ensemble is formed by models that use the same training algorithm. However, these models are not trained on the entire training set. Instead, each model is trained on a different subset of the data. In fact, Bagging stands for Bootstrap Aggregation.Its name refers to the fact that it uses a technique known as the `bootstrap`. Overall, Bagging has the effect of reducing the variance of individual models in the ensemble.\n",
    "\n",
    "Let's first try to understand what the bootstrap method is. Consider the case where we have 3 balls labeled A, B, and C. A bootstrap sample is a sample drawn from this with replacement. By replacement, we mean that any ball can be drawn many times.\n",
    "\n",
    "![Bootstrap](assets/bootstrap.png)\n",
    "\n",
    "For example, in the first bootstrap sample shown above in the diagram, B was drawn 3 times in a raw. In the second bootstrap sample, A was drawn two times while B was drawn once, and so on. Now, how can this help us produce an ensemble?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bagging: Training**\n",
    "\n",
    "In the training phase, bagging consists of drawing N different bootstrap samples from the training set. As shown in the diagram below, each of these bootstrap samples are the used to train N models that use the same algorithm:\n",
    "![Bootstrap Training](assets/bootstrap_training.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bagging: Prediction**\n",
    "\n",
    "When a new instance is fed to the different models, forming the bagging ensemble, each model output its prediction:\n",
    "\n",
    "![Bagging Prediction](assets/bagging_prediction.png)\n",
    "\n",
    "The meta-model collects these predictions and outputs a final prediction depending on the nature of the problem."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Bagging: Classification & Regression**\n",
    "\n",
    "* In *classification*, the final prediction is obtained by majority voting. The corresponding classifier in scikit-learn is `BaggingClassifier` \n",
    "* In *regression*, the final prediction is the average of the predictions made by the individual models forming the ensemble. The corresponding regressor in scikit-learn is `BaggingRegressor`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define the bagging classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following examples we'll work with the Indian Liver Patient dataset from the UCI machine learning repository. Our task is to predict whether a patient suffers from a liver disease using 10 features including Albumin, age and gender. We'll do so using a Bagging Classifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.824143Z",
     "start_time": "2020-02-11T09:27:32.817573Z"
    }
   },
   "outputs": [],
   "source": [
    "X = utils.liver_disease.drop('Liver_disease', axis=1)\n",
    "y = utils.liver_disease['Liver_disease']\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.829539Z",
     "start_time": "2020-02-11T09:27:32.826687Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import DecisionTreeClassifier\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "# Import BaggingClassifier\n",
    "from sklearn.ensemble import BaggingClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.833217Z",
     "start_time": "2020-02-11T09:27:32.830966Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate dt\n",
    "dt = DecisionTreeClassifier(random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.837467Z",
     "start_time": "2020-02-11T09:27:32.834518Z"
    }
   },
   "outputs": [],
   "source": [
    "bc = BaggingClassifier(base_estimator=dt, n_estimators=50, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate Bagging performance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we instantiated the bagging classifier, it's time to train it and evaluate its test set accuracy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.953765Z",
     "start_time": "2020-02-11T09:27:32.838933Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit bc to the training set\n",
    "bc.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:32.964841Z",
     "start_time": "2020-02-11T09:27:32.955327Z"
    }
   },
   "outputs": [],
   "source": [
    "# Predict test set labels\n",
    "y_pred = bc.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:27:56.819713Z",
     "start_time": "2020-02-11T09:27:56.816474Z"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate acc_test\n",
    "acc_test = accuracy_score(y_test, y_pred)\n",
    "print(f'Test set accuracy of bc: {acc_test:.2f}') "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Out of Bag Evaluation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall that in bagging, some instances may be sampled several times for one model. On the other hand, other instance may not be sampled at all."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Out Of Bag (OOB) instances**\n",
    "\n",
    "On average, for each model, 63% of the training instances are sampled. The remaining 37% that are not sampled constitute what is known as the Out-of-bag or OOB instances. Since OOB instances are not seen by a model during training, these can be used to estimate the performance of the ensemble without the need for cross-validation. This technique is known as OOB-evaluation.\n",
    "\n",
    "To understand OOB-evaluation more concretely, take a look at this diagram:\n",
    "\n",
    "![OOB Evaluation](assets/oob_evaluation.png)\n",
    "\n",
    "Here, for each model, the bootstrap instances are shown in blue while the OOB-instances are shown in red. Each of the N models constituting the ensemble is then trained on its corresponding bootstrap samples and evaluated on the OOB instances. This leads to the obtainment of `N` OOB scores labeled $OOB_1$ to $OOB_N$. The OOB-score of the bagging ensemble is evaluated as the average of these N OOB scores as shown by the formula on the top."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prepare the ground"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following example, we'll compare the OOB accuracy to the test set accuracy of a bagging classifier trained on the Indian Liver Patient dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In sklearn, we can evaluate the OOB accuracy of an ensemble classifier by setting the parameter `oob_score` to `True` during instantiation. After training the classifier, the OOB accuracy can be obtained by accessing the `.oob_score_` attribute from the corresponding instance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:32:28.250344Z",
     "start_time": "2020-02-11T09:32:28.247752Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import DecisionTreeClassifier\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "# Import BaggingClassifier\n",
    "from sklearn.ensemble import BaggingClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:32:40.027398Z",
     "start_time": "2020-02-11T09:32:40.024831Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate dt\n",
    "dt = DecisionTreeClassifier(min_samples_leaf=8, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:33:08.533968Z",
     "start_time": "2020-02-11T09:33:08.530809Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate bc\n",
    "bc = BaggingClassifier(base_estimator=dt, n_estimators=50, oob_score=True, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### OOB Score vs Test Set Score"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we instantiated `bc`, we will fit it to the training set and evaluate its test set and OOB accuracies."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:34:43.777279Z",
     "start_time": "2020-02-11T09:34:43.658988Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit bc to the training set \n",
    "bc.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:34:50.536759Z",
     "start_time": "2020-02-11T09:34:50.528185Z"
    }
   },
   "outputs": [],
   "source": [
    "# Predict test set labels\n",
    "y_pred = bc.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:35:00.505559Z",
     "start_time": "2020-02-11T09:35:00.502510Z"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate test set accuracy\n",
    "acc_test = accuracy_score(y_test, y_pred)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:35:07.968539Z",
     "start_time": "2020-02-11T09:35:07.966043Z"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate OOB accuracy\n",
    "acc_oob = bc.oob_score_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:35:36.849639Z",
     "start_time": "2020-02-11T09:35:36.846768Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print acc_test and acc_oob\n",
    "print(f'Test set accuracy: {acc_test:.3f}, OOB accuracy: {acc_oob:.3f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Random Forests (RF)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll learn now about another ensemble learning method knows as `Random Forests`. Recall that in bagging the base estimator could be any model, including a decision tree, logistics regression or even a neural network. Each estimator is trained on a distinct bootstrap sample drawn from the training set using all available features."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Random Forests is an ensemble method that uses a decision tree as a base estimator. In Random Forests, each estimator is trained on a different bootstrap sample having the same size as the training set. Random Forests introduces further randomization than bagging when training each of the base estimator. When each tree is trained, only $d$ features can be sampled at each node without replacement, where $d$ is a number smaller than the total number of features."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The diagram below shows the training procedure for random forests:\n",
    "\n",
    "![RF Training](assets/rf_training.png)\n",
    "\n",
    "Notice how each tree forming the ensemble is trained on a different bootstrap sample from the training set. In addition, when a tree is trained, at each node, only $d$ features are sampled from all features without replacement. The node is then split using the sampled feature that maximizes information gain. In scikit-learn $d$ defaults to the square-root of the number of features. For example, if there are 100 features, only 10 features are sampled at each node."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once trained, prediction can be made on new instances. When a new instance is fed to the different base estimators, each of them outputs a prediction. The predictions are then collected by the random forest's meta-model and a final prediction is made depending on the nature of the problem.\n",
    "\n",
    "![RF Prediction](assets/rf_prediction.png)\n",
    "\n",
    "* For `classification`, the final prediction is made by majority voting. The corresponding scikit-learn class is `RandomForestClassifier`.\n",
    "* For `regression`, the final prediction is the average of all the labels predicted by the base estimators. The corresponding scikit-learn class is `RandomForestRegressor`.\n",
    "\n",
    "In general, Random Forests achieves a lower variance than individual trees.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Feature Importance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When a tree based method is trained, the predictive power of a feature or its importance can be assessed. In scikit-learn, feature importance is assessed by measuring how much the tree nodes use a particular feature to reduce impurity. Note that the importance of a feature is expressed as a percentage indicating the weight of that feature in training and prediction. \n",
    "\n",
    "Once we train a tree-based model in scikit-learn, the features importances can be accessed by extracting the `feature_importance_` attribute from the model. To visualize the importance of features as assessed by `rf`, we can create a pandas series of the features importances and then sort the series and make a horizontal-barplot."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train a RF regressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following examples we'll predict bike rental demand in the Capital Bikeshare program in Washington, D.C using historical weather data from the [Bike Sharing Demand](https://www.kaggle.com/c/bike-sharing-demand) dataset available through Kaggle. For this purpose, we will be using the random forests algorithm. As a first step, we'll define a random forests regressor and fit it to the training set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:38:20.237539Z",
     "start_time": "2020-02-11T09:38:20.214938Z"
    }
   },
   "outputs": [],
   "source": [
    "bikes = pd.read_csv('data/bikes.csv')\n",
    "bikes.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:40:24.465301Z",
     "start_time": "2020-02-11T09:40:24.459760Z"
    }
   },
   "outputs": [],
   "source": [
    "X = bikes.drop('cnt', axis=1)\n",
    "y = bikes['cnt']\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:45:17.710138Z",
     "start_time": "2020-02-11T09:45:17.707689Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import RandomForestRegressor\n",
    "from sklearn.ensemble import RandomForestRegressor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:45:19.739290Z",
     "start_time": "2020-02-11T09:45:19.736771Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate rf\n",
    "rf = RandomForestRegressor(n_estimators=25, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:46:23.865966Z",
     "start_time": "2020-02-11T09:46:23.769886Z"
    }
   },
   "outputs": [],
   "source": [
    "rf.fit(X_train, y_train) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the RF regressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll now evaluate the test set RMSE of the random forests regressor `rf` that we trained above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:49:15.206186Z",
     "start_time": "2020-02-11T09:49:15.203666Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import mean_squared_error as MSE\n",
    "from sklearn.metrics import mean_squared_error as MSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:49:23.478910Z",
     "start_time": "2020-02-11T09:49:23.471907Z"
    }
   },
   "outputs": [],
   "source": [
    "y_pred = rf.predict(X_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:49:29.977554Z",
     "start_time": "2020-02-11T09:49:29.974624Z"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate the test set RMSE\n",
    "rmse_test = MSE(y_test, y_pred) ** 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:49:49.590541Z",
     "start_time": "2020-02-11T09:49:49.587931Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print rmse_test\n",
    "print(f'Test set RMSE of rf: {rmse_test:.2f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Visualizing features importances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we'll determine which features were the most predictive according to the random forests regressor `rf` that we trained above."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this purpose, we'll draw a horizontal barplot of the feature importance as assessed by `rf`. Fortunately, this can be done easily thanks to plotting capabilities of `pandas`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:52:02.374517Z",
     "start_time": "2020-02-11T09:52:02.369340Z"
    }
   },
   "outputs": [],
   "source": [
    "# Create a pd.Series of features importances\n",
    "importances = pd.Series(data=rf.feature_importances_, index= X_train.columns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:53:03.925363Z",
     "start_time": "2020-02-11T09:53:03.922038Z"
    }
   },
   "outputs": [],
   "source": [
    "# Sort importances\n",
    "importances_sorted = importances.sort_values()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T09:53:12.021030Z",
     "start_time": "2020-02-11T09:53:11.753871Z"
    }
   },
   "outputs": [],
   "source": [
    "# Draw a horizontal barplot of importances_sorted\n",
    "importances_sorted.plot(kind='barh', color='lightgreen')\n",
    "plt.title('Features Importances')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apparently, `hr` and `workingday` are the most important features according to `rf`. The importances of these two features add up to more than 90%!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc-hr-collapsed": false
   },
   "source": [
    "# Boosting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Boosting refers to an ensemble method in which several models are trained sequentially with each model learning from the errors of its predecessors. In this part of the lesson, we'll introduce two boosting methods: AdaBoost and Gradient Boosting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Adaboost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Boosting** refers to an ensemble method in which many predictors are trained and each predictor learns from the errors of its predecessor. More formally, in boosting many weak learners are combined to form a strong learner. A **weak learner** is a model doing slightly better than random guessing. For example, a decision tree with a maximum-depth of one, known as decision-stump, is a weak learner.\n",
    "\n",
    "In boosting, an ensemble of predictors are trained sequentially and each predictor tries to correct the errors made by its predecessor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AdaBoost stands for **Ada**ptive **Boost**ing. In AdaBoost, each predictor pays more attention to the instances wrongly predicted by its predecessor by constantly changing the weights of training instances. Further more, each predictor is assigned a coefficient $\\alpha$ that weighs its contribution in the ensemble's final prediction ($\\alpha$ depends on the predictor's training error).\n",
    "\n",
    "As shown in the diagram, there are N predictors in total:\n",
    "\n",
    "![AdaBoost Training](assets/adaboost.png)\n",
    "\n",
    "First, $predictor_1$ is trained on the initial dataset (X,y), and the training error for $predictor_1$ is determined. This error can be then be used to determine the $\\alpha_1$ which is $predictor_1$'s coefficient. $\\alpha_1$ is then used to determine the weights $W^{(2)}$ of the training instances for $predictor_2$. Notice how the incorrectly predicted instances shown in green acquire higher weights. When the weighted instances are used to train $predictor_2$, this predictor is forced to pay more attention to the incorrectly predicted instances. This process is repeated sequentially, until the $N$ predictors forming the ensemble are trained."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An important parameter used in training is the learning rate: $0 < \\eta < 1$; it is used to shrink the coefficient $\\alpha$ of a trained predictor. It's important to note that there's a trade-off between $\\eta$ and the number of estimators. A smaller value of $\\eta$ should be compensated by a greater number of estimators."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once all the predictors in the ensemble are trained, the label of a new instance can be predicted depending on the nature of the problem. \n",
    "\n",
    "* For `classification`, each predictor predicts the label of the new instance and the ensemble's prediction is obtained by weighted majority voting. The scikit-learn class is `AdaBoostClassifier`.\n",
    "* For `regression`, the same procedure is applied and the ensemble's prediction is obtained by performing a weighted average. The scikit-learn class is `AdaBoostRegressor`.\n",
    "\n",
    "CARTs are used most of the time in boosting because of their high variance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define the AdaBoost classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following examples we'll revisit the [Indian Liver Patient](https://www.kaggle.com/uciml/indian-liver-patient-records) dataset which was introduced in a previous section. Our task is to predict whether a patient suffers from a liver disease using 10 features including Albumin, age and gender. However, this time, we'll be training an AdaBoost ensemble to perform the classification task. In addition, given that this dataset is imbalanced, we'll be using the ROC AUC score as a metric instead of accuracy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a first step, we'll start by instantiating an AdaBoost classifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:32:16.532778Z",
     "start_time": "2020-02-11T11:32:16.530395Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import DecisionTreeClassifier\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "\n",
    "# Import AdaBoostClassifier\n",
    "from sklearn.ensemble import AdaBoostClassifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:33:00.432997Z",
     "start_time": "2020-02-11T11:33:00.430146Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate dt\n",
    "dt = DecisionTreeClassifier(max_depth=2, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:33:11.115983Z",
     "start_time": "2020-02-11T11:33:11.113292Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate ada\n",
    "ada = AdaBoostClassifier(base_estimator=dt, n_estimators=180, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train the AdaBoost classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we've instantiated the AdaBoost classifier `ada`, it's time train it. We will also predict the probabilities of obtaining the positive class in the test set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once the classifier `ada` is trained, call the `.predict_proba()` method by passing `X_test` as a parameter and extract these probabilities by slicing all the values in the second column."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:42:36.694254Z",
     "start_time": "2020-02-11T11:42:36.687621Z"
    }
   },
   "outputs": [],
   "source": [
    "X = utils.liver_disease.drop('Liver_disease', axis=1)\n",
    "y = utils.liver_disease['Liver_disease']\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:43:35.756265Z",
     "start_time": "2020-02-11T11:43:35.471971Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit ada to the training set\n",
    "ada.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:43:43.676251Z",
     "start_time": "2020-02-11T11:43:43.646416Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute the probabilities of obtaining the positive class\n",
    "y_pred_proba = ada.predict_proba(X_test)[:,1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the AdaBoost classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we're done training `ada` and predicting the probabilities of obtaining the positive class in the test set, it's time to evaluate `ada`'s ROC AUC score. Recall that the ROC AUC score of a binary classifier can be determined using the `roc_auc_score()` function from `sklearn.metrics`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:46:39.929255Z",
     "start_time": "2020-02-11T11:46:39.926812Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import roc_auc_score\n",
    "from sklearn.metrics import roc_auc_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:46:46.910352Z",
     "start_time": "2020-02-11T11:46:46.904989Z"
    }
   },
   "outputs": [],
   "source": [
    "# Evaluate test-set roc_auc_score\n",
    "ada_roc_auc = roc_auc_score(y_test, y_pred_proba)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:47:07.115150Z",
     "start_time": "2020-02-11T11:47:07.112399Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print roc_auc_score\n",
    "print(f'ROC AUC score: {ada_roc_auc:.2f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not bad! This untuned AdaBoost classifier achieved a ROC AUC score of 0.64!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gradient Boosting (GB)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gradient Boosting is a popular boosting algorithm that has a proven track record of winning many machine learning competitions. In gradient boosting, each predictor in the ensemble corrects its predecessor's error. In contrast to AdaBoost, the weights of the training instances are not tweaked. Instead, each predictor is trained using the residual errors of its predecessor as labels. In the following sections, we'll explore the technique  known as gradient boosted trees where the base learner is a CART."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand how gradient boosted trees are trained for a regression problem, take a look at the diagram here:\n",
    "\n",
    "![Gradient Boosting](assets/boosted_trees.png)\n",
    "\n",
    "The ensemble consists on $N$ trees. $Tree_1$ is trained using the features matrix $X$ and the dataset labels $y$. The predictions labeled $\\hat{y}_1$ are used to determine the training set residual errors $r_1$. $Tree_2$ is then trained using the features matrix $X$ and the residual errors $r_1$ of $Tree_1$ as labels. The predicted residuals $\\hat{r}_1$ are then used to determine the residuals of residuals which are labeled $r_2$. This process is repeated until all of the $N$ trees forming the ensemble are trained."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An important parameter used in training gradient boosted trees is `shrinkage`. In this context, shrinkage refers to the fact that the prediction of each tree in the ensemble is shrinked after it is multiplied by a learning rate $\\eta$ which is a number between 0 and 1.\n",
    "\n",
    "Similar to AdaBoost, there's a trade-off between $\\eta$ and the number of estimators. Decreasing the learning rate needs to be compensated by increasing the number of estimators in order for the ensemble to reach a certain performance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Once all trees in the ensemble are trained, prediction can be made. When a new instance is available, each tree predicts a label and the final ensemble prediction is given by the formula shown below:\n",
    "\n",
    "$$ y_{pred} = y_1 + \\eta r_1 + ... + \\eta r_N $$\n",
    "\n",
    "In scikit-learn, the class for a gradient boosting regressor is `GradientBoostingRegressor`. Though not discussed heree, a similar algorithm is used for classification problems. The class implementing gradient boosting classification in scikit-learn is `GradientBoostingClassifier`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Define the GB regressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll now revisit the [Bike Sharing Demand](https://www.kaggle.com/c/bike-sharing-demand) dataset that was introduced in the previous section. Recall that our task is to predict the bike rental demand using historical weather data from the Capital Bikeshare program in Washington, D.C.. For this purpose, we'll be using a gradient boosting regressor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a first step, we'll start by instantiating a gradient boosting regressor which we will train in the next example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:54:43.850345Z",
     "start_time": "2020-02-11T11:54:43.848220Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import GradientBoostingRegressor\n",
    "from sklearn.ensemble import GradientBoostingRegressor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:55:06.626867Z",
     "start_time": "2020-02-11T11:55:06.624155Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate gb\n",
    "gb = GradientBoostingRegressor(max_depth=4, n_estimators=200, random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train the GB regressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll now train the gradient boosting regressor `gb` that we instantiated in the previous example and predict test set labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:56:43.906948Z",
     "start_time": "2020-02-11T11:56:43.901085Z"
    }
   },
   "outputs": [],
   "source": [
    "X = bikes.drop('cnt', axis=1)\n",
    "y = bikes['cnt']\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, random_state = utils.SEED)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:57:08.336156Z",
     "start_time": "2020-02-11T11:57:08.174176Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit gb to the training set\n",
    "gb.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:57:16.838494Z",
     "start_time": "2020-02-11T11:57:16.833637Z"
    }
   },
   "outputs": [],
   "source": [
    "# Predict test set labels\n",
    "y_pred = gb.predict(X_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the GB regressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that the test set predictions are available, we can use them to evaluate the test set Root Mean Squared Error (RMSE) of `gb`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T11:59:11.545732Z",
     "start_time": "2020-02-11T11:59:11.542946Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import mean_squared_error as MSE\n",
    "from sklearn.metrics import mean_squared_error as MSE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:00:21.753483Z",
     "start_time": "2020-02-11T12:00:21.750399Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute MSE\n",
    "mse_test = MSE(y_test, y_pred)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:00:31.688619Z",
     "start_time": "2020-02-11T12:00:31.686190Z"
    }
   },
   "outputs": [],
   "source": [
    "# Compute RMSE\n",
    "rmse_test = mse_test ** 0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:00:54.978832Z",
     "start_time": "2020-02-11T12:00:54.975955Z"
    }
   },
   "outputs": [],
   "source": [
    "# Print RMSE\n",
    "print(f'Test set RMSE of gb: {rmse_test:.3f}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stochastic Gradient Boosting (SGB)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Gradient boosting involves an exhaustive search procedure. Each tree in the ensemble is trained to find the best split-points and the best features. This procedure may lead to CARTs that use the same split-points and possibly the same features. To mitigate these effects, we can use an algorithm known as stochastic gradient boosting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In stochastic gradient boosting, each CART is trained on a random subset of the training data. This subset is sampled without replacement. Further more, at the level of each node, features are sampled without replacement when choosing the best split-points. As a result, this creates further diversity in the ensemble and the net effect is adding more variance to the ensemble of trees."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Stochasting Gradient Boosting: Training**\n",
    "\n",
    "Let's take a closer look at the training procedure used in stochastic gradient boosting by examining the diagram shown below:\n",
    "\n",
    "![SGB Training](assets/sgb_training.png)\n",
    "\n",
    "First, instead of providing all the training instances to a tree, only a fraction of these instances are provided through sampling without relacement. The sample data is then used for training a tree. However, not all features are considered when a split is made. Instead, only a certain randomly sampled fraction of these features are used for this purpose.\n",
    "\n",
    "Once a tree is trained, predictions are made and the residual errors can be computed. These residual errors are multiplied by the learning rate $\\eta$ ad are fed to the next tree in the ensemble. This procedure is repeated seqentially until all the trees in the ensemble are trained.\n",
    "\n",
    "The prediction procedure for a new instance in stochastic gradient boosting is similar to that of gradient boosting.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Regression with SGB"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the following set of examples, we'll be working with the Bike Sharing Demand dataset and solving the bike count regression problem using stochastic gradient boosting."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:03:27.267504Z",
     "start_time": "2020-02-11T12:03:27.265412Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import GradientBoostingRegressor\n",
    "from sklearn.ensemble import GradientBoostingRegressor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:03:54.005623Z",
     "start_time": "2020-02-11T12:03:54.002419Z"
    }
   },
   "outputs": [],
   "source": [
    "# Instantiate sgbr\n",
    "sgbr = GradientBoostingRegressor(max_depth=4, \n",
    "                                 subsample=0.9,\n",
    "                                 max_features=0.75,\n",
    "                                 n_estimators=200,                                \n",
    "                                 random_state=utils.SEED)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Train the SGB regressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this example, we'll train the SGBR `sgbr` instantiated above and predict the test set labels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:05:03.994733Z",
     "start_time": "2020-02-11T12:05:03.819462Z"
    }
   },
   "outputs": [],
   "source": [
    "# Fit sgbr to the training set\n",
    "sgbr.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:05:14.298817Z",
     "start_time": "2020-02-11T12:05:14.293719Z"
    }
   },
   "outputs": [],
   "source": [
    "# Predict test set labels\n",
    "y_pred = sgbr.predict(X_test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate the SGB regressor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We have prepared the ground to determine the test set RMSE of `sgbr` which we evaluate in this example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2020-02-11T12:07:02.137403Z",
     "start_time": "2020-02-11T12:07:02.133176Z"
    }
   },
   "outputs": [],
   "source": [
    "# Import mean_squared_error as MSE\n",
    "from sklearn.metrics import mean_squared_error as MSE\n",
    "\n",
    "# Compute test set MSE\n",
    "mse_test = MSE(y_test, y_pred)\n",
    "\n",
    "# Compute test set RMSE\n",
    "rmse_test = mse_test ** 0.5\n",
    "\n",
    "# Print rmse_test\n",
    "print('Test set RMSE of sgbr: {:.3f}'.format(rmse_test))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The stochastic gradient boosting regressor achieves a lower test set RMSE than the gradient boosting regressor (which was 43.140)!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "**[Week 3 - Supervised Learning](https://radu-enuca.gitbook.io/ml-challenge/supervised-learning)**\n",
    "\n",
    "*Have questions or comments? Visit the ML Challenge Mattermost Channel.*"
   ]
  }
 ],
 "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"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": true
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}