集成学习主要分为以下几类：Bagging，Boosting以及Stacking。

传统机器学习算法 (例如：决策树，人工神经网络，支持向量机，朴素贝叶斯等) 的目标都是寻找一个最优分类器尽可能的将训练数据分开。集成学习 (Ensemble Learning) 算法的基本思想就是将多个分类器组合，从而实现一个预测效果更好的集成分类器。集成算法可以说从一方面验证了中国的一句老话：三个臭皮匠，赛过诸葛亮。

Thomas G. Dietterich 指出了集成算法在统计，计算和表示上的有效原因：

统计上的原因

一个学习算法可以理解为在一个假设空间 H 中选找到一个最好的假设。但是，当训练样本的数据量小到不够用来精确的学习到目标假设时，学习算法可以找到很多满足训练样本的分类器。所以，学习算法选择任何一个分类器都会面临一定错误分类的风险，因此将多个假设集成起来可以降低选择错误分类器的风险。

计算上的原因

很多学习算法在进行最优化搜索时很有可能陷入局部最优的错误中，因此对于学习算法而言很难得到一个全局最优的假设。事实上人工神经网络和决策树已经被证实为是一个NP 问题。集成算法可以从多个起始点进行局部搜索，从而分散陷入局部最优的风险。

表示上的原因=

在多数应用场景中，假设空间 H 中的任意一个假设都无法表示 (或近似表示) 真正的分类函数 f。因此，对于不同的假设条件，通过加权的形式可以扩大假设空间，从而学习算法可以在一个无法表示或近似表示真正分类函数 f 的假设空间中找到一个逼近函数 f 的近似值。

集成算法大致可以分为：Bagging，Boosting 和 Stacking 等类型。

Bagging

Bagging是bootstrap aggregating的简写。先说一下bootstrap，bootstrap也称为自助法，它是一种有放回的抽样方法，目的为了得到统计量的分布以及置信区间。基本思想如下：

每次采用有放回的抽样从训练集中取出\(n\)个训练样本组成新的训练集；
利用新的训练集，训练得到\(M\)个子模型 \(\{h_1,h_2,...,h_M\}\)；
对于分类问题，采用投票的方法，得票最多子模型的分类类别为最终的类别；对于回归问题，采用简单的平均方法得到预测值。

Algorithm 1 Bagging 算法
Require:
- 学习算法 \(L\)
- 子模型个数 \(M\)
- 训练数据集 \(T={(x1,y1),(x2,y2),...,(xN,yN)}\)
Ensure:
- Bagging 算法 \(h_f(x)\)
1: function Bagging\((L,M,T)\)
2: for \(m=1\) to \(M\) do
3: \(T_m\)← boostrap sample from training set \(T\)
4: \(h_m\)←\(L(T_m)\)
5: end for
6: \(h_f(x)\)←\(sign(∑_{m=1}^Mh_m(x))\)
7: return \(h_f(x)\)
8: end function

假设对于一个包含 \(M \)个样本的数据集 \(T\)，利用自助采样，则一个样本始终不被采用的概率是 \((1−\frac{1}{M})^M\)，取极限有：

\[\lim_{x \to \infty} \left(1 - \dfrac{1}{M}\right)^M = \dfrac{1}{e} \approx 0.368\]

即每个学习器仅用到了训练集中 63.2% 的数据集，剩余的 36.8% 的训练集样本可以用作验证集对于学习器的泛化能力进行包外估计 (out-of-bag estimate)。

随机森林

随机森林 (Random Forests) 是一种利用CART决策树作为基学习器的 Bagging 集成学习算法。随机森林模型的构建过程如下：

数据采样

作为一种 Bagging 集成算法，随机森林同样采用有放回的采样，对于总体训练集 \(T\)，抽样一个子集 \(T_{sub}\) 作为训练样本集。除此之外，假设训练集的特征个数为 \(d\)，每次仅选择 \(k(k<d)\) 个构建决策树。因此，随机森林除了能够做到样本扰动外，还添加了特征扰动，对于特征的选择个数，推荐值为\( k=log_2⁡d \)。

树的构建

每次根据采样得到的数据和特征构建一棵决策树。在构建决策树的过程中，会让决策树生长完全而不进行剪枝。构建出的若干棵决策树则组成了最终的随机森林。

