集成学习

集成思想主要分为两大流派，Boosting一族通过将弱学习器提升为强学习器的集成方法来提高预测精度（典型算法为AdaBoost）；而另一类则为Bagging，即通过自助采样的方法生成众多并行式的分类器，通过“少数服从多数”的原则来确定最终的结果（典型算法为随机森林）

Bagging

Bagging也叫自举汇聚法（bootstrap aggregating），此类算法可以有效降低variance，其算法过程如下：

1. 从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法有放回抽取n个训练样本（未被抽到的1/3的样本构成袋外数据OOB）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）
2. 每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
3. 对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

Bagging： 随机森林

算法思想

随机森林只是将使用CART决策树作为弱学习器的Bagging方法称为随机森林，特征随机性，相对于一般的Bagging算法，RF会选择采集和训练集样本数N一样个数的样本。

【特点】由于随机性，对于降低模型的方差很有作用，故随机森林一般不需要额外做剪枝，即可以取得较好的泛化能力和抗过拟合能力（Low Variance）。当然对于训练集的拟合程度就会差一些，也就是模型的偏倚会大一些（High Bias）。

【基尼系数】的选择的标准就是每个子节点达到最高的纯度，即落在子节点中的所有观察都属于同一个分类，此时基尼系数最小，纯度最高，不确定度最小，数据分割越彻底，越干净。

RF优点：

• 由于采用了集成算法，本身精度比大多数单个算法要好 ；
• 在测试集上表现良好，由于两个随机性（样本随机、特征随机）的引入，使得随机森林不容易陷入过拟合（样本随机，特征随机） ；
• 在工业上，由于两个随机性的引入，使得随机森林具有一定的抗噪声能力，对比其他算法具有一定优势 ；
• 由于树的组合，使得随机森林可以处理非线性数据，本身属于非线性分类（拟合）模型 ；
• 它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化 ；
• 训练速度快，可以运用在大规模数据集上 ；
• 可以处理缺省值（单独作为一类），不用额外处理 ；
• 由于有袋外数据（OOB），可以在模型生成过程中取得真实误差的无偏估计，且不损失训练数据量 ；
• 在训练过程中，能够检测到feature间的互相影响，且可以得出feature的重要性，具有一定参考意义 ；
• 由于每棵树可以独立、同时生成，容易做成并行化方法 ；
• 由于实现简单、精度高、抗过拟合能力强，当面对非线性数据时，适于作为基准模型。

Boosting（提升方法）

算法思想：

从弱学习算法出发，反复学习，得到一系列弱(基本)分类器，然后组合这些弱分类器，构成一个强分类器，大多数的提升方法都是改变训练数据的概率分布（训练数据的权值分布），针对不同的训练数据调用弱学习算法学习一系列弱分类器。

实际上采用：加法模型(基函数的线性组合)与前向分步算法。

两个问题：

1. 在每一轮如何改变训练数据的权值或概率分布 ?
   答：AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值。降低那些被正确分类样本的权值。
2. 如何将弱分类器组合成一个强分类器？
   答：AdaBoost的做法是，加权多数表决，加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值。

Boosting： AdaBoost

算法思想：

通过迭代每次学习一个基本分类器，每次迭代中，使用全部的样本，改变样本的权重，提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类样本的权值。最后，将基本分类器线性组合作为强分类器，其中给分类误差率小的弱分类器以大的权值，给分类误差率大的弱分类器以小的权值。

每次迭代可以减少它在训练数据集上的分类误差率。

停止条件：当残差足够小或者达到设置的最大迭代次数则停止。

AdaBoost的另一种解释：

模型为加法模型，损失为指数函数，学习算法为前向分步算法（AdaBoost是前向分步算法的特例）。

Boosting： 提升树 boosting tree

被认为是统计学习中最有效的方法之一。

算法思想：

提升树模型采用加法模型（基函数的线性组合）与前向分步算法，同时基函数采用决策树算法，对待分类问题采用二叉分类树，对于回归问题采用二叉回归树。提升树模型可以看作是决策树的加法模型。

对决策树的参数Θ的确定采用经验风险最小化来确定：对于不同的问题采用的损失函数不同。对于分类问题，在决策树中使用的就是0/1损失函数，和前面的adaBoost中的关于分类的推导相同。对回归问题来说，一般采用平方误差函数。

Boosting： 梯度提升树GBDT

算法思想及理解：

一方面可以从残差的角度来理解，每一棵回归树都是在学习之前的树的残差；（使用代价函数对上一轮训练出的模型函数f的偏导来拟合残差。）
一方面可以从梯度的角度掌握算法，即每一棵回归树通过梯度下降法学习之前的树的梯度下降值。

