最全！两万字带你完整掌握八大决策树！

2020 年 7 月 4 日 AI科技评论

作者 | 阿泽

编辑 | 丛末

决策树是一个非常常见并且优秀的机器学习算法，它易于理解、可解释性强，其可作为分类算法，也可用于回归模型。

本文将分三篇介绍决策树，第一篇介绍基本树（包括 ID3、C4.5、CART），第二篇介绍基于集成学习的决策树， Random Forest、Adaboost、GBDT，第三篇介绍基于 Boosting 框架的主流集成算法，包括 Xgboost 和 LightGBM。

第一篇：基本树

对于基本树我将大致从以下四个方面介绍每一个算法：思想、划分标准、剪枝策略，优缺点。

ID3

ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。

1、思想

从信息论的知识中我们知道：信息熵越大，从而样本纯度越低，。ID3 算法的核心思想就是以信息增益来度量特征选择，选择信息增益最大的特征进行分裂。算法采用自顶向下的贪婪搜索遍历可能的决策树空间（C4.5 也是贪婪搜索）。其大致步骤为：

1）初始化特征集合和数据集合；
2）计算数据集合信息熵和所有特征的条件熵，选择信息增益最大的特征作为当前决策节点；
3）更新数据集合和特征集合（删除上一步使用的特征，并按照特征值来划分不同分支的数据集合）；
4）重复 2），3 ）两步，若子集值包含单一特征，则为分支叶子节点。

2、划分标准

ID3 使用的分类标准是信息增益，它表示得知特征 A 的信息而使得样本集合不确定性减少的程度。

数据集的信息熵：

其中

表示集合 D 中属于第 k 类样本的样本子集。

针对某个特征 A，对于数据集 D 的条件熵

为：

其中

表示 D 中特征 A 取第 i 个值的样本子集，

表示

中属于第 k 类的样本子集。

信息增益 = 信息熵 - 条件熵：

信息增益越大表示使用特征 A 来划分所获得的“纯度提升越大”。

3、缺点

ID3 没有剪枝策略，容易过拟合；
信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于 1；
只能用于处理离散分布的特征；
没有考虑缺失值。

C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

1、思想

C4.5 相对于 ID3 的缺点对应有以下改进方式：

引入悲观剪枝策略进行后剪枝；
引入信息增益率作为划分标准；
将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；

对于缺失值的处理可以分为两个子问题：
问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）
问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）

针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；

针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

2、划分标准

利用信息增益率可以克服信息增益的缺点，其公式为

称为特征 A 的固有值。

这里需要注意，信息增益率对可取值较少的特征有所偏好（分母越小，整体越大），因此 C4.5 并不是直接用增益率最大的特征进行划分，而是使用一个启发式方法：先从候选划分特征中找到信息增益高于平均值的特征，再从中选择增益率最高的。

3、剪枝策略

为什么要剪枝：过拟合的树在泛化能力的表现非常差。

1）预剪枝

在节点划分前来确定是否继续增长，及早停止增长的主要方法有：

节点内数据样本低于某一阈值；
所有节点特征都已分裂；
节点划分前准确率比划分后准确率高。

预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间，但另一方面它是基于“贪心”策略，会带来欠拟合风险。

2）后剪枝

在已经生成的决策树上进行剪枝，从而得到简化版的剪枝决策树。

C4.5 采用的悲观剪枝方法，用递归的方式从低往上针对每一个非叶子节点，评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。

后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但同时其训练时间会大的多。

4、缺点

剪枝策略可以再优化；
C4.5 用的是多叉树，用二叉树效率更高；
C4.5 只能用于分类；
C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；
C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

CART

ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

1、思想

CART 包含的基本过程有分裂，剪枝和树选择。

分裂：分裂过程是一个二叉递归划分过程，其输入和预测特征既可以是连续型的也可以是离散型的，CART 没有停止准则，会一直生长下去；
剪枝：采用代价复杂度剪枝，从最大树开始，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩下根节点。CART 会产生一系列嵌套的剪枝树，需要从中选出一颗最优的决策树；
树选择：用单独的测试集评估每棵剪枝树的预测性能（也可以用交叉验证）。

CART 在 C4.5 的基础上进行了很多提升。

C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；
C4.5 只能分类，CART 既可以分类也可以回归；
CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；
CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；
CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

2、划分标准

熵模型拥有大量耗时的对数运算，基尼指数在简化模型的同时还保留了熵模型的优点。基尼指数代表了模型的不纯度，基尼系数越小，不纯度越低，特征越好。这和信息增益（率）正好相反。

其中 k 代表类别。

基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此基尼指数越小，则数据集纯度越高。基尼指数偏向于特征值较多的特征，类似信息增益。基尼指数可以用来度量任何不均匀分布，是介于 0~1 之间的数，0 是完全相等，1 是完全不相等，

此外，当 CART 为二分类，其表达式为：

我们可以看到在平方运算和二分类的情况下，其运算更加简单。当然其性能也与熵模型非常接近。

那么问题来了：基尼指数与熵模型性能接近，但到底与熵模型的差距有多大呢？

我们知道

，所以

我们可以看到，基尼指数可以理解为熵模型的一阶泰勒展开。这边在放上一张很经典的图：

3、缺失值处理

上文说到，模型对于缺失值的处理会分为两个子问题：

如何在特征值缺失的情况下进行划分特征的选择？
选定该划分特征，模型对于缺失该特征值的样本该进行怎样处理？

对于问题 1，CART 一开始严格要求分裂特征评估时只能使用在该特征上没有缺失值的那部分数据，在后续版本中，CART 算法使用了一种惩罚机制来抑制提升值，从而反映出缺失值的影响（例如，如果一个特征在节点的 20% 的记录是缺失的，那么这个特征就会减少 20% 或者其他数值）。

