机器学习15——决策树4（剪枝）

发表: 2019-08-24 浏览: 1439

机器学习

剪枝

为什么要剪枝

决策树算法在生成的过程中，利用递归的方式产生决策树，直到不能继续下去，容易造成对现有的训练数据有很好的分类，但是对未知数据分类不准确，造成了过拟合的现象。

在决策树学习中，将已经生成树进行简化的过程称之为剪枝prunning。简单地说：

去掉某些叶结点或者子树
将上述叶节点的父节点作为新的叶结点

剪枝过程

决策树的剪枝过程，往往就是通过最小化决策树整体的损失函数或者代价函数来实现。损失函数定义为 $C_{\alpha}(T)=\sum _{t=1}^{|T|}N_tH_t(T)+\alpha|T|$ 经验熵为 $H_t(T)=-\sum_k\frac{N_{tk}}{N_t}log\frac{N_{tk}}{N_t}$ 在损失函数中，通常将右端的第一项记为： $C(T)=\sum _{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^{K}N_{tk}log\frac{N_{tk}}{N_t}$ 有 $C_{\alpha}(T)=C(T)+\alpha|T|$

$C(T)$ 表示模型训练数据的预测误差，模型和训练数据之间的拟合程度
$|T|$ 表示模型的复杂程度
控制两者之间的影响
- $\alpha$ 大，模型简单
- $\alpha$ 小，模型复杂
- $\alpha=0$ 表示只考虑模型和训练数据之间的拟合程度，不考虑模型的复杂度

剪枝的过程就， $\alpha$ 确定时，选择损失函数最小的模型，即损失函数最小的子树。

决策树生成和剪枝

生成：
- 通过提高信息增益和信息增益率对训练数据进行更好的拟合；
- 学习局部的模型
剪枝：
- 通过优化损失函数来减小模型的复杂度；
- 学习整体的过程
- 利用损失函数最小原则进行剪枝就是用正则化的极大似然估计来进行模型选择

剪枝算法

输入：生成算法产生的整个数 $T$ ，参数 $\alpha$

输出：修剪后的子树 $T_{\alpha}$

步骤：
- 计算每个节点的经验熵
- 递归地从树的叶结向上回缩
- 满足回缩前后整体树的损失函数： $C_{\alpha}{(T_A)}\leq C_{\alpha}{(T_B)}$ ，则进行剪枝，即原来的父节点变成新的叶结点
- 重复上述操作，直到不能继续为止，得到最小损失函数的子树 $T_{\alpha }$

0 个评论

要回复文章请先登录或注册