通俗理解kaggle比赛大杀器xgboost

小灰灰 2022-05-12 05:58 265阅读 0赞

### 1 决策树 ###

举个例子，集训营某一期有100多名学员，假定给你一个任务，要你统计男生女生各多少人，当一个一个学员依次上台站到你面前时，你会怎么区分谁是男谁是女呢？

很快，你考虑到男生的头发一般很短，女生的头发一般比较长，所以你通过头发的长短将这个班的所有学员分为两拨，长发的为“女”，短发为“男”。

相当于你依靠一个指标“头发长短”将整个班的人进行了划分，于是形成了一个简单的决策树，而划分的依据是头发长短。  
这时，有的人可能有不同意见了：为什么要用“头发长短”划分呀，我可不可以用“穿的鞋子是否是高跟鞋”，“有没有喉结”等等这些来划分呢，答案当然是可以的。

但究竟根据哪个指标划分更好呢？很直接的判断是哪个分类效果更好则优先用哪个。所以，这时就需要一个评价标准来量化分类效果了。

怎么判断“头发长短”或者“是否有喉结”是最好的划分方式，效果怎么量化呢？直观上来说，如果根据某个标准分类人群后，纯度越高效果越好，比如说你分为两群，“女”那一群都是女的，“男”那一群全是男的，那这个效果是最好的。但有时实际的分类情况不是那么理想，所以只能说越接近这种情况，我们则认为效果越好。

量化分类效果的方式有很多，比如信息增益（ID3）、信息增益率（C4.5）、基尼系数（CART）等等。

> **信息增益的度量标准：熵**
> 
> ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。
> 
> 什么是信息增益呢？为了精确地定义信息增益，我们先定义信息论中广泛使用的一个度量标准，称为**熵**（entropy），它刻画了任意样例集的纯度（purity）。给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：
> 
> > ![0_1326017614WvVU.gif][]
> > 
> > 上述公式中，p+代表正样例，比如在本文开头第二个例子中p+则意味着去打羽毛球，而p-则代表反样例，不去打球(在有关熵的所有计算中我们定义0log0为0)。
> 
> 举例来说，假设S是一个关于布尔概念的有14个样例的集合，它包括9个正例和5个反例（我们采用记号\[9+，5-\]来概括这样的数据样例），那么S相对于这个布尔样例的熵为：
> 
> > Entropy（\[9+，5-\]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。
> 
> So，根据上述这个公式，我们可以得到：
> 
>  *  如果S的所有成员属于同一类，则Entropy(S)=0；
>  *  如果S的正反样例数量相等，则Entropy(S)=1；
>  *  如果S的正反样例数量不等，则熵介于0，1之间
> 
> 如下图所示：
> 
> > ![0_1326018003ADwJ.gif][]
> 
> 看到没，通过Entropy的值，你就能评估当前分类树的分类效果好坏了。

更多细节如剪枝、过拟合、优缺点、可以参考此文《[决策树学习][Link 1]》。

所以，现在决策树的灵魂已经有了，即依靠某种指标进行树的分裂达到分类/回归的目的，总是希望纯度越高越好。

###  ###

### 2.回归树与集成学习 ###

如果用一句话定义xgboost，很简单：Xgboost就是由很多CART树集成。但，什么是CART树？

> 数据挖掘或机器学习中使用的决策树有两种主要类型：
> 
> 1.  分类树分析是指预测结果是数据所属的类（比如某个电影去看还是不看）
> 2.  回归树分析是指预测结果可以被认为是实数（例如房屋的价格，或患者在医院中的逗留时间）
> 
> 而术语分类回归树（CART，Classification And Regression Tree）分析是用于指代上述两种树的总称，由Breiman等人首先提出。

**2.1 回归树**  
事实上，分类与回归是两个很接近的问题，分类的目标是根据已知样本的某些特征，判断一个新的样本属于哪种已知的样本类，它的结果是离散值。而回归的结果是连续的值。当然，本质是一样的，都是特征（feature）到结果/标签（label）之间的映射。

理清了什么是分类和回归之后，理解分类树和回归树就不难了。

分类树的样本输出（即响应值）是类的形式，比如判断这个救命药是真的还是假的，周末去看电影《风语咒》还是不去。而回归树的样本输出是数值的形式，比如给某人发放房屋贷款的数额就是具体的数值，可以是0到300万元之间的任意值。