对于问题 2，CART 算法的机制是为树的每个节点都找到代理分裂器，无论在训练数据上得到的树是否有缺失值都会这样做。在代理分裂器中，特征的分值必须超过默认规则的性能才有资格作为代理（即代理就是代替缺失值特征作为划分特征的特征），当 CART 树中遇到缺失值时，这个实例划分到左边还是右边是决定于其排名最高的代理，如果这个代理的值也缺失了，那么就使用排名第二的代理，以此类推，如果所有代理值都缺失，那么默认规则就是把样本划分到较大的那个子节点。代理分裂器可以确保无缺失训练数据上得到的树可以用来处理包含确实值的新数据。

4、剪枝策略

采用一种“基于代价复杂度的剪枝”方法进行后剪枝，这种方法会生成一系列树，每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的，这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。这种方法需要使用一个单独的测试数据集来评估所有的树，根据它们在测试数据集熵的分类性能选出最佳的树。

我们来看具体看一下代价复杂度剪枝算法：

首先我们将最大树称为

，我们希望减少树的大小来防止过拟合，但又担心去掉节点后预测误差会增大，所以我们定义了一个损失函数来达到这两个变量之间的平衡。损失函数定义如下：

为任意子树，

为预测误差，

为子树

的叶子节点个数，

是参数，

衡量训练数据的拟合程度，

衡量树的复杂度，

权衡拟合程度与树的复杂度。

那么如何找到合适的

来使得复杂度和拟合度达到最好的平衡点呢，最好的办法就是另

从 0 取到正无穷，对于每一个固定的

，我们都可以找到使得

最小的最优子树

。当

很小的时候，

是最优子树；当

最大时，单独的根节点是这样的最优子树。随着

增大，我们可以得到一个这样的子树序列：

，这里的子树

生成是根据前一个子树

剪掉某一个内部节点生成的。

Breiman 证明：将

从小增大，

，在每个区间

中，子树

是这个区间里最优的。

这是代价复杂度剪枝的核心思想。

我们每次剪枝都是针对某个非叶节点，其他节点不变，所以我们只需要计算该节点剪枝前和剪枝后的损失函数即可。

对于任意内部节点 t，剪枝前的状态，有

个叶子节点，预测误差是

；剪枝后的状态：只有本身一个叶子节点，预测误差是

。

因此剪枝前以 t 节点为根节点的子树的损失函数是：

剪枝后的损失函数是

通过 Breiman 证明我们知道一定存在一个

使得

，使得这个值为：

的意义在于，

中，子树

是这个区间里最优的。当

大于这个值是，一定有

，也就是剪掉这个节点后都比不剪掉要更优。所以每个最优子树对应的是一个区间，在这个区间内都是最优的。

然后我们对

中的每个内部节点 t 都计算：

表示阈值，故我们每次都会减去最小的

。

5、类别不平衡

CART 的一大优势在于：无论训练数据集有多失衡，它都可以将其子冻消除不需要建模人员采取其他操作。

CART 使用了一种先验机制，其作用相当于对类别进行加权。这种先验机制嵌入于 CART 算法判断分裂优劣的运算里，在 CART 默认的分类模式中，总是要计算每个节点关于根节点的类别频率的比值，这就相当于对数据自动重加权，对类别进行均衡。

对于一个二分类问题，节点 node 被分成类别 1 当且仅当：

比如二分类，根节点属于 1 类和 0 类的分别有 20 和 80 个。在子节点上有 30 个样本，其中属于 1 类和 0 类的分别是 10 和 20 个。如果 10/20>20/80，该节点就属于 1 类。

通过这种计算方式就无需管理数据真实的类别分布。假设有 K 个目标类别，就可以确保根节点中每个类别的概率都是 1/K。这种默认的模式被称为“先验相等”。

先验设置和加权不同之处在于先验不影响每个节点中的各类别样本的数量或者份额。先验影响的是每个节点的类别赋值和树生长过程中分裂的选择。

6、回归树

CART（Classification and Regression Tree，分类回归树），从名字就可以看出其不仅可以用于分类，也可以应用于回归。其回归树的建立算法上与分类树部分相似，这里简单介绍下不同之处。

1）连续值处理

对于连续值的处理，CART 分类树采用基尼系数的大小来度量特征的各个划分点。在回归模型中，我们使用常见的和方差度量方式，对于任意划分特征 A，对应的任意划分点 s 两边划分成的数据集

和

，求出使

和

各自集合的均方差最小，同时

和

的均方差之和最小所对应的特征和特征值划分点。表达式为：

其中，

为

数据集的样本输出均值，

为

数据集的样本输出均值。

2）预测方式

对于决策树建立后做预测的方式，上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果。

总结

最后通过总结的方式对比下 ID3、C4.5 和 CART 三者之间的差异。

除了之前列出来的划分标准、剪枝策略、连续值确实值处理方式等之外，我再介绍一些其他差异：

划分标准的差异：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺点，偏向于特征值小的特征，CART 使用基尼指数克服 C4.5 需要求 log 的巨大计算量，偏向于特征值较多的特征。
使用场景的差异：ID3 和 C4.5 都只能用于分类问题，CART 可以用于分类和回归问题；ID3 和 C4.5 是多叉树，速度较慢，CART 是二叉树，计算速度很快；
样本数据的差异：ID3 只能处理离散数据且缺失值敏感，C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值；从样本量考虑的话，小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序，处理成本耗时较高，而 CART 本身是一种大样本的统计方法，小样本处理下泛化误差较大；
样本特征的差异：ID3 和 C4.5 层级之间只使用一次特征，CART 可多次重复使用特征；
剪枝策略的差异：ID3 没有剪枝策略，C4.5 是通过悲观剪枝策略来修正树的准确性，而 CART 是通过代价复杂度剪枝。

第二篇：基于集成学习的决策树

本篇主要介绍基于集成学习的决策树，其主要通过不同学习框架生产基学习器，并综合所有基学习器的预测结果来改善单个基学习器的识别率和泛化性。

集成学习

常见的集成学习框架有三种：Bagging，Boosting 和 Stacking。三种集成学习框架在基学习器的产生和综合结果的方式上会有些区别，我们先做些简单的介绍。

1、Bagging

