【机器学习】决策树

发表于 | 分类于 |

决策树教程。

决策树

决策树介绍

决策树算法是一种监督学习方法，用于分类和回归任务。它通过递归地分割数据集，构建一棵树状结构模型来进行预测。

从根节点到叶节点的路径来表示决策规则，每个内部节点代表一个特征上的测试，每个分支代表一个测试结果，而每个叶节点代表一个类别（对于分类任务）或输出值（对于回归任务）。

决策树的学习过程可以归纳为递归地选择最优特征进行分裂，直到满足停止条件。

决策树的构建过程

  1. 特征选择： 选择最优特征作为当前节点的分裂依据。常见的特征选择度量有信息增益、信息增益比、基尼指数等。

  2. 分裂节点： 根据选定的特征和特征值，将数据集分割成子集。

  3. 递归构建： 对每个子集重复步骤1和2，直至满足停止条件（如子集中样本数少于阈值、所有样本属于同一类别或达到最大深度）。

  4. 剪枝： 为了避免过拟合，可以通过预剪枝（在构建过程中提前停止）或后剪枝（构建完整树后再修剪）来简化树结构。

决策树的算法变体

  • ID3（Iterative Dichotomiser 3）： 使用信息增益作为特征选择度量，只能处理离散特征，且容易过拟合。

  • C4.5： ID3的改进版本，使用信息增益比来解决ID3偏向选择具有更多值的属性的问题，支持连续特征和缺失值处理。

  • CART（Classification and Regression Trees）： 同时适用于分类和回归任务，使用基尼指数或最小平方误差作为分裂标准。

优点

  • 易于理解和解释，其决策逻辑清晰直观。
  • 数据的划分不依赖于缩放，不需要特征预处理。

缺点

  • 容易过拟合，尤其是当树的深度很大时。
  • 对噪声敏感，数据中的微小变化可能导致树结构的大幅变动。

ID3

ID3算法是一种决策树学习方法，其设计哲学遵循奥卡姆剃刀原理，即倾向于构建更为简化的决策树。

思想：通过计算信息增益来选择最优的特征进行决策树的分裂。

信息增益反映的是某个特征能够带来的信息量，或者说它能够降低数据集不确定性的程度。

算法从根节点开始，采用贪心策略逐层构建决策树，每次选择信息增益最大的特征作为分裂特征。

划分标准：

信息熵、条件熵和信息增益用来量化数据集的不确定性以及特征选择的价值。

  • 数据集的信息熵 (Entropy) 信息熵是用于衡量数据集纯度的一种度量，信息熵越高，说明数据集的不确定性越大，纯度越低。 假设数据集D包含K个不同的类别，第k个类别的样本占数据集的比例是P(k)，则数据集D的信息熵公式为： \(H(D) = - \sum_{k=1}^{K} P(k) \log_2{P(k)}\)

  • 条件熵 (Conditional Entropy) 条件熵是在已知某特征A的情况下，数据集D的不确定性。 假设特征A有N个可能的取值，第i个取值对应的子集是D_i，那么特征A对数据集D的条件熵公式为： \(H(D|A) = \sum_{i=1}^{N} \frac{|D_i|}{|D|} H(D_i)\) 其中，$H(D_i)$ 是子集 $D_i$ 的信息熵。

  • 信息增益 (Information Gain) 信息增益表示在特征A的帮助下，数据集D的不确定性减少了多少。它是数据集D的信息熵与特征A的条件熵之差。信息增益公式如下： \(Gain(D,A) = H(D) - H(D|A)\) 信息增益越大，表明特征A对数据集D的分类能力越强，因此在构建决策树时，ID3算法会选择信息增益最大的特征作为节点的分裂属性。

