xgboost原理
之前一篇文章提到了GBDT，其实就是做一个铺垫，引出今天要说的两个，xgboost和lightboost。
xgboost是GBDT的改进和重要实现，主要在于：
- 提出稀疏感知(sparsity-aware)算法。
- 加权分位数快速近似数学习算法。
- 缓存访问模式，数据压缩和分片上的实现上的改进。
- 加入了Shrinkage和列采样，一定程度上防止过拟合。Tree Boosting
Tree Boosting
XGBoost是一个树集成模型，它使用的是K（树的总数为K）个树的每棵树对样本的预测值的和作为该样本在XGBoost系统中的预测。
预测值
每棵树对样本预测的结果为权重 ,如下图所示，图中未两棵树，因为权重都为1，所以预测值为两棵树x的相加
目标函数
目的是：目标函数也就是均方误差最小
如何最优函数解
arg min f(x)：当f(x)取最小值时，x的取值
模型预测值
如下所示，其中q表示每棵树的结构映射每个样本到相应的叶节点的分数，即q表示树的模型，输入一个样本，根据模型将样本映射到叶节点输出预测的分数；Wq(x)表示树q的所有叶节点的分数组成集合；T是树q的叶节点数量。
目标函数推导
其中为惩罚项，函数如下
惩罚项当中包括节点的个数和权重的平方和，这里遵循一个奥卡姆剃刀准则：最简单的就是最好的。所以节点数越多那么模型就越复杂，模型越复杂那么就越有可能过拟合。然后为什么加上权重的平方和呢？因为我们不希望模型给予某些特征过大的权重，当这个特征发生变化时会对整个模型造成很大的影响，我们希望每个特征都具有更加平均的权重。
这里的和
就是xgboost调参时的两个正则化参数
接下来用泰勒展开来近似原来的目标
常数项先不管它，最终得到这样一个目标函数
其中
在通过节点遍历后样本遍历，计算得到最后的目标函数为
其中
由上图可以看出，当我们指定一颗树的结构的时候，每棵树的得分(score)只与损失函数的一阶导数和二阶倒数相关（γ和λ是在实际应用中需要自己调参的），而该得分表示我们在目标上面最多减少多少。我们可以把它叫做结构分数(structure score)。你可以认为这个就是类似吉尼系数一样更加一般的对于树结构进行打分的函数。
节点的划分
树学习的其中之一的重要问题就是找到最好的节点划分，而节点划分的目的是寻找一个最优结构的树。假设IL和IR是一个节点切分后的左右节点，I等于IL和IR的并集。然后切分后的损失函数定义如下：
节点划分有两种方式，一是基本精确的贪心算法（Basic Exact Greedy Algorithm），二是近似算法（Approximate Algorithm）。下面我们来分别介绍这两种方式。
基本精确的贪心算法（Basic Exact Greedy Algorithm）
为了找到节点最好的划分，该算法的原理是在所有特征上枚举所有的可能的划分，我们称这个算法为Basic Exact Greedy Algorithm。该算法要求为连续特征枚举所有可能的切分，这对计算机的要求很高，所以该算法为了有效的做到这一点，首先根据特征值排序数据并且按照顺序访问数据，以累积方程（6）中结构分数的梯度统计量。
近似算法
Basic Exact Greedy Algorithm是一个非常精确的算法，因为它枚举的所有可能的切分点。但是，当数据不能完全的加载到内存时，它可能不是特别有效地。同样的问题也出现在分布式的设置中。为了有效的支持在这两种设置中的有效的梯度提升，一个近似算法需要被使用。该算法首先根据特征分布的百分位数提出n个候选切分节点，然后，算法将位于相邻分位点之间的样本分在一个桶中，在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。注意到上面算法流程中表明有全局的近似(global)和局部(local)的近似，所谓全局就是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部就是在具体的某一次分裂节点的过程中采用近似算法。该算法如下所示：
总结两种：贪婪就是连续特征枚举所有可能的切分，近似则是根据特征分布的百分位数提出n个候选切分节点
带权重的分位数草图（Weighted Quantile Sketch）
Weighted Quantile Sketch是近似算法中的一个重要步骤，解决近似算法中如何选取候选切分点的问题。特征的百分位数用于使候选节点均匀地分布在数据上，比如某个特征的样本点是1~100，特征的百分位数设为2%，则候选节点的选择就是100*0.02*1=2，4，…，100。
xgboost的优缺点
与GBDT相比
1）GBDT以传统CART作为基分类器，而XGBoost支持线性分类器，相当于引入L1和L2正则化项的逻辑回归（分类问题）和线性回归（回归问题）；
2）GBDT在优化时只用到一阶导数，XGBoost对代价函数做了二阶Talor展开，引入了一阶导数和二阶导数。XGBoost支持自定义的损失函数，只要是能满足二阶连续可导的函数均可以作为损失函数
3）XGBoost在损失函数中引入正则化项，用于控制模型的复杂度。正则化项包含全部叶子节点的个数，每个叶子节点输出的score的L2模的平方和。从Bias-variance tradeoff角度考虑，正则项降低了模型的方差，防止模型过拟合，这也是xgboost优于传统GBDT的一个特性。
4）当样本存在缺失值是，xgBoosting能自动学习分裂方向，即XGBoost对样本缺失值不敏感；
5）XGBoost借鉴RF的做法，支持列抽样，这样不仅能防止过拟合，还能降低计算，这也是xgboost异于传统gbdt的一个特性。
6）XGBoost在每次迭代之后，会将叶子节点的权重乘上一个学习率（相当于XGBoost中的eta，论文中的Shrinkage），主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点；
7）XGBoost工具支持并行，但并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值），XGBoost的并行是在特征粒度上的。XGBoost在训练之前，预先对数据进行了排序，然后保存为(block)结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个块结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行；
8）可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，这种贪心法异常耗时，这时引进近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂；
与LightGBM相比:
1）XGBoost采用预排序，在迭代之前，对结点的特征做预排序pre-sorted算法，遍历选择最优分割点。
能够更精确的找到数据分裂点，但是在空间和时间上有很大的开销：
i. 由于需要对特征进行预排序并且需要保存排序后的索引值（为了后续快速的计算分裂点），因此内存需要训练数据的两倍。
- 首先，对所有特征按数值进行预排序。
- 其次，在每次的样本分割时，到每个特征的最优分割点，将数据分裂成左右两个子节点。
ii. 在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低，但是不能找到最精确的数据分割点；
其思想是将连续的浮点特征离散成k个离散值，并构造宽度为k的Histogram。然后遍历训练数据，统计每个离散值在直方图中的累计统计量。在进行特征选择时，只需要根据直方图的离散值，遍历寻找最优的分割点。
Histogram 算法的优缺点：
1) Histogram算法并不是完美的。由于特征被离散化后，找到的并不是很精确的分割点，所以会对结果产生影响。但在实际的数据集上表明，离散化的分裂点对最终的精度影响并不大，甚至会好一些。原因在于decision tree本身就是一个弱学习器，采用Histogram算法会起到正则化的效果，有效地防止模型的过拟合。
2) 由于离散化，因此时间上有很大的提升。
3) Histogram算法还可以进一步加速。一个叶子节点的Histogram可以直接由父节点的Histogram和兄弟节点的Histogram做差得到。一般情况下，构造Histogram需要遍历该叶子上的所有数据，通过该方法，只需要遍历Histogram的k个捅。速度提升了一倍。
网络通信的优化
XGBoost由于采用pre-sorted算法，通信代价非常大，所以在并行的时候也是采用histogram算法；LightGBM采用的histogram算法通信代价小，通过使用集合通信算法，能够实现并行计算的线性加速。
文章部分引用自 https://blog.****.net/qq_24519677/article/details/81809157