机器学习算法梳理第三篇--XGB
目录
一. 算法原理
在数据建模中，当我们有数个连续值特征时，Boosting分类器是最常用的非线性分类器方法将成百上千个准确率较低的模型组合起来，成为一个准确率较高的模型，这个模型会不断的迭代，每次迭代就会产生一颗新的树，然而当数据集比较大比较复杂的时候，我们可能需要几千次的迭代这样造成巨大的计算瓶颈，xgboost正是为了解决这个瓶颈问题而提出的，单机它采用多线程来加速树的构建过程。在学习xgboost之前必须要熟悉gbdt，gbdt就是boosting方法和cart回归树，通过拟合上一个模型的残差进行学习。
Xgboost相比于GBDT来说，更加有效应用了数值优化，最重要是使损失函数（预测值和真实值的误差）变得更复杂。目标函数依然是所有树的预测值相加等于预测值。
损失函数如下，引入了一阶导数，二阶导数。：
好的模型需要具备两个基本要素：一是要有好的精度（即好的拟合程度），二是模型要尽可能的简单（复杂的模型容易出现过拟合，并且更加不稳定）因此，我们构建的目标函数右边第一项是模型的误差项，第二项是正则化项（也就是模型复杂度的惩罚项）
每一次迭代，都在现有树的基础上，增加一棵树去拟合前面树的预测结果与真实值之间的残差
目标函数如上图，最后一行画圈部分实际上就是预测值和真实值之间的残差
先对训练误差进行展开：
xgboost则对代价函数进行了二阶泰勒展开，同时用到了残差平方和的一阶和二阶导数
再研究目标函数中的正则项：
在这种新的定义下，我们可以把目标函数进行上述改写，其中I被定义为每个叶子上面样本集合Ij = {i|q(xi)=j}，g是一阶导数，h是二阶导数。
树的复杂度可以用树的分支数目来衡量，树的分支我们可以用叶子结点的数量来表示
那么树的复杂度式子：右边第一项是叶子结点的数量T，第二项是树的叶子结点权重w的l2正则化，正则化是为了防止叶子结点过多
此时，每一次迭代，相当于在原有模型中增加一棵树，目标函数中，我们用wq（x）表示一棵树，包括了树的结构以及叶子结点的权重，w表示权重（反映预测的概率），q表示样本所在的索引号（反映树的结构）
将最终得到的目标函数对参数w求导，并令导数为0，并将w*带回目标函数，可知目标函数值由红色方框部分决定：
、
二. 分裂节点算法
三. 正则化
上面的式子已然很漂亮，但是，后面的Ω(ft)仍然是云遮雾罩，不清不楚。现在我们就来定义如何衡量一棵树的正则化项。这个事儿并没有一个客观的标准，可以见仁见智。为此，我们先对CART树作另一番定义，如下所示：
需要解释下这个定义，首先，一棵树有T个叶子节点，这T个叶子节点的值组成了一个T维向量w，q(x)是一个映射，用来将样本映射成1到T的某个值，也就是把它分到某个叶子节点，q(x)其实就代表了CART树的结构。w_q(x)自然就是这棵树对样本x的预测值了。
有了这个定义，xgboost就使用了如下的正则化项：
注意：这里出现了γ和λ，这是xgboost自己定义的，在使用xgboost时，你可以设定它们的值，显然，γ越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大。λ越大也是越希望获得结构简单的树。
为什么xgboost要选择这样的正则化项？很简单，好使！效果好才是真的好。
四. 对缺失值处理
通常情况下，我们人为在处理缺失值的时候大多会选用中位数、均值或是二者的融合来对数值型特征进行填补，使用出现次数最多的类别来填补缺失的类别特征。
很多的机器学习算法都无法提供缺失值的自动处理，都需要人为地去处理，但是xgboost模型却能够处理缺失值，也就是说模型允许缺失值存在。
原是论文中关于缺失值的处理将其看与稀疏矩阵的处理看作一样。在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。
原文的伪代码如下：
五. 优缺点
-
Regularization：
-
标准的GBM并没有XGBoost的Regularization，这个能帮助减少过拟合问题
-
-
Parallel Processing:
-
XGBoost实现了并行计算，与GBM相比非常快
-
但是基于序列的模型，新模型的建立是基于前面已经建立好的模型，如何能实现并行计算呢？探索一下吧
-
XGBoost 支持在Hadoop上实现
-
-
High Flexibility
-
XGBoost允许用户定制优化目标和评价标准
-
这一点将会使得我们对模型有很多可以改进的地方
-
-
Handling Missing Values
-
XGBoost有内嵌的处理缺失值的程序
-
其他模型中用户被要求为缺失值提供相应的与其他值不同的值去填充缺失值，XGBoost会尝试对缺失值进行分类，并学习这种分类
-
-
Tree Pruning:
-
GBM会停止对一个节点进行分裂，当其计算到这个节点的split的loss是负数时，GBM是一个贪婪算法
-
XGBoost的分类取决于max_depth，当树的深度达到max_depth时，开始进行剪枝，移除没有正基尼（no positive gain）节点的split
-
另一个优点是一个节点被分裂的时候loss为-2，当其二次分裂的时候loss可能为+10，GBM会停止该节点的分裂，XGBoost会进入到第二步，然后结合两个分裂的影响，最终为+8
-
-
Built-in Cross-Validation
-
XGBoost允许每一个交叉验证实现boosting过程，因而通过一次run就能获得boosting迭代的优化量
-
与GBM需要运营grid-search且需要限时值的范围获得优化量不同
-
-
Continue on Existing Model
-
用户可以通过上个版本的XGBoost模型训练新版本的模型
-
GBM的sklearn也有这个特性
XGBoost 的不足：
- xgBoosting采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低；
- xgBoosting采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销；LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合，因此引入了一个阈值进行限制，防止过拟合.
六. 应用场景
分类/回归
七. sklearn参数
在运行XGboost之前，必须设置三种类型成熟：general parameters，booster parameters和task parameters：
General parameters
该参数参数控制在提升（boosting）过程中使用哪种booster，常用的booster有树模型（tree）和线性模型（linear model）。
Booster parameters
这取决于使用哪种booster。
Task parameters
控制学习的场景，例如在回归问题中会使用不同的参数控制排序。
XGBoost的变量类型有三类：
-
General Parameters：调控整个方程
-
Booster Parameters：调控每步树的相关变量
-
Learning Task Parameters：调控优化表现的变量
1.General Parameters：
-
booster [default=gbtree]：
-
gbtree: tree-based models，树模型
-
gblinear: linear models，线性模型
-
-
silent [default=0]:
-
设置成1表示打印运行过程中的相关信息
-
通常选择默认值就好，打印出的信息能够帮助理解model
-
-
nthread [default to maximum number of threads available if not set]
-
主要用于并行计算，系统的内核数需要作为变量
-
如果希望运行所有的内核，就不需要设置该参数，程序会自己检测到该值
-
2.Booster Parameters
虽然XGBoost有两种boosters,作者在参数这一块只讨论了tree booster，原因是tree booster的表现总是好于 linear booster
-
eta [default=0.3]
-
与GBM中学习率的概念相似
-
通过减小每一步的权重能够使得建立的模型更鲁棒
-
通常最终的数值范围在[0.01-0.2]之间
-
-
min_child_weight [default=1]
-
定义观测样本生成的孩子节点的权重最小和
-
这个概念与GBM中的min_child_leaf概念类似，但是又不完全一样，这个概念指的是某观测叶子节点中所有样本权重之和的最小值，而GBM指的是叶子节点的最少样本量
-
用于防止过拟合问题：较大的值能防止过拟合，过大的值会导致欠拟合问题
-
需要通过CV调参
-
-
max_depth [default=6]
-
树的最大深度
-
用于防止过拟合问题
-
通过CV调参
-
通常值的范围：[3-10]
-
-
max_leaf_nodes
-
一棵树最多的叶子节点的数目
-
与max_depth定义一个就好
-
-
gamma [default=0]
-
一个节点分裂的条件是其分裂能够起到降低loss function的作用，gamma 定义loss function降低多少才分裂
-
这个变量使得算法变得保守，它的值取决于 loss function需要被调节
-
-
max_delta_step [default=0]
-
此变量的设置使得我们定义每棵树的权重估计值的变化幅度。如果值为0，值的变化没有限制，如果值>0，权重的变化将会变得相对保守
-
通常这个参数不会被使用，但如果是极度不平衡的逻辑回归将会有所帮助
-
-
subsample [default=1]：
-
与GBM的subsample定义一样，指的是没有每棵树的样本比例
-
低值使得模型更保守且能防止过拟合，但太低的值会导致欠拟合
-
通常取值范围[0.5-1]
-
-
colsample_bytree [default=1]
-
与GBM中的max_features类似，指的是每棵树随机选取的特征的比例
-
通常取值范围[0.5-1]
-
-
colsample_bylevel [default=1]
-
指的是树的每个层级分裂时子样本的特征所占的比例
-
作者表示不用这个参数，因为subsample和colsample_bytree组合做的事与之类似
-
-
lambda [default=1]
-
l2正则化权重的术语（同 Ridge regression）
-
用于处理XGBoost里的正则化部分，虽然很多数据科学家不怎么使用这个参数，但是它可以用于帮助防止过拟合
-
-
alpha [default=0]
-
l1正则化的权重术语（同Lasso regression）
-
当特征量特别多的时候可以使用，这样能加快算法的运行效率
-
-
scale_pos_weight [default=1]
-
当样本不平衡时，需要设置一个大于0的数帮助算法尽快收敛
-
3.Learning Task Parameters
此类变量用于定义优化目标每一次计算的需要用到的变量
-
objective [default=reg:linear]
-
用于定义loss function，通常有以下几类
-
binary:logistic-用于二分类，返回分类的概率而不是类别（class）
-
multi:softmax-多分类问题，返回分类的类别而不是概率
-
multi:softprob-与softmax类似，但是返回样本属于每一类的概率
-
-
eval_metric [ default according to objective ]
-
这个变量用于 测试数据（validation data.）
-
默认值：回归-rmse；分类-error
-
通常值如下：
-
rmse – root mean square error
-
mae – mean absolute error
-
logloss – negative log-likelihood
-
error – Binary classification error rate (0.5 threshold)
-
merror – Multiclass classification error rate
-
mlogloss – Multiclass logloss
-
auc: Area under the curve
-
-
-
seed [default=0]
-
随机种子的值
-
有些变量在Python的sklearn的接口中对应命名如下：
1. eta -> learning rate
2. lambda ->reg_lambda
3. alpha -> reg_alpha
https://zhuanlan.zhihu.com/p/34534004
https://blog.****.net/gentelyang/article/details/80100300