缺点：

  • 过拟合风险：由于缺乏剪枝策略，ID3算法构建的决策树可能过于复杂，导致过拟合现象。
  • 偏好多值特征：信息增益准则倾向于选择具有较多取值的特征，这可能导致模型对某些类型特征的不公正偏好。
  • 仅适用离散特征：ID3算法直接处理离散特征，对连续型特征需要额外的离散化步骤。
  • 忽略缺失值：算法在处理数据时，没有机制来妥善处理缺失值。

C4.5

C4.5是一种决策树学习算法，在多个方面对ID3进行了改进，特别是在处理连续特征、缺失值和防止过拟合方面。

思想

  • 悲观剪枝策略：C4.5引入了后剪枝技术，通过递归地检查每个非叶节点，判断用单个叶节点替代子树是否能减少错误率。
  • 信息增益率：为了克服信息增益偏向于选择具有更多独特值的特征的问题，C4.5使用信息增益率作为特征选择的标准，该指标考虑了特征的固有价值。
  • 连续特征处理：C4.5将连续特征离散化，通过计算各划分点的信息增益来选择最优分割点。
  • 缺失值处理：对于缺失值，C4.5在计算信息增益率时仅使用完整数据，并在实际分类时按概率分配样本至子节点。

划分标准

信息增益率用以平衡特征选择，避免偏好具有较多取值的特征。

信息增益率 $GainRatio(D,A)$ 为信息增益除以特征 $A$ 的固有值（Intrinsic Value），其公式为： \(GainRatio(D,A) = \frac{Gain(D,A)}{IV(A)}\) 其中固有值 $IV(A)$ 定义为： \(IV(A) = -\sum_{v \in values(A)} \frac{|D_v|}{|D|}\log_2\left(\frac{|D_v|}{|D|}\right)\)

注意，信息增益率更偏好取值范围较少的特征（分母值越小，整体值越大）。 因此不是直接用增益率最大的特征进行划分，而是先筛选信息增益高于平均值的特征，再选择其中增益率最高的特征。

剪枝策略

剪枝的需求主要来自以下两个原因：

  1. 过拟合的树在泛化能力的表现非常差。
  2. 预剪枝可以减少计算量
  • 预剪枝：在节点划分前评估是否继续增长。
    • 节点内数据样本低于某一阈值；
    • 所有节点特征都已分裂；
    • 节点划分前准确率比划分后准确率高。
  • 后剪枝：基于已生成树进行剪枝，得到简化版的剪枝决策树。
    • 悲观剪枝，用递归的方式从低往上针对每一个非叶子节点，评估每个非叶节点的子树是否可由单个叶节点替代，以减少过拟合。 如果剪枝后与剪枝前相比其错误率是保持或者下降，则这棵子树就可以被替换掉。

预剪枝可以降低过拟合风险同时减少训练时间，但也可能带来欠拟合风险。 后剪枝的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但其训练时间会大的多。

CART

CART（Classification and Regression Trees）是一种用于分类和回归的决策树算法。

CART算法在决策树构建中采用了二叉树结构，相较于多叉树，这简化了决策树的规模，提高了算法的效率。

思想

  • 分裂：CART算法通过二叉递归划分来构建决策树，能够处理连续和离散特征，没有明确的停止条件，理论上会一直生长。
  • 剪枝：CART使用基于代价复杂度的剪枝策略，从最大树开始逐步剪枝，每次选择训练数据熵对整体性能贡献最小的那个分裂节点作为下一个剪枝对象，直到只剩根节点。 这样产生一系列嵌套的剪枝树，从中选出一颗最优的决策树。
  • 树选择：通过独立的测试集或交叉验证评估每棵剪枝树的预测性能，以选择最优决策树。

划分标准

CART算法使用Gini指数作为划分标准，它衡量了数据集的不纯度，Gini指数越小，数据集纯度越高。Gini指数计算简单，避免了熵模型中的对数运算，适用于分类和回归问题。 Gini指数和信息增益（率）正好相反。

假设一个数据集 $D$ 由 $k$ 个不同的类别组成，其中第 $i$ 类的样本占比为 $p_i$，则数据集 $D$ 的基尼系数 $Gini(D)$ 定义为： \(Gini(D) = \sum_{i=1}^{k} p_i(1-p_i) = 1 - \sum_{i=1}^{k} p_i^2\)

