XGBoost
https://www.cnblogs.com/mantch/p/11164221.html
https://www.sohu.com/a/327017474_99979179----|
|
- 已经得到了前面t-1棵树构成的加法模型，如何确定第t棵树的学习目标？
学习目标是给定叶子节点结构时，每个叶子节点的得分（使得目标函数最小）
2）生成第t棵树
xgboost采用二叉树，开始的时候，全部样本都在一个叶子节点上。然后叶子节点不断通过二分裂，逐渐生成一棵树。
叶子节点的取值问题前面已经解决了。
选择哪个特征分裂？：xgboost采用特征并行的方法进行计算选择要分裂的特征，即用多个线程，尝试把各个特征都作为分裂的特征，找到各个特征的最优分割点，计算根据它们分裂后产生的增益，选择增益最大的那个特征作为分裂的特征。
3）选择什么分裂点位？
xgboost选择某个特征的分裂点位的方法有两种，一种是全局扫描法，另一种是候选分位点法。
全局扫描法将所有样本该特征的取值按从小到大排列，将所有可能的分裂位置都试一遍，找到其中增益最大的那个分裂点，其计算复杂度和叶子节点上的样本特征不同的取值个数成正比。
而候选分位点法是一种近似算法，仅选择常数个（如256个）候选分裂位置，然后从候选分裂位置中找出最优的那个。
boosting集成学习，由多个相关联的决策树联合决策.
与之对比的是random foreast（随机森林）算法，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有啥毛线关系。
所以首先Xgboost首先是一个boosting的集成学习.
https://www.cnblogs.com/zongfa/p/9324684.html
稀疏自适应分割策略
实际情况下避免不了数据稀疏，产生数据稀疏的原因主要有三个：1，数据缺失，2，统计上为0，3，one-hot编码。而适应稀疏数据非常重要。XGBoost提出的是在计算分割后的分数时，遇到缺失值，分别将缺失值带入左右两个分割节点，然后取最大值的方向为其默认方向。
3.XGBoost的优缺点
与GBDT对比
1.GBDT的基分类器只支持CART树，而XGBoost支持线性分类器，此时相当于带有L1和L2正则项的逻辑回归（分类问题）和线性回归（回归问题）。
2.GBDT在优化时只使用了一阶倒数，而XGBoost对目标函数进行二阶泰勒展开，此外，XGBoost支持自定义损失函数，只要损失函数二阶可导
3.XGBoost借鉴随机森林算法，支持列抽样和行抽样，这样即能降低过拟合风险，又能降低计算。
4.XGBoost在目标函数中引入了正则项，正则项包括叶节点的个数及叶节点的输出值的L2范数。通过约束树结构，降低模型方差，防止过拟合。
5.XGBoost对缺失值不敏感，能自动学习其分裂方向
6.XGBoost在每一步中引入缩减因子，降低单颗树对结果的影响，让后续模型有更大的优化空间，进一步防止过拟合。
7.XGBoost在训练之前，对数据预先进行排序并保存为block，后续迭代中重复使用，减少计算，同时在计算分割点时，可以并行计算
8.可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，这种贪心法异常耗时，这时引进近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂；
与LightGBM对比
1.XGBoost采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低，但是不能找到最精确的数据分割点。同时，不精确的分割点可以认为是降低过拟合的一种手段。
2.LightGBM借鉴Adaboost的思想，对样本基于梯度采样，然后计算增益，降低了计算
3.LightGBM对列进行合并，降低了计算
4.XGBoost采样level-wise策略进行决策树的生成，同时分裂同一层的节点，采用多线程优化，不容易过拟合，但有些节点分裂增益非常小，没必要进行分割，这就带来了一些不必要的计算；LightGBM采样leaf-wise策略进行树的生成，每次都选择在当前叶子节点中增益最大的节点进行分裂，如此迭代，但是这样容易产生深度很深的树，产生过拟合，所以增加了最大深度的限制，来保证高效的同时防止过拟合。
链接：https://www.jianshu.com/p/a62f4dce3ce8