本文主要对决策树、gbdt、xgboost、lightgbm、catboost进行简述和整理，包括模型原理、优劣性等内容

1.决策树

决策树是一种通过对历史数据进行测算，对新数据进行分类和预测的算法，以此为依据，对新产生的数据结果进行预测的机器学习方法，由3个主要部分组成，分别为决策节点，分支和叶子节点，具体定义与数据结构中的树基本相同
构建决策树的方法有很多种，其中ID3、C4.5、CART树的构建方法比较常见，

决策树构建方法	支持模型	树结构	连续值处理	缺失值处理	剪枝	特征选择	原理
ID3	分类	多叉树	不支持	不支持	不支持	信息增益	用信息熵减条件熵得到信息增益，信息增益越大，说明使用此特征分类的信息“纯度”提升越大
C4.5	分类	多叉树	支持	支持	支持	信息增益率	用信息增益除以分支数的信息熵，用以解决信息增益下出现的分支数越多，信息增益偏向越大的问题
CART	分类 回归	二叉树	支持	支持	支持	基尼系数 均方差	从数据集中抽取两个样本不一样的概率，基尼系数越小，数据集的纯度越高

1.1 CART分类树

算法输入是训练集D，基尼系数的阈值，样本个数阈值
输出是决策树T
算法从根节点开始，用训练集递归的建立CART树
具体如下：
1.对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归
2.计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归
3.计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值都是寻找最佳切分点，通过计算基尼系数进行比较
4.在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2
5. 对左右的子节点递归的调用1-4步，生成决策树
6. 在预测阶段，加入样本a落入某个叶子节点中，节点里有多个训练样本，对于样本a的类别概率使用的是这个叶子节点里概率最大的类别，概率值为叶子中最大类别的数目/所有样本数目

1.2 CART回归树

算法输入是训练集D，均方差的阈值，样本个数阈值
输出是决策树T
算法从根节点开始，用训练集递归的建立CART树
具体如下：
1.对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归
2.计算样本集D的均方差，如果均方差小于阈值，则返回决策树子树，当前节点停止递归
3.计算当前节点现有的各个特征的各个特征值对数据集D的均方差，对于离散值和连续值都是寻找最佳切分点，通过计算均方差进行比较
4.在计算出来的各个特征的各个特征值对数据集D的均方差中，选择均方差最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2
5. 对左右的子节点递归的调用1-4步，生成决策树
6. 在预测阶段，加入样本a落入某个叶子节点中，节点里有多个训练样本，对于样本a的预测值使用的是这个叶子节点里各个训练样本的均值或者中位值

2.gbdt

GBDT是集成学习boosting的方法，可以看做是N棵树组成的加法模型，对应的公式如下：

x表示输入样本，c表示每棵决策树，I表示每棵树的权重
算法实现过程如下：
输入：训练数据集T，损失函数为L
输出：回归树F(x)
1.初始化
估计使损失函数极小化的常数值，它是只有一个根节点的树，一般平方损失函数为节点的均值，绝对损失函数为节点样本的中位数

2.对m=1,2…M(m表示迭代次数，即生成的弱学习器个数)
(a)对样本i=1,2…,N，计算损失函数的负梯度在当前模型的值，将它作为残差的估计，对于平方损失函数，它就是所说的残差，对于一般损失函数，就是残差的近似值

(b)对于输入样本拟合一个回归书，得到第m棵树的叶节点区域Rj，j表示每棵树的叶节点个数
©对j=1,2…J，利用线性搜索，估计叶节点区域的值，使损失函数最小化，计算

(d)更新

(3)得到最终的回归树

注：对于gbdt分类算法，损失函数为log损失，残差为真实label - softmax后输出的值

3.xgboost

xgboost官方文档
xgboost是一种level-wise生长策略的集成树模型，相比于比较容易过拟合的gbdt，做了一些工作，具体如下
目标函数：

将目标函数进行泰勒展开，取前三阶，移除高阶小项，转化为如下函数：

上式中的第一项表示损失误差，第二项是正则项，控制树的负责督，防止过拟合
最优切分点分割算法

4.lightgbm

