决策树过拟合问题研究

摘要

数据库知识发现是(Knowledge Discovery in Databases，简称KDD)是当前涉及人工智能和数据库等学科的一门相当活跃的研究领域，分类是其中的一个重要研究方向。决策树是分类中常用的模型之一，自1966年被提出以来已经得到了广泛的研究和应用。然而，由于种类偏见，过拟合等问题，使决策树优化成为研究人员关注的热点。 本文基于针对可疑实例分析以及结点纯度差变化趋势两个方面分别对决策树构造算法中的过拟合问题处理展开研究，主要工作如下： 1.综述并分析了现有决策树经典算法及主要优化算法。 2.提出了基于可疑实例影响度分析的改进的C4.5rules算法，将可疑实例进行有效划分，并计算其全局影响度大小，使得分类规则能有效避开可疑实例而更加正确的反应数据的真实情况。 3.针对传统决策树过拟合现象普遍且大多数预剪枝算法严重依赖领域知识的问题，提出基于结点纯度差(PDN，Purity Distance of Node)变化趋势的决策树优化算法，通过跟踪相邻父子结点间的最大纯度差变化趋势，判定停止建树的时机，可以独立于领域知识实现有效的预剪枝并很好地控制了过拟合的发生，同时大大减小了决策树规模。 4.基于上述研究，实现了原型系统，从理论和实验上证明了所提出的算法的正确性和有效性。

目录

文摘

英文文摘

论文说明：图表目录

声明

致谢

第一章绪论

1.1数据挖掘

1.1.1数据挖掘的发展

1.1.2数据挖掘的模式

1.1.3数据挖掘面临的挑战

1.2分类简介

1.2.1分类研究现状

1.2.2常用的分类模型

1.3本文的课题来源及主要内容及组织

1.4小结

第二章决策树分类算法及其优化方法综述

2.1基于决策树的经典分类算法

2.1.1 CLS算法

2.1.2 ID3算法

2.1.3 C4.5算法

2.1.4 CART算法

2.1.5 SLIQ算法

2.2决策树优化研究概述

2.2.1改进测试属性选择方法

2.2.2修改测试属性空间

2.2.3对数据进行限制

2.2.4属性离散化

2.2.5剪枝

2.2.6改变数据结构

2.2.7多方法融合

2.2.8其它优化方法

2.3小结

第三章基于可疑实例影响度分析的决策树优化研究

3.1可疑实例辨别及其对全局影响度研究概述

3.2基于可疑实例影响度分析的改进的C4.5rules算法

3.2.1经典的C4.5rules算法

3.2.2基于可疑实例影响度度量的改进的C4.5rules算法

3.2.3实验分析

3.3 小结

第四章基于PDN变化趋势的决策树优化研究

4.1过度拟合及剪枝

4.2基于PDN变化趋势的预剪枝方法

4.2.1算法描述

4.2.2关键代码

4.3实验

4.3.1试验效果图

4.4小结

第五章实验系统简介

5.1引言

5.2系统结构及实现

5.2.1系统主界面

5.2.2数据导入模块

5.2.3决策树算法模块

5.3主要函数介绍

5.4实验数据

5.5小结

第六章结束语

6.1本文总结

6.2工作展望

参考文献

研究生期间主要科研工作及成果