决策树-剪枝处理
前言：理解《机器学习》P79-83中的决策树剪枝示例。
决策树生成
原始数据集如下所示，前10行为训练集，后7行为验证集，由此数据集可生成如下所示的决策树。
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1LIledaa-1674722994891)(G:Backupimage-typora-masterimage-20230125153350210.png)]](https://bcxiaobai.eu.org/wp-content/themes/CorePress/static/img/loading.gif)
下面解释未进行剪枝操作的决策树为何如上图所示。
不对解释每个结点和分支，仅重点解释为何先由属性「脐部」来划分类别，以及「脐部」=凹陷后只需要按「色泽」划分，不再需要按其他的属性划分。
根结点包含所有训练集
D
D
D，共计
1
、
2
、
3
、
6
、
7
、
10
、
14
、
15
、
16
、
17
{1、2、3、6、7、10、14、15、16、17}
1、2、3、6、7、10、14、15、16、17 的10个样例，其中正例占比=反例占比=5/10。故，根结点的信息熵：
E
n
t
=
−
∑
k
=
1
2
p
k
log
2
p
k
=
1
Ent=-sum ^{2}_{k=1}p_{k}log _{2}p_{k}=1
Ent=−∑k=12pklog2pk=1。
若以属性「色泽」为类别划分的属性，得：
| 色泽 | 训练样例 | 正例
p 1 p_1 p1 |
反例
p 2 p_2 p2 |
信息熵
E n t ( D i ) Ent(D^i) Ent(Di) |
|
|---|---|---|---|---|---|
|
D 1 D^1 D1 |
青绿 |
{ 1 , 6 , 10 , 17 } {1,6,10,17} {1,6,10,17} |
2/4 | 2/4 | 1 |
|
D 2 D^2 D2 |
乌黑 |
{ 2 , 3 , 7 , 15 } {2,3,7,15} {2,3,7,15} |
3/4 | 1/4 | 0.811 |
|
D 3 D^3 D3 |
浅白 |
{ 14 , 16 } {14,16} {14,16} |
0 | 1 | 0 |
信息增益：
G
a
i
n
(
D
,
色泽
)
=
E
n
t
(
D
)
−
∑
v
=
1
3
∣
D
v
∣
∣
D
∣
E
n
t
(
D
v
)
=
1
−
(
4
10
∗
1
+
4
10
∗
0.811
+
2
10
∗
0
)
=
0.2756
Gain(D, 色泽)=Ent(D)-sum ^{3}_{v=1} dfrac{rvert D^v rvert}{rvert D rvert}Entleft( D^{v}right)=1-(dfrac{4}{10}*1+dfrac{4}{10}*0.811+dfrac{2}{10}*0)=0.2756
Gain(D,色泽)=Ent(D)−∑v=13∣D∣∣Dv∣Ent(Dv)=1−(104∗1+104∗0.811+102∗0)=0.2756
同理，计算出其他属性的信息增益，根蒂：0.1145；敲声：0.1735；纹理：0.1735；脐部：0.2756；触感：0。属性「脐部」和「色泽」的信息增益同样大，可任选其一的「脐部」作为划分属性。
此外，当「脐部」=凹陷时，训练样例为D’={1,2,3,14}，「色泽」=青绿、乌黑、浅白的训练样例分别为：{1}、{2,3}、{14}，各类中类别相同无需再划分。
树的剪枝–预剪枝与后剪枝
剪枝（pruning）可以应对过拟合，剪枝处理分为预剪枝（prepruning）和后剪枝（post-pruning）。
| 剪枝 | 特点 | 优点 | 缺点 |
|---|---|---|---|
| 预剪枝 | 决策树生成过程中，对每个结点划分前进行估计，若划分不能提升决策树泛化性能，则不划分 | 边生成决策树边确定是否划分，可减少决策树的训练时间和测试时间 | 存在欠拟合的风险，即有些划分可能当前不利于模型性能，但后续划分可能有利于模型 |
| 后剪枝 | 生成决策树后，自底向上对非叶结点考察，若取消划分能提升决策树泛化性能，则取消 | 欠拟合风险小。通常比预剪枝保留更多分支，泛化性能更优 | 因是生成决策树后再剪枝，训练和测试时间更多 |
下面借助预剪枝中是否对根结点按属性「脐部」来划分和是否对「脐部」=凹陷的训练样本按色泽来划分，理解预剪枝和后剪枝的过程。
是否对根结点按属性「脐部」来划分：
- 不按「脐部」来划分后，因为训练集中好、坏瓜类别个数相等，所以可选择好瓜作为类别标记，则对于单结点的决策树，验证集中编号
{
4
,
5
,
8
}
{4,5,8}
{4,5,8} 样例被划分正确，验证集精度为3
/
7
3/7
3/7。 - 按「脐部」来划分，验证集中正确分类的编号是：
{
4
,
5
,
8
,
11
,
12
}
{4,5,8,11,12}
{4,5,8,11,12}，错误分类的编号是：{
13
,
9
}
{13,9}
{13,9}，故精度为5
/
7
5/7
5/7。
因此，按「脐部」划分可提升验证集精度。
是否对「脐部」=凹陷的训练样本按色泽来划分：划分前后验证集精度下降，故不划分，具体如下图所示。
注意：确定是否按「色泽」划分时，验证集中确定分类的编号要考虑「脐部」=稍凹和平坦中正确的编号。
参考文章或视频：