First

附上我的博客中这个文章的地址

剪枝优化

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

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

后置剪枝

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

决策树剪枝过程

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

其最后用于验的损失函数如下公式1.1：

$loss = \sum_{t=1}^{leaf} \frac{D_t}{D}H(t)$
剪枝系数的引入：
剪枝系数的目的为，平衡准确度和树的节点数量之间的关系。所以很自然的想到我们常用的处理手法，在损失函数中引入叶子结点的变量，得到公式1.2。
$loss_{\alpha} = loss + \alpha*leaf$
设剪枝前的损失函数为 $loss(R)$ ，剪枝后的损失函数为 $loss(r)$ ，由于我们是想让剪枝前后的准确率尽量不变，所以让剪枝前后的损失函数相等，化简得公式1.3，即剪枝系数。注：剪枝后为根节点，所以 $r=1$ 。
$\alpha = \frac{loss(r)-loss(R)}{R_{leaf}-1}$
最后，由于我们想尽量减去的叶子结点多点，又同时保持准确度，故剪枝系数越小越好。