白话梳理树模型——从决策树到lightGBM

本文仅为简单梳理树模型升级过程，尽量少牵扯到数学公式，用大白话来理解。

预备知识

熵，熵用来描述事件的不确定性，越随机熵值越大。

如何理解不确定性呢？假设现在有一个伯努利分布，p(0) = p(1) = 1/2，则这个分布的不确定性是最大的，因为我们抽样的时候完全无法确定抽样出来的那个数值的概率更大，两者都是1/2，所以不确定性在这里可以理解为某个事件发生的概率。我们再来看看熵值的公式：

对于一个伯努利其熵值为：
H(p) = -p(p)log(p) - (1-p)log(1-p)

为了验证我们上面提到的伯努利分布的某个事件发生概率为1/2时熵最大，将p=1/2代入上式得到的熵值与p=4/5时的熵值进行比较即可，可以得到
H(p=1/2) > H(p=4/5)。

当P等于4/5时，我们有很大的概率（80%）可以确定事件会发生，而p=1/2时，则完全无法确定事件是否会发生，因为发生不发生的概率相等，这就是事件发生的不确定性。也即熵值H(p=1/2) > H(p=4/5)可以得出p=4/5时，不确定性更小，能更方便的猜出事件是否会发生。

交叉熵
在深度学习中，最常见的loss函数即是交叉熵损失函数。我们从不确定性角度来理解交叉熵损失函数：我们训练模型的目标是要使得loss变小，即事件发生的不确定性变小，不确定性小就表示模型更能猜出正确类别了。

决策树

树模型作为一种简单易理解的方式，其训练过程即是通过简单if/else来将所有的样本划分到其对应的叶子中。

ID3决策树

ID3决策树使用信息增益来作为特征选择标准，每次选择信息增益最大的特征。需要注意的是ID3是一颗多叉树，因此他总是倾向于选择特征值更多的特征来进行分裂。如何理解呢？

一个极端的例子，假设我们以人的DNA为特征来对训练集中的人群进行分类，毫无疑问的，只需要这一个特征（每个样本一个特征值）且只要这一次分裂就可以将所有人分开，因为每个人的DNA是唯一的，因此每一个人都是一个叶子结点。但是这个时候如果我们想要预测测试集怎么办？测试集中的人群DNA在训练集中没出现过，因此模型无法对测试集进行正确预测。也就是发生了我们常常说的过拟合现象。

白话信息增益：信息增益可以理解为在得知了额外的信息后事件发生不确定性的减少量。譬如我们想知道明天是否会下雨，如果我们在一个黑房子里面则什么信息都收不到，但是当我们走出房门，发现天气闷热，蚂蚁搬家蛇过道这些额外信息（即特征）后我们就可以很大概率说明天会下雨了。同时我们也知道了特朗普竞选总统失败（特征），但是这个对于明天是否下雨是无关的，无法帮助我们确定明天是否会下雨，也即没有什么信息增益。

ID3小总结：

• ID3决策树为多叉树，因此每个特征只使用一次，因为一次就将能分开的样本全部分开了；
• ID3决策树偏好值更多的特征，因此更容易发生过拟合现象；
• 没有剪枝，容易过拟合；
• 无法处理缺失值；
• 只能处理离散值；

C4.5决策树

C4.5决策树针对ID3决策树偏好值多的缺点进行改进，引入了信息增益比来作为分裂标准。

C4.5相较于ID3的改进有：

• 1、使用信息增益比来作为分裂标准，此时又会导致另一个问题——更加倾向于值更少的特征，值更少（熵更小，即计算信息增益比的分母更小）；
• 2、能处理连续数据，具体方法为：遍历所有值，以每个值来作为分割点将所有样本分为两类，找到信息增益比最大的点；
• 3、可以处理缺失值，具体地，仅使用非缺失样本来计算特征的信息增益，并将信息增益乘以缺失率以降低显示出缺失的影响，而对于缺失样本则是将缺失样本以某个概率分到子节点；
• 4、添加了剪枝来防止过拟合，有两种剪枝策略：
  • 预剪枝：在建树的过程中如果分裂后的准确率变低了，则停止分裂。这是一种贪心算法，可能得不到全局最优解；
  • 后剪枝：在完成建树后，依次删掉叶子节点并求准确率，最后通过比较就能得到最好的树。能得到全局最优解，但是算法复杂度较大；

