决策树的剪枝算法
Last updated
Last updated
输入: ID3或C4.5的决策树 参数a 输出: 剪枝后的决策树$T_a$
从树的根结点开始
如果该结点的孩子中存在子树(不全是叶子结点),则先对子树做prune
所有子树都prune之后,再判断该结点的孩子是否都是叶子
如果不全是叶子,对该结点的算法结束
如果该结点的孩子都是叶子,则尝试对该结点剪枝
5.a 计算$C_a(T_B)$,代表该结点split后以该结点为根结点的子树的损失,其损失的计算方式与整棵树的计算方式相同
因此在生成树的时候为每个叶子结点保存它的$N_t$和$H_t$
5.b 计算$C_a(T_A)$,代表该结点split之前作为一个叶子结点时的熵。因此在生成树时记录该split之前的熵
5.c 比较$C_a(T_B)$和$C_a(T_A)$,如果$C_a(T_A)\le C_a(T_B)$,则将该结点修改为叶子结点。即:计算该结点的输出标记,并删除它的所有孩子结点。
对该结点的处理结束,由于这个算法是递归调用的,如果该结点有父结点,则要继续处理它的父结点。
【?】如何通过DP实现