集成学习（1）

随机森林

1. 原理

随机森林属于Bagging的扩展变体

Bagging：有放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。

RF以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括RF包括四个部分：

1、随机选择样本（放回抽样）；

2、随机选择特征；

3、构建决策树；

4、随机森林投票（平均）。

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

在构建决策树的时候，RF的每棵决策树都最大可能的进行生长而不进行剪枝；在对预测输出进行结合时，RF通常对分类问题使用简单投票法，回归任务使用简单平均法。

2. 随机森林的生成方法

对于 $t=1,2,…,T$ ：

对训练集进行第 $t$ 次随机采样，共采集 $m$ 次，得到包含 $m$ 个样本的采样集 $D_t$ ；
用采样集 $D_t$ 训练第 $t$ 个决策树模型 $G_t(x)$ ，在训练决策树模型的节点的时候，在节点上所有的样本特征中选择一部分样本特征，在这些随机选择的部分样本特征中选择一个最优的特征来做决策树的左右子树划分；

如果是分类算法预测，则 $T$ 个弱学习器投出最多票数的类别或者类别之一为最终类别。如果是回归算法，T个弱学习器得到的回归结果进行算术平均得到的值为最终的模型输出。

RF使用了CART决策树作为弱学习器；

RF通过随机选择节点上的一部分样本特征，这个数字小于n，从中选择一个最优的特征来做决策树的左右子树划分，这样进一步增强了模型的泛化能力。

3. 什么是袋外数据（Out of Bag）

在一个含有 $m$ 个样本的训练集中进行随机采样，样本被采到的概率是 $\frac{1}{m}$ ，不被采到的概率是 $1-\frac{1}{m}$ ，则：

$m\rightarrow\infty,\quad\lim_{n\rightarrow+\infty}(1 - \frac{1}{m})^{m}=0.368$

4. 随机森林是否需要做交叉验证

结论：不需要

它可以在内部进行评估，也就是说在生成的过程中可以对误差进行无偏估计，由于每个基学习器只使用了训练集中约63.2%的样本，剩下约36.8%的样本可用做验证集来对其泛化性能进行“包外估计”。

5. 为什么随机森林不会发生过拟合

在建立每一棵决策树的过程中，有两点需要注意采样与完全分裂。

采样：RF对输入的数据要进行行、列的随机采样。

对于行采样，采用有放回的方式，也就是在采样得到的样本集合中，可能有重复的样本。假设输入样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每一棵树的输入样本都不是全部的样本，使得相对不容易出现over-fitting

对于列采样：列采样，从M 个feature中，选择m个(m << M)
完全分裂：对采样之后的数据使用完全分裂的方式建立出决策树，这样决策树的某一个叶子节点要么是无法继续分裂的，要么里面的所有样本的都是指向同一个类。

6. 随机森林与Bagging的对比

RF的起始性能较差（当只有一个基学习器时）随着学习器增多，随机森林通常会收敛到更低的泛化误差。

RF选择与输入样本数目相同多的样本（采样样本次）；Bagging一般选择比输入样本少的样本。

随机森林的训练效率也会高于Bagging，因为在单个决策树的构建中，Bagging使用的是确定性决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是随机性特征数，只需考虑特征的子集。

7. 随机森林的优缺点

优点：

（1）不必担心过度拟合（模型方差小，泛化能力强）；
（2）对于部分缺失特征不敏感；
（3）能够处理很高维的数据并且不需要特征选择，训练完成后可以给出特征的重要性；
（5）算法容易理解；
（6）可以高度并行处理。

缺点：

（1）在噪声较大的分类或者回归问题上会过拟合。
（2）执行速度虽然比Boosting等快，但是比单个的决策树慢很多。
（3）可能会出现一些差异度非常小的树，淹没了一些正确的决策。
（4）由于树是随机生成的，结果不稳定（kpi值比较大）

GBDT

1. 原理

Boosting：使用多个分类器，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练的分类器的性能来进行训练。Boosting是通过关注被已有分类器错分的那些数据来获得新的分类器。

Boosting分类的结果是基于所有分类器的加权求和结果的（bagging中权值是一致的）

GBDT与传统的Boosting区别较大，它的每一次计算都是为了减少上一次的残差

而为了消除残差，我们可以在残差减小的梯度方向上建立模型

残差：和预测值相加后能得到真实值的累加量

在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方向，与传统的Boosting中关注正确错误的样本加权有着很大的区别。

关键：利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。
GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树）。

结论：GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，通过不断减少训练过程中产生的残差对问题不断优化

2. GBDT的生成方法