所以，对于回归树，你没法再用分类树那套信息增益、信息增益率、基尼系数来判定树的节点分裂了，你需要采取新的方式评估效果，包括预测误差（常用的有均方误差、对数误差等）。而且节点不再是类别，是数值（预测值），那么怎么确定呢？有的是节点内样本均值，有的是最优化算出来的比如Xgboost。

> CART回归树是假设树为二叉树，通过不断将特征进行分裂。比如当前树结点是基于第j个特征值进行分裂的，设该特征值小于s的样本划分为左子树，大于s的样本划分为右子树。
> 
> ![1-3.png][]
> 
> 而CART回归树实质上就是在该特征维度对样本空间进行划分，而这种空间划分的优化是一种NP难问题，因此，在决策树模型中是使用启发式方法解决。典型CART回归树产生的目标函数为：
> 
> ![2-3.png][]
> 
> 因此，当我们为了求解最优的切分特征j和最优的切分点s，就转化为求解这么一个目标函数：
> 
> ![3-3.png][]
> 
> 所以我们只要遍历所有特征的的所有切分点，就能找到最优的切分特征和切分点。最终得到一棵回归树。

**2.2 boosting集成学习**

所谓集成学习，是指构建多个分类器（弱分类器）对数据集进行预测，然后用某种策略将多个分类器预测的结果集成起来，作为最终预测结果。通俗比喻就是“三个臭皮匠赛过诸葛亮”，或一个公司董事会上的各董事投票决策，它要求每个弱分类器具备一定的“准确性”，分类器之间具备“差异性”。

集成学习根据各个弱分类器之间有无依赖关系，分为Boosting和Bagging两大流派：

1.  Boosting流派，各分类器之间有依赖关系，必须串行，比如Adaboost、GBDT(Gradient Boosting Decision Tree)、Xgboost
2.  Bagging流派，各分类器之间没有依赖关系，可各自并行，比如随机森林（Random Forest）

而著名的Adaboost作为boosting流派中最具代表性的一种方法，本博客曾详细介绍它。

> AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。
> 
> 具体说来，整个Adaboost 迭代算法就3步：
> 
> 1.  初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权值：1/N。
> 2.  训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
> 3.  将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。

而另一种boosting方法GBDT（Gradient Boost Decision Tree)，则与AdaBoost不同，GBDT每一次的计算是都为了减少上一次的残差，进而在残差减少（负梯度）的方向上建立一个新的模型。

boosting集成学习由多个相关联的决策树联合决策，什么叫相关联？举个例子

1.  有一个样本\[数据->标签\]是：\[(2，4，5)-> 4\]
2.  第一棵决策树用这个样本训练的预测为3.3
3.  那么第二棵决策树训练时的输入，这个样本就变成了：\[(2，4，5)-> 0.7\]
4.  也就是说，下一棵决策树输入样本会与前面决策树的训练和预测相关

很快你会意识到，Xgboost为何也是一个boosting的集成学习了。

而一个回归树形成的关键点在于：

*  分裂点依据什么来划分（如前面说的均方误差最小，loss）；
 *  分类后的节点预测值是多少（如前面说，有一种是将叶子节点下各样本实际值得均值作为叶子节点预测误差，或者计算所得）

至于另一类集成学习方法，比如Random Forest（随机森林）算法，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有啥关系。本文暂不展开介绍。

### 3.GBDT ###

说到Xgboost，不得不先从GBDT(Gradient Boosting Decision Tree)说起。因为xgboost本质上还是一个GBDT，但是力争把速度和效率发挥到极致，所以叫X (Extreme) GBoosted。

包括前面说过，两者都是boosting方法（如图所示：Y = Y1 + Y2 + Y3）

![70][]  
咱们来看个年龄预测的例子。

> 简单起见，假定训练集只有4个人：A,B,C,D，他们的年龄分别是14,16,24,26。其中A、B分别是高一和高三学生；C,D分别是应届毕业生和工作两年的员工。

如果是用一棵传统的回归决策树来训练，会得到如下图所示结果：

![quesbase64153148112917172596.png][]  
现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。

