机器学习 Boosting 和 xgboost

Boosting

工作机制：先从初始训练集练出一个基学习器，再根据基学习器的表现对训练的样本分布进行调整，使得先前基学习器的训练样本在后续受到更多的关注，然后基于调整后的样本分布来训练下一个基学习器；如此循环往复，直至学习器达到事先指定的值T，最终将这T个基学习器进行加权结合。
Boosting有很多实现版本，比如Adaboost,GBDT 和XGBoost,由于书中已经详细的讲解了Adaboost，我们将主要介绍GBDT 和XGBoost。
1． CART——Boost的基础
CART(回归树, regressiontree)是xgboost最基本的组成部分。其根据训练特征及训练数据构建分类树，判定每条数据的预测结果。其中构建树使用gini指数计算增益，即进行构建树的特征选取。
一个CART往往过于简单,并不能有效地做出预测，为此，采用更进一步的模型boosting tree，利用多棵树来进行组合预测。
输入：训练集T={(x_1,y_1 ),(x_2,y_2 ),…(x_n,y_n ),)}
输出：提升树f_M (x)
步骤(1):初始化f_0 (x)=0
(2)、对m=1,2,3,…M（a）计算残差r_mi=y_i-f_((m-1) ) (x_i ),i=1,2,…,n
(b)拟合残差r_mi学习一个回归树，得到T(x:θ_M) 更新f_m (x)=f_((m-1) ) (x)+T(x:θ_m)
(3)、得到回归提升树：f_M (x)=∑_(m=1)^M▒〖T(x:θ_m)〗
2、gbdt算法
gbdt的算法可以总结为：
a、算法在拟合的每一步都新生成一颗决策树；
b、在拟合这棵树之前，需要计算损失函数在每个样本上的一阶导和二阶导，即 g_i 和 h_i ；
c、通过贪心策略生成一颗树，计算每个叶子结点的的G_i 和 H_i ，利用等式 〖w_j〗^*=G_j/(H_j+λ)计算预测值 w ；
d、把新生成的决策树 f_t (x) 加入 〖y ̂_i〗^t=〖y ̂_i〗^(t-1)+ϵf_t (x_i) ，其中ϵ 为学习率，主要为了抑制模型的过拟合。

1、XGBoost——GBDT树的提升

3XGBoost具体过程
首先，定义一个目标函数f(t)=∑_(i=1)^n▒〖L(y_i,y ̂^(t-1)+f_t (x_i ))+Ω(f_t )+c〗
正则项：Ω(f_t )=√T+1/2 λ∑_(i=1)^{T▒〖ω_j〗}2
T：叶子节点数
ω_j：j个叶子节点的权重
利用泰勒展开式f(x+∆x)≈f(x)+f^’(x) ∆x+1/2 f^’’ (x)∆x^2,对上式进行展开：
f(t)≈∑_(i=1)^n▒〖[L(y_i,y ̂^(t-1) )+g_i f_t (x_i )+1/2 h_i 〖f_t〗^2 (x_i )]+Ω(f_t )+c〗
g_i： L(y_i,y ̂^(t-1) )对y ̂^(t-1)的一阶导数
h_i： L(y_i,y ̂^(t-1) )对y ̂^(t-1)的二阶导数
L(y_i,y ̂^(t-1) )：真实值与前一个函数计算所得残差
由于残差是一致的（我们都是在已知前一个树的情况下计算下一颗树的），同时，在一个叶子节点上的数的函数值是相同的，可以做合并，于是
f(t)≈∑_(i=1)^n▒〖[L(y_i,y ̂^(t-1) )+g_i f_t (x_i )+1/2 h_i 〖f_t〗^2 (x_i )]+Ω(f_t )+c〗
=∑_(i=1)^n▒〖[g_i f_t (x_i )+1/2〗 h_i 〖f_t〗^2 (x_i)]+Ω(f_t )+c
=∑_(i=1)^T▒〖[(∑_(i∈I_j)▒〖g_i)w_j+1/2(〗〗 ∑_(i∈I_j)▒〖h_i)〖w_j〗^2]+γT+1/2 λ∑_(i=1)^{T▒〖〖w_j〗}2+C〗〗
=∑_(i=1)^T▒〖[(∑_(i∈I_j)▒〖g_i)w_j+1/2(〗〗 ∑_(i∈I_j)▒〖h_i)〖w_j〗^2]+γT+C〗

