基于遗传算法的决策树剪枝方法

论文摘要

决策树剪枝是决策树优化的常用方法。在保持决策树分类精度的前提下,该方法通过去掉决策树中某些子树的方法,达到减小决策树规模的目的。目前的决策树剪枝方法按照一定顺序遍历决策树包含的所有子树,以决策树的分类精度或者规模为依据决定子树是否应该被移除,因此剪枝效率较低且存在着一定的剪枝偏置。本文提出了一种两阶段的决策树剪枝方法。其中第一阶段使用遗传算法对剪枝决策树空间进行搜索,来构造当前最优决策树集合；第二阶段综合决策树的分类精度,规模和稳定性三方面因素,从当前最优决策树集合中找到一棵决策树作为最优剪枝后决策树。基于遗传算法的决策树剪枝方法由于采用多标准评价决策树子树,克服了原有剪枝算法的偏置。同时引入遗传算法来加速剪枝决策树空间的搜索速度。在多个UCI数据库上的实验结果表明,使用该方法得到的决策树很好的平衡了决策树分类精度和规模之间的关系,使得剪枝后的决策树具有良好的分类性能。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景与意义
• 1.2 国内外研究现状
• 1.3 研究内容
• 1.4 论文组织
• 第2章 决策树学习
• 2.1 基本的决策树学习算法
• 2.1.1 分割属性的选择
• 2.1.2 决策树的停止标准
• 2.1.3 叶子节点的类别标签
• 2.2 决策树的解释
• 2.3 决策树分类精度的评估
• 2.4 本章小结
• 第3章 决策树剪枝算法
• 3.1 决策树的过度拟合现象
• 3.2 决策树剪枝方法
• 3.2.1 预剪枝方法
• 3.2.2 后剪枝方法
• 3.3 决策树后剪枝方法的分析
• 3.3.1 代价复杂度剪枝
• 3.3.2 减小错误率的剪枝
• 3.3.3 悲观错误剪枝
• 3.3.4 规则后剪枝
• 3.3.5 后剪枝算法的比较
• 3.4 本章小结
• 第4章 基于遗传算法的决策树剪枝算法
• 4.1 决策树剪枝中的假设空间搜索
• 4.2 遗传算法
• 4.2.1 算法综述
• 4.2.2 遗传算法框架
• 4.3 评价决策树的标准
• 4.3.1 分类精度
• 4.3.2 稳定性
• 4.3.3 规模
• 4.3.4 综合评价
• 4.4 两阶段剪枝过程
• 4.4.1 最优决策树集合构造
• 4.4.2 决策树的表示
• 4.4.3 适应度函数的表示
• 4.4.4 遗传算子
• 4.4.5 最优剪枝树的选择
• 4.5 实验结果及分析
• 4.6 本章小结
• 第5章 总结与展望
• 参考文献
• 致谢
• 攻读学位期间取得的科研成果