我们会得到如下图所示结果：

![quesbase64153148115267426581.png][]  
在第一棵树分枝和图1一样，由于A,B年龄较为相近，C,D年龄较为相近，他们被分为左右两拨，每拨用平均年龄作为预测值。

*  此时计算残差（**残差的意思就是：A的实际值 - A的预测值 = A的残差**），所以A的残差就是实际值14 - 预测值15 = 残差值-1。
 *  注意，A的预测值是指前面所有树累加的和，这里前面只有一棵树所以直接是15，如果还有树则需要都累加起来作为A的预测值。

> 残差在数理统计中是指实际观察值与估计值（拟合值）之间的差。“残差”蕴含了有关模型基本假设的重要信息。如果回归模型正确的话， 我们可以将残差看作误差的观测值。

进而得到A,B,C,D的残差分别为-1,1，-1,1。

然后拿它们的残差-1、1、-1、1代替A B C D的原值，到第二棵树去学习，第二棵树只有两个值1和-1，直接分成两个节点，即A和C分在左边，B和D分在右边，经过计算（比如A，实际值-1 - 预测值-1 = 残差0，比如C，实际值-1 - 预测值-1 = 0），此时所有人的残差都是0。

残差值都为0，相当于第二棵树的预测值和它们的实际值相等，则只需把第二棵树的结论累加到第一棵树上就能得到真实年龄了，即每个人都得到了真实的预测值。

换句话说，现在A,B,C,D的预测值都和真实年龄一致了。Perfect！  
A: 14岁高一学生，购物较少，经常问学长问题，预测年龄A = 15 – 1 = 14  
B: 16岁高三学生，购物较少，经常被学弟问问题，预测年龄B = 15 + 1 = 16

C: 24岁应届毕业生，购物较多，经常问师兄问题，预测年龄C = 25 – 1 = 24  
D: 26岁工作两年员工，购物较多，经常被师弟问问题，预测年龄D = 25 + 1 = 26

### 4.Xgboost ###

**4.1 xgboost树的定义**

本节的示意图基本引用自xgboost原作者陈天奇的讲义PPT中。

举个例子，我们要预测一家人谁是谁，则可以先通过年龄区分开小孩和大人，然后再通过性别区分开是男是女，如下图所示。

> ![70 1][]

就这样，训练出了2棵树tree1和tree2，类似之前gbdt的原理，两棵树的结论累加起来便是最终的结论，所以小孩的预测分数就是两棵树中小孩所落到的结点的分数相加：2 + 0.9 = 2.9。爷爷的预测分数同理：-1 + （-0.9）= -1.9。具体如下图所示

> ![5-2.png][]

恩，你可能要拍案而起了，惊呼，这不是跟上文介绍的gbdt乃异曲同工么？

事实上，如果不考虑工程实现、解决问题上的一些差异，xgboost与gbdt比较大的不同就是目标函数的定义。xgboost的目标函数如下图所示：

![quesbase6415314827826172363.png][]

其中

*  红色箭头所指向的L 即为损失函数（比如平方损失函数：![l][] (yi,y^i) = (yi−y^i)2，或logistic损失函数：![70 2][]）
 *  红色方框所框起来的是正则项（包括L1正则、L2正则）
 *  红色圆圈所圈起来的为常数项
 *  对于![f(x)][f_x]，xgboost利用泰勒展开三项，做一个近似

我们可以很清晰地看到，最终的目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。

额，峰回路转，突然丢这么大一个公式，不少人可能瞬间就懵了。没事，下面，咱们来拆接下这个目标函数。

**4.2 xgboost目标函数**

xgboost的核心算法思想不难，基本就是

1.  不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。
    
    ![4-2.png][]
    
    注：w\_q(x)为叶子节点q的分数，![70 3][]对应了所有K棵回归树（regression tree）的集合，而f(x)为其中一棵回归树。
2.  当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数
3.  最后只需要将每棵树对应的分数加起来就是该样本的预测值。

显然，我们的目标是要使得树群的预测值![70 4][]尽量接近真实值![y\_\{i\}][y_i]，而且有尽量大的泛化能力。

所以，从数学角度看这是一个泛函最优化问题，故把目标函数简化如下：

![quesbase64153155669134287033.png][]

