XGB简介

之前分别简要讲了RF与GBDT的原理，现在终于要到XGB，这个算法之前也是困扰了我好久，现在对它进行一个大概的梳理。
基于陈天奇的这篇文章，经典之作：https://arxiv.org/pdf/1603.02754v1.pdf

算法原理

首先我们知道树的集成基本原理是多个分类器结果相加，用陈天奇的例子来说就是：

图一
对每一个样本的预测结果等于tree1和tree2叶子节点的预测分数之和。

考虑这样一种情况，我们有一个数据集，包含m个样本n个特征

根据树的集成思想，为了得到每个样本i最终的预测结果yi，我们需要使用K个additive functions
这里的f代表每棵树的结构，注意这里的每棵树都为回归树，树的结构表示成字母为 这里面的q代表了一棵树的具体结构，w代表这棵树叶子节点的分数，T代表这棵树的叶子节点的数量（这是一个很重要的指标，后面正则化会用到）

• 这样我们就能把上面的每个fk每棵树的结构对应起来了
  

• 这样对于每一个样本，我们都可以把它分到某一棵树的叶子节点i上，得到它在这棵树上的预测分数wi
  这时我们可以得到带正则的损失函数为：
  

  

• 在讲解XGB具体的迭代过程之前，我们需要知道XGB也是一种gradient boosting的方法，联想到之前的GBDT，第t轮次的预测结果应该是等于t-1轮次的结果加上负梯度。接下来我们来看在XGB中，第t轮次的预测结果是怎么计算的。

• 针对第i个样本的预测分数yi，其在第t轮次的预测结果为

  
  记第t轮次的结果可以表示为上一轮次的结果加上一个ft: 因此我们在这一轮的目的就是要找出这样的一个ft，使得损失函数最小： 对于凸函数L我们采用二阶泰勒展开： 关于gi和hi分别有： 由于上一轮次的预测值已经确定了，我们去掉常数可以得到在第t轮次的损失函数： 进一步将后面的损失函数展开：
  需要注意的是这里面的ij代笔第j个叶子节点上的所有样本点集合，对于每一个样本点i，我们的ft表示其在t轮次的预测分数，因此具体到每个叶子节点上，则有因此我们可以将上图中第一个等式的求和号换成第二个等式的求和号。即从以样本为计数单位换为以每个叶子节点为计数单位。

• 接下来就变得简单了，我们可以认为这是一个关于wj的二次函数，求导可得：

  wj 损失函数最小值 关于gi和hi，对于一颗确定的树，我们是可以计算的，如 计算gi hi 上面的Lq(t)非常重要，他可以评估某棵结构为q的树的质量，类似于决策树中的不纯度，它可以作为建树的评判标准。我们马上可以想到，是不是遍历所有的树结构q，然后选出其中根据公式Lq(t)计算的损失函数最小的就可以了呢？答案是否定的，一棵树可以非常复杂，遍历所有的树结构显然是不可能的。

因此我们选取一种贪心算法来分裂，由于训练数据可能有很多特征，构建一棵树可能有许多种不同的构建形式，我们不可能枚举所有可能的树结构q来一一计算它的分值。贪心算法从一个单独树叶开始迭代的增加分支。假设ileft和iright是分割之后节点的左侧和右侧实例集合，令I = ileft U iright，那么在节点分割后的损失减少量为：

这个公式通常用于在实践中评估候选分裂节点是不是应该分裂。

过拟合—Shrinkage and Column Subsampling

上面介绍算法原理部分已经指出损失函数中带有正则项，但是XGB中还有一些防止过拟合的方法。

• 其中一种是Shrinkage方法，这种方法会在每轮迭代中的叶子节点分数wj上增加一个缩减因子，这样会减少每棵单独的树和其叶子节点对未来的树的影响。
• 另外一种方法是Column Subsampling，这中对特征进行子采样的方法之前在RF中已经介绍过，它是每次建树时抽取一部分特征来建树，这里选择特征可以是根据GINI指数来选择，即选择GINI指数较大（即信息量最大，最不纯的特征）的一些特征来建树（当然这里前提是基分类器是CART的情况）他可以起到防止过拟合作用，甚至还有助于加快并行算法的运行速度。

选取分裂节点

Basic Exact Greedy Algorithm

• 对于一个单独的特征，我们先将它的所有取值排序，然后依次选取分裂节点计算Lsplit，选取最大的节点进行分裂。
• 之前一直愁于找不到具体的计算来练练手，想要自己真正用XGB算法来建几棵树，这里有一篇博客讲的非常好，安利一下（除了一些公式的拼写问题）
  https://blog.csdn.net/qq_22238533/article/details/79477547

Approximate Algorithm

exact greedy algorithm使用贪婪算法非常有效的找到分裂节点，但是当数据量很大时，数据不可能一次性的全部读入到内存中，或者在分布式计算中，这样不可能事先对所有值进行排序，且无法使用所有数据来计算分裂节点之后的树结构得分。为解决这个问题，近似算法被应用进来。近似算法首先按照特征取值的统计分布的一些百分位点确定一些候选分裂点，然后算法将连续的值映射到 buckets中，然后汇总统计数据，并根据聚合统计数据在候选节点中找到最佳节点。

这个近似算法其实在陈天奇的论文是最难的部分了，因为这里好像也涉及到XGB的分布式与并行实现，会有一个buckets分桶的思想，好像也是面试问XGB最高阶的问题了

• 对于每个特征，只考察分位点，减少计算复杂度。
• 该算法会首先根据特征分布的百分位数 (percentiles of feature distribution)，提出候选划分点 (candidate splitting points)。接着，该算法将连续型特征映射到由这些候选点划分的分桶(buckets) 中，聚合统计信息，基于该聚合统计找到在 proposal 间的最优解。
• Global：学习每棵树前，提出候选切分点；
• Local：每次分裂前，重新提出候选切分点；
  算法图看得我眼都花了：
  算法讲解

处理缺失值

Sparsity-aware Split Finding

XGB处理缺失值的方式其实很简单，就是比较把缺失值放在左节点还是右节点好，比较的准则就是之前的Lsplit（还记得之前面试时被问到这个问题，当时还不会答...）

算法：

首先需要注意到两个集合一个是I,其包含所有的样本（包括含空缺值的样本）。
Ik是不包含空缺值样本的集合。
在计算总的G和H时用的是I！！也就说空缺值的一阶导数和二阶导数已经包含进去了。
可以看到内层循环里面有两个for，第一个for是从Ik中把特征取值从小到大排序，这里不包括空缺值样本，然后从小到大进行扫描，这个时候在计算GR的时候是用总的G减去GL，HR也是同样用总的H减去HL,这意味着把空缺样本归到了右子结点。

第二个for相反过来，把空缺样本归到了左子结点。
只要比较这两次最大增益出现在第一个for中还是第二个for中就可以知道对于空缺值的分裂方向，这就是xgboost如何学习空缺值的思想。

XGB的主要原理和一些优点就先讲到这儿，之后会补充一些近似算法的详细方法以及XGB为什么能实现并行运算，有时间的话会补上python中XGB包的参数吧，毕竟算法工程师的“主要工作”还是—调参，哈哈哈。