自顶向下决策树增量剪枝方法研究

摘要

决策树学习作为机器学习的一个重要分支，目前已经成功应用于多个领域之中。但是由于有限样本学习自身的不足，使得在决策树学习过程中容易出现过度拟合现象，严重影响了决策树学习的效果。为了克服决策树学习中的种种缺陷，一般采用决策树剪枝算法作为决策树学习算法的后续步骤对生成的决策树进行优化。
　　目前常用的决策树剪枝算法大部分基于统计学分析。由于具有较少样本的训练样例集合统计学特性不明显，容易发生改变，所以导致剪枝策略失效。在总结分析前人工作的基础上，本文提出了一种新的决策树剪枝算法。该算法以增量学习为基础，通过比较确定规则和偶然规则在信息增益变化过程中的差异，最终达到保留必然规则，去除偶然规则的目的。此外为了加快决策树剪枝过程的处理速度，算法定义了自顶向下的搜索次序，避免了对同一决策子树的迭代处理。
　　自顶向下的决策树增量剪枝方法不完全依赖训练样例集合的统计学特性，所以受训练样例数目的影响较小。通过与多种常见决策树剪枝算法的实验比较，证实了算法的正确性和有效性。

目录

封面

声明

中文摘要

英文摘要

目录

第 1 章 绪 论

1.1 课题的研究背景

1.2 课题的研究现状

1.3 课题的研究内容

1.4 本论文的组织结构

第 2 章 决策树及其学习算法

2.1 分类问题概述

2.2 决策树

2.3 决策树表示

2.4 基本的决策树学习方法

第 3 章 决策树剪枝算法

3.1 决策树剪枝算法

3.2 决策树后剪枝方法的分析

第 4 章 自顶向下的决策树增量剪枝

4.1 算法概述

4.2 实验数据

4.3 实验比较

第 5 章 总结与展望

参考文献

致谢