随机森林在众多分类算法中表现十分出众，其主要的优点包括：

由于随机森林引入了样本扰动和特征扰动，从而很大程度上提高了模型的泛化能力，尽可能地避免了过拟合现象的出现。
随机森林可以处理高维数据，无需进行特征选择，在训练过程中可以得出不同特征对模型的重要性程度。
随机森林的每个基分类器采用决策树，方法简单且容易实现。同时每个基分类器之间没有相互依赖关系，整个算法易并行化。

随机森林的推广

由于RF在实际应用中的良好特性，基于RF，有很多变种算法，应用也很广泛，不光可以用于分类回归，还可以用于特征转换，异常点检测等。下面对于这些RF家族的算法中有代表性的做一个总结。

extra trees

extra trees是RF的一个变种, 原理几乎和RF一模一样，仅有区别有：

对于每个决策树的训练集，RF采用的是随机采样bootstrap来选择采样集作为每个决策树的训练集，而extra trees一般不采用随机采样，即每个决策树采用原始训练集。
在选定了划分特征后，RF的决策树会基于基尼系数，均方差之类的原则，选择一个最优的特征值划分点，这和传统的决策树相同。但是extra trees比较的激进，他会随机的选择一个特征值来划分决策树。

从第二点可以看出，由于随机选择了特征值的划分点位，而不是最优点位，这样会导致生成的决策树的规模一般会大于RF所生成的决策树。也就是说，模型的方差相对于RF进一步减少，但是偏倚相对于RF进一步增大。在某些时候，extra trees的泛化能力比RF更好。

Totally Random Trees Embedding

Totally Random Trees Embedding(以下简称 TRTE)是一种非监督学习的数据转化方法。它将低维的数据集映射到高维，从而让映射到高维的数据更好的运用于分类回归模型。我们知道，在支持向量机中运用了核方法来将低维的数据集映射到高维，此处TRTE提供了另外一种方法。

TRTE在数据转化的过程也使用了类似于RF的方法，建立T个决策树来拟合数据。当决策树建立完毕以后，数据集里的每个数据在T个决策树中叶子节点的位置也定下来了。比如我们有3颗决策树，每个决策树有5个叶子节点，某个数据特征x划分到第一个决策树的第2个叶子节点，第二个决策树的第3个叶子节点，第三个决策树的第5个叶子节点。则x映射后的特征编码为(0,1,0,0,0, 0,0,1,0,0, 0,0,0,0,1), 有15维的高维特征。这里特征维度之间加上空格是为了强调三颗决策树各自的子编码。

映射到高维特征后，可以继续使用监督学习的各种分类回归算法了。

Isolation Forest

Isolation Forest（以下简称IForest）是一种异常点检测的方法。它也使用了类似于RF的方法来检测异常点。

对于在T个决策树的样本集，IForest也会对训练集进行随机采样,但是采样个数不需要和RF一样，对于RF，需要采样到采样集样本个数等于训练集个数。但是IForest不需要采样这么多，一般来说，采样个数要远远小于训练集个数？为什么呢？因为我们的目的是异常点检测，只需要部分的样本我们一般就可以将异常点区别出来了。

对于每一个决策树的建立， IForest采用随机选择一个划分特征，对划分特征随机选择一个划分阈值。这点也和RF不同。

另外，IForest一般会选择一个比较小的最大决策树深度max_depth,原因同样本采集，用少量的异常点检测一般不需要这么大规模的决策树。

对于异常点的判断，则是将测试样本点\(x\)拟合到\(T\)颗决策树。计算在每颗决策树上该样本的叶子节点的深度\(h_t(x)\)。从而可以计算出平均高度\(h(x)\)。此时我们用下面的公式计算样本点\(x\)的异常概率:

\[s(x,m)=2^{−\frac{h(x)}{c(m)}}\]

其中，\(m\)为样本个数。\(c(m)\)的表达式为：

\[𝑐(𝑚)=2ln(𝑚−1)+\zeta−2\frac{𝑚−1}{𝑚}\]

\(𝜉\)为欧拉常,\(s(x,m)\)的取值范围是[0,1],取值越接近于1，则是异常点的概率也越大。