LightGBM 中文文档
lightgbm是一个基于leaf-wise的集成决策树模型，相比于xgboost，在速度上和内存消耗上有极大的改进，精度基本与xgboost相同，甚至有时可以超过xgboost，具体工作如下
LightGBM = XGBoost + Histogram + GOSS + EFB，即lightgbm主要的工作改进有结合直方图算法，GOSS算法，EFB算法
直方图算法
直方图算法是替代XGBoost的预排序(pre-sorted)算法的。
预排序算法首先将样本按照特征取值排序，然后从全部特征取值中找到最优的分裂点位，该算法的候选分裂点数量与样本数量成正比。
而直方图算法通过将连续特征值离散化到固定数量(如255个)的bins上，使得候选分为点位为常数个(num_bins -1).
此外，直方图算法还能够作直方图差加速。当节点分裂成两个时，右边叶子节点的直方图等于其父节点的直方图减去左边叶子节点的直方图。从而大大减少构建直方图的计算量。

GOSS算法
GOSS算法全称为Gradient-based One-Side Sampling，即基于梯度的单边采样算法，主要思想是通过对样本采样的方法来减少计算目标函数增益时候的复杂度
如果对全部样本进行随机采样，势必会对目标函数增益的计算精度造成较大的影响，GOSS算法的创新之处在于它只对梯度绝对值较小的样本按照一定比例进行采样，而保留了梯度绝对值较大的样本，由于目标函数增益主要来自于梯度绝对值较大的样本，因此这种方法在计算性能和计算精度之间取得了很好的平衡
EFB算法
EFB算法全称是Exclusive Feature Bundling，即互斥特征绑定算法，EFB算法可以有效减少用于构建直方图的特征数量，从而降低计算复杂度，尤其是特征中包含大量稀疏特征的时候
在许多应用场景下，数据集中会有大量的稀疏特征，这些稀疏特征大部分样本都取值为0，只有少数样本取值非0，通常可以认为这些稀疏特征是互斥的，即它们几乎不会同时取非零值，利用这种特性，可以通过对某些特征的取值重新编码，将多个这样互斥的特征捆绑成为一个新的特征

5.模型对比

.XGBoost的优缺点
与GBDT对比
1.GBDT的基分类器只支持CART树，而XGBoost支持线性分类器，此时相当于带有L1和L2正则项的逻辑回归（分类问题）和线性回归（回归问题）
2.GBDT在优化时只使用了一阶倒数，而XGBoost对目标函数进行二阶泰勒展开，此外，XGBoost支持自定义损失函数，只要损失函数二阶可导
3.XGBoost借鉴随机森林算法，支持列抽样和行抽样，这样即能降低过拟合风险，又能降低计算。
4.XGBoost在目标函数中引入了正则项，正则项包括叶节点的个数及叶节点的输出值的L2范数。通过约束树结构，降低模型方差，防止过拟合。
5.XGBoost对缺失值不敏感，能自动学习其分裂方向
6.XGBoost在每一步中引入缩减因子，降低单颗树对结果的影响，让后续模型有更大的优化空间，进一步防止过拟合。
7.XGBoost在训练之前，对数据预先进行排序并保存为block，后续迭代中重复使用，减少计算，同时在计算分割点时，可以并行计算

与LightGBM对比
1.XGBoost采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低，但是不能找到最精确的数据分割点。同时，不精确的分割点可以认为是降低过拟合的一种手段。
2.LightGBM借鉴Adaboost的思想，对样本基于梯度采样，然后计算增益，降低了计算
3.LightGBM对列进行合并，降低了计算
4.XGBoost采样level-wise策略进行决策树的生成，同时分裂同一层的节点，采用多线程优化，不容易过拟合，但有些节点分裂增益非常小，没必要进行分割，这就带来了一些不必要的计算；LightGBM采样leaf-wise策略进行树的生成，每次都选择在当前叶子节点中增益最大的节点进行分裂，如此迭代，但是这样容易产生深度很深的树，产生过拟合，所以增加了最大深度的限制，来保证高效的同时防止过拟合。

6.参考文献

1.决策树算法原理(上)
2.决策树算法原理(下)
3.决策树分类和预测算法的原理及实现
4.梯度提升树(GBDT)原理小结
5.GBDT基本原理及算法描述
6.《Greedy Function Approximation：A Gradient Boosting Machine》
7.XGBoost原理
8.GDBT模型、XGBoost和LightGBM之间的区别与联系