通过对t求导等于0，可以得到：
w_j=-G_j/(H_j+λ)
将w_j带入目标函数的简化公式如下：
f(t)=-1/2 ∑_(j=1)^{T▒〖〖G_j〗}2/(H_j+λ)+√T〗+C
目标函数简化后，看可以看到XGBoost的目标函数是自定义的，计算时只是用到了它的一阶导和二阶导。得到简化公式后，下一步针对选择的特征计算其所带来的增益，从而选择合适的分裂特征
g(ϕ)=g(before)-g(after)
=1/2 [〖G_L〗^{2/(H_L+λ)+〖G_R〗}2/(H_R+λ)-(G_L+G_R )^2/(H_L+H_R+λ)]-γ
GBDT和XGBoost的区别（有很多的不同，这里选取几点进行说明）
1、传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的logistic回归（分类问题）或者线性回归（回归问题）。
2、传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。 xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的方差，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
3、Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
4、对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向，具体来说就是，XGboos把缺失值当做稀疏矩阵来对待，本身的在节点分裂时不考虑的缺失值的数值。缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那一个。如果训练中没有数据缺失，预测时出现了数据缺失，那么默认被分类到右子树。
xgboost工具支持并行。xgboost的并行不是树粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为块结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个块结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
5.XGboost处理缺失值
随机森林与GBDT的区别
1、随机森林采用的bagging思想，而GBDT采用的boosting思想。这两种方法都是Bootstrap思想的应用，Bootstrap是一种有放回的抽样方法思想。虽然都是有放回的抽样，但二者的区别在于：Bagging采用有放回的均匀取样，而Boosting根据错误率来取样（Boosting初始化时对每一个训练样例赋相等的权重1／n，然后用该算法对训练集训练t轮，每次训练后，对训练失败的样例赋以较大的权重），因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的，各训练集之间相互独立，弱分类器可并行，而Boosting的训练集的选择与前一轮的学习结果有关，是串行的。
2‘组成随机森林的树可以是分类树，也可以是回归树；而GBDT只能由回归树组成。
组成随机森林的树可以并行生成；而GBDT只能是串行生成。
对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来。
随机森林对异常值不敏感；GBDT对异常值非常敏感。
随机森林对训练集一视同仁；GBDT是基于权值的弱分类器的集成。
7、随机森林是通过减少模型方差提高性能；GBDT是通过减少模型偏差提高性能。
XGBoost算法可以说是一种集成式提升算法，是将许多基础模型集成在一起，形成一个很强的模型。这里的基础模型可以是分类与回归决策树CART（Classification and Regression Trees），也可以是线性模型。如果基础模型是CART树（如图1所示），比如第1颗决策树tree1预测左下角男孩的值为+2，对于第1颗决策树遗留下来的剩余部分，使用第2颗决策树预测值为+0.9，则对男孩的总预测值为2+0.9=2.9。
GBDT
GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学。这就是Gradient Boosting在GBDT中的意义,一般梯度迭代。

GBDT 还是年龄预测，简单起见训练集只有4个人，A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图1所示结果：
GBDT(Gradient Boosting DecisionTree)梯度提升迭代决策树，是一个集成模型，基分类器采用CART，集成方式为Gradient Boosting。GBDT是通过采用加法模型（即基函数的线性组合），以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。GBDT算法的直观理解是，每一轮预测和实际值有残差，下一轮根据残差再进行预测，最后将所有预测相加，得出结果。GBDT通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度。

随机森林和XGBoost算法

随机森林和XGBoost算法均是集成学习的子类，两者有许多相似之处。
随机森林与XGBoost均依靠于决策树的构建模型，并支持并行化方法能在大数据集上有效运行。在处理高维数据时，两种算法均支持列抽样以降低计算量。
另外，两者在抗过拟合方面异曲同工，随机森林利用每棵决策树随机选取样本，随机选取特征防止过拟合，而XGBoost则是通过引入正则化项控制模型的复杂程度。
但两者在许多方面存在差异。
在思想方面，随机森林沿用bagging设计构思，其每棵树都是独立的；而XGBoost算法则沿用boosting思想设计，前面决策树的训练决定着下一棵决策树的输入样本。
在处理异常值方面，由于设计思想原因XGBoost算法相对于随机森林对异常值更敏感。
在性能提高方面，随机森林是通过减少数据的方差提升性能；XGBoost则是通过减少偏差提高性能。
在最终的输出结果方面，随机森林采用多数投票等综合方法；而XGBoost是将所有结果累加起来，利用多棵相关联的树联合决策。

（从word 上面粘贴过来的文档还是有数学符号的不兼容啊，看来以后只能直接在MARKDOWN上面编辑了）