目录

1 什么是Ensemble Methods？
2 Ensemble Methods的类别有哪些？
  2.1 Bagging (Bootstrap aggregating)
    2.1.1 Random Forest
  2.2 Boosting methods
    2.2.1 Gradient Boosting Machines/Models (GBM)
  2.3 Stacking
  2.4 Bukets of Models

1 什么是Ensemble Methods？

机器学习的算法中，讨论的最多的是某种特定的算法，比如Decision Tree，KNN等，在实际工作中，Ensemble methods（组合方法）的效果往往是最好的，因为它往往可以打破bias-variance tradeoff。

所谓Ensemble methods，就是把几种机器学习的算法组合到一起，或者把一种算法的不同参数组合到一起，即把多个弱学习者（weak learner）结合起来，就会产生一个强学习者。

打一个比方，单个的学习器，我们把它类比为一个独裁者。而组合起来的学习器（Ensemble methods），我们把它类比为一个决策委员会。前者由一个人来根据经验来决策一个事件（对于回归问题，我们类比为预测一个数字）。后者有一系列的委员来决定。我们假设二者享有的经验（训练数据）是相同的。前者的个人能力可能比后者中的任意一个委员都要强大，但它也有它的缺陷。然而，对于后者，委员的各自能力或许不是很突出，但是各有所长，各有所短，对于一个事件，大家按照各自的优势做出判断，最后投票（可能是加权的投票）做出决定（对于回归问题，我们类比为对各自的预测值做平均，同样，可能是加权的平均）。

Ensemble methods不仅适合大数据集，也适合小数据集。同时我们常见的结果计算方法如Max Voting, Averaging, Weighted Averaging也算是简单的Ensemble methods。

1. Bagging (stands for Bootstrap Aggregating) is a way to decrease the variance of your prediction by generating additional data for training from your original dataset using combinations with repetitions to produce multisets of the same cardinality/size as your original data. By increasing the size of your training set you can't improve the model predictive force, but just decrease the variance, narrowly tuning the prediction to expected outcome.

2. Boosting is a two-step approach, where one first uses subsets of the original data to produce a series of averagely performing models and then "boosts" their performance by combining them together using a particular cost function (=majority vote). Unlike bagging, in the classical boosting the subset creation is not random and depends upon the performance of the previous models: every new subsets contains the elements that were (likely to be) misclassified by previous models.

3. Stacking is a similar to boosting: you also apply several models to your original data. The difference here is, however, that you don't have just an empirical formula for your weight function, rather you introduce a meta-level and use another model/approach to estimate the input together with outputs of every model to estimate the weights or, in other words, to determine what models perform well and what badly given these input data.
   

2 Ensemble Methods的类别有哪些？

2.1 Bagging (Bootstrap aggregating)

Averaging methods/Bagging是指最终的model给出的output是所有models的算术平均。

目的

单一的强算法很容易就导致over-fitting，variance很大，经过aggregate之后就消除此问题。

步骤

STEP1 - Bootstrapping: 从总的数据集中抽取M个training sets，这样会产生M个有着相同bias的sparallel models（比如N个没有pruning的trees，每一个tree有high variance but low bias）。
STEP2 - Averaging: 对这些树的output求平均，这样可以减少model variance，这样variance和bias都相对于单个tree model能降低。

一个Bagging tree的算法

1. 从数据中有放回地取一个大小为N的随机样本(bootstrap样本)。
2. 像往常一样构造一个分类树，但不要修剪。
3. 为每个终端节点分配一个类，并存储每个case的类。
4. 大量重复步骤1-3。
5. 对于数据集中的每个observation，计算[它被分类在某一个类别中的树的数量/总的树的数量]。
6. 通过对树集的多数投票，将每个观察结果分配到一个最终类别。如果在大量的树中，一个给定的观察值有51%的时间被分类为“1”，这就成为它的class。

如何计算error

使用Out-of-Bag (OOB) Error Estimation。也就是对每一个observation，它可能被用来train一个model，也可能落在bag之外变成OOB test set。我们用所有对它来说是OOB的model output取平均值作为它的predicted value，然后算error。Bagging不需要cross validation。

手写版bagging tree图例

2.1.1 Random Forest

Random Forest是bagging的一种，其应用于tree model上。可以说是最好的classification model之一。

为什么要在bagging基础上创造RF

在Bagging中，一个强预测因子将在所有的树中占主导地位，导致所有baggesd trees都相似且outputs之间有很强的correlation，即便在averaging之后也难以大幅减少variance。而Random Forest通过每次node split对predictor的random choice给弱预测因子机会，从而解决了这个问题。

算法

1. 从数据中有放回地取一个大小为N的随机样本(bootstrap样本)。
2. 无放回地抽取M个预测变量
3. 使用步骤2中选择的预测变量构建split
4. 对于后续的每个split，重复步骤2和步骤3，直到树达到所需的大小。不修剪。每棵树都是由随机样本的case和每个split的random sampled features产生的。
5. 为每个终端节点分配一个类，并存储每个case的类。
6. 大量重复步骤1-5。
7. 对于数据集中的每个observation，计算[它被分类在某一个类别中的树的数量/总的树的数量]。
8. 通过对树集的多数投票，将每个观察结果分配到一个最终类别。如果在大量的树中，一个给定的观察值有51%的时间被分类为“1”，这就成为它的class。

