（应用数学专业论文）覆盖粗糙集研究.pdf

西南交通大学研究生硬士学位论文第1 页 摘要 粗糙集理论是波兰科学家z p a w l a k 于1 9 8 2 年提出的一种数据分析理论， 目前已发展成为一种处理模糊和不确定性信息的数学理论，并且成功地应用 于机器学习、模式识别、决策支持、数据挖掘、过程控制等领域。 p a w l a k 粗糙集理论是以等价关系为基础建立的。为了推广粗糙集理论的 应用范围，研究者提出了多种广义的粗糙集模型。其中。z b o n i k o w s k i 利用 论域上的覆盖建立了覆盖粗糙集模型。许多学者对z b o n i k o w s k i 定义的算子 做了适当的修改，得到了新的覆盖近似算子。本文讨论了这些算子的性质及 其相互关系，并进而讨论了这些近似算子和z b o n i k o w s k i 模型中近似算子之 间的相互关系。 租糙集理论中有两个基本包含关系式，即u d 2 uc ( y ) 和 及z n y ) o ( x ) f l p 0 9 ，这意味着在进行粗糙集的并、交运算时信息有可能 丢失。张化光哺通过两种算子，解决了p a w l a k 粗糙集模型信息丢失问题。 本文将探讨覆盖租糙集的信息丢失问题通过在覆盖粗糙集模型中定义两种 新型的算子，解决了覆盖粗糙集模型信息丢失问题，并基于这两种新型算子 证明了覆盖粗糙集具有良好的代数性质，进而建立了一种基于布尔代数的覆 盖粗糙集模型。 关键词：粗糙集：覆盖粗糙集；覆盖上近似；覆盖下近似；布尔代数 西南交通大学研究生硕士学位论文第页 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 sb e e nd e v e l o p e dt ob ean e w m a t h e m a t i e a lt 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 d s u c c e s s f u l l yt om a n ya r e a si n c l u d i n gm a c h i n el e a r n i n g ，p a t t e r nr 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 ga n dp r o c e s sc o n t r 0 1 t h et h e o r yo fp 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 c e r a l a f i o n t h er e s e a c h e r sp u tf o r w a r dm a n yk i n d so fg e n e r a l i z e dr o u g hs e tm o d e l s i no r d e rt oe x p a n di t sa p p l y i n ga r 饯i s a m o n gt h e s er e s c a c ha r o a s z b o n i k o w s k i e s t a b l i s h e dc o v e r i n gr o u g hs e tm o d e lu s i n gac o v e r i n go fau n i v e r s e n e r e s e a r c h e r sr e a s o n a b l ym o d i f i e dt h ed i f i n i t i o no ft h ec o v e r i n ga p p r o x i m a t i o n o p e r a t i o ni nz b o n i k o w s k i sm o d e la n dp r o p o s e ds o m ep a i r so fc o v e r i n g a p p r o x i m a t i o no p e r a t o r s i nt h i sp a p e r , w ed i s c u s st h ep r o p e r t i e so ft h e s ec o v e r i n g a p p r o x i m m i o no p e r a t o r s t h er e l a t i o n s h i p sa m o n gt h e s eo p e r a t o r s 嗍 i n v e s t i g a t e d f u r t h c r m o r e 也er c l m i o n s h i p sb e t w e e nt h e s eo p e r a t o r sa n dt h e o p e r a t o r si nz b o n i k o w s k im o d e lw e r ei n v e s t i g a t o d t h e r ea r et w ob a s i c a lr a l a t i o n a lf o m u l a so f r o u g hs e ti n c l u s i o n ：c un2 ) uc ( y ) m d c ( x n y ) c ( x ) c l c ( y ) 憾m 锄st h a tt h ei n f o r m a t i o nm a y b el o s ti nt h eo p e r a t i o n so fu n i o n , i n t e r s e c t i o na n dc o m p l e m e n ti nr o u g hs e tt h e o r y z h a n gh u a g u a n g 2 8 ，2 9 】s o l v e st h ep r o b l e m so fi n f o r m a t i o nl o s tb yi n t r o d u c i n g t w oo p e r a t o r si np a w l a km o d e l i nt h i sp a p e r , w ew i l ld i s c u s st h ep r o p e r t i e so f i n f o r m a t i o ni o s ti nt h ec o v c r i n gr o u 曲s e t w es o l v et h i sp r o b l e m sb yi n t r o d u c i n g t w oi l e wt y p e so fo p c r a t e r si nc o v e r i n gr o u g hs e t w ea l s od i s c u s st h ea l g e b r a i c p r o p e r t i e so f 山ec o v e r i n gr o u g hs e tb a s e do ut h et w oo p e r a t o r s f u t h e r m o r e w e e s t a b l i s ht h ec o v e r i n gr o u g hs e tb a s e do nt h eb o o l e a na l g e b r a k e yw o r d s ：r o u g hs e t ；c o v e r i n gr o u g hs e t ：c o v e r i n gl o w e ra p p r o x i m a f i o m c o v e r i n gu p p e ra p p r o x i m a t i o n ：b o o l e a na l g e b r a 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权西南交通大学可以将本论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复印手段保存和汇编本学位论 文 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密口，使用本授权书 ( 请在以上方框内打“，”) 学位论文作者签名：傣幻均 日期：町2 千 指导老师签名：詹芝主， 日期：阳7 ，1 2 ，乒 西南交通大学学位论文创新性声明 本人郑重声明：所呈交的学位论文，是在导师指导下独立进 行研究工作所得的成果。除文中已经注明引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写过的研究成果。对本 文的研究做出贡献的个人和集体，均已在文中作了明确的说明。 本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 本文主要针对覆盖粗糙集，对几种不同类型的覆盖粗糙集的 性质及相互之问的关系进行了研究，并且定义并讨论了覆盖粗糙 集中的新型算子。 许多学者对z b o n i k o w s k i 定义的算子做了适当的修改，得到 了新的覆盖近似算子。本文讨论了这些算子的性质及其相互关系， 并且进而讨论了这些近似算子和z b o n i k o w s k i i 模型下近似算子 之间的相互关系。 粗糙集理论中有两个基本包含关系式，郾 u y ) 2 ) u ( 】r ) 和弓( x n l o c _ c ( x ) n c ( y ) 这意味着在 进行粗糙集的并、交运算时信息有可能丢失。张化光通过两种算 子，解决了p a w l a k 粗糙集模型信息丢失问题。本文通过在覆盖粗 糙集模型中定义两种新型的算子，解决了覆盖粗糙集模型信息丢 失问题，并基于这两种新型算子证明了覆盖粗糙集具有良好的代 数性质，进而建立了一种基于布尔代数的覆盖粗糙集模型。 西南交通大学研究生硕士学位论文 第1 页 第1 章绪论 本章将介绍本文的写作背景并简要介绍本文的主要研究工作。 1 1 粗糙集理论概述 粗糙集作为一种处理不精确、不确定与不完全数据的新的数学理论，最 初是由波兰数学家z p a w l a k 于1 9 8 2 年提出的。由于最初关于粗糙集理论的 研究大部分是用波兰语发表的，因此当时没有引起国际学术界的重视，研究 地域也仅局限在东欧一些国家，直到2 0 世纪8 0 年代末才逐渐引起各国学者 的注意。近几年来，由于它在机器学习与知识发现。一、数据挖掘h ”、决策 支持与分析照锕等方面的广泛应用，研究逐渐趋热。1 9 9 2 年，第一届关于粗 糙集理论国际学术会议在波兰召开。1 9 9 5 年，a c mc o 咖u n i z a t i o n 将其列为 新浮现的计算机科学的研究课题；1 9 9 8 年，国际信息科学杂志( i n f o r m a t i o n s c i e n c e s ) 还为粗糙集理论的研究出了一期专辑。这些表明了粗糙集理论与 应用研究有着广泛的发展前景。 租糙集理论建立在分类机制的基础上，它将分类理解为特定空间上的等 价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数 据的划分，每一被划分的集合称为概念。粗糙集理论的主要思想是利用已知 的知识库。将不精确或不确定的知识用已知的知识库中的知识来近似刻画。 该理论与其他处理不确定和不精确问题理论的最显著的区别是它无需提供问 题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述 或处理可以说是比较客观的。由于这个理论未能包含处理不精确或不确定原 始数据的机制，所以这个理论与概率论，模糊数学和证据理论等其他处理不 确定或不精确问题的理论有很强的互补性。 1 1 粗糙集理论的研究现状 目前，粗糙集理论的研究主要集中在：粗糙集模型的推广，阿题的不确定 性研究，与其他处理不确定性、模糊性问题的数学理论的关系与互补，纯粹的 数学理论方面的研究，粗糙集的算法研究等。这些研究有的是受应用的推动 而产生，有的是纯理论的。 i 1 1 粗糙集模型的推广 p a w l a k 粗糙集模型的推广一直是粗糙集理论研究的主流方向之一。目前 西南交通大学研究生硕士学位论文第2 页 主要有两种方法：乱构造性方法：b 代数( 公理化) 方法。 a 构造性方法是对原始p a w l a k 粗糙集模型的一般推广，其主要思路是从 给定的近似空间出发去研究粗糙集和近似算子。它是以论域上的二元关系或 布尔子代数作为基本要素，然后导出租糙集代数系统( 2 u ，u n ，a p r ，a p r ) 这种方法所研究的问题往往来源于实际，所建立的模型有很强的应用价值， 其主要缺点是不易深刻了解近似算子的代数结构。 在p a w l a k 粗糙集模型中有三个最基本的要素：一个论域u ，u 上的一个 二元等价关系胄( 或划分) ( 它们构成了近似空间) ，一个被近似描述的( 经典) 集合，也称为专家概念。这样，推广的形式主要也有三个方向，即从论域方向、 从关系方向( 包括近似空间) 以及从集合方向。 从论域方向推广的目前只有一种，就是双论域的情形，当然这时的二元关 系就变成为两个论域笛卡尔乘积的一个子集。对于将论域推广到多个的情形 来研究粗糙集理论的文献还没有见到。 关系的推广：一种是将论域上的二元等价关系推广成为一般的二元关系 得到了一般关系下的粗糙集模型：另一种是将对象工所在的等价类看成是x 的 一个邻域，从而导出了基于邻域算子的粗糙集模型：z a k o w s k i 把划分放宽为覆 盖，将p a w l a k 粗糙集理论推广为覆盖广义粗糙集理论：也有将由关系导出的 划分推广为一般的布尔子代数，以此出发定义粗糙集和近似算子：更一般的 是将普通关系推广成模糊关系或模糊划分，得到模糊粗糙集模型。 将集合和近似空间进行推广。这一类的推广是与其他处理不确定、不精 确或模糊知识( 如概率论、模糊数学、信息论、证据理论等) 结合起来进行研 究。 b 代数方法也称为公理化方法，有时也称为算子方法，这种方法不是以二 元关系为基本要素，它的基本要素是一对满足某些公理的一元( 集合) 近似算 子厶h ：2 “- - - p 2 u ，即粗糙代数系统( ，一，u ，n ，厶日) 中近似算子是事先给定 的。这种方法研究的明显优点是能够深刻地了解近似算子的代数结构，其缺点 是应用性不够强。 1 l2 不确定性问题的理论研究 粗糙集理论中知识的不确定性主要由两个原因产生：一个原因是直接来 自于论域上的二元关系及产生的知识模块，即近似空间本身。从这个角度看。 处理知识的不确定方法往往用信息熵来刻画，知识的粗糙性实质上是其所含 西南交通大学研究生硕士学位论文第3 页 信息多少的更深层次的刻画，不少学者在这方面做了研究工作“。粗糙集 理论中知识不确定性的另一个原因来自于给定论域里粗糙近似的边界，当边 界为空集时知识是完全确定的，边界越大知识就越粗糙或越模糊。一些学者 引进了粗糙熵巨( 工) 的概念来刻画x 的不确定性。 寻求一个合适的度量来刻画知识的不确定性也是粗糙集理论研究的一个 重要方向。 1 1 3 粗糙集与其他处理不确定性理论的关系 租糙集理论与其他处理模糊性或不确定性理论的关系研究，主要集中在 它与概率统计、模糊数学、d s 证据理论和信息论的相互渗透与补充。 在信息系统中，知识库的知识的类型一般有两类：一类是知识库中所有对 象的描述是完全已知的，p a w l a k 粗糙集模型和一般关系下的粗糙集模型就是 属于这一类：另一类是知识库中的对象的描述只有部分是己知的，只能通过 训练样本所提供的信息类刻画概念，抽取样本时应符合统计规律性，因此概 率统计与粗糙集理论的结合就显得非常自然。 模糊集理论和粗糙集理论在处理不确定性和不精确性问题方面都推广了 经典集合论。具有一定的相容性和相似性，然而它们的侧重面不同。模糊集 通过对象关于集合的隶属程度来近似描述，而粗糙集通过一个集合关于某个 可利用的知识库的一对上、下近似来描述；模糊集强调边界的不分明性，而 粗糙集强调对象间的不可分辨性；模糊集研究的是不同对象间的隶属关系， 粗糙集研究的是不同类中的对象组成的集合关系：模糊集的隶属函数大多是 由专家凭经验给出，带有较强的主观性，而粗糙集的粗糙隶属函数的计算是 从被分析的数据中直接获得的，相对客观。目前所见的模糊粗糙集模型“6 “1 和粗糙模糊集模型是二者结合的成功范例。粗糙集理论与d s 证据理论在处 理不确定性问题时方法是不同的，但却有某种相容性。粗糙集理论中的下近 似和上近似的概率恰好分别是d s 证据理论中的信任函数和似然函数“”，然 而生成信任函数和似然函数的基本概率分配函数( 即m a s s 函数) 方法是不同 的，前者来自于系统中数据本身，比较客观，而后者往往来自于专家的经验， 带有很强的主观性，粗糙集理论与d s 证据理论有很强的互补性。 i 1 4 算法研究 粗糙集理论中有效算法研究是粗糙集理论应用于信息系统知识发现领域 的一个主要研究方向。粗糙集理论的应用上主要有两大类：一类是无决策的 分析，内容主要包括数据压缩、约简、聚类与机器学习等；另一类是有决策 西南交通大学研究生硕士学位论文第4 页 分析，内容主要包括决策分析、规则提取等，也涉及对原始数据的预处理， 如数据压缩与约简等。目前，粗糙集理论中有效算法研究主要集中在导出规 则的增量式算法，约简的启发式算法，粗糙集基本并行算法，以及与粗糙集 有关的神经网络与遗传算法等嘲。这些研究的成功应用有的已经获得了商业 价值。 1 1 5 粗糙集与其他数学理论的联系 随着对粗糙集理论研究的不断深入，它与其他数学分支的联系也更加紧 密。例如，从算子的观点看粗糙集理论，它与拓扑空间、数理逻辑、模态逻 辑、格与布尔代数、算子代数等联系较为紧密：从构造性和集合的观点来看， 它与概率论、模糊数学、证据理论、图论、信息论等联系较为密切。粗糙集 理论研究不但需要以这些理论作为基础，同时也相应地带动这些理论的发 展。 目前，数学理论与粗糙集理论结合起来进行研究已有文章出现，并不断 有新的数学概念出现，如“粗糙逻辑”“”、“粗糙理想”、“粗糙半群”“” 等等。随着粗糙结构与代数结构，拓扑结构，序结构等各种结构的不断整合。 必将涌现出新的富有生机的研究方向。 1 2 本文的学术背景和写作动机 在p a w l a k 粗糙集模型中。论域上的等价关系起着至关重要的作用。基 于等价关系形成的划分，构造了论域上的上、下近似算子，用于刻画不精确 概念，并进而研究相应的知识约简与知识获取问题。但在很多实际问题中，对 象之间的等价关系很难构造，或者对象之间本质上没有等价关系为了推广 粗糙集理论的应用范围，根据一些具体问题，研究者对p a w l a k 粗糙集模型 进行了多种形式的推广，相继出现了变精度粗糙集模型、程度粗糙集模型、 模糊粗糙集模型、基于一般二元关系的粗糙集模型、基于覆盖理论的粗糙集 模型等。 z b o n i k o w s k i 哺1 从实际应用出发，提出了覆盖粗糙集模型，讨论了相关 的性质。2 0 0 3 年w i l l i a mz h u 和f e i y u ew a n g 在覆盖粗糙集的基础上给出 了约简的概念和方法，并证明了一个覆盖通过约简得到的最简覆盖是惟一的， 而且最简覆盖相同的两个覆盖产生相同的覆盖上、下近似这说明，覆盖约 简方法是信息系统和数据挖掘中消除冗余数据的一种技术。 在覆盖粗糙集模型的研究中，针对z b o n i k o w s k i 定义的算子不具有对偶 性，特别是其上近似算子不满足单调性。许多学者对其定义的近似算子做了 西南交通大学研究生硕士学位论文第5 页 适当的修改。其中，w i l l i a mz h u 啪1 对覆盖近似算子做了适当修改，定义了几 种新的覆盖上近似算子，并且讨论了它们的性质，公理化条件，约简及其相 互之间的关系。借助邻域，针对z b o n i k o w s k i 模型中上、下近似算子不对偶 的特性，秦克云o ”定义了几对对偶的近似算子，并且讨论了它们的性质及其 相互关系。 本文讨论并完善以上两位学者提出的这些算子的性质及其相互关系，并 且进而讨论了这些近似算子和z b o n i k o w s k i 模型中近似算子之间的相互关 系。 粗糙集理论中有两个基本包含关系式，即u y ) 2 u ( 】，) 和 c ( x n r ) c _ 及幻n 舀( y ) ，这意味着在进行粗糙集的并、交运算时信息有可能 丢失蚓。张化光在文e 2 8 和 2 9 中定义了两种算子，解决了p a w l a k 粗糙集 模型信息丢失问题。本文将探讨覆盖粗糙集的信息丢失问题，通过在覆盖粗 糙集模型中定义两种新型的算子，解决了覆盖粗糙集模型信息丢失问题，并 基于这两种新型算子证明了覆盖粗糙集具有良好的代数性质，进而建立了一 种基于布尔代数的覆盖粗糙集模型。 西南交通大学研究生硕士学位论文第6 页 第2 章粗糙集理论的基本知识 本章主要介绍p a w l a k 粗糙集模型以及覆盖粗糙集模型的一些基本概念 与性质，作为后面各章节的基础。 2 1p a w l a k 粗糙集模型 2 1 1 知识与知识库 1 8 粗糙集理论认为知识是对对象进行分类的能力。设所讨论的对象的集合 为u ，称【，为论域。若工【，则称x 为一概念。【，中任何概念族称为关于 ，的抽象知识，简称知识。p a w l a k 粗糙集理论仅讨论对论域u 形成划分的知 识，一个划分，的定义为：z = 墨，五，置 ；其中五量u ，五a ，f ，时 有五n z ，= a ，且u 五= 【厂【，上的一族划分称为关于u 的一个知识库。 设r 是( 厂上的一个等价关系，u r 表示置的所有等价类构成的集合，【巩 表示包含元素工u 的等价类。称二元组k = ( u ，r ) 为一个知识库，其中u 为 论域，r 是u 上的一族等价关系。 若p r 且p 刀，则n p ( p 中所有等价关系的交集) 也是一个等价关 系，称为p 上的不可区分关系，训3 i n d ( p ) ，且有【乩d t ，2 廖工】且这样， u i n d ( p ) 表示与等价关系族p 相关的知识，称为置中关于【，的p 基本知识。 2 1 2p a w l a k 粗糙集模型及其相关性质 1 ，3 设u 是一个非空有限集合，r 是【，上的一个等价关系，称二元组( u ，r ) 为 p a w l a k 近似空间。对于任意j 互u ，z 关于近似空间，固的下、上近似分 别定义为： 丛= x l t x , n ； 西南交通大学研究生硕士学位论文第7 页 尉册= 伽l 嗍。n z 纺 集合魄( 幻= 取一丛称为x 的r 边界域；眇。( 幻= 盟称为x 的正 域；n e g _ ( 的= 【厂一融称为x 的r 负域。 显然厨= p 咚旺) u ( 的 当凰幻足( 幻时，称二元组( 型j 0 ，只( 柳为近似空间中的租糙集。 星x 或p o s d x ) 是由那些根据知识矗判断肯定属于工的u 中元素组成的 集合；豇是那些根据知识r 判断可能属于x 的u 中元素组成的集合； 缸。( x ) 是那些根据知识r 既不能判断肯定属于j 又不能判断肯定属于一z ( 即u - x ) 的u 中元素组成的集合；珏曙t ( 朋是那些根据知识且判断肯定不 属于x 的中元素组成的集合。 令。表示空集，一x 表示x 关于u 的补集。下面是p a w l a k 粗糙集的一 些性质： o l ) 星) = u ，( 1 h ) 酗) = u ； ( 2 l ) 豇a ) = a ，( 2 h ) r ( o ) = a ； ( 3 l ) 垦( 柳x ，( 3 h ) 石r ( 朋； ( 4 l ) 墨( x n d = 星( 幻n 星( d ，( 4 1 1 ) i ( x u d = 趸( x ) u 页( y ) ； ( 5 l ) 墨 ) = 墨( 椰，( 5 h ) i 饭( 柳= _ ( j ) ； ( 6 l ) 趴一只，( 鲫) 即田一墨( 柳； ( 7 l ) x y j 烈幻星( 幻，( 7 1 1 ) x 】，j i ( 石) 页( y ) ： ( 8 l ) 扑一艄，( 8 h ) 砰_ ( 删一私) ： 西南交通大学研究生硕士学位论文第8 页 ( 9 l ) v k u r ，星僻) = 足，( 9 h ) v k e u i r ，r ( i o = 置 容易看出，( 3 l ) ，( 4 l ) 和( 8 l ) 是下近似算子的基本性质，即由( 3 l ) ， “l ) 和( 8 l ) ，可以推出其它性质；( 3 h ) ，( 4 t i ) 和( 明) 是上近似算子的基本性 质，即由( 3 h ) ，( 4 h ) 和( 8 h ) 可以推出其它性质。 一般情况下，下列等式不成立： ( 1 ) 豇x u d = 凰石) u 星( y ) ： ( 2 ) r ( x n 】1 = r ( x ) n r ( r ) 。 2 2 覆盖粗糙集的基本概念及性质 2 2 1z b o n i k o w s k i 覆盖粗糙集模型及其相关性质 1 9 定义2 1 设【，是有限论域，c 是u 上的子集族。若c 中没有空集作为元 素，并且所有元素之并为u ，则称c 是论域【，的一个覆盖。 显然，论域【，上的由等价关系所形成的划分也是一个覆盖，覆盖是划分 的推广。 定义2 2 设【，是有限论域，c 是【厂上的覆盖，称二元组( 以o 为一个覆 盖近似空间。 定义2 3 设，c ) 是覆盖近似空间。对于x u ，称 埘留o ) = x c k a ( v s c ) o s s k = ，k = $ 为工的最小描述。 类似于p a w l a k 近似空间，可以引入上、下近似的概念。 定义2 4 对于集合x u ，集族c = 省c 墨x ) 称为x 的覆盖下 近似集族。 集合置= u c ) 称为石的覆盖下近似。 集族b n ( x ) = u 彪i e 石一置) 称为x 的覆盖边界集族。 集族f ) = c ( x ) u b n ( x ) 称为工的覆盖上近似集族。 西南交通大学研究生硕士学位论文第9 页 集合x = u c c x 9 称为石的覆盖上近似。 如果f = c ) ，则称x 是精确的，否则，称z 是不确定的。 定理2 i 设，c ) 是覆盖近似空问，对于任意z ，y c _ u ，x e u ，有 ( 1 ) c ( 动= c ( a ) = g ，c ( u ) = c ( 叨= u ； ( 2 ) c f ； ( 3 ) ) = g = f 佤) ； ( 4 ) x c _ y g c ( d 置s z ； ( 5 ) c 佤) = a ； ( 6 ) c ( 刁) o 营 工) c ； ( 7 ) f ( 工) 产朋玎o ) ； ( 8 ) r 脚= n c ；x 研 定理2 2 设，c ) 是覆盖近似空间，对于任意x ，y c _ c 厂，有 ( 1 ) 以= u = c ，；( 2 ) a = d = a ； ( 3 ) 置x r ；( 4 ) ( 置) - x ，( r ) = r 文献 2 0 通过举例说明了下面的性质一般不成立： ( i ) ( j n y ) = 置n z ，( x u y ) = 石u y ； ( 2 ) 置一卜x ) ，工一( 一； ( 3 ) x y j x i f ； ( 4 ) ( 一五) 一五，卜r ) 一r 西南交通大学研究生硕士学位论文第l o 页 2 2 2 最简覆盖 2 0 定义2 5 设c 是论域u 上的一覆盖，k c ，如果置是c f x l 中的一些 集合的并集。则称x 是c 的一个可约简的元素，否则，称足是c 的一个不可 约简的元素。 定义2 6 设c 是论域u 上的一覆盖，如果c 的每个元素都是不可约简的 元素，则称c 是不可约简的；否则，称c 是可约简的。 命题2 1 设c 是论域【，上的一覆盖，如果k 是c 的一个可约简的元素， 则c - k 也是u 的覆盖。 命题2 2 设c 是论域u 上的一覆盖，k c ，k 是c 的一个可约简的元 素，局e c 一 足l ，则墨是c 的一个可约简的元素当且仅当它是c - , r 的一 个可约简元素。 由上面两个命题可知，删除一个覆盖的可约简元素后所得的仍然是一个 覆盖。删除一个覆盖的可约简元素后不会产生任何新的可约简元素，也不会 使原来的可约简元素变成新覆盖下的不可约简元素。因此，可以通过同时删 除一个覆盖的所有可约简元素或者逐次删除可约简元素的方法来得到一个不 含可约简元素的覆盖删除覆盖的可约简元素的过程，称之为覆盖约简。 定义2 7 设c 是论域u 上的一覆盖，称通过覆盖约简而得到的新的不含 可约简元素的覆盖为c 的最简覆盖。记为r e a u a ( o 命题2 3 设c 是论域【，上的一覆盖，则c 和r e a u a ( c ) 产生相同的覆盖 下、上近似。 命题2 4 设c l 和c 2 是论域【，的两个覆盖，c i 和c 2 产生相同的覆盖下、 上近似当且仅当忍如以( c ；声昆础耐( g ) 西南交通大学研究生硕士学位论文第11 页 第3 章覆盖粗糙集模型的相互关系 p a w l a k 粗糙集理论是以等价关系为基础建立的，为了推广该理论的应用 范围，研究者提出了多种广义的粗糙集模型。其中，z b o n i k o w s k i 利用论域 上的覆盖建立了覆盖粗糙集模型。许多学者对z b o n i k o w s k i 定义的算子做了 适当的修改，得到了新的覆盖近似算子。本章讨论这些算子的性质及其相互 关系，进而研究这些近似算子和z b o n i k o w s k i 近似算子之间的相互关系。 3 1 四种覆盖粗糙集模型 3 1 1 第一种类型覆盖粗糙集 定义3 1 2 1 设，c ) 是覆盖近似空间，对任意j e u ， ( 力= n 足e c ；x k 称为工的邻域。 由定理2 1 ( 8 ) ，容易得到o ) = n 砌( 刁 定义3 2 设缈，o 是覆盖近似空间，x _ c u ，集合c i = u e c ；k x ) 称为x 的第一种类型覆盖下近似；集合己) = u ( 工) 称为工的 第一种类型覆盖上近似。 3 1 1 1 第一种类型覆盖粗糙集的性质 1 9 ，2 1 设缈，c ) 是覆盖近似空间，对于任意肖，y o u ，有 ( 1 ) c 1 ( a ) = 己( 彩) = o ，c l ( = 互( = u ： ( 2 ) 鸟) x e ) ； ( 3 ) ( c l ) ) = g ，己( 己) ) = 互； ( 4 ) x y jc l ) g ( y ) 磊( x ) 互( 】，) ； ( 5 ) 己( z u y ) = 互( z ) u 互( 】，) ； 西南交通大学研究生硕士学位论文第1 2 页 ( 6 ) v k e c g ( 幻= 置；己( 足) = 足 下面的性质一般不成立： ( 1 ) g 岱n l 乍鸟) n 鸟( y ) ； ( 3 ) 磊( 一g ； ( 5 ) 霸( 弓户一弓 ( 2 ) g ( 一x 户一互； “) c g ( - g ) 一g ： 例3 1 设【，= k 鼠c ，d ) ，墨= 4 b ) ，局= 口，b ，d ，墨= 似d ) ， c = 墨，局，墨 则c 是u 的一个覆盖。 ( 1 ) 设z = 口，b ，c ) ，y = c d ) 则x n l ，= 0 ，有g n 卿； 但是5 = z ，g ( d ：r ，g n g ( d = c ) 彩 ( 2 ) 设z = 口，以4 ，则有c l = 口，以c ) 但是己( 一d = 己( p ) ) = c ，d ) ， 故有g ( j ) 一磊d ( 3 ) 设z = d ，同上，可得五( 幻一鸟 ( 4 ) 设x = a , b ，c ) 则有c 1 = 取b , c ) ，g ( 一g ) = g ( d ) 产a 故有g ( 一g ) ( 5 ) 设z = 口，b ，c ) ，则有己阶 以b ，d ，一蟊阶 d ) ，己( 一五) ( d ) ) = c ，d ) ，故有己( 一e ( 硼一磊 3 1 1 2 第一种类型覆盖粗糙集的约简及拓扑性质 定理3 1 设c 是u 的一个覆盖，如果k 是c 的可约简元素，则对任意 x e u ， ，o ) 在c 一 k 和c 中相同。 证明：由 2 z 的性质8 ，m d ( x ) 在c - k 和c 中相同。又由o ) 的定义， 西南交通大学研究生颈士学位论文第1 3 页 得到( 力在c 一 置 和c 中相同。 命题3 1 2 0 2 2 ( 1 ) 两个不可约覆盖生成相同的覆盖下近似，那么这两个覆盖相同。 ( 2 ) 设c 是u 的一个覆盖，则c 和m d u c t ( o 生成相同的下近似算子。 ( 3 ) 设c l ，g 是u 的两个覆盖，q 和c 2 生成相同的下近似当且仅当 r e d u a ( c , ) = r e d u c t ( g ) 由 2 2 的定理3 和5 及g ) 的定义，容易得到以下定理。 定理3 2 ( 1 ) 设c 是u 的一个覆盖，则c 和r e d u a ( c ) 生成相同的上近似 算子。 ( 2 ) 设c l ，c 2 是u 的两个覆盖，如果风庙耐( q ) = 忍西耐( c 2 ) ，则q 和g 生成相同的上近似。 ( 3 ) 设g ，c 2 是u 的两个覆盖，如果g 和g 生成相同的下近似，也生 成相同的上近似。 定义3 3 1 2 3 ( 闭包算子) 对一个算子d ：p ) _ 尸) ，如果对任意 置y o u ，满足 ( 1 ) d ( x o d = d ( x ) o d ( d ,( 2 ) x c ，( 柳； ( 3 ) d ( o ) = o ；( 4 ) d ( c ，( ) = 州柳 则称这个算子为u 上的闭包算子。 定义3 4 1 2 3 ( 内部算子) 对一个算子i n t ：p ) _ ，( ，如果对任意 置r u ，满足 ( 1 ) j n t ( x f l y ) = i n t ( x ) n i n t ( y ) ； ( 2 ) i n t ( x ) x ； 西南交通大学研究生硕士学位论文第1 4 页 ( 3 ) i n t ( o = u ；( 4 ) t n t ( i n t ( x ) ) = i n t ( x ) 则称这个算子为u 上的内部算子。 定理3 3 2 3 c l 是内部算子当且仅当v k ，k e c k n k = o 或者k n k 是c 中元素的并。 定理3 4e 是闭包部算子 证明：由性质( 1 ) ，( 2 ) ，( 3 ) ，( 5 ) 可以得到结论。 3 1 1 3 第一种类型覆盖粗糙集近似算子的公理化 定理3 5 2 0 ( 下近似算子的公理化) 设【，是一个非空集合，如果算子 l ：p ( u ) 一p ) 满足下面的性质：对任意工，y c _ u ， ( 1 弘( 功= u ；( 2 谬s y 三( 幻s 三( d ； ( 3 ) 工( 田x ；( 4 ) 工( ) ) = ( 朋 则存在【厂的一个覆盖c ，使得g ( d = 以j d 定理3 6 ( 上近似算子的公理化) 设【，是一个非空集合，如果算子 h ：尸) 专尸( 是一个闭包算子，即日满足下面的性质：对任意x ，y u ， ( 1 ) h ( x u n = h ( x ) u h ( d ；( 2 ) x g ( 幻； ( 3 ) 日印) = 彩：( 4 ) 小日( 朋) = 日( 幻 则存在u 的一个覆盖c 。使得己( j 0 = 日( 。聊 证明：令c = x u p ( x ) = 置 ，由( 2 ) ，日( ，则日( = ，u e c 因此，c 是u 的一个覆盖。对于任意z u ，由( 2 ) ， 对t i l t x ) ，又由( 4 ) ， c ，因此，( 日( 了 ) 。若x y ，由( 1 ) 有，h ( x u y ) ：h ( y ) = 日【的u 日( y ) ，则h ( x ) c h ( y ) 又对任意工足，k e c ，日( 习) 日( 幻 西南交通大学研究生硕士学位论文第1 5 页 = 足，则由邻域的定义，训砖) s ( 力因此，日( 工) ) ；( d 由论域u 的有 限性，得云( 舯= 小肋 3 1 2 第二种类型覆盖粗糙集 定义3 5 设缈，c ) 是覆盖近似空间，x u ，集合g = u k c k 朋称为x 的第二种类型覆盖下近似；集合磊= u n ( x ) ( x ) f l x a 称为x 的第二种类型覆盖上近似。 3 1 2 1 第二种类型覆盖粗糙集的性质 1 9 ，2 1 设( u ，c ) 是覆盖近似空间，对于任意x ，y o u ，有 ( 】) 鸟印) 一磊( 四= a ，( u ) - - 磊( u p = u ； ( 2 ) 幺) j 己； ( 3 ) g ( g ) 咆； ( 4 ) x c ：r j q ( 】，) 己( 柳己( y ) ； ( 5 ) 己僻u y ) = 己( 抑u 互( 功； ( 6 ) 垤c c g 皤) = j l ： 下面的性质一般不成立： 己( 己( 功= 己 例3 2 设u = 口，髓c ，墨= 口，研，恐= 豫d ，c = 墨，局 贝u c i u 的 一个覆盖，且( 口) = 以b ) ，( = 6 ) ，( 力= 6 c ) 令x = d ) ， 磊= u ( “) 似) n 扣 o ) 号( 4 ) = 4 ，b ，磊( 己傅) ) = 磊“4 ，6 ) = n ( a ) u n ( b ) u i v ( c ) = u ，故有己( 己( 删己( 西南交通大学研究生硕士学位论文第1 6 页 3 1 2 2 第二种类型覆盖粗糙集的约简及拓扑性质 定理3 7 ：设q ，c 2 是u 的两个覆盖，如果凰沈耐( g ) = 觑舭f ( c 2 ) ，则 c l 和c 2 生成相同的上近似。 证明：由定理3 2 ( 2 ) 和第二种类型覆盖上近似算子的定义，容易得到证 明。 推论3 1 设g ，c 2 是u 的两个覆盖，如果g 和c 2 生成相同的下近似， 也生成相同的上近似。 定理3 8 n ( x ) ；x e u ) 形成( ，的划分时，己是闭包算子。 证明：f h 2 1 j 的定理2 1 ， n ( x ) ；x e u ) 形成u 的划分当且仅当弓= 磊 又由定理3 4 ，可以得到证明。 3 1 3 第三种类型覆盖粗糙集 定义3 6 设似c ) 是覆盖近似空间，x s u ，集合鸟= u x c 石 称为x 的第三种类型覆盖下近似；集合己) = x e u ( x ) n x o ) 称为 石的第三种类型覆盖上近似。 3 1 3 i 第三种类型覆盖粗糙集的性质 1 9 ，2 1 设，c ) 是覆盖近似空间，对于任意x ，y c _ u ，有 ( 1 ) 鸟( a ) = 己( g ) = o ，g ( 【，) = 己( 【，) = c ，； ( 2 ) g ) s x 己： ( 3 ) g ( 鸟) = ，己( 己) ； ( 4 ) x y j g g ( y ) 己( 柳己( y ) ； ( 5 ) 己( z u d = 弓( 柳u 弓( 功； ( 6 ) v k c 。c 3 僻) = k 西南交通大学研究生硕士学位论文第1 7 页 3 1 3 2 第三种类型覆盖粗糙集的约简及拓扑性质 定理3 9 2 3 设q ，c 2 是，的两个覆盖，如果r e a u c t ( c , ) = r e d u c t ( c 2 ) ， 则g 和c 2 生成相同的上近似 推论3 2 设，c 2 是c ，的两个覆盖，如果q 和岛生成相同的下近似， 也生成相同的上近似。 定理3 1 0 己是闭包算子。 证明：由性质( 1 ) ，( 2 ) ，( 3 ) ，( 5 ) 可以得到结论。 3 i 3 3 第三种类型覆盖粗糙集