Part_11.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Ensemble Methods\n",
    "Ensemble methods are *meta-algorithms* that add randomization to learning algorithms so to have them generate multiple predictors on the same training data. These predictors are then aggregated, either linearly or by taking a majority vote, to form a single predictor.\n",
    "\n",
    "Adding randomization and then combining predictors has an *averaging effect* on the performance of the learning algorithm, which corresponds to **reducing variance** and **increasing bias**.\n",
    "\n",
    "For this reason, ensemble methods are often used with nonparametric learning algorithms (such as tree predictors) that have little bias.\n",
    "\n",
    "In this notebook we explore two such methods: bagging and random forests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import seaborn as sns\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.ensemble import BaggingClassifier\n",
    "from sklearn.model_selection import train_test_split, cross_val_score, validation_curve, learning_curve\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Forest Cover Type Dataset\n",
    "This dataset includes information on trees. More specifically, the type (which is the label to predict), shadow coverage, distance to nearby landmarks (e.g., roads), soil type, and local topography. There are 7 classes of tree types, 55 features, and a total of 15120 data points."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "forest = pd.read_csv('../Datasets/forest-cover-type.csv')\n",
    "forest.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "forest.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The class distribution is perfectly balanced."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ax = sns.countplot(x=\"Cover_Type\", data=forest)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We control that there are no missing values with the method `isna()`, and then we sum the results over rows in each column."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "forest.isna().sum() # check for missing values in columns"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then create two `ndarrays` $X$ and $y$ containing data points and labels. We also create a train-test split with proportions $2/3-1/3$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = forest.drop(columns=['Id', 'Cover_Type']).values\n",
    "y = forest['Cover_Type'].values\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we evaluate a tree classifier algorithm on this split."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "learner = DecisionTreeClassifier(criterion='gini')\n",
    "\n",
    "learner.fit(X_train, y_train)\n",
    "y_pred = learner.predict(X_test)\n",
    "test_score = accuracy_score(y_test,y_pred)\n",
    "np.round(test_score, decimals=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The resulting tree classifier is quite large and deep."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "int(learner.tree_.node_count), int(learner.tree_.max_depth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We compute the CV estimate of the risk."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "scores = cross_val_score(learner, X, y, cv=5)\n",
    "np.round(scores.mean(), decimals=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Changing the splitting criterion does not help."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "learner = DecisionTreeClassifier(criterion='entropy')\n",
    "\n",
    "scores = cross_val_score(learner, X, y, cv=5)\n",
    "np.round(scores.mean(), decimals=2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we look at the learning curve from 1K to 9K examples."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sizes = range(1000, 10001, 2000)\n",
    "train_size, train_score, val_score = learning_curve(learner, X, y, train_sizes=sizes, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plt.title('Decision tree')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(train_size, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(train_size, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(train_size, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training accuracy\")\n",
    "plt.plot(train_size, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Training size')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zero training error indicates that the algorithm has no bias, while the large difference between training and test performance reveals a high variance. The final cross-validated performance is only $66\\%$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(np.round(np.mean(val_score, 1), decimals=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see what happens when we constrain the depth of the tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "depths = np.arange(1,33,5)\n",
    "learner = DecisionTreeClassifier()\n",
    "train_score, val_score = validation_curve(learner, X, y, param_name='max_depth', param_range=depths, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.title('Tree classifier vs. depth')\n",
    "plt.plot(depths, np.mean(val_score, 1), label='CV accuracy')\n",
    "plt.plot(depths, np.mean(train_score, 1), label='Training accuracy')\n",
    "plt.legend()\n",
    "plt.xlabel('Depth')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Below depth 5 the tree underfits. Above depth 5, overfitting starts. However, the CV estimate of the accuracy does not get any worse. Injecting bias could be the way to improve performance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bagging\n",
    "The first ensemble method we explore on this dataset is *Bagging*. This method uses any base algorithm $A$ and creates different predictors on a given training set $S$ (viewed as a $m \\times d$ matrix of data points and features) by subsampling rows and colums of $S$ and feeding the resulting random matrix to $A$.\n",
    "\n",
    "We run bagging with the tree classifier algorithm as base algorithm.\n",
    "\n",
    "We start by looking at the learning curve while using bagging over a **single** tree classifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_lrn = DecisionTreeClassifier(criterion='gini')\n",
    "bag_lrn = BaggingClassifier(base_estimator=tree_lrn, n_estimators=1)\n",
    "\n",
    "sizes = range(1000, 10001, 2000)\n",
    "train_size, train_score, val_score = learning_curve(bag_lrn, X, y, train_sizes=sizes, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plt.title('A single bagging tree')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(train_size, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(train_size, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(train_size, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(train_size, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Training size')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Due to the subsampling of the data matrix, the bagged algorithm has a higher bias and a smaller variance than the base algorithm. However the cross-validated accuracy went down a bit, revealing that the decrease in variance did not compensate for the increase in bias."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(np.round(np.mean(val_score, 1), decimals=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now test bagging with $10$ tree classifiers instead of one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_lrn = DecisionTreeClassifier()\n",
    "bag_lrn = BaggingClassifier(base_estimator=tree_lrn, n_estimators=10)\n",
    "sizes = range(1000, 10001, 2000)\n",
    "train_size, train_score, val_score = learning_curve(bag_lrn, X, y, train_sizes=sizes, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plt.title('Bagging')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(train_size, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(train_size, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(train_size, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(train_size, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Training size')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the resulting bagged algorithm has now essentially no bias on this dataset (zero training error), and the variance has improved with respect to using a single tree classifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(np.round(np.mean(val_score, 1), decimals=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Random Forest\n",
    "Our second method is *Random Forest*. Unlike bagging, Random Forest uses **only tree predictor algorithms as base algorithms**. The data matrix is subsampled as in Bagging, but Random Forest uses an additional randomization. When splitting a node during the construction of the tree, the split that is chosen is no longer the best split among all features (as in the standard tree classifier algorithm). Instead, the split is optimized over a random subset of the features. Hence the bias of Random Forest is higher than that of Bagging applied to tree predictors, but the decrease in variance usually compensates for the increase in bias, hence yielding an overall better model.\n",
    "\n",
    "As Random Forest works well also with shallow trees, we limit the depth of the trees to $10$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rf_lrn = RandomForestClassifier(n_estimators=10, max_depth=10)\n",
    "sizes = range(1000, 10001, 2000)\n",
    "train_size, train_score, val_score = learning_curve(rf_lrn, X, y, train_sizes=sizes, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.title('Random Forest')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(train_size, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(train_size, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(train_size, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(train_size, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Training size')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As expected, the bias increased and the decrease of the variance compensated this increase. However, the resulting performance is similar if not worse than that of Bagging."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(np.round(np.mean(val_score, 1), decimals=2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now investigate how the depth of the trees affects the performance of Random Forest. We explore a range of depths from $3$ to $30$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "depths = np.arange(3,31,3)\n",
    "learner = RandomForestClassifier(n_estimators=10)\n",
    "train_score, val_score = validation_curve(learner, X, y, param_name='max_depth', param_range=depths, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.title('Random Forest')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(depths, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(depths, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(depths, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(depths, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Tree depth')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that depths larger than $15$ give little or no improvement. Therefore, we run a direct comparison between Bagging and Random Forest with tree depth capped at $15$. We plot cross-validated performance for $1$, $10$ and $100$ trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_trees = [1,10,100]\n",
    "tree_lrn = DecisionTreeClassifier()\n",
    "bag_lrn = BaggingClassifier(base_estimator=tree_lrn)\n",
    "rf_lrn = RandomForestClassifier(max_depth=15)\n",
    "train_score, bag_val_score = validation_curve(bag_lrn, X, y, \n",
    "                                              param_name='n_estimators',\n",
    "                                              param_range=num_trees,\n",
    "                                              cv=3)\n",
    "train_score, rf_val_score = validation_curve(rf_lrn, X, y,\n",
    "                                             param_name='n_estimators',\n",
    "                                             param_range=num_trees,\n",
    "                                             cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.title('Bagging vs. Random Forest')\n",
    "bag_val_score_mean = np.mean(bag_val_score, axis=1)\n",
    "bag_val_score_std = np.std(bag_val_score, axis=1)\n",
    "rf_val_score_mean = np.mean(rf_val_score, axis=1)\n",
    "rf_val_score_std = np.std(rf_val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.xscale(\"log\")\n",
    "plt.fill_between(num_trees, bag_val_score_mean - bag_val_score_std,\n",
    "                 bag_val_score_mean + bag_val_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(num_trees, rf_val_score_mean - rf_val_score_std,\n",
    "                 rf_val_score_mean + rf_val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(num_trees, bag_val_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Bagging\")\n",
    "plt.plot(num_trees, rf_val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"Random Forest\")\n",
    "plt.legend()\n",
    "plt.xlabel('Number of Trees')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, Bagging still performs better but Random Forest uses trees that are much smaller on average than those used by Bagging (depth $15$ as opposed to depth around $30$).\n",
    "\n",
    "Next, we consider a different dataset."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### MNIST dataset\n",
    "Handwritten numerals. The original dataset is already split in training (60K) and test (10K) sets. For efficiency reasons, we only work with the test set, which we further split in training and test.\n",
    "\n",
    "Each row of the data matrix consists of 785 values: the first value is the label (a number from 0 to 9) and the remaining 784 values are the pixel values (a number from 0 to 255)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mnist = pd.read_csv(\"../Datasets/MNIST/mnist_test.csv\")\n",
    "mnist.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mnist.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We create the data matrix, the list of labels, and a train/test split with proportions $4/5-1/5$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mnist_X = mnist.drop(\"label\",1)\n",
    "mnist_y = mnist[\"label\"]\n",
    "X = mnist_X.values\n",
    "y = mnist_y.values\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, it is instructive to visualize the original images from the list of pixels."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(6,6))\n",
    "for digit_num in range(0,64):\n",
    "    plt.subplot(8,8,digit_num+1)\n",
    "    grid_data = mnist_X.iloc[digit_num].values.reshape(28,28)\n",
    "    plt.imshow(grid_data, interpolation = \"none\", cmap = \"bone_r\")\n",
    "    plt.xticks([])\n",
    "    plt.yticks([])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We start by checking the performance of the standard tree classifier algorithm. Since the number of features is higher in this dataset, we set the option `random` for choosing which leaf to split. This speeds up the computation at the cost of building a slightly larger tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_lrn = DecisionTreeClassifier(splitter='random')\n",
    "\n",
    "tree_lrn.fit(X_train, y_train)\n",
    "y_pred = tree_lrn.predict(X_test)\n",
    "test_score = accuracy_score(y_test,y_pred)\n",
    "np.round(test_score, decimals=2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "int(tree_lrn.tree_.node_count), int(tree_lrn.tree_.max_depth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The analysis of the learning curve for the tree classifier algorithm shows essentially no bias and a large variance (see below). Another good case for Bagging!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sizes = range(1000, 6666, 1000)\n",
    "train_size, train_score, val_score = learning_curve(tree_lrn, X, y, train_sizes=sizes, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plt.title('Decision tree')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(train_size, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(train_size, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(train_size, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(train_size, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Training size')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We run the tree classifier algorithm as base algorithm for Bagging, and we generate a total of $10$ trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree_lrn = DecisionTreeClassifier(splitter='random')\n",
    "bag_lrn = BaggingClassifier(base_estimator=tree_lrn, n_estimators=10)\n",
    "sizes = range(1000, 6666, 1000)\n",
    "train_size, train_score, val_score = learning_curve(bag_lrn, X, y, train_sizes=sizes, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.title('Bagging')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(train_size, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(train_size, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(train_size, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(train_size, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Training size')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bagging is working pretty well: we did not get any bias and the variance went down significantly.\n",
    "\n",
    "We now check the performance of Random Forest with a cap of $10$ on the depth of the trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "rf_lrn = RandomForestClassifier(n_estimators=10, max_depth=10)\n",
    "\n",
    "sizes = range(1000, 6666, 1000)\n",
    "train_size, train_score, val_score = learning_curve(rf_lrn, X, y, train_sizes=sizes, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plt.title('Random Forest')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(train_size, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(train_size, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(train_size, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(train_size, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Training size')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "OK, while the variance error went down nicely, the overall performance is worse than Bagging due to a slight increase of the bias.\n",
    "\n",
    "We then take a look at the performance of Random Forest as we vary the depth of the trees."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "depths = np.arange(3,31,3)\n",
    "learner = RandomForestClassifier(n_estimators=10)\n",
    "train_score, val_score = validation_curve(learner, X, y, param_name='max_depth', param_range=depths, cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "plt.title('Random Forest')\n",
    "train_score_mean = np.mean(train_score, axis=1)\n",
    "train_score_std = np.std(train_score, axis=1)\n",
    "val_score_mean = np.mean(val_score, axis=1)\n",
    "val_score_std = np.std(val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.fill_between(depths, train_score_mean - train_score_std,\n",
    "                 train_score_mean + train_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(depths, val_score_mean - val_score_std,\n",
    "                 val_score_mean + val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(depths, train_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Training score\")\n",
    "plt.plot(depths, val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"CV accuracy\")\n",
    "plt.legend()\n",
    "plt.xlabel('Tree depth')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We see a good spot at approximately depth $12$. We are now ready to run a direct comparison between Bagging and Random Forest with depth capped at $12$. In order to further speed up computation, we use two other options: `min_samples_split=20` (the minimum number of examples required to split a leaf) and `min_samples_leaf=10` (a split will only be considered if it leaves at least $10$ training examples in each child leaf)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "num_trees = [1,10,100]\n",
    "tree_lrn = DecisionTreeClassifier(splitter='random', min_samples_split=20, min_samples_leaf=10)\n",
    "bag_lrn = BaggingClassifier(base_estimator=tree_lrn)\n",
    "rf_lrn = RandomForestClassifier(max_depth=12, min_samples_split=20, min_samples_leaf=10)\n",
    "train_score, bag_val_score = validation_curve(bag_lrn, X, y,\n",
    "                                              param_name='n_estimators',\n",
    "                                              param_range=num_trees,\n",
    "                                              cv=3)\n",
    "train_score, rf_val_score = validation_curve(rf_lrn, X, y,\n",
    "                                             param_name='n_estimators',\n",
    "                                             param_range=num_trees,\n",
    "                                             cv=3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.title('Bagging vs. Random Forest')\n",
    "bag_val_score_mean = np.mean(bag_val_score, axis=1)\n",
    "bag_val_score_std = np.std(bag_val_score, axis=1)\n",
    "rf_val_score_mean = np.mean(rf_val_score, axis=1)\n",
    "rf_val_score_std = np.std(rf_val_score, axis=1)\n",
    "plt.grid()\n",
    "plt.xscale(\"log\")\n",
    "plt.fill_between(num_trees, bag_val_score_mean - bag_val_score_std,\n",
    "                 bag_val_score_mean + bag_val_score_std, alpha=0.1,\n",
    "                 color=\"r\")\n",
    "plt.fill_between(num_trees, rf_val_score_mean - rf_val_score_std,\n",
    "                 rf_val_score_mean + rf_val_score_std, alpha=0.1, color=\"g\")\n",
    "plt.plot(num_trees, bag_val_score_mean, 'o-', color=\"r\",\n",
    "         label=\"Bagging\")\n",
    "plt.plot(num_trees, rf_val_score_mean, 'o-', color=\"g\",\n",
    "         label=\"Random Forest\")\n",
    "plt.legend()\n",
    "plt.xlabel('Number of Trees')\n",
    "plt.ylabel('Accuracy')\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So, finally Random Forest is taking the lead when the number of trees is large enough. Recall that Random Forest predictors have a much smaller memory footprint than Bagging predictors. For this reason, Random Forest is often preferred in industrial applications. Both methods are highly parallelizable, as trees can be spread across many cores and evaluated in parallel."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}