GBDT通过迭代M轮，每轮产生一个弱分类器 $T\left ( x;\theta _m \right )$

弱分类器的损失函数为 $\hat\theta_{m} = \mathop{\arg\min}_{\theta_{m}} \sum_{i=1}^{N}L\left ( y_{i},F_{m-1}(x_{i})+T(x_{i};\theta_{m} ) \right )$

样本 $x_i$ 的损失函数的负梯度为 $y_i^` = -[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}]_{F(x)=F_{m-1}(x)}$ ，利用 $(x_i,y_I^`)$ 拟合一颗CART树

每个弱分类器在当前模型 $F_{m-1}(x)$ 的基础上进行训练

弱分类器的要求：足够简单，低方差高偏差（训练过程是通过降低偏差来提高分类精度的）
最终的总分类器是将每轮训练的弱分类器加权得到的（加法模型）

$F_{m}(x) = \sum_{m=1}^{M}T\left ( x;\theta _m \right )$

GBDT通过经验风险及消化来确定下一个分类器的参数。如果选择平方损失函数，那么这个差值就是残差：

$min\frac{1}{2}\sum_{i=1}^{N}(y_i - (F_{m-1}(x_i) + T(x_i;\theta_m)))^2\rightarrow y_i-F_{m-1}=T$

希望损失函数能够不断减小，并且快速的减小

让损失函数沿着梯度下降的方向

3. GBDT如何选择特征

GBDT默认的弱分类器是CART树

假设总共有M个特征，首先选取一个特征 $j$ 作为二叉树的第一个切分特征，然后对特征 $j$ 选择一个切分点 $m$
特征 $j$ 的值小于 $m$ ，则分为一类，如果大于 $m$ ，则分为另一类

遍历每个特征，然后对每个特征遍历它所有可能的切分点，找到最优特征 $m$ 的最优切分点 $j$

衡量我们找到的特征 $m$ 和切分点 $j$

回归：平房误差 $min_{j,m}[min_{c_1}\sum_{x_i\in R_1(j,m)}(y_i - c_1)^2 + min_{c_2}\sum_{x_i\in R_2(j,m)}(y_i - c_2)^2]$ ， $c_m=ave(y_i|x_i\in R_m)$

分类： $Gini(p)=\sum_{k=1}^{K}p_k(1-p_k)=1 - \sum_{k=1}^{K}p_k^2$ ，对于给定的集合D，基尼系数为 $Gini(D)=1 - \sum_{k=1}^{K}[\frac{C_k}{D}]^2$

4.GBDT如何构建特征

GBDT可以产生特征的组合

在CTR预估中，工业界一般会采用逻辑回归，但LR本身只适合处理线性问题，如果要处理非线性，可以进行特征组合

Facebook发表过一篇文章，利用GBDT去产生有效的特征组合，以便逻辑回归进行训练来提升最终的效果。

GBDT 生成了两棵树，两颗树一共有五个叶子节点。我们将样本 X 输入到两颗树当中去，样本X 落在了第一棵树的第二个叶子节点，第二颗树的第一个叶子节点，于是我们便可以依次构建一个五纬的特征向量[0,1,0,1,0]

5.GBDT如何用于分类

GBDT 无论用于分类还是回归一直都是使用的CART 回归树

GBDT 每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值。这个要求每轮迭代的时候，弱分类器的输出的结果相减是有意义的。残差相减是有意义的。

弱分类器是分类树，类别相减是没有意义的

在训练时，针对样本 $x_i$ 每个可能的类（总共 $K$ 类）都训练一个分类回归树

实质上是在每轮训练的时候同时训练 $K$ 颗树。第 $k$ 颗树针对样本 $x_i$ 的第 $k$ 类，输入为 $(x_i, y_k),y_{k=c}=1$

对应的 $K$ 个输出为 $f_k(x_i)$

