【机器学习】决策树

留白_

419人浏览 · 2026-07-06 14:56:43

留白_ · 2026-07-06 14:56:43 发布

1. 简介

决策树是一种树形结构，树中每个内部节点表示一个特征上的判断，每个分支代表一个判断结果的输出每个叶子节点代表一种分类结果。

分类：

ID3 决策树——通过信息增益来划分，越大越优先考虑。

C4.5 决策树——通过信息增益率划分，越大越优先考虑。

CART 决策树——通过基尼指数划分，越小越优先考虑。

建立过程：

特征选择：选取有较强分类能力的特征。
决策树生成：根据选择的特征生成决策树。
决策树也易过拟合，采用剪枝的方法缓解过拟合。

2. ID3 决策树

2.1. 信息熵

熵 Entropy：信息论中代表随机变量不确定度的度量。

公式

$H(x) = -\sum p(x_i)*log_2p(x_i)$

其中，p(xi)为数据中类别出现的概率，H(x)表示信息的信息熵值。

熵越大，数据的不确定性度越高，信息就越多。
熵越小，数据的不确定性越低。

2.2 信息增益

概念：特征a对训练数据集D的信息增益g(D，a)，定义为集合D的熵H(D)与特征a给定条件下D的熵H(D|a)之差。

公式：

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

其中，H(D|A)是条件熵，公式为

$H(D|A)=\sum_{v=1}^{n}\frac{D^v}{D}H(D^v)=\sum_{v=1}^{n}\frac{D^v}{D}\sum_{k=1}^{m}\frac{c^{kv}}{D^v}log_2\frac{c^{kv}}{D^v}$

举个例子：已知有6个样本，根据特征A：α 部分对应的目标值为：AAAB；β 部分对应的目标值为BB，如下表所示。计算此时的信息增益。

2.3. ID3决策树

搭建流程：

计算每个特征的信息增益
使用信息增益最大的特征将数据集拆分为子集
使用该特征（信息增益最大的特征）作为决策树的一个节点
使用剩余特征对子集重复上述（1，2，3）过程

这个链接讲的很好！

ID3决策树https://blog.csdn.net/weixin_66845445/article/details/130174519?fromshare=blogdetail&sharetype=blogdetail&sharerId=130174519&sharerefer=PC&sharesource=I_Like_S_&sharefrom=from_link

不足：偏向于选择种类多的特征作为分裂依据，只根据少数特征进行学习，可能导致过拟合。

3. C4.5 决策树

信息增益率公式：

$Gain\_Tatio(D,a)=\frac{Gain(D,a)}{IV(a)}$ , $IV(a)=-\sum_{v=1}^{n}\frac{D^v}{D}Ent(\frac{D^v}{D})$

其中，Gain_Ratio是信息增益率，Gain是信息增益，IV是特征熵。

信息增益率的本质：

特征的信息增益 ÷ 特征的内在信息
相当于对信息增益进行修正，增加一个惩罚系数
特征取值个数较多时，惩罚系数较小;特征取值个数较少时，惩罚系数较大。
惩罚系数:数据集D以特征a作为随机变量的熵的倒数。

举个例子

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

计算特征a 的信息增益率：

计算特征b 的信息增益率：

结论：如果只比较信息增益是特征a更大，但是考虑信息增益率就是特征b更大，选择特征b作为分裂特征。

C4.5的搭建流程与ID3的基本一致，就是判断指标不同。

4. CART决策树

CART决策树是一种决策树模型，它既可以用于分类，也可以用于回归。

CART回归树使用平方误差最小化策略。
CART分类生成树采用的基尼指数最小化策略。

4.1. CART分类树

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

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

举个例子：

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

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

第一步

1. 计算 ‘是否有房’ 的基尼指数

2. 计算 ‘婚姻状况’ 的基尼指数

最终：最小的基尼指数是以married作为分裂点的基尼指数，所以预选分裂点为：{married} 和 {single，divorced}。

3. 计算 ‘年收入’ 的基尼指数

4. 选取分裂点

奥卡姆剃刀原理：其核心内容为“如无必要，勿增实体”，主张在解释现象时应选择假设最少的理论。（能达到相同的效果，就选择更简单的形式）

因为 ‘婚姻状况’ 和 ‘年收入’ 都是最小值0.3，根据奥卡姆剃刀原理，最终选取 ‘婚姻状况’ 作为分裂点。就像下图所示。

第二步

在married分类中的2-4-6-9数据中 ‘是否拖欠贷款’ 都是no，已达到最大纯度，所以不需要再拆分。

序号	是否有房	年收入（K）	是否拖欠贷款
2	no	100	no
4	yes	120	no
6	no	60	no
9	no	75	no

在married分类中的1-3-5-7-8-10数据还需要进一步分叉。

序号	是否有房	年收入（K）	是否拖欠贷款
1	yes	125	no
3	no	70	no
5	no	95	yes
7	yes	220	no
8	no	85	yes
10	no	90	yes

1. 计算此时表中 ‘是否有房’ 的基尼指数

有房子的基尼值：有房子有1、7共计两个样本，对应：2个no、0个yes

Gini(是否有房，yes)=1-(2/2)²-(0/2)²= 0

无房子的基值:无房子有3、5、8、10共四个样本，对应：1个no、3个yes

Gini(是否有房，no)=1-(1/4)²-(3/4)²= 0.375

基尼系数:第一部分样本占了总样本的2/6行量，第二部分样本占了总样本的,4/6

