（系统工程专业论文）基于粗集理论的信息系统的属性约简算法研究.pdf

摘要 摘要 粗集理论在经历了2 0 多年的发展之后，已经在理论和应用上取得了丰硕的 成果。它具有很强的分析能力，不需要数据之外的先验知识，成为处理不精确、 不确定、模糊性知识的新的有力的数学分析工具。本文对粗集理论中信息系统的 属性约简算法及应用进行了研究，提出了两个新的属性约简算法。 本文的主要工作体现在： 1 介绍了粗集理论的基本概念和不完备信息系统对粗集理论的扩展。 2 介绍了知识的粒度和不完备信息系统的知识粒度，指出了粒度原有定义 的不足，改进了粒度的计算公式。 3 介绍了粗集理论中属性约简的有关理论，分析了各种已有的属性约简算 法，提出了两个新的、可通用于完备信息系统和不完备信息系统的算法 基于粒度的信息表属性约简算法( b g m a ) 希j 基于分类质量的决策表 属性约简算法( b r d r a ) ，并用实例证明了新算法的有效性。 4 介绍了数据融合目标识别的有关理论、方法，应用新的属性约简算法 b r d r a ，对目标识别中可能存在的不完备情况进行了探讨。 关键词：粗集：信息系统：属性约简 a b s l r a c t a b s t r a c t a f t e rm o r et h a n2 0y e a r so fd e v e l o p m e n t ，g r e a ta c h i e v e m e n t sh a v eb e e nr e c e i v e d b o t hi nt h e o r e t i ca n da p p l i c a t i o nf i e l d si nr o u g hs e t ( r s ) t h e o r y r st h e o r yh a sv e r y s t r o n gq u a l i t a t i v ea n a l y s i sa b i l i t y ；i td o e s n tn e e da n yp r e l i m i n a r yo ra d d i t i o n a l i n f o r m a t i o nb e y o n dt h ed a t as e t i ti san e wp r o m i s i n gt o o lf o rd e a l i n gw i t hi m p r e c i s e ， i n c o m p l e t ea n du n c e r t a i nd a t a t h i sp a p e rm a i n l y m a k e sr e s e a r c ho na t t r i b u t e r e d u c t i o na l g o f i t h r n so fi n f o r m a t i o ns y s t e m sa n di t sa p p l i c a t i o nb a s e do nr st h e o r y ， a n d p r o v i d e st w on e wa l g o r i t h m s 0 u rw o r kl i s t sa sb e l o w ： 1 i n t r o d u c et h eb a s i ct h e o r i e so fr sa n dt h ee x t e n s i o no fr su n d e r i n c o m p l e t ei n f o r m a t i o ns y s t e m s 2 i n t r o d u c e k n o w l e d g eg r a n u l a t i o n a n dk n o w l e d g eg r a n u l a t i o no f i n c o m p l e r ei n f o r m a t i o ns y s t e m s ，p o i n to u tt h el i m i t a t i o no fp r i m a r y d e f i n i t i o no f g r a n u l a t i o n ，a n di m p r o v et h ef o r m u l a 3 i n t r o d u c ea t t r i b u t er e d u c t i o ni nr st h e o r y ，s u m m a r i z es o m ek i n d so f a l g o r i t h m s ，a n dp r o v i d et w on e wa l g o r i t h m s - - - - b g i r a ，b r d r a ， w h i c hc a nb eu s e di nc o m p l e t ei n f o r m a t i o ns y s t e m sa n di n c o m p l e t e i x f f o r m a t i o ns y s t e m s ，a n dp r o v et h ev a l i d i t yb ys o m ee x a m p l e s 4 i n t r o d u c et h et h e o r ya n dm e t h o do fd a t af u s i o na n dt a r g e tr e c o g n i t i o n ， a n dt h e na p p l yb r d r at ot a r g e tr e c o g n i t i o n ，a n da n a l y z es o m e i n s t a n c e so f a p p l i c a t i o ni nt a r g e tr e c o g n i t i o n k e yw o r d s ：r o u g hs e t ；i n f o r m a t i o ns y s t e m ；a t t r i b u t er e d u c t i o n 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成 果。本人在论文写作中参考的其他个人或集体的研究成果，均在 文中以明确方式标明。本人依法享有和承担由此论文产生的权利 和责任。 声明人( 签名) ：j 诏d 叠棚6 年墨窍日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦 门大学有权保留并向国家主管部门或其指定机构送交论文的纸 质版和电子版，有权将学位论文用于非赢利目的的少量复制并允 许论文进入学校图书馆被查阅，有权将学位论文的内容编入有关 数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密 的学位论文在解密后适用本规定。 本学位论文属于 1 、保密() ，在年解密后适用本授权书。 2 、不保密( 、) ( 请在以上相应括号内打“4 ”) 作者签名：孑锯1 i i 导师签名： 日期：扒存朋动日 日期：年月 i ：t 第一章绪论 1 1 粗集理论的特点 第一章绪论 z p a w l a k 教授在1 9 8 2 年提出粗集理论1 1 1 后，1 9 9 1 年出版了第一本关于粗 集理论的专著闭和1 9 9 2 年r s l o w i n s k i 主编的论文集3 1 推动了国际上对粗集理论 的深入研究。1 9 9 2 年在波兰召开了第一届国际粗糙集合研讨会之后，每年都召 开一次以粗集理论为主题的国际研讨会，从而推动了粗集理沧的发展和应用。另 外，国际上还成立了十余个国家的学者参加的粗集学术研究会。目前粗集理论已 成为人工智能领域中一个较新的学术热点，引起了越来越多的科研人员的关注。 粗集理论是一种刻划不完整性和不确定性的数学工具，能有效地分析和处理 不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在 的规律，它具有许多优点 4 】： ( 1 ) 粗集理论在数学上非常严密，有一整套处理数据分类问题的数学方法， 特别是当数据是不确定、不完整和不精确的时候。 ( 2 ) 粗集理论将知识定义为不可分辨关系的簇，因此知识有比较清晰的数学 含义，很方便用数学方法来分析处理。 ( 3 ) 基于粗集的计算方法非常适合并行处理，粗集计算机的研制工作已在进 行之中。 ( 4 ) 粗集理论和模糊逻辑、神经网络、概率推理、信度网络、遗传算法、混 沌理论一起形成了软计算方法的基础，为问题的处理提供了鲁棒性较强和成本较 低的解决方案。 ( 5 ) 粗集理论的实用性很强，粗集理论是为丌发自动生成规则系统而提出 的，因而它的研究完全是应用驱动的。 ( 6 ) 粗集理论无需提供除问题所需处理的数据之外的任何先验信息，这是和 模糊理论与证据理论等理论的最大的区别。 ( 7 ) 粗集理论能发现数据中隐含的模式和关系，对数据进行约简，评价数据 的重要性，从数据中产生规则，结果易于被理解。 基于粗集理论的信息系统的属性约简算法研究 作为独立的理论框架，粗集理论能有效地处理下列问题：彳i 确定或不精确知 识的表达、经验学习、知识分析、矛盾分析、不确定推理、基于信息保留的数据 简化、近似模式分类、识别并评价数据间的依赖性、发现数据中因果关系、发现 数据中的相似性和区别、从数据中产生决策算法、基于一致性评价信息质量。 1 2 粗集理论的研究现状 目前对粗集理论的研究主要集中在以下几个方面： ( 1 ) 粗集的数学性质 对粗集数学性质的研究，主要包括集合和分类近似的性质、决策表性质、代 数结构、粗集逻辑、粗集拓扑结构等问题，它们是粗集理论形成和发展的基础 m ，l 9 1 。 ( 2 1 属性值的离散化 因为粗集理论只能处理离散型数据，所以在实际应用时，要先对连续属性值 进行离散化处理。离散化处理要在粗集理论分析的其他环节之前，属于粗集理论 中的数据预处理问题之一【2 0 1 。连续属性的离散化使得粗集理论对离散和连续的属 性都能处理，扩大了粗集理论的应用范围。 ( 3 1 核集与约简的求取 核集和约简的求取是粗集理论中的两个核心内容，在数据的约简过程中发挥 着重要作用。核集是绝对必要的属性集合，找出核集可以核集为起点，求取属性 约简，往往能大大减少计算量 5 1 - 5 3 】。约简往往不惟一，求出所有的最小约简是 n p 难题，故常采用启发式方法找出最优或次优约简。 ( 4 ) 粗集模型的拓展 经典粗集不能用于不确定信息建模，而现实数据大多是不精确的。概率粗集 模型通过条件概率来定义概念的一e 下近似5 4 1 。可变精度粗集模型( v p r s ) 5 5 , 5 6 1 在基本耜集模型的基础上，引入( o s 7 o 5 ) ，即允许一定程度的错误分类率。针 对经典粗集中等价关系条件太强的缺陷，提出了用容差关系、相似关系、量化容 差关系、限制容差关系、基于联系度的容差关系、基于加权联系度的容差关系等 代替传统的等价关系的关系模型 2 5 - 2 7 5 7 , 5 8 j 。 ( 5 ) 与其方法的结合与互补 第一章绪论 粗集与模糊集合 模糊集用隶属度描述不确定性信息，粗集是用正域、负域和边界域处理不精 确信息。对粗集与模糊集关系的研究见文献 4 9 , 5 9 , 6 0 】。文献【6 l 讨论了基于模糊划分 的集合近似问题，提出了粗模糊集和模糊粗集的概念。 粗集与证据理论 文献【6 2 】研究了粗集与证据理论的关系。前者使用上下近似而后者使用信任函 数和似然函数作为处理不确定性的工具。粗集中的近似质量由数据本身得出，而 信任( 似然) 值需要专家人为设定，因此粗集具有客观性，而证据理论带有一定 的主观性。 粗集与概念格理论1 6 3 , 6 4 】 概念格又称为o a l o i s 格，也是建立在分类基础上，但比分类有更大的概括性， 它往往在归纳几个分类的基础上，产生一个概念。根据数据集中对象与属性之间 的二元关系，建立对象集与属性集之间的某种对应。概念将属性与对象作为统一 体，更好地反映了人的思维特征。概念格理论与粗集理论有所不同，又有共性， 可相互借鉴，相互促进。 1 3 粗集理论的应用 粗集理论具有较强的实用性，从诞生到现在虽然只有二十几年的时间，但已 经在许多领域取得了较好的应用成果。文献1 5 蚧绍了粗集理论在股票数据分析、 模式识别、地震预报、冲突分析、知识发现、粗糙控制、医疗诊断、专家系统、 人工神经元网络、决策分析等中的具体应用，目前有关粗集理论的应用主要包括 以下几个方面： ( 1 1 数据挖掘与规则生成 数据挖掘与规则生成是粗集理论在实际中最主要的应用。介绍这方面的文献 非常多，主要包括网络应用方面、管理科学领域的应用方面、医疗诊断等方面。 ( 2 ) 决策评价 利用粗集理论还可以进行决策评价，以给决策者提供正确的决策参考意见。 文献f 6 7 1 介绍了有关绿色评价的理论。 ( 3 ) 模式识别 基十租集理论的信息系统的属性约简算法研究 粗集理论的另一个主要应用就是模式识别功能。文献0 1 5 0 】介绍了粗集理论 在该方面的应用情况。 ( 4 ) 故障诊断 故障诊断是一个涉及到有效决策制定的复杂而困难的问题，针对机械结构复 杂和存在多激励源等造成故障诊断困难这一难题，可以通过粗集建立机械故障诊 断决策表，运用粗集的属性约简，消除冗余特征，获取简化了的决策规则，再与 神经网络、模糊理论等方法相结合，可以得到较好的诊断结果，这类文献很多， 如文献【1 2 6 5 1 。 ( 5 ) 数据融合目标识别 数据融合目标识别涉及的理论非常丰富，但是传统的方法存在一定的缺陷和 不足，将粗集理论引入目标识别领域中，可以取得比较令人满意的识别结果。文 献【。3 1 7 “74 8 j 介绍了有关这方面的较新的应用情况。 1 4 本文的工作和组织 1 4 1 本文的工作 1 、介绍了粗集理论的基本概念及其思想内涵，以及不完备信息系统对粗集 理论的扩展。 2 、介绍了知识粒度的概念，分析了原有粒度定义的不足，改进了粒度的计 算公式。 3 、介绍了粗集理论中属性约简的有关理论和方法，归纳分析了各种属性约 简算法，指出各个算法的优劣，提出了两个新的约简算法基于粒度的信息表 属性约简算法( b g i r a ) 和基于分类质量的决策表属性约简算法( b r d r a ) ，并 用实例证明了新算法的有效性。 4 、介绍了数据融合目标识别的理论、方法，将基于分类质量的决策表属性 约简算法应用于目标识别的实例中，对目标识别中存在不完备数据的情况进行了 一定的探讨。 1 4 2 本文的结构安排 本文由六章组成。 4 第一章绪论 第一章绪论 简要介绍了粗集理论的特点，研究现状，实践中的应用情况及本文的结构安 排。 第二章信息系统和粗集基本理论 介绍了知识和知识库及信息系统的类型，阐述了粗集理论的基本概念及其思 想内涵。 第三章知识的粒度 介绍了知识的粒度，分析了原有粒度定义的不足，改进和统一了粒度的计算 公式。 第四章信息系统属性约简算法研究 归纳总结了信息系统属性约简的各种已有算法，提出了两个新的算法一基 于粒度的信息表属性约简算法和基于分类质量的决策表属性约简算法，对比指出 新算法的特点，并用实例证明了算法的有效性。本章是重点。 第五章b r d r a 在目标识别中的应用探讨 介绍了数据融合目标识别的理论、方法，探讨了目标识别应用中的不完备情 况。 第六章总结 对本次工作的总结及以后工作的展望。 摹于粗集理论的信息系统的属性约简算法研究 第二章信息系统与粗集基本理论 知识表达是智能信息系统的关键。信息系统这个概念作为智能信息处理领域 的一个具有形式化定义和明确语义的专业术语，最初出现于波兰学者z p a w l a k 提出的粗集理论0 - 3 a 9 , 2 0 j 。基于粗集理论的知识发现，主要是借助于信息系统这 样一种有效的数据表知识表达方式。 粗集理论是一种刻划不完整性、不确定性的一个强有力的数学工具，能有效 地分析不精确( i m p r e c i s e ) 、不一致( i n c o n s i s t e n t ) 、不完整( i n c o m p l e t e ) 等各 种不完备的信息，还可以对数据进行分析和推理，从中发现隐含的知识，揭示潜 在的规律。它是。种关于数据推理的新方法，既不同于统计方法，也不同于模糊 集合论处理不精确数据的方法，最主要的是它不需要任何数据以外的先验知识。 因为它具有诸多优点，所以成为知识发现和决策领域的一个研究热点。自诞生以 来，在众多科研工作者和学者的共同努力下，研究已经历了1 0 多年的时间，无 论是在系统理论、计算模型的建立和应用系统的研制开发上，都已取得了丰硕成 果，也建立了一套较为完善的粗集理论体系。本章将首先介绍知识、信息系统、 决策表的基本概念，然后介绍粗集的基本理论，如上近似、下近似、正域、负域、 边界域、属性约简等内容，并针对实际中往往存在不完备的数据，结合不完备信 息系统，引入限制容差关系，对粗集的有关理论进行扩展。 2 1 知识与知识库 从认知科学的一些观点看，认为知识来源于人类以及其他物种的分类能力， 本文中，认为信息系统的知识发现问题本质上是按照属性特征将对象进行分类的 问题。通常，我们在对现实问题进行处理的时候，会将讨论的现实个体局限在某 一个特定的区域范围之内，这个区域内的所有个体就组成问题的论域u 。以分类 为基础，可以将分类理解为等价关系，而这些等价关系对论域u 进行划分。对 于论域中由等价关系划分出的任意子集x ，都可称之为u 中的一个概念。我们 认定空集。也是一个特殊的概念。论域u 中的任意概念簇称为关于u 的抽象知 识，简称为知识，它代表了对u 中个体的分类。这样，知识就可以定义为：给 第二章信息系统与粗集基本理论 定一组数据集合u 和等价关系集合r ，在等价关系集合r 下对数据集合u 的划 分，称为知识，记为u r 。u 上的一簇划分( 对u 的分类) 称为关于u 的知识 库。 设u 是一个论域，r 是u 上的一个等价关系。u r 表示u 上由r 导出的所 有等价类。【叫。表示包含元素x 的r 的等价类，x u 。一个知识库就是一个关 系系统k = u ，p ) ，其中u 是论域，p 是u 上的一个等价关系簇。如果q c p ， 且q o ，则n q ( q 的所有等价关系的交) 也是一个等价关系，记作i n d ( q ) 。 2 2 信息系统1 1 8 l 信息系统的基本成分是研究对象的集合，关于这些对象的知识是通过指定对 象的属性和它们的属性值柬描述的。一般地，一个信息系统s 可以表示为四元组， s = ( u ，r ，v ，) ，其中u 为论域，是对象的非空有限集合；r 是属性的非空有限 集合：v = u v r 是属性值的集合，矿表示属性r r 的属性值范围，即属性r 的值 r e r 域；厂：u r 斗v 是一个信息函数，它指定u 中每一个对象x 的属性值。通常 信息系统s = ( u ，r ，v ，厂) 也可简记为s = ( u ，r ) 。 信息系统的数据以关系表的形式表示。关系表的行对应要研究的对象，列对 应对象的属性，对象的信息是通过指定对象的各属性值来表达的。容易看出，一 个属性对应一个等价关系，一个表可以看作是一族等价关系，即知识库。 对于每个属性子集p r ，定义属性集p 的不可区分关系i n d ( p ) 为 i n d ( p ) = ( x ，y ) u 2 l v r p ，f ( x ，) = f ( y ，r ) ) ( 2 1 ) 如果( x ，y ) i n d ( p ) ，则称x 与y 是p 不可区分的。容易证明v p c r ，不可区 分关系i n d ( p ) 是u 上的等价关系，符号u i n d ( p ) 表示不可区分关系i n d ( p ) 在u 上导出的划分，i n d ( p ) 中的等价类称为p 的基本集，符号 x 】p 表示 包含x e u 的p 等价类。 在不产生混淆的情况下，也可用p 来代替i n d ( p ) ，u i n d ( p ) 可简记为 u p 。 令p 、q c r ，p ! q ( 或u i n d ( p ) - u i n d ( q ) ) 表示对任意x e i n d ( p ) ，存 在y a u i n d ( q ) ，使得x e y 。这意味着p 的划分比q 更精细，或者q 的划分 基于粗集理论的信息系统的属性约简算法研究 比p 更粗糙。p q ( 或u i n d ( p ) u i n d ( q ) ) 表示对于任意x 1 n d ( p ) ，存在 y u i n d ( q ) ，使得x y ，且存在x o i n d ( p ) ，v o e u i n d ( q ) ，使得x o c v o 。 下面讨论两个信息系统的关系。 令s l = ( u ，r 1 ) 和s 2 = ( u ，r 2 ) 为两个信息系统。若1 n d ( r 1 ) = i n d ( r 2 ) ， 即u r l - u 瓜2 ，则称s l 和s 2 ( 或r l 和r 2 ) 是等价的，记作s i = s 2 ( 或r l = r 2 ) 。 这意味着可以用不同的属性集对对象进行描述，以表达关于论域u 的完全相同 的事实。 对于s i = ( u ，r i ) 和s 2 = ( u 。r 2 ) 两个信息系统，当1 n d ( r 1 ) i n d ( r 2 ) 时，称信息系统s 1 ( 或属性集r t ) 比信息系统s 2 ( 或属性集r d 更精细，或者 称s 2 比s 1 更粗糙。 信息系统s = ( u ，r ) 也可称为知识表达系统或知识r 。 令u r = x l ，x 2 ，x n ， 其中，有趣的是最小划分： r ( = “x l x e u ( 2 2 ) 和最大划分： 只( = ( u ) ( 2 3 ) 在不引起混淆的情况下，也可以将五( 和五( u ) 简记为盖和j 毛。 例2 1 表2 1 给出一个关于玩具积木的信息系统。 表2 1 玩具积木信息系统 样本集u颜色( a 1 )形状( a 2 )大小( a s ) x i r e dr o u n ds m a l l x 2 b l u e s q u a r el a r g e x 3 r e d t r i a n g u l a r s m a l l x 4 b l u e t r i a n g u l a r s m a l l x 5 y e l l o wr o u n d s m a l l x 6 y e l l o w s q u a r e s m a l l x 7 r e d t r i a n g u l a rl a r g e x 8 y e l l o w t r i a n g u l a rl a r g e 资料米源：干国胤：( r o u g h 集理论与知识获取，西安交大出版社，2 0 0 1 年5 月。 第二章信息系统与粗集基本理论 表中论域u = 。l ，x 2 ，x 3 , x 4 , x 5 ，x 6 ，x 7 ，x 8 ) ，属性集合r _ a l ，a 2 ，a 3 ) ，根据这个信息 系统，可以得到有关的概念描述，如将玩具积木按照颜色、形状、大小可以分别 进行如下分类，得到有关玩具积木的知识： u a t 2 “x i ，x 3 ，x t ， x 2 ，x 4 ， x 5 ，x 6 ，x 8 ) ) ； u a 2 2 “x 1 ，x s ， x 2 ，x 6 ， x 3 ，x 4 ，x 7 ，x 8 ) ： u a 3 = “x l ，x 3 ，x 4 ，x 5 ，x 6 ， x 2 ，x 7 ，x 8 ) ) 。 2 3 决策表 决策表也是一种特殊而重要的信息系统，它表示当满足某些条件时，决策( 行 为、操作、控制) 应当如何进行。可以定义为：设一信息系统s = ( u ，r ，v ，f ) ， r = c ud 是属性集合，c 和d 分别称为条件属性和决策属性，具有条件属性和决策 属性的信息系统称为决策表。有时为区别于决策表，信息系统也简称为信息表。 一个决策表中的决策属性有时是唯一的，称为单一决策表；有时不是唯一的， 称为多决策表。对于有多个决策属性的决策表，可以通过两种方法变换成为单一 决策表： 方法一是将原决策表中其余决策所对应的列去掉而得到新的单一决策表； 方法二是综合多决策表中所有决策属性的取值来形成一个综合决策，从而将 多决策问题转化为单一决策问题。 本文中所讨论的决策表，不做特别说明，都是单一决策表。 例如表2 _ 2 就是一个决策表。 表2 2 流感病例决策表 条件属性 样本集u决策属性 头疼肌肉疼体温 x i 是是正常否 x 2 是是高 是 x 3 是是很高 是 x 4否是正常 否 x 5 否否品 否 x 6 否是很高是 资料来源：工圉胤： r o u t 曲集理论与知识获取，西安交大出版社，2 0 0 1 年5 月。 基于粗集理论的信息系统的属性约简算法研究 2 4 粗集 令x c u ，r 为一等价关系，当x 能用属性r 确切地描述( 即是属性集r 所 确定的u 上的基本集的并时) ，我们称x 是r 可定义的，否则称x 为r 不可定 义的。r 可定义集是论域的子集，它可在知识库k 中被精确地定义，而r 不可 定义集不能在这个知识库中被定义。r 可定义集也称作r 精确集，r 不可定义集 也称为r 非精确集或r 粗集( 在不发生混淆的情况下也简称粗集) 。 当存在一等价关系r i n d ( k ) 且x 为r 精确集，集合x _ g u 称为k 中的 精确集；当对于任何r 1 n d ( k ) ，但x 为r 粗集，则x 称为k 中的粗集。粗 集可以近似地定义，为达到这个目的，使用两个精确集粗集的上近似集和下 近似集来描述。 假设给定知识库k = ( u ，r ) ，对于每个子集x g u 和一个等价关系r ，可以根 据r 的基本集合的描述来划分集合x ，下面两个等式分别是r 的下近似和r 的 上近似： r ( x ) 2 x u k k j ) j ( 2 4 ) r 。( x ) 2 工 ( x u x r 1 7 o ) ( 2 5 ) 即当且仅当 x 】r x ，x r ( x ) ；当且仅当【x 】r n x a ，x r - ( x ) 。 集合b n r ( x ) = r ( x ) & ( x ) 称为x 的r 边界；p o s r ( 均= i 乙( x ) 称为 x 的r 正域；n e g r ( x ) = u l r ( x ) 称为x 的r 负域。 r ( x ) 是根据知识r ，u 中所有一定能归入集合x 的元素构成的集合。r ( x ) 是根据知识r ，u 中所有一定能和可能归入集合x 的元素构成的集合。边 界b n r ( ) ( ) 是根据知识r ，u 中既不能肯定归入集合x ，又不能肯定归入集合x 的 元素构成的集合。正域p o s r ( x ) 是根据知识r ，u 中所有一定能归入集合x 的元 素构成的集合。负域n e g r ( x ) 是根据知识r ，u 中所有不能确定一定归入集合x 的元素的集合。边界域b n r ( x ) 是某种意义上论域的不确定域，边界域中的元素 既不能肯定地属于集合x ，也不能肯定地属于x 。 有了边界域的定义，可以得到上近似集、下近似集、正域、边界域之间的如 下关系： r - ( x ) = p o s r ( x ) ub n r ( x ) = r ( x ) ub n r ( x ) = u 、& ( x ) o 第二章信息系统与粗集基本理论 上近似、下近似、边界域等几个集合的基数之间有如下的关系： l u b n r ( x ) l = l u i - i r ( x ) & ( x ) l 例2 2 在表2 2 所示的决策表中，对于属性子集b = 头疼，肌肉疼) ，集合 x = x 2 ，x 3 ，x 5 ) 是一个粗集，下面分别计算集合x 的上近似集，下近似集，正域， 负域，边界域。 首先计算论域u 的所有b 基本集， u i n d ( b ) = “0 1 ，x 2 ，x 3 ，( x 4 ，x 6 ，( x 5 ， 令b i = x l ，x 2 ，x 3 ) ，b 2 = x 4 ，) ( 6 ) ，b 3 = x 5 ，集合x 与基本集有如下关系： x n b l = x 2 ，x 3 o ， x n b 2 = a ， x n b 3 = ( x d g 。 由此可得集合x 的上近似集、下近似集、f 域、边界域、负域： b ( x ) = b lub 3 = x 1 ，x 2 ，x 3 ，x 5 ) ， b ( x ) = b 3 2 。5 ) ， p o s b ( x ) = b ( x ) = b 3 = ( x 5 ， b n b ( x ) = b 12 ( x l ，x 2 ，x 3 n e g b ( x ) = u 、b ( x ) = x 4 x 6 根据上近似集、下近似集的定义，不难得到如下命题： 命题2 1 ( 1 ) 当且仅当r ( x ) = r - ( x ) ，称集合x 是r 可定义集； ( 2 ) 当且仅当r ( x ) r ( x ) ，称集合x 是r r o u g h 集。 也可将& ( x ) 描述为x 中的最大可定义集，将r _ ( x ) 描述为含有x 的 最小可定义集。 2 5 近似集的性质 从近似的定义，可以得到下近似集& ( x ) 和上近似集r - ( x ) 的下列性质 命题2 2 ( 1 ) r ( x ) x c _ r - ( x ) ， ( 2 ) ( a ) = r ( a ) = o ，r u ) 2r _ ( u ) 2 u ， 基于粗集理论的信息系统的属性约简算法研究 ( 3 ) r _ ( x u y ) = r - ( x ) ur - ( y ) ( 4 ) r ( x n y ) = r ( x ) nr ( y ) ( 5 ) x g y 蕴含r ( x ) & ( y ) ( 6 ) x c _ y 蕴含r ( x ) r ( y ) ( 7 ) r - ( x u ) & ( 均u r ( y ) ( 8 ) r ( x n 量r ( x ) nr ( y ) ( 9 ) r ( 一x ) = - r - ( x ) ( 1 0 ) r ( 一x ) 一r ( x ) ( 1 1 ) r ( & ( x ) ) = r - ( r ( x ) ) - r ( x ) ( 1 2 ) r ( r ( x ) ) = r ( r ( x ) ) = r - ( x ) 证明：( 略1 2 6 分类质量 粗集的不可定义性( 不确定性) 是由于粗集x 的边界不确定性引起的。集 合x 的边界区域越大，其确定性程度就越小。所以可以用集合x 的精度和粗度 这两个概念来描述粗集x 的不确定性程度。 定义2 1 假设集合x 是论域u 上的一个关于知识r 的粗集，定义其r 精度 ( 在不发生混淆的情况下，也简称精度) 为 d r ( x ) = l r _ ( x ) l l r 一( j ) i 其中，x g ：如果x _ g ，可定义d r ( ) 。= 1 。 由此可见，粗集x 的精度是一个g f 1 o ，1 】上的实数，它定义了粗集x 的 可定义程度，即集合x 的确定度。 定义2 2 假设集合x 是论域u 上的一个关于知识r 的粗集，定义其r 粗度 ( 在不发生混淆的情况下，也简称粗度) 为 p r ( x ) = 1 一d r ( x ) x 的粗度与精度恰恰相反，表示的是集合x 的知识的不完全程度。 根据粗集x 的上近似集、下近似集的特征，对粗集x 的不确定程度也可以 作如下定义： 假设集合x 是论域u 上的一个关于知识r 的粗集， 1 2 第二章信息系统与粗集基本理论 ( 1 ) 如果& ( x ) a 且r ( x ) u ，则称x 为r 粗可定义的； ( 2 ) 如果r ( x ) = a 且r ( x ) u ，则称x 为r 内不可定义的； ( 3 ) 如果& ( x ) g 且r - ( x ) = u ，则称x 为r 外不可定义的； ( 4 ) 如果r ( x ) = o 且r ( x ) = u ，则称x 为r 全不可定义的。 对于上面定义，可以作如下的直观理解： 当1 l ( x 1 = r ( x ) 时，集合x 的边界域为空，即根据属性集r 就可以完全 肯定地判定任何元素是否属于集合x ，即x 所对应的概念是一个确定的概念。 对于粗集，由于边界域的存在，导致部分元素不能够被确定地判定。如果x 为r 粗可定义的，意味着我们可以确定u 中的部分元素是否属于x 或x ；如果x 为 r 内不可定义的，意味着可以确定u 中的部分元素是否属于j ，但不能确定u 中的任一元素是否属于x ；如果x 为r 外不可定义的，意味着可以确定u 中的 部分元素是否属于x ，但不能确定u 的任一元素是否属于x ；如果x 为r 全不 可定义的，意味着不能确定u 的任一元素是否属于x 或x 。 对于例2 2 中的粗集x = x 2 ，x 3 ，x s ，b = 头疼，肌肉疼 ，x 就是粗可定义的， 因为 b ( x ) = b 1 u b s = x l ，x 2 ，x 3 ，x s u b ( x ) = b 3 = x 5 ) 囝。 x 的精度和粗度分别为 d r ( x ) = ( x ) l 1 8 一( j ) i 2l 4 = o 2 5 ， p r ( x ) = 1 d r ( x ) = 0 7 5 。 如果x = x 2 ，x 3 ，则x 就是内不可定义的，因为 b 一( x ) = b z = x j ，x 2 ，x 3 u b ( x ) = 。 x 的精度和粗度分别为 d r ( x ) = i b ( x ) l i b 一( x ) i = 0 4 = 0 ， p r ( x ) = 1 一d r ( x 产1 。 在论域u 中，如果集合簇f = x 1 ，x 2 ，x 。 ( u = u 置) 是论域u 上定义的知 t = l 识，可以定义属性子集b 描述这些知识的能力，即b 对f 完成分类的准确度。 基于粗集理论的信息系统的属性约简算法研究 定义2 3 设集合簇f = x i ，x 2 ，x n ( u = u 置) 是论域u 上定义的知识，b t = l 是一个属性子集，b 对f 近似分类的精度( 也可简称为分类精度) d ( b ，f ) 为 d ( 曰，r ) = i s _ x , ) i z i b 一( 玉) l j = li = l 定义2 4 设集合簇f = x 1 ，x 2 ，x 。) ( u = u z ) 是论域u 上定义的知识，b i = l 是一个属性子集，b 对f 的近似分类质量( 也可简称为分类质量) r ( b ，f ) 为 r ( b ，f ) = i b ( x j ) i i u i = 1 b 对f 的分类精度描述的是当使用知识b 对对象进行分类时，在所有可能 的决策中确定决策所占的比例：b 对f 的分类质量是应用知识b 对对象进行分 类时，能够确定决策的对象在论域中所占的比例。 例2 3 在表2 2 所示的决策表中，若f = x l ，x 2 ，x l = x 2 ，x 3 ，x 4 ，x 5 ) ，x 2 = x l ，x 6 ， 对于属性子集b = 头疼，肌肉疼) ，论域u 的所有b 基本集为 x l ，x 2 ，x 3 ， x 4 ，x 6 ， x 5 ) ) ， 令b i = x l ，x 2 ，x 3 ) ，b 2 = x 4 ，x 6 ，b 3 = x 5 ) ，有 b ( x 1 ) = x 5 ) o b ( x 2 ) = o b ( x 1 ) = x l ，x 2 ，x 3 ，x 4 ，x 5 ，x 6 = u ， b ( x 2 ) = x l ，x 2 ，x 3 ，x 4 ，x 6 ， d ( b ，f ) = ( 1 + 0 ) ( 6 + 5 ) = o 0 9 ， r ( b ，f ) 2 ( 1 + 0 y 62 0 1 7 。 2 7 属性约简 属性约简是粗集理论的核心内容之一。众所周知，信息系统中的属性并不是 同等重要的，甚至其中某些属性是冗余的。所谓属性约简，就是在保持信息系统 的分类能力不变的条件下，删除其中不相关或者不重要的属性。 定义2 5 设u 是一个论域，r 是定义在u 上的一个等价关系簇，p r ，如 果i n d ( m p ) = i n d ( r ) ，则称关系p 在r 中是绝对不必要的( 多余的) ；否 第二章信息系统与粗集基本理论 则，称p 在r 中是绝对必要的。 绝对不必要的关系在知识库中是多余的，如果将它们从知识库中去掉，不会 改变该知识库的分类能力。相反地，若去掉一个绝对必要的关系，则一定会改变 知识库的分类能力。 定义2 6 设u 为一个论域，r 为定义在u 上的一个等价关系簇，p r 。如 果每个关系p e r 在r 中都是绝对必要的，则称关系簇r 是独立的；否则，称r 是相互依赖的。 对于相互依赖的关系簇来说，其中包含有冗余关系，可以对其约简；而对于 独立的关系簇，去掉其中任何一个关系都将破坏知识库的分类能力，不能对其约 简。 定义2 7 设u 是一个论域，r 是定义在u 上的一个等价关系簇，r 中所有 绝对必要的关系组成的集合称为关系簇r 的绝对核，记作c o r e ( r ) 。 定义2 8 设u 是一个论域，r 和q 是定义在u 上的两个等价关系簇，且q c r 。 如果i n d ( q ) = i n d ( r ) ，并且q 是独立的，则称q 是r 的一个绝对约简。 如果知识q 是知识r 的绝对约简，那么，u 中通过知识r 可区分的对象， 同样可以用知识q 来区分。 定理2 1 对于任何信息系统s = ( u ，r ) ，约简总是存在的f 4 9 】。 证明若对于任意a r ，都有u ( r - f a ) ) u r ，则r 本身就是约简。若 a e r ，且有u ( r - a ) ) = u r ，则研究b i = r 一 a ) 。若对于任意b l b i ，都有u 瓜u ( b l 一 b 1 ) ，则b l 就是约简，若存在b l b l ，且有u 很- 1j ( b i - b 1 ) ) ，则再研 究b 2 = b 1 b 1 ) ，重复以上过程。由于r 是有限集，所以总能找到一个b c _ r ，使 u b = u r ，且u ( b b ) u r ( v b b ) 。这时，b 即为信息系统的一个约简a 一般地，信息系统的约简不是惟一的。 在讨论决策表属性约简的时候，一个条件属性对应着一个等价关系，它对论 域u 形成一个划分。决策表所有条件属性形成条件属性集合c 对论域u 的划分 u c ，同时，决策属性d 也对论域形成一个划分u d 。这两个划分形成了条件属 性和决策属性在对论域样本分类上的知识。属性约简的目的就是要从条件属性集 合中发现部分必要的条件属性，使得根据这部分条件属性形成的相对于决策属性 的分类和所有条件属性形成的相对于决策属性的分类一致，即和所有条件属性相 对于决策属性有相同的分类能力。这也就是决策表的相对约简。 基于粗集理论的信息系统的属性约简算法研究 定义2 9 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，q 的 p 正域记为 p o s p ( q ) =u p ( x ) x c d j ! 曾 定义2 1 0 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，若 p o s p ( q ) = p o s ( p q r p ( q ) ，则称r 为p 中相对于q 可省略的( 不必要的) ，简称p 中q 可省略的；否则，称r 为p 中相对于o 不可省略的( 必要的) 。 定义2 1 1 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，若p 中的每一个r 都是p 中q 不可省略的，称p 为( 相对于) q 独立的。 定义2 1 2 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，若p 的q 独立子集s c p 有p o s s ( q ) = p o s p ( q ) ，则称s 为p 的q 约简。记p 的所有q 约简关系簇为r e d q ( p ) 。 定义2 1 3 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，p 的 所有q 不可省略原始关系簇称为p 的q 核，记为c o r e q ( p ) 。 定义2 1 4 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，如果 p o s p ( q ) = u ，则称论域u 是p 上相对于q 一致的。 定义2 1 5 设u 是一个论域，p 和q 是定义在u 上的两个等价关系簇，r e d q ( p ) 为p 的所有q 约简关系簇，c o r e q ( p ) 为p 的q 核，则c o r e q ( p ) = r r e d o ( p ) 。 例2 4 下面用一个例子对相对约简和绝对约简加以说明口0 1 。 表2 3 关于气象信息的决策表 条件属性决策属性