从决策树，随机森林，到XGBoost

树类模型的发展与总结

0x01 决策树

1-1 整体技术

根据条件概率分布——判别模型

本质在于归纳出一组分类规则

求解方法一般为正则化的极大似然函数

决策树生成方法为递归的选择最优特征

过拟合-剪枝 —> 1-3 剪枝

1. 特征选择
2. 决策树的生成
3. 剪枝

1-1 需要用到的公式

假设随机变量X的概率分布为

$$P(X = x_{i}) = p_{i}, i = 1,2,...,n$$

假设有随机变量(X, Y)，其联合概率分布为

$$P(X = x_{i}, Y = y_{i}) = p_{ij}, i = 1,2,...,n; j = 1,2,...,m$$

熵

表示随机变量不确定性的程度

$$H(X) = -\sum_{i = 1}^{n}p_{i}log_{2}{p_{i}}$$ $$H(X) = -\sum_{i = 1}^{n}p_{i}log_{e}{p_{i}}$$

以2为底，最后单位为bit；以e为底，最后单位为nat；

熵与X的值无关，而与X的分布有关，所以可以记为

$$H(X) = -\sum_{i = 1}^{n}p_{i}log_{2}{p_{i}}$$

条件熵

$$H(Y|X) = \sum_{i = 1}^{n}p_{i}H(Y|X = x_{i})$$

经验熵和经验条件熵就是当熵和条件熵中的概率是由数据估计得到时，对应的熵和条件熵

经验熵

假设数据集为D，$|C_{k}|$表示第k类的样本数

$$H(D) = \sum_{k = 1}^{K}\frac{|C_{k}|}{|D|}log_{2}{\frac{|C_{k}|}{|D|}}$$

经验条件熵

$D{i}$表示因为特征A所划分的数据子集，$|D{ik}|$表示$|D_{i}|$中属于第k类的数量

$$H(D|A) = \sum_{i = 1}^{n}\frac{|D_{i}|}{|D|}\sum_{k = 1}^{K}\frac{|D_{ik}|}{|D|}log_{2}{\frac{|D_{ik}|}{|D|}}$$

信息增益

信息增益表示得知X的概率使得对Y的不确定性的减小程度

$$g(D,A) = H(D) - H(D|A)$$

信息增益比

$$g_{R}(D,A) = \frac{g(D,A)}{H(D)}$$

基尼指数

$$Gini(p) = \sum_{k = 1}^{n}p_{k}(1-p_{k}) = \sum_{k = 1}^{n}1-p_{k}^{2}$$ $$Gini(D) = \sum_{k = 1}^{n}1-{\frac{|C_{k}|}{|D|}}^{2}$$

条件基尼指数

$$Gini(D) = \sum_{k=1}^{K}\frac{|D_{k}|}{|D|}Gini(D_{k})$$ $$Gini(D, A) = Gini(D | A) = \frac{|D_{1}|}{|D|}Gini(D_{1})+\frac{|D_{2}|}{|D|}Gini(D_{2})$$

1-2 ID3 C4.5 CART

ID3算法 选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点，再对子节点循环调用

ID3相当于用极大似然法进行概率模型的选择

C4.5是ID3的改进，使用信息增益比

这两种算法只有生成，没有剪枝，容易过拟合

需要预剪枝 —> 1-3 剪枝

剪枝使用损失函数来进行，考虑决策树的复杂度

CART算法 classification and regression tree

先生成尽可能大的决策树（完全生长），用验证集进行剪枝并选择最优子树

基尼指数

计算每种特征及特征中每种取值下的基尼指数，例如 $A$ 特征下 $a{1},a{2},…,a_{A}$

计算量变大了

结束条件

1. 样本数量小于阈值
2. 样本集基尼指数小于阈值（样本集中样本基本属于同一类）
3. 没有更多特征

1-3 CART回归

回归需要特别拿出来说要下，因为其他两个只能进行分类

cart可以实现最小二乘回归树

采用平方损失

1-4 剪枝

后剪枝 CART

一般采用递归的方式

$g(t)=\frac{C(t)-C(T_{t})}{\left|t\right|-1}$

$T{0}$中减去g(t)值最小的子树$T{t}$就为$T{1}$，这个最小的g(t)就为$\alpha{1}$，之后不断剪枝，$\alpha$不断增大，就获得了$\alpha$区间和子树集合。

下一步利用交叉验证选取最好的子树，这一过程也就选择了最好的$\alpha$

预剪枝 ID3 C4.5

0x02 集成学习

1. 找到误差互相独立的基分类器
2. 训练基分类器
3. 合并基分类器的结果

2-0 偏差 方差

偏差

• 偏差是指由有所采样得到的大小为m的训练数据集，训练出的所有模型的输出的平均值真实模型输出之间的偏差；

方差

• 方差是指有所有采样得到的大小为m的训练数据集，训练出的所有模型的输出的方差；

2-1 Boosting

串行，对上层分类错误的样本，基于更高的权重。

最后的结果采用各层输出的加权结果

目的在于缩小偏差

2-2 Bagging

并行

样本集分离子样本集，最终基分类器投票

目的在于缩小方差

2-3 Stacking

之前写过专门介绍stacking的文章：Stacking 模型融合

