（基础数学专业论文）基于改进限制容差关系的信息系统知识约简.pdf

西南交通大学研究生硕士学位论文第1 页 摘要 粗糙集理论是波兰科学家之p a w l a k 于1 9 8 2 年首先提出的一种数据分析 理论，目前已发展成为一种处理不确定性信息的数学理论，并且成功地应用 于机器学习、数据挖掘( d a t am i n i n g ) 、智能数据分析、控制算法获得等领域 p a w l a k 最初提出的粗糙集理论是建立在等价关系基础之上的，然而相应 的理沦不适用于处理不完备的信息系统，现实中不完备信息系统的广泛存在 极大地限制了粗集理论的应用领域于是在后来的粗糙集理论研究中，研究 者提出了各种扩充的粗糙集模型，如一般关系下的粗糙集模型、变精度粗糙集 模型、模糊粗糙集模型、概率粗糙集模型等针对不完备信息系统，为了刻划 对象间的不可区分关系，k r y s c k i e w c z 提出了容差关系；s t e f a n o w k i 等人提出了 非对称相似关系和量化容差关系；王国胤在容差关系和非对称相似关系基础 上提出了介于两者之间的限制容差关系本文在分析以上关系的基础上，提 山了改进限制容差关系该关系的特点是：通过引入阈值先将原不完备信息 系统进行划分，再利用联系度的概念确定改进限制容差类，基于产生的这些 类得到上下近似本文接着讨论了上下近似的代数性质，并把在完备信息系 统基础上建立的一些粗糙集理论的重要概念引入到不完备信息系统中，对不 完备信息系统进行了更深入地探讨 属性约简是信息系统知识发现研究的核心内容之一，对完备信息系统的 约简问题，目前学术界进行了大量的研究，其中包括基于正域的约简、基于信 息熵的约简、基于包含度的约简等本文基于改进限制容差关系，把正域约 简、信息熵约简以及张文修等针对不一致决策表提出的分布约简、分配约简、 最大分布约简和近似约简引入不完备信息系统，并讨论它们之间的关系，且 证明了对于相容的不完备决策表，熵约简、分布约简、正域约简、最大分布约 简、分配约简及近似约简都是等价的；文中通过定义属性的信息量，给出了分 配约简的一种启发式算法：条件信息量约简算法，分析了该算法的时间复杂 度经实验检验，该算法是有效的 关键词粗糙集；不完备信息系统；改进限制容差关系；知识约简；信息量 西南交通大学研究生硕士学位论文第页 a b s t r a c t r o u g hs e tt h e o r yi san e wt h e o r yo fd a t aa n a l y s i s ，i tw a sf i r s tp u tf o r w a r db y p o l a n ds c i e n t i s tz p a w l a k a tp r e s e n ti th a sd e v e l o p e dt ob ean e wm a t ht h e o r y t o o lt od e a lw i t hv a g u e n e s sa n du n c e r t a i n t y i th a sb e e na p p l i e dt om a n ya r e a s s u c c e s s f u l l yi n c l u d i n gm a c h i n el e a r n i n g ，p a r e mr e c o g n i t i o n ，d e c i s i o ns u p p o r t ， d a t am i n i n g ，p r o c e s sc o n t r o la n dp r e d i c t i v em o d e l i n g p a w l a kr o u g hs e tw a se s t a b l i s h e da tt h eb a s eo fe q u i v a l e n tr e l a t i o n b u ti t i s n o ts u i tt od e a lw i t hi 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 o mt h el a t e rr e s e a r c ho f r o u g hs e tt h e o r y t h er e s e a r c h e r sa d d r e s sa l lk i n d so fm o d e l si no r d e rt oe x p a n di t s a p p l y i n ga s p e c t e x a m p l e sa r eg e m e r a i i z e db i n a r y - r e l a t i o nr o u g hs e tm o d e l ， v a r i e t yp r e c i s i o nr o u g hs e tm o d e l ，v a g u er o u g hs e tm o d e l ，p r o b a b i t i t yr o u g hs e t m o d e le t c i no r d e rt od e s c r i b et h ei n d i s t i n c tr e l a t i o n s h i po fo b j e c t si ni n c o m p l e t e i n f o r m a t i o ns y s t e m k r y s c k i e w c zp r e s e n t e dt o l e r a n c er e l a t i o n ；s t e f a n o w k ie 琵 p r e s e n t e ds i m i l a r i t yr e l a t i o na n dq u a n t i t a t i v et o l e r a n c er e l a t i o n b a s e do nt h e s e r e l a t i o n s ，w a n gg yp r e s e n t sl i m i t e dt o l e r a n c er e l a t i o n ，f o l l o w e db yp r o v i n gt h i s m o d e li ss u p e r i o rt ot o l e r a n c er e l a t i o na n ds i m i l a r i t yr e l a t i o n i nt h i sp a d e r , t h e s e r e l a t i o n sa r ea n a l y z e da n di m p r o v e d1 i m i t e d t o l e r a n c er c l a t i o ni sp r e s e n t e d i nt h i s r e l a t i o n t h r e s h o l d sa r ei n t r o d u c e da n da ni n c o m p l e t es y s t e mi sd i v i d e di n t ot w o d a r t s t h ea i mo ft o l e r a n tr e l a t i o nb a s e do nc o n n e c t i o nd e g r e ei st oa s c e r t a i n c l a s s e sb yw h i c ht h el o w e ra p p r o x i m a t i o ns e ta n du p p e ra p p r o x i m a t i o ns e to fas e t i nu n i v e r s ea r ec o n f i r m e d i nt h es e c o n dp a r t ，t h i sp a p e rd i s c u s s e sa l g o r i t h m p r o p e r t ya n dp r e s e n t ss o m eu s e f u le x p l o r a t i o na b o u ti n c o m p l e t ei n f o r m a t i o n s y s t e mb yi n t r o d u c i n gs o m ei m p o r t a n td e f i n i t i o no f c o m p l e t ei n f o r m a t i o ns y s t e m 一 k n o w l e d g er e d u c t i o ni so n eo ft h em o s ti m p o r t a n tp r o b l e m si nt h es t u d yo f i n f o r m a t i o ns y s t e ma n dk n o w l e d g e ，d i s c o v e r y t h e r ea r em a n yt y p e so fk n o w l e d g e r e d u c t i o n si nt h ea r e ao fr o u g hs e t s i nt h i sp a p e r , s o m et y p e so fr e d u c t i o n so f c o m p l e t ei n f o r m a t i o na r ef i r s tp r e s e n t e dt oi n c o m p l e t ei n f o r m a t i o ns y s t e m f o l l o w e db yt h er e l a t i o n s h i pb e t w e e nt h e s er e d u c t i o nm e t h o d s ，a l s o ，f o r i n c o m p l e t ec o n s i s t e n td e c i s i o nt a b l e s ，e n t r o p yr e d u c t i o n ，d i s t r i b u t i o nr e d u c t i o n ， p o s i t i v ed o m a i nr e d u c t i o n m a x i m u md i s t r i b u t i o nr e d u c t i o n , a s s i g n m e n tr e d u c t i o n a n da p p r o x i m a t er e d u c t i o na r ea l lp r o v e dt ob ee q u i v a l e n t b a s e do nc o n d i t i o n i n f o r m a t i o nq u a n t i t y 。ah e u r i s t i ca l g o r i t h mf o ra s s i g n m e n tr e d u c t i o ni sp r e s e n t e d ， a n dt h ee o m p l e x i t yo ft h i sa l g o r i t h mi sa n a l y z e d f i n a l l y , t h ee x p e r i m e n t a lr e s u l t s h o w st h i sa l g o r i t h mc a nf i n dt h i sa s s i g n m e n tr e d u c t i o nf o ri n c o m p l e t e i n f o r m a t i o ns y s t e m k e y w o r d s ：r o u g hs e t ；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 ；i n f o r m a t i o nq u a n t i t y ； k n o w l e d g er e d u c t i o n 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 本章将介绍本文的写作背景并简要介绍本文的主要研究工作 1 1 引言 二十世纪七十年代初，波兰科学学院、华沙大学的学者组成了研究小组， 开始了对信息系统逻辑特性的长期基础性研究针对从实验中得到的以数据 形式表述的不精确、不确定、不完整的信息和知识，进行了分析，这一研究成 为粗糙集理论产生的基础1 9 8 2 一年z p a w l a k 发表了经典论文r o u g hs e t t ”1 ，宣 告了粗糙集理论的诞生由于最初的研究大多是以波兰文发表的，因此在当 时并未引起国际上数学界和计算机界的重视，研究地域局限于东欧各国，到 了八，卜年代术，这一理论终于引起了各国学术界的注意，许多数学家、逻辑学 家和计算机研究人员对粗糙集理论和应用产生极大兴趣并做了大量研究工作， 1 9 9 1 年z p a w l a k 出版的专著”r o u g hs e t ”【1 6 1 成为粗糙集理论研究的第一个里 程碑1 9 9 2 年应用专著【2 的出版对这时期的工作成果作了极好的总结，也 进一步促进了粗糙集理论的应用扩展1 9 9 2 年，第一界关于粗糙集理论的国 际学术会议在波兰召开；1 9 9 5 年，a c mc o m m u n i z a t i o n 将其列为新浮现的计 算机科学的研究课题；1 9 9 8 年，国际信息科学杂志( i n f o r m a t i o ns c i e n c e s ) 还 为粗糙集理论的研究出了一期专辑这些表明了粗糙集理论与应用的研究有 着广泛的发展前景 对于粗糙集的概念，目前研究者从不同的角度来定义：一种就是原始的 p a w l a k i5 1 意义下的，也有由上、下近似构成的一对集合来命名的【2 j ，还有以下 近似和上近似构成的区f 司集( 集合类) 来定义的【2 ”，定义观点的不同往往带 来研究的侧重面的不同目前，对粗糙集理论的研究主要集中在：粗糙集的模 型的推广，问题的不确定的研究，与其他处理不确定性，模糊性问题的数学理 论的关系与互补，纯粹的数学理论方面的研究，粗糙集的算法研究和人工智 能方向关系的研究等这些研究有的是受应用的推动而产生，有的是纯理论 的 i 1 1 粗糙集模型的推广 p a w l a k 粗糙集模型的推广一直是粗糙集理论研究的主流方向，目前主要 有一般二元关系下的粗糙集模型、变精度粗糙集模型、模糊粗糙集模型、概 率龃糙集模型等 1 1 2 不确定性问题的理论研究 西南交通大学硕士研究生学位论文第2 页 粗糙集理论中知识的不确定性主要由两个原因产生的：一个原因是直接 来自于论域上的二元关系及产生的知识模块，即近似空间本身从这个危度 看，处理知识的不确定方法往往用信息熵来刻画，知识的粗糙性实质上是其 所含信息多少的更深层次的刻画【3 0 ，不少学者在这方面做了研究工作口o 粗糙集理论中知识不确定性的另一个原因来自于给定论域里粗糙近似的边界， 当边界为空集时知识是完全确定的，边界越大知识就越粗糙或越模糊从这 个角度看，一些学者引进了粗糙熵e ，f ) 的概念来刻画x 的不确定性【l j 寻求一个合适的度量来刻画知识的不确定性也是粗糙集理论研究的一个 重要方向 一 1 1 3 粗糙集与其他处理不确定性问题理论的关系 在粗糙集理论与其他处理模糊性或不确定性方法的理论研究中，主要集 中在它与概率统计、模糊数学、d s 证据理论和信息论的相互渗透与补充 在信息系统中，知识库的知识的类型一般有两类：一类库中所有对象的描 述是完全已知的，p a w l a k 粗糙集模型和一般关系下的粗糙集模型就是属于这 一种：另一类库中的对象的描述只有部分是己知的，只能通过训练样本所提供r 的信息类刻画概念，抽取样本时应符合统计规律性，因此概率统计与粗糙集 理论的结合就显得非常自然 模糊集理论和粗糙集理论在处理不确定性和不精确性问题方面都推广了 经典集合论具有一定的相容性和相似性，然而它们的侧重面不同模糊集通 过对象关于集合的隶属程度来近似描述，而粗糙集通过一个集合关于某个可 利用的知识库的一对上、下近似来描述；模糊集强调边界的不分明性，而粗糙 集强调对象间的不可分辨性；模糊集研究的是不同对象间的隶属关系，粗糙集 研究的是不同类中的对象组成的集合关系：模糊集的隶属函数大多是由专家 凭经验给出，带有很强的主观性，而粗糙集的粗糙隶属函数的计算是从被分 析的数据中直接获得的，非常客观目前所见的模糊粗糙集模型 5 , 6 , 1 4 】和粗糙 模糊集模型是二者结合的成功范例 粮糙集理论与d s 证据理论在处理不确定性的问题方面其产生和研究 方法是不同的，但却有某种相容性粗糙集理论中的下近似和上近似的概率 恰好分别是d s 证据理论中的信任函数和似然函数 2 6 , 3 8 1 ，然而生成信任函数 和似然函数的基本概率分配函数，( 即m a s s 函数) 方法是不同的，前者来自于 系统中数掘本身，比较客观，而后者往往来自于专家的经验，带有很强的主观 性，粗糙集理论与d s 证据理论有很强的互补性 1 1 4 算法研究 粗糙集理论中有效算法研究是粗糙集在人工智能方向上研究的一个主要 方向粗糙集理论在人工智能的应用上主要有两大类：一类是无决策的分析， 内容主要包括数据压缩、约简、聚类与机器发现等；另一类是有决策分析，内 西南交通大学硕士研究生学位论文第3 页 容主要包括决策分析、规则提取等，也涉及对原始数据的预处理，如数据压缩 与约简等目前，粗糙集理论中有效算法研究主要集中在导出规则的增量式 算法，约简的启发式算法，粗糙集基本并行算法1 3 ”，以及与粗糙集有关的神 经删络与遗传算法等【8 】这些研究的成功应用有的已经获得了商业价值 1 1 5 粗糙集与其他数学理论的联系 随着对粗糙集理论研究的不断深入，它与其他数学分支的联系也更加紧 密例如，从算子的观点看粗糙集理论，它于拓扑空间、数理逻辑、模态逻辑、 格与布尔代数、算子代数等联系较为紧密；从构造性和集合的观点来看，它与 概率论、模糊数学、证据理论、图论、信息论等联系较为密切粗糙集理论研 究不但需要以这些理论作为基础，同时也相应地带动这些理论的发展 目前，数学理论与粗糙集理论结合起来进行研究已有文章出现，如“粗糙 逻辑”【1 1 , 1 3 “粗糙理想”、“粗糙半群”【lo j 等等随着粗糙结构与代数结构，拓 扑结构，序结构等各种结构的不断整合，必将不断涌现出新的富有生机的数 学分支 作为人工智能和认知科学中新的研究热点，粗糙集理论的有效性已被计一 算机学科的基础研究人员所认可目前，粗糙集理论已经在机器学习、知识歌 取、决策分析、数据库中知识发现【1 9 ，3 1 、专家系统、决策支持系统 1 2 , 1 8 , 2 1 、归 纳推理、模式识别、智能控制等领域得到了广泛应用 到目前为止，关于粗糙集理论与应用方面的文章很多，有关书籍也正在 陆续出版一些粗糙集理论与应用综述方面的文章详细介绍了粗糙集理论在 各个阶段理论研究与应用研究方面的成果 1 2 本文的写作动机 如前所述，p a w l a k 粗糙集模型中论域上的等价关系起着至关重要的作用 然而相应的理论不适合处理不完备信息系统对于不完备信息系统，一些研 究者通常采用直接忽略空缺属性值或采用统计学原理对遗漏属性值进行估计 补充，把不完备信息系统转化为完备信息系统来处理如c h m i e l e w s k i 在 1 9 9 3 年提出把不完备信息系统中存在缺省值的对象直接删除的方法来解决这 个问题；f z u n g p e ih o n g 等提出在属性约简和提取规则的同时估计对象的缺省 属性值的方法等另外一些研究者直接从刻画不完备信息系统对象间的不可 区分关系的角度出发，提出了几种扩充关系，如k r y s z k i e w i c z 提出用相容关系 来拙述不完备信息系统中对象之间的关系，然后在这个关系的基础上提出了 属性约简和规则提取的方法，后来研究者对k r y s z k i e w i c z 方法中的相容关系 作了一些修改，如s t e f a n o w s k i 等提出了相似关系，王国胤提出了限制容差关 系文中在分析现有的几种关系的基础上提出了一种新的关系改进限制 容差关系，并通过比较分析了它的特点， 西南交通大学硕士研究生学位论文第4 页 粗糙集理论中有效算法研究是粗糙集在人工智能方向上研究的一个主要 方向，其中有关属性约简的启发式算法多数是以完备信息系统为研究对象，一以 p a w l a k 粗糙集为理论基础的如苗夺谦等从信息角度对决策中属性的重要性 给出度量，提出了一种基于互信息的知识相对约简启发式算法，该算法的复杂 度是多项式的，并通过实例说明该算法能得到决策表的最小约简，但并不能保 证算法的完备性：王国胤等对粗糙集理论的信息论观点进行了分析，对知识约 简在信息论观点和代数观点进行了研究，用条件熵为启发知识设计了决策表 的启发式知识约简算法，通过仿真实验验证了该算法的有效性和约简效果：梁 吉业等将信息量的概念引入信息系统，提出了一个基于信息量的属性约简算 法，但该算法没有考虑决策表的情形：j w g u a n 等在等价关系基础上定义了等 价矩阵，从而将等价关系与等偷矩阵对等起来，通过矩阵的计算来刻画粗计算 这种方法是直观而有效的，但该方法也未考虑决策表的情形张文修等针对不 一致决策表，提出了最大分布约简的概念，讨论了分布约简、分配约简、最大 分布约简和近似约简之间的关系，并给出了求这些约简的分明矩阵方法文中 基于改进限制容差关系，通过定义不完备信息系统属性的信息量，以属性相x t 蘑要性为启发知识，设计不完备决策表的分配约简的算法，并通过实例分析 蜕明此算法能有效地找到不完备信息系统的分配约简 1 3 本文具体研究工作简介 1 本文通过分析现有的几种针对不完备信息系统而建立的扩充关系，借助集 对分析中联系度的概念，对王国胤提出的限制容差关系模型的特点和缺驺 进行了深入地分析提出了一种新的扩充关系改进限制容差关系该 关系的特点是：1 ) 将不完备信息系统划分为两部分，舍弃部分信息以便于 统一处理；2 ) 加入闽值相当于加入人的主观要求；3 ) 效果更加直观，也 更符合人的主观要求 2 在提出的改进限制容差关系的基础上，对上、下近似算子的代数性质进行 了讨论，并把p a w l a k 粗糙集理论中的一些重要概念引入不完备信息系统 中，对不完备信息系统进行了更深入地探讨 3 基于改进限制容差关系，把正域约简、信息熵约简以及张文修等针对不一 致决策表提出的分布约简、分配约简、最大分布约简和近似约简引入不完 备信息系统，并讨论它们之间的关系；给出了分配约简的一种启发式算法： 条件信息量约简算法，分析了该算法的时间复杂度经实验检验，该算法 是有效的 西南交通大学硕士研究生学位论文第5 页 1 4 预备知识 1 4 1 知识与知识厍 设u g 是有限论域，任何子集x u ，称为u 中的一个概念或范畴 u 中的任何概念族称为关于u 的抽象知识，简称知识p a w l a k 粗糙集模型中 讨论的知识都是对u 形成划分的概念族【3 5 1 一个划分j 定义为j d = l ，五鼍 ，其中五星u ，置o ，置n j ，= o ，对于f ，i ，j = 1 ，2 ，”； u 片= u ，5 i u 上的一族划分称为u 的一个知识库( k n o w l e d g eb a s e ) 设r 是u 上的一个等价关系族，表示r 的所有等价关系类( 或者u 上的分类) 构成的集合若p r ，且p o ，则n p ( p 中所有等价关系的交 集) 也是一个等价关系，称为p 上的不可区分( i n d i s c e m i b i l i t y ) 关系，记为 i n d ( p ) 设q 也是u 上的一个等价关系，若i d ( p ) 量i n d ( q ) ，则称p 比q 细， 或q 比p 糖，记为尸 q 1 4 2p a w la k 粗糙集模型上下近似的定义 定义1 4 1 i ”1 给定知识库k = ( u ，r ) ，r 是一个等价关系的集合，对于 v x 量u ，定义两个子集， 型= u y 陡x = x 6 u l x 】。x 厨= u y e l y n x a h x u 帆n 。 分别称它们为的r 下近似和r 上近似集对于p a w l a k 粗糙集模型的上、下 近似算子的相关性质可以参考文献 1 5 】 1 4 3 一般二元关系下的粗糙集模型上下近似的定义 定义1 4 2 设u 是有限非空论域，足三u x u 为u 上一个任意的二元关 系，称a = ( u ，r ) 为广义近似空间对于任意x u ，工关于近似空间4 ：f u ，r 1 西南交通大学硕士研究生学位论文 第6 页 的下近似印r x 和上近似面r 。x 分别定义为 型。工= x e u i r s ( x ) z ) ， 面。= x e v l r s ( x ) n x ) 其中，r 。( x ) = y u l x r y ) 1 4 4 约简的概念 殴k = f 抄，r 1 是一知识库，p r ，称p p 为p 中不必要的，若 i n d ( p ) = i n d ( p 一 p ) ；否则称p 为p 中必要的若任一p p 是p 中必要的， 则称p 为独立的，否则称p 是依赖的【3 3 】 定义1 4 3 【圳设p 和q 是u 中两个等价关系的集合，如果q p ，q 是独 立的，且i n d ( p ) = 扔d ( q ) ，则称q 是p 的约简 1 4 5 知识的表达系统( 信息系统) 与决策表 称四元组s = ( u ，a ，v ，f ) 是一个信息系统【3 9 1 ，或数据库系统，其中： ，：对象的非空有限集合，其中元素称为对象； a ：属性的非空有限集合，其中元素称为属性； v = u 圪，是属性n 的值域； ，：u x a 呻矿称为信息函数 决策表是一类特殊的信息系统，s = ( u ，c u d ，v ，厂) ，其中c 为条件属性 集合，d 为决策属性在本文中完备或不完备的信息系统均是指决策表的情况 用粗糙集理论来处理信息系统时，p a w l a k 粗糙集模型中论域上的等价关 系起着至关重要的作用，因此它只适用于完备信息系统，对不完备信息系统 的处理所用理论基础为一般二元关系下的粗糙集理论 西南交通大学硕士研究生学位论文 第7 页 第2 章改进限制容差关系 在p a w l a k 粗糙集模型中：论域上的等价关系起着至关重要的作用基于 等价关系，p a w l a k 定义了论域上的上、下近似算予，用于刻划不确定洼概念， 从理论上为完备信息系统的约简、决策表规则的提取等提供了一套较为完善 的方法 ， 然而，等价关系不适合用于描述不完备信息系统的对象为了刻划论域 中对象问的不可区分关系，人们将等价关系的条件放宽，从不同角度出发，提 出了容差关系、相似关系、量化容差关系、限制容差关系等 本章主要在分析几种已有的扩充关系的特点的基础上提出了一种新肋扩 充关系改进限制容差关系，并通过理论证明和实例分析说明了其优越性 2 1 几种已有的不可区分关系 2 1 1 容差关系 给定信息系统s = ( u ，a ，v ，f ) ，a = c u d ，c n d 彩，其中c 为条件属 性集合，d 为决策属性集对于有遗漏属性值的属性子集b 量a ，记空值为 “”，k r y s c k i e w c z 定义了如下容差关系： 定义2 1 1 1 9 容差关系疋的定义如下： = ( x ，y ) 卜u y e u v 。( 巳+ e b ；( 巳( z ) = 巳( y ) v 。( x ) = + v 。( y ) = + ) ) 显然，死是自反且对称的，但不一定是传递的进一步，用符号瓦( x ) 表 示满足关系( 墨y ) 的个体对象y 的集合，称为对象x 的容差类 根据定义2 1 1 得到上、下近似的定义： 西南交通大学硕士研究生学位论文第8 页 定义2 1 2 9 1 不完备信息系统s = ( u ，爿，v ，f ) 中对象集合x 关于属性集 b g 爿的下近似x ；和上近似肆分别是： 霹= x 卜u 且( x ) x ) 肆= x 卜u 且咒( x ) n x a 从上述定义不难看出，容差关系认为空值和任意值都是相等的，这很容 易将实际上不同属性值的个体对象误判为同一类，即容差关系的要求过于宽 松 2 1 2 非对称相似关系 s t e f a n o w k i 等人认为空值不是不确定的，而是当前不存在的，从而不允许 比较空值基于此观点，只要两个对象的已知属性值相同，就可以认为它们相 似同样记未知值为”，：给出非对称相似关系如下： 定义2 1 3 非对称相似关系品的定义为： 瓯= ( x ，y ) 卜u y e u ，、v c j ( c j b j ( 。( x ) = - v ：，( y ) ) ) 显然，非对称相似关系自反且传递，但不对称直观上，非对称相似关系 可以认为是包含关系的一个代表，只要x 的描述包含于y 的描述就认为x 与y 相似 、 为定义基于相似关系的上、下近似，s t e f a n o w 西给出了非对称相似于。的 对象集r 。( x ) ，x 与之非对称相似的对象巧1 ( x ) 如下： 定义2 1 4 犯2 1 r b ( x ) = 驯y u ，s ( y ，x ) 1 ( x ) = y 睢u ，s ( ) 一般地，r 。( x ) ( x ) 对象集合x 的上、下近似可以进一步定义如下： 西南交通大学硕士研究生学位论文第9 页 定义2 1 5 2 2 1 不完备信息系统s = ( u ，a ，v ，f ) 的对象集合x 关于属性集 合b a 的下近似；和上近似彳? 分别定义为： ；= x u 旧( x ) 至x 霹= ur b ( x ) 比较容差关系和非对称相似关系，s t e f a n o w k i 得到如下结论： 定理2 1 1 圳给定信，g 着a n s = ( u ，a ，矿，f ) 及x c _ u ，在非对称相似关系 r 。2 _ t ，x 的上近似和下近似是对容差关系下x 的上近似和下近似的改进， 即j ：x ：，群z ； 从上文不难看出，根据非对称相似关系得到的近似集合比在容差关系下 得到的近似集合含有更多的信息，但这种方法没有采用容差关系安全，因为 一些对象在知之甚少的情况下被肯定地划分到某类中 2 1 3 量化容差关系 对于不完备信息系统中的个体，也可以根据已知信息的相同程度来刻画 它们之间的相近似程度据此，s t e f a n o w k i 等人提出了基于量化容差关系田1 的 扩充粗糙集模型 不同的量化容差( 近似) 关系可以用不同的比较规则来定义，给定一个 量化容差关系，对于个体对象全集u 的每一个元素，s t e f a n o w k i 定义了容差 类的概念，有关量化容差关系的具体概念、对象集合x 的上、下近似的定义， 请参考文献 3 2 】 如果容差度的取值为1 ，就可以得到容差类的概念 量化容差关系中，需要预先知道信息系统中属性值的概率情况，这对于 1 个不完备信息系统来说是困难的在甚至连系统的整体情况都还不清楚 的时候，根本不可能精确地知道其分布概率 堕堕奎塑查兰堡圭堡壅竺堂堡笙塞 篁! ! 里 2 1 4 限制容差关系 针对以上关系的缺陷，王国胤, m i n t 限制容差关系三如下： 定义2 1 6 给定不完备信息系统s = ( u ，_ ，矿，厂) 及u 上定义的二元关 系l ( 限制容差关系) b a ，令 b ( x ) = 6 1 6 三b 6 ( x ) + j 则 。 一( ) 。 1 q 。“l ( 乩。一o ( z ) = 6 ( 力= + ) ) v ( ( b ( 刁n 弓( ，) t 。) n 觇。( p ( z ) ；- ) n p ( y ) t ) 一p ( ；) ；6 ) ) ) ) j 显然，限制容差关系三具有自反性、对称性，但不具有传递性进一易 用符号三一卜) 表示在属性集合b 上满足关系上( 工，y ) 的个体对象y 的集合，即 对象x 的限制容差类y k ( x ) 直观看，有两种情形：1 ) x ，y 在占上全为 空值；2 ) x ，y 在曰上存在同不为空值的属性，且取值相同 限制容差关系排除了容差关系中取值不全为空的两对象无相同取值的情 形，如x = ( + ，1 ，o ，+ ) ，y = ( o ，t ，1 ) ，有y ( x ) 而y 诺毛( x ) 同时去掉了非对称 形似关系中y & ( x ) 蕴涵y 不能比x 更不完备的要求从而放宽了相似关系 而严格了容差关系 限制容差关系的上、下近似的定义如下： 定义2 , 1 7 口2 1 不完备信息系统s 。( u ，a ，v ，厂) 中对象集合关于属性集 b a 的下近似x ；和上近似硭分别为： 碟2 h x e u a l e ( z ) 砷群= h x g a g ( z ) o 比较限制容差关系与容差关系、相似关系，可得到如下两定理： 西南交通大学硕士研究生学位论文 第1 1 页 定理2 1 2 给定信息系统s = ( u ，爿，v ，f ) 和集合b a ，x ，则 x ；量x ：，x | x ； 定理2 1 3 3 2 1 给定信息系统s = ( u ，a ，v ，f ) 和集合b a ，z u ，若 v x u ，昂( x ) g ，则 x i 兰x ：至x ；x ：x ：x ； 。 定理2 1 3 说明，当信息系统不含有属性值全为空的对象时，# 艮制容差关 系介于容差类和相似类两情形之间定理2 1 2 和定理2 1 ，3 的具体证明参阅文 献 3 2 2 2 改进限制容差关系 虽然从理论上讲限制容差关系优于容差关系和非对称相似关系，但是， 它还存在缺陷 缺陷一：对完全没有相同属性值对象的情况处理得不够理想这种情况可 以详细表示为：两个对象满足兄( x ) n 名( y ) = 国这个条件，即两个对象没有 共同存在的相等属性值我们可将这种情况再细分为两种情况：两个对象的属 性值完全不知；存在已知的属性值限制容差关系认为前一种情况两对象不可 分辨，而后一种情况可以分辨，即 v be b ( 6 ( x ) = 6 ( y ) 三+ ) l b ( x ，) b ( x ) n 最( y ) = o 、 6 b ( 6 ( x ) + v 6 p ) + ) j 一厶( x ，y ) 这两种情况下对象x 和y 没有任何一个相同的已知属性值，限制容差关系却认 为这两种情况的可分辨性不同直观上来讲，限制容差关系认为两个完全未知 西南交通大学硕士研究生学位论文第1 2 页 属性值的对象相同，而没有共同已知属性值的对象不同，这显然不符合情理， 既然没任何一个相同的已知属性值，可以认为这两个对象能够分辨， 缺陷二：对于定义的第二种情况，即 ( b ( x ) n 最( z ) a ) v 。( ( 6 ( x ) + ) ，、( 6 ( y ) ，) 专( 6 ( 工) = 6 ( y ) ) ) 处理得也不够理想限制容差定义认为两对象只要有一个属性值相同，而在其 它属性上取值无法比较时仍视为同类在属性较多的情况下，这个条件过于宽 松因此，针对第二种情况，我们引入一个阈值，将己知属性值个数所占 比例小于此闽值的对象( 空值过多) 单独划出来，剩余对象构成新的论域， 再取闽值口，两对象在容差关系下( 或限制容差关系下) 相同属性值比重大 于口，且无已知不相同属性值的认为属同一类，为此，我们首先介绍集对( s e t p a i r ) 关联度的概念 定义2 2 1 刚给定两个集合爿和b ，并设这两个集合组成集对它们共有 个属性，其中，集a 和b 在s 个属性上取值相同；在p 个属性上取值不同； 在f 个属性上取值不明确，则称比值为集对。帮b 的同一度；为一和 b 的差异度：为a 矛i i b 的对立度，并用卢( 正口) = + f + _ ，表示爿 和b 的关系，简记为： ( “，b ) = 盯+ b i + c j 显然：0 以，b ，c 1 ，a + b + c = 1 ，称为a 与日的关联度 下面我们借助关联度的概念讨论不完备信息系统中对象间的关系 对不完备信息系统s = ( u ，c u d ，v ，) ，b c 设l b l = ”，v x u ，令 m ( x ) = 1 d 1 日b a a ( x ) i ，取o o 排除了限制容差关系中的第一种情况：限制容差关系 的第二种情况相当于联系度o 形时，有聍( x ) k ( x ) 因此，在一般情况下( 信息系统中不含全为 空值的对象) ，限制容差关系是改进限制容差关系的特殊情形所以定义2 2 2 可以作为改进限制容差关系的毒义( 注：我们认为若m ( x ) = m ( _ y ) = o ，则同 度日= 0 ) 西南交通大学硕士研究生学位论文第1 4 页 相应地，我们定义基于改进限制容差关系的上、f 近似算于： 定义2 2 3 对满足上述关系的信息系统s = ( u , b u d ，v ，f ) ，x u ， 碟、j 学分别表示改进限制容差关系的上、。下近似，定义如下： 鹾= 川xe u 巧2 ( x ) n x a )睇2 = h 工u l 蛩( x ) x 定理2 2 1 一般情况下( 论域中不含属性值全为空的对隽，当b = c ，即b 为条件属性集时，限制容差关系与改进限制容差关系等价，即 x ：= x i x 誊= x ； 也可以写作 e ：= 并?露= 肆其中o a ：q - 形( i b i = 唧) 证明因b = c ，所以对任意x u ，一定存在6 b 1 吏 ! 导- b ( x 1 + ，不会有 任意6 b ，b ( x ) = b ( y ) = + ，排除了限制容差关系中的第一种情况，均为 ( 昂( x ) n 晶( x ) 妒) v 。( ( 6 ( x ) ) ( 6 ( y ) + ) _ ( 6 ( x ) t 6 ( y ) ) ) 又由以上分析知限制容差关系中的第二种情况相当于 0 口：- ( i b i = n ) 的改进限制容差关系，所以结论成立 口 定理2 2 2 若存在x u ，对于任意6s b ，有6 ( x ) = + ，则礞( x ) = x 证明因为对于任意6 b ，有6 ( x ) = + ，故任意y u ，b ( x ) n 弓( y ) = o 因此找彳i 到一个与x 具有改进限制容差关系的对象 口 事实上，定理2 2 1 和定理2 2 2 分别对应于o ，k 的两种极端的情 况定理2 2 1 保证了每一个对象都存在至少一个已知属性值，在这种情况下， 两种关系模型取得了一致；定理2 2 2 的条件决定了若两个对象没有任何一个 相例属性值，限制容差关系下的容差类中的对象可能会有多个，而改进限制 西南交通大学硕士研究生学位论文 第1 5 页 容差类关系下的容差类中只有对象本身从这两种极端情况可以看出，当 0 _ a 2 玉z 时，已知的属性值越多，改进限制容差关系就越接近限制容差关 系 定理2 , 2 3 对不完备信息系统s = ( u ，a ，v ，f ) ，x 量u ，当 o 口：形( 吲= n ) ，有 x 。s x ： 证明 1 ) 当q = 口：= 0 时霹= x j 砖x o = x 互砖 2 ) 当o 时，碍2 ( y ) k ( y ) ，故臂( y ) 爿，从而y 野，所以 x 2 三x ；：另一方面，任取y x 。s ，则譬2 ( y ) n x a ，又当? z 时， 五一( y ) n x a ，从而y 硭，所以磋硭 口 山定理2 2 3 和定理2 2 4 知：改进限制容差关系是对限制容差关系的改 讲 西南交通大学硕士研究生学位论文第1 6 页 2 3 性能分析 下面用- + 实n n n 完备信息系统来分析比较这些扩充关系模型之间的 性能我们仍采用文献【3 2 中用于分析容差关系、相似关系、限制容差关系性 质的不完备信息系统( 如表1 ) 裂1一个不完备信息表 | a 以 嘎岛 矾 吩魄 品 喁 岛q oq 1 q 2 c l 32223313 ( ? 、