【作者】 裴小兵；

【导师】 王元珍；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2006， 博士

【摘要】 粗糙集方法是一种能有效地分析和处理不精确、不一致、不完整等各种不确定性信息的数据分析工具。该方法近年日益受到国际学术界的重视,已经在模式识别、机器学习、决策支持、知识发现、故障诊断、预测建模等领域得到成功的应用。知识约简是粗糙集方法的核心问题之一,是粗糙集应用的关键技术,也是知识发现的重要研究课题,已成为一个备受关注的研究热点。有效、快速的知识约简算法是粗糙集方法应用的基础,也是粗糙集方法规模应用的保障。围绕知识约简中的三个重要问题即属性约简、决策规则获取以及基于知识约简的知识发现工具,开展了五个方面的研究工作:信息系统的属性约简、相容决策系统的属性约简、不相容决策系统的属性约简、决策规则获取和基于知识约简的知识发现工具的研究。Skowron分明矩阵法在粗糙集方法中占有重要的地位,但它需要数据集中才能进行属性约简。人们借鉴它的相关结论和思想对粗糙集的知识约简进行了研究,但缺乏对算法本身做进一步的研究。对Skowron分明矩阵法进行了扩展,提出了扩展分明矩阵和扩展分明函数概念,并在此基础上提出了扩展分明矩阵的属性约简方法,称做扩展分明矩阵法。针对现有信息系统绝对属性约简算法的低效性和不能适应对象集变化的情形,通过分析对象集的增加与属性约简的变化关系,给出了信息系统增量式绝对属性约简的理论基础,并在此基础上提出了增量式绝对属性约简算法,算法克服了传统相应算法的不足。现有相容决策系统的相对属性约简算法在算法效率和算法完备性等方面都没有得到很好解决。针对这些问题,给出了全部相对属性约简的判定定理,采用在已有约简集的基础上计算新的约简集的思想,提出了一种全部相对属性约简算法,并通过实验证明了算法是高效的;给出了属性集相对分类能力的定义,证明了该定义的合理性,提出了一种最优相对属性约简的启发式算法,证明了算法是完备的,并从理论和实验两方面证明了算法是高效的。为了克服现有不相容决策系统属性约简算法效率低下的问题,研究了最大分布约简、分布约简和可能约简的理论基础,提出了一种全部最大分布约简、分布约简和可能约简算法,并通过实验证明了算法的高效性;为了弥补不相容决策系统最优属性约简算法研究成果的匮乏,给出了最大分布约简、分布约简和可能约简的等价定义,在此基础上给出了属性重要性度量,提出了最优最大分布约简、分布约简和可能约简的启发式算法,并证明了算法是有效的。为了提高现有决策规则获取算法的效率,采取一边计算构成等价类的相对分明函数的合取范式,一边通过该合取范式与已有的规则集计算出新的规则集,提出了一种改进的决策规则获取算法,并证明了改进的合理性。以上述提出的知识约简算法为基础,设计了基于知识约简的知识发现工具。更多还原

【Abstract】 The rough set community, which is an excellent data analysis tool to handle uncertain information, such as imprecise, inconsistent, incomplete and so on, is one of the hardest fields. It has received much attention of the researchers around the world. Rough set community has been applied to many areas successfully including pattern recognition, machine learning, decision support, knowledge discovery, fault diagnosis, forecast modeling and so on. Knowledge reduction is one of the basic contents in rough set community, key technology of rough set community applied and important research contents in knowledge discovery, becoming one of the hottest research fields. Efficient and effective algorithms for knowledge reduction are the foundation of rough set community applied, also the guarantee of rough set community applied on a large scale. Surrounding the three key problems of knowledge reduction, i.e. attribute reduction, decision rule mining and the knowledge discovery tool based on knowledge reduction, the following five works have been done: attribute reduction in information system, attribute reduction in consistent decision system, attribute reduction in inconsistent decision system, decision rule mining and knowledge discovery tool based on knowledge reduction.Skowron’s discernible matrix method is one of import concepts in rough sets community, it require the set of data must be centralized. Many results have been obtained based on it, but there is no more research on it-self. Therefore, the concepts of extended discenibility matrix and extended discernibility function are introduced, from which Skowron’s discernible matrix method is extended, called extended discenibility matrix method.In order to overcome the drawbacks of the existing algorithms in inefficient and inadaptable the case of increase object. The relationship between increase of objects and attribute reductions are analyzed, the judgment theorem for the set of all absolute attribute reductions in information system is obtained, from which an incremental algorithm for the set of all absolute attribute reductions is proposed.There are some drawbacks of the existing relative attribute reduction algorithms in consistent decision system, such as their efficient and completeness. In order to overcome those drawbacks, the judgment theorem with respect to the set of all relative attribute reductions is obtained. Based on calculating the set of all relative reductions by the set of relative reductions, which have been calculated, from which an algorithm for the set of all relative reductions is proposed and its efficient is proved by expierment; A concept of relative discernibility is introduced based on a viewpoint that knowledge is an ability of classing thing, and prove the concept reasonableness, from which an algorithm for the optimal attribute reduction is developed. In addition, the proof of completeness of this algorithm is given. Theoretical analysis and experimental results show that the algorithm is better than those existing algorithm.In order to improvement the efficiency of attribute reduction algorithm in inconsistent decision system, the theory foundation of maximum distribution reduction, distribution reduction and possible reduction is obtained, from which the approaches to the set of all maximum distribution reduction, distribution reduction and possible reduction are presented. In addition, its efficient is proved by experiment. In order to reinforce the optimal attribute reduction algorithm in inconsistent decision system, the equivalence definitions with respect to maximum distribution reduction, distribution reduction and possible reduction are introduced, and the significance of attribute is defined, from which the heuristic algorithms for the optimal maximum distribution reduction, distribution reduction and possible reduction are proposed. Finally, the experimental results show that the algorithm is effective.There are some drawbacks of the existing learning algorithm for decision rules, such as their inefficient. In order to overcome those drawbacks, one side calculates the conjunctive normal form of discernible function for equivalence class, the other side calculates the new rules from the conjunctive normal form and the rules, which has been calculated, from which an improved learning algorithm for decision rules is proposed, and its reasonableness is proved by experiment.Based on the algorithms for knowledge reduction above, a knowledge discovery tool is designed.更多还原