（运筹学与控制论专业论文）粗糙集理论在代数系统——群、环上的应用.pdf

摘要 粗糙集理论不但是一种新型的处理模糊和不确定知识的数学工具，而且是 个不完备信息的新颖、有效的软计算方法，目前已在机器学习、知识发现、决策 分析、人工智能、数据挖掘、模式识别、故障检测等方面得到了广泛的应用。同 时，纯粹的数学理论与粗糙集理论结合起来进行研究已有文章出现，并不断有新 的数学概念出现，如“粗糙逻辑”、“半群中的粗理想”、“粗糙陪集”、“粗糙不变 子群”、“粗糙群和粗糙子群”、“粗糙群的同态与同构”。当然，随着粗糙结构与 代数结构、拓扑结构、序结构等各种结构的不断整合，必将不断涌现出新的富有 生机的数学分支。本文根据粗糙结构和代数结构，研究了粗糙集理论在代数系统 群、环上的应用，以此建立比较完善的粗糙代数系统。具体如下： 1 、研究了粗糙集理论在代数系统群上的应用。首先给出了粗糙半群的 定义及其性质，然后在粗糙群和粗糙子群的基础上，进一步研究了粗糙子群的若 干性质，接着在粗糙陪集、粗糙不变子群的基础上，给出了粗糙不变子群的三个 重要性质和粗糙商群的概念，最后在粗糙群同态与同构的基础上，给出了粗糙群 同态基本定理与同构定理。 2 、研究了粗糙集理论在代数系统环上的应用。首先给出了粗糙环的定 义及其性质，其次给出了粗糙子环、粗糙理想、粗糙商环的定义及其性质，最后 研究了粗糙环的同态与同构。 论文分为四章： 第一章对粗糙集理论的研究现状和发展前景进行了介绍。 第二章介绍了粗糙集理论基本知识，如不可分辨关系、基本集、近似空间、 上近似、下近似、负域、边界域、粗糙集等概念，以及粗糙集的代数性质，同时 还介绍了粗糙集理论的特点。 第三章研究了粗糙集理论在代数系统群上的应用。在这一章中，首先重 新给出了粗糙半群的定义，其次在粗糙群、粗糙子群、粗糙陪集、粗糙不变子群 的基础上，给出了粗糙子群的若干性质、粗糙不变子群的三个重要性质和粗糙商 群的定义，最后在粗糙群同态与同构的基础上，给出了粗糙群同态基本定理与同 构定理。 第四章研究了粗糙集理论在代数系统环上的应用。在这一章中，首先给 出了粗糙环的定义及其性质，其次给出了粗糙子环、粗糙理想、粗糙商环的定义 及其性质，最后研究了粗糙环的同态与同构。 关键词：近似空间，粗糙集，粗糙群，同态与同构，粗糙环 i i a b s t r a c t r o u g h s e tt h e o r yi sn o t o n l yan e w m a t h e m a t i c a lt o o ld e a l i n gw i t h v a g u e n e s sa n d u n c e r t a i n t yb u ta l s oan e w a n de f f e c t i v es o f tc o m p u t i n gm e t h o d i tw a sb e e n w i d e l y u s e di nt h ea r e ao fm a c h i n e l e a r n i n g ，k n o w l e d g ed i s c o v e r y , d e c i s i o na n a l y s i s ，a r t i f i c i a l i n t e l l i g e n c e ，d a t am i n i n g ，p a t t e r nr e c o g n i t i o n ，f a u l td i a g n o s i s ，e t c a tt h es a n l et i m e ， s o m ea r t i c l e st h a th a v eb e e ns t u d i e da b o u tt h et h e o r yc o m b i n e d p u r em a t h e m a t i c sw i t h r o u g hs e t sh a v eb e e ne m e r g e d ，a n ds o m en e wm a t h e m a t i c a ln o t i o n s ，s u c ha sr o u g h l o g i c ，r o u g hi d e a li ns e m i g r o u p s ，r o u g hg r o u p sa n dr o u g hs u b g r o u p s ，r o u g hc o s e t s ， r o u g hi n v a f i a n ts u b g r o u p sa n dh o m o m o r p h i s m a n di s o m o r p h i s mo f r o u g hg r o u p s ，a r e i n t r o d u c e d c e r t a i n l y , w i t ht h ei n t e g r a t i o no fr o u g hs t r u c t u r ea n da l g e b r as t r u c t u r e ， t o p o l o g ys t r u c t u r e ，o r d e r s t r u c t u r em a dt h eo t h e rs t r u c t u r e s ，s o m en e wv i t a l m a t h e m a t i c a lb r a n c h e sw i l lb ee m e r g e d a c c o r d i n gt ot h er o u g hs t r u c t u r ea n da l g e b r a s t r u c t u r e ，t h em a i nw o r ki s t o s t u d yt h ea p p l i c a t i o no fr o u g hs e tt h e o r yo na l g e b r a s y s t e m - - g r o u p sa n dr i n g si nt h i st h e s i s s ot h a tr o u g ha l g e b r as y s t e mi s b u i l tb e t t e r p e r f e c t l y t h eg e n e r a lp r o c e s sa sf o l l o w s ： 1 t h em a i nw o r ki st o s t u d yt h ea p p l i c a t i o no fr o u g hs e tt h e o r yo na l g e b r a s y s t e m - - g r o u p s f i r s t l y , t h ed e f i n i t i o na n dp r o p e r t i e so fr o u g hs e m i g r o u p si sg i v e n t h e ns o m e p r o p e r t i e so fr o u g hs u b g r o u p s b a s e do n r o u g hg r o u p sa n dr o u g hs u b g r o u p s a r ei n t r o d u c e d ，a n dt h r e ei m p o r t a n tp r o p e r t i e so fr o u g hi n v a r i a n ts u b g r o u p sa n dt h e c o n c e p t o f r o u g hq u o t i e n tg r o u p s b a s e do n r o u g h c o s e t sa n d r o u g h i n v a r i a n ts u b g r o u p s a r e i n t r o d u c e d s u b s e q u e n t l y , b a s e d o i ls o m e c o n c e p t s o f h o m o m o r p h i s m a n d i s o m o r p h i s mo fr o u g hg r o u p s ，b a s i ch o m o m o r p h i s m t h e o r e ma n di s o m o r p h i s m t h e o r e mo f r o u g hg r o u p s a r ep u tf o r w a r da n dp r o v e d 2 t h em a i nw o r ki st o s t u d yt h ea p p l i c a t i o no fr o u g hs e tt h e o r yo na l g e b r a s y s t e m - - r i n g sf i r s t l y ，t h ed e f i n i t i o na n dp r o p e r t i e so fr o u g hr i n g si sg i v e n t h e n t h e d e f i n i t i o na n dp r o p e r t i e so f r o u g hs u b r i n g s ，r o u g hi d e a la n dr o u g hq u o t i e n tr i n g sa r e p u tf o r w a r da n dp r o v e d f i n a l l y , h o m o m o r p h i s ma n di s o m o r p h i s m o fr o u g hr i n g si s s t u d i e d t h e r ea r ef o u rc h a p t e r si nt h i st h e s i s ： i nc h a p t e r1 ，p r e s e n ts t a t eo fr e s e a r c h e sm a dd e v e l o p m e n tp r o s p e r i t yo f t h er o u g h s e tt h e o r ya r ei n t r o d u c e d i nc h a p t e r2 ，b a s i ck n o w l e d g eo ft h er o u g hs e tt h e o r y , s u c ha si n d i s c e r n i b i l i t y i i i r e l a t i o n ，e l e l n e n t a r ys e t ，a p p r o x i m a t es p a c e ，u p p e ra p p r o x i m a t i o n ，l o w e r a p p r o x i m a t i o n ，n e g a t i v er e g i o n ，b o u n d a r yr e g i o n ，r o u g hs e t ，e t c ，a n da l g e b r a i cp r o p e r t i e so fr o u g h s e ta r ei n t r o d u c e d a tt h es a m et i m e ，t h ef e a t u r eo ft h e r o u g hs e tt h e o r yi s a l s o i n t r o d u c e d i nc h a p t e r3 ，t h ea p p l i c a t i o no fr o u g hs e t st h e o r yt oa l g e b r as y s t e m - - g r o u p si s s t u d i e d i nt h i s c h a p t e r , f i r s t l y , t h ed e f i n i t i o no fr o u g hs e m i g r o u p si sg i v e na f r e s h t h e nb a s e do n r o u g hg r o u p s ，r o u 曲s u b g r o u p s ，r o u g hc o s e t s ，r o u g h i n v a r i a n t s u b g r o u p s ，s o m ep r o p e r t i e so fr o u g hs u b g r o u p sm a dr o u g h i n v a r i a n ts u b g r o u p sa n dt h e c o n c e p to fr o u g hq u o t i e n tg r o u p sa r ei n t r o d u c e d f i n a l l y , b a s e do ns o m ec o n c e p t so f h o m o m o r p h i s m a n di s o m o r p h i s mo f r o u g hg r o u p s ，b a s i ch o m o m o r p h i s m t h e o r e ma n d i s o m o r p h i s m t h e o r e m o f r o u g hg r o u p sa r ep u tf o r w a r d a n d p r o v e d i nc h a p t e r4 ，t h ea p p l i c a t i o no fr o u g hs e t st h e o r yt oa l g e b r as y s t e m - - r i n g si s s t u d i e d i nt h i sc h a p t e r ，f i r s t l y , t h ed e f i n i t i o no fr o u g hr i n g sa n dk sp r o p e r t i e sa r eg i v e n t h e nt h ed e f i n i t i o na n dp r o p e a i e so fr o u g hs u b r i n g s ，r o u g hi d e a l sa n dr o u g hq u o t i e n t r i n g sa r ep u tf o r w a r da n dp r o v e d f i n a l l y , h o m o m o r p h i s ma n di s o m o r p h i s mo f r o u g h r i n g si ss t u d i e d k e yw o r d s ：a p p r o x i m a t es p a c e ，r o u g hs e t ，r o u g hg r o u p s ，h o m o m o r p h i s m a n d i s o m o r p h i s m ，r o u g hr i n g s i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包括其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作过的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 日期：州悔1 月6 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印、或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：彳舯二导师签名：冷产羔 日期：上力扛年，月日 电子科技大学硕士学位论文 第一章引言 粗糙集作为种处理不精确、不确定与不完全数据的新的数学理论。最初是由 波兰数学家z p a w l a k 于1 9 8 2 年提出 1 1 。由于最初关于粗糙集( r o u g hs e t ) 理论( 也 称粗集理论或r s 理论) 的研究大部分是用波兰语发表的，因此当时没有引起国际 计算机学界和数学界的重视，研究领域也仅局限在东欧一些国家，直到2 0 世纪 8 0 年代末才引起各国学者的注意。近几年来，由于它在机器学习与知识发现旺”、 数据挖掘h ，5 1 、决策支持与分析6 ，7 ，8 1 等方面的广泛应用，研究逐渐趋热。1 9 9 2 年 在波兰k i e k r z 召开了第一届国际粗糙集理论研讨会；1 9 9 3 年在加拿大b a n f f 召开 了第二届国际粗糙集理论与知识发展研讨会：1 9 9 6 年在东京召开了第五届国际粗 糙集理论学术会议：2 0 0 1 年五月在重庆召开了中国第一届r o t 【曲集与软计算学 术研讨会。2 0 0 3 年1 0 月在重庆召开了中国第三届r o u g h 集与软计算学术研讨会 和9 t h i n t e r n a t i o n a lc o n f e r e n c eo l lr o u g hs e t s ，f u z z ys e t s ，d a t am i n i n ga n dg r a n u l a r c o m p u t i n g 。1 9 9 5 年a c mc o m m u n i c 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 ) k 丕为粗糙集理论的研究出 版了一期专辑。在中国几乎所有重要的计算机学术期刊均刊登有粗糙集理论的学 术论文。对粗糙集的理论的知识表示与其它处理不确定性问题数学方法的关系， 国内有很多综述报告及四本著作【j “圳。 粗糙集理论是建立在分类机制的基础上的，它将分类理解为在特定空间上的 等价关系，而等价关系构成了对该空间的划分。粗糙集理论将知识理解为对数据 的划分，每一被划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识 库，将不精确或不确定的知识用已知的知识库中的知识来( 近似) 刻画。该理论与 其它处理不确定和不精确问题理论的最显著的区别是它无需提供问题所需处理 的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理可以说是 比较客观的，由于这个理论未能包含处理不精确或不确定原始数据的机制，所以 这个理论与概率论，模糊数学和证据推理等其它处理不确定或不精确问题的理论 有很强的互补性。 1 1 粗糙集理论的研究现状 粗糙集理论的研究由于其历史较短，所以到目前为止，对粗糙集理论的研究 主要集中在：粗糙集模型的推广；问题的不确定性的研究；它处理不确定性，模 第1 页共5 4 页 电子科技大学硕士学位论文 糊性问题的数学理论的关系与互补；纯粹的数学理论方面的研究；粗糙集的算法 研究和人工智能其它方向关系的研究等。这些研究有的是应用的推动而产生，有 的是纯理论的。 1 1 1 粗糙集模型的推广 p a w l a k 粗糙集模型的推广一直是粗糙集理论研究的主流方向，目前主要有两 种方法：( 1 ) 构造性方法；( 2 ) 代数性( 公理化) 方法。 f 1 1 构造性方法是对原始p a w l a k 粗糙集模型的一般推广，其主要思想是从给 定的近似空间出发去研究粗糙集和近似算子。它是以论域上的二元关系或布尔代 数作为基本要素的，然后导出粗糙集代数系统( 2 “，n ，u ，爿) 。这种方法所研究 的问题往往来源于实际，所建立的模型有很强的应用价值，其主要缺点是不易深 刻了解近似算子的代数结构。 在p a w l a k 粗糙集模型中有三个最基本的要素：一个论域u ，u 上的一个二 元等价关系r ( 或划分) ( 它们构成了近似空间) ，一个被近似描述的( 经典) x 。这样， 推广的形式主要也有三个方向，即从论域方向、从关系方向( 包括近似空间) 和从 集合方向。 从论域方向推广的目前只有一种，就是双论域的情形【9 ，当然这时的二元关 系就变成为两个论域笛卡尔乘积的一个子集。对于将论域推广到多个的情形来研 究粗糙集理论的文献还未见到。 关系的推广：一种是将论域上的二元等价关系推广成为任意的二元关系得到 了一般关系下的粗糙集模型【1 0 】：另一种是将对象石所在的等价类看成是x 的一个 领域，从而推广导出了基于领域算子的粗糙集模型【1 1 】；也有将由关系导出的划分 推广成为一般的布尔子代数的，以此出发去定义粗糙集和近似算子【12 j ：更一般 的有将普通关系推广成模糊关系或模糊划分 1 3 ，1 4 ，1 6 1 而获得模糊粗糙集模型。 将集合和近似空间进行推广。这一类的推广是与其它处理不确定，不精确或 模糊的知识f 如概率论，模糊数学，信息论，证据推理等) 结合起来进行研究的。 当知识库中的知识是由于随机原因或经统计得到的，即知识库中的知识很可 能是不确定的，很多学者提出了统计( 或概率) 粗糙集模型 1 7 , 1 8 , 1 9 ，变精度粗糙集 模型【2 明实质l 也可以归入这类模型，寻求具有最小风险的b a y e s 决策问题也可转 化为这类模型2 ”。这一类模型在数据分析的增量式机器学习中有重要应用“。 目前见到的此类模型中，近似空间中二元关系大都是等价关系，对于非等价关系 给出的情形的文章尚未见到。 当知识库中的知识模块都是清晰概念，而被描述的概念是一个模糊概念，人 第2 页共5 4 页 电子科技大学硕士学位论文 们建立了粗糙模糊集模型【2 2 】来解决此类问题的近似推理。当知识库中的知识模块 也是模糊的，有些学者提出了模糊粗糙集模型【2 , 1 2 , 1 4 。 ( 2 ) 代数方法也称为公理化方法有时也称为算子方法，这种方法不是以二元关 系为基本要素，它的基本要素是一对某些公理的元近似算子l h ：2 “一2 “， 即粗糙代数系统( 2 “，n ，u ，厶h ) 中近似算子是事先给定的。这种方法研究的明 显优点是能够深刻地了解近似算子的代数结构，其缺点是应用性不强。 1 1 2 不确定性问题的理论研究 粗糙集理论中知识的不确定性主要由两个原因产生的：一个原因是直接来自 于论域上的二元关系及其产生的知识模块，即近似空间本身，如果二元等价关系 产生的每一个等价类中只有一个元素，那么等价关系产生的划分不含有任何信 息。划分越粗，每一个知识模块越大，知识库中的知识就越粗糙，相对于近似空 间的概念和知识就越不确定，这时处理知识的不确定性的方法往往用香农信息熵 来刻画，知识的粗糙性与信息熵的关系比较密切，知识的粗糙性实质上是其所含 信息多少的更深层次的刻画【翊。单从这个角度来看，粗糙集理论与信息论的关系 就比较密切，不少学者在这方面做了研究工作【2 土”，3 。 粗糙集理论中知识不确定性的另一个原因来自于给定论域里粗糙近似的边 界，当边界为空集时知识是完全确定的，边界越大知识就越粗糙或越模糊。至今， 粗糙集理论刻画概念x 的不确定性用正则条件熵h 。( x 4 l r 。) ( 其中x = x ，一) 是由x 产生的一个划分，r + = ( x ，x 2 ，以) 是由r 产生的一个划分) 和粗糙性 测度p 。( z ) 来实现的。但是这两个度量并没有提供那些完全属于x 的下近似的 区域里面与不可分辨关系的知识粒度有关的不确定性，于是有人引进了粗糙熵 e f x l 的概念来刻画概念盖的不确定性阱“。 1 1 3 与其它处理不确定性方法的理论的研究 在粗糙集理论与其他处理模糊性或不确定性方法的理论研究中，主要集中在 它与概率统计，模糊数学，d s 证据理论( 证据理论是由德普斯特( a p d e m p s t e r ) 首次提出，并由沙佛( g s h a f e r ) 进一步发展起来的用于处理不确定的一种理论。证 据理论( t h ed e m p t e r s h a f e rt h e o r yo fe v i d e n c e ) 也称d s ( d e m p t e r - s h a f e r ) 理- 论) 和 信息论的相互渗透与补充。 在信息系统中，知识库的知识类型一般由两类：一类库中所有对象的描述是 完全已知的，p a w l a k 粗糙集模型和一般二元关系下的粗糙集模型就是属于这一 种：另一类库中的对象的描述只有部分是已知的，即知识库中的知识是不确定的， 第3 页共5 4 页 电子科技大学硕士学位论文 它只能通过训练样本所提供的信息来刻画概念，为了使从训练样本获得的规则符 合整个论域的对象，在抽取样本时应符合统计规律性，粗糙集理论不管这一类工 作，因此概率统计作为研究自然界，人类社会及技术过程中大量随机现象的规律 性的一门学科，它与粗糙集理论的结合就显得非常自然。 粗糙集理论用粗糙隶属函数来刻画知识的模糊性。对于只建立在一般二元关 系月下的近似空间j = ( u ，r ) ，粗糙隶属函数为 ，、陋n r 。( x ) i 蜥 卜莆 其中当r 是等价关系时，r 。( 戈) = 训。在概率近似空间下，粗糙隶属函数为 、 p ( x n r 。( x ) p x ( x ) 2 1 丽 粗糙隶属函数一般不是z m e h 意义下的隶属函数1 7 0 。 模糊集和粗糙集理论在处理不确定性和不精确性问题方面都推广了经典集 合论。虽有一定的相容性和相似性，然而它们的侧重面不同。从知识的“粒度” 的描述上来看，模糊集是通过对象关于集合的隶属程度来近似描述的，而粗糙集 是通过一个集合关于某个可利用的知识库的一对上、下近似来描述的；从集合对 象的关系来看，模糊集强调的是集合边界的病态定义上的，即边界的不分明性， 而粗糙集强调的是对象间的不可分辨性；从研究的对象来看，模糊集研究的是属 于同一类的不同对象间的隶属关系，重在隶属程度，而粗糙集研究的是不同类中 的对象组成的集合关系，重在分类。虽然模糊集的隶属函数和粗糙集的粗糙隶属 函数都反映了概念的模糊性，直观上有一定的相似性，但是模糊集的隶属函数大 多是专家凭经验给出的，因此往往带有很强的主观意志，而粗糙集的粗糙隶属函 数的记算是从被分析的数据中直接获得的，非常直观。也正因为如此，将粗糙集 理论和模糊集理论进行某些“整合”后去描述知识的不确定性和不精确性比它们 各自描述知识的不确定性和不精确性可望显示出更强的功能。目前所见的模糊粗 糙集模型 2 , 1 2 , 1 4 1 是其中的一些成功范例。 1 1 4 算法研究 粗糙集理论中有效算法研究是粗糙集在人工智能方向上研究的一个主要方 向。目前，粗糙集理论中有效算法研究主要集中在导出规则的增量式算法，约简 的启发式算法，粗糙集基本并行算法1 4 m ，以及与粗糙集有关的神经网络与遗传算 法 ：2 5 】等。这些研究的成功应用有的已经获得了商业价值。 第4 页共5 4 页 电子科技大学硕士学位论文 1 1 5 与其它数学理论的联系 随着对粗糙集理论的研究的不断深入，与其它数学分支的联系也更加紧密。 例如，从算子的观点看粗糙集理论，与之关系较紧的有拓扑空间、数理逻辑、模 态逻辑、格与布尔代数、算子代数等；从构造性和集合的观点来看，它与概率论、 模糊数学、证据理论、图论、信息论等联系较为密切。粗糙集理论研究不但需要 虬这些理论作为基础，同时也相应地带动这些理论的发展。 目前，纯粹的数学理论与粗糙集理论结合起来进行研究已有文章出现，并不 断有新的数学概念出现，如“粗糙逻辑1 2 6 , 2 7 】j j 、“半群中的粗理想2 8 】”、“粗糙半群 的性质【4 2 ”、“粗糙陪集m 1 ”、“粗糙不变子群 4 3 k 粗糙群和粗糙子群 2 9 】”、“粗糙 群的同态与同构 4 4 ”。当然，随着粗糙结构与代数结构，拓扑结构，序结构等各 种结构的不断整合，必将不断涌现出新的富有生机的数学分支。 1 2 粗糙集理论的发展前景 粗糙集理论作为一种处理含糊和不精确性问题的新型数学工具。对于当今现 代计算机的应用来说，这种理论无疑是最有挑战性的领域之一。它自问世以来， 无论是在理论或应用上都是一种新的最重要的并且是迅速发展的一门既有理论 又有应用的研究领域。对于人工智能和认知科学似乎也是十分重要的，尤其在机 器学习、知识获取、决策分析、数据库的知识发现、专家系统、归纳推理、矛盾 归结、模式识别、决策支持系统、模糊控制及其他各个方面的应用，粗糙集理论 都为之提供了一种很有效的新的数学方法。同时，粗糙集理论处理的主要问题包 括数据库中的数据约简、数据相关性的发现、数据意义的评估、由数据产生决策 控制算法、数据的近似分类、数据中的相似性或差异性的发现、数据中范式的分 析以及因果关系的发现。特别地，粗糙集方法在医学、药学、银行、商业、金融、 市场研究、工程设计、气象学、振动分析、开关函数、冲突分析、图像处理、声 音识别、并发系统分析、决策分析、字符识别及其他领域都有重要的应用。可以 预言，粗糙集方法将在数据挖掘和软计算，特别是处理大型数据库和复杂问题等 方面，必将显示出“英雄有用武之地”的气魄。 1 3 粗糙群、粗糙环的理论研究 众所周知，具有一个二元运算的代数系统半群与群，不但是自然科学许 多领域的理论基础，而且在应用科学中也有广泛应用。例如，在自动机理论中就 用到半群，群；在信息安全与编码理论中就用到群。而对于具有两个二元运算的 第5 页共5 4 页 电子科技大学硕士学位论文 代数系统环，不但在编码理论的研究中有很多应用，而且在计算机和时序机 的研究中也有很多应用。因此，我将粗糙集理论与代数系统群、环理论结合 起来进行研究，更进一步研究粗糙群，并将研究粗糙予群、粗糙不变子群的性质、 粗糙商群、粗糙群同态基本定理与同构定理等，进而研究粗糙环、粗糙子环、粗 糙环的同态与同构、粗糙理想等的定义及其性质，以此建立比较完善的粗糙代数 系统。 第6 页共5 4 页 电子科技大学硕士学位论文 第二章粗糙集理论基础及其特点 粗糙集理论的研究已经历了2 0 余年的时间，无论是在系统理论、计算模型 的建立和应用系统的研制开发上，都已取得了很多成果，也建立了一套较为完善 的粗糙集理论体系。在本章中，首先，我将介绍粗糙集理论的产生与发展和所处 理的主要问题，其次介绍粗糙集理论的一些基本概念，对其基本概念如知识、不 可分辨关系、基本集、上近似、下近似、正域、负域、边界域进行分析，然后对 定义在粗糙集上的代数运算的性质进行介绍，最后给出粗糙集理论的特点和一个 用粗糙集理论的基本概念分析问题的一个实例。 2 1 粗糙集理论 2 1 1 粗糙集理论的产生与发展 在本世纪7 0 年代，波兰学者z p a w l a k 和些波兰科学院、波兰华沙大学的 逻辑学家们，一起从事关于信息系统逻辑特征的研究。粗糙集理论就是在这些研 究的基础上产生的。1 9 8 2 年，z p a w l a k 发表了经典论文r o u g h s e t 【lj ，宣告了粗 糙集理论的诞生。此后，粗糙集理论引起了许多数学家逻辑学家和计算机研究人 员的兴趣，他们在粗糙集的理论和应用方面做了大量的研究工作。1 9 9 1 年z p a w l a k 的专著 8 1 和1 9 9 2 年应用专集 9 1 的出版，对这一段时期理论和实践工作的成 果作了较好的总结，同时促进了粗糙集在各个领域的应用。此后召开的与粗糙集 有关的国际会议进一步推动了粗糙集的发展。越来越多的科技人员开始了解并准 备从事该领域的研究。 2 1 2 粗糙集理论所处理的主要问题 粗糙集能有效地处理下列问题： f 1 1 数据库中的数据约简； ( 2 ) 数据相关性的发现； ( 3 ) 数据意义的评估； ( 4 ) 数据产生决策控制算法； 岱) 数据的近似分类； ( 6 ) 数据中的相似性或差异性的发现； ( 7 ) 数据中范式的发现以及因果关系的发现。 第7 页共5 4 页 电子科技大学硕士学位论文 2 1 3 粗糙集理论的一些基本概念 2 ，1 3 1 知识的含义 “知识”这个概念在不同的范畴内有多种不同的含义。在粗糙集理论中，“知 识”被认为是一种分类能力嘲。人们的行为是基于分辨现实的或抽象的对象的能 力，如医生给病人诊断，必须辨别出患者得的是哪一种病。这些根据事物的特征 差别将其分门别类的能力均可以看作是某种“知识”。 2 1 3 2 不可分辨关系与基本集 分类过程中，相差不大的个体被归于同一类，它们的关系就是不可分辨关系 ( i n d i s c e m i b i l i t yr e l a t i o n ) 。假如只用两种黑白颜色把空间中的物体分成两类： 黑 色物体) 、 白色物体) ，那么同为黑色的两个物体就是不可分辨( i n d i s c e r n i b l e ) 的， 因为描述它们特征属性的信息相同，都是黑色。如果再引入方、圆的属性，又可 以将物体进一步分为四类： 黑色方物体 、 黑色圆物体 、 白色方物体 、 白 色圆物体) ，这时，如果两个同为黑色圆物体，则它们还是不可分辨的。不可分 辨关系也称为个等价关系( e q u i v a l e n c er e l a t i o n s h i p ) ，两个黑色圆物体间的不可 分辨关系可以理解为它们在黑、圆两种属性下存在等价关系。 基本集( e l e m e n t a r ys e t ) 定义为由论域中相互问不可分辨的对象组成的集合， 是组成论域知识的颗粒( g r a n u l e ) 。不可分辨关系这一概念在粗糙集理论中十分重 要，它深刻地揭示出知识的颗粒状结构( g r a n u l es m t c t u r e ) ，是定义其它概念的基 础。知识可认为是一簇等价类( e q u i v a l e n c ec l a s s ) ，它将论域分割成一簇等价类。 2 1 3 3 集合的下近似、上近似、负域和边界域 粗糙集理论延拓了经典的集合论，把用于分类的知识嵌入集合内，作为集合 组成的一部分。一个对象a 是否属于集合x 需根据现有的知识来判断，可分为三 种情况： ( 1 ) 对象以肯定属于集合x ； ( 2 ) 对象a 肯定不属于集合x ； ( 3 1 对象n 可能属于也可能不属于集合。 集合的划分密切依赖于我们所掌握的关于论域的知识，是相对的而不是绝对的。 设u 是非空集合称为论域r 是 ，上的一簇等价关系，即关于u 的知识，刚 序对s = ( u ，r ) 称为近似空间。v ( x ，y ) u x u ，若( e y ) r ，则称对象x 和y 在 近似空间s = ( u ，r ) 中是不可分辨的。u r 是u 上由r 生成的等价类全体，它构 成了u 的一个划分。u r 中的集合称为基本集或原子集。若将u 中的集合称为 第8 页共5 4 页 电子科技大学硕士学位论文 概念或表示知识，则s = ( u ，月) 称为知识库，原子集表示基本概念或知识模块。 任意有限的基本集的并和空集均称为可定义集，否则称为不可定义的。可定义集 也称为精确集，它可以在知识库中被精确地定义或描述，可表示已知的知识。 对于论域u 上任意一个子集工( x 痧) ，x 不一定能用知识库的知识来精确 地描述，即爿可能为不可定义集，这时就用x 关于s = ( 【，r ) 的一对下近似4 ( x ) 和上近似a ( x ) 来“近似”地描述，其定义如下： 定义2 1 3 3 1 令s = ( u ，r ) 是一个近似空间，假设z u ，则 4 ( z ) = x i f _ v l c x 。x ) ， 4 ( 誓) = x u k 工 。n x ) 分别称为彳在近似空间s = ( u ，五) 中的下近似和上近似。其中 x 。是x 所在的 r 一等价类。 下近似4 ( x ) 也称作关于s 的正域，记作p n 9 ( x ) ，它可以解释为由那些 根据现有知识判断出肯定属于互的对象所组成的最大集合，上近似x ( x ) 可以解 释为由那些根据现有知识判断出可能属于x 的对象所组成的最小集合。u a x 称作关于s 的负域，记作n e g ( x ) ，它可以解释为由那些根据现有知识判断出 肯定不属于x 的对象所组成的集合。b n ( x ) = a ( x ) 一4 ( z ) 称作x 的边界域 ( 简称边界) ，它可以解释为由那些根据现有知识判断出可能属于x 但不能完全 肯定是否一定属于x 的对象所组成的集合。显然，下近似4 ( x ) 是s 中含在x 中 的最大可定义集，而上近似j ( 彳) 是s 中包含x 的最小可定义集。因此，x 是可 定义集当且仅当( x ) = a ( x ) ；x 是不可定义集当且仅当鱼x ) 爿( x ) 。称 a ( x ) = ( ( ) ，爿( x ) ) 为x 在近似空间s = ( v ，r ) 中的粗糙集。显然，对于一个固定的近似空间 s ：( u ，r ) 和x u ，则a ( x ) 是唯一的。称 ( 彳) = l a x ) i i a ( x ) i 为由等价关系r 定义的x 关于s 的近似精度，近似精度反映了根据现有知识对石 的了解程度。其中防【表示集合z 的基数。 显然o 口。( x ) l 。如果口。( x ) = 1 ，则称集合卫相对于r 是清晰的( c r i s p ) 的：如果口。( x ) 1 ，则称集合z 相对于j r 是粗糙的。( x ) 可认为是在等价关 系尺下逼近集合x 的精度。 定义2 1 3 ，3 。2 令4 = ( 厶j ) 和b = ( 璺百) 是近似空间s = ( u ，r ) 的任意两个 粗糙集，则 ( 1 ) a u b = ( a u 旦，a u b ) ； ( 2 ) 4 n b = ( n 旦，a f l b ) ； 第9 页共5 4 页 电子科技大学硕士学位论文 ( 3 ) a b 的充要条件是爿n b = a ； ( 4 ) 一4 = 一4 ，u 一4 ) ，这里一a 叫做彳在s = ( u ，r ) 中的粗糙补； ( 5 ) a b = a n ( 一b ) = ( 4 一一b ，一a 垦) 。 2 14 粗糙集的代数性质 与初等集合论相似，上近似集和下近似集也有一些类似的代数性质，这里作 一个简单介绍。 性质2 1 4 1 a ( x ) x a ( x ) 。 证明：设x a ( x ) ，则有【z 。z ；而x x 】。，所以x x 。因此4 ( x ) x 。 又设x x ，【x 。n x ，所以x a ( x ) 。因此互a ( x ) 。故 4 ( r ) 至x 4 ( y ) 。 性质2 1 4 2 4 ( 庐) = a ( o ) = ，( u ) = a ( u ) = u 。 证明：由性质2 1 4 1 知，4 ( 矽) 兰驴，而4 ( ) ，因此( 矽) = 妒；假设 爿( 妒) 妒则存在x 使得x a ( o ) ，即 x 。n 庐，而【x 。n = ，这与假设矛 盾，因此4 ( 驴) = 。故 ( ) = 4 ( ) = 妒。 又由性质21 4 1 知，a ( u ) u ：又因为当x u ，有b 】。u ，所以 x 4 ( u ) ，即u e ( u ) ，因此( u ) = u 。再由性质2 1 4 1 知，u 量爿( u ) ，但 a ( u ) u ，因此4 ( u ) = u 。故 4 ( u ) = 4 ( u ) = u 。 生质2 1 4 3 a ( x u y ) = a ( x ) u 爿( i ，) 。 证明：x a ( x u y ) 铸【x 。n ( x u y ) ( z 。n ) u ( b 。n y ) 铮 x 。n x 驴v x 】 n 】，矽 xe 4 ( 肖) v x 4 ( y ) 曹x a ( x ) u a ( y ) ， 因此 a ( x u 王r ) = a ( x ) u 爿( y ) 。 。l 生质2 1 4 4a ( x u y ) = ( y ) u 4 ( 】，) 。 证明：x 4 ( x u y ) 甘m 。僻u y 1 ( i x 。x ) ( x 。n y ) 营x ( z ) n a ( r ) ， 因此 第1 0 页共5 4 页 电子科技大学硕士学位论文 4 ( u y ) = 4 ( x ) u ( y ) 。 性质2 1 4 5x y = 4 ( y ) ( y ) 。 证明：设盖兰y ，则x n y = x ，所以a ( x n y ) = 4 ( x ) 。由性质2 1 4 4 知， 4 ( x ) n 4 ( y ) = ( x ) ，因此4 ( x ) ( y ) 。故 。y y = 4 ( 。r ) ( y ) 。 1 l 生质2 1 4 6x y = ，a ( x ) 一( 】，) 。 证明：设x y ，则x u y = y ，所以a ( x u y ) = 4 够) 。由性质2 1 4 3 知， a ( x ) n a ( r ) = a ( x ) ，因此a ( x ) 爿(