粗糙集理论研究.doc
约46页DOC格式手机打开展开
粗糙集理论研究,页数 46 字数 26415摘要硕士学位研究成果粗糙集理论是一种新的处理模糊和不确定知识的软计算工具。它能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律，近年来在机器学习、数据挖掘等多个领域得到广泛应用。粗糙集是知识获取的一种方法。作为当前的研究热点，在知识获...
内容介绍
此文档由会员 天缘 发布
粗糙集理论研究
页数 46 字数 26415
摘要
硕士学位研究成果
粗糙集理论是一种新的处理模糊和不确定知识的软计算工具。它能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律，近年来在机器学习、数据挖掘等多个领域得到广泛应用。
粗糙集是知识获取的一种方法。作为当前的研究热点，在知识获取的研究中尚存在一些问题未能解决，我们对其中两个主要问题——求核问题和增量式知识获取模型进行了研究和讨论，得到了较好的结果。
属性约简是知识获取中最重要的部分之一。决策表核属性的确定往往是信息约简过程的出发点和关键。以前的可辨识矩阵求核算法由于忽略了某些因素而产生错误结果，叶东毅在新的求核算法中虽然把错误改正了，但算法复杂度明显提高。本文在定义的合并规则的基础上提出一种求核算法，该算法不仅改正了以前可辨识矩阵求核法的错误，而且在性能上优于叶东毅和Hu Xiaohua的求核算法。
近几年在粗糙集理论研究中对求解属性的最小约简或较小约简以及求取最简规则集[1～3]的算法已经进行了一些研究，但这些研究都是针对静态数据的。而数据库是动态的，因此许多研究者建议[4～6]，数据库知识发现算法应该是增量式的。属性最小约简的增量式算法以及增量式更新概念格的算法已经开始被研究，但对于增量式的知识获取算法的研究工作还比较少。在以上工作的基础上，本文研究了增量式知识获取问题，发现当把知识的树结构和粗糙集的知识获取思想进行结合后，对于增量式学习的数据可以取得好的学习效果。在此基础上，我们提出基于粗糙集和规则树的增量式知识获取算法(RRIA)。实验表明，RRIA比传统粗糙集知识获取算法不仅具有更快的学习速度，而且生成的规则对样本的识别率可以达到甚至超过传统粗糙集知识获取算法；同时，我们还把RRIA算法与ID4算法进行了比较测试，结果表明RRIA算法无论规则的质量还是正确识别率都优于ID4算法。
关键词： 粗糙集，核属性，知识约简，可辨识矩阵，规则树，判定树 增量式学习
目 录
第一章 绪论 1
1.1引言 1
1.2 粗糙集理论及应用的发展状况 1
1.3 论文背景及工作内容 2
1.4 论文组织与结构 4
第二章 粗糙集理论基础 4
2.1引言 4
2.2 粗糙集的基本概念 4
2.2.1知识和不分明关系 4
2.2.2粗糙集与近似 5
2.2.3近似精度 6
2.3决策表、约简、核 6
2.3.1决策表 6
2.3.2约简与核 7
2.4可辨识矩阵 8
2.5属性重要性 9
2.6 规则集 10
2.7 小结 10
第三章 基于合并规则的决策表求核方法 5
3.1 引言 5
3.2 合并规则及其性质 5
3.3 S与S/在求核问题上的等价性分析 6
3.4 基于记录合并的属性求核算法 8
3.4.1 基于记录合并的属性求核算法 8
3.4.2 算法复杂度分析 9
3.5 实验结果 10
3.6 小结 11
第四章 基于粗糙集和规则树的增量式知识获取算法 12
4.1 增量式知识获取算法讨论 12
4.1.1引言 12
4.1.2 一般值约简算法[21] 12
4.1.3 归纳值约简算法[21] 13
4.1.4 ID3、ID4和ID5R算法[15,16] 13
4.1.5 概念格上规则提取的渐进式算法[20] 18
4.1.6 几种增量式学习算法的比较 20
4.2 基于粗糙集和规则树的增量式知识获取算法 21
4.2.1 引言 21
4.2.2 规则树 21
4.2.3算法的几个策略 22
4.2.4 算法描述 25
4.2.5算法复杂度分析 25
4.2.6 算法性能分析 26
4.3 RRIA算法测试 26
4.3.1引言 26
4.3.2 测试1：RRIA和粗糙集非增量式知识获取算法的比较测试 26
4.3.3测试2：RRIA和ID4算法的比较 27
4.4 小结 28
第五章 结论 30
致谢 31
参考文献 32
参考文献
[1] Hu，X. H.，Cercone，N.，Learning in Relational Databases: A Rough Set Approach. Inter. J. of Computational Intelligence，11(2)，pp.323~338，1995。
[2] Jelonek，Krawiec，K.，Slowinski，R.，Rough Set Reduction of Attributes and Their Domains for Neural networks，Computational Intelligence，11(2)，pp. 339~347，1995。
[3] 苗夺谦，Rough Set理论及其在机器学习中的应用研究，中国科学院自动化所博士学位论文，1997.6。
[4] Fayyad，U. M.，Piatetsky-Shapiro，L.，Smyth，P.，Uthurusamy，R.，Advances in Knowledge Discovery and Data Mining，Melno Park，California: AAAI Press/The MIT Press，1996.
[5] Cercone，V.，Tsuchiya，M.，Luesy Editor’s Introduction，IEEE Transations on Knowledge and Data Engineering，5(6)，pp.901~902，1993。
页数 46 字数 26415
摘要
硕士学位研究成果
粗糙集理论是一种新的处理模糊和不确定知识的软计算工具。它能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律，近年来在机器学习、数据挖掘等多个领域得到广泛应用。
粗糙集是知识获取的一种方法。作为当前的研究热点，在知识获取的研究中尚存在一些问题未能解决，我们对其中两个主要问题——求核问题和增量式知识获取模型进行了研究和讨论，得到了较好的结果。
属性约简是知识获取中最重要的部分之一。决策表核属性的确定往往是信息约简过程的出发点和关键。以前的可辨识矩阵求核算法由于忽略了某些因素而产生错误结果，叶东毅在新的求核算法中虽然把错误改正了，但算法复杂度明显提高。本文在定义的合并规则的基础上提出一种求核算法，该算法不仅改正了以前可辨识矩阵求核法的错误，而且在性能上优于叶东毅和Hu Xiaohua的求核算法。
近几年在粗糙集理论研究中对求解属性的最小约简或较小约简以及求取最简规则集[1～3]的算法已经进行了一些研究，但这些研究都是针对静态数据的。而数据库是动态的，因此许多研究者建议[4～6]，数据库知识发现算法应该是增量式的。属性最小约简的增量式算法以及增量式更新概念格的算法已经开始被研究，但对于增量式的知识获取算法的研究工作还比较少。在以上工作的基础上，本文研究了增量式知识获取问题，发现当把知识的树结构和粗糙集的知识获取思想进行结合后，对于增量式学习的数据可以取得好的学习效果。在此基础上，我们提出基于粗糙集和规则树的增量式知识获取算法(RRIA)。实验表明，RRIA比传统粗糙集知识获取算法不仅具有更快的学习速度，而且生成的规则对样本的识别率可以达到甚至超过传统粗糙集知识获取算法；同时，我们还把RRIA算法与ID4算法进行了比较测试，结果表明RRIA算法无论规则的质量还是正确识别率都优于ID4算法。
关键词： 粗糙集，核属性，知识约简，可辨识矩阵，规则树，判定树 增量式学习
目 录
第一章 绪论 1
1.1引言 1
1.2 粗糙集理论及应用的发展状况 1
1.3 论文背景及工作内容 2
1.4 论文组织与结构 4
第二章 粗糙集理论基础 4
2.1引言 4
2.2 粗糙集的基本概念 4
2.2.1知识和不分明关系 4
2.2.2粗糙集与近似 5
2.2.3近似精度 6
2.3决策表、约简、核 6
2.3.1决策表 6
2.3.2约简与核 7
2.4可辨识矩阵 8
2.5属性重要性 9
2.6 规则集 10
2.7 小结 10
第三章 基于合并规则的决策表求核方法 5
3.1 引言 5
3.2 合并规则及其性质 5
3.3 S与S/在求核问题上的等价性分析 6
3.4 基于记录合并的属性求核算法 8
3.4.1 基于记录合并的属性求核算法 8
3.4.2 算法复杂度分析 9
3.5 实验结果 10
3.6 小结 11
第四章 基于粗糙集和规则树的增量式知识获取算法 12
4.1 增量式知识获取算法讨论 12
4.1.1引言 12
4.1.2 一般值约简算法[21] 12
4.1.3 归纳值约简算法[21] 13
4.1.4 ID3、ID4和ID5R算法[15,16] 13
4.1.5 概念格上规则提取的渐进式算法[20] 18
4.1.6 几种增量式学习算法的比较 20
4.2 基于粗糙集和规则树的增量式知识获取算法 21
4.2.1 引言 21
4.2.2 规则树 21
4.2.3算法的几个策略 22
4.2.4 算法描述 25
4.2.5算法复杂度分析 25
4.2.6 算法性能分析 26
4.3 RRIA算法测试 26
4.3.1引言 26
4.3.2 测试1：RRIA和粗糙集非增量式知识获取算法的比较测试 26
4.3.3测试2：RRIA和ID4算法的比较 27
4.4 小结 28
第五章 结论 30
致谢 31
参考文献 32
参考文献
[1] Hu，X. H.，Cercone，N.，Learning in Relational Databases: A Rough Set Approach. Inter. J. of Computational Intelligence，11(2)，pp.323~338，1995。
[2] Jelonek，Krawiec，K.，Slowinski，R.，Rough Set Reduction of Attributes and Their Domains for Neural networks，Computational Intelligence，11(2)，pp. 339~347，1995。
[3] 苗夺谦，Rough Set理论及其在机器学习中的应用研究，中国科学院自动化所博士学位论文，1997.6。
[4] Fayyad，U. M.，Piatetsky-Shapiro，L.，Smyth，P.，Uthurusamy，R.，Advances in Knowledge Discovery and Data Mining，Melno Park，California: AAAI Press/The MIT Press，1996.
[5] Cercone，V.，Tsuchiya，M.，Luesy Editor’s Introduction，IEEE Transations on Knowledge and Data Engineering，5(6)，pp.901~902，1993。