需要调节的参数

Random Forest包括3个主要的优化参数。

• Node Size节点大小：与决策树不同，森林中每棵树的终端节点上的观测数量可能非常小。我们的目标是grow尽可能少的unbiased tree。
• Number of Trees树的数量：实际上，500棵树往往是一个不错的选择。
• Number of Predictors Sampled采样的预测变量的数量：Rule of thumb: m=p/3 for regression; m=sqrt(p) for classification；可以通过OOB error找到最优的m。

如果数据集是Unbalanced

Taking Costs into Account。考虑如下两种方法：

• Weighted Classification Votes: After all of the trees are built, one can differentially weight the classification votes over trees. For example, one vote for classification in the rare category might count the same as two votes for classification in the common category.

• Stratified Bootstrap Sampling: When each bootstrap sample is drawn before a tree is built, one can oversample one class of cases for which forecasting errors are relatively more costly. The procedure is much in the same spirit as disproportional stratified sampling used for data collection (Thompson, 2002).

如何对decision tree的rule做出解释

Random forest为了精确牺牲了解释力度，但是我们可以通过variable importance plot去弥补一些，看一看哪些predictor在预测中发挥重要作用。
特定一个变量的Variable importance等于[RSS或者Gini在split中下降的总数/RF中tree的总数]。Variable importance越高，这个predictor在预测中越重要。

2.2 Boosting methods（提升算法）

Boosting methods是指一种迭代，即利用一个基础算法进行预测，然后在后续的其他算法中利用前面算法的结果，通过给 misclassified examples更多的权重来重点处理错误数据，从而不断的减少错误率。迭代地构建弱分类器，并将它们聚合为最终的强分类器。其动机是使用几种简单的弱算法来达到很强大的组合算法。Boosting methods包含比如AdaBoost（Adaptive Boost），Gradient Tree Boosting（GBDT）。

2.2.1 AdaBoost

3 main ideas

1. Adaboost 通过结合很多weak learners去做classification，这些weak learner一般是stumps(只有一个split的decision tree)
2. 一些stumps在最后的vote占有更高的权重
3. 每一个stump的形成是基于对前面一个stump的错误的学习

Steps

1. Assign uniform weights for all data points where N is the total number of training data points.
2. At each iteration fit a classifier to the training data and update weights of each observations.

3. The final model is given by amount of say of each classifier.

   
   

Code

from sklearn.ensemble import AdaBoostClassifier # For Classification
from sklearn.ensemble import AdaBoostRegressor  # For Regression
from skleran.tree import DecisionTreeClassifier

dt = DecisionTreeClassifier()
clf = AdaBoostClassifier(n_estimators=100, base_estimator=dt, learning_rate=1)
# Above I have used decision tree as a base estimator, you can use any ML learner as base estimator if it accepts sample weight
clf.fit(x_train, y_train)

2.2.2 Gradient Boosting Machines/Models (GBM)

GMB是按顺序生长树，每棵树都使用先前生长的树的信息生长。它主要的思想是，每一次建立模型是从之前建立模型的损失函数的梯度下降方向上建立的。如果我们的模型能够让损失函数持续的下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度（Gradient)的方向上下降。

from sklearn.ensemble import GradientBoostingClassifier  # For Classification
from sklearn.ensemble import GradientBoostingRegressor   # For Regression

clf = GradientBoostingClassfier(n_estimators=100, learning_rate=1.0, max_depth=1)
clf.fit(X_train, y_train)

算法

1.在数据上拟合一个简单的线性回归器或决策树 [将x作为输入，将y作为输出]
2.计算错误残差。实际目标值，减去预测目标值[e1 = y - y_predicted1]
3.将误差残差的新模型拟合为具有相同输入变量的目标变量[称之为e1_predicted]
4.将预测残差添加到先前的预测中
[y_predicted2 = y_predicted1 + e1_predicted]
5.拟合剩余的残差模型。即[e2 = y - y_predicted2]并重复步骤2至5，直至开始过拟合或残差总和恒定。通过持续检查验证数据的准确性可以控制过度拟合。

可调节的参数

• Number of splits in each tree每个树的分支数 d： 每棵树都非常小(弱学习者)，只有几个终端节点(由参数d决定)。一般 d = 1比较好，每棵树都是一个stump，由一个单独的分裂组成，最后boosting是一个additive model。

• Number of trees树的数目 B：与对数据拟合单一的大型决策树(这相当于硬拟合数据，可能会过度拟合)不同，boosting通过grow许多树(由参数B决定)来learn slowly。Bagging中如果B太大，可能会over-fitting，为了找一个适中的B，需要用cross validation。

• Learning rate学习率 λ：给定当前模型，我们先使用一个小决策树来拟合残差，然后我们在f()表现不佳的地方慢慢改进。shrinkage parameterλ进一步减缓了这一过程，允许更多不同形状的树attack残差。如果 λ比较小，一般B会需要比较大。

2.3 Stacking

Steps

1. Build multiple base models over the training data.
2. Build the final ensemble model by taking the output predictions from these models as its additional inputs for training to make the final prediction.

2.4 Bukets of Models

参考链接

1 https://www.biaodianfu.com/boosting.html
2 https://towardsdatascience.com/ensemble-methods-bagging-boosting-and-stacking-c9214a10a205