3-6 决策树、CART树、GBDT、xgboost、lightgbm一些关键点梳理

1、决策树

2、CART树

2.1 CART分类树-输入样本特征；输出样本对应的类别(离散型)

2.2 CART回归树-输入样本特征；输出样本的回归值(连续型)

3、GBDT

3.1 提升树

3.2 GBDT

4、xgboost

4.1 损失函数及节点展开

4.2 精确贪心算法及相关近似算法

4.3 对于缺失值的处理和Shrinkage

4.4 系统设计（SYSTEM DESIGN）

5、lightgbm

5.1 Histogram直方图算法

5.2 GOSS, Gradient-based One-Side Sampling，基于梯度的单边采样算法

5.3 EFB算法，Exclusive Feature Bundling，互斥特征绑定算法

参考了以下资料

1、决策树

树的节点代表样本的集合，通过筛选特征，将特征空间划分为互不相交的样本集合。经典的分类树算法，主要有ID3、C4.5、CART树（CART分类树、CART回归树）

（1）ID3、C4.5重点在于如何选取最优特征对样本进行划分；

（2）CART树，二叉树的结构，涉及最优特征的选择以及该特征下最优划分点的选择。

ID3决策树：计算最大信息增益的特征，对样本进行划分；

C4.5决策树：计算最大信息增益率（也叫信息增益比）的特征，对样本进行划分。

ID3决策树、C4.5决策树输入为离散特征、输出为K分类的结果。

信息增益，也称集合D和特征A的互信息，公式： $g(D,A) = H(D) - H(D| A)$

其中，H(D)为当前集合的信息熵，信息熵越大说明信息不确定性越大，H(D|A)是特征A条件下集合D的信息熵（特征A下的条件熵）；信息熵衡量信息的不确定性，信息增益衡量特征A对D不确定性减少的程度。H(D|A)越小，g(D,A)越大，特征更有利于分类。

通过信息熵定义，K为分类任务的类别个数，计算样本集D的信息熵，计算公式如下：

$H(D) = -\sum_{k=1}^{K}\frac{\left | C_{k} \right |}{\left | D \right |}log\frac{\left | C_{k} \right |}{\left | D \right |}$

特征A下的D的条件熵计算如下：其中，A特征有n个取值，通过每个特征取值对D样本进行划分，然后计算各划分子集的信息熵和

$H(D|A) = \sum_{i=1}^{n}\frac{\left | D_{i} \right |}{\left | D \right |}H(D_{i})=-\sum_{i=1}^{n}\frac{\left | D_{i} \right |}{\left | D \right|}\sum_{k=1}^{K}\frac{\left | D_{ik} \right |}{\left | D_{i} \right |}log\frac{\left | D_{ik} \right |}{\left | D_{i} \right |}$

信息增益率的引入考虑到，信息增益相近的情况下，某特征类别情况过多的情况容易产生过拟合等问题。因此，除以特征取值在D下的信息熵，信息增益率计算如下，n为A特征下特征取值的个数：

$g_{R}(D,A) = \frac{g(D,A)}{H_{A}(D)},H_{A}(D)=-\sum_{i=1}^{n}\frac{\left | D_{i} \right |}{\left | D \right |}log\frac{\left | D_{i} \right |}{\left | D \right |}$

2、CART树

CART树，名字叫分类与回归树(classification and regression tree, CART)。是二叉树的结构，对于离散和连续特征，都可以将样本通过特征的取值，划分到左右两个集合中。因此，原则上需要计算每个特征下每个特征取值的情况，从而选择最优划分点以及对应的特征。CART分类树和CART回归树的展开方式略有不同。

2.1 CART分类树-输入样本特征；输出样本对应的类别(离散型)

CART分类树采用基尼指数作为划分条件，基尼指数越大说明不确定性越小，计算公式如下：

$Gini(D) = \sum_{i=1}^{K}p_{k}(1-p_{k})=1-\sum_{i=1}^{K}p_{k}^{2} = 1-\sum_{i=1}^{K}(\frac{\left | C_{k} \right |}{\left | D \right |})^{2}$ ，交叉熵是plogp,这里是p(1-p)

在特征A的条件下(特征取值a划分点下)，集合D的基尼指数定义如下，书上都写成Gini(D,A)，实际和H(D|A)的意思类似：