Bagging 全称叫 Bootstrap aggregating，看到 Bootstrap 我们立刻想到著名的开源前端框架（抖个机灵，是 Bootstrap 抽样方法），每个基学习器都会对训练集进行有放回抽样得到子训练集，比较著名的采样法为 0.632 自助法。每个基学习器基于不同子训练集进行训练，并综合所有基学习器的预测值得到最终的预测结果。Bagging 常用的综合方法是投票法，票数最多的类别为预测类别。

2、Boosting

Boosting 训练过程为阶梯状，基模型的训练是有顺序的，每个基模型都会在前一个基模型学习的基础上进行学习，最终综合所有基模型的预测值产生最终的预测结果，用的比较多的综合方式为加权法。

3、Stacking

Stacking 是先用全部数据训练好基模型，然后每个基模型都对每个训练样本进行的预测，其预测值将作为训练样本的特征值，最终会得到新的训练样本，然后基于新的训练样本进行训练得到模型，然后得到最终预测结果。

那么，为什么集成学习会好于单个学习器呢？原因可能有三：

1）训练样本可能无法选择出最好的单个学习器，由于没法选择出最好的学习器，所以干脆结合起来一起用；

2）假设能找到最好的学习器，但由于算法运算的限制无法找到最优解，只能找到次优解，采用集成学习可以弥补算法的不足；

3）可能算法无法得到最优解，而集成学习能够得到近似解。比如说最优解是一条对角线，而单个决策树得到的结果只能是平行于坐标轴的，但是集成学习可以去拟合这条对角线。

偏差与方差

上节介绍了集成学习的基本概念，这节我们主要介绍下如何从偏差和方差的角度来理解集成学习。

1、集成学习的偏差与方差

偏差（Bias）描述的是预测值和真实值之差；方差（Variance）描述的是预测值作为随机变量的离散程度。放一场很经典的图：

模型的偏差与方差

偏差：描述样本拟合出的模型的预测结果的期望与样本真实结果的差距，要想偏差表现的好，就需要复杂化模型，增加模型的参数，但这样容易过拟合，过拟合对应上图的 High Variance，点会很分散。低偏差对应的点都打在靶心附近，所以喵的很准，但不一定很稳；
方差：描述样本上训练出来的模型在测试集上的表现，要想方差表现的好，需要简化模型，减少模型的复杂度，但这样容易欠拟合，欠拟合对应上图 High Bias，点偏离中心。低方差对应就是点都打的很集中，但不一定是靶心附近，手很稳，但不一定瞄的准。

我们常说集成学习中的基模型是弱模型，通常来说弱模型是偏差高（在训练集上准确度低）方差小（防止过拟合能力强）的模型，但并不是所有集成学习框架中的基模型都是弱模型。Bagging 和 Stacking 中的基模型为强模型（偏差低，方差高），而Boosting 中的基模型为弱模型（偏差高，方差低）。

在 Bagging 和 Boosting 框架中，通过计算基模型的期望和方差我们可以得到模型整体的期望和方差。为了简化模型，我们假设基模型的期望为

，方差

，模型的权重为

，两两模型间的相关系数

相等。由于 Bagging 和 Boosting 的基模型都是线性组成的，那么有：

模型总体期望：

模型总体方差（公式推导参考协方差的性质，协方差与方差的关系）：

模型的准确度可由偏差和方差共同决定：

2、Bagging 的偏差与方差

对于 Bagging 来说，每个基模型的权重等于 1/m 且期望近似相等，故我们可以得到：

通过上式我们可以看到：

整体模型的期望等于基模型的期望，这也就意味着整体模型的偏差和基模型的偏差近似。
整体模型的方差小于等于基模型的方差，当且仅当相关性为 1 时取等号，随着基模型数量增多，整体模型的方差减少，从而防止过拟合的能力增强，模型的准确度得到提高。但是，模型的准确度一定会无限逼近于 1 吗？并不一定，当基模型数增加到一定程度时，方差公式第一项的改变对整体方差的作用很小，防止过拟合的能力达到极限，这便是准确度的极限了。

在此我们知道了为什么 Bagging 中的基模型一定要为强模型，如果 Bagging 使用弱模型则会导致整体模型的偏差提高，而准确度降低。

Random Forest 是经典的基于 Bagging 框架的模型，并在此基础上通过引入特征采样和样本采样来降低基模型间的相关性，在公式中显著降低方差公式中的第二项，略微升高第一项，从而使得整体降低模型整体方差。

3、Boosting 的偏差与方差

对于 Boosting 来说，由于基模型共用同一套训练集，所以基模型间具有强相关性，故模型间的相关系数近似等于 1，针对 Boosting 化简公式为：

通过观察整体方差的表达式我们容易发现：

整体模型的方差等于基模型的方差，如果基模型不是弱模型，其方差相对较大，这将导致整体模型的方差很大，即无法达到防止过拟合的效果。因此，Boosting 框架中的基模型必须为弱模型。
此外 Boosting 框架中采用基于贪心策略的前向加法，整体模型的期望由基模型的期望累加而成，所以随着基模型数的增多，整体模型的期望值增加，整体模型的准确度提高。

基于 Boosting 框架的 Gradient Boosting Decision Tree 模型中基模型也为树模型，同 Random Forrest，我们也可以对特征进行随机抽样来使基模型间的相关性降低，从而达到减少方差的效果。

4、小结

我们可以使用模型的偏差和方差来近似描述模型的准确度；
对于 Bagging 来说，整体模型的偏差与基模型近似，而随着模型的增加可以降低整体模型的方差，故其基模型需要为强模型；
对于 Boosting 来说，整体模型的方差近似等于基模型的方差，而整体模型的偏差由基模型累加而成，故基模型需要为弱模型。

️那么这里有一个小小的疑问，Bagging 和 Boosting 到底用的是什么模型呢？

Random Forest

Random Forest（随机森林），用随机的方式建立一个森林。RF 算法由很多决策树组成，每一棵决策树之间没有关联。建立完森林后，当有新样本进入时，每棵决策树都会分别进行判断，然后基于投票法给出分类结果。

1、思想

Random Forest（随机森林）是 Bagging 的扩展变体，它在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括 RF 包括四个部分：

