决策树提升-GBDT
大纲
XGBoost和随机森林中决策树的关系
随机森林中，多个决策树是并列关系；XGBoost中，多个决策树是递进关系，即第m个决策树建树时，样本数据本身的权重w是由上一棵树的的权重a修改过的；
GBDT
Boosting(提升)
注：上图公式中的a表示弱学习器的权重；
Bagging(随机森林)思想概述：找到一些学习学得比较好的决策树，并在决策树的基础上进行学习，这样就能学得比任何一个树都好；
Boosting思相概述：在弱学习器学习的过程中将错误样本记录下来，然后将错误样本进行多次学习，直到将错误样本都学会，这样就能得到一个高性能的模型；
Boosting的实现方式
注2：上面的公式为两类分类问题的示例，二分类问题时，可以用符号函数来确定预测结果f(x)，(正类或反类)；
注：AdaBoost M1算法中，m表示第几个弱分类器(学习器)，M表示弱分类器(学习器)的总数；
表示每个弱学习器训练前，每个样本的权重；i表示第几个样本，
在上面示例的分类问题中表示错误率，即分对就不计入误差，分错就就将该样本的权重计入误差；弱分类器为已经训练好的模型；算法概述：
1）对每个弱分类器m(总数为M个)，分别用N个样本进行预测，初始时每个样本的权重为1/N；
2）计算各个弱分类器m的误差，计算误差时不是分对就取0，分错就取1，而是分错为该样本的权重
的正值，分对为0，然后求和算出该分类器的总误差；3）计算各个弱分类器m的权重
；4）利用弱分类器
的权重更新样本在一个弱分类预测时，样本的权重
，即分错的样本权重变大，分对的样本权重变小；5）最后对于训练集的每一个样本数据而言，该样本数据在所有弱分类器上的预测结果的加权组合，即为最终的预测结果；
证明该算法这样取误差、权重、分布后能取得较好效果的步骤为：
注：上面的0-1损失不好优化，因此改为指数损失；注2：指数损失实际上为0-1损失的一个上界；Zm的乘积就是训练误差；
注：Boosting是通过迭代不停的修改样本的权重，使得弱学习器可以集中精力处理分错的样本，最后的强学习器是弱学习器的一个线性组合；
Gradient Boosting
用递度下降的方法来推导Boosting的一般形式；
注：前向逐步递增是指每次增加一个弱学习器
，其权重为
(增加弱学习器时需要使得损失函数更小，如果损失函数的值变大了，是不增加)； 假设损失函数取指数损失后
注：AdaBoost可以看成是损失函数取指数时，前向逐步递增的一个过程；
L2Boosting
注：收缩因子每增加一次，都会学得一个新的弱学习器，如决策树，随着训练参数的同，会生成多个作为弱学习器的决策树；
Boosting as 函数梯度下降
GBM in Scikit learn
注：GBM为弱学器Boosting之后的强学习器；
XGBoost
注：XGBoost是比sklearn中GBM更好的一个实现，是GBM的优化实现；LightGBM同XGBoost，为另一种GBM的优化实现；
理论上，模型整合时，模型之间的差异越大越好；
https://github.com/szilard/benchm-ml
https://github.com/dmlc/xgboost/tree/master/d
下面公式的目的是求使得损失函数最小的
m;
注：L2损失
中，
为要通过训练数据x求的未知参数，
为L2损失的定义形式，即残差的平方的1/2，
为预测值，y为直值，
为L2损失的一阶导，
为L2损失的二阶导；二阶Taylor展开的损失函数
中，
对应Taylor展开式中的
，
对应Taylor展开式中的
；
注：只有叶子节点上才会存放样本，也只有叶子节点有权重，结构函数的自变量是样本数据，返回的是叶子节点的编号；
(XGBoost对树的复杂度，即正则的定义方式)
注：公式中
即叶子节点的权重
，损失函数为上面的二阶Taylor展开的形式；以下为在知道树的结构q的情况下求w：
注：树需要确定的参数为树的结构以及树的分数；
注：树的分数中，
为Gt的平方；以下为求树的结构
注：增加分裂点时，需要确定两个问题：
1）用哪个特征进行分裂；
2）用特征哪个点进行分裂；
为分裂后的树的分数减去分裂前的分数，
的绝对值越大越好；
以下为精确搜索(穷举)的伪代码
注：决策树分裂的特征是可以重复的，因此，在做精确搜索时，每分确定一个分裂点，都必须将所有特征，以及特征下的值都计算一次分数，然后选择一个最佳的；
注：近似搜索时，对于连续型特征值，可将其离散化；
注：不同于线性回归，XGBoost不需要做缺省值填补；如上图中的红色线条，XGBoost在每个节点上可以设置一个缺省方向，如果某个样本在某个节点上的值缺失了，就直接走缺省方向；稀疏特征的方向的确定，也是通过穷举，分别算出左边和右边的分数，再确定稀疏特征的方向；
注：XGBoost建树时，采用的是全分裂的方法，即如果
出现负值，也不提前终止，而是继续分裂直到最大深度，分裂完成后，再对完全树进行剪枝；
注：XGBoost可以单独调用，也可以和sklearn一起使用，上图中第一个XGBoost的接口，第二个为sklearn中GBM的接口；XGBoost中树的最大深度不用太大，通常为3-10，正常情况下可以设置为6；XGBoost中树的深度不宜太深的原因：一棵树没有学好时，会有另外的树集中对错误的样本进行学习；
