Bagging is a procedure that let's use bootstrapping to reduce the variance, and ultimately performance, of a prediction. The procedure can be defined as follows:
\n",
"We have data $D=[(X_1, Y_1),(X_2, Y_2),...,(X_N, Y_N)]$ and we want to learn:$\\:\\: E[Y|X]=\\hat{f}(X)$. Define a bootstrap sample $D^b$ as $N$ samples from $D$, sampled with replacement. Let $E^b[Y|X]=\\hat{f}^b(X)$ be the function learned from training set $D^b$.\n",
"Our bagged prediction is then the mean of all estimates of $f^b(X)$. I.e.,\n",
"
\n",
"
We can see in the above example that variance of the bootstrapped predictions is very high, especially around the extreme values of $X$, where there is less data. The goal of Bagging is to reduce the variance of the prediction (and thus improve accuracy). The lever that controls the amount of variance reduction is the number of bootstrap samples used.\n",
"
\n",
"When to use Bagging
\n",
"According to the original Bagging paper by Leo Breiman, bagging will produce a much better reduction in training error when the underlying classifier or regression model is unstable, and sensitive to minor variations of the data $D$. The above example was meant to show Bagging at work. We used a linear regression on polynomial features, and even though the underlying model was misspecified (we used degree 6 where the truth is degree 3), the bagged estimate isn't too far from the estimate without bagging. One must be careful when choosing to use bagging, because it can actually hurt performance if the underlying model is fairly stable (if you rerun the above regression example with different data sets or different bootstrapping iterations, you might find that the bagged MSE is worse).\n",
"
The Random Forest algorithm is probably the most well known and utilized implementation of the Bagging technique. A RF is an ensemble of Decision Trees, where both bagging and random feature selection are used to reduce the variance of the forest. The basic algorithm goes as follows:
\n",
"Assume we have a data matrix $D=[X,Y]$ with $N$ records and $M$ features.
\n",
"\n",
"Train
\n",
"For each $b$ of $B$ iterations:\n",
"
We'll start by building a forest using SKlearn.ensemble. Check out here for a brief overview of Ensemble methods in Python. We'll also compare this to a single tree. This test is close to an off-the-shelf test, in the sense that we are not doing any intelligent hyper-parameter optimization. However, we do use a few well reasoned starting parameters." ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from sklearn.ensemble import RandomForestClassifier\n", "from sklearn.tree import DecisionTreeClassifier\n", "import pandas as pd\n", "import course_utils as bd\n", "imp.reload(bd)\n", "\n", "\n", "f = 'C:/Users/kevin/Documents/GitHub/DS_course/datasets/Cell2Cell_data.csv'\n", "dat=pd.read_csv(f, header=0, sep=',')\n", "train, test = bd.trainTest(dat, 0.8)\n", "lab = 'churndep'\n", "\n", "\n", "#We'll build a RF and compare to a DT\n", "clf_def = DecisionTreeClassifier(criterion='entropy', min_samples_leaf = 20)\n", "clf_def = clf_def.fit(train.drop(lab, 1), train[lab])\n", "dt_pred = clf_def.predict_proba(test.drop(lab,1))\n", "\n", "rf_def = RandomForestClassifier(criterion='entropy', n_estimators=100)\n", "rf_def = rf_def.fit(train.drop(lab, 1), train[lab])\n", "rf_pred = rf_def.predict_proba(test.drop(lab,1))\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
Now compare the forest to the tree using AUC
" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [], "source": [ "from sklearn.metrics import roc_curve, auc, roc_auc_score\n", "import course_utils as bd\n", "imp.reload(bd)\n", "\n", "\n", "bd.plotAUC(test[lab], dt_pred[:,1], 'DT')\n", "plt.show()\n" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": true }, "outputs": [], "source": [ "bd.plotAUC(test[lab], rf_pred[:,1], 'RF')\n", "plt.show()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can see that with little optimization involved, the RF is already a bit better. Let's see how much better we can do with a grid search on both the DT and the RF. We have already covered DT optimization in a different module, so here we'll focus on the input parameters of the RandomForestClassifier object that let us tune the forest.
\n",
"\n",
"The following two are forest specific:\n",
"
Usually we would want to use cross-validation for performance tuning. For Random Forests, this becomes problematic, as cross-validation with RF's can be painfully slow. That's because each cross-validation step requires building k*n_estimators trees. One advantage of a random forest is that it performs what is called an \"out-of-bag\" error calculation. Remember that each tree is built from a bootstrap sample of the data, so that for each tree, some portion of the data is not used for that tree. The RF method computes an out-of-bag prediction for each record $[x_i, y_i]$ by averaging the prediction $f^b(x_i,y_i)$ on record $i$ for the bootstrap iterations in which record $i$ was not chosen in the bootstrap. The out-of-bag prediction can then be used to compute out-of-sample error for model selection and validation. This method should be equivalent to $N$-fold cross-validation. \n",
"\n",
"
\n",
"We'll start by building a tree of oob predictions enabled and then compare the performance to a true hold out set.\n",
"\n",
"
We can see two very important things here. \n", "
We can see in the plot above that the forest gets better with more trees, but we see that this effect tapers off asymptotically. We also see somewhat of a Golidlocks phenomenon with respect to the optimal number of features. Having too few features is suboptimal (i.e., max_feat=1), probably due to high bias in the trees. Conversely, having too many features (max_feat=11) is also bad, and this is because the individual trees are too correlated with each other, which prevents the Bagging approach from reducing the overall variance (see the analysis below to understand the math behind this statement). The right number of features is in the middle. We see that choosing $3$ or $6$ perform relatively the same. $3$ happens to be closer to the good heuristic default, which is max_feat=sqrt(total feats). \n",
"
\n",
"Next, for the purpose of educating ourselves, we'll also look at the Test set AUC's on each of the design options above.\n",
"
We can see similar patterns in the true holdout evaluation as we did in the OOB evaluation. We also tend to see a few more things. For one thing, having more trees actually hurts the performance for some levels of max_feat. We also see that the best choice for max_feat was indeed $3$.\n", "\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Feature Importance\n", "Much like with Decision Trees, the Random Forest Classifier has a built in mechanism for evaluating feature importance. Quoting the sklearn documentation:
\n",
"\n",
"Features used at the top of the tree contribute to the final prediction of a larger fraction of the input samples. The expected fraction of the samples they contribute to can thus be used as an estimate of the relative importance of the features.\n",
"
\n",
"The above computation is made for each feature in each tree and then averaged over all trees in the forest. The Random Forest Classifier returns an attribute with an importance score for each feature, and these scores sum to $1$ across all features.\n",
"
\n",
"We'll train a RF on the best options found above and then look at the feature importances.\n",
"\n",
"
We can show with a little algebra why Random Forests lead to generally better estimation performance.
Let's say that the variance of a single tree of size $N$ and $p$ features is: $Var(T_b(X))=\\sigma^2$. Similarly the variance of the Random Forest is the variance of the sum of such trees, i.e., $Var(RF(X))=Var(\\frac{1}{B}\\sum\\limits_{b=1}^B \\: T_b(X)).$ Because the invidual trees are trained with overlapping records and features, the individual tree estimates are correlated. Thus, the variance does not factor completely cleanly into a sum of individual tree variances. We'll solve this by using the following relation:
\n",
"\n",
"