C4.5树仍然使用的是多叉树，因此每个特征仅使用一次，在后续分裂中不再使用。且只能用于分类。

CART决策树

CART决策树相对于C4.5树进行了改进：

• CART决策树使用二叉树，效率高，且特征可以重复使用；
• 使用gini系数来最为分裂标准，计算复杂度大大降低；
• 缺失值处理：分裂时仍然是仅考虑CART树并通过乘以一个系数来显示缺失值的影响；而对于缺失值如何划分到子节点，则是使用了一种较为复杂的代理分裂的策略，简单理解即是对于这些缺失的样本选择别的特征来计算gini增益，如果又碰到了缺失，就需要再次找代理特征。。。；
• 对于回归问题，使用最小方差（也即均方误差）和来作为分裂标准；
• 使用代价复杂度剪枝策略，即不仅考虑了准确率，还将树的复杂度考虑进去了。

随机森林（Random Forest）

随机森林属于bagging算法，有两个随机过程：

• 1、对于每颗子树，有放回的随机选择N个样本（即bootstrap抽样）；
• 2、在每个结点分裂时，先随机选择m个特征，然后按照某个分裂标准从这些特征中选择分裂特征；

预测时，分类问题投票，回归问题求平均。

优点：

• 效果挺好；
• 速度快，易并行；
• 能处理高维数据，不用作特征选择；

梯度提升树（Gradient Boosting Decision Tree）

梯度提升树由多个回归决策树串联得到，因此建树时的分裂标准是均方误差和。

回归树如何解决分类问题？
以逻辑回归为例，逻辑回归其实也可以理解为广义线性回归函数来拟合对数几率。因此回归树也可以用类似的方法来进行分类。

梯度提升树的每个树都会拟合上棵树的拟合目标残差。

在梯度提升决策树中，还添加了shrinkage，这个是与adaboost的一个重大区别，相当于学习率，控制每棵树学习到更少的东西，使用更多的树来进行集成学习。

缺点：

• 对异常点敏感，可通过huber loss来进行缓解；
• 没有剪枝策略；

XGBOOST

xgboost的相对于GBDT的一个非常重要的改进就是使用泰勒二阶展开来近似拟合残差，也即如下公式：

xgb原始loss
上面为xgb原始loss，其中后面一项为模型复杂度损失。使用泰勒二阶展开近似的过程如下：

上面的泰勒展开中，f(x)其实是上一棵树的结果（也即原loss中的y^t-1），△x表示的是当前树要拟合的结果（也即原loss中的f_t(x)）。
因此，我们只需要求出每一步模型的一阶（gi）和二阶导数值（hi）并对目标函数最优化求解即可得到当前步最优的 f_t(x)。

再加上模型复杂度的表示，可以得到最终loss：

这里我们简单说一下模型复杂度的组成，第一项 γT其实是控制的树的叶子节点不要太多（可以理解为参数不要太多，L1正则化），第二项其实是控制每个叶子结点的数值不要太大（可以理解为模型参数不要太大，L2正则化）。

上面几步看不明白的可以去https://zhuanlan.zhihu.com/p/87885678 看一步一步的推导过程。

可以看到，模型的优化目标其实仅与前一棵树一阶导（G）、二阶导（H）、lambda（可以理解为L2正则化系数）、γ（理解为L1正则化系数）有关系。对于决策树的每次分裂，我们的目标其实就是要使得上面的目标函数值更小，换句话说，上面的目标函数就是我们的分裂标准，这与前面所有的决策树的分裂方式都是完全不同的。

看看下面的图可能更好理解：

如何选择分裂特征？

• 1、像cart树那样遍历特征的所有值以找到最佳分裂点，此方法能找大全局最优，但是计算量大；
• 2、排序分箱（其实还使用了二阶导加权）然后遍历几个分箱值以寻找最佳分裂点，此方法不一定能找到全局最优，但是能大大提升运算效率。

稀疏感知算法

在分裂选择特征时，仅使用非缺失值来进行计算增益。而对于缺失结点的划分，则是将每个缺失样本分别放入到两个子节点中，哪个增益大就选择划分到哪个结点。

工程化优化

略。。。

