文 | Jin.Zhang

来自数据算法（gh_e67de4d10fad）

0. 前言

虽然近年深度学习的使用越来越广泛，但是在小数据集上树模型表现往往会更加优秀，也是中小规模数据集上首选使用的模型。理论上使用树模型可以对特征空间进行无限划分，同时可以加入反映树复杂度的正则项、剪枝策略等防止过拟合，因此通过参数调整权衡方差与偏差，可以得到较优的精度。

单一的树模型不太常用，提度提升树GBDT是一种精度更高的基于树的组合模型。XGBoost在GBDT的基础上，对目标函数增加了二阶泰勒展开项，同时加入了正则项，是一个更高效、更高精度的树模型实现框架。LightGBM是软微2017年开源的相比XGBoost具有更快速度的树模型。CatBoost是俄罗期Yandex公司开源的另一个实现框架，有自己的特色。

本文将从GBDT开始逐渐展开依次介绍这三个开源框架的实现原理以及各自主要的特点，并且通过我们业务数据上的实验对比三个框架的性能以及精度。

1. XGBoost介绍

XGBoost是在原始GBDT的基础上一步一步改进而来，不管是算法的优化还是系统实现都非常优秀。在速度以及精度上均比传统的GBDT表现更好。

1.1 GBDT实现方式

传统的GBDT是一种基于Boosting的加性模型，基模型是CART。CART最终结果是多颗CART的结论之和，因此学习过程是依次学习每一颗树。每颗树的学习方向是目标函数在当前已学到模型的梯度方向。整体框架还是基于Gradient Boosting：

GBDT的每一次迭代都是学习一颗CART树，每一颗CART学习的方向则是：

。

对应以上框架，以L2loss为例：

第一步，求解初始模型

:

即初始值设为所有样本label的均值。

第二步，求梯度：

因此，在GBDT以损失函数为L2loss的回归模型中，下一颗树的学习方向就是

了。

1.2 XGBoost原理

相比于GBDT，XGBoost对目标函数进行了二阶泰勒展开，再对二次展开式求极值得到下棵树要学习的目标：

其中：

引入正则项：

其中，T：树的叶子数量，

：第i个叶子的权重。对目标函数加入正则项后，将按样本加和的目标函数转换成按叶子加和：

对于转换后的目标函数，取极小值时有：

其中w为叶子的权重，Obj为取极小值时目标函数的值。

分裂增益的计算为：分裂之前目标函数的值减去分裂之后目标函数的值：

有了目标函数以及分裂增益计算公式，然后就是遍历每一个特征，寻找最佳分裂阈值：

1.3 XGBoost的并行化加速

虽然Boosting是一种串行的学习框架，但是树模型学习过程的主要计算消耗在特征及分裂阈值的计算上。XGBoost的并行方式则主要是在计算分裂阈值时，分多个线程，每个线程分配一部分的特征进行计算，然后再将所有线程的计算结果取分裂增益最大的特征及阈值进行树的生长。

2. LightGBM介绍

LightGBM由微软于2017年开源。借鉴了许多XGBoost的实现方法，如目标函数的二阶泰勒展开、树叶子节点值的计算、树复杂度表达等。但是在此基础上，LightGBM采用了直方图加速方法以及Leafwise的树生长方式，因此在训练速度方面表现比XGBoost更加卓越，同时训练精度与能保持相当水平。

2.1 直方图加速

在传统GBDT和XGBoost中(后来也支持特征直方图)采用的是特征预排序再寻找分裂阈值的方式，LightGBM中则是首先对特征进行分桶并构建直方图，然后在直方图的基础上来进行后面的分裂计算。

以上为预排序的方式计算分裂阈值。在数据预处理阶段会按特征值的排序建立索引，然后按照索引依次遍历每一个阈值，进行分裂增益的计算。可以看出这种方式的时间复杂度为O(#data)。

采用直方图的方式，会在预处理阶段对特征值进行分桶。特征分桶处理后，只需要遍历每一个桶，分桶后的计算时间复杂度为O(#bins)。分桶操作后，可能找到的不是最优的分裂阈值，但是一个优点是能降低过拟合的风险。可见，采用特征分桶然后再进行寻找分裂阈值能够大大减小时间复杂度。

在对一个叶子进行分裂之后，需要重新计算其两个孩子节点的直方图(直方图每一个桶保存的是落到该桶的样本数量、样本一阶导数之和、样本二阶导数之和)。直方图作差如下图所示，指只需要计算样本较少的孩子节点的特征直方图，然后将父节点的特征直方图减去小孩子节点的直方图，就得到大孩子节点的直方图，如此计算只需要遍历小叶子上的样本，从而达到加速的目的。

2.2 树的生长方式

XGBoost和传统的GBDT采用Levelwise的树生长方式，这种生长方式对当前层的所有叶子均进行分裂，而不考虑新生成的叶子和当前层未分裂的叶子的分裂增益大小，因此这种贪心方法还不够“贪心”。LightGBM采用的是Leafwise的树生长方式，通过计算当前树的所有叶子的分裂增益，选择最大分裂增益的叶子进行分裂，理论上Leafwise相比于Levelwise每次分裂可能会产生更大的增益，因此拟合速度更快。Levelwise和Leafwise见下图所示。

Levelwise是对当前层所有叶子进行分裂，Leafwise则是对当前所有叶子找出分裂增益最大的叶子，然后进行分裂生长。

2.3 category特征处理

一般在使用树模型或者线性模型时都要对category特征进行onehot处理，特征的处理过程需要消耗时间，onehot之后的特征要么占用更大的存储空间，要么采用稀疏格式存储。在LightGBM中可以直接使用category特征，得到的结果和采用onehot前处理是一致的。

上图表示category特征和onehot之后的特征，右图为onehot之后的分裂以及直接使用category的分裂。

2.4 缺失值处理

LightGBM对缺失值可以自动处理，在计算分裂增益的过程中，当前特征为缺失值的样本先放到左叶子计算分裂增益，然后再放到右叶子计算分裂增益，从中选择增益更大的方式进行分裂。从而得到缺失值是往左或者往右分裂。

2.5 分布式网络通信

XGBoost的分布式训练中，采用的是基于tree算法的AllReduce数据同步方式。LightGBM则根据不同步骤的特点，分别采用基于Recursive Doubling的AllReduce以及基于Recursive Halving算法的ReduceScatter进行数据同步[3]，可以使通信更加高效。

3. CatBoost介绍

CatBoost同样是基于Boosting tree的梯度提升树模型框架，最大的特点对category特征的直接支持，甚至支持字符串类型的特征。

3.1 category的处理

CatBoost对category特征的处理与LightGBM不同，是按照如下方式转换成数值类型：

a. 将训练样本随机重新排序

b. 将label值转化为整型

对于regression：将label映射到k个桶中并用桶号来代替label，取值为[0, k-1]。

对于Classification：正/负样本用1/0表示。

对于MutiClassification：k类编码为[0, k-1]。

c. 转换特征值

依次遍历每一个样本，按如下公式将category特征转换为数据型：

其中：

：转换后的数值

：平滑因子

：遍历到当前样本，与当前样本label相同的样本总数量

：遍历到当前样本的总样本数量

4. 实验

为对比三个树模型框架的性能，在我们业务的数据上做了相关实验。训练数据为1000w样本量，测试数据为10w的样本量。实验结果如下：

从实验的结论来看，在精度方面基本差不多，但在速度上CatBoost表现最差，LightGBM表现最优。