0x02 Adaboost

以ID3决策树为例，其实什么基分类器都可以；不过树形结构简单、且比较容易产生随机结果。

Adaboost采用前向分步算法，通俗理解也就是串行思想，逐步优化基分类器；

1. 在当前数据集的权重分布情况下，训练基分类器；
2. 计算错误率
3. 根据错误率更新样本权重

训练误差是指数级下降的；

不需要考虑误差下界，AdaBoost具有适应性，也就是名字里的adaptive；

0x03 GDBT

GBDT主要的优点有：

• • 1) 可以灵活处理各种类型的数据，包括连续值和离散值。
  • 2) 在相对少的调参时间情况下，预测的准确率也可以比较高。这个是相对SVM来说的。
  • 3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

• from百面机器学习：

• • • 预测阶段计算速度较快，树与树之间可以并行化计算
    • 在分布稠密的数据机上，泛化能力和表达能力都比较好
    • 具有较好的解释性和鲁棒性
    • 能够自动发现特征质检的高阶关系
    • 不需要做特殊预处理（比如归一化）

GBDT的主要缺点有：

• • 由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
  • 在高维稀疏数据上，表现不如SVM或神经网络
  • 在处理文本分类特征问题上，相对其他模型优势不如在处理数值特征时明显
  • 训练过程需要串行，只能在决策树内部采用一些局部并行手段提高训练速度

0x04 XGBoost

XGBoost是GDBT的工程实现，

主要改进：

1. 数学上：
   • 二阶泰勒展开
   • 正则化项
2. 工程上：
   • 训练阶段中树的分裂阶段可以并行
   • 可以处理缺失值

• 适用于树模型的正则项
• 包含了输的叶子节点个数、每个叶子节点输出分数的L2平方和
  • 正则化项γ起到了一定的预剪枝的效果
  • xgboost采用预剪枝策略，只有分裂后的增益大于0才会进行分裂。
• 缺失值
  • XGBoost 在构建树的节点过程中只考虑非缺失值的数据遍历，而为每个节点增加了一个缺省方向，当样本相应的特征值缺失时，可以被归类到缺省方向上，最优的缺省方向可以从数据中学到。至于如何学到缺省值的分支，其实很简单，分别枚举特征缺省的样本归为左右分支后的增益，选择增益最大的枚举项即为最优缺省方向。
  • 在构建树的过程中需要枚举特征缺失的样本，乍一看该算法的计算量增加了一倍，但其实该算法在构建树的过程中只考虑了特征未缺失的样本遍历，而特征值缺失的样本无需遍历只需直接分配到左右节点，故算法所需遍历的样本量减少，稀疏感知算法比 basic 算法速度块了超过 50 倍。
• 抽样
• • 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样（即每次的输入特征不是全部特征），不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
  • 行抽样：传统GBDT在每轮迭代时使用全部的数据；XGB则采用了类似RF的策略，支持对数据进行采样
• 并行化处理：
• • 在训练之前，预先对每个特征内部进行了排序找出候选切割点，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。
  • 在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行，即在不同的特征属性上采用多线程并行方式寻找最佳分割点。

• 参数

  • XGB架构参数

  • • booster：CART、或者线性模型、或者DART

    • n_estimator：

    • objective：

    • • 分类：MSE
      • 分类：二分类用logistic、多分类用softma

  • 弱学习器参数

  • • max_depth：树的深度
    • min_child_weight：最小子节点的权重。如果某个子节点权重小于这个阈值，则不会在分裂。使用的是该节点所有二阶导数的和
    • gamma：分裂所带来的损失最小阈值，大于此值，才能继续分裂
    • subsample：子采样参数，无放回抽样
    • colsample_bytree 整棵树的特征采样比例
    • colsample_bylevel 某层的特征采样比例
    • colsample_bynode 某一个树节点的特征采样比例
    • reg_alpha：L1正则化参数
    • reg_lambda： L2正则化参数

• • • 其他

    • • n_jobs控制算法的并发线程数

      • scale_pos_weight用于类别不平衡的时候，负例和正例的比例。类似于sklearn中的class_weight

      • importance_type则可以查询各个特征的重要性程度。最后可以通过调用booster的get_score方法获取对应的特征权重。

      • • “weight”通过特征被选中作为分裂特征的计数来计算重要性
        • “gain”和“total_gain”则通过分别计算特征被选中做分裂特征时带来的平均增益和总增益来计算重要性
        • “cover”和 “total_cover”通过计算特征被选中做分裂时的平均样本覆盖度和总体样本覆盖度来来计算重要性。

• Shrinkage（缩减），相当于学习速率（xgboost中的eta）。每次迭代，增加新的模型，在前面成上一个小于1的系数，降低优化的速度，每次走一小步逐步逼近最优模型比每次走一大步逼近更加容易避免过拟合现象；

0x05 LightGBM

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

从 LightGBM 名字我们可以看出其是轻量级（Light）的梯度提升机（GBM），其相对 XGBoost 具有训练速度快、内存占用低的特点。

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

LightGBM与 XGBoost 的对比

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

内存更小

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

速度更快

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

　参考

【机器学习】决策树（下）——XGBoost、LightGBM（非常详细）