优点：

• 精度更高：二阶泰勒展开近似；
• 更灵活：不仅支持CART还支持线性分类器；
• 正则化：将剪枝过程整合到了loss函数中（L1系数控制结点数量，L2系数控制叶子结点数值）；
• shrinkage：削弱每棵树的影响，使用更多的树来进行集成学习；
• 缺失值处理：稀疏感知算法；
• 并行化；

LightGBM

更快，占用内存更小的GBM。

优化的点如下：

• 1、单边抽样：xgb在每棵树学习时其实还是使用了所有的样本的（or 抽样），而这些样本里面其实有很多样本已经学习的很好了，也即梯度很小，贡献也很小，因此在lgb中后续树学习时，使用梯度大的那部分样本a，然后加上抽取一些梯度小的样本得到总样本b，分裂时梯度小的样本需要乘以权重(1-a)/b来保持数据分布不变，使用这些样本来进行学习；

• 2、直方图算法：直方图算法与xgb中分裂时候的分箱算法基本是相同的，即对连续数值进行分箱处理，然后遍历分箱值即可以找到特征最佳分裂点；

• 3、直方图加速：左节点的直方图可以由父节点直方图减去左节点得到。且在构建直方图时，还可以先构建小的直方图来进一步减小计算量；

• 4、互斥特征捆绑：高维特征常常是稀疏的，且不同特征还有可能是互斥的，通过允许一定的非互斥率，将那些可能互斥的特征捆绑在一起可以达到降维的效果；

• 5、leaf-wise算法：也可以理解为类深度优先算法。xgb中是每层所有结点一起分裂，可以视为广度优先算法，这种做法的缺点是可能有些结点他的分裂收益已经很小了，不分裂可能更好。因此在lgb中，采用leaf-wise的类深度优先算法，每次都寻找分裂收益最大的结点来进行分裂。这种做法可以减少计算量；

• 6、类别特征最优分割：一般的决策树使用类别特征进行分裂时使用的是one-vs-rest的策略，这种策略（1）可能会产生分裂时样本划分不均衡；（2）将数据划分到多个小空间容易导致过拟合，影响决策树学习。因此lgb采用了一种many-vs-many的算法，即将多个类别捆绑为一组作为一个类，其余的类别作为另一类；

• 7、工程方面：特征并行、数据并行、投票并行、缓存优化；

与xgb相比：

• 1、内存更小：

  • 不需要xgb的预排序，lgb使用的分箱，只需要存bin值即可；
  • 互斥特征捆绑达到了降维的效果；

• 2、速度更快：

  • 单边梯度；
  • 分箱操作；
  • 互斥特征捆绑；
  • leaf-wise生长;
  • 工程上的一些优化；

基于树模型的特征选择

树模型解释性较好，我们常常可以通过树模型来进行特征选择，留下重要特征。不同树模型特征重要性评估方法略有区别。

决策树、随机森林、GBDT

决策树、随机森林和GBDT的特征重要性评估方法相同都是根据不纯度减小(也即gini系数)来进行度量：

sklearn API
从上面可以看出，基于不纯度减小的评估方法容易受特征维度的影响（误导），某个特征维度越高（即含有的类别越多），这个特征的重要性常常会被认为比较重要。

XGBoost

xgboost的特征重要性评估方法更为多样，如下：

从上面看，主要分为三种：

• weight，也即根据特征使用的次数来决定其权重；
• gain，根据收益（也即loss减小量）来决定其收益，其又可以分为两种：
  • gain，平均每次使用特征获得的收益；
  • total_gain，使用某个特征的收益总和；
• cover，覆盖率，也即这个特征覆盖了多少个样本，同样也分为两种：
  • cover，平均覆盖率，平均每次使用特征覆盖的样本数量（或者说覆盖率）；
  • total_cover，总覆盖率，某个特征总覆盖率。

LightGBM

lightGBM的特征评估方式如下：

如上，包括两种：

• split，也即特征使用次数，与xgboost中的weight是一致的；
• gain，使用特征的总收益（也即loss减小），与xgboost中的total_gain相同。

参考：
《统计学习方法》李航
【机器学习】决策树（下）——XGBoost、LightGBM（非常详细）
树模型(六)：XGBoost (带手动建树实例，非常推荐)