仿照Softmax，则属于类别 $c$ 的概率为： $p_{c}=\frac{exp(f_c(x_i)}{\sum_{k=1}^{K}exp(f_k(x_i))}$
计算每个树针对类别1的残差

残差 $y_{ck}=k-p_c,k=1,…,K$

针对下一轮，将本轮的残差作为输入 $(x_i,y_{ck}(x_i))$ 输入 $k$ 第颗树（同样 $K$ 有棵树）

6. GBDT如何做正则化

为了防止过拟合，需要对GBDT做正则化，主要有三种方式：

与Adaboost类似的正则化项：步长（learning rate），定义为 $v$

$F_k(x)=F_{k-1}(x)+f_k(x)\rightarrow F_k(x)=F_{k-1}(x)+vf_k(x)$

$0<v\leq1$ ，较小的 $v$ 意味着更多的弱学习期迭代次数
通过子采样步长（subsample），定义为 $s\in (0,1]$ 。RF采用有放回抽样，GBDT采用不放回抽样

当 $s=1$ ，则不采用子采样；当 $s<1$ ，则使用部分样本做GBDT

部分样本可以减少方差（防止过拟合），但是会增加样本拟合偏差，所以 $s$ 不能太低
正则化剪枝

7. GBDT通过什么方式减少误差

每棵树都是在拟合当前模型的预测值和真实值之间的误差，GBDT是通过不断迭代来使得误差减小的过程。

8. GBDT相比于传统的LR，SVM效果为什么好一些？

GBDT基于树模型，继承了树模型的优点 [对异常点鲁棒、不相关的特征干扰性低（LR需要加正则）、可以很好地处理缺失值、受噪音的干扰小]

9. GBDT如何求梯度

BGDT进行梯度下降时是损失函数对目标函数求导： $\frac{\part L}{\part f_{m-1}}$ ，而不是对特征值

决策树的目标函数没法用一个表达式求解，每个节点都是用一个值来分离样本，无法直接通过表达式来求解

把函数 $f_{m-1}$ 理解成在所有样本上的函数值，即负梯度为 $-\frac{\part L}{\part f_{m-1}(x_i)}$

对于样本 $x_i,i=1,…,N$ ，都有一个梯度值，最终的函数梯度为所有样本的梯度和

10. GBDT的训练问题

如何设置单颗树的停止生长条件？
- 节点分裂时的最小样本数
- 最大深度
- 最大叶子节点数
- loss满足的约束条件
如何评估特征的权重大小？
- 通过计算每个特征在训练集下的信息增益，最后计算每个特征信息增益与所有特征信息增益之和的比例
- 用相同的GBDT参数对每个特征训练一个模型，然后计算每个特征正确分类的个数，最后计算每个特征正确分类的个数与所有正确分类个数之和的比例
当增加样本数量时，训练时长是线性增加的吗？

不是，生成单颗树树时，对于$$ $，损失函数极小值与样本数量$ N$$不是线性相关
当增加树的颗树时，训练时长是线性增加的吗？

不是，因为每棵树的生成时间复杂度不一样
每个节点上都保存什么信息？
- 中间节点保存某个特征的分割值
- 也几点保存预测 $x_i$ 是某个类别的概率
如何防止过拟合？
- 增加样本（数据偏差或数据集小的缘故），移除噪声
- 减少特征，保留重要的特征
- 对样本进行采样
- 对特征进行采样
GBDT在训练和预测是都用到了步长，这两个步长一样吗？有什么用？如何设置？
- 训练步长和预测步长是一样的，可以从训练的过程中获得（更新当前迭代模型的时候）
- 作用：使得每次更新模型的时候，Loss能够平稳地沿着负梯度的方向下降，不至于震荡
- 设置：一种是按照策略来决定步长，另一种是在训练模型是学习步长
  - 初始时步长相同（较小的值），随着迭代次数动态改变（衰减）
  - 训练第 $k$ 颗树时，利用前 $k-1$ 颗树求梯度，所以可以把步长当作一个变量来学习
- 如果步长较大，训练时容易发生震荡，模型学习不好；步长较小时，训练时间过长，迭代次数较大，生成较多的树，使得模型变复杂
GBDT哪些部分可以并行？
- 计算每个样本的梯度
- 挑选最佳分裂特征及分裂节点时，对特征计算相应的误差及均值时
- 更新每个样本的负梯度时
- 预测时，将之前所有树的结果累加的时候
树生长畸形会怎么样，如何预防？

在树的生成过程中，加入不平衡约束条件。

对样本集中分裂到某个节点，对另一个节点的样本很少的情况进行惩罚

10. RF与GBDT的区别

组成随机森林的树可以分类树也可以是回归树，而GBDT只由回归树组成
组成随机森林的树可以并行生成，而GBDT是串行生成
随机森林的结果是多数表决，而GBDT则是多棵树累加之和
随机森林对异常值不敏感，而GBDT对异常值比较敏感
随机森林是通过减少模型的方差来提高性能，而GBDT是减少模型的偏差来提高性能的
随机森林不需要进行数据预处理，即特征归一化。而GBDT则需要进行特征归一化

GBDT的优缺点

优点

可以灵活处理各种类型的数据，包括连续值和离散值。
相对于SVM来说，在相对少的调参时间情况下，预测的准备率也可以比较高。
使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

缺点

由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

XGBoost

XGBoost是一个大规模、分布式的通用Gradient Boosting库，它在GB框架下实现了GBDT和一些广义线性机器学习算法。

XGBoost与GBDT的区别

传统的GBDT以CART作为基分类器，XGBoost还支持线性分类器

此时XGBoost相当于带L1和L2正则项的LR
GBDT使用Gini系数进行分裂，XGBoost是经过优化推导后得到的

$Gain=\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R + \lambda} - \gamma$
XGBoost对损失函数进行二阶泰勒展开（同时用到了一阶和二阶导数），传统GBDT在优化时只使用一阶导数信息。XGBoost还支持自定义代价函数