如你所见，这个目标函数分为两部分：损失函数和正则化项。且**损失函数揭示训练误差**（即预测分数和真实分数的差距）**，正则化定义复杂度。**

对于上式而言，![70 4][]是整个累加模型的输出，正则化项∑kΩ(![^\{f\_\{k\}\}][f_k])是则表示树的复杂度的函数，值越小复杂度越低，泛化能力越强，其表达式为

![quesbase64153155674940294423.png][]

T表示叶子节点的个数，w表示叶子节点的分数。直观上看，目标要求预测误差尽量小，且叶子节点T尽量少（γ控制叶子结点的个数），节点数值w尽量不极端（λ控制叶子节点的分数不会过大），防止过拟合。

> 插一句，一般的目标函数都包含下面两项
> 
> ![70 5][]
> 
> 其中，误差/损失函数鼓励我们的模型尽量去拟合训练数据，使得最后的模型会有比较少的 bias。而正则化项则鼓励更加简单的模型。因为当模型简单之后，有限数据拟合出来结果的随机性比较小，不容易过拟合，使得最后模型的预测更加稳定。

**4.2.1 模型学习与训练误差**

具体来说，目标函数第一部分中的 ![70 6][] 表示第![70 6][]个样本，![70 7][] (y^i−yi) 表示第 ![70 6][] 个样本的预测误差，我们的目标当然是误差越小越好。

类似之前GBDT的套路，xgboost也是需要将多棵树的得分累加得到最终的预测得分。

![hPRke6w.png][]

那接下来，我们如何选择每一轮加入什么![f][]呢？答案是非常直接的，选取一个![70 8][] 来使得我们的目标函数尽量最大地降低。

> ![70 9][]

再强调一下，第t轮的模型预测等于前t-1轮的模型预测y(t-1)加上ft，因此误差函数项记为l(yi,y(t-1)+ft),后面一项为正则化项。在当前步，![70 10][]以及y(t-1)都是已知值，模型学习的是![70 8][]。

上面这个公式可能有些过于抽象，我们可以考虑当![70 7][] 是平方误差的情况，这个时候我们的目标可以被写成下面这样的二次函数

> ![70 11][]

更加一般的，损失函数不是二次函数咋办？泰勒展开，不是二次的想办法近似为二次（如你所见，定义了一阶导![g][]和二阶导![h][]）。

> ![4UggIum.png][]

由于前t-1棵树的预测分数与![y\_\{i\}][y_i]的残差对目标函数的优化不影响，可以直接去掉，且常数项也可以移除，从而得到如下一个比较统一的目标函数。

> ![quPhp1K.png][]

这时，目标函数只依赖于每个数据点的在误差函数上的一阶导数![g][]和二阶导数![h][]（相信你已看出xgboost的不同了，目标函数保留了泰勒展开的二次项）。

到目前为止我们讨论了目标函数中的第一个部分：训练误差。接下来我们讨论目标函数的第二个部分：如何定义树的复杂度。

**4.2.2 树的复杂度**

首先，梳理下几个规则

*  用叶子节点集合以及叶子节点得分表示
 *  每个样本都落在一个叶子节点上
 *  q(x)表示样本x在某个叶子节点上，wq(x)是该节点的打分,即该样本的模型预测值

所以当我们把树成**结构部分q**和**叶子权重部分w后，**结构函数q把输入映射到叶子的索引号上面去，而w给定了每个索引号对应的叶子分数是什么。

> ![P5QtOgo.png][]

另外，如下图所示，xgboost对树的复杂度包含了两个部分：

1.  一个是树里面叶子节点的个数T
2.  一个是树上叶子节点的得分w的L2模平方（对w进行L2正则化，相当于针对每个叶结点的得分增加L2平滑，目的是为了避免过拟合）

> ![20170228153006200][]

还记得4.2节开头对目标函数的说明吧（损失函数揭示训练误差 + 正则化定义复杂度）？

