决策树优化策略

1、剪枝优化是什么?

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

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

后置剪枝

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

2、决策树剪枝过程

1
2
3
4
5
6
7
8
9
10
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,这里使用的算法其实大部分代码实现(不是使用别人写好的函数),可以在 《机器学习实战》 中找到。

  • 本文作者: Author:DeamoV
  • Github:https://github.com/VDeamoV
  • Email:vincent.duan95@outlook.com
  • 本文链接: Artical: 决策树优化策略
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
  • 版权声明: 原创文章如转载,请注明出处