RF和Bagging对比：

随机选择样本和Bagging相同，随机选择特征是指在树的构建中，会从样本集的特征集合中随机选择部分特征，然后再从这个子集中选择最优的属性用于划分，这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的‘平均’特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。

RF的起始性能较差，特别当只有一个基学习器时，但随着学习器数目增多，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging，因为在单个决策树的构建中，Bagging使用的是‘确定性’决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。

优缺点

优点：

训练可以高度并行化，对于大数据时代的大样本训练速度有优势，算是主要优势；
能够处理很高维的数据，并且不用特征选择，而且在训练完后，给出特征的重要性；
相对于Boosting系列的Adaboost和GBDT， RF实现比较简单。

缺点：在噪声较大的分类或者回归问题上容易过拟合。

Boosting

Boosting 是一种提升算法，可以将弱的学习算法提升 (boost) 为强的学习算法。基本思路如下：

利用初始训练样本集训练得到一个基学习器。
提高被基学习器误分的样本的权重，使得那些被错误分类的样本在下一轮训练中可以得到更大的关注，利用调整后的样本训练得到下一个基学习器。
重复上述步骤，直至得到 \(M\)个学习器。
对于分类问题，采用有权重的投票方式；对于回归问题，采用加权平均得到预测值。

AdaBoost

AdaBoost（Adaptive Boosting）是 Boosting 思想的最经典实现之一，它的核心哲学是“从失败中学习”。

核心逻辑（调整样本权重）：在每一轮训练后，模型会挑出上一轮做错的题（即分类错误的样本），并在下一轮中加大这些错题的权重。
通俗理解：就像学生复习迎考，第一遍做对的题下次扫一眼就行；第一遍做错的题，重点用红笔圈出来，下次专门死磕这些难啃的骨头。
最终形态：训练结束后，把所有的弱分类器集合起来进行“加权投票”。准确率越高的分类器，手里握着的票数（话语权）就越重。

详情参考：AdaBoost

GBDT

GBDT（Gradient Boosting Decision Tree）将 Boosting 引入了更具数学美感的梯度优化领域，它的核心哲学是“步步逼近完美”。

核心逻辑（拟合残差）：GBDT 不再像 AdaBoost 那样去调整样本权重，而是让每一棵新生成的决策树去学习上一轮预测结果与真实值之间的残差（Residual）。在数学上，这等价于沿着损失函数的负梯度方向进行优化。
通俗理解：假设你的目标是赚 100 块钱。第一棵树帮你赚了 70 块（差 30）；第二棵树的目标就不再是 100，而是专门去赚这剩下的 30 块，结果它赚了 20 块（差 10）；第三棵树的目标就变成了赚 10 块……如此不断填补前人的窟窿。
基模型限制：顾名思义，GBDT 的基学习器通常只能是 CART 回归树，即使是分类任务，底层也是通过回归树来输出概率。

详情参考：GBDT（梯度提升树）

XGB

XGBoost（eXtreme Gradient Boosting）是陈天奇大神在 GBDT 基础上打造的究极工程进化版。它曾经横扫 Kaggle 等各大算法竞赛，是公认的“大杀器”。

核心逻辑（二阶泰勒展开 + 正则化）：它不仅继承了 GBDT 拟合残差的思想，还在数学和工程上做到了极致的优化。
关键杀手锏：
1. 更精准的数学指引：GBDT 只用了一阶导数，而 XGBoost 对损失函数进行了二阶泰勒展开（引入了海森矩阵），这就好比不仅知道下山的方向，还知道了下山的坡度，收敛更快更准。
2. 自带防弹衣（正则化）：它在目标函数中加入了惩罚项（控制树的深度和叶子节点的权重），极大地降低了模型过拟合的风险。
3. 极致的工程优化：支持特征级别的并行计算、能够自动处理缺失值、引入了近似直方图算法等，训练速度实现了质的飞跃。

详情参考：XGBoost

常用问题解答

RF和GBDT的区别

他们都是由多棵树组成，最终的结果都是由多棵树一起决定。而不同点主要有：

