GBDT学习总结（Boosting、决策树）
1 GBDT简介
GBDT (Gradient Boosting Decision Tree) 梯度提升决策树。DT－Decision Tree决策树，GB是Gradient Boosting，是一种学习策略，GBDT的含义就是用Gradient Boosting的策略训练出来的DT模型
在前几年深度学习还没有大行其道之前，GBDT在各种竞赛是大放异彩。一是效果确实挺不错。二是即可以用于分类也可以用于回归。三是可以筛选特征
2 集成学习
集成学习就是将多个弱的学习器结合起来组成一个强的学习器。
这就涉及到，先产生一组‘个体学习器’，再用一个策略将它们结合起来。
个体学习器可以选择：决策树，神经网络。
集成时可以所有个体学习器属于同一类算法：全是决策树，或全是神经网络；也可以来自不同的算法。
结合策略：例如分类问题，可以用投票法，少数服从多数。
之所以用这种集成的思想，是因为单独用一个算法时，效果往往不容易达到很好，但如果多个个体算法结合在一起，取长补短，整体效果就会比单独一个要强。
当然集成并不是不管怎么选择学习器，怎么组合都一定会获得更好的效果，最好的情况是，每个学习器都不是特别差，并且要具有一定的多样性，否则可能集成后的会没有效果，或者起负作用。
这就是集成学习的一个核心问题：如何生成准确性又不是很差，并且还能保证多样性的个体学习器呢
目前主要有两种生成方式：
Boosting：个体学习器间存在强依赖关系，必须串行生成。
Bagging，随机森林：个体之间不存在强依赖关系，可并行生成。
3 Boosting
Boosting 的思想,三个臭皮匠顶一个诸葛亮:
- 给定初始训练数据，由此训练出第一个基学习器；
- 根据基学习器的表现对样本进行调整，在之前学习器做错的样本上投入更多关注；
- 用调整后的样本，训练下一个基学习器；
- 重复上述过程 T 次，将 T 个学习器加权结合。
简单讲，就是每次训练单个弱学习器时，都将上一次分错的数据权重提高一点再进行当前单个弱学习器的学习。这样越往后执行，训练出的单个弱学习器就会越在意那些容易分错（权重高）的点。当执行 M 次后，通过加权求和的方式组合成一个最终的学习器。
Boosting模型可以抽象为一个前向加法模型（additive model）:
根据 Boosting 的定义，它有三个基本要素：
基学习器
组合方式
目标函数
4 AdaBoost
Boosting 的代表是 Adaboost。
• 第 1 行，初始化样本权重分布，此时每个数据的权重是一样的，所以是 1/m；
以分类问题为例，最初令每个样本的权重都相等，对于第 t 次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器 C_t。
• 第 2 行，进入 for 循环 T 次，即基学习器的个数为 T 个；
• 第 3 行，根据具有当前权重分布 D_t 的数据集，学习出 h_t；
前一个分类器分错的样本会被用来训练下一个分类器。
h_t 是分量分类器 C_t 给出的对任一样本点 xi 的标记（+1或-1），h_t(xi) = yi 时，样本被正确分类。
• 第 4 行，计算当前学习器的误差；
• 第 5 行，如果误差大于 0.5，就停止；
AdaBoost 方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。
• 第 6 行，计算当前学习器的权重 α_t；
权值是关于误差的表达式，当下一次分类器再次错分这些点之后，会提高整体的错误率，这样就导致分类器权值变小，进而导致这个分类器在最终的混合分类器中的权值变小，也就是说，Adaboost算法让正确率高的分类器占整体的权值更高，让正确率低的分类器权值更低，从而提高最终分类器的正确率。
• 第 7 行，得到下一时刻的权重分布 D_t＋1.
如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost 方法能“聚焦于”那些较难分（更富信息）的样本上。
5 Gradient Boosting
AdaBoost每一轮基学习器训练过后都会更新样本权重，再训练下一个学习器，最后将所有的基学习器加权组合。AdaBoost使用的是指数损失，这个损失函数的缺点是对于异常点非常敏感，因而通常在噪音比较多的数据集上表现不佳。Gradient Boosting在这方面进行了改进，使得可以使用任何损失函数 (只要损失函数是连续可导的)，这样一些比较robust的损失函数就能得以应用，使模型抗噪音能力更强。
和Adaboost不同，Gradient Boosting 在迭代的时候选择梯度下降的方向来保证最后的结果最好。
算法将负梯度作为残差值来学习基本模型h(x).
6 决策树与CART
1976年-1986年，J.R.Quinlan给出ID3算法原型并进行了总结，确定了决策树学习的理论。这可以看做是决策树算法的起点。1993，Quinlan将ID3算法改进成C4.5算法，称为机器学习的十大算法之一。ID3算法的另一个分支是CART(Classification adn Regression Tree, 分类回归决策树)，用于预测。这样，决策树理论完全覆盖了机器学习中的分类和回归两个领域。
6.1 决策树
决策树(decision tree)一般都是自上而下的来生成的。每个决策或事件（即自然状态）都可能引出两个或多个事件，导致不同的结果，把这种决策分支画成图形很像一棵树的枝干，故称决策树。
决策树利用如下图所示的树结构进行决策，每一个非叶子节点是一个判断条件，每一个叶子节点是结论。从跟节点开始，经过多次判断得出结论。
决策树的构建是数据逐步分裂的过程，构建的步骤如下:
步骤1：将所有的数据看成是一个节点，进入步骤2；
步骤2：从所有的数据特征中挑选一个数据特征对节点进行分割，进入步骤3；
步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤4；否则，进入步骤2；
步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。
从上述步骤可以看出，决策生成过程中有三个重要的问题：
（1）数据如何分割
（2）如何选择分裂的属性
（3）什么时候停止分裂
决策树（decision tree）算法基于特征属性进行分类，其主要的优点：模型具有可读性，计算量小，分类速度快。
6.2 ID3
6.2.1 信息增益
熵的概念主要是指信息的混乱程度，变量的不确定性越大，熵的值也就越大，熵的公式可以表示为：
信息增益：表示得知特征A的信息而使得D集合的信息不确定性减少的程度。它为集合D的经验熵减去特征A的条件熵。公式表示为：
g(D,A)=H(D)−H(D|A)
6.2.2 ID3思想
ID3采用信息增益作为选择最优的分裂属性的方法，选择熵作为衡量节点纯度的标准. ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
6.2.3 停止分裂的条件
（1）最小节点数
当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。
（2）熵或者基尼值小于阀值。
由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度时，节点停止分裂。
（3）决策树的深度达到指定的条件
节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。
（4）所有特征已经使用完毕，不能继续进行分裂。
6.2.4 ID3的局限性：
1.ID3没有考虑连续特征
2.ID3采用信息增益大的特征优先建立决策树的节点。在相同条件下，取值比较多的特征比取值少的特征信息增益大。
3.ID3算法对于缺失值的情况没有做考虑
4. 没有对决策树进行剪枝处理，很可能会出现过拟合的问题
6.3 C4.5
C4.5算法与ID3算法一样使用了信息熵的概念，并和ID3一样通过学习数据来建立决策树。每次进行选取特征属性的时候，不再使用ID3算法的信息增益，而是使用了信息增益率这个概念。
属性a的可能取值数目越多，则IV(a)的值越大，这样通过引入约束项，可以从一定程度上削弱“对取值多的属性”的偏好，但是同时增益率准则对可取值数目较少的属性有所偏好。
6.4 CART
ID3中使用了信息增益选择特征，增益大优先选择。C4.5中，采用信息增益比选择特征，减少因特征值多导致信息增益大的问题。CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（比）相反。
6.4.1 基尼系数
6.4.2 CART算法
分类与回归树（Classification and Regression Trees, CART）是由*Leo Breiman, Jerome Friedman, Richard Olshen与Charles Stone于1984年提出，既可用于分类也可用于回归。CART被称为数据挖掘领域内里程碑式的算法。
不同于C4.5，CART本质是对特征空间进行二元划分（即CART生成的决策树是一棵二叉树），并能够对标量属性（nominal attribute）与连续属性（continuous attribute）进行分裂。
CART算法流程与C4.5算法相类似：
- 若满足停止分裂条件（样本个数小于预定阈值，或Gini指数小于预定阈值（样本基本属于同一类，或没有特征可供分裂），则停止分裂；
- 否则，选择最小Gini指数进行分裂；
- 递归执行1-2步骤，直至停止分裂
6.4.3 CART回归树
首先，GBDT使用的决策树是CART回归树，无论是处理回归问题还是二分类以及多分类，GBDT使用的决策树通通都是都是CART回归树。为什么不用CART分类树呢？因为GBDT每次迭代要拟合的是梯度值，是连续值所以要用回归树。
对于回归树算法来说最重要的是寻找最佳的划分点，那么回归树中的可划分点包含了所有特征的所有可取的值。在分类树中最佳划分点的判别标准是熵或者基尼系数，都是用纯度来衡量的，但是在回归树中的样本标签是连续数值，所以再使用熵之类的指标不再合适，取而代之的是平方误差，它能很好的评判拟合程度。
7 GBDT算法说明
将Decision Tree和Gradient Boosting介绍完了，下面将这两部分组合在一起就是我们的GBDT了。
决策树和Gradient Boosting结合诞生了GBDT，GBDT继承了决策树的诸多优点，同时也改进了其缺点。由于GBDT采用的树都是复杂度低的树，所以方差很小，通过梯度提升的方法集成多个决策树，最终能够很好的解决过拟合的问题。然而Boosting共有的缺点为训练是按顺序的，难以并行，这样在大规模数据上可能导致速度过慢，所幸近年来XGBoost和LightGBM的出现都极大缓解了这个问题.
7.1 GBDT构造特征
如上图所示，我们 使用 GBDT 生成了两棵树，两颗树一共有五个叶子节点。我们将样本 X 输入到两颗树当中去，样本X 落在了第一棵树的第二个叶子节点，第二颗树的第一个叶子节点，于是我们便可以依次构建一个五纬的特征向量，每一个纬度代表了一个叶子节点，样本落在这个叶子节点上面的话那么值为1，没有落在该叶子节点的话，那么值为 0.
于是对于该样本，我们可以得到一个向量[0,1,0,1,0] 作为该样本的组合特征，和原来的特征一起输入到逻辑回归当中进行训练。实验证明这样会得到比较显著的效果提升。