随机选择样本（放回抽样）；
随机选择特征；
构建决策树；
随机森林投票（平均）。

随机选择样本和 Bagging 相同，采用的是 Bootstrap 自助采样法；随机选择特征是指在每个节点在分裂过程中都是随机选择特征的（区别与每棵树随机选择一批特征）。

这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的“平均”特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。

随机采样由于引入了两种采样方法保证了随机性，所以每棵树都是最大可能的进行生长就算不剪枝也不会出现过拟合。

2、优缺点

优点

在数据集上表现良好，相对于其他算法有较大的优势
易于并行化，在大数据集上有很大的优势；
能够处理高维度数据，不用做特征选择。

Adaboost

AdaBoost（Adaptive Boosting，自适应增强），其自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

1、思想

Adaboost 迭代算法有三步：

初始化训练样本的权值分布，每个样本具有相同权重；
训练弱分类器，如果样本分类正确，则在构造下一个训练集中，它的权值就会被降低；反之提高。用更新过的样本集去训练下一个分类器；
将所有弱分类组合成强分类器，各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，降低分类误差率大的弱分类器的权重。

2、细节

1）损失函数

Adaboost 模型是加法模型，学习算法为前向分步学习算法，损失函数为指数函数的分类问题。

加法模型：最终的强分类器是由若干个弱分类器加权平均得到的。

前向分布学习算法：算法是通过一轮轮的弱学习器学习，利用前一个弱学习器的结果来更新后一个弱学习器的训练集权重。第 k 轮的强学习器为：

定义损失函数为 n 个样本的指数损失函数：

利用前向分布学习算法的关系可以得到：

因为

已知，所以令

，随着每一轮迭代而将这个式子带入损失函数，损失函数转化为：

我们求

，可以得到：

将

带入损失函数，并对

求导，使其等于 0，则就得到了：

其中，

即为我们前面的分类误差率。

最后看样本权重的更新。利用

和

，即可得：

这样就得到了样本权重更新公式。

2）正则化

为了防止 Adaboost 过拟合，我们通常也会加入正则化项，这个正则化项我们通常称为步长（learning rate）。对于前面的弱学习器的迭代

加上正则化项

我们有：

的取值范围为

。对于同样的训练集学习效果，较小的

意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

3、优缺点

1）优点

分类精度高；
可以用各种回归分类模型来构建弱学习器，非常灵活；
不容易发生过拟合。

2）缺点

对异常点敏感，异常点会获得较高权重。

GBDT

GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，从名字中我们可以看出来它是属于 Boosting 策略。GBDT 是被公认的泛化能力较强的算法。

1、思想

GBDT 由三个概念组成：Regression Decision Tree（即 DT）、Gradient Boosting（即 GB），和 Shringkage（一个重要演变）

1）回归树（Regression Decision Tree）

如果认为 GBDT 由很多分类树那就大错特错了（虽然调整后也可以分类）。对于分类树而言，其值加减无意义（如性别），而对于回归树而言，其值加减才是有意义的（如说年龄）。GBDT 的核心在于累加所有树的结果作为最终结果，所以 GBDT 中的树都是回归树，不是分类树，这一点相当重要。

回归树在分枝时会穷举每一个特征的每个阈值以找到最好的分割点，衡量标准是最小化均方误差。

2）梯度迭代（Gradient Boosting）

上面说到 GBDT 的核心在于累加所有树的结果作为最终结果，GBDT 的每一棵树都是以之前树得到的残差来更新目标值，这样每一棵树的值加起来即为 GBDT 的预测值。

模型的预测值可以表示为：

为基模型与其权重的乘积，模型的训练目标是使预测值

逼近真实值 y，也就是说要让每个基模型的预测值逼近各自要预测的部分真实值。由于要同时考虑所有基模型，导致了整体模型的训练变成了一个非常复杂的问题。所以研究者们想到了一个贪心的解决手段：每次只训练一个基模型。那么，现在改写整体模型为迭代式：

这样一来，每一轮迭代中，只要集中解决一个基模型的训练问题：使

逼近真实值

。

举个例子：比如说 A 用户年龄 20 岁，第一棵树预测 12 岁，那么残差就是 8，第二棵树用 8 来学习，假设其预测为 5，那么其残差即为 3，如此继续学习即可。

那么 Gradient 从何体现？其实很简单，其残差其实是最小均方损失函数关于预测值的反向梯度(划重点)：

也就是说，预测值和实际值的残差与损失函数的负梯度相同。

但要注意，基于残差 GBDT 容易对异常值敏感，举例：

很明显后续的模型会对第 4 个值关注过多，这不是一种好的现象，所以一般回归类的损失函数会用绝对损失或者 Huber 损失函数来代替平方损失函数。

GBDT 的 Boosting 不同于 Adaboost 的 Boosting，GBDT 的每一步残差计算其实变相地增大了被分错样本的权重，而对与分对样本的权重趋于 0，这样后面的树就能专注于那些被分错的样本。

3）缩减（Shrinkage）

Shrinkage 的思想认为，每走一小步逐渐逼近结果的效果要比每次迈一大步很快逼近结果的方式更容易避免过拟合。即它并不是完全信任每一棵残差树。

Shrinkage 不直接用残差修复误差，而是只修复一点点，把大步切成小步。本质上 Shrinkage 为每棵树设置了一个 weight，累加时要乘以这个 weight，当 weight 降低时，基模型数会配合增大。

2、优缺点

1）优点

可以自动进行特征组合，拟合非线性数据；
可以灵活处理各种类型的数据。

2）缺点

对异常点敏感。

3、与 Adaboost 的对比

1）相同：

都是 Boosting 家族成员，使用弱分类器；
都使用前向分布算法；

2）不同：

迭代思路不同：Adaboost 是通过提升错分数据点的权重来弥补模型的不足（利用错分样本），而 GBDT 是通过算梯度来弥补模型的不足（利用残差）；
损失函数不同：AdaBoost 采用的是指数损失，GBDT 使用的是绝对损失或者 Huber 损失函数；

第三篇：基于 Boosting 框架的主流集成算法