- 集成学习：RF属于bagging思想，而GBDT是boosting思想；
- 偏差-方差权衡：RF不断的降低模型的方差，而GBDT不断的降低模型的偏差；
- 训练样本：RF每次迭代的样本是从全部训练集中有放回抽样形成的，而GBDT每次使用全部样本；
- 并行性：RF的树可以并行生成，而GBDT只能顺序生成(需要等上一棵树完全生成)；
- 最终结果：RF最终是多棵树进行多数表决（回归问题是取平均），而GBDT是加权融合；
- 数据敏感性：RF对异常值不敏感，而GBDT对异常值比较敏感；
- 泛化能力：RF不易过拟合，而GBDT容易过拟合。

XGBoost与GBDT有什么不同

- 基分类器：XGBoost的基分类器不仅支持CART决策树，还支持线性分类器，此时XGBoost相当于带L1和L2正则化项的Logistic回归（分类问题）或者线性回归（回归问题）；
- 导数信息：XGBoost对损失函数做了二阶泰勒展开，GBDT只用了一阶导数信息，并且XGBoost还支持自定义损失函数，只要损失函数一阶、二阶可导；
- 正则项：XGBoost的目标函数加了正则项，相当于预剪枝，使得学习出来的模型更加不容易过拟合；
- 列抽样和缩减：XGBoost支持列采样，与随机森林类似，同时对每棵树输出使用shrinkage，都是用于防止过拟合；
- 缺失值处理：对树中的每个非叶子结点，XGBoost可以自动学习出它的默认分裂方向。如果某个样本该特征值缺失，会将其划入默认分支；
- 并行化：注意不是tree维度的并行，而是特征维度的并行。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度；
- 可并行的近似直方图算法：树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

XGBoost为什么使用泰勒二阶展开

- 精准性：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，阶信息本身就能让梯度收敛更快更准确。这一点在优化算法里的牛顿法里已经证实了。可以简单认为一阶导指引梯度方向，二阶导指引梯度方向如何变化。
- 可扩展性：Xgboost官网上有说，当目标函数是MSE时，展开是一阶项（残差）+二阶项的形式（官网说这是一个nice form），而其他目标函数，如logloss的展开式就没有这样的形式。为了能有个统一的形式，所以采用泰勒展开来得到二阶项，这样就能把MSE推导的那套直接复用到其他自定义损失函数上。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。

XGBoost为什么快

- 分块并行：训练前每个特征按特征值进行排序并存储为Block结构，后面查找特征分割点时重复使用，并且支持并行查找每个特征的分割点；
- 候选分位点：每个特征采用常数个分位点作为候选分割点；
- CPU cache 命中优化：使用缓存预取的方法，对每个线程分配一个连续的buffer，读取每个block中样本的梯度信息并存入连续的Buffer中;
- Block 处理优化：Block预先放入内存；Block按列进行解压缩；将Block划分到不同硬盘来提高吞吐

XGBoost防止过拟合的方法

- 目标函数添加正则项：叶子节点个数+叶子节点权重的L2正则化；
- 列抽样：训练的时候只用一部分特征（不考虑剩余的block块即可）；
- 子采样：每轮计算可以不使用全部样本，使算法更加保守；
- shrinkage: 可以叫学习率或步长，为了给后面的训练留出更多的学习空间；
- 剪枝：多种方式限制树的复杂度

Stacking

Stacking 本身是一种集成学习方法，同时也是一种模型组合策略，我们首先介绍一些相对简单的模型组合策略：平均法 和 投票法。

对于 数值型的输出 \(h_i(x)∈R\)，

简单平均法 (Simple Averaging)

\[H \left(\mathbf{x}\right) = \dfrac{1}{M} \sum_{i=1}^{M}{h_i \left(\mathbf{x}\right)}\]

加权平均法 (Weighted Averaging)

\[H \left(\mathbf{x}\right) = \sum_{i=1}^{M}{w_i h_i \left(\mathbf{x}\right)}\]

其中，\(w_i\) 为学习器 \(h_i\) 的权重，且 \(w_i≥0,∑_{i=1}^Tw_i=1\)。

对于 分类型的任务，学习器 \(h_i\) 从类别集合 \({c_1,c_2,…,c_N}\) 中预测一个标签。我们将 \(h_i\) 在样本 \(x\) 上的预测输出表示为一个 \(N\) 维向量 \((h_i^1(x);h_i^2(x);…,h_i^N(x))\)，其中 \(h_i^j(x)\) 为 \(h_i\) 在类型标签 \(c_j\)上的输出。