> 从数学角度看这是一个泛函最优化问题，故把目标函数简化如下：
> 
> ![quesbase64153155669134287033.png][]
> 
> 如你所见，这个目标函数分为两部分：误差函数和正则化项。且**误差/损失函数揭示训练误差**（即预测分数和真实分数的差距）**，正则化定义复杂度。**
> 
> 对于上式而言，![70 4][]是整个累加模型的输出，正则化项∑kΩ(![^\{f\_\{k\}\}][f_k])是则表示树的复杂度的函数，值越小复杂度越低，泛化能力越强，其表达式为
> 
> ![quesbase64153155674940294423.png][]
> 
> T表示叶子节点的个数，w表示叶子节点的分数。直观上看，目标要求预测误差尽量小，且叶子节点T尽量少（γ控制叶子结点的个数），节点数值w尽量不极端（λ控制叶子节点的分数不会过大），防止过拟合。

在这种新的定义下，我们可以把目标函数进行如下改写

![20160421105451052][]

其中![70 12][]被定义为每个叶节点 j 上面样本集合 ![20160421105402974][]，g是一阶导数，h是二阶导数。这一步是由于xgboost目标函数第二部分加了两个正则项，一个是叶子节点个数(T),一个是叶子节点的分数(w)。

从而，加了正则项的目标函数里就出现了两种累加

*  一种是![70 6][] \- > n（样本数）
 *  一种是![70 13][] \-> T（叶子节点数）

这一个目标包含了T个相互独立的单变量二次函数。我们可以定义

![20160421105610771][]

最终公式可以化简为

![20160421105711217][]

通过对![20160421105932533][]求导等于0，可以得到

![20160421110031784][]

然后把![20160421105932533][]最优解代入得到：

![20160421110139754][]

**4.3 打分函数计算**

Obj代表了当我们指定一个树的结构的时候，我们在目标上面最多减少多少。我们可以把它叫做结构分数(structure score)![20160421110535150][]

**4.3.1 分裂节点**

xgboost的原始论文中给出了两种分裂节点的方法

（1）枚举所有不同树结构的贪心法

不断地枚举不同树的结构，利用这个打分函数来寻找出一个最优结构的树，加入到我们的模型中，再重复这样的操作。不过枚举所有树结构这个操作不太可行，所以常用的方法是贪心法，每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算。

> ![20160421110908655][]

第一个值得注意的事情是为了避免每次扩展都要枚举所有可能的分割方案，如何高效地枚举所有的分割呢？

设置一个值a，然后枚举所有x < a、a < x这样的条件（**x代表某个特征比如age，把age从小到大排序：假定从左至右依次增大，则比a小的放在左边，比a大的放在右边**），对于某个特定的分割a，我们要计算a左边和右边的导数和。

> ![20160421111024891][]

我们可以发现对于所有的特征x，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL和GR。然后用上面的公式计算每个分割方案的分数就可以了。

第二个值得注意的事情就是引入分割不一定会使得情况变好，因为我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝， 当引入的分割带来的增益小于一个阀值的时候，我们可以剪掉这个分割。

大家可以发现，当我们正式地推导目标的时候，像计算分数和剪枝这样的策略都会自然地出现，而不再是一种因为heuristic（启发式）而进行的操作了。

下面是论文中的算法

> ![20170228144201588][]

（2）近似算法

主要针对数据太大，不能直接进行计算

> ![20170228144525979][]

**4.4 小结：Boosted Tree Algorithm**

总结一下，如图所示

![L7PhJwO.png][]

咱们来再次回顾整个过程。

如果某个样本label数值为4，那么第一个回归树预测3，第二个预测为1； 另外一组回归树，一个预测2，一个预测2，那么倾向后一种，为什么呢？前一种情况，第一棵树学的太多，太接近4，也就意味着有较大的过拟合的风险。

OK，听起来很美好，可是怎么实现呢，上面这个目标函数跟实际的参数怎么联系起来，记得我们说过，回归树的参数：

1.  选取哪个feature分裂节点呢
2.  节点的预测值（总不能靠取平均值这么粗暴不讲道理的方式吧，好歹高级一点）

最终的策略就是：贪心 + 最优化（对的，二次最优化） 。

通俗解释贪心策略：就是决策时刻按照当前目标最优化决定，说白了就是眼前利益最大化决定，“目光短浅”策略。

这里是怎么用贪心策略的呢，刚开始你有一群样本，放在第一个节点，这时候T=1，w多少呢，不知道，是求出来的，这时候所有样本的预测值都是w,带入样本的label数值，此时loss function变为