二阶导数有利于梯度下降的更快更准

在不确定损失函数具体形式的情况下，仅仅依靠输入数据的值就可以进行叶子分类优化计算
XGBoost在代价函数里加入了正则项，用于控制模型复杂度

$Obj=\sum_{i=1}^{N}l(y_i,y_i^,) + \sum_{k=1}^{K}\Omega(f_k),\quad\Omega(f_k)=\gamma T + \frac{1}{2}\sum_{j=1}^{T}w_j^2$
XGBoost支持列抽样。不仅能降低过拟合，还能减少计算
XGBoost会进行权重缩减。在每一次迭代完成后，会将叶子结点的权重乘上盖系数，主要是为了削弱每棵树的影响。
XGBoost对缺失处理。对于特征有缺失的样本，XGBoost可以自动学习出它的分裂方向
XGBoost支持并行
- XGBoost的并行并不是Tree粒度上的，XGBoost也是一次迭代完才能进行下一次迭代
- XGBoost的并行是在特征粒度上（决策树最耗时的步骤就是对特征值进行排序，确定最佳分类节点）
- XGBoost在训练前，预先对数据进行排序，保存为block结构，后边的迭代中重复使用这个结构大大减小计算量。各个特征的增益计算就可以多线程进行。

Bagging、RF、Boosting、Adaboost、GBDT

Bagging：可以看成投票选举的方式。通过训练多个模型（每个模型从初始训练集中随机选取出 $N$ 个组成训练集训练模型），将这些训练好的模型进行加权组合来获得最终的输出结果(分类/回归）。

在特征一定的情况下，用Bagging思想去提升效果。

RF：RF在Bagging的基础上做了修改。在样本集中采用Boostrap采样 $N$ 个样本，建立CART树，在树的每个节点上，从所有属性中随机选择K个属性，选择出一个最佳属性特征作为节点。

随机森林既可以处理离散属性，也可以处理连续值

Boosting：Boosting算法是一个迭代过程，每次新的训练都是为了改进上一次的结果。Boosting在采样时给样本增加了一个权重，使得Loss Function尽量考虑哪些分错类的样本。

Boosting采样的不是样本，而是样本的分布。对分类正确的样本降低权重，分类错误的样本增加权重（通常是边界附近的点），最有加权组合多个弱分类器

Adaboost：对数据集，建立个弱分类器。每次将分错的数据权重提高，将分对的数据权重降低，再进行分类。

每次迭代的样本是一样的，即没有采样过程，只是不同样本的权重不一样

初始化训练集相等的权重，
在训练集上进行轮，每次训练后，对失败的权重加大，让学习器在后续学习中更加关注这些样本，从而得到一个预测函数，预测函数也有一定的权重。

GBDT：每一次的计算是为了减少上一次的残差，在残差梯度减少的梯度方向上建立一个新的模型

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,772评论 6赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,458评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,610评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,640评论 1赞 276
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,657评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,590评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,962评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,631评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,870评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,611评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,704评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,386评论 4赞 319
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,969评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,944评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,179评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,742评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,440评论 2赞 342

集成学习（1）

随机森林

1. 原理

2. 随机森林的生成方法

3. 什么是袋外数据（Out of Bag）

4. 随机森林是否需要做交叉验证

5. 为什么随机森林不会发生过拟合

6. 随机森林与Bagging的对比

7. 随机森林的优缺点

GBDT

1. 原理

2. GBDT的生成方法

3. GBDT如何选择特征

4.GBDT如何构建特征

5.GBDT如何用于分类

6. GBDT如何做正则化

7. GBDT通过什么方式减少误差

8. GBDT相比于传统的LR，SVM效果为什么好一些？

9. GBDT如何求梯度

10. GBDT的训练问题

10. RF与GBDT的区别

GBDT的优缺点

优点

缺点

XGBoost

XGBoost与GBDT的区别

Bagging、RF、Boosting、Adaboost、GBDT

推荐阅读更多精彩内容