第三篇主要介绍基于 Boosting 框架的主流集成算法，包括 XGBoost 和 LightGBM。

XGBoost

XGBoost 是大规模并行 boosting tree 的工具，它是目前最快最好的开源 boosting tree 工具包，比常见的工具包快 10 倍以上。Xgboost 和 GBDT 两者都是 boosting 方法，除了工程实现、解决问题上的一些差异外，最大的不同就是目标函数的定义。故本文将从数学原理和工程实现上进行介绍，并在最后介绍下 Xgboost 的优点。

1、数学原理

1）目标函数

我们知道 XGBoost 是由

个基模型组成的一个加法运算式：

其中

为第

个基模型，

为第

个样本的预测值。

损失函数可由预测值

与真实值

进行表示：

其中

为样本数量。

我们知道模型的预测精度由模型的偏差和方差共同决定，损失函数代表了模型的偏差，想要方差小则需要简单的模型，所以目标函数由模型的损失函数

与抑制模型复杂度的正则项

组成，所以我们有：

为模型的正则项，由于 XGBoost 支持决策树也支持线性模型，所以这里再不展开描述。

我们知道 boosting 模型是前向加法，以第

步的模型为例，模型对第

个样本

的预测为：

其中

由第

步的模型给出的预测值，是已知常数，

是我们这次需要加入的新模型的预测值，此时，目标函数就可以写成：

求此时最优化目标函数，就相当于求解

。

泰勒公式是将一个在

处具有

阶导数的函数

利用关于

的

次多项式来逼近函数的方法，若函数

在包含

的某个闭区间

上具有

阶导数，且在开区间

上具有

阶导数，则对闭区间

上任意一点

有

，其中的多项式称为函数在

处的泰勒展开式，

是泰勒公式的余项且是

的高阶无穷小。

根据泰勒公式我们把函数

在点

处进行泰勒的二阶展开，可得到如下等式：

我们把

视为

，

视为

，故可以将目标函数写为：

其中

为损失函数的一阶导，

为损失函数的二阶导，注意这里的导是对

求导。

我们以平方损失函数为例：

则：

由于在第

步时

其实是一个已知的值，所以

是一个常数，其对函数的优化不会产生影响，因此目标函数可以写成：

所以我们只需要求出每一步损失函数的一阶导和二阶导的值（由于前一步的

是已知的，所以这两个值就是常数），然后最优化目标函数，就可以得到每一步的

，最后根据加法模型得到一个整体模型。

2）基于决策树的目标函数

我们知道 Xgboost 的基模型不仅支持决策树，还支持线性模型，这里我们主要介绍基于决策树的目标函数。

我们可以将决策树定义为

，

为某一样本，这里的

代表了该样本在哪个叶子结点上，而

则代表了叶子结点取值

，所以

就代表了每个样本的取值

（即预测值）。

决策树的复杂度可由叶子数

组成，叶子节点越少模型越简单，此外叶子节点也不应该含有过高的权重

（类比 LR 的每个变量的权重），所以目标函数的正则项可以定义为：

即决策树模型的复杂度由生成的所有决策树的叶子节点数量，和所有节点权重所组成的向量的

范式共同决定。

这张图给出了基于决策树的 XGBoost 的正则项的求解方式。

我们设

为第

个叶子节点的样本集合，故我们的目标函数可以写成：

第二步到第三步可能看的不是特别明白，这边做些解释：第二步是遍历所有的样本后求每个样本的损失函数，但样本最终会落在叶子节点上，所以我们也可以遍历叶子节点，然后获取叶子节点上的样本集合，最后在求损失函数。即我们之前样本的集合，现在都改写成叶子结点的集合，由于一个叶子结点有多个样本存在，因此才有了

和

这两项，

为第

个叶子节点取值。

为简化表达式，我们定义

，

，则目标函数为：

这里我们要注意

和

是前

步得到的结果，其值已知可视为常数，只有最后一棵树的叶子节点

不确定，那么将目标函数对

求一阶导，并令其等于

，则可以求得叶子结点

对应的权值：

所以目标函数可以化简为：

上图给出目标函数计算的例子，求每个节点每个样本的一阶导数

和二阶导数

，然后针对每个节点对所含样本求和得到的

和

，最后遍历决策树的节点即可得到目标函数。

3）最优切分点划分算法

在决策树的生长过程中，一个非常关键的问题是如何找到叶子的节点的最优切分点，Xgboost 支持两种分裂节点的方法——贪心算法和近似算法。

A.贪心算法

从深度为的树开始，对每个叶节点枚举所有的可用特征；
针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；
选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集
回到第 1 步，递归执行到满足特定条件为止

那么如何计算每个特征的分裂收益呢？

假设我们在某一节点完成特征分裂，则分列前的目标函数可以写为：

分裂后的目标函数为：

则对于目标函数来说，分裂后的收益为：

注意该特征收益也可作为特征重要性输出的重要依据。

对于每次分裂，我们都需要枚举所有特征可能的分割方案，如何高效地枚举所有的分割呢？

我假设我们要枚举所有

这样的条件，对于某个特定的分割点

我们要计算

左边和右边的导数和。

我们可以发现对于所有的分裂点

，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和

和

。然后用上面的公式计算每个分割方案的分数就可以了。

观察分裂后的收益，我们会发现节点划分不一定会使得结果变好，因为我们有一个引入新叶子的惩罚项，也就是说引入的分割带来的增益如果小于一个阀值的时候，我们可以剪掉这个分割。

B.近似算法

贪婪算法可以的到最优解，但当数据量太大时则无法读入内存进行计算，近似算法主要针对贪婪算法这一缺点给出了近似最优解。

对于每个特征，只考察分位点可以减少计算复杂度。

该算法会首先根据特征分布的分位数提出候选划分点，然后将连续型特征映射到由这些候选点划分的桶中，然后聚合统计信息找到所有区间的最佳分裂点。

在提出候选切分点时有两种策略：

Global：学习每棵树前就提出候选切分点，并在每次分裂时都采用这种分割；
Local：每次分裂前将重新提出候选切分点。