![quesbase64153155689536706939.png][]

*  如果这里的l(w−yi)误差表示用的是平方误差，那么上述函数就是一个关于w的二次函数求最小值，取最小值的点就是这个节点的预测值，最小的函数值为最小损失函数。
 *  本质上来讲，这就是一个二次函数最优化问题！但要是损失函数不是二次函数咋办？泰勒展开，不是二次的想办法近似为二次。

接着来，接下来要选个feature分裂成两个节点，变成一棵弱小的树苗，那么需要：

1.  确定分裂用的feature，how？最简单的是粗暴的枚举/穷举（嗯，够粗暴），然后选择loss function效果最好的那个；
2.  如何确立节点的w以及最小的loss function，大声告诉我怎么做？对，二次函数的求最值（计算二次的最值一般都有固定套路，即导数等于0的点） 。所以，选择一个feature分裂，计算loss function最小值，然后再选一个feature分裂，又得到一个loss function最小值，你枚举完，找一个效果最好的，把树给分裂，就得到了小树苗。

在分裂的时候，你可以注意到，每次节点分裂，loss function被影响的只有这个节点的样本，因而每次分裂，计算分裂的增益（loss function的降低量）只需要关注打算分裂的那个节点的样本。

总而言之，XGBoost使用了和CART回归树一样的想法，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是使用的目标函数不一样。具体做法就是分裂后的目标函数值比单子叶子节点的目标函数的增益，同时为了限制树生长过深，还加了个阈值，只有当增益大于该阈值才进行分裂。

以下便为设定的阈值

> ![15.png][]

从而继续分裂，形成一棵树，再形成一棵树，每次在上一次的预测基础上取最优进一步分裂/建树，是不是贪心策略？

凡是这种循环迭代的方式必定有停止条件，什么时候停止呢？简言之，设置树的最大深度、当样本权重和小于设定阈值时停止生长以防止过拟合。具体而言，则

1.  当引入的分裂带来的增益小于设定阀值的时候，我们可以剪掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思，阈值参数为![70 14][]（即正则项里叶子节点数T的系数）；
2.  当树达到最大深度时则停止建立决策树，设置一个超参数max\_depth，避免树太深导致学习局部样本，从而过拟合；
3.  当样本权重和小于设定阈值时则停止建树。什么意思呢，即涉及到一个超参数-最小的样本权重和min\_child\_weight，和GBM的 min\_child\_leaf 参数类似，但不完全一样。大意就是一个叶子节点样本太少了，也终止同样是防止过拟合；
4.  貌似看到过有树的最大数量的…

### 6 参考文献与推荐阅读 ###