相同点：这两种理解角度从总体流程和输入输出上没有区别的，它们都是迭代回归树，都是累加每棵树结果作为最终结果，每棵树都在学习前面树尚存的不足。
不同点：每一步迭代时的求解方法的不同。

• 前者使用残差（残差是全局最优值），每一步都试图向最终结果方向优化。
• 后者使用梯度（梯度是局部最优方向），每一步试图让当前结果更好一点。

看起来前者更科学一点，毕竟有绝对最优方向不学，为什么舍近求远去估计一个局部最优方向呢？原因在于灵活性。
前者最大问题是，由于它依赖残差，损失函数一般固定为反映残差的均方差，因此很难处理纯回归问题之外的问题。而后者求解方法为梯度下降，只要可求导的损失函数都可以使用。

优缺点：

• 优点：预测精度高、适合低维数据、能处理非线性数据。
• 缺点：并行麻烦（因为上下两棵树有联系）如果数据维度较高时会加大算法的计算复杂度。

梯度提升树GBDT 主要由三个概念组成：

• Regression Decistion Tree 回归树
• Gradient Boosting 梯度提升
• Shrinkage 缩减

Regression Decistion Tree 回归树：

GBDT中的所有决策树都是回归树，而非分类树。以ID3为例，穷举每一个属性特征的信息增益值，每一次都选取使信息增益最大的特征进行分枝，直到分类完成或达到预设的终止条件，实现决策树的递归构建。

• 回归树的每个节点得到的是一个预测值而非分类树式的样本计数。
• 在分枝节点的选取上，回归树并没有选用最大熵值来作为划分标准，而是使用了最小化均方差。
  一般来讲，回归树的分枝不太可能实现每个叶子节点上的属性值都唯一，更多的是达到我们预设的终止条件即可（例如叶子个数上限），这样势必会存在多个属性取值，那么该节点处的预测值自然就为基于这些样本所得到的平均值了。

Gradient Boosting 梯度提升：

GB基本思想为：沿着梯度方向，构造一系列的弱分类器函数，并以一定权重组合起来，形成最终决策的强分类器。每一棵树所学习的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。利用最速下降的近似方法，即利用损失函数的负梯度在当前模型的值，作为回归问题中提升树算法的残差的近似值，拟合一个回归树。

举个例子，同样使用年龄进行分枝，假设我们A的真实年龄是18岁，但第一棵树的预测年龄是12岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁……以此类推学习下去，这就是梯度提升在GBDT算法中的直观意义。

Shrinkage 缩减：

Shrinkage思想：每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。换句话说缩减思想不完全信任每一个棵残差树，它认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，只有通过多学几棵树才能弥补不足。

Bagging，Boosting二者之间的区别

1）样本选择上：

• Bagging：训练集是在原始集中采用Bootstrap有放回抽样，从原始集中选出的各轮训练集之间是独立的。
• Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2）样例权重：

• Bagging：使用均匀取样，每个样例的 权重相等。
• Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3）预测函数：

• Bagging：所有预测函数的权重相等。
• Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4）集成学习方法：

• Bagging：并行化方法各个预测函数可以并行生成。
  Boosting：序列化方法各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

Bagging + 决策树 = 随机森林
AdaBoost（提升方法） + 决策树 = 提升树
Gradient Boosting + 决策树 =GBDT（梯度提升树）

5）划重点为什么说bagging是减少variance，而boosting是减少bias？

• Bagging对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的bias和variance（事实上，各模型的分布也近似相同，但不独立）。由于:
  偏差期望
  所以bagging后的bias和单个子模型的接近，一般来说不能显著降低bias。
  另一方面，若各子模型独立，可以显著降低variance:
  方差(子模型独立)
  若各子模型完全相同，此时不会降低variance：
  方差(子模型相同)
  bagging方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低variance。
  为了进一步降低variance，Random forest通过随机选取变量子集做拟合的方式de-correlated了各子模型（树），使得variance进一步降低。

• boosting从优化角度来看，是用forward-stagewise这种贪心法去最小化损失函数 。
  常见的AdaBoost即等价于用这种方法最小化exponential loss：
  Adaboost-指数损失
  所谓forward-stagewise，就是在迭代的第n步，求解新的子模型f(x)及步长a（或者叫组合系数），来最小化:
  迭代损失
  这里fn-1(x)是前n-1步得到的子模型的和。
  因此boosting是在sequential地最小化损失函数，其bias自然逐步下降。
  但由于是采取这种sequential、adaptive的策略，各子模型之间强相关，于是子模型之和并不能显著降低variance。所以说boosting主要还是靠降低bias来提升预测精度。

【参考资料】

1. 【CSDN】http://www.cnblogs.com/earendil/p/8872001.html
2. 《统计学习方法》ch8. 李航