直观上来看，Local 策略需要更多的计算步骤，而 Global 策略因为节点没有划分所以需要更多的候选点。

下图给出不同种分裂策略的 AUC 变换曲线，横坐标为迭代次数，纵坐标为测试集 AUC，eps 为近似算法的精度，其倒数为桶的数量。

我们可以看到 Global 策略在候选点数多时（eps 小）可以和 Local 策略在候选点少时（eps 大）具有相似的精度。此外我们还发现，在 eps 取值合理的情况下，分位数策略可以获得与贪婪算法相同的精度。

第一个 for 循环：对特征 k 根据该特征分布的分位数找到切割点的候选集合。XGBoost 支持 Global 策略和 Local 策略。
第二个 for 循环：针对每个特征的候选集合，将样本映射到由该特征对应的候选点集构成的分桶区间中，即，对每个桶统计值，最后在这些统计量上寻找最佳分裂点。

下图给出近似算法的具体例子，以三分位为例：

根据样本特征进行排序，然后基于分位数进行划分，并统计三个桶内的

值，最终求解节点划分的增益。

4）加权分位数缩略图

事实上， XGBoost 不是简单地按照样本个数进行分位，而是以二阶导数值

作为样本的权重进行划分，如下：

那么问题来了：为什么要用

进行样本加权？

我们知道模型的目标函数为：

我们稍作整理，便可以看出

有对 loss 加权的作用。

其中

与

皆为常数。我们可以看到

就是平方损失函数中样本的权重。

对于样本权值相同的数据集来说，找到候选分位点已经有了解决方案（GK 算法），但是当样本权值不一样时，该如何找到候选分位点呢？（作者给出了一个 Weighted Quantile Sketch 算法，这里将不做介绍。）

5）稀疏感知算法

在决策树的第一篇文章中我们介绍 CART 树在应对数据缺失时的分裂策略，XGBoost 也给出了其解决方案。

XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支，其实很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。

在构建树的过程中需要枚举特征缺失的样本，乍一看该算法的计算量增加了一倍，但其实该算法在构建树的过程中只考虑了特征未缺失的样本遍历，而特征值缺失的样本无需遍历只需直接分配到左右节点，故算法所需遍历的样本量减少，下图可以看到稀疏感知算法比 basic 算法速度块了超过 50 倍。

2、工程实现

1）块结构设计

我们知道，决策树的学习最耗时的一个步骤就是在每次寻找最佳分裂点是都需要对特征的值进行排序。而 XGBoost 在训练之前对根据特征对数据进行了排序，然后保存到块结构中，并在每个块结构中都采用了稀疏矩阵存储格式（Compressed Sparse Columns Format，CSC）进行存储，后面的训练过程中会重复地使用块结构，可以大大减小计算量。

每一个块结构包括一个或多个已经排序好的特征；
缺失特征值将不进行排序；
每个特征会存储指向样本梯度统计值的索引，方便计算一阶导和二阶导数值；

这种块结构存储的特征之间相互独立，方便计算机进行并行计算。在对节点进行分裂时需要选择增益最大的特征作为分裂，这时各个特征的增益计算可以同时进行，这也是 Xgboost 能够实现分布式或者多线程计算的原因。

2）缓存访问优化算法

块结构的设计可以减少节点分裂时的计算量，但特征值通过索引访问样本梯度统计值的设计会导致访问操作的内存空间不连续，这样会造成缓存命中率低，从而影响到算法的效率。

为了解决缓存命中率低的问题，XGBoost 提出了缓存访问优化算法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就是实现了非连续空间到连续空间的转换，提高了算法效率。

此外适当调整块大小，也可以有助于缓存优化。

3、“核外”块计算

当数据量过大时无法将数据全部加载到内存中，只能先将无法加载到内存中的数据暂存到硬盘中，直到需要时再进行加载计算，而这种操作必然涉及到因内存与硬盘速度不同而造成的资源浪费和性能瓶颈。为了解决这个问题，XGBoost 独立一个线程专门用于从硬盘读入数据，以实现处理数据和读入数据同时进行。

此外，XGBoost 还用了两种方法来降低硬盘读写的开销：

块压缩：对 Block 进行按列压缩，并在读取时进行解压；
块拆分：将每个块存储到不同的磁盘中，从多个磁盘读取可以增加吞吐量。

3、优缺点

1）优点

精度更高：GBDT 只用到一阶泰勒展开，而 XGBoost 对损失函数进行了二阶泰勒展开。XGBoost 引入二阶导一方面是为了增加精度，另一方面也是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数；
灵活性更强：GBDT 以 CART 作为基分类器，XGBoost 不仅支持 CART 还支持线性分类器，（使用线性分类器的 XGBoost 相当于带 L1 和 L2 正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题））。此外，XGBoost 工具支持自定义损失函数，只需函数支持一阶和二阶求导；
正则化：XGBoost 在目标函数中加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、叶子节点权重的 L2 范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合；
Shrinkage（缩减）：相当于学习速率。XGBoost 在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间；
列抽样：XGBoost 借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算；
缺失值处理：XGBoost 采用的稀疏感知算法极大的加快了节点分裂的速度；
可以并行化操作：块结构可以很好的支持并行计算。

2）缺点

虽然利用预排序和近似算法可以降低寻找最佳分裂点的计算量，但在节点分裂过程中仍需要遍历数据集；
预排序过程的空间复杂度过高，不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引，相当于消耗了两倍的内存。

LightGBM

LightGBM 由微软提出，主要用于解决 GDBT 在海量数据中遇到的问题，以便其可以更好更快地用于工业实践中。

从 LightGBM 名字我们可以看出其是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。下图分别显示了 XGBoost、XGBoost_hist（利用梯度直方图的 XGBoost）和 LightGBM 三者之间针对不同数据集情况下的内存和训练时间的对比：

那么 LightGBM 到底如何做到更快的训练速度和更低的内存使用的呢？

我们刚刚分析了 XGBoost 的缺点，LightGBM 为了解决这些问题提出了以下几点解决方案：