$Gini(D,A=a) = \frac{\left | D_{1} \right |}{\left | D \right |}Gini(D_{1}) + \frac{\left | D_{2} \right |}{\left | D \right |}Gini(D_{2}),D_{1}\epsilon D_{R(A<=a)},D_{2}\epsilon D_{R(A>a)}$

分类树最终叶子节点上，相同类别值最多的类别对应被划分集合的类别。

2.2 CART回归树-输入样本特征；输出样本的回归值(连续型)

CART回归树通过最小化损失函数的方式来选择划分点，每个叶子节点集合对应的预测值为使得被划分集合损失函数最小的回归值。CART回归树希望每个集合划分后，总损失函数值都能减小。

因此，选取最优特征及特征取值的划分点，如下：其中j代表特征，s代表特征的划分点，c1代表左子树使得左子树集合损失最小的回归值，c2代表右子树使得右子树集合损失最小的回归值

$\underset{j,s}{min} [\underset{c_{1}}{min}\sum_{x_{i}\epsilon R_{1(j,s)}}loss(y^{i},c_{1})+\underset{c_{2}}{min}\sum_{x_{i}\epsilon R_{2(j,s)}}loss(y^{i},c_{2})]$

里面的min求得左、右子树的损失最小以及c1、c2的值，外面的min保证求得整体最小损失值下的j和s。可以看出要算出候选的j、s的损失，需要先算出里面min的c1和c2。

如果 $loss(y^{i},c) = (y_{i}-c)^{2}$ 那么， $c_{m} = \frac{1}{N_{m}}\sum_{x_{i}\epsilon R_{m}(j,s)}y_{i}$

3、GBDT

提升树、GBDT相关内容在李航的统计机器学习书中，讲的很简明。由于GBDT是提升树的一种，因此先简介提升树。基本参照李航书中的内容，然后简明扼要的在提一下关键点。

3.1 提升树

提升树（boosting tree）就是boosting集成方法 + 基模型采用决策树。通过损失函数来度量模型拟合的好坏。希望每一次加入一棵决策树后，模型的预测值与标签的损失最小。

一般来说，对于分类问题，损失函数采用指数损失，基模型是二叉分类树；

对于回归问题，损失函数采用平方，基模型是二叉回归树。

当然损失函数也可以其他一般的形式。注意这里指的损失函数是指整个集成学习模型的损失

提升树的关键在于这个损失函数的最小值怎么求（或者如何逼近）的问题，往损失函数最小值方向逼近的数值，就是新加决策树的label。

采用平方误差损失的回归问题，每个树要拟合的值 = 残差 = - 梯度；这种情况每棵树要拟合的值就是当前模型和label的差，同时负梯度方向也意味着能够最快速到达损失函数最小值的方向。

但是，并不是所有损失函数都能满足这样的性质，一般来说损失最小值在哪里不容易求出。只能通过每次从负梯度方向走一点，一步一步靠近。于是就有了梯度提升树。

3.2 GBDT

GBDT每次让决策树拟合负梯度的数值，一点一点靠近损失函数的最小值。

下图也是李航书上的截图，以回归问题为例，核心步骤就大致为3步：

（1）每一轮先算负梯度即（a），作为回归树的label；

（2）然后，回归树有label就能根据回归树的训练得到，叶子节点上挂了样本的回归树即（b）；

（3）由于最终训练目的是让集成学习算法的损失最小，于是有了（c），算每个叶子节点上让损失最小的值作为这个节点的预测值。

两个看似很重要，但是又看似很傻的疑惑：

（1）（a）中每一步残差怎么求？

答：GBDT中用当前预测值下的负梯度值来计算，也就是说损失函数定了，当前预测值定了，损失函数求导后当前预测值代入，然后加个负号，就OK了。加负号是因为，要损失函数的最小化方向是一阶导（梯度）的负方向。

（2）（b）这一步的回归树怎么展开？回归树本身的损失函数和整体集成学习模型损失有什么关联吗？

答：可以看出如果按回归树展开（回归树的损失函数也就是回归树怎么展开其实没有硬性规定），回归树算出来叶子节点的预测值，未必和（c）算出来的一致。之所以算（c）这个式子，就是希望预测时候加上已经展开的回归树叶子节点的预测值，能让损失函数最小

