文章目录
本课程来自深度之眼，部分截图来自课程视频以及李航老师的《统计学习方法》第二版。
公式输入请参考： 在线Latex公式
导入
模型常常会出现过拟合的现象，造成过拟合的原因有：
1.训练epoch太多（解决方法是早停）
2.模型太复杂（降低模型复杂度：减少参数，网络层数减少，剪枝）
剪枝
1.复杂的模型结构往往可能会造成过拟合的现象。
2.剪枝的目的是在决策树构造结束后，去裁掉部分枝桠以此降低模型复杂度。
后剪枝：生成树之后再剪枝。
预剪枝：在生成树的过程中干预生成过程，使得模型倾向于不生成复杂的模型。
设树
T
T
T的叶节点个数为
∣
T
∣
|T|
∣T∣，
t
t
t是树
T
T
T的叶节点，该叶节点有
N
t
N_t
Nt个样本点，其中
k
k
k类的样本点有
N
t
k
N_{tk}
Ntk个，
k
=
1
,
2
…
,
K
k=1,2…,K
k=1,2…,K。
H
t
(
T
)
H_t(T)
Ht(T)为叶节点
t
t
t上的经验熵
H
t
(
T
)
=
−
[
N
t
1
N
t
log
N
t
1
N
t
+
N
t
2
N
t
log
N
t
2
N
t
+
⋯
+
N
t
k
N
t
log
N
t
k
N
t
]
=
−
∑
k
N
t
k
N
t
log
N
t
k
N
t
H_t(T)=-\left[\cfrac{N_{t1}}{N_t}\log \cfrac{N_{t1}}{N_t}+\cfrac{N_{t2}}{N_t}\log \cfrac{N_{t2}}{N_t}+\cdots+\cfrac{N_{tk}}{N_t}\log \cfrac{N_{tk}}{N_t}\right]\\=-\sum_k \cfrac{N_{tk}}{N_t}\log \cfrac{N_{tk}}{N_t}
Ht(T)=−[NtNt1logNtNt1+NtNt2logNtNt2+⋯+NtNtklogNtNtk]=−k∑NtNtklogNtNtk
α
≥
0
\alpha≥0
α≥0为参数，则决策树学习的损失函数可以定义为：
C
α
(
T
)
=
∑
t
=
1
T
N
t
N
H
t
(
T
)
+
α
∣
T
∣
=
∑
t
=
1
T
N
t
H
t
(
T
)
N
+
α
∣
T
∣
C_\alpha(T)=\sum_{t=1}^T\cfrac{N_t}{N}H_t(T)+\alpha|T|\\ =\cfrac{\sum_{t=1}^TN_tH_t(T)}{N}+\alpha|T|
Cα(T)=t=1∑TNNtHt(T)+α∣T∣=N∑t=1TNtHt(T)+α∣T∣
上式中分母N代表训练集中所有的样本数量，是一个固定值，因此去掉后就和书上的形式是一样的了：
C
α
(
T
)
=
∑
t
=
1
T
N
t
H
t
(
T
)
+
α
∣
T
∣
C_\alpha(T)=\sum_{t=1}^TN_tH_t(T)+\alpha|T|
Cα(T)=t=1∑TNtHt(T)+α∣T∣
这个式子的第一项是希望整棵树的经验熵越小越好，第二项则是希望树的节点越少越好，如果去掉某个节点对整棵树的熵影响不大，则模型倾向去掉这个节点。
α
\alpha
α是惩罚因子。将上式可以写为：
C
α
(
T
)
=
C
(
T
)
+
α
∣
T
∣
C_\alpha(T)=C(T)+\alpha|T|
Cα(T)=C(T)+α∣T∣
剪枝算法
输入：生成算法产生的整个树
T
T
T，参数
α
\alpha
α；
输出：修剪后的子树
T
α
T_\alpha
Tα。
（1）计算每个结点的经验熵。
（2）递归地从树的叶结点向上回缩。
设一组叶结点回缩到其父结点之前与之后的整体树分别为
T
B
T_B
TB与
T
A
T_A
TA，其对应的损失函数值分别是
C
α
(
T
A
)
C_\alpha(T_A)
Cα(TA)与
C
α
(
T
B
)
C_\alpha(T_B)
Cα(TB)，如果
C
α
(
T
A
)
≤
C
α
(
T
B
)
C_\alpha(T_A)\le C_\alpha(T_B)
Cα(TA)≤Cα(TB)
则进行剪枝，即将父结点变为新的叶结点。
（3）返回（2），直至不能继续为止，得到损失函数最小的子树
T
α
T_\alpha
Tα。
这个算法就是要计算剪枝前后树的熵是否有变化，变小则剪枝，否则不剪
如上图所示，要求变化，红圈部分是剪枝前后不变的部分，可以不用计算，只计算剪枝部分。
在这个基础上还有CART算法，不展开。