单边梯度抽样算法；
直方图算法；
互斥特征捆绑算法；
基于最大深度的 Leaf-wise 的垂直生长算法；
类别特征最优分割；
特征并行和数据并行；
缓存优化。

本节将继续从数学原理和工程实现两个角度介绍 LightGBM。

1、数学原理

1）单边梯度抽样算法

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。

GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。具体算法如下所示：

我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序（无需保存排序后结果），然后拿到前 a% 的梯度大的样本，和总体样本的 b%，在计算增益时，通过乘上

来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

2）直方图算法

A.直方图算法

直方图算法的基本思想是将连续的特征离散化为 k 个离散特征，同时构造一个宽度为 k 的直方图用于统计信息（含有 k 个 bin）。利用直方图算法我们无需遍历数据，只需要遍历 k 个 bin 即可找到最佳分裂点。

我们知道特征离散化的具有很多优点，如存储方便、运算更快、鲁棒性强、模型更加稳定等等。对于直方图算法来说最直接的有以下两个优点（以 k=256 为例）：

内存占用更小：XGBoost 需要用 32 位的浮点数去存储特征值，并用 32 位的整形去存储索引，而 LightGBM 只需要用 8 位去存储直方图，相当于减少了 1/8；
计算代价更小：计算特征分裂增益时，XGBoost 需要遍历一次数据找到最佳分裂点，而 LightGBM 只需要遍历一次 k 次，直接将时间复杂度从降低到，而我们知道。

虽然将特征离散化后无法找到精确的分割点，可能会对模型的精度产生一定的影响，但较粗的分割也起到了正则化的效果，一定程度上降低了模型的方差。

B.直方图加速

在构建叶节点的直方图时，我们还可以通过父节点的直方图与相邻叶节点的直方图相减的方式构建，从而减少了一半的计算量。在实际操作过程中，我们还可以先计算直方图小的叶子节点，然后利用直方图作差来获得直方图大的叶子节点。

C.稀疏特征优化

XGBoost 在进行预排序时只考虑非零值进行加速，而 LightGBM 也采用类似策略：只用非零特征构建直方图。

3）互斥特征捆绑算法

高维特征往往是稀疏的，而且特征间可能是相互排斥的（如两个特征不同时取非零值），如果两个特征并不完全互斥（如只有一部分情况下是不同时取非零值），可以用互斥率表示互斥程度。互斥特征捆绑算法（Exclusive Feature Bundling, EFB）指出如果将一些特征进行融合绑定，则可以降低特征数量。

针对这种想法，我们会遇到两个问题：

哪些特征可以一起绑定？
特征绑定后，特征值如何确定？

对于问题一：EFB 算法利用特征和特征间的关系构造一个加权无向图，并将其转换为图着色算法。我们知道图着色是个 NP-Hard 问题，故采用贪婪算法得到近似解，具体步骤如下：

构造一个加权无向图，顶点是特征，边是两个特征间互斥程度；
根据节点的度进行降序排序，度越大，与其他特征的冲突越大；
遍历每个特征，将它分配给现有特征包，或者新建一个特征包，是的总体冲突最小。

算法允许两两特征并不完全互斥来增加特征捆绑的数量，通过设置最大互斥率

来平衡算法的精度和效率。EFB 算法的伪代码如下所示：

我们看到时间复杂度为

，在特征不多的情况下可以应付，但如果特征维度达到百万级别，计算量则会非常大，为了改善效率，我们提出了一个更快的解决方案：将 EFB 算法中通过构建图，根据节点度来排序的策略改成了根据非零值的技术排序，因为非零值越多，互斥的概率会越大。

对于问题二：论文给出特征合并算法，其关键在于原始特征能从合并的特征中分离出来。假设 Bundle 中有两个特征值，A 取值为 [0, 10]、B 取值为 [0, 20]，为了保证特征 A、B 的互斥性，我们可以给特征 B 添加一个偏移量转换为 [10, 30]，Bundle 后的特征其取值为 [0, 30]，这样便实现了特征合并。具体算法如下所示：

4）带深度限制的 Leaf-wise 算法

在建树的过程中有两种策略：

Level-wise：基于层进行生长，直到达到停止条件；
Leaf-wise：每次分裂增益最大的叶子节点，直到达到停止条件。

XGBoost 采用 Level-wise 的增长策略，方便并行计算每一层的分裂节点，提高了训练速度，但同时也因为节点增益过小增加了很多不必要的分裂，降低了计算量；LightGBM 采用 Leaf-wise 的增长策略减少了计算量，配合最大深度的限制防止过拟合，由于每次都需要计算增益最大的节点，所以无法并行分裂。

5）类别特征最优分割

大部分的机器学习算法都不能直接支持类别特征，一般都会对类别特征进行编码，然后再输入到模型中。常见的处理类别特征的方法为 one-hot 编码，但我们知道对于决策树来说并不推荐使用 one-hot 编码：

会产生样本切分不平衡问题，切分增益会非常小。如，国籍切分后，会产生是否中国，是否美国等一系列特征，这一系列特征上只有少量样本为 1，大量样本为 0。这种划分的增益非常小：较小的那个拆分样本集，它占总样本的比例太小。无论增益多大，乘以该比例之后几乎可以忽略；较大的那个拆分样本集，它几乎就是原始的样本集，增益几乎为零；
影响决策树学习：决策树依赖的是数据的统计信息，而独热码编码会把数据切分到零散的小空间上。在这些零散的小空间上统计信息不准确的，学习效果变差。本质是因为独热码编码之后的特征的表达能力较差的，特征的预测能力被人为的拆分成多份，每一份与其他特征竞争最优划分点都失败，最终该特征得到的重要性会比实际值低。

LightGBM 原生支持类别特征，采用 many-vs-many 的切分方式将类别特征分为两个子集，实现类别特征的最优切分。假设有某维特征有 k 个类别，则有

中可能，时间复杂度为

，LightGBM 基于 Fisher 大佬的《On Grouping For Maximum Homogeneity》实现了

的时间复杂度。

上图为左边为基于 one-hot 编码进行分裂，后图为 LightGBM 基于 many-vs-many 进行分裂，在给定深度情况下，后者能学出更好的模型。