这两个问题实际是希望大家有所思考，并过渡到后续xgboost是什么做的，（a）和（c）这两个式子要干的事情，能不能结合起来？

4、xgboost

xgboost采用CART回归树作为基分类器模型。上述已经介绍了GBDT的原理，那么：

（1）GBDT基分类器都是树模型，存在过拟合问题怎么办

（2）每个样本最终挂在回归树的叶子节点上面

（3）加上回归树叶子节点上面的预测值后，使得损失函数最小

GBDT每一步算负梯度后，用回归树展开叶子节点，而且回归树展开时每一个划分点上还要遍历样本算左右节点最优（回归树损失意义上的最优）的c1、c2。最终还是要算每个叶子节点在集成模型上损失值最小的节点预测值。回归树展开结果显然未必是最优的，可否直接建立样本划分和损失函数的关联呢？

通过样本-叶子节点-损失的方式，样本组成叶子节点，叶子节点预测值决定集成模型损失，将损失函数由基于样本的求和，转换成基于叶子节点的求和。然后求极值。通过样本划分计算损失函数的大小。

4.1 损失函数及节点展开

xgboost还在GBDT的损失函数上，加了正则化项，将损失函数近似为二阶泰勒展开，将目标函数（损失函数+正则化项）基于样本形式的求和，转换为基于叶子节点预测值的求和形式（下图第一行变为第四行），求得损失函数的极值。这里每个样本gi和hi是已知的

通过以上步骤就能将每个叶子节点样本集合的最小损失函数和叶子节点预测值Wj直接求得，通过划分点可直接得到划分以后两个区域的最小损失和。Gain衡量划分后损失函数减少量，Gain越大说明划分点越好。

4.2 精确贪心算法及相关近似算法

这里的划分点依旧需要暴力枚举，枚举每个特征下的每个特征取值的划分点。每个叶子节点递归的采用这个过程去划分叶子节点中的样本，作为左右两部分求损失和。直到停止条件，CART树最大深度限制、最大叶子节点数量限制、Gain小于一定阈值等

上图，算法1就是精确贪心算法，求每个树节点，每个特征下每个特征取值的划分，求Gain最大的那个划分点。但是，如果样本的特征维度过高、特征取值数量过多，展开效率还是很低。因此，在特征维度和特征取值这两方面进行筛选或取值的压缩，以减少计算量。

上图，算法2就是特征层面的近似算法，对树的每个节点或者每层节点展开时，只采样部分特征

对于特征数值方面的压缩，采用按比例分桶的策略，通过hi作为权重的按权划分，以及设置阈值等策略。同时，还有特征数值全局分桶策略（对树的每个节点采用同样的分桶策略）、局部策略（按层采用分桶策略）

4.3 对于缺失值的处理和Shrinkage

上图，为缺失值处理的方式，在某个特征下，部分样本没有特征的取值（但样本都是有gi和hi的），这是就把缺失值样本都放左边或者都放右边，比较Gain的大小

至于Shrinkage，就是每个基模型都会有个学习率，就如同神经网络中梯度下降的学习率（learning rate)

4.4 系统设计（SYSTEM DESIGN）

在系统设计方面，还有xgboost还在特征并行计算（设计了一种block结构）、cache优化和数据读取优化。充分利用了CPU、磁盘、内存、缓存的资源。多线程读取数据，并行处理特征

5、lightgbm

整体原理和xgboost相同，可见看到xgboost的计算量主要受三方面的影响：

（1）样本特征的取值个数

（2）样本的特征维度

（3）叶子节点上样本的数量

lightgbm分别从这每个方面有所优化。

5.1 Histogram直方图算法

对每个特征下的特征取值进行了合并，减少了特征取值的情况，减少了特征的划分点。

1、替代XGBoost的预排序算法
2、将连续的浮点特征值离散化成k个整数，同时构造一个宽度为k的直方图，即将连续特征值离散化到k个bins上（比如k=255）候选分裂点数量 = k-1
3、当遍历一次数据后，直方图累积了需要的统计量（同一个bin里面gi、hi求和），然后根据直方图的离散值，遍历寻找最优的分割点
4、XGBoost需要遍历所有离散化的值，LightGBM只要遍历k个直方图的值