（计算机应用技术专业论文）基于粗糙集的值约简方法研究.pdf

摘要 粗糙集理论是一种处理含糊和不确定性问题的新型数学工具，以 其为理论基础的数据分析与处理技术得到越来越广泛的应用。数据约 简是非常重要的一个研究课题，本文基于粗糙集理论，着重对值约简 理论与方法进行研究。 分析了支持度、置信度以及覆盖度等决策规则的度量方法，研究 度量所体现的规则性质。论述了值约简的过程，针对目前值约简方法 的不足，将区分矩阵引入值约简。阐述了区分矩阵的发展及其特点， 在此基础上全面分析了各种区分矩阵进行值约简存在的问题。给出了 一种改进的区分矩阵，在代数观点内解决了值约简过程中所产生的新 的不一致。同时将新的规则区分矩阵用于知识库的增量式更新，设计 了一种增量式算法，该方法能够同时获得一致性规则和不一致性规 则。 通过分析信息论的基本观点，探讨了信息熵、决策熵和条件熵的 思想。在值约简理论的基础上，详细分析产生值约简异常的实质原因。 给出值约简形式化描述，保证规则值约简前后决策和不一致程度不 变，并且设计了一种基于局部熵的值约简算法，该算法能适应决策表 的不一致情形，逐步消除了值约简异常，且运用此方法所提取的规则 集能够保持与原信息系统一致。 最后采用u c i 数据集进行实验仿真，仿真结果进一步阐明了相 关理论成果。 关键词粗糙集，值约简，区分矩阵，异常 a bs t r a c t r o u g hs e tt h e o r yi san e wm a t h e m a t i c a lt o o lt od e a lw i t hv a g u e n e s s a n du n c e r t a i n t y ar a p i dg r o w t ho fi n t e r e s tc a nb el a t e l ys e e ni nr o u g hs e t t h e o r ya n di t sa p p l i c a t i o n s d a t ar e d u c t i o ni s av e r yi m p o r t a n ts u b j e c t t h i st h e s i sr e s e a r c h e so nv a l u e sr e d u c t i o nb a s e do nr o u g hs e tp r i m a r i l y t h em e a s u r e m e n to fd e c i s i o nr u l e si sa n a l y z e ds u c ha ss u p p o r t ， c e r t a i n t ya n dc o n v e r a g e ；t h ep r o p e r t i e s o ft h em e a s u r e m e n t sa r ea l s o s t u d i e d m e a n w h i l et h i st h e s i sd i s c u s s e st h ep r o c e s so fv a l u e sr e d u c t i o n i nv i e wo ft h ed e f i c i e n c i e so fv a l u e sr e d u c t i o n d i c e m i b i l i t ym a t r i xi s i n t r o d u c e di n t ov a l u e sr e d u c t i o n t h ed e v e l o p m e n ta n dt r a i t s o f d i c e m i b i l i t ym a t r i xa r ed i s c u s s e d ；t h ep r o b l e m so fv a l u e sr e d u c t i o nb a s e d o nd i c e m i b i l i t ym a t r i xa r ec o m p r e h e n s i v e l ya n a l y z e dt o o a ni m p r o v e d d i c e m i b i l i t ym a t r i xi sp u tf o r w a r d w h i c hc a ns o l v e i n c o n s i s t e n c eo f v a l u e sr e d u c t i o ni na l g e b r av i e w m o r e o v e rt h ei m p r o v e dd i c e m i b i l i t y m a t r i xi su s e di na ni n c r e m e n t a la l g o r i t h mt ou p d a t et h ee x i s t i n gd e c i s i o n r u l e sw i t hi n c r e m e n t a lw a yw h e nan e we x a m p l ei sa d d e di nd e c i s i o n t a b l e n i sa l g o r i t h mc a na c q u i r eb o t hc o n s i s t e n ta n di n c o n s i s t e n tr u l e sa t t h es a m et i m e a c c o r d i n g t ot h eb a s i cv i e wo fi n f o r m a t i o ne n t r o p y , d e c i s i o ne n t r o p y a n dc o n d i t i o ne n t r o p ya r es t u d i e d o nt h et h e o r yo fv a l u e sr e d u c t i o n ，t h e r e a s o n so fa n o m a l i e si nv a l u e sr e d u c t i o n a r e a n a l y z e d i nd e t a i l s f u r t h e r m o r eaf o r m a td e s c r i p t i o ni sp r o p o s e ds ot h a tr u l e sc a nk e e pt h e i r d e c i s i o n sa n di n c o n s i s t e n c ya f t e rr e d u c t i o n a na l g o r i t h mb a s e do n d i c e m i b i l i t ym a t r i xt h a tc a na d a p tt o i n c o n s i s t e n ts t a t ei s d e s i g n e d i n f o r m a t i o ne n t r o p yi si n t r o d u c e di n t od i c e m i b i l i t y m a t r x v a l u e s r e d u c t i o na n o m a l i e sc a nb ee l i m i n a t e da n dt h er u l e sc a nk e e pa c c o r dw i t h t h eo r i g i n a li n f o r m a t i o ns y s t e mu s i n gt h i sm e t h o d f i n a l l y u c id a t a s e ti su s e df o r e x p e r i m e n t t h e r e s u l t so f e x p e r i m e n ti l l u s t r a t ec o r r e l a t i v et h e o r yf u r t h e r k e yw o r d sr o u g hs e t ，v a l u e sr e d u c t i o n ，d i s c e r n i b i l i t ym a t r i x ， a n o m a li e s 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特另t l ；d n 以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：盛益 日期：二堕年 月旦日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：墅导师签名坳日期：泣年上月j 上日 硕士学位论文 第一章绪论 第一章绪论 粗糙集理论作为智能信息处理的有效工具之一，具有处理不精确、不确定和 不完备数据，并从中获取知识的能力，自上世纪8 0 年代提出以来得到不断完善 与发展，取得了良好的研究和应用成果，但现实问题中，数据规模和复杂程度的 俱增给粗糙集方法与技术提出了挑战，其理论在实际应用中存在一些问题。本章 介绍了课题研究的背景与意义，粗糙集理论和值约简的国内外研究现状，以及论 文的主要内容与结构。 1 1 课题研究背景 2 l 世纪是信息爆炸的时代，庞大的信息量渗透在社会生活和生产的各个领 域。面对丰富数据知识已成为社会生活和生产的第一推动力，如何处理看似杂乱 无章、数以亿的信息并使之成为各个领域的有用知识成为当前亟待研究的课题。 在自然科学、社会科学和工程技术的很多领域中，都不同程度涉及到不确定因素 和对不完备信息的处理。尽管目前在分析数据方面已经提出了用于数据挖掘的简 单统计分析技术，但实用的智能数据分析技术目前仍不成剿1 i 。因此，寻求一种 快速、准确的从海量数据集中发现知识、提取潜在有用信息，已成为知识发现、 数据挖掘的一点热点研究领域1 2 l 【引。 经典逻辑中只有真假二值，但在现实生活中有大量含糊现象存在于真假二值 之间。早在1 9 0 4 年，著名哲学家g f r e g e 提出含糊概念，并把其归结到边界线 区域，即在全域上存在一些个体既不能在某个子集上被分类，也不能在该子集的 补集上被分类。1 9 6 5 年，l a z a d e h 提出模糊集理论1 4 i ，不少学者试图通过这一 理论解决g f r e g e 的含糊概念，但模糊集没有给出数学公式描述这一含糊概念， 故无法计算出边界线上含糊元素的具体数目。1 9 8 2 年，波兰数学家z p a w l a k 提 出粗糙集理论1 5 l ，把这些无法确认的个体都归属于边界线区域，将这种边界线区 域定义为上近似集和下近似集之差集。由于上近似集和下近似集都可通过等价关 系给出确定的数学公式描述，因此含糊元素数目可以被计算出，从而实现了 g f r e g e 的边界线思想。粗糙集理论主要兴趣在于它恰好反映了人们用粗糙集方 法处理不分明问题的常规性，即以不完全信息或知识去处理一些不分明现象的能 力，或依据观察、度量到的某些不精确的结果而进行分类数据的能力。 与其它处理不确定信息的方法比较，如模糊集、概率统计等，粗糙集具有如 下基本特点：( 1 ) 粗糙集理论不需要先验知识。模糊集和概率论统计方法是处理 硕士学位论文第一章绪论 不确定信息的常用方法，但这些方法需要一些数据的附加信息或先验知识，如模 糊隶属函数和概率分布等，这些信息有时不容易得到。粗糙集理论分析方法仅利 用数据本身提供的信息，无须任何先验知识。( 2 ) 粗糙集是一个强大的数据分析 工具。它能表达和处理不完备信息；能在保留关键信息的前提下对数据进行化简 并求的知识的最小表达；能识别并评估数据之间的依赖关系，揭示出概念简单的 模式；能从经验数据中获取易于证实的规则知识，特别适用于智能控制。( 3 ) 粗 糙集与模糊集分别刻划了不完备信息的两个方面1 6 l ：粗糙集以不可分辨关系为基 础，侧重分类，模糊集基于元素对集合隶属程度的不同，强调集合本身的含混性。 从粗糙集的观点看，粗糙集合不能清晰定义的原因是缺乏足够的论域知识，但可 以用一对清晰集合逼近。有关粗糙集和模糊集内在联系的阐述及模糊粗糙集的概 念，请参见文献f 7 j 1 8 】【9 1 。粗糙集和证据理论也有一些相互交叠之处【1 0 l ，在实际应用 中可以相互补充。相对其他软计算工具，粗糙集理论表现出了强大的优势，其研 究逐渐趋热，目前己广泛应用于模式识别、机器学习、知识获取、人工智能、经 济预测等众多领域。 粗糙集理论有效地克服了传统的数据分析和信息处理方法的不足，成为信息 科学和认知科学领域新的研究和应用热点，在不确定问题和智能计算、数据分析 方面表现出较强的处理能力，得到了学术界的广泛关注i l l l 。另外，粗糙集理论与 其他数据分析方法结合，可以有效地增强智能信息处理能力，为智能决策提供新 的方法和技术。目前，粗糙集理论已在模式识别、机器学习、医疗诊断、图像处 理、数据挖掘和专家系统等领域得到广泛的应用。 目前，粗糙集的理论研究方向主要有数学性质、模型拓展、有效算法和智能 分析方法融合等。粗糙集在数学性质方面的研究主要是对其理论中知识的不确定 性问题进行理论研究，包括其代数结构、拓扑结构、粗糙逻辑和粗糙集收敛性等 问题。粗糙集在模型拓展方面的研究包括可变精度模型、相似模型和连续属性离 散化模型，主要解决数据分析时遇到数据噪声、数据不完备和连续数据离散化等 问题。粗糙集在有效性算法方面的研究主要集中在下面几个方面：约简的启发式 算法、粗糙集基本运算的并行算法、导出规则的增量式算法、大数据集中的粗糙 集计算实现。粗糙集与其他智能分析方法的融合可以取长补短以实现不同的应用 目的，如r o u g hs e t 与f u z z ys e t 理论、神经网络、遗传算法、证据理论、专家 系统、b a y e s 理论、概率统计理论等智能理论的结合。 1 2 国内外研究综述 粗糙集理论是传统集合理论的扩展，是进行数据分析的一种较新思想方法， 2 硕士学位论文 第一章绪论 更是有效地分析和处理不精确、不一致、不完整等各种不完备信息的数学工具， 并从中发现隐含的知识，获取潜在的规则。 1 9 9 1 年p a w l a kz 出版了专著，较系统地阐述了粗糙集基础理论思想，奠定 了粗糙集的数学基础，该书与1 9 9 2 年出版的粗糙集理论应用专集较好地概括了 这一时期粗糙集理论与实践的研究成果，促进了它的进一步发展，成为学习和应 用粗糙集理论的重要文献。1 9 9 2 年在波兰召开了第一届国际粗糙集理论研讨会， 着重讨论了集合近似定义的基本思想及其应用，粗糙集环境下的机器学习基础研 究是这次会议的重要主题。1 9 9 3 年在加拿大b a n f f 召开了第二届国际粗糙集与知 识发现研讨会，积极推动了国际上对粗糙集理论与应用的研究，许多著名的k d d 学者参加了这次会议，介绍了许多应用扩展粗糙集理论的知识发现方法和系统。 1 9 9 6 年在日本东京召开了第五届国际粗糙集研讨会，促进了亚洲地区对粗糙集 理论与应用的研究。从1 9 9 2 年至今，每年都召开以粗糙集为主题的国际会议， 成立了粗糙集学术研究会，推动了粗糙集理论的发展和应用。二十世纪末以来， 我国学者也开展了对粗糙集理论与方法的深入研究，取得了许多研究成果，在该 领域的研究取得了令人瞩目的成绩，与国际学术界之间的交流也日益广泛。 现实世界的数据常常存在着冗余，因此有必要将由大量数据所构成的数据库 进行约简，删除那些无意义的数据。约简包括两方面：属性约简和属性值约简。 属性约简f 堙l f l 3 j f l 4 j 只能在一定程度上去掉决策表中的冗余信息，提高系统知识的清 晰度。但是在对数据库进行分析时，我们经常关心蕴涵在数据当中的潜在知识， 因此很有必要对决策表进行值约简，去除所有不影响规则生成的冗余属性。属性 值约简是对具体的每条规则而言，消除多余的属性值，使规则泛化。经过值约简 后得到的规则能更适用于大多数训练样例中的样本，用尽量少的规则来代表训练 样例中所有的样本，而且规则支持度增大，能提高规则泛化能力和决策分析的有 效性，克服噪声对数据分析的影响。 作为一种从实例中发现知识的归纳学习算法，对于决策规则的发现一直是粗 糙集理论研究与实际应用中一个非常重要的研究内容，国内外学者在决策表的值 约简方面做了许多研究工作i 怡1 1 1 6 l l ”1 ，提出了一些决策表的值约简的思想和方法， 如区分矩阵法、启发式值约简算法等。常见的一些粗糙集应用系统，如r o s e 和 r o s e t t a 中也有一些用于规则提取的工具软件。这类算法由于在计算的过程中不 能将约简过程和信息决策系统的具体内容分离开来，其通用性不强，提取规则的 效率也有限。 ( 1 ) 基于区分矩阵的值约简 区分矩阵是一种信息表示技术，体现了条件对决策的影响，最早由波兰华沙 大学数学家s k o w r o n 提出1 18 】1 1 9 1 。由区分矩阵可以唯一定义一个区分函数，它精确 3 硕士学位论文第一章绪论 地描述了决策信息系统中对象之间的差别。根据区分矩阵得到区分函数，进而化 简区分函数来计算规则的约简f 2 0 1 1 2 l l f 2 2 堤粗糙集理论中求值约简的主要方法之一。 区分函数由区分矩阵中的某一行( 列) 来构造，把出现在这一行( 列) 中的每个属性 作为布尔变量，并且对每个矩阵分量进行先析取后合取的布尔运算，其结果就是 一条规则的值约简。 目前区分矩阵的定义方法有：h u 等学者提出的区分矩阵的元素项是决 策属性值不同的两个对象中取值不同的条件属性的集合l 矧。叶东毅等人改进 了h u 的区分矩阵，考虑到了不一致性情况下求属性核的异常，将一致性的条件 等价类与不一致性的条件等价类区别对待【2 4 1 。杨明等提出的矩阵只需比较一 致性对象之间的条件属性以及一致性对象和不一致性对象的条件属性，减少了矩 阵中元素的个数嘲。 将这些区分矩阵直接应用于值约简还存在一些不足：由h u 等学者提出 的区分矩阵对于一致性的决策表，可以达到完整的值约简，但是在不一致的决策 表中，将会出现一些不正确规则。这是因为该矩阵按决策属性值的不同分类体现 了不同等价类的对象之间条件属性的差别，没有考虑不一致对象，当出现某一个 不一致性对象与某个一致性对象含有相同的属性值也决策也相同时，就会不可避 免的出现不正确的规则。该矩阵在保持相对正域不变的基础上考虑了不一致 性情况下的异常，因此可以得到不一致性决策表的代数约简。但是在构造区分矩 阵时，对每个矩阵元素均要判断所比较的对象条件等价类是否都是不一致性等价 类，计算代价高。杨明等提出的方法中，其原理与文献 2 4 所定义的区分矩 阵相同心射，只是在该矩阵中，不再需要再次判断两个对象是否都是不一致性对象。 该方法在空间复杂度和计算复杂度上相对于文献 2 4 都有改进。 以上区分矩阵处理的是单个对象，这样对于一个大型的决策信息系统来说， 当决策信息系统中对象数量很多时，需要建立一个庞大的区分矩阵，消耗的存储 空间将是巨大的。文献 2 6 提出了一种规则区分矩阵，将区分矩阵中的比较单位 改为由条件属性和决策属性联合分类后等价类，这样就能节省存储空间并减少矩 阵运算量。该矩阵能求取不致性决策表信息论的约简族，但是没有考虑到值约 简所产生的新的不一致性，在所得到的规则集仍然会出现一些矛盾的规则。因此， 使用区分矩阵进行值约简有待进一步研究。 ( 2 ) 启发式值约简 文献 2 7 】以相对正域作为附加信息，依次考虑删除每个属性值是否改变其相 对正域来进行属性值约简。该方法的优点在于使属性的简化和属性值的简化一次 完成，形成一张对核值做记号的核值表。标记法【2 8 1 1 2 9 l 就是从值核入手对信息表中 的条件属性逐个考察，根据属性值对信息表的不同影响做出不同的标记，针对不 4 硕士学位论文 第一章绪论 同的标记做不同的处理。 以相对正域作为启发信息的不足之处在于没有考虑到边界域，为此文献 2 7 只能得到一致性表的值核，文献 2 8 的算法所得到的规则存在着一定程度上的冗 余，文献 2 9 虽然对此作出了改进，从决策表的值核入手，再分析值核以外的属 性，同时引入了决策树i d 3 算法中对属性的熵评价方法，加入了置信度、支持度 等概念。但是该算法需要考虑某些属性值的恢复问题，实际计算很不方便，计算 复杂度也比较大，而且这些算法仍然只针对一致性决策表，没有考虑存在不一致 性对象的情况，对不一致性规则不能进行简化。 文献 3 0 提出一种最简规则挖掘方法，可以挖掘出满足给定精确度的最简产 生式规则，该方法简洁有效，但是它通过人为给定分类正确度来修改不一致对象 决策值，最后所得到的规则可能与原信息系统不一致。文献 3 1 提出一种基于分 布约简的规则获取方法，采用启发式算法计算分布约简，挖掘出最简产生式规贝i j 。 ( 3 ) 基于规则质量的值约简 值约简的前提是在保证不改变决策表的分类能力的条件下对决策表进行化 简。因此，在对决策表进行值约简时，先将经过属性约简后的决策表的每一行看 成一条决策规则，计算每条规则的质量，然后删除该决策规则的每个属性，根据 该决策规则质量的变化决定其是否被删除。目前常用的衡量规则质量【3 2 1 的方法包 括经验公式法1 3 3 j ，关联性衡量，一致性衡量，信息量衡量1 ，逻辑完备性衡量以 及差别性衡量。 基于粗糙集的值约简研究存在诸多问题，均有待进一步发展和完善，这也是 开展本文研究工作的基点和出发点。 1 3 论文主要工作 现实世界的数据常常存在着冗余，因此有必要将由大量数据所构成的数据库 进行值约简，删除那些无意义的数据，使其变换为相对自然简洁的表示。经过值 约简后得到的规则能更适用于大多数训练样例中的样本，用尽量少的规则来代表 训练样例中所有的样本，而且规则支持度增大，能提高规则泛化能力和决策分析 的有效性，克服噪声对数据分析的影响。 值约简就是去除多余的属性值用最少的条件属性来区分每个决策类，为进一 步求完备规则集和研究匹配规则打下基础。很多学者对它进行了研究并提出了不 同的值约简思想和方法，如区分矩阵法，启发式值约简法，但是目前的这些值约 简算法主要是针对一致性决策表，对不一致性决表p i 不能很好适应。因此，对不 一致性决策表进行值约简成为粗糙集理论的热门研究课题，有着广泛而深远的应 5 硕士学位论文第一章绪论 用价值。 本文将粗糙集理论与值约简相结合，围绕值约简的特点分析、值约简在粗糙 集数据处理中的作用和值约简的方法的原理和特性展开论述，分析值约简方法中 存在的问题，提出新的区分矩阵并论述其性质和优点。从代数方法和概率方法两 个方面重点论述不同的值约简方法的原理、过程及其性质，在值约简方法的特性、 算法的改进以及值约简层次的建立等方面展开了深入的研究，提出自己的观点和 看法。主要研究内容包含以下几个方面： ( 1 ) 分析规则获取的过程及本质，在此基础上给出一种基于粗糙集理论的启 发式规则获取方法。其特点在于：首先求取规则的核值属性作为获取规则约简的 基础；再采用启发式算法，根据属性重要度值求得规则的最小约简，从而避免了 n p 完全问题。该算法简便、直观，易于从本质上体现规则获取的过程及实质。 ( 2 ) 在分析现有的值约简理论与方法的基础上，将区分矩阵引入值约简，分 析了经典区分矩阵用于值约简存在的问题以及导致出现错误规则的原因，给出一 种改进的区分矩阵，考虑到值约简可能导致的新的不一致性，从而有效地应用区 分矩阵得到规则集。 ( 3 ) 给出值约简形式化描述，通过粗糙集模型值约简异常分析，阐述值约简 层次与异常的关系，进而给出一种基于局部熵的值约简算法，挖掘出最简产生式 规则。该方法能适应决策表的不一致情形，且运用此方法所提取的规则集能够保 持与原信息系统一致。 ( 4 ) 当新对象加入时需更新规则集，为避免重新运行规则获取算法，本文所 设计的增量式算法将浓缩后数据存放于另一专用决策表中，在原有规则集基础上 进行规则知识库的增量式更新，减少了规则产生过程中的搜索空间范围，算法简 洁且易于实现。 1 4 论文组织结构 本文共分五章： 第一章绪论。主要介绍研究背景、国内外研究现状，阐述了本文主要工作及 其创新点； 第二章介绍粗糙集理论并阐述值约简的概念。首先介绍粗糙集理论的基础内 容，包括知识表达与决策信息系统、上下近似与粗糙集合、决策规则等基本概念； 然后阐述值约简、区分矩阵的概念，以及决策规则的度量。 第三章论述值约简的代数方法。首先描述了核值属性的概念，阐述了相对正 域的启发式值约简算法，然后详细讨论经典区分矩阵与值约简存在的问题，提出 6 硕士学位论文 第一章绪论 了一种改进的区分矩阵，论述了基于区分矩阵的值约简方法以及规则知识库的增 量式更新的基本思想、步骤及算法，通过理论和实验两方面对性质进行分析。 第四章论述值约简的信息论方法。对值约简进行了形式化描述，通过值约简 异常分析，阐述值约简层次与异常的关系，最后提出了一种基于局部熵的值约简 算法，并通过实验验证该方法的有效性。 第五章总结论文的研究工作，对未来的研究工作进行展望，并提出进一步研 究的方向。 1 5 本章小结 本章主要简介粗糙集理论的诞生背景、发展历程、以及一些基本特点；结合 信息检索领域综述国内外相关研究现状；简述本文的研究内容；最后给出论文的 总体结构组织。 7 硕士学位论文 第二章粗糙集理论概述 第二章粗糙集理论概述 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想是 在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规则。目 前，粗糙集理论已被成功地应用于机器学习、决策分析、过程控制、模式识别与 数据挖掘等领域。 2 1 粗糙集基本概念 粗糙集理论认为知识是对对象进行分类的能力，在不可分辨关系的基础上引 入上、下近似等概念来刻画知识的不确定性，度量属性的重要性和知识的依赖性， 通过属性约简和值约简等过程完成不精确、不确定和不完备数据的分析与处理， 从原始数据集中获取规则和知识。 2 1 1 上、下近似 粗糙集理论认为知识是将对象进行分类的能力。假定我们起初对全域里的元 素具有必要的信息或知识，通过这些知识能够将其划分到不同的类别，若我们对 两个元素有相同的信息，则它们就是不可分辨的( 即根据已有的信息不能够将其 分开) ，显然这是一种等价关系。， 定义2 1 设u 是非空有限论域，月是u 上的二元等价关系，序对i s = ( u ，尺) 称为近似空间。v ( x ，y ) ( u xu ) ，若( x ，y ) r ，则称对象工和y 在近似空间俗 是不可分辨的。 定义2 2 在近似地定义r o u g h 集时，要借用上近似集和下近似集两个概念： 星( x ) = u r u i n o ( r ) a y x ) 足( x ) = u r u m o ( r ) a y n x 彩) 其中星( x ) 和e ( x ) 分别为x 的r 上近似和r 下近似，y 是u 上按等价关系 r 生成的等价类。下近似为所有被包含在z 中的等价类的并集，上近似为所有与 x 交集不为空的等价类的并集。 定义2 3 关于r ，x 可分为以下几种情形： ( 1 ) 星( x ) = r ( x ) ，x 称为可定义的； ( 2 ) r ( x ) oa n dj r ( x ) u ，x 称为粗糙可定义的； ( 3 ) 星( x ) aa n dr ( x ) = u ，x 称为外部不可定义的； ( 4 ) r ( x ) = aa n d 尺( x ) u ，x 称为内部不可定义的； 8 硕士学位论文 第二章粗糙集理论概述 ( 5 ) 星( x ) = oa n d 月( j ) = u ，x 称为完全不可定义的。 定义2 4 上近似与下近似之间的差称为x 的r 边界( 域) ，表示为： b n r ( x ) = r ( x ) 一星( x ) 边界是那些既不能在x 上被分成等价类，也不能在叫上被分成等价类的元 素的集合。边界域为空，则可通过等价关系恰当地观察k 否则只能r o u g h 地观 察x 。 近似精度a r ( x ) = c a r d ( r ( x ) ) c a r d ( - r ( x ) ) ，表示获得关于x 的知识是否完 全的程度。其中c a r d ( y ) 表示集合】，的基数。显然，对每一个r 和x u 有 0 砧( x ) s l 。因为星( x ) r ( x ) j c a r d ( r ( x ) ) c a r d ( r ( x ) ) ，所以 0 a r ( x ) 1 。当a 宠( x ) = 1 时，b n r ( x ) = r ( x ) - r ( x ) ，此时x 是可精确定义 的；当a r ( x ) 1 时，【薯k 则是不一致性等价类。m i n l d ( x , ) i ，f d ( ) 1 ) 1 表示等价类【】c 和【k 都 是不一致性等价类。这种区分矩阵考虑了将一致性的条件等价类和不一致性的条 件等价类区别对待。 定义2 1 4 决策信息系统馏= ( u ，a = c u d ，v ，f ) 的区分函数定义为： 1 4 硕士学位论文第二章粗糙集理论概述 胛( 俗) = a v d m i ，】) j g s j 其中符号 和v 是指布尔逻辑中的合取与析取运算符，v d m i ，j 】是指区分矩阵 项d m i ，j 】中的所有属性的析取表达式。通过布尔运算，将区分函数胛( 胚) 由 合取范式转化为极小析取范式，其极小析取范式中的所有合取式是决策信息系统 尽的所有约简。 根据区分矩阵和区分函数的定义，基于区分矩阵和逻辑运算的约简过程很简 单：首先对决策信息系统中的所有实例进行逐对比较，得到决策信息系统的区分 矩阵；再次，对区分函数进行逻辑运算，将其转化为极小析取范式；最后，输出 极小析取范式中的所有合取范式( 即决策信息系统的所有约简) 。 区分函数的化简就是属性的约简，通过逻