基于粗糙集和规则树的增量式知识获取算法

论文编号:TX051        论文字数:26418,页数:45

摘要
粗糙集理论是一种新的处理模糊和不确定知识的软计算工具。它能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律，近年来在机器学习、数据挖掘等多个领域得到广泛应用。
粗糙集是知识获取的一种方法。作为当前的研究热点，在知识获取的研究中尚存在一些问题未能解决，我们对其中两个主要问题——求核问题和增量式知识获取模型进行了研究和讨论，得到了较好的结果。
属性约简是知识获取中最重要的部分之一。决策表核属性的确定往往是信息约简过程的出发点和关键。以前的可辨识矩阵求核算法由于忽略了某些因素而产生错误结果，叶东毅在新的求核算法中虽然把错误改正了，但算法复杂度明显提高。本文在定义的合并规则的基础上提出一种求核算法，该算法不仅改正了以前可辨识矩阵求核法的错误，而且在性能上优于叶东毅和Hu Xiaohua的求核算法。
近几年在粗糙集理论研究中对求解属性的最小约简或较小约简以及求取最简规则集[1～3]的算法已经进行了一些研究，但这些研究都是针对静态数据的。而数据库是动态的，因此许多研究者建议[4～6]，数据库知识发现算法应该是增量式的。属性最小约简的增量式算法以及增量式更新概念格的算法已经开始被研究，但对于增量式的知识获取算法的研究工作还比较少。在以上工作的基础上，本文研究了增量式知识获取问题，发现当把知识的树结构和粗糙集的知识获取思想进行结合后，对于增量式学习的数据可以取得好的学习效果。在此基础上，我们提出基于粗糙集和规则树的增量式知识获取算法(RRIA)。实验表明，RRIA比传统粗糙集知识获取算法不仅具有更快的学习速度，而且生成的规则对样本的识别率可以达到甚至超过传统粗糙集知识获取算法；同时，我们还把RRIA算法与ID4算法进行了比较测试，结果表明RRIA算法无论规则的质量还是正确识别率都优于ID4算法。

关键词：  粗糙集   核属性  知识约简  可辨识矩阵  规则树   判定树   增量式学习 

Abstract
Rough set theory is emerging as a new tool for dealing with fuzzy and uncertain data. It is very efficient to analyse and process imprecise and imperfect data. It can find potential knowledge and rule from data. In recent years，it has been studied and applied in many fields such as machine learning，data mining and etc.
Knowledge acquision is one of the most important part of rough set，and it is also the focus of researching. There are some problems in knowledge acquisition that need to be solved. We deal with two key problems in this paper，that is，computation of attribute core and incremental aquisition of knowledge.
Attribute reduction is one of the most important parts in knowledge acquisition. The core attributes of a decision table are often the start and key of many information reduction procedures. Hu’s method of computating core attributes based on discernibility matrix was wrong because of ignoring some factors. The error was corrected by Ye Dongyi，but his alogrithm’s complexity was too high. In this paper，we present a new algorithm based on objects，combination. The algorithm corrects Hu’s error and its complexity is lower than Ye’s method and Hu’s method.
In resent years，many rough set based algorithms for computing the smallest or smaller reduction of attributes and knowledge acquisition are developed[1～3]. They are almost based on static data. However，real databases are always dynamic. So，many researchers[4～6] suggest that knowledge acquisition in databases should be incremental. Incremental arithmetic for the smallest reduction of attributes and incremental algorithm of rule extraction based on concept lattice have been developed，but there are few incremental rough set based algorithms about knowledge acquisition. On the basis of former results，we develop a rough set and rule tree based incremental knowledge acquisition algorithm (RRIA) in this paper. Simulation results show that our algorithm can learn more quickly than classical rough set based knowledge acquisition algorithms，and the performance of knowledge learned by our algorithm can be the same as or even better than classical rough set based knowledge acquisition algorithms. Besides，we compare our algorithm with ID4 algorithm. The results show that the rule quality and the recognition rate of our algorithm are both better than ID4.
Key words: Rough Set  Core Attribute  Knowledge Reduction  Discernibility Matrix  Rough set  Independent learning  Knowledge acquisition

目    录
摘要   1
Abstract   2
第一章  绪论  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
第三章 基于合并规则的决策表求核方法  10 
3.1  引言  10
3.2  合并规则及其性质   11
3.3  S与S/在求核问题上的等价性分析  12
3.4  基于记录合并的属性求核算法  14
3.4.1 基于记录合并的属性求核算法  14
3.4.2 算法复杂度分析   15
3.5 实验结果   16
3.6 小结   17
第四章  基于粗糙集和规则树的增量式知识获取算法   18
4.1 增量式知识获取算法讨论  18
4.1.1引言   18
4.1.2 一般值约简算法[21  18
4.1.3 归纳值约简算法[21]   19
4.1.4 ID3、ID4和ID5R算法[15,16]   19
4.1.5 概念格上规则提取的渐进式算法[20]   24
4.1.6 几种增量式学习算法的比较   26
4.2  基于粗糙集和规则树的增量式知识获取算法   27
4.2.1 引言   27
4.2.2 规则树 27
4.2.3算法的几个策略 28
4.2.4 算法描述 31
4.2.5算法复杂度分析  31
4.2.6 算法性能分析  32
4.3 RRIA算法测试   32
4.3.1引言    32
4.3.2 测试1：RRIA和粗糙集非增量式知识获取算法的比较测试   32
4.3.3测试2：RRIA和ID4算法的比较   33
4.4 小结   35
第五章 结论   36
致谢   37
参考文献   38