{"cells":[{"metadata":{"_uuid":"f4ad785c5ba65f0b33d8dcebf88ba9d07c141c11"},"cell_type":"markdown","source":"## Ensemble Methods\n\n![](https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcRJt5zCyHpIt9K_GbD059NYcNF3rOqSmoKq3SaCnmrBAgUisPF4)"},{"metadata":{"_uuid":"5c24c9cb934a47072c125278ba6ef416c8beb687"},"cell_type":"markdown","source":"* **Ensemble methods** combine several **decision trees classifiers** to produce better **predictive performance** than a single **decision tree classifier.*The main principle behind the ensemble model is that a group of weak learners come together to form a strong learner, thus increasing the accuracy of the model.*** When we ***try to predict the target variable using any machine learning technique, the main causes of difference in actual and predicted values are noise, variance, and bias.** Ensemble helps to reduce these factors (except noise, which is irreducible error).\n\n![](https://www.analyticsvidhya.com/wp-content/uploads/2015/07/variance_bias.png)\n\n* **Ensemble learning** is **Fable of blind men and elephant.** All of the blind men had their own description of the elephant. Even though each of the description was true, it would have been better to come together and discuss their undertanding before coming to final conclusion. This story perfectly describes the Ensemble learning method.\n![](https://cdn-images-1.medium.com/max/1200/1*10t9S7xvWE5Z3NEZrmHG2w.jpeg)\n\n* Ensemble methods are meta-algorithms that combine several machine learning techniques into one predictive model in order to decrease variance (bagging), bias (boosting), or improve predictions (stacking). Ensemble methods can be divided into two groups: *sequential* ensemble methods where the base learners are generated sequentially (e.g. AdaBoost) and *parallel* ensemble methods where the base learners are generated in parallel (e.g. Random Forest). The basic motivation of sequential methods is to exploit the dependence between the base learners since the overall performance can be boosted by weighing previously mislabeled examples with higher weight.  The basic motivation of parallel methods is to exploit independence between the base learners since the error can be reduced dramatically by averaging. \n\n![](https://d3ansictanv2wj.cloudfront.net/figure_12-f5c12a524e288367ef4f59526486e0ce.jpg)\n\n* Most ensemble methods use a single base learning algorithm to produce homogeneous base learners, i.e. learners of the same type leading to *homogeneous ensembles*. There are also some methods that use heterogeneous learners, i.e. learners of different types, leading to *heterogeneous ensembles*. In order for ensemble methods to be more accurate than any of its individual members the base learners have to be as accurate as possible and as diverse as possible.\n"},{"metadata":{"_uuid":"d43abb06bf43060e30c25fa5b5e858f82a669f05"},"cell_type":"markdown","source":"### Bagging\n\n![](https://www.analyticsvidhya.com/wp-content/uploads/2015/07/bagging.png)"},{"metadata":{"_uuid":"e653f81f453e3796b4c9a0965722697fefc73ac7"},"cell_type":"markdown","source":"* **Bagging** stands for **bootstrap aggregation.*One way to reduce the variance of an estimate is to average together multiple estimates.*** \nFor example, we can train $M$ different trees $f_m$ on different subsets of the data (chosen randomly with replacement) and compute the ensemble:\n\n\\begin{equation}\n   f(x) = \\frac{1}{M}\\sum_{m=1}^{M}f_m(x) \n\\end{equation}\n\n* **Bagging uses bootstrap sampling to obtain the data subsets for training the base learners.** For **aggregating** the **outputs of base learners**, ***bagging uses voting for classification and averaging for regression.***\n"},{"metadata":{"trusted":true,"_uuid":"65ec862eaa22f3166bd227d6073365e12bd774d3"},"cell_type":"code","source":"%matplotlib inline\n\nimport itertools\nimport numpy as np\n\nimport seaborn as sns\nimport matplotlib.pyplot as plt\nimport matplotlib.gridspec as gridspec\n\nplt.style.use(\"fivethirtyeight\")\n\nfrom sklearn import datasets\n\nfrom sklearn.tree import DecisionTreeClassifier\nfrom sklearn.neighbors import KNeighborsClassifier\nfrom sklearn.linear_model import LogisticRegression\nfrom sklearn.ensemble import RandomForestClassifier\n\nfrom sklearn.ensemble import BaggingClassifier\nfrom sklearn.model_selection import cross_val_score, train_test_split\n\nfrom mlxtend.plotting import plot_learning_curves\nfrom mlxtend.plotting import plot_decision_regions\n\nnp.random.seed(0)\n\nimport warnings\n\ndef fxn():\n    warnings.warn(\"deprecated\", DeprecationWarning)\n    warnings.warn(\"ignore\", FutureWarning)\n\nwith warnings.catch_warnings():\n    warnings.simplefilter(\"ignore\")\n    fxn()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"c6a3ac278920cda3d5141a85373944b5f1fb9d82"},"cell_type":"code","source":"iris = datasets.load_iris()\nX, y = iris.data[:, 0:2], iris.target\n    \nclf1 = DecisionTreeClassifier(criterion='entropy', max_depth=1)\nclf2 = KNeighborsClassifier(n_neighbors=1)    \n\nbagging1 = BaggingClassifier(base_estimator=clf1, n_estimators=10, max_samples=0.8, max_features=0.8)\nbagging2 = BaggingClassifier(base_estimator=clf2, n_estimators=10, max_samples=0.8, max_features=0.8)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"cc6aa513f8f385adfed4c8db69e13b084b5d37ab"},"cell_type":"code","source":"label = ['Decision Tree', 'K-NN', 'Bagging Tree', 'Bagging K-NN']\nclf_list = [clf1, clf2, bagging1, bagging2]\n\nfig = plt.figure(figsize=(20, 12))\ngs = gridspec.GridSpec(2, 2)\ngrid = itertools.product([0,1],repeat=2)\n\nfor clf, label, grd in zip(clf_list, label, grid):        \n    scores = cross_val_score(clf, X, y, cv=3, scoring='accuracy')\n    print(\"Accuracy: %.2f (+/- %.2f) [%s]\" %(scores.mean(), scores.std(), label))\n        \n    clf.fit(X, y)\n    ax = plt.subplot(gs[grd[0], grd[1]])\n    fig = plot_decision_regions(X=X, y=y, clf=clf, legend=2)\n    plt.title(label)\n\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"7ef7b8e25fa4893917bbfeed06dc8a1084293820"},"cell_type":"markdown","source":"* The figure above shows the decision boundary of a decision tree and k-NN classifiers along with their bagging ensembles applied to the Iris dataset. The decision tree shows axes parallel boundaries while the $k=1$ nearest neighbors fits closely to the data points. The bagging ensembles were trained using $10$ base estimators with $0.8$ subsampling of training data and $0.8$ subsampling of features. The decision tree bagging ensemble achieved higher accuracy in comparison to k-NN bagging ensemble because k-NN are less sensitive to perturbation on training samples and therefore they are called *stable learners*. Combining stable learners is less advantageous since the ensemble will not help improve generalization performance."},{"metadata":{"trusted":true,"_uuid":"6f78e77ad0dfaf5827d6832822bf27e7f959ea42"},"cell_type":"code","source":"#plot learning curves\nX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)\n    \nplt.figure(figsize=(20,8))\nplot_learning_curves(X_train, y_train, X_test, y_test, bagging1, print_model=False, style='ggplot')\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"48e98cc1d567575f8a5868deabefd73352796e3e"},"cell_type":"markdown","source":"* The figure above shows learning curves for the bagging tree ensemble. We can see an average error of $0.3$ on the training data and a U-shaped error curve for the testing data. The smallest gap between training and test errors occurs at around $80\\%$ of the training set size."},{"metadata":{"trusted":true,"_uuid":"c2cb58b966f3091034a03184c4115a4690b5c022"},"cell_type":"code","source":"#Ensemble Size\nnum_est = np.linspace(1,100,20, dtype=int)\nbg_clf_cv_mean = []\nbg_clf_cv_std = []\nfor n_est in num_est:    \n    bg_clf = BaggingClassifier(base_estimator=clf1, n_estimators=n_est, max_samples=0.8, max_features=0.8)\n    scores = cross_val_score(bg_clf, X, y, cv=3, scoring='accuracy')\n    bg_clf_cv_mean.append(scores.mean())\n    bg_clf_cv_std.append(scores.std())","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"95df90e84b7a08d31ef92074b05f25f99863af3e"},"cell_type":"code","source":"plt.figure(figsize=(20,8))\n(_, caps, _) = plt.errorbar(num_est, bg_clf_cv_mean, yerr=bg_clf_cv_std, c='red', fmt='-o', capsize=5)\nfor cap in caps:\n    cap.set_markeredgewidth(1)                                                                                                                                \nplt.ylabel('Accuracy'); plt.xlabel('Ensemble Size'); plt.title('Bagging Tree Ensemble');\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"11217592d4323cfe2a153647403595b9b2694b90"},"cell_type":"markdown","source":"* The figure above shows how the test accuracy improves with the size of the ensemble. Based on cross-validation results, we can see the accuracy increases until approximately $10$ base estimators and then plateaus afterwards. Thus, adding base estimators beyond $10$ only increases computational complexity without accuracy gains for the Iris dataset."},{"metadata":{"_uuid":"78aabc15797be4e16762622f1384ce971cfc98c5"},"cell_type":"markdown","source":"* A commonly used class of ensemble algorithms are forests of randomized trees. In **random forests**, each tree in the ensemble is built from a sample drawn with replacement (i.e. a bootstrap sample) from the training set. In addition, instead of using all the features, a random subset of features is selected further randomizing the tree. As a result, the bias of the forest increases slightly but due to averaging of less correlated trees, its variance decreases resulting in an overall better model."},{"metadata":{"_uuid":"14b00e292e88b73cdacceafea4fe46c9fb174e7b"},"cell_type":"markdown","source":"* In **extremely randomized trees** algorithm randomness goes one step further: the splitting thresholds are randomized. Instead of looking for the most discriminative threshold, thresholds are drawn at random for each candidate feature and the best of these randomly-generated thresholds is picked as the splitting rule. This usually allows to reduce the variance of the model a bit more, at the expense of a slightly greater increase in bias."},{"metadata":{"_uuid":"52d6434de722fa62aae3239a55954f70c882d10d"},"cell_type":"markdown","source":"### Boosting\n\n![](https://www.analyticsvidhya.com/wp-content/uploads/2015/07/boosting.png)"},{"metadata":{"_uuid":"eb75fc3fa4d395bde3e3037c6f42b9a91f1a96cf"},"cell_type":"markdown","source":"* **Boosting** refers to a ***family of algorithms that are able to convert weak learners to strong learners.**The main principle of boosting is to fit a sequence of weak learners (models that are only slightly better than random guessing, such as small decision trees) to weighted versions of the data, where more weight is given to examples that were mis-classified by earlier rounds.*** \n* ***The predictions are then combined through a weighted majority vote (classification) or a weighted sum (regression) to produce the final prediction.*** \n* *The principal difference between boosting and the committee methods such as bagging is that base learners are trained in sequence on a weighted version of the data.*   "},{"metadata":{"trusted":true,"_uuid":"2bb3b418692bd499d063b076907f7d759d0f4db4"},"cell_type":"code","source":"import itertools\nimport numpy as np\n\nimport seaborn as sns\nimport matplotlib.pyplot as plt\nimport matplotlib.gridspec as gridspec\n\nfrom sklearn import datasets\n\nfrom sklearn.tree import DecisionTreeClassifier\nfrom sklearn.neighbors import KNeighborsClassifier\nfrom sklearn.linear_model import LogisticRegression\n\nfrom sklearn.ensemble import AdaBoostClassifier\nfrom sklearn.model_selection import cross_val_score, train_test_split\n\nfrom mlxtend.plotting import plot_learning_curves\nfrom mlxtend.plotting import plot_decision_regions","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"ed12322f85b06db9ebd7b3fc3fb0201d06efdf03"},"cell_type":"code","source":"iris = datasets.load_iris()\nX, y = iris.data[:, 0:2], iris.target\n    \n#XOR dataset\n#X = np.random.randn(200, 2)\n#y = np.array(map(int,np.logical_xor(X[:, 0] > 0, X[:, 1] > 0)))\n    \nclf = DecisionTreeClassifier(criterion='entropy', max_depth=1)\n\nnum_est = [1, 2, 3, 10]\nlabel = ['AdaBoost (n_est=1)', 'AdaBoost (n_est=2)', 'AdaBoost (n_est=3)', 'AdaBoost (n_est=10)']","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"8a5467bb579892fbf797891882b1eb3e4403676a"},"cell_type":"code","source":"fig = plt.figure(figsize=(20, 13))\ngs = gridspec.GridSpec(2, 2)\ngrid = itertools.product([0,1],repeat=2)\n\nfor n_est, label, grd in zip(num_est, label, grid):     \n    boosting = AdaBoostClassifier(base_estimator=clf, n_estimators=n_est)   \n    boosting.fit(X, y)\n    ax = plt.subplot(gs[grd[0], grd[1]])\n    fig = plot_decision_regions(X=X, y=y, clf=boosting, legend=2)\n    plt.title(label)\n\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"1dbf80f4772c6ddb6f32ec9ce3793ae57e8d508b"},"cell_type":"markdown","source":"* The **AdaBoost algorithm** is illustrated in the figure above. ***Each base learner consists of a decision tree with depth $1$, thus classifying the data based on a feature threshold that partitions the space into two regions separated by a linear decision surface that is parallel to one of the axes.***"},{"metadata":{"trusted":true,"_uuid":"611e7d6cad25d75fe43fd620d4608e6b74fe5848"},"cell_type":"code","source":"#plot learning curves\nX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)\n\nboosting = AdaBoostClassifier(base_estimator=clf, n_estimators=10)\n        \nplt.figure(figsize=(20,8))\nplot_learning_curves(X_train, y_train, X_test, y_test, boosting, print_model=False, style='ggplot')\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"f5e3f199600a4189fc239b71c6f8e5bdb5a9a1e2"},"cell_type":"code","source":"#Ensemble Size\nnum_est = np.linspace(1,100,20, dtype=int)\nbg_clf_cv_mean = []\nbg_clf_cv_std = []\nfor n_est in num_est:\n    ada_clf = AdaBoostClassifier(base_estimator=clf, n_estimators=n_est)\n    scores = cross_val_score(ada_clf, X, y, cv=3, scoring='accuracy')\n    bg_clf_cv_mean.append(scores.mean())\n    bg_clf_cv_std.append(scores.std())","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"21dddbf48e1b0a08dac2f6875fc3480807fe68b0"},"cell_type":"code","source":"plt.figure(figsize=(20,8))\n\n(_, caps, _) = plt.errorbar(num_est, bg_clf_cv_mean, yerr=bg_clf_cv_std, c='red', fmt='-o', capsize=5)\nfor cap in caps:\n    cap.set_markeredgewidth(1) \nplt.xticks(range(4), ['KNN', 'RF', 'NB', 'Adaboost'])\nplt.ylabel('Accuracy'); plt.xlabel('Ensemble Size'); plt.title('AdaBoost Ensemble');\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"681555e22aaaf7573a56b7a284a76caa39de2cd1"},"cell_type":"markdown","source":"The figure above shows how the test accuracy improves with the size of the ensemble."},{"metadata":{"_uuid":"3fb2ea7fb551a95af323e8ee2ab6544748a3b150"},"cell_type":"markdown","source":"* **Gradient Tree Boosting** is a ***generalization of boosting to arbitrary differentiable loss functions. It can be used for both regression and classification problems.***"},{"metadata":{"_uuid":"96d9f4e1643eead02864e49812c4e29d12fcdb4f"},"cell_type":"markdown","source":"### Stacking\n\n![](https://cdn-images-1.medium.com/max/665/0*G0Mv1RkCPMqiPZzu.png)"},{"metadata":{"_uuid":"fe1a502107cddf6bb426ffb061a6584593ef28d5"},"cell_type":"markdown","source":"* **Stacking is an ensemble learning technique that combines multiple classification or regression models via a meta-classifier or a meta-regressor.**\n* ***The base level models are trained based on complete training set then the meta-model is trained on the outputs of base level model as features. The base level often consists of different learning algorithms and therefore stacking ensembles are often heterogeneous.***"},{"metadata":{"trusted":true,"_uuid":"f31a6cab3013bfd56d864514d0ea01b8982d0f55"},"cell_type":"code","source":"import itertools\nimport numpy as np\nimport seaborn as sns\nimport matplotlib.pyplot as plt\nimport matplotlib.gridspec as gridspec\n\nfrom sklearn import datasets\n\nfrom sklearn.linear_model import LogisticRegression\nfrom sklearn.neighbors import KNeighborsClassifier\nfrom sklearn.naive_bayes import GaussianNB \nfrom sklearn.ensemble import RandomForestClassifier\nfrom mlxtend.classifier import StackingClassifier\n\nfrom sklearn.model_selection import cross_val_score, train_test_split\n\nfrom mlxtend.plotting import plot_learning_curves\nfrom mlxtend.plotting import plot_decision_regions","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"ae9316c955673c94f2d12a61f7a9d98d3b4af7f3"},"cell_type":"code","source":"iris = datasets.load_iris()\nX, y = iris.data[:, 1:3], iris.target\n\nclf1 = KNeighborsClassifier(n_neighbors=1)\nclf2 = RandomForestClassifier(random_state=1)\nclf3 = GaussianNB()\nlr = LogisticRegression()\nsclf = StackingClassifier(classifiers=[clf1, clf2, clf3], \n                          meta_classifier=lr)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"48bdb8dcc5093483da9c99767af0d3095687d052"},"cell_type":"code","source":"import warnings\nwarnings.simplefilter(action='ignore', category=FutureWarning)\nlabel = ['KNN', 'Random Forest', 'Naive Bayes', 'Stacking Classifier']\nclf_list = [clf1, clf2, clf3, sclf]\n    \nfig = plt.figure(figsize=(20,13))\ngs = gridspec.GridSpec(2, 2)\ngrid = itertools.product([0,1],repeat=2)\n\nclf_cv_mean = []\nclf_cv_std = []\nfor clf, label, grd in zip(clf_list, label, grid):\n        \n    scores = cross_val_score(clf, X, y, cv=3, scoring='accuracy')\n    print (\"Accuracy: %.2f (+/- %.2f) [%s]\" %(scores.mean(), scores.std(), label))\n    clf_cv_mean.append(scores.mean())\n    clf_cv_std.append(scores.std())\n        \n    clf.fit(X, y)\n    ax = plt.subplot(gs[grd[0], grd[1]])\n    fig = plot_decision_regions(X=X, y=y, clf=clf)\n    plt.title(label)\n\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"72ef5e6dd593d64978073cb2ee2ddf586bc53ea9"},"cell_type":"markdown","source":"* ***The stacking ensemble*** is illustrated int the figure above. It consists of ***k-NN, Random Forest and Naive Bayes base classifiers whose predictions are combined by Lostic Regression as a meta-classifier.*** We can see the blending of decision boundaries achieved by the ***stacking classifier.***"},{"metadata":{"trusted":true,"_uuid":"a48ee68f6d775485137e8a34dc572dfac92aecbf"},"cell_type":"code","source":"#plot classifier accuracy    \nplt.figure(figsize=(20,8))\n(_, caps, _) = plt.errorbar(range(4), clf_cv_mean, yerr=clf_cv_std, c='orange', fmt='-o', capsize=5)\nfor cap in caps:\n    cap.set_markeredgewidth(1)                                                                                                                                \nplt.xticks(range(4), ['KNN', 'RF', 'NB', 'Stacking'])        \nplt.ylabel('Accuracy'); plt.xlabel('Classifier'); plt.title('Stacking Ensemble');\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"8274859ca9f60f6e8041b576c380ec846239caa4"},"cell_type":"code","source":"#plot learning curves\nX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)\n    \nplt.figure(figsize=(20,8))\nplot_learning_curves(X_train, y_train, X_test, y_test, sclf, print_model=False, style='ggplot')\nplt.show()","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"817fc4fb9d26be30d6b9d28f8ecbc39a401863e8"},"cell_type":"markdown","source":"**We can see that stacking achieves higher accuracy than individual classifiers and based on learning curves, it shows no signs of overfitting.**"}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.6.6","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":1}