集成学习知识点

集成学习（ensemble learning）通过多个机器学习模型的组合形成一个精度更高的模型，参与组合的模型称为弱学习器（weak learner）。在预测时使用这些弱学习器模型联合进行预测，训练时需要用训练样本集依次训练出这些弱学习器。

根据训练各个弱学习器的不同思路，目前广为使用的有两种方案：

Bagging和Boosting

前者通过对原始训练样本集进行随机抽样，形成不同的训练样本集来训练每个弱学习器，各个弱学习器之间可以认为近似是独立的，典型代表是随机森林；后者为训练样本增加权重（AdaBoost），或者构造标签值（GBDT）来依次训练每个弱学习器，各个弱学习器之间相关，后面的弱学习器利用了前面的弱学习器的信息。下面分别对这两类算法进行介绍。

Bagging

装袋算法是一种提高分类模型的方法
（1）从训练集S中bootstrap有放回地选取数据集M(M<S)；
（2）生成一个分类模型C
（3）重复以上步骤m次，得到m个分类模型C1，C2…Cm
（4）对于分类问题，每一个模型投票决定，少数服从多数
（5）对于回归问题，取平均值

Bagging的核心思想是对训练样本集进行抽样，形成新的训练样本集，以此训练各个弱学习器。由于每个弱学习器使用了不同的样本集，因此各不相同。预测时，用每个弱学习器分别进行预测，然后投票。在这里，每个弱学习器的地位是相等的。

随机森林

Bagging的典型代表是随机森林，由Breiman等人提出，它由多棵决策树组成。预测时，对于分类问题，一个测试样本会送到每一棵决策树中进行预测，然后投票，得票最多的类为最终分类结果。对于回归问题随机森林的预测输出是所有决策树输出的均值。

训练时，使用bootstrap抽样来构造每个弱学习器的训练样本集。这种抽样的做法是在n个样本的集合中有放回的抽取n个样本形成一个数据集。在新的数据集中原始样本集中的一个样本可能会出现多次，也可能不出现。随机森林在训练时依次训练每一棵决策树，每棵树的训练样本都是从原始训练集中进行随机抽样得到。在训练决策树的每个节点时所用的特征也是随机抽样得到的，即从特征向量中随机抽出部分特征参与训练。即随机森林对训练样本和特征向量的分量都进行了随机采样。

正是因为有了这些随机性，随机森林可以在一定程度上消除过拟合。对样本进行采样是必须的，如果不进行采样，每次都用完整的训练样本集训练出来的多棵树是相同的。随机森林使用多棵决策树联合进行预测可以降低模型的方差。

解释：随机森林是一种基于树模型的装袋算法的改进，嘉定数据集中有M个特征和N个观测值。每一个数有放回的随机抽取N个观测值，m( $m=\sqrt{M}或者m=logM$ )，为什么？因为这是为了避免随机森林的过拟合。最后把每一个单一的决策树的结果综合起来。

也就是说tree我们可以自己选，当数据量大的时候，tree多一点，数据量小的时候，tree少一点。

优点：

减少了模型方差，提高了预测准确性
不需要给树做剪纸(减少过拟合)

Adaboost

Boosting作为一种抽象框架很早就被提出[6]，但一直没有很好的具体实现。AdaBoost算法（Adaptive Boosting，自适应Boosting）由Freund等人提出，是Boosting算法的一种实现版本。在最早的版本中，这种方法的弱分类器带有权重，分类器的预测结果为弱分类器预测结果的加权和。训练时训练样本具有权重，并且会在训练过程中动态调整，被前面的弱分类器错分的样本会加大权重，因此算法会更关注难分的样本。2001年级联的AdaBoost分类器被成功用于人脸检测问题，此后它在很多模式识别问题上得到了应用。

集成学习知识点
具体的流程原理：

假设我们有训练集S，特征值为X，我们初始化权重为 $w_i=\frac{1}{N}$

1.设定一个DT: C1(x)
2.分类的误差为 $error=\frac{\sum{w_i}I(y_i != C_1(x))}{\sum{w_i}}$
3.知道了error，我们找到一个 $\alpha=log\frac{1-error}{error}$ ,和LR很像对吧
4.再找一个DT：C2(x)，这次我们把他放在分错的数据集上
5.重复前面4个步骤，得到好多个C tree：C1，C2.。。。Cm
6.我们最后得到的是加权和 $C(x)=\sum{\alpha_iC_i(x)}$ ，这就是预测结果

Adaboost的本质就是关注之前被错分的样本，准确率高的弱分类器有更大的权重。

AdaBoost算法在模式识别中最成功的应用之一是机器视觉里的目标检测问题，如人脸检测和行人检测。在2001年Viola和Jones设计了一种人脸检测算法。它使用简单的Haar特征和级联AdaBoost分类器构造检测器，检测速度较之前的方法有2个数量级的提高，并且有很高的精度。VJ框架是人脸检测历史上有里程碑意义的一个成果，奠定了AdaBoost目标检测框架的基础。

GBDT

Adaboost是通过更新样本权重来保证树的多样性，GBDT是通过改变结果来保证输的多样性。每一棵树学的都是之前所有树结论和的残差，这个残差就是一个加预测值后能得到真实值的累加量。

加性模型：每次添加一个弱学习器，同时已生成的弱学习模型保持不变。使用梯度下降法去优化每次添加的弱学习模型。

优点：
1.通过减少模型误差来提高准确性
2.快速训练，计算效率高

缺点：
1.容易过拟合
2.难以并行计算(因为是基于上一步的错误，连续迭代)

减少过拟合的办法：
1.控制决策树的数量，树的深度，节点个数，每次分割节点的条件(越深越容易过拟合)

XGBoost

$Obj = \sum_{i=1}^{n}l(y_i,y) + \sum_{k=1}^{K}\omega(\theta)$ 损失函数+惩罚项

具体原理过程就不po了，讲一下思路

这里需要有牛顿法的只是， $L(\theta^t)在\theta^{t-1}$ 处进行二阶泰勒展开，将一阶和二阶导数分别记为g和h

二阶收敛速度快，但是计算比较复杂

我们重新定义决策树，q(x)表示将样本x分到了某个叶子节点上，w是叶子结点的分数，所以 $W_{q(x)}$ 表示回归树对样本的预测值

我们把一开始的Obj中的预测值项变换一下，再用二阶泰勒展开得到一个带g和h的结果，之后我们优化结果，把 $l$ 那一部分去掉，得到一个优化结果。我们再把惩罚项带入，合并同类项。最后用Gj和Hj分别代替gi和hi的和。得到最终的公式。

LightGBM

他是一种基于决策树的提升算法，是基于XGBoost的一种改进

XGBoost	LightGBM
pre-sorted方法	histogram算法
level-wise生长策略	leaf-wise生长策略

Histogram算法：
（1）把连续的浮点特征值离散化乘N个整数，构造一个宽度为N的直方图
（2）遍历数据时，根据离散化后的值作为索引在直方图中累计统计量。
（3）一次遍历后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点

什么是level-wise和leaf-wise?
level-wise就是每次都有新的层出现，而leaf-wise是层虽然有那么深，但是我还是可以在没有叶子的地方加一层叶子