对于二分类模型，当决策树的一个节点被特征 $A$ 分裂为两个子集 $D_1$ 和 $D_2$，则分裂后的加权基尼系数 $Gini_A(D)$ 为： \(Gini_A(D) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)\)

基尼指数可以理解为熵模型的一阶泰勒展开。

缺失值处理

CART算法会通过代理测试（Surrogate Splits）来处理该特征中缺失值的样本。

代理测试是指寻找能够替代缺失值特征的其他特征，用这些替代特征的值来决定样本应被划分到哪个子节点中。

  • 代理分裂器的确定：对于树的每个节点，CART算法都会找到一组代理分裂器，无论在训练数据上是否存在缺失值。 代理分裂器的选取基于其与主分裂器（即选定的划分特征）的相关性和预测性能。 代理分裂器必须在性能上超过一个默认规则，才能被视为合格的代理。
  • 缺失值样本的处理：当遇到一个特征值缺失的样本时，CART算法会根据其排名最高的代理分裂器来决定样本的走向。 如果最高排名的代理分裂器的值也缺失，算法会转而使用排名第二的代理，依此类推。 如果所有代理分裂器的值都缺失，那么样本会被默认划分到具有最多样本的那个子节点中。

剪枝策略

CART采用基于代价复杂度的剪枝方法，通过定义一个损失函数，权衡模型复杂度与训练数据拟合度，以防止过拟合现象。

代价复杂度剪枝的目标是找到一棵既不会因为过于复杂而过拟合，也不会因为过于简单而欠拟合的决策树。这个过程通过定义一个损失函数来实现，该损失函数同时考虑了决策树的训练误差和复杂度。损失函数的公式如下：

\[R_\alpha(T) = R(T) + \alpha |T|\]

其中，

  • $R(T)$ 是决策树 $T$ 的训练误差，
  • $ T $ 是决策树 $T$ 的叶子节点数量，
  • $\alpha$ 是一个控制复杂度惩罚的参数。

在之前的决策树上进行如下改进：

  • 对于决策树的每个子树，计算损失函数 $R_\alpha(T)$，其中 $\alpha$ 参数决定了对复杂度惩罚的强度。
  • 从最大决策树开始，递归地检查每个非叶节点，判断用一个叶节点替代该子树是否能够减少损失函数的值。如果剪枝后损失函数的值减少，那么这个子树就被一个叶节点取代。
  • 随着 $\alpha$ 参数的变化，会产生一系列嵌套的剪枝树。每个 $\alpha$ 值对应一个最优子树。通过在验证集上评估这些树的性能，可以确定一个最优的 $\alpha$ 值，从而找到最优的决策树。

$\alpha$ 的值决定了剪枝的程度。较小的 $\alpha$ 会导致较少的剪枝，较大的 $\alpha$ 则会导致更多的剪枝。通常，$\alpha$ 的值需要通过交叉验证来确定，以找到使验证误差最小化的点。

损失函数中的第一项 $R(T)$ 衡量了决策树对训练数据的拟合程度，第二项 $\alpha T $ 则是对复杂度的惩罚。通过调整 $\alpha$ 的值，可以平衡这两者，避免过拟合或欠拟合。

通过代价复杂度剪枝，CART算法能够在保持良好泛化性能的同时，避免决策树变得过于复杂。这种方法不仅提高了模型的稳定性，也减少了模型的训练时间和存储需求。

类别不平衡

CART内置了一种先验机制，能够自动处理类别不平衡问题。

只需通过计算每个节点相对于根节点的类别频率比值，即为对类别进行自动加权，实现类别均衡。

回归树

CART算法不仅适用于分类，也适用于回归。在回归树中，通过最小化均方差来确定最佳分割点，预测时使用叶节点的均值或中位数作为输出结果。