1.  xgboost原始论文：[https://arxiv.org/pdf/1603.02754v1.pdf][https_arxiv.org_pdf_1603.02754v1.pdf]
2.  xgboost作者讲义PPT：[https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf][https_homes.cs.washington.edu_tqchen_pdf_BoostedTree.pdf]
3.  [XGBoost 与 Boosted Tree][XGBoost _ Boosted Tree]
4.  xgboost原理：[https://blog.csdn.net/a819825294/article/details/51206410][https_blog.csdn.net_a819825294_article_details_51206410]
5.  xgboost入门与实战（原理篇）：[https://blog.csdn.net/sb19931201/article/details/52557382][https_blog.csdn.net_sb19931201_article_details_52557382]
6.  [CART的Wikipedia][CART_Wikipedia]
7.  [集成学习（Ensemble Learning)][Ensemble Learning]
8.  [浅谈集成学习：Boosting与随机森林][Boosting]
9.  [从决策树学习谈到贝叶斯分类算法][Link 1]
10. [决策树（三）--完整总结（ID3，C4.5，CART,剪枝，替代）兼源码剖析][--_ID3_C4.5_CART]
11. [一文读懂机器学习大杀器XGBoost原理][XGBoost]
12. [为什么在实际的 kaggle 比赛中 gbdt 和 random forest 效果非常好？][kaggle _ gbdt _ random forest]
13. [通俗、有逻辑的写一篇说下Xgboost的原理，供讨论参考][Xgboost]
14. [七月在线机器学习第8期第4课 决策树、随机森林、GBDT、xgboost][8_4_ _GBDT_xgboost]
15. [xgboost的一些核心参数][xgboost]
16. 在线编辑LaTeX公式：[http://private.codecogs.com/latex/eqneditor.php?lang=zh-cn][http_private.codecogs.com_latex_eqneditor.php_lang_zh-cn]

### 后记 ###

终于大致搞懂了这个经常刷屏的xgboost，再次印证我之前说过的一句话：当你学习某个知识点感觉学不懂时，十有八九不是你不够聪明，十有八九是你所看的资料不够通俗、不够易懂（如果还是不行，问人）。

希望阅读此文的你，也有同样的感受。

以下的本文的改进过程，供理解上参考：

1.  8.4上午第一版，通过一个通俗易懂的年龄预测例子介绍gbdt，因为gbdt是理解xgboost的基础；
2.  8.4下午第二版，xgboost的推导里公式很多，初学者很容易陷进去，后通过抓住xgboost的核心：目标函数，梳理清晰xgboost的脉络框架；
3.  8.5上午第三版，优化了决策树的介绍部分，比如增加对信息增益的介绍；
4.  8.5下午第四版，优化大部分公式的显示，比如之前是纯文本显示，现改成LaTeX图片显示；
5.  8.6上午第五版，优化对booting集成学习的介绍，已让全文更循序渐进；
6.  8.6晚上第六版，规范xgboost目标函数的公式表示，并梳理全文多处细节、公式；
7.  9.1上午第七版，完善4.3.1节中xgboost树的分裂划分方式，以更清晰；

[0_1326017614WvVU.gif]: /images/20220512/58fb8e164113455387a200452e5c02e7.png
[0_1326018003ADwJ.gif]: /images/20220512/d2925b111d3e4325b0613e34f2cd3c35.png
[Link 1]: https://blog.csdn.net/v_july_v/article/details/7577684
[1-3.png]: /images/20220512/6e0863d931314feea21563e94ce6b75a.png
[2-3.png]: /images/20220512/925113b6e5c04a16a95954735b34f1ac.png
[3-3.png]: /images/20220512/7767ca1ac7ca48df830be8498526d7ff.png
[70]: /images/20220512/17f4d36cd4c143518004263c5f54d673.png
[quesbase64153148112917172596.png]: /images/20220512/950473da57104e13a9e1d0a50e8b4db8.png
[quesbase64153148115267426581.png]: /images/20220512/6fa3fac1789e4e6d9b869934adbfcf05.png
[70 1]: /images/20220512/f1c014b14615476abd02e848ab16b9cf.png
[5-2.png]: /images/20220512/d18fe47003f541c390f056ceb69d97d6.png
[quesbase6415314827826172363.png]: /images/20220512/5bb0006c10454d70ac88b14b0ce254a4.png
[l]: https://private.codecogs.com/gif.latex?l
[70 2]: /images/20220512/de14a678e3fc4a3a854af44255d29496.png
[f_x]: https://private.codecogs.com/gif.latex?f%28x%29
[4-2.png]: /images/20220512/0baee0485e12483c956ea1bcefbb7c47.png
[70 3]: /images/20220512/11d473870fc940699e74c47579946c4e.png
[70 4]: https://img-blog.csdn.net/2018080921415487?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZfSlVMWV92/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[y_i]: https://private.codecogs.com/gif.latex?y_%7Bi%7D
[quesbase64153155669134287033.png]: /images/20220512/8a95f158839043f6b28ca487ff66eb36.png
[f_k]: https://private.codecogs.com/gif.latex?%5E%7Bf_%7Bk%7D%7D
[quesbase64153155674940294423.png]: /images/20220512/dc7fe6e5e5fa47e393b757a5da8630dd.png
[70 5]: /images/20220512/cb2548a9ac2b4f088171207ce0acbbeb.png
[70 6]: /images/20220512/b57505b30528424c8ca4ecd80712f594.png
[70 7]: /images/20220512/70b2e671a4da4faa9530c819b1eaf9d7.png
[hPRke6w.png]: http://i.imgur.com/hPRke6w.png
[f]: https://private.codecogs.com/gif.latex?f
[70 8]: /images/20220512/488b1dd2eeaf4ec8a3b28d010c40076b.png
[70 9]: /images/20220512/7da36f168a5848258f20e34ddd50f49d.png
[70 10]: https://img-blog.csdn.net/20180805124717659?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZfSlVMWV92/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 11]: /images/20220512/eb3560a402744437939238acec8d30ae.png
[g]: https://private.codecogs.com/gif.latex?g
[h]: https://private.codecogs.com/gif.latex?h
[4UggIum.png]: http://i.imgur.com/4UggIum.png
[quPhp1K.png]: http://i.imgur.com/quPhp1K.png
[P5QtOgo.png]: http://i.imgur.com/P5QtOgo.png
[20170228153006200]: /images/20220512/d438aa7d36bf4fd68903e9c37eb2791b.png
[20160421105451052]: /images/20220512/5c946a9c2c614487a63f4bbd11d7163b.png
[70 12]: https://img-blog.csdn.net/20180804185718100?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ZfSlVMWV92/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[20160421105402974]: /images/20220512/def0df70f5434beb830c212e96a6f561.png
[70 13]: /images/20220512/77fadfdf97be4593ae75aef62c680332.png
[20160421105610771]: /images/20220512/8ee5360aa81b496196c182e7007b54bf.png
[20160421105711217]: /images/20220512/e6b2edd9c17049728e61a6f715755bad.png
[20160421105932533]: /images/20220512/454eefa541f74b1b8f7beb63e060d270.png
[20160421110031784]: /images/20220512/c2705f24c5bb4f66a6d0f26cb9b439ac.png
[20160421110139754]: /images/20220512/8dab7c70698e417a9d50af496a7b0cb7.png
[20160421110535150]: /images/20220512/7cee4702881b4d5b9a2e2d6ead420e28.png
[20160421110908655]: /images/20220512/2cc6e1bd81154443a6c273ad97b1bf9c.png
[20160421111024891]: /images/20220512/256b2cbc3831444abc91e897a2d42b1d.png
[20170228144201588]: /images/20220512/4dcc1aedc6c34bc78e20020f855a6486.png
[20170228144525979]: /images/20220512/fa13705068b3460a9cf949cad213adba.png
[L7PhJwO.png]: http://i.imgur.com/L7PhJwO.png
[quesbase64153155689536706939.png]: /images/20220512/d98acccf632d4c12a9e3ba23696cbebf.png
[15.png]: /images/20220512/2d063e59288e47b4abf05bb6dcce57bc.png
[70 14]: /images/20220512/0e0230c7b4704f1bbeb46fab472eae84.png
[https_arxiv.org_pdf_1603.02754v1.pdf]: https://arxiv.org/pdf/1603.02754v1.pdf
[https_homes.cs.washington.edu_tqchen_pdf_BoostedTree.pdf]: https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
[XGBoost _ Boosted Tree]: http://www.52cs.org/?p=429
[https_blog.csdn.net_a819825294_article_details_51206410]: https://blog.csdn.net/a819825294/article/details/51206410
[https_blog.csdn.net_sb19931201_article_details_52557382]: https://blog.csdn.net/sb19931201/article/details/52557382
[CART_Wikipedia]: https://en.wikipedia.org/wiki/Decision_tree_learning
[Ensemble Learning]: https://zhuanlan.zhihu.com/p/27689464
[Boosting]: http://xiaosheng.me/2017/06/10/article70/
[--_ID3_C4.5_CART]: https://blog.csdn.net/zhaocj/article/details/50503450
[XGBoost]: http://www.tensorflownews.com/2018/07/19/%E4%B8%80%E6%96%87%E8%AF%BB%E6%87%82%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E5%A4%A7%E6%9D%80%E5%99%A8xgboost%E5%8E%9F%E7%90%86/
[kaggle _ gbdt _ random forest]: https://www.zhihu.com/question/51818176/answer/127637712
[Xgboost]: https://blog.csdn.net/github_38414650/article/details/76061893
[8_4_ _GBDT_xgboost]: https://www.julyedu.com/course/getDetail/65
[xgboost]: https://juejin.im/post/5b74e892e51d45664153b080
[http_private.codecogs.com_latex_eqneditor.php_lang_zh-cn]: http://private.codecogs.com/latex/eqneditor.php?lang=zh-cn