（应用数学专业论文）基于广义模糊划分的模糊粗糙集理论.pdf

华北电力大学硕士或工程硕士学位论文 摘要 本文定义基于模糊丁相似关系的模糊相似类及仃，模糊相似类的两种模糊粒子， 研究了模糊相似类及盯：模糊相似类的性质定义了广义模糊划分和仃，模糊划分， 分别用构造性方法和公理化方法研究了广义模糊划分和盯，模糊划分与模糊r 关系 之间的公理性质构造了基于广义模糊划分和盯，模糊划分的模糊粗糙集模型，证明 了基于广义模糊划分和吒模糊划分的模糊粗糙集模型与利用模糊丁相似关系定义 的模糊粗糙集模型之间的特殊联系最后研究了基于广义模糊划分的模糊粗糙集的 相对约简和相对核 关键词：模糊丁相似关系；模糊相似类； 集；相对约简；相对核 广义模糊划分；吼模糊划分；模糊粗糙 a b s t r a c t t h i sp a p e rd e f i n e st h ec o n c e p t so ff u z z yg r a n u l a r sa n d 吼f u z z yg r a n u l a r sb a s e do n f u z z yt s i m i l a rr e l a t i o n s ，a n dd e v e l o p st h e i rb a s i cp r o p e r t i e s ；w ed i s c u s st h e r e l a t i o n s h i p sb e t w e e nt h ep r o p e r t i e s o ft h e f u z z yg r a n u l a r s a n d f u z z yt s i m i l a r r e l a t i o n s ，t h a to f 吒f u z z yg r a n u l a r sf u z z ya n dt s i m i l a rr e l a t i o n s l a t e ro n ，g e n e r a l i z e d f u z z yp a r t i t i o n sa n d 仃f u z z yp a r t i t i o n sa d gg i v e n ，a n df u z z yr o u g hs e t sd e s c r i b e db yt h ef u z z yg r a n u l a r s a n d 吒f u z z yg r a n u l a r sa 把f r r s t l yc o n s t r u c t e d ，w h i c ha lep r o v e dt h a tt h ef u z z yr o u g hs e t s b a s e do nt h eo ng e n e r a l i z e df u z z yp a r t i t i o n sa n d 吒f u z z yp a r t i t i o n sr e l a t e dt ot h eo n e st h a t p r o p o s e db ym e m b e r s h i pf u n c t i o n sc l o s e l y f i n a l l y , t h ec o n c e p t so fr e l a t i v er e d u c t i o n a n dr e l a t i v ek e r n e la lep r o p o s e d a ne x a m p l ei se m p l o y e dt oi l l u s t r a t et h ea p p l i c a t i o no f t h er e l a t i v er e d u c t i o na n dr e l a t i v ek e r n e lo ft h ef u z z yr o u g hs e t s l i u j i a n q i ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f c h e nd e g a n g k e yw o r d s ：f u z z yt - s i m i l a rr e l a t i o n ，f u z z y g r a n u l a r , o lf u z z yg r a n u l a r ，g e n e r a l i z e d f u z z yp a r t i t i o n ，f u z z yr o u g hs e t s ，r e l a t i v er e d u c t i o n ，r e l a t i v ec o r e 华北电力大学硕士或工程硕士学位论文 摘要 本文定义基于模糊丁相似关系的模糊相似类及仃，模糊相似类的两种模糊粒子， 研究了模糊相似类及盯：，模糊相似类的性质定义了广义模糊划分和仃，模糊划分， 分别用构造性方法和公理化方法研究了广义模糊划分和盯，模糊划分与模糊r 关系 之间的公理性质构造了基于广义模糊划分和盯，模糊划分的模糊粗糙集模型，证明 了基于广义模糊划分和盯。模糊划分的模糊粗糙集模型与利用模糊丁相似关系定义 的模糊粗糙集模型之间的特殊联系最后研究了基于广义模糊划分的模糊粗糙集的 相对约简和相对核 关键词：模糊丁相似关系；模糊相似类； 集；相对约简；相对核 广义模糊划分；吼模糊划分； 模糊粗糙 a b s t r a c t t h i sp a p e rd e f i n e st h ec o n c e p t so ff u z z yg r a n u l a r sa n d 吒f u z z yg r a n u l a r sb a s e do n f u z z y t s i m i l a rr e l a t i o n s ，a n d d e v e l o p s t h e i rb a s i c p r o p e r t i e s ；w e d i s c u s st h e r e l a t i o n s h i p sb e t w e e nt h ep r o p e r t i e so ft h ef u z z yg r a n u l a r s a n d f u z z yt s i m i l a r r e l a t i o n s ，t h a to fo - lf u z z yg r a n u l a r sf u z z ya n dt s i m i l a rr e l a t i o n s l a t e ro n ，g e n e r a l i z e d f u z z yp a r t i t i o n sa n d 莎f u z z yp a r t i t i o n sa r eg i v e n ，a n df u z z yr o u g hs e t sd e s c r i b e db yt h ef u z z yg r a n u l a r s a n d 吒f u z z yg r a n u l a r sa r ef n - s f l yc o n s t r u c t e d ，w h i c ha r ep r o v e dt h a tt h ef u z z yr o u g hs e t s b a s e do nt h eo ng e n e r a l i z e df u z z yp a r t i t i o n sa n d 吒f u z z yp a r t i t i o n sr e l a t e dt ot h eo n e st h a t p r o p o s e db ym e m b e r s h i pf u n c t i o n sc l o s e l y f i n a l l y , t h ec o n c e p t so fr e l a t i v er e d u c t i o n a n dr e l a t i v ek e r n e la r ep r o p o s e d a ne x a m p l ei se m p l o y e dt oi l l u s t r a t et h ea p p l i c a t i o no f t h er e l a t i v er e d u c t i o na n dr e l a t i v ek e r n e lo ft h ef u z z yr o u g hs e t s l i uj i a n q i ( a p p l i e dm a t h e m a t i c s ) d i r e c t e db yp r o f c h e nd e g a n g k e yw o r d s ：f u z z yt - s i m i l a rr e l a t i o n ，f u z z yg r a n u l a r , o lf u z z yg r a n u l a r ，g e n e r a l i z e d f u z z yp a r t i t i o n ， f u z z yr o u g hs e t s ，r e l a t i v er e d u c t i o n ，r e l a t i v ec o r e 声明尸明 本人郑重声明：此处所提交的硕士学位论文基于广义模糊划分的模糊粗糙集理 论，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得 的研究成果据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或 证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意 学位论文作者签名：日期：型 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期： 导师签名： 日 期： 华北电力大学硕士或工程硕士学位论文 1 1 粗糙集理论研究概况 第一章绪论 粗糙集理论是2 0 世纪8 0 年代初由波兰数学家z p a w l a k 1 首先提出的一种处 理不完备信息和不确定信息的新型数学工具其基本思想是在保持分类能力不变的 前提下，通过知识约简，导出了基于概念的分类规则该理论是一种刻画不完备信 息和不确定信息的数学工具，能有效地分析具有不精确、不一致等各种不完备的信 息通过对数据进行分析和推理，从中发掘隐含的知识，揭示潜在的规律由于最 初关于粗糙集理论的研究文献大部分是用波兰语发表的，因此当时没有弓 起国际学 术界的重视，研究地域仅局限在东欧一些国家，直到2 0 世纪8 0 年代末才逐渐引起 世界各国学者的注意近几年来，由于它在机器学习、数据挖掘、知识发现、决策支 持与分析等方面的广泛应用，因此越来越多的学者加入到研究粗糙集行列中尤其 是1 9 9 2 年第一届关于粗糙集理论的国际学术会议在波兰召开，标志着粗糙集理论 成为计算机科学研究领域的一个重要研究方向，1 9 9 5 年a c m c 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 粗糙集) 的基本理论是建立在等价关系( 又称不可区分关系) 基础之上的它将分类理解为特定空间上的等价关系对特定空间的划分，将知识理 解为对数据的划分，每一个划分集合称为基本概念( 或范畴、知识) 粗糙集就是 用基本概念的集合来近似表示一个不精确的概念，其主要思想是将不精确或不确定 的概念( 知识) 用己知知识库中的知识来近似地刻画该理论与其它处理不精确信 息的理论最显著的区别是它无须提供所需处理问题的数据集合以外的任何先验信 息，所以对问题的不确定性的描述或处理可以说是比较客观的，由于这个理论未能 包含处理不精确或不确定性原始数据的机制，所以这个理论与概率论，模糊数学等 有很强的互补性 为了使粗糙集理论有更大的应用空间，研究者们提出了很多推广的粗糙集模 型研究粗糙集理论的方法主要有两种：( 1 ) 构造性方法；( 2 ) 公理化方法 ( 1 ) 构造性方法是从给定的近似空间出发去研究集合的近似，它是以论域上的二 元关系或布尔代数作为数学基础，然后导出粗糙代数系统这种方法的优点是研究 的问题往往源于实际，所建立的模型有很强的应用价值，不足之处是不易深刻了解 近似算子的代数结构 华北电力大学硕士或工程硕士学位论文 在p a w l a k 粗糙集模型中有三个最基本的要素：1 ) 论域u ；2 ) 论域上的等价关系 尺；3 ) 被近似描述的集合彳因此对p a w l a k 粗糙集模型主要有三个方向，即从论域 方向的推广、从关系方向的推广和从被描述集合方向的推广 从论域方向推广的粗糙集模型主要有一种，即把p a w l a k 粗糙集模型的单论域推 广到双论域 2 7 ，这时二元关系变为两个论域的笛卡儿乘积的子集 从关系方向推广的p a w l a k 粗糙集模型有以下几种方式：一是将论域上的二元等 价关系推广为任意的二元关系从而得到了一般关系下的粗糙集模型 2 8 】；二是将对 象x 所在的等价类看成是x 的一个领域，从而导出了基于领域算子的粗糙集模型 f 2 9 ；另一种方式是将等价关系导出的划分推广成为一般的布尔代数，以此出发定 义粗糙集模型和近似算子 3 0 】，更一般的方式是将等价关系推广成模糊关系或模糊 划分而得到的模糊粗糙集模型【3 1 】 对集合和近似空间进行推广：这一方式是与其它不确定性理论( 如概率论、模 糊数学、信息论、证据理论等) 结合起来进行研究的当知识库中的知识由于随机 原因或经统计得到，即知识库中的知识很可能是不确定的时，人们就提出了概率粗 糙集模型，变精度粗糙集模型实质上也可以归入概率粗糙集模型 。 当知识库中的知识模块都是清晰的概念，而被描述的概念是一个模糊概念时， 定义了粗糙模糊集【7 ，3 2 来解决此类问题的近似和推理；当知识库中的知识模块也是 模糊知识时，就相应地提出了模糊粗糙集模型 7 ，1 2 ，1 9 1 ( 2 ) 公理化方法也称为代数方法或算子方法，这种方法不是以二元关系为基础， 它是以满足某些公理的一对一元集合算子为基础的此方法是将注意力放在粗糙集 理论中所产生的代数系统上来进行研究，利用一个公理集来刻画上、下近似算子， 研究公理集与代数系统之间联系有关这方面的内容在文献 6 ，1 2 ，3 3 ，3 4 中有充分 的论证公理化方法的优点是能够深刻了解近似算子的代数结构，其缺点是应用性 不强 粗糙集理论是通过上近似集合和下近似集合把隐藏在信息系统中的知识揭示 出来，并表达成决策规则形式该理论的另一重要应用就是数据库中的属性约简对 于给定的由离散属性值刻画的数据，我们可以找出一个具有相同信息量的属性子集 来刻画该数据众所周知，知识库中的属性并不是同等重要的，甚至其中某些属性 是冗余的，属性约简就是在保持知识库分类能力不变的前提条件下，删除其中不相 关或不重要的属性属性约简可以看作是粗糙集理论与其它不确定性理论最有区别 的特征的概念之一在现实生活数据中，属性值即可能是符号型的又可能是实值型 的，而经典粗糙集理论很难处理这种类型的数据要想通过经典粗糙集理论得到分 类知识，一般要求数据的属性值是离散型的，遇到数据的属性值是连续的情况，首 先对数据进行预处理即用离散化方法将数据的属性值分成有限的几类，但这种离散 化方法会带来较大的误差，造成大量信息丢失这就需要把模糊集和粗糙集结合起 2 华北电力大学硕士或工程硕士学位论文 来，因此形成了一种新的理论即模糊粗糙集理论【7 】 模糊集理论和粗糙集理论都是对经典集合理论的推广，二者既相互区别又相互 联系，而且还相互补充模糊集和粗糙集都可以用来描述知识的不确定性和不完全 性，然而它们的描述的侧重点不同从知识的粒度方面来看，模糊集主要着眼于知 识的模糊性，而粗糙集主要着眼于知识的粗糙性；从知识的描述方法上来看，模糊 集是通过对象关于集合的隶属程度来近似的描述，而粗糙集是通过一个集合关于某 个已知的可利用的信息库的一对上、下近似来描述；从集合的对象之间的关系来看， 模糊集强调是集合边界的病态定义，即边界的不分明性，而粗糙集强调的是集合对 象之间的不可分辨性；从研究的对象来看，模糊集研究的是属于同一类的不同对象 的隶属关系，重在隶属程度，而粗糙集研究的是不同类中的对象组成集合之间的关 系，重在分类当然模糊集与粗糙集之间的联系还是非常紧密的粗糙集理论中用 粗糙隶属函数来刻画知识的模糊性，粗糙集理论中的粗糙隶属函数可以看成特殊的 模糊隶属函数这样论域中的任何一个经典集都对应于一个模糊集合，此集合的下 近似和上近似分别对应于这个模糊集合的核和支集由于模糊集合理论与粗糙集理 论都可以描述知识的不确定性，且各自的特点不同，因此模糊集理论和粗糙集理论 有很强地互补性，将这两个理论进行某些整合后，去处理知识的不确定性和不完备 性，比它们各自去处理不确定性和不完备性显示出更强大的功能，从而能更好的解 决实际问题 1 2 论文的研究背景 经典粗糙集理论是以等价关系为基础的建立的，但等价关系是一种很特殊的二 元关系，它在处理实值型数据显得无能为力，所以说将粗糙集理论推广到一般二元 关系下进行研究成为一个热门的课题许多学者将经典粗糙集理论进行了改进和推 广，其中一个重要研究方法是将经典粗糙集模型推广到模糊环境下来研究在模糊 环境下研究粗糙集大致分为三类：一类是将模糊属性数据转化为分明属性数据，直 接用经典粗糙集理论进行数据处理，提取规则，或进行属性约简；另一类是从知识 描述的角度出发，将描述粗糙集的一对上、下近似集合算子推广到模糊环境下，提 出了粗糙模糊集或模糊粗糙集 7 ：第三类方法是将粗糙集的基础等价关系推广为 模糊等价关系或模糊丁相似关系，利用这些关系对论域进行一个模糊划分或模糊丁 划分，在此推广的基础上，提出了各种模糊粗糙集模型目前存在的模糊粗糙集模 型主要是利用关系来定义的，没有利用模糊粒结构构造的模糊粗糙集模型，因而无法清 楚地研究模糊粗糙集的粒结构本文对模糊粗糙集的粒结构进行深入的探讨和研究，提 出了用模糊粒子构造模糊粗糙集的想法，定义了广义模糊划分( 广义模糊划分又称丁模 糊划分) 和仃，模糊划分，并构造了基于广义模糊划分和吼模糊划分的模糊粗糙集模 3 华北电力大学硕士或工程硕士学位论文 型文中用构造性方法和公理化方法研究了基于模糊丁相似关系的广义模糊划分和模 糊划分，并把广义模糊划分和盯：模糊划分的元素当作基本模糊粒，用这种基本模糊粒 描述了任意模糊集合的上近似集合和下近似集合最后研究基于广义模糊划分的模糊粗 糙集的属性约简和核，并通过例子对相对约简和相对核进行了说明论文的主要贡献如 下： 1 ) 定义基于模糊丁相似关系的广义模糊划分和盯：模糊划分，研究广义模糊划分和仃，模 糊划分的性质；定义了基于模糊相似类和仃，模糊相似类的两种特殊的模糊信息粒， 研究了模糊信息粒的公理性质 2 ) 研究了满足一定公理的模糊粒集合可以构造出模糊丁相似关系 3 ) 定义了基于广义模糊划分( t 模糊划分) 和盯，模糊划分的模糊粗糙集，讨论此类模 糊粗糙集的性质 4 ) 讨论基于模糊丁相似关系上广义模糊粗糙集的属性约简，用例子分析了相对约简和 相对核的求解 1 3 论文的组织结构 本文第二章介绍了经典粗糙集的基本知识，对经典粗糙集理论中序同构的概念进行 了完善：第三章介绍了模糊集的预备知识，介绍了模糊粗糙集知识第四章构造了基于 模糊r 相似关系的广义模糊划分，用构造性方法和公理化方法研究了广义模糊划分的性 质，构造了基于广义模糊划分的模糊粗糙集模型，研究了该模糊粗糙集模型的性质第 五章构造了定义了基于模糊r 相似关系的模糊划分，用构造性方法和公理化方法研究 了q 模糊划分的性质，最后构造了基于模糊划分的模糊粗糙集模型第六章提出了 模糊粗糙集的相对约简和相对核，基于广义模糊划分的模糊粗糙集模型中的不可区分矩 阵，最后用一个实例说明了研究成果的可行性 4 华北电力大学硕士或工程硕士学位论文 2 1 知识和知识库 第二章粗糙集的基本知识 粗糙集理论认为，知识是对对象进行分类的能力，设u f 2 j 是所讨论的有限对象 集合，称为论域任何子集x 冬u 称为u 中的一个概念( 或范畴) 并规定空集也是一 个概念，u 中的任何概念族称为关于u 的抽象知识，简称知识经典粗糙集( p a w l a k ) 理论是建立在一个等价关系( 即关系具有自反性，对称性，传递性) 上的粗糙集模型， 论域u 上的一个等价关系形成论域u 的一个划分，下面讨论论域u 上的划分形成的 知识称二元组k = ，r ) 为一个知识库( k n o w l e d g eb a s e ) ，其中u 为论域，r 是u 上 的若干等价关系构成的集合 对于知识库k = ，r ) ，若p cr 且p a ，则n p 称为，上的不可区分关系 ( i n d i s c e r n i b i l i t yr e l a t i o n ) ，记为i n d ( p ) 即f n d ( p ) = n p 易证，不可区分关系满足等价 关系的定义，因此不可区分关系是一种等价关系 对于工u ， r r ，记【乩= y u ；( x ，y ) r ) 为包含工的等价类商集 u r = 缸】。；x e u ) 中元素【工】 ，x e u 称为r 初等概念u r 称为一个初等知识对于 p c _ r 有【x k ( 刀=量，称【工】耐工【厂为知识的基本概念，称商集 称为 的 p 基本知识 onoxp u f n d ( p ) u 当k = ( u ，r ) 为一个知识库，我们定义i n d ( k ) 为足所有等价关系的集合，记作 涮( 鬈户 涮( 尸上f 2 j 夕冬r ) 对于置= ，r ) 和k = ( u ，q ) 是u 上的两个知识库，当i n d ( p ) i n d ( q ) ，则称p 比q 更 精细，或者说q 比p 更粗糙当尸比q 更精细时，称p 是q 的特化，q 是p 的推广， 此时q 的每一个等价类( 基本概念) 是若干p 等价类( 基本概念) 之并，这意味着推广是 将某些基本概念组合在一起，而特化则是将某些基本概念分割成更小的单元若 i n d ( p ) = i n d ( 0 9 ，则称k 与k 是等价的 2 2p a w l a k 粗糙集模型 设u 是有限论域，r 是u 上的一个等价关系，当xsu 能表达成某些r 基本概念 的并集时，称x 是r 可定义的集合或精确集，否则称x 是r 不可定义的集合或粗糙 集 若r 是等价关系，称缈，r ) 近似空间任意u 的子集x 可用两个精确集，即 华北电力大学硕士或工程硕士学位论文 p a w l a k 粗糙集的下近似( 1 0 w e ra p p r o x i m a t i o n ) 和上近似( u p p e ra p p r o x i m a t i o n ) 来描述 1 0 x 的下近似丛和上近似r x 分别定义如下： l 丛= 娜x 】足x )m l r x = x 啪震n x a ) x 的下近似丛和上近似r x 又可以等价地写成下列两种形式 j 丛= u m 只吼柳国 i 尺x = u x 】r i 【x 】r n x a ) 集合b n ( x ) = 肘一型称为x 的尺边界域，p o s r ( x ) = 丛称为石的r 正域， n e g 足( 柳= ( ，一心称为x 的r 负域 丛或p o s 置( 工) 是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合， r x 是那些根据知识r 判断可能属于x 的u 中元素组成的集合；b n 。( x ) 是那些根据 知识r 既不能判断肯定属于x 又不能判断肯定不属于x c 的【，中元素组成的集合， 其中x c = u x 称为x 的补集；n e g r x 是那些根据知识尺判断肯定不属于x 的汐中 元素组成的集合 定理2 2 1 p 2 ( 1 ) x 是r 可定义的集合营r x = r x b n 。( x ) = a ， ( 2 ) x 是r 粗糙集营r x 一r x b n 詹( x ) o 丛是包含在x 中的最大可定义集，肘是包含于x 中的最小可定义集这样， 范畴就是可以用已知知识表达的信息项，换句话说，范畴就是用已知的知识可表达 的具有相同性质的对象的子集一般地说，在给定的知识库中，并不是所有对象子 集都可以构成范畴，即不能用知识库中知识准确表达概念因此，这样的子集可以 看作粗范畴( e p 不精确或近似范畴) ，它只能用知识通过两个不精确的范畴即上、下 近似集合，粗略地定义 根据近似定义，我们可以直接得到下列性质 定理2 2 2 【6 1 2 3 4 j 下近似和上近似满足如下性质： ( 1 ) 矽= u ，肋= f 2 j ： ( 2 ) 星( x n y ) = 型n 膨，r ( x u y ) = r ( x u y ) ； ( 3 ) 丛= ( 砑) ，劢。= ( 丛) 。，其中x 表示x 补集即x 。= u x ； 、 ，一 ( 4 ) 丛x ，x r x ； ( 5 ) x 互r ( r x ) ，r ( 墨x ) sx ； ( 6 ) 星x 星( 墨x ) ，r ( x ) s r ( r x ) 从这六条性质可以得到粗糙集的许多性质，我们仅仅列出这六条是因为它们可 以作为粗糙集的公理特征这六条性质在文献 6 中有相关的证明和论述 6 华北电力大学硕士或工程硕士学位论文 当r 为般二元关系时，对象x 的后继邻域定义为足( x ) = y ：( x ，j ，) r ) ，对于 任意x u ，x 关于r 的一般上近似和下近似定义如下： 竺小扛i r 如) c 柳 【缈月x = x l r 。( x ) n x a 显然，当r 为等价关系时，公式( 多即退化为公式 为了进一步分析下近似算子和上近似算子的性质，我们可以把下近似算子和上 近似算子看成是u 的幂集2 u 上的一对一元算子 定义2 2 1 6 , t 2 1算子厶日称为对偶的，如果对任意集合a u ，它们满足 ( 厶) 削= ( 删) 。， ( 凰) 删= ( 以。) 。 由定义2 2 1 和定理2 2 2 性质( 3 ) 可知，公式，( d 和中的上、下近似 算子对偶的，证明参阅文献 1 0 第3 2 节相关内容 设x ，y u ，l ，h 是对偶集合算子 6 ，如果满足： ( 厶) u = u，( 厶) 三( x n n = 三( x ) n 三( y ) ； ( 1 4 , ) n o = 乃，( 马) h ( x u y ) = h ( x ) u h ( i o 则在论域u 上存在一个二元关系r 使得l = a p r 矗，h = a p r 置如果厶日分别满足 ( 厶) 厶x x ，( 马) r h x ；( q ) x l h x ，( h 4 ) h l x 量x ；( 厶) l y 工工x ， ( n , ) i - l n x = _ h x ；那么存在一个自反的，对称的和传递的二元关系r 使得= a p _ 5 盘， 日= 万置 可以概括地说定理2 2 2 中前三条是粗糙集的基本性质，后三条分别对应于二 元关系的自反性，对称性和传递性 集合的不精确性是由于边界域的存在而引起的集合的边界域越大，其精确性 则越低为了更精确地表达这一点，引入了精度的概念，由等价关系r 定义的集合x 的近似精度为： 吣卜翮 其中x 刀，i x l 表示集合x 的基数 近似精度( x ) 用来反映我们对于了解x 的知识的完全程度显然，对于每一 个r 和x u 有0 a r ( x ) 1 华北电力大学硕士或工程硕士学位论文 2 3 知识约简和相对约简 知识约简( 又称属性约简) 是粗糙集理论的核心内容之一，众所周知，知识库中 的知识( 属性) 并不是同等重要的，甚至其中某些知识是冗余的，所谓知识约简，就 是在保持知识库分类能力不变的条件下，删除其中不相关或不重要的知识 设k = 缈，r ) 是一知识库，p r 且p 刀，称p p 为，不必要的，若 i n d ( p ) = i n d ( p - p ) ；否则称p 为p 必要的若任意p cp 为p 必要的，则称p 独立的，否 则称p 为依赖的 定理2 3 1 【1 2 】若p 是独立的，q c _ p ，则2 是独立 设q 冬p ，如果q 是独立的且i n d ( p ) - 爿n d ( q ) ，则称q 为p 的一个约简显然p 可 以有多种约简，p 所有约简构成的集合记为r e d ( p ) p 所有必要元素构成的集合记为 c o r e ( p ) ，称为p 的核 定理2 3 2 u “ c o r e ( p ) = 7 r e d ( p ) 定理2 3 2 说明了核的两个特点，首先说明核是所有约简的计算基础，因为核 包含在所有约简中，并且核可以由砌( 刀蒯( p ) 直接进行计算；其次可解释为在 知识约简时，它是不能消去的知识特征集合因此在用粗糙集理论知识处理数据时， 计算知识的核是一个重要的步骤 在知识挖掘中，往往知道分类结果，为了找出那些对分类结果有影响的知识， 因此就会用到相对约简因此有必要介绍一下知识的相对约简( r e l a t i v er e d u c t i o n ) 和相对核( r e l a t i v ec o r e ) 概念 首先定义一个分类相对于另一个分类的正域 令p 和q 为等价关系族，q 的p 正域记为p o s ，( q ) ，即 p o s p ( q ) - - 删0 ，口丛 2 的p 正域是中所有根据分类u p 的信息可以准确地划分到关系q 的等价 类中去的对象集合 令p 和q 为等价关系族，r ep ，如果p o s e ( q ) = p 啤i 脚( q ) 则称r 为p 中q 不必要 的；否则称为p 中q 必要的 如果p 中的每个属性r 都是q 必要的，则称p 为q 独立的( 或p 相对于q 独立) 设scp ，s 为p 的q 约简当且仅当s 是p 的q 独立子族且e o s s ( q ) = p o s e ( q ) 即s 是保持q 的，正域不变的极小子集p 的q 约简又称为相对约简 p 中所有p 的q 约简组成的集合记作r e d 口( p ) ，p 中所有p 的q 的必要关系组成 的集合称为c o r e o 仞 定理2 3 3 1 1 2 1e o r e e ( p ) = n r e d q ( p ) 华北电力大学硕士或工程硕士学位论文 2 4 区分矩阵 一个知识表达系统也称信息系统就是一个四元组s = ( u ，a ，y ，厂) ，其中【厂是非空 有限论域；4 是属性的非空有限集合，其中元素称为属性：y = u 圪，圪是属性口的 值域；厂：u x a y 是一个信息函数，它为每一个对象的每个属性赋予一个信息值， 即v a a ，x u ，f ( x ，口) y 对于知识表达系统s = 缈，a ，v ，厂) ，设i u i = 刀，即论域u 的基，s 的区分矩 阵是一个刀刀方阵，其中矩阵任意元素为d ( x , y ) = 口a l f ( x , a ) 厂 ，口) ，即d ( x , y ) 是能够区分对象x ，y 的所有属性集合s 区分矩阵记作d ：f 西，1 、 ，n e 定理2 4 1 2 1 设召a ，d ( x , y ) g 则曰是满足bn d ( x ，y ) a 的极小子集当 且仅当b 是彳的一个约简 定理2 4 2 n 0 1 2 1c 淝例= 口彳i j g ，力= a ，即核是区分矩阵中所有单个元素组成 的集合 对于决策表s = ( u ，a ，矿，力，a = c u d ，c n d = 1 2 j ，c 为条件属性集，d 为决 策属性集，可用类似的方法计算属性相对约简和相对核 决策表s 的区分矩阵是一个狞刀矩阵d 丰：f 矿，1，任意元素 d ( x ，y ) = 口a l f ( x ，口) f ( y ，a ) 且c o ( x ，y ) ，对于j ，y u ，c o ( x ，y ) 满足 ( 1 ) x p o s c d 且y 隹p o s c d ；或( 2 ) x 仨p o s c d 且y p o s c d ；( 3 ) 五y p o s c d 且 工，y 正i n d ( d ) 定理2 4 3 1 0 1 2 1 设若c c 是满足条件当d ( x ，y ) f 2 j 时c n d ( x ，y ) a 的极小 子集当且仅当c 是c 关于d 的一个相对约简 定理2 4 4 0 1 2 1c o r e o ( c ) = a e 彳p 似y ) = 口) ，即核是区分矩阵中所有单个元素组 成的集合 2 5 粗糙集理论中序同构的改进 本节讨论了文献 1 0 中等价关系和划分的之间的序同构关系，指出了该文献中序同 构的定义条件的不充分，做出了适当补充 定义 2 5 1 u 叫设l ( i 七) 是有限论域u 的子集， 若 五o ( i k ) ，五r 、x i g o ，) ，u 五= u ，则称 置i f k ) 是【，的划分 划分即是分类，就是将研究对象分成不同的类，各分类之间互不相交，且任何对象 均包含于某一类中 定理2 5 1 卅u 上的等价关系尺必然产生u 上的一个划分p ，u 上的一个划分 华北电力大学硕士或工程硕士学位论文 p 产生u 上的一个等价关系r 从而u 上的等价关系与划分一一对应 证明设犬是u 上的等价关系，记 k = x ，j ( 薯，x j ) r ) ( x j u ) 相应地，记u r = b ， 。l x t u ) ，由定义2 5 1 可证u i r 是一个划分 反之，若彳= 薯】ri x , 【， = 五i ，k ) 是u 的划分，记r = ( 薯，t ) 存在，j i ，慨，x ，x ，) ， 易证r 满足自反性、对称性和传递性，故r 是等价关系 由上述定理可知，等价关系与划分一一对应所以说划分和等价关系在对论域分类能 力上有着相同的分类作用下面就从划分方面构造粗糙集模型，进而研究粗糙集模型中 粒子的性质 为了比较不同划分之间的优劣，就必需要建立划分与划分之间的关系，下面引进了 偏序关系 定义2 5 2 【1 0 1设( k ，s ) ，其中k 是论域，是足上的关系，满足以下性质： 1 ) 自反性：x x( x k ) ； 2 ) 反对称性：当x y ，y x 时，工= y ，( 五y k ) ； 3 ) 传递性：当x y ，y z 时，x z y ，z k ) 称二元组( k ，) 为偏序集 定理2 5 3 邮】 设u 是论域，讼( u ) = r g u 2 i r 是u 上的等价关系) 则( r ( u ) ，c ) 是偏序集 文献 1 0 中第2 0 页对划分之间的“细于关系和“序同构 关系的论述有不妥之 处( 详细说明见附录1 ) ：按照文献 1 0 中定义的细于关系和序同构，序同构不具交换性， 即当( r ( u ) ，互) 兰( k ( u ) ，) ，不能推出( k ( u ) ，) 兰( r ( u ) ，) 例：4 = 毛，恐) ， 毛，_ ， 毛，气) ，鸣= “，x 2 ，x d ， _ ，x 5 ，毛 ) 由细于定义知4 4 ，设 关系墨，垦分别与划分4 ，4 一一对应，由细于包含定义知墨岱是 下面重新定义划分之间的细于关系，定义了序同构关系 定义2 5 2设u 是论域，u 上的两个划分， 肛 五，置，置 ， 肛 x ，k ，z 若对于任意的置a ，存在巧b ，使五弓，则称彳细于曰， 记作a b 定理2 5 4 设u 是对象集，记k ( 【，) 是划分组成的集合，对于定义2 5 2 定义的 细于关系，可证( k 渺) ，) 是偏序集 证明由定义易证 定义2 5 3 设( 墨，。) 与( k ：，：) 是两个偏序集，若存在h ：k 一疋是一一映 射，j j i 一是h 的逆映射，且满足： ( 1 ) 任意x a l 屯| i l ( 五) 2 ( 艺) ，v x , ，屯i q ； ( 2 ) 任意j l l ( 而) ： ( 恐) ，( j i l ( 五) ，而( 而) 疋) ，有j i i ( 玉) 与办- 1 j j l 化) ，即五s 。屯 1 0 华北电力大学硕士或工程硕士学位论文 称( k ，。) 与( ，：) 序同构，记作( k ，。) 兰( 疋，：) 定理2 5 5 设u 是论域，则( k ( ，9 兰( r ) ，) 证明：定义映射h ：r ( u ) 专k ( u ) ，五( 尺) = u r 由定理2 5 1 知h 是一一映射， 所以存在h 以：k ( u ) r ( 【，) 一方面，任取尺，尺，记 ( 尺) = u r = f i x , 庸：而u ， h ( r 7 ) = u r = 葺】：而u ) 当尺r 时，【再k 】( 薯u ) ，因此五( 置) 而( 垦) 另 一方面，取h ( r ) ，h ( r7 ) 是u 的两个划分，若h ( r ) h ( g ) ，由划分h ( r ) ，h ( r ) 对应的 等价关系，可证矗) 互兄( 置，) ，郎有r f ，故定理得证 通过对文献 1 0 中序同构定理和细于定义的修改，对于序同构的两个偏序集的任一 个偏序集进行研究所的结果等价于对另一个偏序集的相应的研究结果 由定理2 5 5 可知，由等价关系形成的等价类构成论域上的一个划分，反之用等关 系定义的粗糙集模型可以划分来描述从划分角度研究粗糙集理论，给出了下面的定义 和定理 定义2 5 3 设u 是论域，a = ( 4 ，4 ，4 ，i ) 是u 上的一个划分称，4 ) 是一个 近似空间，对任意u 中任意一个子集x ，x 关于近似空间( u ，彳) 的下近似集合p x 和 上近似集合p 分别定义为： e 政x = ：u 4 u 4 i 矗怒蓍t 兰1 9o * m ) 1 啊=1 4n x = 彩，= ) 一 下面我们给出了公理化粗糙集中最基本的性质，并利用划分方法加以证明， 定理2 5 6 设【，是论域，基于划分上的下近似集合些和上近似集合p x 具有如 下性质： ( 1 ) 矽= p u = u ，幽= 助= o ； ( 2 ) 丛sx p x ； ( 3 ) 豇xn y ) = 型n 丛，p ( x u y ) = 蹦u ； ( 4 ) ( x ) = ( ( x ) ) 。，- ( x 。) = ( 上( x ) ) 。 证明：( 1 ) 由定义可知坛u ，则x p _ u 又x 一p u ，弘cu 使工4 cu ， 所以彤= u 同理可证彤= u 故彤= p u = u 由定义可证麴= 肋= g ( 2 ) v x e 丛，弘工所以x j 即丛x ，同理由上近似定义得x 蹦 ( 3 ) ( x n d = u 4 1 4 x f l y ，t = l ，m ) = u 4 1 4 x 4 】，= l ，m ) = u 4 f 4 x ，r = 1 9 * oo r e f 1 4 1 4 l t = 1 9 tq * m = 必n 同样可以证明一p ( x u y ) ：两u 却 ( 4 ) p ( x ) = u 41 4x c , ，= 1 ，m ) = u 41 4l i x = f 2 j ，t = 1 ，聊) = ( u 41 4n x o ，t = l ，朋 ) 。= ( _ ( x ) ) 同理可证砸。) = ( 2 ( x ) ) 。 1 1 华北电力大学硕士或工程硕士学位论文 定理2 5 6 说明划分与等价关系是一一对应，因此公式和( 参是代表相同的粗糙 集模型，只不过( d 是从粒子角度研究粗糙集模型，而公式是从关系角度研究的粗糙 集模型现实生活中，由于对象之间关系并不明显，或者说不同对象之间的不可区分性 不太明显，但知识总是以粒子的形式存在的，因此在知识库中用粒子观点构造粗糙集模 型极为重要，这在属性约简中有重要的应用价值 1 2 华北电力大学硕士或工程硕士学位论文 第三章模糊粗糙集 模糊集理论是美国计算机与控制论专家扎德( l a z a d e h ) 于1 9 6 5 年提出