前言
xgboost是一种集成学习算法，通过回归树，每一次对残差（实际值与预测值之差）进行拟合，最后把预测值相加得到最终的预测值。比如一个小男孩是10岁，我用一棵树去拟合，得到4.残差是6，第二课树拟合，得到3，这时残差是3.第三棵树继续拟合，得到2.这时我们的预测值就是4+3+2=9.和实际值10比较接近了。
tree
浅析
1）先看下前言说的相加的数学公式。
equ1
q代表每棵树的结构，通过它我们能知道每个样本在每棵树的位置。T是树的叶子数。
2）然后我们看下目标函数的形式
equ2
是样本i的预测值，
则是样本i的实际值。w代表每个叶子节点的分数。l(
,
)代表预测值与真实值的差异。
(f)作为惩罚项，主要是降低模型的复杂度，避免过拟合。惩罚主要包含两个方面，
T表示更少的叶子数，而||w||的平方项则希望更小的叶子节点分数。
3）我们先令=
+
(
).其中
表示前t-1颗树对样本i的预测值之和，而
(
)表示第t棵树对样本i的预测值，然后对equ2进行泰勒二阶展开。
taylor
上式便是泰勒二阶展开公式。equ2按照泰勒公式展开后如下
equ3
为一阶导数，
为二阶导数。仔细看equ2似乎和泰勒展开表达式不太一样，可以把l(
,
)当成是f(x),
x当作是
(
).
4)去掉常数项l(,
)---实际值和前t-1颗树在第t轮都是已知的。然后把
代入，得
equ4
其中j是叶子，是叶子j上所有的样本集合。此时，我们可以求解目标函数的最小值。令上式的导数为0，我们可以解得
= -
.代入equ4得
equ5
这是目标函数的最小值。然而，需要注意的是，它依然是一个变量。因为树的结构未知。那么，能穷举么？似乎不太现实。这时我们使用贪婪算法
5）我们首先将所有样本置于一个叶子节点上，然后再对这个叶子节点进行分裂。然后不断分裂，树不断生长。然而，前面我们说过惩罚项不希望模型太过复杂。我们可以先计算下分裂带来的目标函数下降是多少
equ6
这个式子是分裂前的目标函数减去分裂后的目标函数。当然，我们希望它是正数
6）上式的值同样是未知的。问题在于用哪个特征划分？又用哪个特征值划分？我们首先能想到的是精确算法。遍历每一个特征，遍历每一个特征值，肯定能找出最佳分裂点。这个计算量有点大。于是又有近似算法。简单说这时我们不再遍历每一个特征值，而只是计算部分特征值，从中选取最优分裂点（only among proposed splits）。如下所示
approximate
其中k代表各个特征，,
就是特征k上面的分割点。然后计算各个区间段的
,
.
便是特征k上的特征值。另外，划分分割点也有两种不同的方法，主要是根据划分的时间点。global会在初始阶段就把分割点确定好了，后面怎么分裂都是用这些分割点。而local方法会在分裂后对这些分割点进行调整，分割点不是固定的。通常global需要更多的分割点才能达到和local同样的效果。下面的图形可以说明精确算法、近似算法（global/local）的差异
split finding
eps可以看成是特征分隔区间的倒数。图中可以看出global方法如果只是把特征分成3个左右区间，准确率是不怎么高的。而local只需要3个，global提升到20个，就能媲美精确算法了。
7）如何处理缺失值。xgboost对于缺失值，要么划分到左子树，要么划分到右子树。具体划分到哪一边是从训练数据中得到的。首先我们把所有的样本分到右子树，然后从右子树不断把不缺失的样本分到左子树，计算最大的分数增加值。然后又把所有样本分到左子树，同样操作，计算最大的分数增加值。如果分到右边分数增加的更多，则默认方向就是右边。以后测试时有缺失值到达这个节点时自动分到右边。原文算法如下
direction
是不含缺失值的集合。注意画红线的地方，先把缺失值划分到右边时，是按从小到大的顺序把非缺失值划分到左子树的。而后面是从大到小排序。这样能加快计算速度
陈天奇博士论文：https://arxiv.org/pdf/1603.02754v1.pdf 陈天奇博士PPT：https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
网友评论