C4.5决策树（信息增益率）、CART决策树（基尼指数）、CART回归树、决策树剪枝

发布于：2025-09-05 ⋅ 阅读:(11) ⋅ 点赞:(0)

一、C4.5决策树

C4.5算法旨在通过递归地划分数据集，构建一棵分类树，使每个分支尽可能“纯净”（即同一类别样本占比高）。它针对ID3算法的主要局限性进行了多项关键改进。

信息增益率 (Gain Ratio)：使用信息增益与固有信息（Intrinsic Information） 的比值来选择划分属性，避免了ID3中使用信息增益时对取值数目多的属性的偏好

 处理连续属性：通过动态二分法将连续值转换为二元分裂问题（如 A ≤ t和 A > t）

处理缺失值：允许样本缺失属性值，在训练和预测阶段采用概率分配机制进行处理

剪枝优化：采用后剪枝（Post-Pruning） 方法，特别是悲观错误剪枝（Pessimistic Error Pruning, PEP），以避免过拟合，无需独立的验证集

1、信息增益率

使用信息增益与固有信息（Intrinsic Information） 的比值来选择划分属性，避免了ID3中使用信息增益时对取值数目多的属性的偏好，它通过归一化处理来修正信息增益对多值属性的偏向性。

信息增益率 $Gain_Ratio(D, a)$ = 信息增益 $Gain(D,a)$ / 特征熵 $IV(a)$

$Gain_Ratio(D, a) = Gain(D, a)/IV(a)$

$IV(a) = - \sum _{v=1}^nD^V/D log_2(D^V/D)$

信息增益率的本质

特征的信息增益 ➗ 特征熵
相当于对信息增益进行修正，增加一个惩罚系数
惩罚系数：数据集D以特征a作为随机变量的熵的倒数

特征多，特征熵大，特征熵大对应 1/特征熵小
特征少，特征熵小，特征熵小对应 1/特征熵大

2、信息增益率计算

回顾信息增益：https://blog.csdn.net/pan13360344415/article/details/151172905?spm=1001.2014.3001.5502

已知数据集

需求：求特征a、b的信息增益率

结论

特征a的信息增益率大于特征b的信息增益率
根据信息增益率，应该选择特征a作为分裂特征

二、CART决策树

1、基尼指数

基尼值Gini（D）：从数据集D中随机抽取两个样本，其类别标记不一致的概率。故，Gini（D）值越小，数据集D的纯度越高。

基尼指数Gini_index（D）：选择使划分后基尼系数最小的属性作为最优化分属性。

注意：

信息增益（ID3）、信息增益率值越大（C4.5），则说明优先选择该特征。

基尼指数值越小（CART），则说明优先选择该特征。

2、基尼指数计算案例

已知：是否拖欠贷款数据。

需求：计算各特征的基尼指数，选择最优分裂点

是否有房

婚姻状况

最终：该特征的基尼值为 0.3（选择基尼值最小），并且预选分裂点为：

{married} 和 {single,divorced}

年收入

先以年收入 65 将样本分为两部分，计算基尼指数

以此类推计算所有分割点的基尼指数，最小的基尼指数为 0.3

3、三种分类树的对比

4、总结

CART模型是一种决策树模型，它即可以用于分类，也可以用于回归。
CART回归树使用平方误差最小化策略，
CART分类生成树采用的基尼指数最小化策略。

三、CART回归树

CART（Classification and Regression Trees）回归树是决策树算法的一种，专门用于处理连续型目标变量的回归问题。它通过构建二叉树结构，将特征空间递归地划分为不同的区域，并在每个区域（叶节点）用该区域内样本的目标变量均值作为预测输出。

1、CART 回归树和 CART 分类树的不同之处：

2、平方损失计算

平方损失： $Loss(y,f(x)) = (f(x) - y)^2$

已知：数据集只有 1 个特征 x, 目标值值为 y

需求：根据平方损失，构建CART 回归树

以此方式计算 2.5、3.5... 等划分点的平方损失，结果如下

当划分点 s=6.5时,m(s) 最小。所以第1个划分变量：特征为 X, 切分点为 6.5

对左子树的 6 个节点计算每个划分点的平方式损失，找出最优划分点，得到最后的结果，s=3.5时，m(s) 最小，所以左子树继续以 3.5 进行分裂

3、小结

选择一个特征，将该特征的值进行排序，取相邻点计算均值作为待划分点
根据所有划分点，将数据集分成两部分：R1、R2
R1 和 R2 两部分的平方损失相加作为该切分点平方损失
取最小的平方损失的划分点，作为当前特征的划分点
以此计算其他特征的最优划分点、以及该划分点对应的损失值
在所有的特征的划分点中，选择出最小平方损失的划分点，作为当前树的分裂点

四、决策树剪枝

决策树剪枝是防止模型过拟合、提升泛化能力的关键步骤。

1、为什么要剪枝？

决策树学习时，为了尽可能正确地分类训练样本，节点划分过程可能会不断重复，有时会造成决策树分支过多。这可能导致模型把训练数据自身的一些特点当作所有数据都具有的一般性质，从而引发过拟合。剪枝通过主动去掉一些分支来降低过拟合的风险，简化模型，提高其泛化能力。

2、预剪枝和后剪枝

① 预剪枝：指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点。

优点：能降低过拟合风险，并且由于很多分支没有展开，它能显著减少决策树的训练和测试时间开销。

缺点：有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝的这种“贪心”本质可能会带来欠拟合的风险。

② 后剪枝：是先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。

优点：后剪枝决策树通常比预剪枝决策树保留了更多的分支，其欠拟合风险很小，泛化性能往往优于预剪枝决策树。

缺点：由于是在生成完全决策树之后再进行剪枝，并且要自底向上地对树中所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。