决策树优化策略

1、剪枝优化是什么？

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

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

后置剪枝

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

2、决策树剪枝过程

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

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

\[loss = \sum_{t=1}^{leaf} \frac{D_t}{D}H(t)\ \ \ 公式1.1\]

那么我们剪枝需要把所有的可能都剪一边么，显然不能。这里就引入了剪枝系数来判别每次剪枝选择哪个节点：首先我们明确，剪枝系数的目的为，平衡准确度和树的节点数量之间的关系。所以很自然的想到我们常用的处理手法，在损失函数中引入叶子结点的变量，得到公式1.2。 注：这种思路我们在LR算法中也用了，生成了Ridge和LASSO

\[loss_{\alpha} = loss + \alpha*leaf\ \ \ \ 公式1.2\]

假定剪枝前的损失函数为$loss(R)$，剪枝后的损失函数为$loss(r)$，由于我们是想让剪枝前后的准确率尽量不变，所以让剪枝前后的损失函数相等，化简得公式1.3，即剪枝系数。注：多次剪枝后为根节点，所以$r=1$。

\[\alpha = \frac{loss(r)-loss(R)}{R_{leaf}-1}\ \ \ \ 公式1.3\]

那么这个系数怎么用呢，答案就是由于我们想尽量减去的叶子结点多点，又同时保持准确度，故剪枝系数越小越好。

3、结语

我们可以看到，到了这里算法开始就有了集成学习的特点了，算法开始从简单的单一的算法进行进化和融合，最终像搭积木一样慢慢完成了后期特别复杂的算法。 BTW，这里使用的算法其实大部分代码实现（不是使用别人写好的函数），可以在《机器学习实战》中找到。