33932a2dc0e5d9a90317f3e47613c155
决策树优化策略

前言

这一章就来填补上一章《决策树&C4.5,ID3,CART》提到的坑,剪枝优化。最近,由于连续打字手腕有点无力,接下来的几天里将会放缓更新速度,不过肯定会负责的把机器学习算法更新完的!

1、剪枝优化是什么?

决策树的剪枝是决策树算法中最基本、最有用的一种优化方案,分为以下两类:

  • 前置剪枝:在构建决策树的过程中,提前停止。这种策略无法得到比较好的结果
  • 后置剪枝:在决策树构建好后,然后开始剪裁,一般使用两种方案。a)用单一叶子结点代替整个子树,也节点的分类采用子树中最主要的分类。b)将一个子树完全替代另一个子树。后置剪枝的主要问题是存在计算效率问题,存在一定的浪费情况。

后置剪枝

后置剪枝的核心思想其实就是交叉验证,其通过对完全树进行剪枝,一直剪到只剩下树根,这样子便得到许多树,随后通过使用数据集分别对他们验证,然后根据结果选择最优树。

2、决策树剪枝过程

while 生成的决策树不为1个节点:
    计算所有内部非叶子节点的剪枝系数;
    选择最小剪枝系数的节点:
        if 有多个最小剪枝系数节点:
            选择包含数据项多的节点删除
        else:
            删除节点
        将剪枝后的树存入之后用的决策树集
for 决策树 in 决策树集:
    用数据集验证决策树,得到最优剪枝后的决策树

其中用于验证决策树的损失函数如下公式 1.1:

top Created with Sketch.