Chapter 15 - Random Forests.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 15 - Random Forests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.1 - Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Bagging or bootstrap aggregation (section 8.7) is a technique for reducing the variance of an estimated prediction function. Bagging seems to work especially well for high-variance, low-bias procedures, such as trees. \n",
    "* For regression, we simply fit the same regression tree many times to bootstrap sampled versions of the training data, and average the result. \n",
    "* For classification, a committee of trees each cast a vote for the predicted class.\n",
    "* Boosting has a committee of weak learners that evolve over time and the members cast a weighted vote. Boosting appears to dominate bagging on most problems, and became the preferred choice.\n",
    "* Random forests are a substantial modification of bagging that builds a large collection of de-correlated trees, and then averages them. \n",
    "* On many problems the performance of random forests is very similar to boosting, and they are simpler to train and tune. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.2 - Definition of Random Forests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Trees are ideal candidates for bagging, since they can capture complex interaction structures in the data, and if grown sufficiently deep, have relatively low bias.\n",
    "* Since trees are notoriously noisy, they benefit greatly from the averaging. \n",
    "* The bias of bagged trees is the same as that of the individual trees, and the only hope of improvement is through variance reduction. \n",
    "* We try to reduce the correlation between trees as much as possible. For this reason, we do things like select k <= p variables for each tree. Often $k=\\sqrt{p}$ or as small as 1.  This reduces the overall variance of the estimates.\n",
    "* Not all estimators can be improved by shaking up the data like this. It seems that highly nonlinear estimators, such as trees, benefit the most.\n",
    "* Random forests do remarkably well, with very little tuning required."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.3 - Details of Random Forests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* When used for classification, a random forest obtains a class vote from each tree, and then classifies using majority vote. \n",
    "* When used for regression, the predictions from each tree at a target point x are simply averaged.\n",
    "\n",
    "Recommended default hyper-parameters:\n",
    "* For classification, the default value for m is $\\sqrt{p}$ and the minimum node size is one.\n",
    "* For regression, the default value for m is $p/3$ and the minimum node size is five.\n",
    "* In practice, they should be treated as tuning parameters.\n",
    "\n",
    "**Out of Bag Samples**\n",
    "* Out of bag sample -- for each observation $z_i = (x_i,y_i)$, construct its random forest predictor by averaging only those trees corresponding to bootstrap samples in which $z_i$ did not appear.\n",
    "* An OOB error estimate is almost identical to that obtained by N-fold cross-validation.\n",
    "* Hence unlike many other nonlinear estimators, random forests can be fit in one sequence, with cross-validation being performed along the way. \n",
    "* Once the OOB error stabilizes, the training can be terminated.\n",
    "\n",
    "**Variable Importance**\n",
    "* At each split in each tree, the improvement in the split-criterion is the importance measure attributed to the splitting variable, and is accumulated over all the trees in the forest separately for each variable.\n",
    "* An alternative way to find variable importance is to pass the OOB samples down the tree and record the error. Then, you take the $j^{th}$ feature and randomly permute it (scramble its values) and then compute the OOB error again and see how much worse the error is.  The scrambling is intended to make the variable useless.\n",
    "\n",
    "**Proximity Plots**\n",
    "* Create an NxN matrix for the observation data.\n",
    "* For every tree, any pair of OOB observations sharing a terminal node has their proximity increased by one. \n",
    "* The proximity plot gives an indication of which observations are effectively close together in the eyes of the random forest classifier.\n",
    "* Proximity plots for random forests often look very similar, irrespective of the data, which casts doubt on their utility. \n",
    "\n",
    "**Random Forests and Overfitting**\n",
    "* When the number of variables is large, but the fraction of relevant variables small, random forests are likely to perform poorly with small m. At each split the chance can be small that the relevant variables will be selected.\n",
    "* When the number of relevant variables increases, the performance of random forests is surprisingly robust to an increase in the number of noise variables. \n",
    "* With 6 relevant and 100 noise variables, the probability of a relevant variable being selected at any split is 0.46 assuming $m = \\sqrt{p} = \\sqrt{106}$.\n",
    "* Increasing B (the number of trees) does not cause the random forest sequence to overfit.\n",
    "* The average of fully grown (not controlling the depth) trees can result in too rich of model, and incur unnecessary variance."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 15.4 - Analysis of Random Forests"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Correlation between pairs of trees decreases as $m$ decreases (the number of variables randomly chosen).\n",
    "* As in bagging, the bias of a random forest is the same as the bias of any of the individual sampled trees.\n",
    "* Improvements in the prediction obtained by bagging or random forests are solely a result of variance reduction.\n",
    "* As $m$ decreases, the bias increases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Accuracy Score: 0.9736842105263158\n",
      "Feature ranking:\n",
      "1. feature 2 (0.442171)\n",
      "2. feature 3 (0.424505)\n",
      "3. feature 0 (0.098740)\n",
      "4. feature 1 (0.034584)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAEICAYAAABPgw/pAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAATqklEQVR4nO3dbZRdV33f8e/PioWpMbipJtTowVJBhCrACukg0tKQWcFu5VAsVoMbuYXElESlrYpTHhqTshzHSUtJE9N2RS9QwaspBIQx1GsSlCpusUN5rIRjSCQjOihQSXGR/AiGYCP498U9ji/j0cwZ6Up3tP39rHWXzz5nz9n/e5b1m6197tFNVSFJOvudM+4CJEmjYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQFfzkvxSkneNuw7pdIufQ9d8knwZeDrwnaHdz66qPzvFc/5cVf2PU6vu7JPkOuBZVfWqcdei9jhDVx8vr6qnDL1OOsxHIcn3jXP8k3W21q2zh4Guk5LkaUneneTuJEeS/FqSZd2xZyb5aJJ7k9yT5HeSXNgdew+wBvjdJA8l+VdJppIcnnX+Lye5pNu+LsnNSd6b5GvAVfONP0et1yV5b7e9NkkleU2SQ0nuT/K6JC9M8vkkDyT5raGfvSrJJ5L8VpIHk3whyUuHjj8jyXSS+5LMJPn5WeMO1/064JeAn+7e++e6fq9JcleSryc5mOSfDJ1jKsnhJG9McrR7v68ZOv7kJL+Z5CtdfR9P8uTu2I8m+WT3nj6XZGrW+zrYjfmnSf7RIv8X0BLkjEEn678AR4FnAecDvwccAt4JBHgb8DHgqcCHgOuAX6iqVyf5MYaWXIaDZh6bgSuAnwGeBLxvnvH7eBGwHngJMA38d+AS4Fzgj5J8sKr+cKjvzcAK4O8DH06yrqruA3YCfwI8A3gOcGuSL1XVR09Q9woev+RyFPh7wMGunt9Psqeq7uiO/1XgacBK4FLg5iS3VNX9wG8APwT8LeD/dbV+N8lK4CPAq7v39lLgQ0meA3wT+E/AC6vqQJKLgO/ved20hDlDVx+3dLO8B5LckuTpwE8yCOhvVNVR4B3AFoCqmqmqW6vq4ao6BtwA/Pgp1vCpqrqlqr7L4JfECcfv6Ver6ltV9QfAN4D3V9XRqjoC/C/gBUN9jwL/oaq+XVUfAA4AL0uyGngx8Ivdue4E3sUgvB9Xd1X9+VyFVNVHqupLNfCHwB8APzbU5dvA9d34u4CHgB9Mcg7wj4Grq+pIVX2nqj5ZVQ8DrwJ2VdWubuxbgb3ddQP4LvDcJE+uqrurat8irp2WKGfo6uMVwzcwk2xkMJO9O8mju89hMEOmC/z/yCCULuiO3X+KNRwa2r54vvF7+urQ9p/P0X7KUPtIfe+nB77CYEb+DOC+qvr6rGOTJ6h7TkkuA34ZeDaD9/GXgD8e6nJvVR0fan+zq28FcB7wpTlOezFwRZKXD+07F7itqr6R5KeBNwHvTvIJ4I1V9YWFatXS5gxdJ+MQ8DCwoqou7F5Praof6o7/W6CA51XVUxnMFjP087M/WvUNBiEGQLcWPjGrz/DPLDT+qK3M0G8OBvcA/qx7fX+SC2YdO3KCuh/XTvIkBktSvwE8vaouBHbxvdfrRO4BvgU8c45jh4D3DF2fC6vq/Kr6dwBVtbuqLgUuAr4A/Oce42mJM9C1aFV1N4Nlgd9M8tQk53Q3Qh9dVrmAwbLAg91a7ptnneKrwF8ban8ROC/Jy5KcC7yVwXrzyY4/aj8AvD7JuUmuAP46g+WMQ8AngbclOS/J84HXAu+d51xfBdZ2yyUAyxm812PA8W62/nf6FNUtP90I3NDdnF2W5G92vyTeC7w8yd/t9p/X3WBdleTpSTYnOZ/BL8aHGCzB6CxnoOtk/QyDMNrPYDnlZgazPYBfAX4EeJDBjbkPz/rZtwFv7dbk31RVDwL/jMH68xEGM/bDzG++8UftMwxuoN4D/BvglVV1b3fsSmAtg9n6fwN+eYHP13+w+++9Se7olmteD9zE4H38QwY3aft6E4PlmT3AfcDbgXO6XzabGXyq5hiDGfubGfyZPwd4Q1fzfQzub/zTRYypJcoHi6R5JLmKwSdy/va4a5EW4gxdkhphoEtSI1xykaRGOEOXpEaM7cGiFStW1Nq1a8c1vCSdlT772c/eU1Wzn9MAxhjoa9euZe/eveMaXpLOSkm+cqJjLrlIUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGga8mYmppiampq3GVIZy0DfcwMMUmjYqBLUiMMdElqhIEuSY3oFehJNiU5kGQmyTVzHH9Hkju71xeTPDD6UiVJ81nwn89NsgzYDlzK4JvY9ySZrqr9j/apqn851P9fAC84DbVKkubRZ4a+EZipqoNV9QiwE9g8T/8rgfePojhJUn99An0lcGiofbjb9zhJLgbWAR89wfGtSfYm2Xvs2LHF1ipJmseob4puAW6uqu/MdbCqdlTVZFVNTkzM+Q1KkqST1CfQjwCrh9qrun1z2YLLLZI0Fn0CfQ+wPsm6JMsZhPb07E5JngP8ZeBToy1RktTHgoFeVceBbcBu4C7gpqral+T6JJcPdd0C7KyqOj2lSpLms+DHFgGqahewa9a+a2e1rxtdWZKkxfJJUUlqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSI3oFepJNSQ4kmUlyzQn6/IMk+5PsS/K+0ZYpSVrIgt9YlGQZsB24FDgM7EkyXVX7h/qsB94CvLiq7k/yA6erYEnS3PrM0DcCM1V1sKoeAXYCm2f1+Xlge1XdD1BVR0dbpiRpIX0CfSVwaKh9uNs37NnAs5N8Ismnk2waVYGSpH56fUl0z/OsB6aAVcDHkjyvqh4Y7pRkK7AVYM2aNSMaWpIE/WboR4DVQ+1V3b5hh4Hpqvp2Vf0p8EUGAf89qmpHVU1W1eTExMTJ1ixJmkOfQN8DrE+yLslyYAswPavPLQxm5yRZwWAJ5uAI65QkLWDBQK+q48A2YDdwF3BTVe1Lcn2Sy7tuu4F7k+wHbgPeXFX3nq6iJUmP12sNvap2Abtm7bt2aLuAN3QvSdIY+KSoJDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNaJXoCfZlORAkpkk18xx/Kokx5Lc2b1+bvSlSpLms+BX0CVZBmwHLgUOA3uSTFfV/lldP1BV205DjZKkHvrM0DcCM1V1sKoeAXYCm09vWZKkxeoT6CuBQ0Ptw92+2X4qyeeT3Jxk9VwnSrI1yd4ke48dO3YS5UqSTmRUN0V/F1hbVc8HbgV+e65OVbWjqiaranJiYmJEQ0uSoF+gHwGGZ9yrun1/oaruraqHu+a7gL8xmvIkSX31CfQ9wPok65IsB7YA08Mdklw01LwcuGt0JUqS+ljwUy5VdTzJNmA3sAy4sar2Jbke2FtV08Drk1wOHAfuA646jTVLkuawYKADVNUuYNesfdcObb8FeMtoS5MkLYZPikpSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiN6PSn6hJS0OV7VmRlH0hnnDF2SGmGgS1IjDHRJaoSBLkmN8KaoFuYNYums4AxdkhphoEtSI3oFepJNSQ4kmUlyzTz9fipJJZkcXYmSpD4WDPQky4DtwGXABuDKJBvm6HcBcDXwmVEXKUlaWJ8Z+kZgpqoOVtUjwE5g8xz9fhV4O/CtEdYnSeqpT6CvBA4NtQ93+/5Ckh8BVlfVR+Y7UZKtSfYm2Xvs2LFFFytJOrFTvima5BzgBuCNC/Wtqh1VNVlVkxMTE6c6tCRpSJ9APwKsHmqv6vY96gLgucDtSb4M/Cgw7Y1RSTqz+gT6HmB9knVJlgNbgOlHD1bVg1W1oqrWVtVa4NPA5VW197RULEma04KBXlXHgW3AbuAu4Kaq2pfk+iSXn+4CJUn99Hr0v6p2Abtm7bv2BH2nTr0sSdJi+aSoJDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREGuiQ1wkCXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNaJXoCfZlORAkpkk18xx/HVJ/jjJnUk+nmTD6EuVJM1nwUBPsgzYDlwGbACunCOw31dVz6uqHwZ+Hbhh5JVKkubVZ4a+EZipqoNV9QiwE9g83KGqvjbUPB+o0ZUoSeqjz5dErwQODbUPAy+a3SnJPwfeACwHfmKuEyXZCmwFWLNmzWJrlSTNY2Q3Ratqe1U9E/hF4K0n6LOjqiaranJiYmJUQ0uS6BfoR4DVQ+1V3b4T2Qm84lSKkiQtXp9A3wOsT7IuyXJgCzA93CHJ+qHmy4D/M7oSJUl9LLiGXlXHk2wDdgPLgBural+S64G9VTUNbEtyCfBt4H7gZ09n0ZKkx+tzU5Sq2gXsmrXv2qHtq0dclyRpkXxSVJIaYaBLUiMMdElqhIEuSY0w0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRpCZqammJqamrcZegsY6BLUiMMdElqhIEuSY0w0CWpEQa6JDWiV6An2ZTkQJKZJNfMcfwNSfYn+XyS/5nk4tGXKkmaz4KBnmQZsB24DNgAXJlkw6xufwRMVtXzgZuBXx91oZKk+fWZoW8EZqrqYFU9AuwENg93qKrbquqbXfPTwKrRlilJWkifQF8JHBpqH+72nchrgd8/laIkSYvX60ui+0ryKmAS+PETHN8KbAVYs2bNKIeWpCe8PjP0I8Dqofaqbt/3SHIJ8K+By6vq4blOVFU7qmqyqiYnJiZOpl5J0gn0CfQ9wPok65IsB7YA08MdkrwAeCeDMD86+jIlSQtZMNCr6jiwDdgN3AXcVFX7klyf5PKu278HngJ8MMmdSaZPcDpJ0mnSaw29qnYBu2btu3Zo+5IR1yVJWiSfFJWkRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNGOmj/1q828ddgKRmOEOXpEYY6JLUCANdkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcIHi7Rk3D7uAqSznDN0SWpEr0BPsinJgSQzSa6Z4/hLktyR5HiSV46+TEnSQhYM9CTLgO3AZcAG4MokG2Z1+7/AVcD7Rl2gJKmfPmvoG4GZqjoIkGQnsBnY/2iHqvpyd+y7p6FGSVIPfZZcVgKHhtqHu32LlmRrkr1J9h47duxkTiFJOoEz+imXqtoB7ACYnJysMzm2NBJJm+OVfxxb0GeGfgRYPdRe1e2TJC0hfQJ9D7A+yboky4EtwPTpLUuStFgLBnpVHQe2AbuBu4CbqmpfkuuTXA6Q5IVJDgNXAO9Msu90Fi3piWNqaoqpqalxl3FW6LWGXlW7gF2z9l07tL2HwVKMJGlMfFJUkhphoEtSIwx0SWqEgS5JjTDQJakRBrokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqxBn999AlNcR/G37JcYYuSY0w0CWpEQa6JDXCQJekRhjoktSIXoGeZFOSA0lmklwzx/EnJflAd/wzSdaOulBJ0vwWDPQky4DtwGXABuDKJBtmdXstcH9VPQt4B/D2URcqSZpfnxn6RmCmqg5W1SPATmDzrD6bgd/utm8GXpqc6Q+pStITW58Hi1YCh4bah4EXnahPVR1P8iDwV4B7hjsl2QpsBVizZs1JlnyGnMUPF4yc1+IxZ+paPPot97fffmbGOxleiyXnjN4UraodVTVZVZMTExNncmhJal6fQD8CrB5qr+r2zdknyfcBTwPuHUWBkqR++gT6HmB9knVJlgNbgOlZfaaBn+22Xwl8tMq/p0vSmbTgGnq3Jr4N2A0sA26sqn1Jrgf2VtU08G7gPUlmgPsYhL4knbLbXTvvrde/tlhVu4Bds/ZdO7T9LeCK0ZYmSVoMnxSVpEYY6JLUCANdkhphoEtSI/wKOmkJ8pMdOhnO0CWpEQa6JDXCQJekRhjoktQIA12SGmGgS1IjDHRJaoSBLkmNMNAlqREZ1/dQJDkGfGUsgy89K5j1/atPYF6Lx3gtHuO1eMzFVTXnd3iOLdD1mCR7q2py3HUsBV6Lx3gtHuO16MclF0lqhIEuSY0w0JeGHeMuYAnxWjzGa/EYr0UPrqFLUiOcoUtSIwx0SWqEgT5GSVYnuS3J/iT7klw97prGJcl5Sf53ks911+JXxl3TuCTZlORAkpkk14y7nnFKcmOSo0n+ZNy1nA1cQx+jJBcBF1XVHUkuAD4LvKKq9o+5tDMuSYDzq+qhJOcCHweurqpPj7m0MyrJMuCLwKXAYWAPcOUT8f8JgCQvAR4C/mtVPXfc9Sx1ztDHqKrurqo7uu2vA3cBK8db1XjUwENd89zu9UScbWwEZqrqYFU9AuwENo+5prGpqo8B9427jrOFgb5EJFkLvAD4zHgrGZ8ky5LcCRwFbq2qJ+K1WAkcGmof5gn6S16LZ6AvAUmeAnwI+IWq+tq46xmXqvpOVf0wsArYmMS/YkuLYKCPWbde/CHgd6rqw+OuZymoqgeA24BN465lDI4Aq4faq7p90oIM9DHqbgS+G7irqm4Ydz3jlGQiyYXd9pMZ3BT8wnirGos9wPok65IsB7YA02OuSWcJA328Xgy8GviJJHd2r58cd1FjchFwW5LPMwi1W6vq98Zc0xlXVceBbcBuBjfJb6qqfeOtanySvB/4FPCDSQ4nee24a1rK/NiiJDXCGbokNcJAl6RGGOiS1AgDXZIaYaBLUiMMdElqhIEuSY34/yJoxk+DfbU8AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "from sklearn.ensemble import RandomForestClassifier\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn.metrics import accuracy_score\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "iris = load_iris()\n",
    "X = iris.data\n",
    "y = iris.target\n",
    "\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y , random_state = 1)\n",
    "clf = RandomForestClassifier(n_estimators=100)\n",
    "clf.fit(X_train, y_train)\n",
    "predicted = clf.predict(X_test)\n",
    "print('Accuracy Score: {}'.format(accuracy_score(predicted, y_test)))\n",
    "\n",
    "importances = clf.feature_importances_\n",
    "std = np.std([tree.feature_importances_ for tree in clf.estimators_], axis=0)\n",
    "indices = np.argsort(importances)[::-1]\n",
    "\n",
    "# Print the feature ranking\n",
    "print(\"Feature ranking:\")\n",
    "for f in range(X.shape[1]):\n",
    "    print(\"%d. feature %d (%f)\" % (f + 1, indices[f], importances[indices[f]]))\n",
    "\n",
    "# Plot the feature importances of the forest\n",
    "plt.figure()\n",
    "plt.title(\"Feature importances\")\n",
    "plt.bar(range(X.shape[1]), importances[indices],\n",
    "       color=\"r\", yerr=std[indices], align=\"center\")\n",
    "plt.xticks(range(X.shape[1]), indices)\n",
    "plt.xlim([-1, X.shape[1]])\n",
    "plt.show()"
   ]
  }
 ],
 "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.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}