（计算机软件与理论专业论文）基于泛系拓扑的粗糙集模型与插入排序研究.pdf

摘要 对一个问题进行拓展研究，首先要找到该问题的相对性因子，对 相对性因子泛化，然后再用泛系方法论中的泛导思想，构造该问题的 新模型。本文从泛系的角度对粗糙集模型的拓展研究就是基于这种思 想。 7 首先，通过对泛系理论中泛系拓扑的研究，根据泛系拓扑与粗糙 集近似的相似性即从内、外逼近某对象，提出了基于泛系拓扑的粗糙 集模型；决策表属性约简是粗糙集的主要内容之一，本文从泛系拓扑 的角度对决策表属性约简也做了研究，提出一套判断决策表是否相容 和求取决策表属性约简的新方法。 其次，基于泛系拓扑的定义，本文定义了泛权场拓扑，其中引入 了元素语义，使问题变得更清晰；通过对泛权场拓扑的进一步研究， 提出基于泛权场拓扑的粗糙集模型；本文从泛权场拓扑的角度对决策 表属性约简也做了研究，提出一套判断决策表是否相容和求取决策表 属性约简的新方法。 最后，基于对泛系拓扑的研究，由某泛序系统下某元素的上、下 逼近，联系到某线序系统下某元素的插入。通过引入偏序宏观序而将 线性序下的插入，拓展到任何序下的插入，并给出了在任何序下插入 的一般算法。另外，通过插入还可以构造拓扑结构。 关键词：粗糙集理论；泛系理论；泛系拓扑；泛权场拓扑；插入 排序；宏观序 i l a b s t r a c t i no r d e rt os t u d yo rg e n e r a l i z eo n ep r o b l e m ，f i r s t , f i n dt h er e l a t i v i t yf a c t o ro ft h e p r o b l e m g e n e r a l i z et h er e l a t i v i t yf a c t o r , t h e n l l s et h ep a n t r a n s m i t t i n go fp a n s y s t e m s m e t h o d o l o g y , c o n s t r u c tn e wm o d e lo ft h ep r o b l e m b a s e do nt h i st h o u g h t ，t h i sp a p e r d o e se x p a n d i n gr e s e a r c ho f r o u g hs e tf o r mt h ev i e wo f p a n s y s t e m s f i r s t ，b yd o i n gr e s e a r c ho fp a n s y s t e mt o p o l o g y , a c c o r d i n gt ot h es i m i l a r i t yo f p a n s y s t e mt o p o l o g ya n dr o u g hs e ta p p r o x i m a t i o n , t h a ti sa p p r o a c h i n ga l lo b j e c tf o r m i n n e ra n do u t e r , p u tf o r w a r dr o u g hs e tm o d e lb a s e do np a n s y s t e mt o p o l o g y ；d e c i s i o n t a b l ea t t r i b u t er e d u c t i o ni so n em a i nc o n t e n to fr o u g hs e tt h e o r y , t h i sp a p e rf r o mt h e v i e wo fp a n s y s t e mt o p o l o g yd o e sr e s e 艰：lo fd e c i s i o nt a b l ea t t r i b u t er e d u c t i o n , p u t f o r w a r dan e wm e t h o df o rj u d g i n gw h e t h e rad e c i s i o nt a b l ei sc o n s i s t e n t ，a l s op u t s f o r w a r dan e wm e t h o df o rd e c i s i o nt a b l ea t t r i b u t er e d u c t i o n s e c o n d ，b a s e do nt h er e s e a r c ho f p a n s y s t c m st o p o l o g yo f p a n s y s t e m st h e o r y , t h i s p a p e rd e f i n e sp a n w e i g h t e df i e l dt o p o l o g y , i nw h i c hw ei n t r o d u c es e m a n t i c so f e l e m e n t ，w h i c hm a k e st h eq u e s t i o n se v e nm o r ec l e a r f u r t h e rs t u d yo np a n w e i g h t e d f i e l dt o p o l o g y , t h i sp a p e rp u t sf o r w a r dr o u g hs e tm o d e lb a s e do np a n w e i g h t e df i e l d t o p o l o g y d e c i s i o nt a b l ea t t r i b u t er e d u c t i o ni so n em a i nc o n t e n to fr o u g hs e tt h e o r y , t h i sp a p e rf o r mt h ev i e wo f p a n w e i g h t e df i e l dt o p o l o g yd o e sr e s e a r c ho f d e c i s i o nt a b l e a t t r i b u t er e d u c t i o n , p u t sf o r w a r dan e wm e t h o do f j u d g i n gw h e t h e rad e c i s i o nt a b l ei s c o n s i s t e n t ，a l s op u t sf o r w a r dan e wm e t h o do f d e c i s i o nt a b l ea t t r i b u t er e d u c t i o n f i n a l l y , b a s e do nt h er e s e a r c ho f p a n s y s t e m st o p o l o g y , b yt h eu p p e ra p p r o x i m a t i o n a n dl o w e ra p p r o x i m a t i o no fp a n s y s t e m st o p o l o g y , w ec o n t a c ti n s e r tt a x i so v e rl i n e a r o r d e rs y s t e m b yi n t r o d u c i n gp a r t i a lm a c r oo r d e r e x p e n di n s e r tt a x i sw h i c hi st r u e o v e rl i n e a ro r d e rt oa n yo r d e r , p u tf o r w a r dag e n e r a li n s e r ta r i t h m e t i c i na d d i t i o n , w e c a nc o n s t r u c tt o p o l o g yb yi n s e r t i n g k e y w o r d ： r o u g hs e tt h e o r y , p a n s y s t e m at h e o r y ，p a n s y s t e m st o p o l o g y , p a n w e i g h t e df i e l dt o p o l o g y , i n s e r tt a x i s ，m a c r oo r d e r 1 1 1 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立进行研究所 取得的成果。学位论文中凡引用它人已经发表或未发表的成果、数据、观点等， 均已明确注明出处。除文中已经注明引用的内容外。不包含任何其他个人或集体 已经发表或撰写过的科研成果。对本文的研究成果做出重要贡献的个人和集体， 均已在文中以明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：蕉渔燕日期：丝翌垒妇a l 目 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归属兰州大 学。本人完全了解兰州大学有关保存、使用学位论文的规定，同意学校保存或向 国家有关部门或机构送交论文的纸质版和电子版，允许论文被查阅和借阅；本人 授权兰州大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用任何复制手段保存和汇编本学位论文。本人离校后发表、使用学位论文或 与该论文直接相关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：莲! 淦篮导师签名：至至；l 扫期；坌翌z 苎：曼1 兰卅f 大学硕士学位论文 1 绪论 1 1 论文主要研究内容 论文研究内容主要有基于泛系3 2 j 7 j 8 3 9 , 4 1 1 拓扑的粗糙集模型研究和基于泛系 拓扑的直接插入排序3 6 1 研究两大部分。第一部分的内容包括以下两项： 1 ) 通过对泛系拓扑的研究，根据泛系拓扑与粗糙集近似的相似性即从内、 外逼近某对象，提出基于泛系拓扑的粗糙集模型；决策表属性约简是租 糙集的主要内容之一，本文从泛系拓扑的角度对决策表属性约简也做了 研究，提出一套判断决策表是否相容和求取决策表属性约简的新方法。 2 ) 基于泛系拓扑的定义，本文定义了泛权场拓扑，其中引入元素语义，使 问题变得更清晰；通过对泛权场拓扑的进一步研究，提出基于泛权场拓 扑的半r 糙集模型：本文从泛权场拓扑的角度对决策表属性约简也傲了研 究，提出一套判断决策表是否相容和求取决策表属性约简的新方法。 第二部分内容主要包括： 基于对泛系拓扑的研究，由某泛序系统下某元素的上、下逼近，联系到某线 序系统下某元素的插入。通过引入偏序宏观序而将线性序下的插入，推广到任何 序下的插入，并给出在任何序下插入的一般算法。另外，通过插入还可以构造拓 扑结构。 1 2 论文研究的目的、意义 1 ) 出于z ，p a w l a k 的粗糙集模型的要求比较苛刻，适用范围比较小，因此有 必要对其进行推广研究，本文基于泛系拓扑对粗糙集模型进行推广。 在p a w l a k 粗糙集模型中有三个最基本的要素：论域u ；u 上的等价关系r ( 它们构成了近似空间) ：被近似对象( 经典集) x 。因而，推广的形式也主要 有三个方向，即从论域方向、从关系方向( 包括近似空间) 和从集合方向。 从论域方向推广的目前只有一种，就是双论域的情形，这时的二元关系就变 成为两个论域笛卡尔乘积1 3 5 】的一个子集。 关系的推广：将论域上的二元等价关系推广成为任意的二元关系，从而得到 绪论 了一般关系下的粗糙集模型1 3 1 ；将对象x 所在的等价类看成是x 的一个邻域，从 而得到基于邻域算子的粗糙集模型【4 l ；用相容关系代替等价关系，从而得到基于 相容关系的粗糙集模型【3 3 2 1 2 2 4 2 - 3 朋1 ；用支配关系代替等价关系，从而得到基于 支配关系的粗糙集模型【2 3 1 ：也有将由关系导出的划分推广成为一般的布尔子代数， 以此出发去定义粗糙集和近似算子1 5 】；更一般的有将普通关系推广成模糊关系或 模糊划分 6 - 9 1 ，而获得模糊粗糙集模型。 集合和近似空间的推广：这一类的推广是与其他处理不确定，不精确或模糊 的知识( 如概率论、模糊数学、信息论、证据理论等) 结合起来进行研究的。当知 识库中的知识是由于随机原因或经统计得到的，即知识库中的知识很可能是不确 定的，很多学者提出了统计( 或概率) 粗糙集模型i o - 1 2 1 ，变精度羊h 糙集模型【j 3 1 实质 上也可以归入这类模型，寻求具有最小风险的b a y e s 决策问题4 】也可转化为这类 模型。这一类模型在数据分析的增量式机器学习中有重要应用【”1 。目前见到的此 类模型中，近似空问中二元关系大都是等价关系，对于非等价关系给出的情形也 有学者在研究。 当知识库中的知识模块都是清晰概念，而被描述的概念是一个模糊概念，人 们建立了粗糙模糊集模型【1 6 1 来解决此类问题的近似推理。当知识库中的知识模块 也是模糊的，有些学者提出了模糊粗糙集模型i s t 。 2 ) 插入排序要求在线性序下进行，但现实中有各种各样的序，如何在各种 序下进行插入? 本文通过引入宏观序而将线性序下的插入推广到任何序下的插 入。 i 3 论文研究总体思路 对事物进行拓展研究，首先要找到该事物的相对性因子，对相对性因子进行 各种泛化，再联系到泛系中的泛导思想，由辩异同【3 9 i ，运泛极口9 1 原则的观察过 程等泛系概念，来看事物的发展。 本文对粗糙集理论及插入排序的研究，都是基于这种思想。首先，讨论了基 于泛系拓扑的粗糙集模型及决策表属性约简：其次讨论了基于泛权场拓扑的粗糙 集模型和决策表属性约简；最后讨论了基于泛系拓扑的插入排序。 2 兰州太学硕上学位论文 1 4 论文创新点 1 ) 通过对泛系拓扑的研究，给出并空自j 的概念，提出基于泛系拓扑的粗糙 集模型，并给出一套判断决策表是否相容和求取决策表属性约简的新方 法。 2 ) 基于泛系拓扑定义了泛权场拓扑，其中引入元素语义，使问题变得更清 晰；通过对泛权场拓扑的进一步研究，提出基于泛权场拓扑的粗糙集模 型，并给出一套判断决策表是否相容和求决策表属性约简的新方法。 3 ) 基于对泛系拓扑与插入排序相似性的分析，将泛系拓扑引入到插入排序 当中，通过求某线序下元素的上、下逼近来确定元素的插入位置。引入 偏序宏观序而将线序下的插入，推广到任何序下的插入，给出在任何序 下插入的般算法。另外，通过插入还可以构造拓扑结构 3 粗糙集与拓扑结构泛系观 2 粗糙集与拓扑结构泛系观 2 1 泛化1 3 9 i 对一个问题进行拓展研究，首先要找到该问题的相对性因子3 9 l ，对相对性因 子进行各种泛化，然后再用泛导【3 9 】思想，构造该问题的各种新模型。 例2 1圆的泛化：在平面上，圆心“o ”和半径“r ”唯一确定一个圆，因 此圆心“0 ”和半径“r ”是圆的相对性因子，将圆表示为圆( o ，r ) ，下面对 圆心“o ”和半径“r ”进行各种泛化，得到圆的各种新模型： 1 1 圆在平面上的泛化 对圆心泛化，圆心由点泛化为点集合 。一 圆同心圆 图2 1 圆心的泛化 f i 9 2 ig e n e r a l i z a t i o nt h ec e n t r eo f ac i r c l e 对半径泛化，圆泛化为椭圆 。一。 圆( o ，r )椭圆( o ，r l 。r 2 ) 图2 2 半径的泛化 f i 9 2 2g e n e r a l i z a t i o nt h es c m i d i a m c t e r 当r i = r 2 时，椭圆退化成圆。 2 ) 将圆从平面泛化到空闻 圆泛化为球 圆泛化为圆锥 。一 平面( _ 二维) 圆空间( 三维) 球 图2 3 平面到空间的泛化( 一) f i 9 2 3g e n e r a l i z a t i o nf r o mp l a n et os p a c e ( o n e ) 4 兰州大学硕士学位论文 。一台 平面( 二二维) 圆空间( 三维) 圆锥 图2 4 平面到空间的泛化( 二) f i 9 2 4g e n e r a l i z a t i o nf r o mp l a n et os p a c e ( t w o ) 对圆心泛化，由点泛化为球( 可能不规则) o 一 平厦( 二维) 圆空间( 三维) 同心球 图2 5 平面到空间的泛化( 三) f i 9 2 5g e n e r a l i z a t i o nf r o mp l a n et os p a c e ( t h r e e ) 对半径泛化，泛化为椭球 o 一 平面( 二维) 圆( o ，r ) 空间( 三维) 椭球( o ，r 1 。r 2 r 3 ) 图2 6 平面剑空间的泛化( 四) f i 9 2 6g e n e r a l i z a t i o nf r o mp l a n et os p a c e ( f o u r ) 可以看出，对圆这个最基本的图形的相对性因子圆心“0 ”和半径“r ”进 行各种泛化，能够泛化出各种各样的规则的和不规则的图形，有平面上的也有空 问上的：同理，其他的基本图形也可以对其相对性因子泛化，泛化出各种各样的 规则的和不规则的图形。因此在处理具体问题的时候，根据需要对问题进行各种 泛化，达到处理问题的目的。 从| j i 面的论述，我们知道圆的相对性因子是圆心“o ”和半径“r ”，因此圆 在计算机中的存储以及对圆的各种操作，只需对相对性因子圆心“0 ”和半径“r ” 存储或操作即可，即： 圆台玲( o ，r ) 存储圆存储( 0 ，r ) 操作圆操作( 0 ，r ) 因此有了相对性因子，任何物体在计算机中的存储，只存储其相对性因子， 对物体的操作也转化为对相对性因子的操作。做图工具c a d 就是一个很好的例 子，c a d 做图可以看成是对基本图形的相对性因子进行各种泛化，也可以看成 对这些相对性因子进行各种操作，从而得到各种各样的图案。 5 粗糙集与拓扑结构泛系观 2 2 粗糙集的拓展思路 2 2 1 粗糙集的泛系思维过程 对于知识库k ( u ，r ) ，其中u 是论域，r 是u 上的知识，任意集合u ， 如何求x 的r 上、下逼近? 下面采用泛系图形化的思维来看粗糙集的求解过程，如图2 7 。 从图2 7 可以看出，对于给定的论域u ，粗糙集的相对性因子是知识r 和集 合x 。因为知识r 和集合x 变了，观察结果就会变，如当r 变为相容关系时， 就要用相容关系下的粗糙集模型 3 3 1 来求解；当变为一般关系时，就要用一般关系 下的粗糙集模型1 3 1 来求解。当集合x 变化时，观察结果也会变。 从异同【3 9 】和极端1 3 9 l 的角度看，在求足( x ) 、r - ( x ) 时，又是求p ( u r ) - 擀 x 的最大同、最小异。当知识r 由等价关系变为相容关系，变为一般关系时， 怎么样泛化p ( u r ) 与集合x 的最大同、最小异到相容关系，一般关系的最大同、 最小异。这就是对粗集的发展。 计算观察结果的公式怎么变，相应的观察结果怎么变，这就是变化思想即泛 导思想。 尺一( x ) 、尺一( x ) 、b n r ( x ) 是r 作用于集合x 的结果，也可看作是主体知识对 观察对象的观察结果，观察结果是果，知识r 是观察结果的原因。 这里的泛系思想是用图形思维及哲理思维，很容易找出泛系谈的相对性因 子，对相对性因子泛化，再联系到泛系中的泛导思想，由辩异同【3 9 l ，运泛极【3 9 1 原则的观察过程等泛系概念，来看粗集的发展。 6 兰州大学硕士学位论文 r u 足( z ) 置一( 如j ( 观察结果：足( d u ( r eu r ：y g 动 黑颜色部分 j r ( z ) 一u ( j ，eu i r ：y n z ，回 蓝硕色部分 地( 西，j r ( d 一足( d 红颜色部分 图2 7 粗糙集的泛系图形化思维 f i 9 2 7t h ep a n s y s t c m sg r a p h i c a lt h i n k i n go f r o u g hs e t 7 粗糙集与拓扑结构泛系观 2 2 2 粗糙集的拓展思路 对事物进行拓展研究，首先要找到孩事物的相对性因子，对相对性因子进行 各种泛化，再联系到泛系中的泛导思想，由辩异同【3 9 i ，运泛极【3 9 i 原则的观察过 程等泛系概念，来看事物的发展。 粗糙集理论有三个因素，论域u ，论域u 上的知识r 和被逼近对象x 。粗糙 集的相对性因子为论域u ，论域u 上的知识r 和被逼近对象x 。对论域u ，论 域u 上的知识r 和被逼近对象x 进行各种泛化，得到粗糙集的各种模型，这就 是对粗糙集的发展。 本文从泛系的角度，基于对泛系拓扑的研究，用图形化的思维和哲理思维对 粗糙集理论进行拓展研究。 2 3 拓扑结构泛系观 定义2 1广义系纠3 7 1 ：有序对s = ( a ，b ) 是广义系统，其中a 是广义硬件， b 是广义软件。 定义2 2 泛系拓扑跚：设s = ( a ，1 3 ) ，b c _ a 2 是一个泛序系统，x a ，h c a ， 1 ) x ( i n t e r i o r , h ) = ) ( ( 1 e f t l i m i t ，h ) - - x ( 1 0 w e r l i m i t , h ) = m a x t it h ，( t ，x ) b = t ft e l l ，( t ， x ) b ，v t c h ，( t ，t ) e bi m p l i e st = t o r1 j t h ，s u c ht h a t ( t ，t ) b 2 ) x ( e l o s u r e ，h ) - - x ( r i g h t l i m i t , h ) - - x ( u p p e r l i m i t ，h ) = m i n t lt e l l ，( x ，t ) b = t i t e l l ，( x ，0e b ，v t e h ，( t ，t ) bi m p l i e st - i o r j t h ，s u c ht h a t ( t ，t ) b 3 ) 假设i - i a ，则x n e x ( i n t e r i o lh n ) ，x n ”e x ( c l o s u r e ，h n ) ，x n = ( x n ，x n ”) 1 ) 、2 ) 、3 ) 分别定义了x 的b 下逼近、上逼近和夹逼近。 定义2 3 子拓扑( 拓扑结构的限定) ：拓扑结构 ，h c _ u ，如果 h ， - - 是拓扑结构 的子拓扑，当且仅当v x ，y e l l ，如果x y ，则x 是自然数拓扑空间，设 是拓8 b 空f q 的限 定，如图2 8 5 i l 2 图2 8 线序 f i 9 2 8l i n e a ro r d e r 根据泛系拓扑的定义，在限定上求x = 3 的上、下逼近? x ( i n t e r i o r , h ) = m a x t it e l l ，t h x _ 2 x ( c l o s u r e ， d = m i n t lt e l l ，x h t ) 叫 求得x = 3 的上、下逼近分别为4 和2 ，它们是唯一的。 由此联系到插入排序，插入排序【3 6 i 的基本思想：在某线性序的限定下，求比 被插入元素小的元素中最大的和比被插入元素大的元素中最小的，将被插入元素 插入到最大的和最小的之间，即确定被插入元素的插入位置。因此，联系泛系拓 扑的定义，可以通过求元素的上、下逼近来确定元素的插入位置。 2 3 2 元素是集合+ 包含关系 p ( u ) ， 元素与集合间的属于关系，诱导出集合之间的包含关系。 设论域u ，则可以求u 的幂集p ( u ) ，p ( u ) 上存在包含关系“”，因此 可以构造拓扑结构 。 在拓扑结构 上，根据泛系拓扑的定义，可以求集合x e u 的上、 下逼近。可进行如下操作： 1 ) 由子集合x 在拓扑结构 上的上、下逼近可能不唯一，不能直接 做插入。可引入偏序宏观序，然后再做插入。 2 ) 粗糙集也是求集合x 的上、下逼近，给定论域u 和u 上的知识r ，集合x 的上、下近似实际上是某些知识块的并，故引入知识r 的并空间h 即知识 块的任意并。n 构成原拓扑结构 的子拓扑，在该子拓 9 粗糙集与拓扑结构泛系观 扑下求粗糙集近似。 2 3 3 元素是划分+ 细分关系 集合之自j 的包含关系诱导出关系之间的细分关系。 设论域u ，则可以求u 的所有划分p ( u 2 ) ，p ( u 2 ) 上存在细分关系“”，因此 可以构造拓扑结构 。 在拓扑结构 上，根据泛系拓扑的定义，可以求划分r 的上、下逼 近。可进行如下操作： 1 ) 划分r 在拓扑结构 上的上、下逼近可能不唯一，可以构造拓扑 结构 的偏序宏观序，使其上、下逼近唯一，再做插入。 2 ) 粗糙集中决策表属性约简：条件属性或条件属性的并决定的划分如果细分决 策属性决定的划分，则条件属性个数最少的条件属性组合为约简。因此，可 以构造划分在细分关系下的拓扑结构来求决策表属性约简。 2 3 4 元素是泛权场+ 包含关系 设论域f u ，则可以求f u 的幂集p ( f u ) ，p ( f u ) 上存在包含关系“”，因此可 以构造拓扑结构 。 在拓扑结构 上，根据泛系拓扑的定义，可以求f x f u 的上、下 逼近。可进行如下操作： 1 ) 由于f x 在拓扑结构 上的上、下逼近可能不唯一，不能直接做插 入。可引入偏序宏观序，然后再做插入。 2 ) 如果将，u 视为粗糙集中的知识，可以在拓扑结构 上求f x 的上、 下逼近。该逼近可能不唯一，构造拓扑结构 的子拓扑使得上、 下逼近唯一。 2 3 5 元素是泛权场+ 细分关系 设论域f u ，则可以求f u 的所有划分p ( f u 2 ) ，p ( f u 2 ) 上存在细分关系a ，因 1 0 兰州大学硕学位论文 此可以构造拓扑结构 。 在拓扑结构 上，根据泛系拓扑的定义，可以求划分a 的上、下 逼近。可进行如下操作： 1 ) 划分，r 在拓扑结构 上的上、下逼近可能不唯一，可以构造拓扑 结构 的偏序宏观序，使其上、下逼近唯一，再做插入。 2 ) 粗糙集中决策表属性约简可以理解为条件属性决定的划分或条件属性的并 决定的划分如果细分决策属性决定的划分，则条件属性个数最少的条件属性 组合为约简。而决策表的每个属性列对应一个泛权场，属性的任意并也对应 一个泛权场，而且这些泛权场之间存在细分关系，因此可以构造泛权场拓扑 来研究决策表属性约简。 从上述各种拓扑结构可以得出一个模式：构造拓扑结构，求拓扑结构的宏观 序或找拓扑结构的子拓扑，在拓扑结构的宏观序或拓扑结构的子拓扑下做一些操 作，如作插入、求粗糙集近似、求约简等等，这些操作实质上都是求某元素在某 泛序下的泛极端。拓扑结构和其子拓扑之间是局整关系口9 1 。 2 4 小结 本章首先以圆为例，阐述了泛化思想，即找事物的相对性因子，对相对性因 子泛化，再用泛系方法论中的泛导思想，由辩异同、运泛极原则的观察过程等泛 系概念，来看事物的发展。 接着又以粗糙集为例，介绍了用图形思维和哲理思维来显化事物的相对性因 子，对相对性因子进行各种泛化，得到事物的各种新模型。给出了粗糙集的推广 思路。 最后对拓扑结构从泛系的角度进行泛化，得到各种拓扑结构模型，并简单介 绍了各种模型下的一些操作( 求极端) ，提出了各种拓扑结构下的一个共同模式： 构造拓扑结构，求拓扑结构的宏观序或找拓扑结构的子拓扑，在拓扑结构的宏观 序或拓扑结构的子拓扑下求某元素的泛极端。 基于泛系拓扑的粗糙集近似和决策表属性约简 3 基于泛系拓扑的粗糙集近似和决策表属性约简 3 1 基于泛系拓扑的粗糙集近似 3 1 1 问题提出 x 的 的上近似 | 璺| 3 1 近似空陌1 ( u r ) 中集合x 的近似划分 f i 驴1t h ea p p r o x i m a t i o np a r t i t i o no f s e txi na p p r o x i m a t i o ns p a c e ( u ，r ) 经典粗糙集理论：已知论域u ( 图3 1 中的大矩形) 上的知识r ( 图3 1 中 的小方块) ，则集合x ( 图3 1 中曲线包围的部分) 的上近似( 图3 1 中黑色加灰 色部分) 可以理解为包含x 的那些知识块的并中最小的，集合x 的下近似( 图 3 1 中黑色部分) 可以理解为被x 包含的那些知识块的并中最大的。从图3 1 可 以看出，在已有的知识r 下，集合x 的下、上近似从集合x 的内、外对集合x 进行逼近。 根据泛系拓扑的定义，在已知的泛序系统下，对象x 的上逼近是该泛序系统 中比x 大的元素中最小的，对象x 的下逼近是该泛序系统中比x 小的元素中最 大的。也就是在已有的泛序系统下，从对象x 的内、外对对象x 进行逼近。 因此，可以从泛系拓扑的角度研究粗糙集近似。 3 1 2 基于泛系拓扑的粗糙集近似 定义3 1 等价关系的并空间：等价关系中等价类的幂集构成等价关系的并 空间。 1 2 兰州大学硕士学位论文 定义3 2 基于泛系拓扑的定义，设论域u ，a = p ( u ) ，b 是a 2 上的包含关系 “”，构成拓扑结构 p ( u ) ，p ，r 是u 上的等价关系，h 是r 的并空间，则 拓扑结构 是拓扑结构 p ( u ) ，璺，的子拓扑，设x e p ( u ) , 1 ) 如果x 仨h ，则x ( i n t e r i o r ，h ) 是x 的r 下近似，x ( c l o s u r e ，h ) 是x 的r 上 近似。此时，称集合x 为h 租糙的： 2 ) 如果x e h ，则x 本身既是x 的r 下近似也是x 的r 上近似。此时，称集 合x 为h 精确的。 例3 1 u = l ，2 ，3 ，4 ，r 是u 上的等价关系，u r = “l ，2 ， 3 ，( 4 ，从泛 系拓扑的角度，求 i ) 集合x i = l 。3 的r 上、下近似? 2 ) 集合x 2 = ( 3 ，4 的r 上、下近似? 解：根据定义3 2 构造拓扑结构 ，如图3 2 。 o 图3 2 拓扑结构 f i e , 3 2t o p o l o g ys t r u c t u r e p ( u ) ，9 1 1 , 2 , 3 。4 n o 图3 3 拓扑结构 p ( u ) 。9 下x i 的上、下近似 f 嘲3t h eu p p e r l o w e ra p p r o x i m a t i o no f x li nt o p o l o g ys t n l c t u 心 p ( u ) ，曾， 1 3 基于泛系拓扑的粗糙集近似和决策表属性约简 1 ) 该拓扑结构中x i = 1 ，3 的r 上近似为 l ，2 ，3 和 1 ，3 ，4 ，r 下近 似为 1 ) 和 3 ，不唯一，如图3 3 。 因此，构造等价关系r 的并空间h ： h = o ，( 1 ，2 ， 3 ， 4 ， l ，2 ，3 ， 1 , 2 ，4 ， 3 ，4 ) ， 1 , 2 ，3 ，4 ，如图3 4 中蓝色部分。 l ，2 ，3 ，4 7 l ，2 ，3 1 , 2 ，4 1 ，3 , 4 ) 2 ，3 ，4 1 ，2 1 , 3 1 ，4 2 ，3 2 ，4 3 , 4 图3 4 拓扑结构 f i 9 3 5t o p o l o g ys t r t t c t u r e 根据定义3 3 ，则有： m i n ( h ) = u r 1 ，r 2 ，r 3 = l ， 2 3 ， 4 1 ) 因为m i i h ) au d ，所以该决策表是相容的。 2 ) 子拓扑中细分红色部分的那些划分对应的属性集为原条件属性集的约 简。即 r 2 ，r 3 为约简，也可以看成在子拓扑中求红色部分的极小值。 3 ) r 2 ，9 3 既是约简也是核。 3 3 小结 首先，基于对粗糙集近似与泛系拓扑相似性的分析，提出基于泛系拓扑的租 糙集近似；其次，基于泛系拓扑，讨论了决策表属性约简，提出一套判断决策表 是否相容和求取决策表属性约简的新方法。 本章采用图形化的思维，给出了粗糙集的全新表述，使得求解过程更加直观。 1 6 兰州大学硕士学位论文 4 基于泛权场拓扑的粗糙集近似和决策表属性约简 4 1 基于泛权场拓扑的粗糙集近似 4 1 1 闯题提出 经典= i ：h 糙集理论，论域u 是一些元素的集合，这些元素是具体事物的抽象， 具体事物的代表，元素的多少代表事物的多少，在u 中没有显化事物和事物的 区别，这使得对事物的认识不是很清晰。因此本文引入元素语义，显化事物之阃 的区别，使得对事物的描述更全面，对事物的认识更清晰。 经典粗糙集： 论域：u = 咖，c ，d 知识：r 2 “a ， b ，c ，( d 仁令没有显化分类的依据 求x = ( a ，b 的上、下逼近? 引入元素语义后，上面的问题就变为： 溅u - m im 胍r = v 此晰 求x - ! b 的上、下逼近， 显然引入元素语义后，对问题的描述更全面。 根据泛系拓扑的定义，泛系拓扑给出在某个泛序系统( 相当于粗糙集中的知 识) 下，求某元素的上、下逼近的方法。而租糙集理论，是在一定的知识下，求 元素的上、下近似。因此可以从泛系拓扑的角度，对租糙集进行推广。下面主要 从泛系拓扑的角度，对引入元素语义后的粗糙集基于泛权场拓扑的粗糙集进 行研究。 1 7 基于泛权场拓扑的粗糙集近似和决策表属性约简 4 1 2 基本概念 定义4 1泛权场口7 】：在一个广义系统s = ( a ，b ) 则s 就是一个泛权场，其中w 为a 的泛权集。 定义4 2 泛权场的限定：设有泛权场兀：u 寸， 如果对v x x ，有 ( x ) = 石，( x ) ，称厶为z ，的限定。 中，如果满足b ：a j w ， ：x 寸w ，集合x u ， 定义4 3 子泛权场：设泛权场力：【，一形，以：x 寸矿，集合x u ，如 果对v xx ，不存在y u x ，使得厶( 工) = 兀，称厶是彳，的子泛权场。 特别地， 设彩也是石，的子泛权场。 定义4 4 泛权场拓扑( 基于泛系拓扑的定义) ：设有泛权场z ，a = p ( ，) ( p ( z ，) 是力的幂空间) ，b 是p ( 兀) 上的包含关系“”，构成系统s = ( p ( 矗) ， ) ，h j p ( 兀) ，设厶p ( f o ) ： 1 ) 五( i n t e r i o r ，努) = z ( 够l i m i t ，) = z ( 1 0 w e r ，h ) = m a x t i f h ，t 五 ； t i f h ，正，v t h ，r t i m p l i e st = f o r1 q t h ，s u c h t h a tf r + 2 ) 六( c l o s u r e ，日) = 正( r i g h t l i r a i t ，h ) = f ( u p p e r ，日) = m i n t l t h ，正嵋 = f ir h ，正t , v t h ，f e ti m p l i e st = f o r _ 1 了f h ，s u c h t h a tt r 3 ) 设吃a 测厶f ( i n t e r i o r ，巩) ，矗f , ( c l o s u r e ，以) ，厶= ( 厶，厶) 1 ) 、2 ) 、3 ) 分别定义了z 的下逼近、上逼近和夹逼近。 4 1 - 3 基于泛权场拓扑的粗糙集近似i 墙i 下面讨论在经典粗糙集中引入元素语义后，如何求元素的上、下近似? 定义4 5( 基于泛权场拓扑的定义) 设兀为一泛权场，a = p ( 石，) ，b 是包 含关系“”，构成拓扑结构 ，兀的所有子泛权场构成尸( 彳，) 的子 空白jh 。则拓扑结构 为拓扑结构 的子拓扑，厶p ( ，) 为被 逼近对象，则： 1 ) 如果厶茌h ，那么厶( i n t e r i o r ，h ) 为厶相对于h 的下逼近；兀( c l o s u r e ，h ) 为 相对于h 的上逼近。此时，称泛权场六为h 粗糙的。 i r 兰州丈学硕士学位论文 2 ) 如果 h ，那么厶本身即是厶相对于h 的下逼近，又是以相对于h 的 上逼近。此时，称泛权场六为h 精确的。 例4 1 己知泛权场正，以，求六相对于矗的上、下逼近? 矗。 王绿7 王 正- 三三) e p 瓴，l 红 绿 黄j lj 解：根据定义4 5 ，构造f , j 的幂空间p ( 正，) ： 乞，三，三，三，王，墨，王，王，v ，曼王， 王工，曼v ，昱王王，曼王，v 王，曼v 王) | p ( z ，) 以及尸( 力) 上的包含关系“”，构成拓扑结构 ，如图4 1 所示，灰色部分为被逼近对象正。 图4 1 拓扑结构 p 魄) ，p f i 9 4 1t o p o l o g ys t r u c t u r e p ( ，u ) p 如图4 z 拓扑结构 中，六的上逼近为( 曼v ) 和(