绝对多数投票法 (Majority Voting)

\[H \left(\mathbf{x}\right) = \begin{cases} c_j, & \displaystyle\sum_{i=1}^{M}{h_i^j \left(\mathbf{x}\right) > 0.5 \displaystyle\sum_{k=1}^{N}{\displaystyle\sum_{i=1}^{M}{h_i^k \left(\mathbf{x}\right)}}} \\ \text{refuse}, & \text{other wise} \end{cases}\]

即如果一个类型的标记得票数过半，则预测为该类型，否则拒绝预测。

相对多数投票法 (Plurality Voting)

\[H \left(\mathbf{x}\right) = c_{\arg\max_j \sum_{i=1}^{M}{h_i^j \left(\mathbf{x}\right)}}\]

即预测为得票数最多的类型，如果同时有多个类型获得相同最高票数，则从中随机选取一个。

加权投票法（Weighted Voting)

\[H \left(\mathbf{x}\right) = c_{\arg\max_j \sum_{i=1}^{M}{w_i h_i^j \left(\mathbf{x}\right)}}\]

其中，\(w_i\) 为学习器 \(h_i\) 的权重，且 \(w_i≥0,∑_{i=1}^Mw_i=1\)

绝对多数投票提供了“拒绝预测”，这为可靠性要求较高的学习任务提供了一个很好的机制，但如果学习任务要求必须有预测结果时则只能选择相对多数投票法和加权投票法。在实际任务中，不同类型的学习器可能产生不同类型的 \(h_i^j(x)\) 值，常见的有：

- 类标记，\(h_i^j(x)∈{0,1}\)，若\(h_i\) 将样本 \(x\) 预测为类型 \(c_j\) 则取值为 1，否则取值为 0。使用类型标记的投票称之为 “硬投票” (Hard Voting)。
- 类概率，\(hij(x)∈{0,1}\)，相当于对后验概率 \(P \left(c_j \ | \ \mathbf{x}\right)\) 的一个估计。使用类型概率的投票称之为 “软投票” (Soft Voting)。

Stacking 方法又称为 Stacked Generalization，是一种基于分层模型组合的集成算法。Stacking 算法的基本思想如下：

利用初级学习算法对原始数据集进行学习，同时生成一个新的数据集。
根据从初级学习算法生成的新数据集，利用次级学习算法学习并得到最终的输出。

对于初级学习器，可以是相同类型也可以是不同类型的。在新的数据集中，初级学习器的输出被用作次级学习器的输入特征，初始样本的标记仍被用作次级学习器学习样本的标记。Stacking 算法的流程如下图所示：

Stacking 算法过程如下：

次级学习器的训练集是有初级学习器产生的，如果直接利用初级学习器的训练集生成次级学习器的训练集，过拟合风险会比较大。因此，一般利用在训练初级学习器中未使用过的样本来生成次级学习器的训练样本。以 k 折交叉检验为例：初始的训练集 T 被随机划分为 k 个大小相近的集合 \(T_1,T_2,...,T_k\)。令 \(T_j \)和\( T¯_j=T∖T_j \)表示第 j 折的测试集和训练集。则对于 M 个初级学习算法，学习器\( h_m(j) \)是根据训练集 \(T¯_j \)生成的，对于测试集 \(T_j \)中的每个样本 \(x_i\)，得到 \(z_{im}=h_m(j)(x_i)\)。则根据 \(x_i \)所产生的次级学习器的训练样本为 \(z_i=((z_{i1},z_{i2},...,z_{iM}),y_i)\)。最终利用 M 个初级学习器产生的训练集 \(T^′={(z_i,y_i)}_{i=1}^N\) 训练次级学习器。

下图展示了一些基础分类器以及 Soft Voting 和 Stacking 两种融合策略的模型在 Iris 数据集分类任务上的决策区域。数据选取 Iris 数据集中的 Sepal Length 和 Petal Length 两个特征，Stacking 中的次级学习器选择 Logistic Regression，详细实现请参见这里。

Reference

集成学习算法 (Ensemble Learning)

#

!

Ensemble Learning概述