决策树类算法
在最近的业务实践中, 涉及了基于决策树类算法的分类器模型, 如 Random Forest, XGBoost, LightGBM, 本文简述这些不同机器学习 分类 算法的基本原理, 优势和使用方法.
1. 决策树算法
决策树算法的目标是通过构建树状的决策规则, 通过在每个节点上对某一个特定的feature进行分类, 一步步地划分特征空间, 由此实现对样本的分类.
1.1 基本原理
决策树的构建流程包括 特征选择, 生成树 和 对树的剪枝 三个部分, 其中树的生成是通过不断生成 子节点 的方式 递归生成 的, 每一个生成的子节点 (分支节点) 都包括对输入数据某个维度的分类规则, 因此我们希望决策树的分支节点所分出的两类样本 尽可能是属于同一类别 的, 它常被用名为 “纯度 (purity)” 的指标描述.
在生成决策树后, 为了避免模型过拟合, 就需要通过剪枝的方式增强模型的泛化能力. 下面简述决策树算法中 特征选择 的常用规则.
-
基于信息熵和信息增益的特征选择
信息熵是来源于信息论和概率统计中的概念, 度量某个随机变量的 不确定性. 其定义为:
定义 (信息熵)
样本集合纯度的程度由信息熵 (
\[\text{Entropy(D)} = -\sum_{k=1}^{\vert D \vert} p_k \cdot \log_{2}(p_k)\]Information Entropy) 度量. 假设样本集合 $D$ 中第 $k$ 类样本占整体样本的比例为 $p_k$, 则定义 $D$ 的信息熵为:可见, 信息熵 $\text{Entropy(D)}$ 的值越小, $D$ 的纯度越高.
因此, 在特征选择一步中, 为了尽可能的选择让分类出的两个数据类别更 “纯净” 的属性, 算法会选择 “纯度提升” 最大的指标作为生成的新节点中的判定规则.
我们可以使用 信息增益 (
Information Gain) 和 信息增益比 (Information Gain Ratio) 建模信息增益的大小:定义 (信息增益)
特征 $a$ 对训练数据集的信息增益 $g(D, a)$ 定义为集合 $D$ 的 经验熵 (
\[g(D, a) = H(D) = H(D \vert a)\]Empirical Entropy) $H(D)$ 与给定特征 $a$ 分类情况下 $D$ 的经验条件熵 $H(D \vert a)$ 的差:定义 (信息增益比)
信息增益比又称增益率, 目的是解决信息增益这个定义中, 信息增益的大小和训练数据集的经验熵大小无关的问题.
其定为: 特征 $a$ 对训练数据集 $D$ 的信息增益 $g_R(D, a)$ 定义为其信息增益 $g(D, a)$ 和训练数据集 $D$ 的经验熵 $H(D)$ 的比值:
\[g_R(D, a) = \frac{g(D,a)}{H(D)}\]若使用信息增益选择特征, 则决策树算法称为 ID3算法, 使用信息增益比的话则为 C4.5 算法.
-
基于基尼指数的特征选择
随机森林算法使用 基尼指数 (
Gini Index) 选择特征的划分属性:定义 (基尼指数)
基尼指数又称 基尼不纯度 (
Gini Impurity), 刻画数据集中的某个特定特征在被随机分类时, 错误分类的概率. 其取值位于 $0$ 和 $1$ 之间.对 “纯净” 的数据集, 即指包含一个分类的数据集而言, 其基尼不纯度为 $0$, 对训练数据中特征在不同分类下随机分布的数据集, 其基尼不纯度为 $1$. 它定义为:
\[\text{Gini}(D) = 1-\sum_{k=1}^{\vert D \vert}(\frac{\vert C_k \vert}{\vert D \vert})^2\]其中 $C_k$ 是 $D$ 中属于第 $k$ 类的样本子集.
在生成树的过程中, 基于使用上述的某个指标进行特征选择的结果, 被选定的最优特征和同时被决定的最优二值切分点会作为新节点的切分规则.
在完成树的生成后, 就可以进行树的剪枝. 一般的常见剪枝算法为 CART, 此处不做详细介绍.
1.3 使用方法
1
2. 随机森林算法
随机森林算法实质是对多棵决策树的组合, 属于一类集成学习 (Ensemble) 方法. 它以决策树为基学习器, 在决策树的训练过程中引入了随机属性选择:
常规决策树在特征选择时会在当前节点可选择的属性集合中选择一个 最优属性, 而随机森林的特征选择过程中会在当前节点可选择的属性集合中首先 随机选择一个子集, 然后在这个子集中再选择一个最优属性进行划分, 对基学习器的多样性引入了 属性扰动, 增加了个体学习器之间的 差异度, 提升了最终得到的集成 (Ensemble) 的泛化能力.
3. XGBoost算法
XGBoost 算法属于 Boosting 算法的一种, 同样遵循 “将多个弱分类器集合 (ensemble) 到一起, 通过不断迭代提升模型的泛化能力” 的思想. XGBoost 算法中使用的树模型是 CART 回归树, 下面首先对其进行简要介绍.
3.1 CART 回归树
CART 回归树是一种二叉树, 其每个非叶子节点都包含一个特征的判断条件, 通过对输入数据的特征进行判断, 将数据划分到左右两个子节点中, 直到叶子节点, 叶子节点中包含了对输入数据的预测值.
在划分样本空间时, CART 回归树使用 平方误差最小化准则 作为划分的依据, 即在每个节点上, 选择使得划分后的两个子节点中的样本的平方误差最小的特征和切分点作为划分的依据:
其中 $R_m$ 是当前节点的样本集合, $f(x_i)$ 是对样本 $x_i$ 的预测值.
因此, CART 回归树的特征选择和切分点选择的过程中, 本质上是在求解目标函数:
由此可知, 只需遍历 所有特征的全部切分点, 即可找到最优的切分特征和切分点, 完成新节点的生成, 最终得到回归树.
3.2 XGBoost 算法思想
基于 CART 回归树, XGBoost 的基本思想是通过不断迭代, 生成一系列回归树. 每生成的新回归树实际上是在上一棵的基础上学习一个新函数以拟合上一棵树的残差, 从而不断提升模型的泛化能力.
在算法流程执行结束后, 我们将得到多棵回归树, 通过将这些回归树的预测值相加, 就可以得到最终的预测值:
\[\hat{y}_i = \sum_{k=1}^{K}f_k(x_i)\]其中 $f_k(x_i) = w_{q(x_i)}$ 是第 $k$ 棵树的预测值, $q(x_i)$ 是样本 $x_i$ 被划分到的叶子节点的索引, $w$ 是叶子节点的权重.
3.3 XGBoost 的目标函数
XGBoost 的目标函数由两部分组成: 正则化项 和 损失函数. 损失函数衡量 预测结果和真实结果的差距, 正则化项包括 叶子节点的数量 和 叶子节点的权重 两部分, 用于衡量模型的复杂度, 从而避免模型过拟合.
即:
\[\text{ObjectiveFunction}(T) = \sum_{i=1}^{n}l(y_i, \hat{y}_i^{(T)}) + \sum_{k=1}^{T}\Omega(f_k)\]其中 $l(y_i, \hat{y}_i^{(T)})$ 是损失函数, $\Omega(f_k)$ 是正则化项, $f_k$ 是第 $k$ 棵树. 并且有:
\[\Omega(f) = \gamma T + \frac{1}{2}\lambda \Vert w \Vert^2\]其中 $T$ 是叶子节点的数量, $w$ 是叶子节点的权重, $\gamma$ 和 $\lambda$ 是正则化项的超参数.
在误差反向传播的过程中, 损失函数的近似方式是 取它在 $f_{t}=0$ 处的二阶泰勒展开:
\[\text{ObjectiveFunction}(T) \approx \sum_{i=1}^{n}[l(y_i, \hat{y}_i^{(T-1)}) + g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t)\]其中 $g_i$ 和 $h_i$ 是损失函数在 $f_{t-1}$ 处的一阶和二阶导数, $f_t(x_i)$ 是第 $t$ 棵树对样本 $x_i$ 的预测值.
并且, 实践证明 前 $t-1$ 棵树的预测值 $\hat{y}_i^{(t-1)}$ 对第 $t$ 棵树的预测值 $\hat{y}_i^{(t)}$ 的影响不大, 因此可以将其忽略, 从而得到:
\[\text{ObjectiveFunction}(T) \approx \sum_{i=1}^{n}[g_if_t(x_i) + \frac{1}{2}h_if_t^2(x_i)] + \Omega(f_t)\]由于上式描述的是所有样本的损失函数, 因此可以将其拆分为每个叶子节点的损失函数之和:
\[\text{ObjectiveFunction}(T) \approx \sum_{j=1}^{T}[G_jw_j + \frac{1}{2}(H_j + \lambda)w_j^2] + \gamma T\]因此可得到对于 每一个叶子节点 的最优权重 $w_j$ 的解析解:
\[w_j^* = -\frac{G_j}{H_j + \lambda}\]也就是说:
\[\text{ObjectiveFunction}(T) \approx -\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j + \lambda} + \gamma T\]由上面的推理过程可知, 在每一轮迭代中, 我们需要计算每个叶子节点的 一阶导数 $G_j$ 和 二阶导数 $H_j$, 从而计算出每个叶子节点的最优权重 $w_j^*$, 从而得到每个叶子节点的最优预测值 $f_t(x_i)$, 进而得到第 $t$ 棵树的预测值 $\hat{y}_i^{(t)}$.
3.4 XGBoost 的节点分裂算法
在讨论了如何计算每个叶子节点的最优权重 $w_j^*$ 后, 下面我们讨论 XGBoost 算法中分裂节点的策略. 和 CART 回归树相同, XGBoost 同样使用 贪心算法, 通过遍历所有特征的所有切分点, 选择使得 上面所提到的目标函数 增益最小的特征和切分点作为分裂节点的依据.
在这一步中, 同时还可限制只有当 增益大于某个阈值 时, 才进行分裂, 从而避免树生长过深, 导致过拟合.
3.5 XGBoost 的优势
XGBoost 算法设计了多种策略防止过拟合, 同时支持在寻找最佳分裂特征时, 对候选分裂点进行并行化计算, 提升了算法的时间效率.
4. LightGBM算法
XGBoost 算法的缺点是在寻找最佳分裂特征时, 由于需要遍历所有特征的所有切分点, 导致算法的时间复杂度较高. LightGBM 算法在 XGBoost 算法的基础上, 通过 直方图算法 和 基于梯度的单边采样 等技术, 提升了算法的时间效率.
4.1 直方图算法
我们可以简单地将直方图算法理解为 对特征的离散化 : 将每个连续的特征拆分到多个范围中, 每个范围作为一个 箱子, 每个箱子中包含了该范围内的样本数量, 将对特征的切分点的遍历过程, 转化为对每个箱子的遍历过程, 从而提升了算法的时间效率.
和 XGBoost 不同, 直方图算法无需额外存储对每个连续特征预排序的结果, 而且可以用 int_32 类型的整数存储特征的离散化结果, 相比 XGBoost 用 float_32 类型的浮点数存储特征的连续值, 节省了大量的内存空间.
LightGBM 的另一个基于直方图的优化称为 直方图作差加速: 一个叶子节点的直方图可以通过其父节点的直方图和兄弟节点的直方图作差得到, 从而避免了对整个数据集的遍历, 提升了算法的时间效率.
4.2 含深度限制的按叶子节点采样算法
LightGBM 中决策树的生长策略是 按叶子生长 (Leaf-wise), 避免如 XGBoost 算法一样在遍历一次数据时同时对同一层的所有叶子节点进行分裂.
在同一层的叶子节点中, LightGBM 选择 增益最大 的叶子节点进行分裂, 由此在分裂次数相同的情况下, 该策略可降低更多的拟合误差, 实现更优的模型精度.
为了避免过拟合, LightGBM 在按叶子生长的决策树的生长过程中, 通过 限制叶子节点的深度 的方式, 限制了决策树的生长深度, 从而避免了过拟合.
4.3 单边梯度采样算法
单边梯度采样算法 (Gradient-based One-Side Sampling, GOSS) 的思想是: 对样本进行采样, 丢弃一些对 计算信息增益没有帮助的样本, 也就是梯度较小的样本, 留下更有用的数据, 同时尽可能地避免影响数据的总体分布.
为了避免影响数据的总体分布, GOSS 将要进行分裂的特征的所有取值按照 绝对值大小 进行 降序排列, 选取绝对值最大的前 $p$ 个样本并从中随机采样 $q$ 个样本, 其中 $p$ 和 $q$ 是超参数, 表示大梯度数据和小梯度数据的采样比例.
随后, 被选定的小梯度数据会乘以一个系数 $\frac{1-q}{p}$, 从而避免过大改变数据的分布. 最后, 将大梯度数据和小梯度数据合并, 作为本轮迭代的训练数据.
