基于属关联度的启发式约简方法.doc

1.本课题所涉及的问题及应用现状综述粗糙集理论中有效算法的研究是粗糙集理论在人工智能研究中的一个主要方向。目前，粗糙集理论中有效算法研究主要集中在规则提取、属性约简算法以及与粗糙集有关的神经网络和遗传算法研究等。属性约简是粗糙集理论的核心问题之一。属性约简的任务就是在保持知识表达系统中分类能力不变的情况下，删除其中不相关或不重要的属性。但是己经证明求解所有约简和求解最小约简都是NP-hard 问题。属性约简与核的求解一直就是粗糙集理论研究的热点与难点。2本课题需要重点研究的关键问题、解决的思路及实现预期目标的可行性分析 粗糙集理论一这种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法，便不失为一种处理复杂系统的较为有效的方法。随着信息时代的到来，数据不断增长，并且在很多情况下数据中含有大量的冗余信息和噪声。那么如何从大量的、杂乱无章的、带干扰的数据中挖掘潜在的、有利用价值的信息(知识)，即是寻找最快方法对最普遍、更一般的信息系统的有用知识的提取。在探索的过程中，讨论各种理论支持下的约简方法，比较方法的有效性，并随之将方法在理论的基础上进行推广，逐渐更人性化、更能被人们所理解的处理更一般的信息系统。而粗糙集中分辨矩阵和依赖度两工具，实用性与理解性比较强，可较为有效的用于一般的决策表中。而把依赖空间引入到属性约简(即在依赖空间中对属性约简进行讨论)具有一定的理论和实际意义及应用前景。3.完成本课题的工作方案对粗糙集理论进行研究，理解属性约简的作用与现实意义。了解灰度理论模型，并将此概念能引入到粗糙集理论中，计算其条件决策属性关联度，衡量各条件属性的重要性，以此作为启发式信息，设计相应的约简算法。编程实现一个具体的属性约简系统。 题目应完成的工作方案如下：（1）掌握粗糙集理论中有关数据约减方法的原理；（2）掌握灰色理论模型在粗糙集理论中的应用；（3）选择合适的实验数据集，并设计数据库；（4）设计正确、合理的数据结构；（5）编程实现一个基本的应用系统。 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 算法实例分析216 研究工作总结与展望266.1研究工作总结266.2 研究工作展望27致谢29参考文献30摘要粗糙集理论是一种处理含糊和不确定性信息的新型数学工具，其理论提出以来得到迅速的发展和广泛的应用。而知识约简是粗糙集理论重要研究内容之一，它的主要目的在于去除数据中的冗余信息，同时保持原决策信息系统的分类能力不变。当出现大量或海量数据时，原有约简方法效率就会变低，所以须对粗糙集约简计算理论进行优化，并且发展完善相关计算算法，以提高知识约简的效率。本文首先基于粗糙集理论，针对知识约简优化计算问题提出了两种知识约简方法，分析了这两种方法之间的关系以及它们的优缺点。并根据关联度以及灰度的理论分析，提出了减少执行时间的改进算法，降低了算法的时间复杂度，并最终完成了实验仿真。根据仿真结果得出结论：虽然经典的基于分辨矩阵的属性约简算法就约简后属性个数而言，比另外两种算法的效率有所提高，但其执行时间要高出很多，尤其当实例数较大时，执行时间会高出数倍左右。该结论有助于改进知识约简的效率，进一步提高粗糙集数据分析能力。关键词：粗糙集，属性约简，差别矩阵，关联度ABSTRACTRough Set Theory is a new mathematical tool to reason about uncertain and vague information. It has been rapidly 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 feasible. 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 reduction 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 algorithm 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 much 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, completeness, associated- II -基于属性关联度的启发式约简方法1引言随着计算机、网络和通讯等信息技术的高速发展，商务贸易的电子化，政府和企业事务自动化的迅速普及，产生了大规模的数据；同时日益增长的科学计算和大规模的工业生产过程也提供了海量数据。数据丰富、信息贫乏是当今数字化社会面临的一个巨大挑战。在海量数据背后隐藏着许多重要的信息，因此人们希望对其进行更高层次的分析，以便能够更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但是无法发现数据中存在的关系和规则，无法根据现有数据库中的数据预测未来的发展趋势，缺乏挖掘数据背后隐藏的知识的手段和方法。知识发现(Knowledge Discovery,简称KDD)和数据挖掘(Data Mining，简称 DM)正是在这种情况下产生和发展的一种新型数据分析技术。数据挖掘是知识发现过程中的核心步骤，粗糙集(Rough Set)理论作为一种应用于数据挖掘中的数学工具有着它不可替代的优点。属性约简(Attribute Reduction)是粗糙集理论中一个重要的研究课题。一般说来，数据库中的数据属性并不是同等重要的，而且还存在冗余，这不利于做出正确而简洁的决策。属性约简要求在保持数据库的分类和决策能力不变的条件下，删除不相关或不重要的属性。人们总期望找到最小约简，但这已被证明是一个NP 完全问题。由于在粗糙集的属性约简中约简属性集必须满足 2 个条件，即保持原分类质量不变和属性集中不含冗余属性，故粗糙集的属性约简是一个多约束、多目标的搜索优化过程。尽管基本粗糙集理论与其他处理不确定性的理论相比，具有不可替代的优越性，但是仍然存在着某些片面性与不足之处。例如：在研究属性约简的问题时，考虑数据的规模是比较少的情形；对于海量数据的情形，时间和空间复杂度较大。所以寻找快速、有效的启发式属性约简算法是研究粗糙集理论的一个有意义的课题。31基于属性关联度的启发式约简方法2 绪论2.1 粗糙集理论的研究现状近年来，粗糙集理论已经应用于机器学习、决策支持、知识发现、专家系统、模式识别等领域。目前对粗糙集理论的研究主要集中在求解属性的最小约简、较小约简和最简规则集。粗糙集有效算法方面的研究包括如何求等价类、上近似、下近似、正区域、约简和核等等。现在国际上已经研制出了一些粗糙集工具应用软件，如 KDD-R 是由加拿大 Regnia 大学研制开发的基于可变精度粗糙集扩展模型的数据库知识发现系统。KDD-R 系统曾成功应用于医学数据分析和电信市场的决策分析等。LERS 是美国 Kansas 大学开发的基于粗糙集的实例学习系统，该系统曾用于医学研究、气候预测和环境保护等。Rough DAS&Rough Class是波兰 Poznan 工业大学开发的基于粗糙集的 KDD 决策分析系统。Rough Enough是挪威 Troll Data Inc.公司开发的，它包括数据输入、预处理、编辑、生成可辨识矩阵、集合近似、约简、生成规则、预测和分析功能。Rosetta 是波兰华沙大学和挪威科技大学联合开发的基于粗糙集的 KDD 决策分析系统，该系统可以处理多种格式的数据，如文本和数据库等，这些数据以决策表的形式存在于 Rosetta系统中，当决策表成功装载入 project 后，系统使用粗糙集理论逐步分析数据，最后得到决策规则。目前，国内学术界对粗糙集理论有了一定的研究，但对其在数据挖掘中的应用还不够深入。现有的算法存在一定的缺点，这大大地阻碍了粗糙集理论的应用。当前，对粗糙集(Rough Set)理论的研究集中在数学性质、粗糙集拓广、与其它不确定方法的关系和互补及有效算法等方面：1） 粗糙集理论数学性质方面的研究，主要讨论粗糙集的代数结构、拓扑结构及粗糙集的收敛性问题。2） 粗糙集拓广方面的研究主要涉及粗糙集模型(或称变精确性粗糙集模型)与对连续属性的离散化等。3） 粗糙集理论与其他不确定性方法之间关系的研究中，目前主要讨论其与模糊集理论和 DS 证据理论的关系和互补。4） 在粗糙集有效算法方面的研究，主要集中于：(1) 导出规则的增量式算法；(2) 约简的启发式方法；(3) 粗糙集基本运算的并行算法。5） 基于粗糙集的逻辑是关于粗糙集的不确定推理的基础，发展这类逻辑的理论基础也是目前粗糙集理论研究的重要课题。粗糙集理论中有效算法的研究是粗糙集理论在人工智能研究中的一个主要方向。目前，粗糙集理论中有效算法研究主要集中在规则提取、属性约简算法以及与粗糙集有关的神经网络和遗传算法研究等。属性约简是粗糙集理论的核心问题之一。属性约简的任务就是在保持知识表达系统中分类能力不变的情况下，删除其中不相关或不重要的属性。但是己经证明求解所有约简和求解最小约简都是NP-hard 问题。属性约简与核的求解一直就是粗糙集理论研究的热点与难点。现有的粗糙集属性约简算法大致可以分为三类:1） Pawlak 数据约简算法。这种方法按照属性约简的定义进行求解，需要对条件属性集的幂集中的所有元素进行考察，因而具有指数型时间复杂度，该算法具有很强的理论指导意义，但其计算速度慢，且不易于计算机实现，因此，其实际应用的局限性较大。2） 区分矩阵属性约简方法。波兰华沙大学的著名数学家 Skowron提出的区分矩阵是求最小约简的有利工具。通过区分矩阵得出核属性，根据核属性求区分函数的最小析取范式，最后得到的每个析取分量对应着一个约简，因此可以得到最小约简。算法的时间复杂度为，其中 X 为条件属性的子集， A为属性集合， U 叫为对象(实例)集合。该算法比 Pawlak 数据约简算法的时间复杂度减少一半，并可以求出信息系统的所有约简，可以找到最小属性约简；但该算法在处理海量数据的信息系统属性约简问题上不是非常有效的。3） 启发式属性约简算法。目前，对这类约简算法的研究较多。主要有基于遗传算法、通过属性重要度或区分矩阵中属性频度等启发信息来寻求信息系统的约简。这类方法可以对大规模数据集进行处理。现有的关于属性约简的文献大部分都是在基于属性重要度和基于区分矩阵两种算法的基础上提出，典型的有X.Hu 提出的基于属性重要度的约简算法，基于属性依赖度的约简方法，苗夺谦等人的基于属性互信息的约简方法，基于区分矩阵属性频率的约简算法和基于关联矩阵等约简算法都各有优点。Wrobleswski J 等人提出的基于遗传算法求最小属性约简的算法也得到比较好的效果。文献提出了一种在优化初始群体基础上提高算法性能的启发式遗传算法，以属性重要度作为约简启发式信息；代建华等提出的算法是通过信息论中互信息来定义的属性重要度为启发式信息进行遗传算法约简，具有较好的约简效果和收敛速度。2.2 本文的工作目前有很多求解最小约简的算法，至今，在那些大数据量高维数的决策表上进行最小约简的求解还没有一种很好的解决方法。本文以粒计算和免疫遗传算法为工具对属性约简算法进行研究，具体内容如下：1） 综述了粗糙集理论的国内外研究现状，分析了粗糙集在属性约简的优势。2） 分析和研究了经典粗糙集的属性约简理论。3） 将属性约简和粗糙集理论相结合，提出了决策表系统中的信息挖掘方法，以及以属性重要性作为启发信息的属性约简算法，并进行了实例分析。4） 研究在约简算法中引入综合改进思想，提出基于属性的灰度的属性约简算法和色关联度的概念，将事物之间，因素之间的关联性引入算法，提高算法的性能。依照决策属性对条件属性的依赖度，以及曲线的形状的相似度决定条件属性的约简次序，实现对条件属性的快速、有效约简，从而提高了算法的全局搜索能力。2.3 本文的组织本文章节及内容的安排如下：第一章 绪论。概述粗糙集理论的国内外研究状况；介绍本文的工作安排。第二章 粗糙集基础理论。介绍粗糙集理论的基本概念。第三章 关联信息系统属性约简算法。针对同种信息系统具有不同属性的情况给出了不同的属性约简算法。例如：利用相似区分矩阵计算混合属性信息系统属性约简和利用信息量求取系统的属性约简等。并对相应的算法进行相关的改进以提高其运算效率。第四章 基于属性的灰度的属性约简方法。针对决策表中可能被约简的条件属性，计算其决策关联度，用于衡量各条件属性的重要性，并以此决定属性约简次序。第五章 结论与展望。总结了本文的研究工作，阐明本文研究工作中的难点和创新点，提出进一步研究的方向。3 粗糙集的基础理论粗糙集理论是一种处理含糊和不精确性问题的新型数学工具，其基本思想是在保持分类能力不变的前提下，通过知识约简，导出概念的分类规则。它自问世以来，无论是在理论或应用上都是迅速发展的一个既有理论又有应用的重要的、新的研究领域。3.1 粗糙集理论概况3.1.1 粗糙集的研究对象粗糙集的研究对象是由一个多值属性(特征、症状、特性等)集合描述的一个对象(观察、病历等)集合，对于每个对象及其属性都有一个值作为其描述符号，对象、属性和描述符是表达决策问题的 3 个基本要素。这种表达形式也可以看成一个二维表格，表格的行与对象相对应，列对应于对象的属性；各行包含了表示相应对象信息的描述符，还有关于各个对象的类别成员的信息。通常,关于对象的可得到的信息不一定足以划分其成员类别。换句话说，这种不精确性导致了对象的不可分辨性。给定对象间的一个等价关系，即导致由等价关系构成的近似空间的不可分辨关系，粗糙集就用不可分辨对象类形成的上近似和下近似来描述。这些近似分别对应了确定属于给定类的最大的对象集合和可能属于给定类的最小的对象集合。下近似和上近似的差是一个边界集合，它包含了所有不能确切判定是否属于给定类的对象。这种处理可以定义近似的精度和质量。粗糙集方法可以解决重要的分类问题，所有冗余对象和属性的约简包含属性的最小子集，能够很好地近似分类，得到可以接受质量的分类。而且，它还可以用决策规则集合的形式表示最重要属性和特定分类之间的所有重要关系。3.1.2 粗糙集理论的特点(1)粗糙集不需要先验知识。模糊集和概率统计方法是处理不确定信息的常用方法，但这些方法需要一些数据的附加信息或先验信息，如模糊隶属函数和概率分布等，这些信息并不容易得到。粗糙集分析方法仅利用数据本身提供的信息，无须任何先验知识。(2)粗糙集是一个强大的数据分析工具。它能表达和处理不完备信息；能在保留关键信息的前提下对数据进行化简并求得知识的最小表达式；能识别并评估数据之间的依赖关系，揭示出概念简单的模式；能从经验数据中获取易于证实的规则知识，特别适用于智能控制。(3)粗糙集与模糊集不同。粗糙集与模糊集分别刻画了不完备信息的两方面：粗糙集以不可分辨关系为基础，侧重分类，模糊集基于元素对集合隶属程度的不同，强调集合本身的含混性。从粗糙集的观点看，粗糙集合不能清晰定义的原因是缺乏足够的论域知识，但可以用一对清晰集合逼近。虽然粗糙集和模糊集特点不同，但它们之间有着密切的关系，有很强的互补性；粗糙集和证据理论也有一些相互交叠之处，在实际应用中可以相互补充。(4)粗糙集具有数学意义。将知识定义为不可分辨关系的一个族集，使得知识具有了清晰的数学意义，便于用集合运算处理。(5)不需要关于数据的附加信息。3.2 知识与知识库粗糙集以不可分辨关系为基础，给出知识表达系统这一模型，利用精确的上、下近似集逼近不精确对象，赋予知识清晰的数学意义，从而提供了用数理逻辑方法来表达、约简、分析、推理不精确知识的新思路。知识理论的各个方面研究得到了逻辑学、信息工程、系统工程和人工智能工作者的广泛重视。现己有许多理解、表述和处理知识的方法。由于当涉及到不同领域时知识具有不同定义，与 AI 相比，粗糙集理论中关于知识的理解可能更接近于认识科学。粗糙集理论认为知识是蕴藏在人类的分类能力之中的，知识以关于对象的分类能力为基础。这里对象是指感兴趣的所有东西，如事物、状态、抽象概念和过程等，称之为论域 U。因此，粗糙集理论中，知识被理解成关于论域的一组划分模式。论域可以按照不同的属性分成不同的类别，具有相同特征的知识构成基本集，其元素具有不可分辨关系，基本集是构成知识的模块，使知识具有粒状结构与层次性。通常我们不处理一个单独的分类而是处理论域上的一些分类族。一个论域上的分类族，定义为一个论域上的知识库。知识库的定义：K =(U,R)其中 K 为知识库，U 为全体对象的集合称为论域，R 为论域 U 上的等价关系(等价关系与分类的概念等同)，它是一种属性或多种属性的集合。可以根据不同的 R 对 U 进行不同形式的分类。知识库也被称作近似空间。这样，知识库表达了一个或一组智能机构的各种基本分类方式(例如，按照颜色、温度等等划分)，它构成了该机构所需的定义与环境或其本身的关系的基础构件。设 U 是一个论域，R 是 U 上的等价关系，U /R表示 U 上由 R 导出的所有等价类。 x R表示包含元素 x U的 R 等价类。一个知识库就是一个关系系统K = U , P，其中 U 是论域，P 是 U 上的一个等价类簇。如果 Q=P 且 Q R ，则PQ(Q 的所有等价类的交也是一个等价关系)，记作 IND(Q)。定义 2.1 K=(U,P)和 M=(U,Q)是两个知识库，若 IND(P)= IND(Q)，则称 K 和M(或 Q 和 P)是等价的，记作 K M (或者 P Q)。因此，当 K 和 M 是同样的基本范畴集时，知识库 K 和 M 中的知识都能使我们确切地表达关于论域的完全相同的事实。这个概念意味着可以用不同的属性集对对象进行描述，以表达关于论域的完全相同的事实。对于两个知识库 K=(U, P)和 M=(U, Q)，当 IND (P) IND(Q)时，称知识库 P比知识库 Q 更精细，或者说 Q 比 P 更粗糙。当 P 比 Q 更精细时，我们称 P 为 Q的特化，Q 为 P 的推广。由以上可知，推广是将某些范畴组合在一起，而特化则是将范畴分割成更小的单元。3.3 不可分辨关系与上、下近似集近似空间构成论域U 的一个划分；若R 是U 上的一个等价关系（R 是 U 上的关系并且是自反、对称、传递的），以 x R表示 x的R 等价类， U / R表示R 的所有等价类构成的集合，即商集；R 的所有等价类构成U 的一个划分，划分块与等价类相对应。等价关系组成的集合为等价关系族。例如：论域U= x1 , x2,x3,x4,x5,R1,R2是等价关系，根据这两个等价关系可以将论域U 进行划分：U / R1 = x1,x2,x3,x4, x5 ， U / R2 = x1,x3,x2,x4,x5。U / R1中的x1 , x2，代表 x1 R1的等价类。若记 R= R1 , R2 ，即 R 为等价关系族，其中包含有两个等价关系。定义 2.2 令 R 为等价关系族，设 PR，且 PR，则 P 中所有等价关系的交集称为 P 上的不可区分关系，记作 IND(P)，即有： = 显然 IND(P)也是等价关系。这样我们可以根据此等价关系，进行论域的划分：U / IND(P)= x1 ,x2,x3,x4,x5。不可区分关系是 Pawlak 粗糙集理论中最基本的概念。若( x, y ) IND(P)，则称对象 x与 y 是不可区分的，即x, y 存在于不可区分关系 IND(P)的同一个等价类中。依据等价关系族 P 形成的分类知识，x, y 无法区分。我们称U /IND(P)中的各等价类称为 P 基本集。给粗糙集下定义，必须给出近似的概念，因为含糊概念无法用已有知识精确表示。例如在知识U / R1 = x1 , x 2 , x3 , x4 , x5中，概念x1 , x 2 ,x3 就不能用其中知识精确表示。定义 2.3 设集合 X U，R 是一个等价关系，称RX =x | x U , 且X为集合 X 的R 下近似集；称 RX = x | x U , 且XU为集合 X 的R 上近似集。称集合BN R ( X ) =为 X 的R 边界域；称POS R ( X )= 为X 的R正域；称NEG R ( X )=U为 X 的R 负域。用图 2.1 表示更加直观：由上述定义我们可以知道，下近似RX 是由必定属于 X 的对象组成的集合；而上近似RX 是由可能属于 X 的对象组成的集合；BN R ( X )表示既不能明确判断属于 X ，也不能明确判断不属于 X 的对象组成的集合；NEG R ( X )则表示一定不属于 X 的对象组成的集合。粗糙集的定义：当 BN R (X)= 时，即 R X= RX ，称 X 是 R 精确集；当BN R (X)时，即 R X R X，称 X 是 R 粗糙集。以上讨论了粗糙集的一些基本概念。粗糙集的不可定义性不确定性)是由于粗糙集 X 的边界不确定引起的。集合 X 的边界区域越大，其确定性程度就越小。我们可以用集合 X 的精度来描述粗糙集 X 的不确定性程度。定义 2.4 由等价关系R 定义的集合 X 的近似精度为：其中 X ， |X| 表示集合 X 的基数，显然有 01。直观的理解，反映了知识U /R近似表示 X 的完全程度。如图 2.1 中表示的那样，下近似占上近似的比例就是近似精度。很显然当=1 时，X 是R 的精确集；当 01 时， X 是 R 的粗糙集。在粗糙集中，表示集合不精确性的数值是通过现有知识中的两个精确集合定义的。产生不精确性的原因在于我们对论域的现有知识有限，随着知识粒度的细化，不精确性会随之降低。根据粗糙集 X 的上近似集、下近似集的特征，我们对粗糙集 X 的不确定程度也可以作如下定义:（1）称 X 是R 粗糙可定义的，如果有RX 且RX U ；（2）称 X 是R 内不可定义的，如果有RX = 且RX U ；（3）称 X 是R 外不可定义的，如果有RX 且RX =U ；（4）称 X 是R 全不可定义的，如果有RX = 且RX =U ；对于定义，我们可以作如下的直观理解：若 X 是R 粗糙可定义的，则可以确定U 中的某些元素是否属于 X 或不属于X ；若 X 是 R 内不可定义的，则可以确定U 中的某些元素是否不属于 X ，但对U中任意元素都无法确定其是否属于 X ；若 X 是R 外不可定义的，则可以确定U 中的某些元素是否属于 X ，但对U 中任意元素都无法确定其是否不属于 X ；若 X 是R 内不可定义的，则对U 中任意元素，既无法确定其是否属于 X ，也无法确定其是否不属于 X 。3.4 信息系统在粗糙集理论中，我们通常用等价关系代替分类。当 R 为 U 上的划分R = x 1 , x2 , , xn表达等价关系，（U，R）称为近似空间。粗糙集理论提供了知识的一种形式模型，近似空间的概念将知识定义为不可分辨关系的簇集，这使得知识具有了数学意义，从而可以使用数学方法来处理数据约简和数据分类等问题。我们可以从形式上将数据库中的信息用数据表或者属性值的形式简单的表示出来。其中数据表的“列”用属性名来标识，“行”用对象名来标识，并且每一行表示对应对象的一条信息。每个属性上的值被确定后该对象的特征就完全被确定了。在所有属性上取值都一样的几个对象，则认为它们之间没有任何差别。粗糙集理论特别适合处理以数据表形式来表示的信息。通过引入信息系统的概念，建立起近似空间和数据表之间的联系。信息系统是一种知识表达方式，知识的表达方式在智能数据处理中有十分重要的地位。信息系统有时也称为知识表示系统。形式上，四元组 S = (U , A, V , f)是一个信息系统，其中：U ：对象的非空有限集合，即论域；A ：属性的非空有限集合；V=， Va 是属性的值域；f ：U A V是一个信息函数，它为每个对象的每个属性赋予一个信息值，即a A，x U， f ( x, a )V a。决策信息系统是将信息系统中的属性分为条件属性与决策属性两类，因此需要研究两类属性的关系，从信息系统仅仅可以得到分类，而从决策信息系统中可以获得决策知识。决策信息系统是信息系统的一个特例，它是信息系统中最为常用的一个决策系统。多数决策问题都可以用决策表形式来表达。它可以根据信息系统定义如下：定义 2.5 设 S = (U , A , V , f)是一个信息系统（知识表达系统）， A = C D，C D=，C 称为条件属性集合， D 称为决策属性集。具有条件属性和决策属性的信息系统称为决策信息系统。3.5 知识的依赖性知识的依赖性可形式化地定义如下：令 K=（U，R）是一个知识库，P、Q、R。知识 Q 依赖于知识 P（记作 PQ）当且仅当 IND(P) IND(Q)。知识 Q 与知识 P 等价（记作 PQ）当且仅当 PQ 且 QP。知识 Q 与知识 P 独立（记作 P Q）当且仅当 PQ 与 QP 均不成立。当知识 Q 依赖于知识 P 时，也可以说知识 Q 是由知识 P 导出的。有时候知识的依赖性可能是部分的，这意味着知识 Q 仅有部分是由知识 P导出的，这可以由知识的正域来定义：令 K=（U，R）是一个知识库，P、QR。当k = (Q)= 时，我们称知识 Q 是k 度依赖于知识 P 的，记作 P kQ。当k =1 时，我们称 Q 完全依赖于 P；当 0k 1 时，称 Q 粗糙依赖于 P；当k =0 时，称 Q 完全独立于 P。系数 (Q)可以看作 Q 和 P 之间的依赖度。3.6 属性约简与核知识约简在信息系统分析与知识发现等领域具有重要的应用意义。知识之间的依赖性决定知识是否可以进行约简，根据依赖性所定义的知识的重要性往往是知识约简的重要启发式信息。决策信息系统的简化就是化简决策系统中的条件属性，化简后的决策系统具有与化简前的决策表相同的功能，但是化简后的决策系统具有更少的条件属性。因此，决策信息系统的简化在工程应用中相当重要，同样的决策可以基于更少量的条件，使我们通过一些简单的手段就能获得同样的结果。无决策系统指的是属性集只有条件属性而没有决策属性的系统。有决策系统与无决策系统的区别在于：有决策系统的属性集可分为两部分，一部分是条件属性，另一部分是决策属性；而无决策系统则没有决策属性。对于简化的目的，二者也有明显的不同；无决策系统的简化是为了得到最小属性集和核集；有决策系统的简化则是为了得到最简的决策规则。无决策系统简化的理论依据是可分辨性准则；有决策系统的简化依据是协调性原则。有决策系统的简化只是针对条件属性集，而决策属性集是不需简化的。本文主要是对有决策系统的约简算法研究。定义 2.6 令 P 为等价关系族，RP，如果有 IND(P)=IND(PR )，则称R为 P 中不必要的；否则称R 为 P 中必要的。如果每一个关系RP 都是 P 中必要的，则称 P 为独立的；否则称 P 为依赖的。定理 2.1 设 S = (U , A , V , f)是一个信息系统，R B 具有以下性质：当B A时，IND ( A ) IND ( B)；说明当属性越多时，等价关系越少，划分越细。推论 2.1 B a B则 IND ( B) IND( B a)即| IND( B ) | | IND( B a )|所以如果有| IND ( B )|= | IND ( B a)|则a为不必要的冗余属性。其中| |表示集合的基数。定义 2.7 设 U 为一个论域，Q 和 P 为定义在 U 上的两个等价关系簇且 QP，若 Q 独立的，且 IND(P)=IND(Q)，则称 Q 是等价关系族 P 的一个绝对约简，记作：RED(P)。P 中所有绝对必要关系的集合称为等价关系族 P 的核，记作：CORE(P)。定 理 2.2 等 价 关 系 族 P 的 核 等 于 P 的 所 有 约 简 的 交 集 ， 即CORE(P)= RED(P)在应用中，一个分类（知识）相对于另一个分类（知识）的关系十分重要，因此需要引入知识的相对约简和相对核的概念。我们先介绍正域和可省、不可省的概念：定义 2.8 设P 和Q为论域上的等价关系，Q 的P 正域记作， 定义 2.9 设 P 和 Q 为论域上的等价关系族，rP，若有则称日 r 为 P 中 Q 不必要的，否则称 r 为 P 中 Q 必要的。若 P 中的任一关系 r 都是 Q 必要的，则称 P 为 Q 独立的。定义 2.10 设 SP，称 S 为 P 的 Q 约简，当且仅当 S 是 P 的 Q 独立子族，且 (Q)= (Q)。P 中所有 Q 必要的原始关系构成的集合称为 P 的 Q 核，记作： (P)。P 的 Q 核是知识 P 的本质部分。P 的 Q 约简是 P 的子集，且是独立的。它具有与知识 P 相同的分类能力。定理 2.3 P 的 Q 核等于 P 的所有 Q 约简的交集，即 (P)= (P)。核心这个概念有两方面的作用。一方面由于核心包含在所有的约简中，所以它可以作为属性约简时启发式算法的计算基础；另一方面，核心可以解释为当属性约简时它是不能消去的属性集合。一般约简是在不改变对论域中对象的分类能力的前提下消去冗余知识，而相对约简是在不改变将对象划分到另一个分类中去的分类能力的前提下消去冗余知识。决策信息系统的属性约简，即相对约简，就是要从条件属性集合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性的分类和所有条件属性所形成的相对于决策属性的分类一致，即和所有条件属性相对于决策属性有相同的分类能力。一般地讲，一个决策表的属性约简集不是唯一的，即对同一个决策表可能存在多个相对约简集。因为属性约简的目的是导出关于决策表的决策规则，约简中属性的多少直接影响着决策规则的繁简。因此，人们往往期望找到具有最少条件属性的约简集，即最小约简。然而，遗憾的是 Wong S.K.和 Ziarko W.已经证明了找出一个决策表的最小约简是 NP-hard 问题，即当数据库数据量增大时，该问题的复杂度将以指数增加。导致 NP-hard 问题的主要原因是属性的组合爆炸问题，解决这类问题的一般方法是采用启发式搜索方法求出最优或次最优约简。4 关联属性约简算法及其改进4.1 分辨矩阵及基于分辨矩阵的算法分辨矩阵(Discernibility Matrix)是由波兰华沙大学的著名数学家Skowron提出的，是求粗糙集约简的一个有力工具，利用这个工具，可以将存在于复杂信息系统中的全部不可分辨关系表达出来。信息系统S中关于条件属性C的分辨矩阵M(c)可定义为：，Mij包含在ui和uj上具有不同值的所有属性（ui和uj属不同概念）。换句话说，Mij代表区分ui，uj的全部信息。可证明M(s) = mij是对称的。核与分辨矩阵有着密切关系，从分辨矩阵中可以计算出一个信息系统的核(可能为空)。考虑到分辨矩阵包含了决策表中所有属性区分信息，因此，核属性外的其余有用属性应从条件属性组合数不为1的矩阵元素中分析取得。假设某信息表除核属性C0外还有两个条件属性组合，分别表示为a1 a2 am，b1 b2 bn,为便于进行数学逻辑运算，我们将属性组合以布尔值表示其中是否包含某个条件属性。假设，ai=0表示不包含条件属性ai，而ai =1表示包含条件属性ai，根据分辨矩阵的定义可以知道，如果要识别所有决策不同的记录，则ai (i=1,2,.,m)、 bj =m和(j=1,2,.,n)之中必然至少各需保留一条属性。构造一个如下的逻辑表达式：P =(a1a2am )(b1b2bn)由以上分析可以得到，要识别所有决策不同的记录，则必然有P=1。我们将P转化为析取范式的形式，即转换为P =(a1b1) (a1b2) (ambn)，且令P中任意合取式项的值均等于1，则该合取式代表的属性组合连同核属性一起即可将原决策表中的所有记录区分开来。这样在析取范式中某个由合取式表示的属性组合连同核属性一起将作为最终的约简结果。由于析取范式由多个合取式构成，究竟采用哪种属性组合应根据我们进行约简的目的而定。如果希望最终得到的约简结果中条件属性的数目最少，我们就选取析取范式中元素数目最少的合取式；如果希望最终得到的决策规则最少，则一般还要进行值约简之后才能作出决定。下面举例加以说明。设有如下（3-1）决策表，其中a、b、c、d为条件属性，D为决策属性U/AabcdDX110301X200222X320301X400323X511301（3-1）其分辨矩阵可构造为： 可以知道，core (A)=c，S =a ,d，P =a d，从而得到两个约简为：B =a ,c和B =c ,d。这种约简算法适合比较小的数据集。虽然该算法不是寻找最优化简的最佳方法，但差别矩阵却有效的提供了核的求解方法。通过例子我们可以将基于分辨矩阵的约简素发描述如下:算法功能计算最优约减或包含用户强调属性的最优约减。输入预处理后的归纳关系表R； R的属性集,由条件属性集C 和结论属性集D 组成.输出一个属性子集.给出用户强调的属性集(可能为空)；由分辨矩阵算出核； = ； ；计算中的属性的意义值,并对排序；WHILE K( , D) K( , D) DO从 中选择属性意义值最大的那个属性；= ； = - ；计算约减属性集中的条件属性相对于结论属性的依赖度K( ,D)；求约减子集中的属性个数| N； FOR i = 0 to N - 1 DO IF 中THEN 将移出； 计算K( , D)； IF K( , D) K( , D) THEN = 。求得约减后,就意味着将归纳表R(数据库)简化为确定的模式,即挖掘出隐藏在R 中的用户关心的本质信息. 该算法已在Regina大学开发的KDD-R 中得到应用,是目前为数不多的基于粗集理论的实用性发现系统实例.4.2启发式属性约简算法求取一个信息系统的最小约简和求取其全部约简一样，都是NP复杂问题。即如果一个信息系统研究的对象数目为m，属性数目为n，则考察属性集的全部约简理论上要进行次基本操作，计算的复杂性随着数据表的增大呈指数增长。在前面所提出的算法中，通过将不包含核属性的条件属性组合表示为合取范式并转换为析取范式时，实际上我们已经求取了信息系统的全部属性约简。当信息系统不是一个非常复杂的系统时，即该信息系统仅有少量的条件属性和记录时，该方法具有很好的实用性。但是如果信息系统具有大量条件属性和记录时，利用该方法进行求解的空间和时间复杂度大大增加，效率将显著降低。假如能先对属性的重要性进行排序，使得比较重要的属性被优先选取，那么将使约简算法中的循环次数大大降低，当属性个数较多时，改进算法就能显示其优越性。最早的启发式约简计算方法是Hu提出的基于属性重要性的启发式方法。它的主要原理是：该算法以核为出发点，将属性的重要性作为启发式规则，不断从C中按属性的重要性从大到小选择属性，直到该集合是一个约简为止，接着检查该集合中的每个属性，看移走该属性是否会改变该集合对决策属性的依赖度。各算法对属性重要性的度量不同，目前的报道涉及到以下几种度量：1.根据依赖度定义。设T为一二维决策表,C,D分别为其条件属性集和决策属性集。RC，则对于任意属性aC的属性重要性可定义如下： SGF(a,R,D)=k(Ra,Dk(R,D)。其中有，。2.根据信息熵来定义。假设H(D/R)为D相对于R的条件熵，属性a的重要性定义为：SGF(a,R,D)=H(D/R)H(D/Ra)。3.根据差别矩阵中的频率。设M是由决策表T构造的差别矩阵，令p(a)为M中属性a的频率函数，它为a在M中出现的次数，SGF(a,R,D)=p(a)。4.3 算法改进根据我们对粗集理论的研究，以及对3.1节算法的理论分析与实验验证，我们发现上述算法中SGF的求解过程很复杂,占据该算法的大部分处理时间。笔者通过分析SGF表达式,认为SGF表示条件属性集中某个属性对结论属性集的依赖关系的关联程度,也可以看成是此属性携带了与结论有关的信息量的大小,该属性明确地表示与结论属性的肯定带或边界带相匹配程度的大小。SGF实质就是计算单个条件属性对结论的贡献,但计算过于复杂。笔者提出直接构造单个属性与结论属性相关程度的概念与计算表达式. 这个以单个属性为基础的概念是关联度。关联度对一个条件属性集为C ,结论属性为D 的归纳关系表示为R ,条件属性c(c C) 相对于结论属性D的关联度可定义为:表示由属于c 划分R 形成的等价类,是一个系统概念,表示等价类中系统概念所占的个数。表示在所有等价类中所有系统概念所占的个数的最大者. 由此定义,的值越大,由属性c 对R 划分出的等价类就越能明确与系统概念的肯定带或边界带相匹配,即c对结论属性贡献越大,可用作为计算初始选择条件属性中与结论属性具有最大关联程度的方法,即要寻找的启发函数. 可以认为最后的约减结果肯定包含了值较大的那些属性。引入关联度后,算法描述如下:算法功能计算最优约减或包含用户强调属性的最优约减。输入预处理后的归纳关系表R； R的属性集,由条件属性集C 和结论属性集D 组成.输出一个属性子集. 给出用户强调的属性集(可能为空)； (2) =；(3)；(4