其基本思想在于每次分组时都会根据训练目标对类别特征进行分类，根据其累积值

对直方图进行排序，然后在排序的直方图上找到最佳分割。此外，LightGBM 还加了约束条件正则化，防止过拟合。

我们可以看到这种处理类别特征的方式使得 AUC 提高了 1.5 个点，且时间仅仅多了 20%。

2、工程实现

1）特征并行

传统的特征并行算法在于对数据进行垂直划分，然后使用不同机器找到不同特征的最优分裂点，基于通信整合得到最佳划分点，然后基于通信告知其他机器划分结果。

传统的特征并行方法有个很大的缺点：需要告知每台机器最终划分结果，增加了额外的复杂度（因为对数据进行垂直划分，每台机器所含数据不同，划分结果需要通过通信告知）。

LightGBM 则不进行数据垂直划分，每台机器都有训练集完整数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。

2）数据并行

传统的数据并行策略主要为水平划分数据，然后本地构建直方图并整合成全局直方图，最后在全局直方图中找出最佳划分点。

这种数据划分有一个很大的缺点：通讯开销过大。如果使用点对点通信，一台机器的通讯开销大约为

；如果使用集成的通信，则通讯开销为

，

LightGBM 采用分散规约（Reduce scatter）的方式将直方图整合的任务分摊到不同机器上，从而降低通信代价，并通过直方图做差进一步降低不同机器间的通信。

3）投票并行

针对数据量特别大特征也特别多的情况下，可以采用投票并行。投票并行主要针对数据并行时数据合并的通信代价比较大的瓶颈进行优化，其通过投票的方式只合并部分特征的直方图从而达到降低通信量的目的。

大致步骤为两步：

本地找出 Top K 特征，并基于投票筛选出可能是最优分割点的特征；
合并时只合并每个机器选出来的特征。

4）缓存优化

上边说到 XGBoost 的预排序后的特征是通过索引给出的样本梯度的统计值，因其索引访问的结果并不连续，XGBoost 提出缓存访问优化算法进行改进。

而 LightGBM 所使用直方图算法对 Cache 天生友好：

首先，所有的特征都采用相同的方法获得梯度（区别于不同特征通过不同的索引获得梯度），只需要对梯度进行排序并可实现连续访问，大大提高了缓存命中；
其次，因为不需要存储特征到样本的索引，降低了存储消耗，而且也不存在 Cache Miss的问题。

3、与 XGBoost 的对比

本节主要总结下 LightGBM 相对于 XGBoost 的优点，从内存和速度两方面进行介绍。

1）内存更小

XGBoost 使用预排序后需要记录特征值及其对应样本的统计值的索引，而 LightGBM 使用了直方图算法将特征值转变为 bin 值，且不需要记录特征到样本的索引，将空间复杂度从降低为，极大的减少了内存消耗；
LightGBM 采用了直方图算法将存储特征值转变为存储 bin 值，降低了内存消耗；
LightGBM 在训练过程中采用互斥特征捆绑算法减少了特征数量，降低了内存消耗。

2）速度更快

LightGBM 采用了直方图算法将遍历样本转变为遍历直方图，极大的降低了时间复杂度；
LightGBM 在训练过程中采用单边梯度算法过滤掉梯度小的样本，减少了大量的计算；
LightGBM 采用了基于 Leaf-wise 算法的增长策略构建树，减少了很多不必要的计算量；
LightGBM 采用优化后的特征并行、数据并行方法加速计算，当数据量非常大的时候还可以采用投票并行的策略；
LightGBM 对缓存也进行了优化，增加了 Cache hit 的命中率。

参考文献：

《机器学习》周志华，
《数据挖掘十大算法》吴信东
CART 树怎么进行剪枝?，zhihu.com/question/22697086
机器学习算法中 GBDT 与 Adaboost 的区别与联系是什么？- Frankenstein 的回答 - 知乎，https://www.zhihu.com/question/54626685/answer/140610056
为什么说bagging是减少variance，而boosting是减少bias，https://www.zhihu.com/question/26760839
Ensemble Learning - 周志华，https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/springerEBR09.pdf
使用sklearn进行集成学习——理论，https://www.cnblogs.com/jasonfreak/p/5657196.html
《XGBoost: A Scalable Tree Boosting System》，https://arxiv.org/pdf/1603.02754.pdf
陈天奇论文演讲 PPT，https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
LightGBM: A Highly Efficient Gradient Boosting Decision Tree，https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf
LightGBM 文档，https://lightgbm.readthedocs.io/en/latest/
论文阅读——LightGBM 原理，https://www.biaodianfu.com/lightgbm.html
机器学习算法之 LightGBM，https://blog.csdn.net/shine19930820/article/details/79123216
关于sklearn中的决策树是否应该用one-hot编码？- 柯国霖的回答 - 知乎，https://www.zhihu.com/question/266195966/answer/306104444
如何玩转LightGBM，https://v.qq.com/x/page/k0362z6lqix.html
A Communication-Efficient Parallel Algorithm for Decision Tree， http://papers.nips.cc/paper/6381-a-communication-efficient-parallel-algorithm-for-decision-tree

本文首发于知乎：

【机器学习】决策树（上）——ID3、C4.5、CART（非常详细），https://zhuanlan.zhihu.com/p/85731206
【机器学习】决策树（中）——Random Forest、Adaboost、GBDT （非常详细），https://zhuanlan.zhihu.com/p/86263786
【机器学习】决策树（下）——XGBoost、LightGBM（非常详细），https://zhuanlan.zhihu.com/p/87885678

ACL 2020原定于2020年7月5日至10日在美国华盛顿西雅图举行，因新冠肺炎疫情改为线上会议。为促进学术交流，方便国内师生提早了解自然语言处理（NLP）前沿研究，AI 科技评论将推出「ACL 实验室系列论文解读」内容，同时欢迎更多实验室参与分享，敬请期待！

点击"阅读原文"，直达“ACL 交流小组”了解更多会议信息。

登录查看更多