Giniindex(D，是否有房)=2/6 * 0 + 4/6 * 0.375 = 0.2500

2.计算此时表中 ‘年收入’ 的基尼指数

先将数据按照 ‘年收入’ 按从小到大进行排序，再计算基尼指数：

是否拖欠贷款	no	yes	yes	yes	no	no
年收入	70	85	90	95	125	220
相邻值中点	77.5	87.5	92.5	110	172.5
Gini_index	0.4000	0.5000	0.4444	0.4	0.4

待确定的分裂点为:77.5、87.5、92.5、110、172.5。（其中77.5就是70和85的均值，后面的也依次类推）

以年收入为92.5将样本分成两部分（小于92.5的，和大于92.5的），计算基尼指数：

Gini_index=3/6 * [1-(1/3)²-(2/3)²] + 3/6 * [1-(2/3)²-(1/3)²] = 0.4444

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

3. 选取分裂点

上面的计算可知，‘是否有房’ 的基尼指数小于 ‘年收入’的基尼指数，所以选择 ‘是否有房’为下一个分裂节点。

第三步

根据 ‘是否有房’ 分类得到的两类：
yes的是数据第1和第7条，并且两条的 ‘是否拖欠贷款’ 都是 no，所以无需再往下分支。

序号	年收入（K）	是否拖欠贷款
1	125	no
7	220	no

no的是3-5-8-10，需要继续分支。

序号	年收入（K）	是否拖欠贷款
3	70	no
5	95	yes
8	85	yes
10	90	yes

先将数据按照 ‘年收入’ 按从小到大进行排序，再计算基尼指数：

是否拖欠贷款	no	yes	yes	yes
年收入	70	85	90	95
中值	77.5	87.5	97.5
Gini_index	0	0.25	0.333

最小值为0，所以按77.5进行分支。

4.2. CART回归树

CART回归树和 CART分类树的不同之处在于：

CART 分类树预测输出的是一个离散值，CART 回归树预测输出的是一个连续值
CART分类树使用基尼指数作为划分、构建树的依据，CART回归树使用平方损失
分类树使用叶子节点多数类别作为预测类别，回归树则采用叶子节点里均值作为预测输出

CART回归树的平方损失：

$Loss(y,f(x)) = (f(x)-y)^2$

举个例子：根据平凡损失，构建CART回归树。

已知：数据集只有一个特征x，目标值为y。

x	1	2	3	4	5	6	7	8	9	10
y	5.56	5.7	5.91	6.4	6.8	7.05	8.9	8.7	9	9.05

分析：因只有1个特征，所以只需选择该特征的最优划分点，并不需要计算其他特征。

类似于上面例子中对于 ‘年收入’ 数据列的处理方式，就是计算的一个是基尼指数，一个算的是平方损失。

1. 先将特征x的值排序，并取相邻元素均值作为待划分点，如下表所示：

y	5.56	5.7	5.91	6.4	6.8	7.05	8.9	8.7	9	9.05
x	1	2	3	4	5	6	7	8	9	10
中值	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5
平方损失	15.72	12.07	8.36	5.78	3.91	1.93	8.01	11.73	15.74

2.计算每一个划分点的平方损失，例如：划分点1.5的平方损失计算过程为：

R1为小于1.5的样本个数，样本数量为1，其输出值为5.56

RI = 5.56

R2为大于1.5的样本个数，样本数量为9，其输出值为：

R2 = (5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)/9 = 7.5

该划分点的平方损失：

L(1.5) = (5.56-5.56)² + [(5.7-7.5)² + (5.91-7.5)² + ... + (9.05-7.5)²] = 0 + 15.72 = 15.72

3. 算出以每一个中值为划分点的平方损失后，取平方损失最小的中值作为划分点。此时为6.5。

4. 然后根据6.5划分成两部分再继续计算中值对应的平方损失，继续往下进行划分....

CART回归树构建过程小结：

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

5. 决策树剪枝

为什么要剪枝？

决策树剪枝是一种防止决策树过拟合的一种正则化方法;提高其泛化能力。

剪枝：把子树的节点全部删掉，使用用叶子节点来替换

剪枝方法

预剪枝：指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点;
后剪枝：是先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。

剪枝方法的优缺点

预剪枝

优点：预剪枝使决策树的很多分支没有展开，不单降低了过拟合风险，还显著减少了决策树的训练、测试时间开销
缺点：有些分支的当前划分虽不能提升泛化性能，但后续划分却有可能导致性能的显著提高;预剪枝决策树也带来了欠拟合的风险

后剪枝

优点：比预剪枝保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝。
缺点：后剪枝先生成，后剪枝。自底向上地对树中所有非叶子节点进行逐一考察，训练时间开销比未剪枝的决策树和预剪枝的决策树都要大得多。

6. 总结

名称	提出时间	分支方式	特点
ID3	1975	信息增益	1.ID3只能对离散属性的数据集构成决策树 2.倾向于选择取值较多的属性
C4.5	1993	信息增益率	1.缓解了ID3分支过程中总喜欢偏向选择值较多的属性 2.可处理连续数值型属性，也增加了对缺失值的处理方法 3.只适合于能够驻留于内存的数据集，大数据集无能为力
CART	1984	基尼指数	1.可以进行分类和回归，可处理离散属性，也可以处理连续属性 2.采用基尼指数，计算量减小 3.一定是二叉树