集成算法（三）

梯度提升树

简介：

基本思想：积跬步以至千里，每次学习一点。先用一个初始值来学习一棵决策树，叶子处可以得到预测的值，以及预测之后的残差，然后后面的决策树就是要基于前面决策树的残差来学习，直到预测值和真实值的残差为0。最后对于测试样本的预测值，就是前面许多棵决策树预测值的累加。

GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

GBDT也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型.（GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树））

它的每一次计算都是为了减少上一次的残差，而为了消除残差，我们可以在残差减小的梯度方向上建立模型,所以说，在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法，与传统的Boosting中关注正确错误的样本加权有着很大的区别。

通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

算法步骤：

损失函数主要有：指数损失、对数损失、均方差、绝对损失

对于回归问题：

对于分类问题：样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。

主要有两个方法：一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。

目前GBDT的算法比较好的库是xgboost。当然scikit-learn也可以。

GBDT优点：

1.可以灵活处理各种类型的数据，包括连续值和离散值。

2.在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。

3.使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

GBDT缺点：

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

GBDT和随机森林对比：

相同点：

1.都是由多棵树组成；

2.最终的结果都是由多棵树一起决定；

不同点：

（1）随机森林的子树可以是分类或回归树，而GBDT只能是回归树；

（2）基于bagging思想，而gbdt是boosting思想，即采样方式不同

（3）随机森林可以并行生成，而GBDT只能是串行；

（4）输出结果，随机森林采用多数投票，GBDT将所有结果累加起来；

（5）随机森林对异常值不敏感，GBDT敏感，随进森林减少方差，GBDT减少偏差；

GBDT和随机森林哪个容易过拟合？

随机森林，因为随机森林的决策树尝试拟合数据集，有潜在的过拟合风险，而boosting的GBDT的决策树则是拟合数据集的残差，然后更新残差，由新的决策树再去拟合新的残差，虽然慢，但是难以过拟合。

-------------------------------------------------------------------------------------------------------------------------------------------------

Adaboost

理论上任何学习器都可以用于Adaboost.但一般来说，使用最广泛的Adaboost弱学习器是决策树和神经网络。对于决策树，Adaboost分类用了CART分类树，而Adaboost回归用了CART回归树。

Adaboost算法可以简述为三个步骤：

（1）首先，是初始化训练数据的权值分布D1。假设有N个训练样本数据，则每一个训练样本最开始时，都被赋予相同的权值：w1=1/N。

（2）然后，训练弱分类器hi。具体训练过程中是：如果某个训练样本点，被弱分类器hi准确地分类，那么在构造下一个训练集中，它对应的权值要减小；相反，如果某个训练样本点被错误分类，那么它的权值就应该增大。权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。

（3）最后，将各个训练得到的弱分类器组合成一个强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。

换而言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

Adaboost的主要优点：

1）Adaboost作为分类器时，分类精度很高。

2）在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，不用对特征进行筛选，非常灵活。

3）作为简单的二元分类器时，构造简单，结果可理解。

4）不容易发生过拟合。

Adaboost的主要缺点：

对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

-------------------------------------------------------------------------------------------------------------------------------------------------

目前GBDT的算法比较好的库是xgboost。当然scikit-learn也可以。

Xgboost

简介：

XGBoost是boosting算法的其中一种。Boosting算法的思想是将许多弱分类器集成在一起形成一个强分类器。因为XGBoost是一种提升树模型，所以它是将许多树模型集成在一起，形成一个很强的分类器。而所用到的树模型则是CART回归树模型

算法思想：

该算法思想就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值。

如下图例子，训练出了2棵决策树，小孩的预测分数就是两棵树中小孩所落到的结点的分数相加。爷爷的预测分数同理

Xgboost优点：

1.XGB利用了二阶梯度来对节点进行划分，相对其他GBM、GBDT来说，精度更加高。

2.利用局部近似算法对分裂节点的贪心算法优化，取适当的eps时，可以保持算法的性能且提高算法的运算速度。

3.在损失函数中加入了L1/L2项，控制模型的复杂度，提高模型的鲁棒性。

4.提供并行计算能力，主要是在树节点求不同的候选的分裂点的Gain Infomation（分裂后，损失函数的差值）

5.Tree Shrinkage，column subsampling等不同的处理细节。

Xgboost缺点：

1.需要pre-sorted，这个会耗掉很多的内存空间

2.数据分割点上，由于XGB对不同的数据特征使用pre-sorted算法而不同特征其排序顺序是不同的，所以分裂时需要对每个特征单独做依次分割，遍历次数为#data * #features来将数据分裂到左右子节点上。

3.尽管使用了局部近似计算，但是处理粒度还是太细了。

4.由于pre-sorted处理数据，在寻找特征分裂点时（level-wise），会产生大量的cache随机访问。

GBDT与Xgboost区别：

1）目标函数通过二阶泰勒展开式做近似。传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。注：支持自定义代价函数，只要函数可一阶和二阶求导。

2）定义了树的复杂度，即xgboost在代价函数里加入了正则项，用于控制模型的复杂度，正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。代替了剪枝。

3）分裂结点处通过结构打分和分割损失动态生长。结构分数代替了回归树的误差平方和。

4）分裂结点特征分割点选取使用了近似算法-可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。用于加速和减小内存消耗。

5）可以处理稀疏、缺失数据(节点分裂算法能自动利用特征的稀疏性),可以学习出它的分裂方向，加快稀疏计算速度。

6）列抽样（column subsampling）[传统GBDT没有]，Shrinkage(缩减)，相当于学习速率(xgboost中的eta)[传统GBDT也有]。

7）支持并行化处理。xgboost的并行是在特征粒度上的，在训练之前，预先对特征进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行，即在不同的特征属性上采用多线程并行方式寻找最佳分割点。

8）传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。通过booster [default=gbtree]设置参数:gbtree: tree-based models/gblinear: linear models。

-------------------------------------------------------------------------------------------------------------------------------------------------

LightGBM

简介：

在2017年年1月微软在GitHub的上开源了一个新的升压工具–LightGBM。在不降低准确率的前提下，速度提升了10倍左右，占用内存下降了3倍左右。因为他是基于决策树算法的，它采用最优的叶明智策略分裂叶子节点，然而其它的提升算法分裂树一般采用的是深度方向或者水平明智而不是叶，明智的。因此，在LightGBM算法中，当增长到相同的叶子节点，叶明智算法比水平-wise算法减少更多的损失。因此导致更高的精度，而其他的任何已存在的提升算法都不能够达。与此同时，它的速度也让人感到震惊，这就是该算法名字灯的原因。

LightGBM与Xgboost区别：

因此LightGBM针对Xgboost这些缺点进行了相应的改进

1.LightGBM基于histogram算法代替pre-sorted所构建的数据结构，利用histogram后，会有很多有用的tricks。例如histogram做差，提高了cache命中率（主要是因为使用了leaf-wise）

2.在机器学习当中，我们面对大数据量时候都会使用采样的方式（根据样本权值）来提高训练速度。又或者在训练的时候赋予样本权值来关于于某一类样本（如Adaboost）。LightGBM利用了GOSS来做采样算法

3.由于histogram算法对稀疏数据的处理时间复杂度没有pre-sorted好。因为histogram并不管特征值是否为0。因此我们采用了EFB来预处理稀疏数据