《基于属性关联度的启发式约简方法.doc》由会员分享，可在线阅读，更多相关《基于属性关联度的启发式约简方法.doc（36页珍藏版）》请在金锄头文库上搜索。
1、1.本课题所涉及的问题及应用现状综述粗糙集理论中有效算法的研究是粗糙集理论在人工智能研究中的一个主要方向。目前，粗糙集理论中有效算法研究主要集中在规则提取、属性约简算法以及与粗糙集有关的神经网络和遗传算法研究等。属性约简是粗糙集理论的核心问题之一。属性约简的任务就是在保持知识表达系统中分类能力不变的情况下，删除其中不相关或不重要的属性。但是己经证明求解所有约简和求解最小约简都是NP-hard 问题。属性约简与核的求解一直就是粗糙集理论研究的热点与难点。2本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析 粗糙集理论一这种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，
2、便不失为一种处理复杂系统的较为有效的方法。随着信息时代的到来，数据不断增长，并且在很多情况下数据中含有大量的冗余信息和噪声。那么如何从大量的、杂乱无章的、带干扰的数据中挖掘潜在的、有利用价值的信息(知识)，即是寻找最快方法对最普遍、更一般的信息系统的有用知识的提取。在探索的过程中，讨论各种理论支持下的约简方法，比较方法的有效性，并随之将方法在理论的基础上进行推广，逐渐更人性化、更能被人们所理解的处理更一般的信息系统。而粗糙集中分辨矩阵和依赖度两工具，实用性与理解性比较强，可较为有效的用于一般的决策表中。而把依赖空间引入到属性约简(即在依赖空间中对属性约简进行讨论)具有一定的理论和实际意义及应用
3、前景。3.完成本课题的工作方案对粗糙集理论进行研究，理解属性约简的作用与现实意义。了解灰度理论模型，并将此概念能引入到粗糙集理论中，计算其条件决策属性关联度，衡量各条件属性的重要性，以此作为启发式信息，设计相应的约简算法。编程实现一个具体的属性约简系统。 题目应完成的工作方案如下：（1）掌握粗糙集理论中有关数据约减方法的原理；（2）掌握灰色理论模型在粗糙集理论中的应用；（3）选择合适的实验数据集，并设计数据库；（4）设计正确、合理的数据结构；（5）编程实现一个基本的应用系统。 4指导教师审阅意见 指导教师(签字)： 年 月 日说明：本报告必须由承担毕业论文(设计)课题任务的学生在毕业论文(设计
4、) 正式开始的第1周周五之前独立撰写完成，并交指导教师审阅。目录摘要IABSTRACTII1引言12 绪论22.1 粗糙集理论的研究现状22.2 本文的工作42.3 本文的组织43 粗糙集的基础理论53.1 粗糙集理论概况53.1.1 粗糙集的研究对象53.1.2 粗糙集理论的特点53.2 知识与知识库63.3 不可分辨关系与上、下近似集73.4 信息系统93.5 知识的依赖性103.6 属性约简与核114 关联属性约简算法及其改进144.1 分辨矩阵及基于分辨矩阵的算法144.2启发式属性约简算法164.3 算法改进175 基于属性的灰度的属性约简方法205.1 定义与算法205.2 算法实
5、例分析216 研究工作总结与展望266.1研究工作总结266.2 研究工作展望27致谢29参考文献30摘要粗糙集理论是一种处理含糊和不确定性信息的新型数学工具，其理论提出以来得到迅速的发展和广泛的应用。而知识约简是粗糙集理论重要研究内容之一，它的主要目的在于去除数据中的冗余信息，同时保持原决策信息系统的分类能力不变。当出现大量或海量数据时，原有约简方法效率就会变低，所以须对粗糙集约简计算理论进行优化，并且发展完善相关计算算法，以提高知识约简的效率。本文首先基于粗糙集理论，针对知识约简优化计算问题提出了两种知识约简方法，分析了这两种方法之间的关系以及它们的优缺点。并根据关联度以及灰度的理论分析，
6、提出了减少执行时间的改进算法，降低了算法的时间复杂度，并最终完成了实验仿真。根据仿真结果得出结论：虽然经典的基于分辨矩阵的属性约简算法就约简后属性个数而言，比另外两种算法的效率有所提高，但其执行时间要高出很多，尤其当实例数较大时，执行时间会高出数倍左右。该结论有助于改进知识约简的效率，进一步提高粗糙集数据分析能力。关键词：粗糙集，属性约简，差别矩阵，关联度ABSTRACTRough Set Theory is a new mathematical tool to reason about uncertain and vague information. It has been rapidly
7、developed and widely applied in many fields. Reduct is the most important concept in rough set, whose main purpose is to remove the redundant information and preserves classification accuracy of original information system. Facing with huge amounts of data, the old algorithms for reduct is not feasi
8、ble. It is necessary to optimize the computation theory, and proposes some practical algorithms to improve the efficiency of reduct. Based on rough set theory, the thesis mainly focuses on the problems of optimized computation for reduct. In this paper, based on rough set theory for knowledge reduct
9、ion made to optimize the calculation of two methods of knowledge reduction, analysis of the relationship between the two methods and their advantages and disadvantages.And in accordance with gray relational grade, as well as theoretical analysis, to reduce the execution time of the improved algorith
10、m reduces the algorithms time complexity.The simulation results based on the conclusion: Although the classic tell-based matrix attribute reduction algorithm to reduce the number of attributes in terms of after than the other two algorithms to improve efficiency, but its execution time should be muc
11、h higher, especially when larger number of instances, the execution time will be about several times higher. The conclusions help to improve the efficiency of knowledge reduction to further improve the ability of rough set data analysis.KEY WORDS: rough set, reduct discernibility matrix, completenes
12、s, associated- I -基于属性关联度的启发式约简方法1引言随着计算机、网络和通讯等信息技术的高速发展，商务贸易的电子化，政府和企业事务自动化的迅速普及，产生了大规模的数据；同时日益增长的科学计算和大规模的工业生产过程也提供了海量数据。数据丰富、信息贫乏是当今数字化社会面临的一个巨大挑战。在海量数据背后隐藏着许多重要的信息，因此人们希望对其进行更高层次的分析，以便能够更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但是无法发现数据中存在的关系和规则，无法根据现有数据库中的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段和方法。知识发现(Kno
13、wledge Discovery,简称KDD)和数据挖掘(Data Mining，简称 DM)正是在这种情况下产生和发展的一种新型数据分析技术。数据挖掘是知识发现过程中的核心步骤，粗糙集(Rough Set)理论作为一种应用于数据挖掘中的数学工具有着它不可替代的优点。属性约简(Attribute Reduction)是粗糙集理论中一个重要的研究课题。一般说来，数据库中的数据属性并不是同等重要的，而且还存在冗余，这不利于做出正确而简洁的决策。属性约简要求在保持数据库的分类和决策能力不变的条件下，删除不相关或不重要的属性。人们总期望找到最小约简，但这已被证明是一个NP 完全问题。由于在粗糙集的属性
14、约简中约简属性集必须满足 2 个条件，即保持原分类质量不变和属性集中不含冗余属性，故粗糙集的属性约简是一个多约束、多目标的搜索优化过程。尽管基本粗糙集理论与其他处理不确定性的理论相比，具有不可替代的优越性，但是仍然存在着某些片面性与不足之处。例如：在研究属性约简的问题时，考虑数据的规模是比较少的情形；对于海量数据的情形，时间和空间复杂度较大。所以寻找快速、有效的启发式属性约简算法是研究粗糙集理论的一个有意义的课题。27基于属性关联度的启发式约简方法2 绪论2.1 粗糙集理论的研究现状近年来，粗糙集理论已经应用于机器学习、决策支持、知识发现、专家系统、模式识别等领域。目前对粗糙集理论的研究主要集
15、中在求解属性的最小约简、较小约简和最简规则集。粗糙集有效算法方面的研究包括如何求等价类、上近似、下近似、正区域、约简和核等等。现在国际上已经研制出了一些粗糙集工具应用软件，如 KDD-R 是由加拿大 Regnia 大学研制开发的基于可变精度粗糙集扩展模型的数据库知识发现系统。KDD-R 系统曾成功应用于医学数据分析和电信市场的决策分析等。LERS 是美国 Kansas 大学开发的基于粗糙集的实例学习系统，该系统曾用于医学研究、气候预测和环境保护等。Rough DAS&Rough Class是波兰 Poznan 工业大学开发的基于粗糙集的 KDD 决策分析系统。Rough Enough是挪威 Troll Data Inc.公司开发的，它包括数据输入、预处理、编辑、生成可辨识矩阵、集合近似、约简、生成规则、预测和分析功能。Rosetta 是波兰华沙大学和挪威科技大学联合开发的基于粗糙集的 KDD 决策分析系统，该系统可以处理多种格式的数据，如文本和数据库等，这些数据以决策表的形式存在于 Rosetta系统中
