基于粗糙集和灰色理论的决策树算法研究

摘要

在决策树分类算法的实际应用中，由于数据集本身经常存在着属性值缺失或包含冗余属性较多的情况，同时现有的决策树分支属性选择方法容易产生过多的规则，这些往往导致生成的决策树规模较大。因此，进一步改进决策树算法，使其更加适合数据挖掘的应用要求，具有重要的理论和现实意义。
　　 本文从属性值缺失的填补、属性约简和决策树分支属性选择三方面进行研究。
　　 第一，由于基于K近邻算法的属性值缺失填补算法中没有考虑填补后是否会导致数据冲突的现象；对K值的选取需多次尝试，但未必取到最优值；而且有些填补是在整个数据集中进行的，这在实际应用中可能会导致填补的数据出现严重错误。针对上述缺陷，本文利用灰色理论和粗糙集理论相结合得到GRFill(Grey theory Rough set put)属性值缺失填补算法，并实现了平均值填补法和基于欧式距离的最近邻填补法，填补完成后通过根均方误差RMSE(Root Mean Squared Error)的大小及C4.5算法生成的决策树的预测准确率来比较GRFill填补算法与上述两种算法的填补效果。
　　 第二，针对传统的基于区分矩阵的属性约简算法的时间及空间复杂度高的缺点进行改进，实现了删除冗余属性且对决策树性能有所改进的RSredu(RoughSet reduct)属性约简算法。
　　 第三，利用粗糙集理论定义条件属性与决策属性的分类关系，得到了利用条件属性与决策属性分类一致性大小作为分支属性选择标准的RDTree(RoughSet Decesion Tree)决策树算法。
　　 实验结果表明，GRFill填补算法的根均方误差RMSE小于平均值填补法和基于欧式距离的最近邻填补法，分类预测准确率高于平均值填补法和基于欧式距离的最近邻填补法；经过RSredu属性约简算法约简后再进行决策树分类，减小了决策树的规模；利用条件属性与决策属性的分类一致性大小作为分支属性选择标准的RDTree决策树算法生成的决策树叶子数及总节点数少于C4.5算法，准确率及平均运行时间与C4.5算法相近。最后，将上述三点研究结合得到组合优化的RGDTree(RoughSet Gray theory Decesion Tree)决策树分类算法，并在WEKA平台上实现，利用UCI标准数据集和FoodMart2000中的数据样本对RGDTree算法的分类性能进行验证，结果表明，本文所做的研究有利于决策树分类器性能的改进。

目录

文摘

英文文摘

声明

第1章 绪论

1.1课题研究的背景与意义

1.2国内外研究现状

1.2.1决策树分类算法的研究现状

1.2.2基于粗糙集的数据挖掘研究现状及发展

1.2.3基于灰色理论的数据挖掘研究现状及发展

1.3本文的研究内容

1.4本文的组织结构

第2章 相关理论及WEKA平台

2.1决策树分类算法的基本理论

2.1.1决策树生成过程

2.1.2决策树算法的主要研究内容

2.1.3决策树分类算法的评价指标

2.1.4常见的决策树分类算法比较

2.2粗糙集的相关原理和定义

2.3灰色理论

2.3.1灰色系统概念

2.3.2灰色关联分析法

2.4 WEKA平台

2.4.1 WEKA数据格式

2.4.2 WEKA图形用户界面

2.4.3 WEKA数据挖掘流程

第3章 基于灰色理论和粗糙集的数据预处理

3.1基于粗糙集和灰色理论的属性值缺失填补

3.1.1属性值缺失形成的原因及填补的重要性

3.1.2属性值缺失处理方法

3.1.3 GRFill属性值缺失填补方法

3.2基于粗糙集的属性约简算法研究

3.2.1常见的属性约简算法

3.2.2改进的基于区分矩阵的属性约简算法

第4章 基于粗糙集的分支属性选择

4.1基于粗糙集的属性选择方法

4.1.1基于属性相似度的决策树生成算法

4.1.2基于粗糙集的属性选择标准

4.1.3分类一致性定义

4.1.4 RDTree算法基本思路及描述

4.1.5 RDTree算法实例

4.1.6实验与结果分析

第5章 WEKA平台上组合算法的实现与应用

5.1 RGDTree算法实现

5.1.1 RGDTree算法主要成员方法

5.1.2 RGDTree算法流程

5.1.3 RGDTree算法在WEKA上的实现

5.2 RGDTree算法在UCI数据集上分析测试

5.3 RGDTree算法在实际数据样本中的应用

5.3.1数据样本

5.3.2实验与结果分析

总结与展望

致谢

参考文献

攻读硕士学位期间发表的论文