（计算机软件与理论专业论文）系统约简的泛系观与特征关系的属性约简.pdf

捅费 摘要 采集数据是科学研究和数据利用与分析的基础。粗糙集理论已经成为处理完 备信息系统强有力的工具。在现实生活中，由于条件、技术、方法的限制，以及 主观因素和客观因素的影响，导致数据缺失而形成不完备信息系统。针对缺失数 据，存在遗漏语义和缺席语义两种。本文从两种语义并存的特征关系出发，进行 了属性约简方法的研究。 首先，本文基于双重语义对不完备信息系统进行了重新定义，提出了双重语 义下的不完备信息系统单属性局部完备性和不完备度。 其次，本文基于特征关系把粒度、信息熵和条件信息熵和区分矩阵重新定义， 并提出了基于特征关系的粒度启发式属性约简算法，基于特征关系的信息熵属性 约简算法和基于特征关系的区分矩阵属性约简算法。通过算法复杂度分析可知： 在三种约简方法中，区分矩阵算法时间复杂度最低。 然后，本文利用变精度粗集模型思想和粒度方法，提出了不完备信息系统基 于特征关系的程度属性约简方法，给出了相应的算法并进行时间复杂度分析，并 用实例说明了算法的有效性以及证实了程度属性约简算法是以较小的信息损失， 得到更加简单的信息系统。 最后，本文通过泛化思想，认识了信息系统和关系。分析了系统约简中的泛 系关系，定义了泛权系统中泛权重要度，运用泛导、泛极和泛通，分析了约简过 程并给出了相应的泛权约简算法。 关键词：不完备信息系统；特征关系；属性约简：泛化 a b s t r a c t c o l l e c t i n gd a t ai st h eu s ef o u n d a t i o no fs c i e n t i f i cr e s e a r c ha n dd a t aa n a l y s i s r o u g h s e tt h e o r yh a sb e c o m eap o w e r f u lt o o lt od e a lw i t hac o m p l e t ei n f o r m a t i o ns y s t e m i n r e a ll i f e ，b e c a u s eo ft h ec o n d i t i o n s ，t e c h n o l o g y , m e t h o d s ，l i m i t a t i o n s ，a sw e l la s s u b j e c t i v ef a c t o r sa n do b j e c t i v ef a c t o r s ，m i s s i n gd a t aa n dc a u s et h ef o r m a t i o no f 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 s f o rt h ec a s eo fm i s s i n gd a t a ，f r o mt h es e m a n t i c s ， t h e r ea r et w ok i n d so fo m i s s i o ns e m a n t i ca n da b s e n c es e m a n t i c i nt h i sp a p e r ，t h e c h a r a c t e r i s t i cr e l a t i o no ft h ec o e x i s t e n c eo ft w ot y p e so fs e m a n t i c ，c a r r y i n go u ta m e t h o do fa t t r i b u t er e d u c t i o nr e s e a r c h f i r s to fa l l ，t h i sp a p e r ，b a s e do nt h ec h a r a c t e r i s t i cr e l a t i o n s h i p i 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 ，r e d e f i n e st h es y s t e ma n dl o c a lc o m p l e t e n e s sa n di n c o m p l e t e n e s s s e c o n d l y , t h i sp a p e r , b a s e do nt h ec h a r a c t e r i s t i cr e l a t i o n s h i pr e d e f i n eg r a n u l a r i t y , e n t r o p ya n dc o n d i t i o ne n t r o p ya n dd i s t i n g u i s h e d m a t r i xa n dg i v et h eg r a n u l a r i t y h e u r i s t i ca t t r i b u t er e d u c t i o na l g o r i t h m ，i n f o r m a t i o ne n t r o p ya t t r i b u t e f e d u c t i o n a l g o r i t h ma n dd i s t i n g u i s h e d m a t r i xa t t r i b u t er e d u c t i o na l g o r i t h m t h r o u g ht h e a l g o r i t h mc o m p l e x i t ya n a l y s i s ，a m o n gt h et h r e em e t h o d s ，t h ed i s t i n g u i s h e dm a t r i x a l g o r i t h mh a st h em i n i m u m t i m ec o m p l e x i t y t i f d l v b yu s eo fv a r i a b l ep r e c i s i o nr o u g h s e tm o d e li d e a ，p u tf o r w a r dt h ed e g r e e a t t r i b u t er e d u c t i o nm e t h o db a s e do nt h ec h a r a c t e r i s t i c r e l a t i o n s h i pi nt h ei n c o m p l e t e i n f o r m a t i o n s y s t e m a n dg i v e a l g o r i t h m ， a n d m a k et h ea n a l y s i so f t i m e c o m p l e x i t y a tl a s t ，a ne x a m p l es t a t e dt h ee f f e c t i v e n e s so ft h ea l g o r i t h m ，a sw e l la s c o n f i r m e dt h ed e g r e ea t t r i b u t er e d u c t i o nm e t h o db a s e do n as m a l l e rl o s so f i n f o r m a t i o n ，t h ei n f o r m a t i o ns y s t e mm o r es i m p l e f i n a l l y , t h i sp a p e ru n d e r s t a n d st h ei n f o r m a t i o ns y s t e m sa n dr e l a t i o n s h i p sb yt h e g e n e r a l i z a t i o nt h i n k i n g ，a n a l y z e sp a n s y s t e m sr e l a t i o n sd u r i n gp a n w e i g h tr e d u c t i o n ， a n dd e f i n e si m p o r t a n c eo fp a n w e i g h t s t h r o u g ht h ea n a l y s i s o ft h ep r o c e s so f r e d u c t i o nb yu s eo fp a n d e r i v a t i v e ，p a n e x t r e m aa n dp a n c o m m u n i c a t i o n ，t h ep a n w e i g h t r e d u c t i o na l g o r i t h mh a sb e e ng i v e n k e yw o r d s ：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 ，c h a r a c t e r i s t i cr e l a t i o n s h i p ，a t t r i b u t er e d u c t i o n ， g e n e r a l i z a t i o n i l l 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发表的 成果、数据、观点等，均已明确注明出处。除文中已经注明引用的内 容外，不包含任何其他个人或集体已经发表或撰写过的科研成果。对 本文的研究成果做出重要贡献的个人和集体，均己在文中以明确方式 标明。 本声明的法律责任由本人承担。 论客作者签名：二纽日期： 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：j 蜇毽 导师签名：业日 期：竺全：5 ：1 第1 章绪论 1 绪论 1 1 论文研究背景及意义 采集数据是科学研究和数据利用与分析的基础。对于完备的数据表而言，经 典的粗糙集模型在知识获取、决策规则提取和数据挖掘等方面具有强大的功能， 已成为解决这方面问题的有力工具。然而在现实生活中，由于条件、技术、方法 的限制，以及主观因素和客观因素的影响，使得到的所有原始数据并不是合情合 理的，有时候总会存在以下问题，比如数据不一致、噪声、缺失等。数据缺失会 导致信息的不完备，人们不能直接从这种数据中获取所需要的知识，从而制约了 数据的正常利用。因此，研究不完备信息系统信息提取、知识获取、模式挖掘或 决策分析在解决数据缺失情况下的数据利用问题显得尤为必要。 基于等价关系的粗糙集理论是通过上下近似集来描述不精确知识或概念的， 在处理完备信息表的数据处理和利用方面，功能强大，但对于不完备信息表，应 用受到了限制，因此，建立不完备信息表的粗糙集模型，可以解决数据缺失情况 下的属性约简、信息提取等问题。对于不完备信息表，一般情况下，数据的缺失 并没有本质的区别，然而，在现实情况下，数据的缺失是不同的，主要是由于缺 失的影响因素不同导致的。 特征关系把不完备信息表中缺失数据按照遗漏语义和缺席语义严格分开，增 加了问题分析的复杂性，但更接近于现实情况，因此，研究特征关系及基于特征 关系的约简是必要的。经典粗糙集约简，往往是在判断约简前后信息表中的信息 完全一致( 主要是指知识的分类能力) ，在不完备信息表中，由于存在属性值的 缺失，因此，严格一致并不一定能够保证约简的信息量前后是等值的，在有时可 以放宽约简条件进行约简，规定所得的约简符合一定的误差要求( 误差必须满足 用户需求和质量控制条件) ，从而使约简在满足约束条件的情况，最大限度地简 化信息表。当然，这样的约简也是基于不同关系提出的，它是对基于关系扩展模 型研究的延伸，对于完善约简方法，提供新的解决思路，不完备信息系统重要规 则提取是非常有益的。 泛系方法论运用数理、物理、哲理和技理理法思想对事物进行重证再发现， 兰州大学硕士学位论文 从而，为人类认识世界提供了新的工具。泛化成为泛系理论运用的基本方法，信 息系统和其中的关系都存在泛化，可以运用泛化思想和泛系理论知识认识系统中 的约简，为解决约简中的一些问题提供新的思路和方法。 1 2 国内外研究现状 国内外许多学者针对不完备信息表展开了丰富的研究，为利用不完备数据解 决实际问题提供了许多方法。主要集中在不完备信息表的粗集模型扩展和基于容 差关系等的约简算法。为了解决不完备信息系统中不同语义间数据的关系，文献 【1 6 - 1 9 1 ，j j v g r z y m a l a b u s s e 提出了特征关系，在文献【3 6 】中提出了特征关系的 上下近似，并将特征关系与容差关系，非对称相似关系进行了比较分析，文献 3 7 】 对特征关系进一步展开研究，分析j j v g r z y m a l a b u s s e 提出的特征关系的缺陷， 提出了新的特征关系。但均没有对特征关系中，遗漏语义和缺席语义下，不完备 信息系统的特征进行分析，也没有提出相应的约简算法和基于特征关系的粒度表 示、信息熵和条件信息熵、区别矩阵等相应的理论方法。因此，不完备信息系统 中的特征关系的研究与容差关系相比还很少，特征关系的研究有待深入。 利用泛系方法论解决计算机领域和其它领域问题的相关研究，国内外研究较 多，但对约简本身进行泛化后，开展的研究还较少，因此，这方面还须深入研究。 1 3 论文主要研究内容 论文主要研究不完备信息系统基于特征关系的属性约简方法。 首先，针对不完备信息系统进行两种语义的描述，定义了属性的局部完备特 征和不完备度； 其次，提出了基于特征关系的粒度、信息熵和区别矩阵的属性约简方法，并 给出了算法，分析了算法的复杂度； 然后，利用变精度思想，提出了基于特征关系的程度属性约简方法。 最后，通过泛系中泛化思想，认识了信息系统和关系，并运用泛系理论分析 了系统约简。 2 第1 章绪论 1 4 论文结构 第1 章介绍了论文研究背景及意义，国内外研究现状，论文的主要研究内容， 论文结构及论文创新点。 第2 章介绍了论文研究总体思路，拟解决的关键问题及相关知识。 第3 章对不完备信息系统中的特征关系进一步研究，重新定义了两种语义下 的不完备信息系统，提出了单属性局部完备性和不完备度描述，并给出了基于特 征关系中的约简方法。 第4 章提出了不完备信息系统基于特征关系的程度属性约简方法。 第5 章提出了系统约简问题的泛系观。通过系统中的泛化思想，泛权系统中 的增权和减权，泛权约简中的泛系关系描述，给出泛权重要度与泛权约简算法。 最后是结论。分析了本文的优点和不足以及对未来工作进行了展望。 1 5 论文创新点 ( 1 ) 对不完备信息系统基于遗漏和缺席语义进行了重新定义，提出了不完备 信息系统单属性的局部完备性和不完备度。 ( 2 ) 通过不完备信息系统两种语义并存的特征关系研究，建立基于特征关系 的粒度、信息熵和差别矩阵属性约简方法。 ( 3 ) 通过单属性的局部特征和不完备度与粒度关系的分析，提出了单属性局 部特征和不完备度的启发式约简算法。 ( 4 ) 利用变精度粗糙集模型建立思想，提出了不完备信息系统程度属性约简 方法。 3 第2 章论文研究总体思路及相关知识 2 论文研究总体思路及相关知识 2 1 论文研究总体思路 在现有不完备信息系统约简方法的基础上，着重对特征关系和程度属性约 简方法进行研究。提出双重语义下不完备信息系统的定义和局部特征描述，归纳 各种关系扩展的粗集模型，并给出特征关系下的不完备信息系统约简方法和程度 属性约简方法。 2 2 拟解决的关键问题 特征关系是不完备信息系统中更一般的关系，它存在缺失语义的区分，即遗 漏语义和缺席语义。对于单语义的容差关系、非对称相似关系等一类粗集扩展模 型在解决双重语义下的不完备信息系统属性约简问题显得无能为力。本文对特征 关系进行深入研究，提出基于两种语义的不完备信息系统定义方法及其属性特 征，基于不完备信息系统特征关系进行属性约简。 2 3 粗集理论基础 粗糙集理论【1 却堤由波兰华沙理工大学的z , p a w l a k 教授提出的一种研究不完 整、不确定知识和数据的表达、学习、归纳的理论方法。自1 9 9 0 年以来，粗糙 集理论因其在处理不完整数据和不精确知识方面所具有的独特优势，而日益受到 各研究领域的广泛关注，是目前使用较多的一种归纳学习方法，尤其是知识的约 简。目前粗糙集理论已成为知识约简的一种最有效的方法。 2 3 1 知识和范畴 定义2 1 1 2 7 , 2 s l 设u 一西是我们感兴趣的对象组成的有限集合，称为论域。任 何子集x u 称为u 中的一个概念或范畴u 中的任何概念组称为关于u 的抽 象知识，简称知识。 定义2 2 【5 9 j 一个知识库可以定义成一个关系系统： 5 兰州大学硕士学位论文 k 一妙，r ) ( 2 1 ) 其中u 是论域，r 是u 上等价关系。u r 为r 的所有等价类族，用【x 且表示子 集x 属于r 中的一个范畴，且尺包含元素x e u 。 定义2 31 2 7 , 2 s 设知识库k = ，r ) ，若pcr ，p 巾，则np ( p 中全部 等价关系的交集) 也是一个等价关系，称为p 上的不可分辨关系，记为i n d ( e ) ： b k 。一- n x l ( 2 2 ) 触 其中k 】r 是r 中x 的等价类。 定义2 4 1 2 7 , 2 8 1 设表示与等价关系簇p 相关的知识，称为k 中关于u 的 p 基本知识。伽d ( d 的等价类称为知识p 的基本概念或基本范畴。特别地，如果 q r ，q 的等价类称为知识尺的q 初等范畴。可见，基本范畴是初等范畴的交 集。 2 3 2 上下近似集合 与经典集合论不同，在粗糙集理论中，对象和集合的关系有：对象在集合中、 对象不在集合中、对象不确定是否在集合中等三种。为了明确表述这三种关系， 粗糙集理论通过一对上下近似集来完整描述，上下近似集是基于等价关系定义 的。 定义2 5 1 2 7 , 2 8 1 设集合xcu 为论域u 的任一子集，尺是u 上的等价关系： r 一( x ) 一b 【，l k lc _ x j ( 2 3 ) 尺一( x ) 一k u i k lnx m ( 2 4 ) 分别称为x 的尺下近似和z 的足上近似集合。p o s 矗仁) ar 一( x ) 称为x 的尺正 域；n e g r ( x ) - u - r 一( x ) 称为x 的足负域；b n 足( x ) = r 。( x ) - r 一( x ) 称为x 的 r 边界域。 2 3 3 约简和核 定义2 6 1 2 7 ，2 8 1 令r 为一等价关系族，且，r ，如果f 以( r ) = i n d ( r 一 ，) ) ， 则称，是尺中可省略的，否则称r 是r 中不可省略的。如果r 中的所有关系都不 可省略，则称j 5 c 是独立的，否则称r 是依赖的。 6 第2 荤论文研究总体思路及相关知识 定义2 7 印, 2 a l 设q p 是独立的，并且切d ( q ) 一i n d ( p ) ，则称q 是关系族p 的一个约简，记为r e d ( p ) 。p 中所有不可约去关系的集合称为p 的核，记为 c o r e ( p ) 。 由此，根据约简与核可定义，可以得出以下性质。 性质2 1 【2 7 2 8 l c o r e ( p ) = nr e d ( p ) ( 2 5 ) 其中删( p ) 是p 的所有简化族。 定义2 8 【砌l 设p 、q 为u 中的两个等价关系，q 的p 正域为 p o s p ( q ) - u 只似) ( 2 6 ) 工 由式2 7 可见，q 的p 正域是相对于，论域中通过表达的知识能够确切 地归入类中的对象的集合。 定义2 9 z 7 捌设p 、q 为u 中的两个等价关系，p 。( q ) 一p d 一 r ( q ) ， 则称为r e p 是p 中q 可省略的，否则，称为r e p 是p 中q 不可省略的。如果关 系集p 中的所有关系都是q 不可省略的，则称p 是q 独立的，否则就是依赖的。 定义2 1 0 阻2 8 1 尺p 是p 的q 约简，i p 沩r e d q ( p ) 。当且仅当r 是满足条 件胛p ( q ) 一p o s 足( q ) 的最小子集，族集p 中所有q 不可省略的关系的集合称为 p f f j q 核，记为c d 嘞( p ) 。 由相对核的定义可得以下性质： 性质2 2 2 7 捌c o r e 口( p ) = n r e d o ( p ) ( 2 7 ) 其中r e d q ( p ) 是p 中所有q 简化族。 2 3 4 不完备信息的一些关系 ( 1 ) 容差关系( 即相容关系) 基于缺失数据的遗漏语义，k r y s z k i e w i c z 首先提出了容差关系【5 , 6 1 。设 s = 妙，彳) 是一不完备信息表，属性子集b _ c a ，k r ) ，s z k i e w i c z 定义了如下的容 差关系丁。 定义2 1 1 5 , 6 1容差关系z 的定义为： 7 兰州大学石贞士掌位论文 瓦( w ) = 妣) ，) l 口( 工) ；口( y ) va ( z ) 一毒v 口( y ) 咄v x ，y u ，v ae b ) ( 2 8 ) 显然，z 是自反的和对称的，但不满足传递性。 用符号瓦( x ) 表示在属性集合b 上满足关系毛( x ，y ) 的个体对象x 的集合，称 为对象茗的容差类。基于以上定义，k r y s z k i e w i c zm 定义了不完备信息表中对象 集合x 关于属性子集b a 的上下近似集。 定义2 1 2 1 5 , 6 1 设s ；似，彳) 是一不完备信息表，对象集合x 关于属性子集 b c a 的下近似乃( x ) 和上近似z 口( x ) 分别定义为： 毛( 石) = x i ，；x ，v x e u ) ( 2 9 ) t n ( x ) = 仁i ，；n x 西，v x e u ) ( 2 1 0 ) 显然，t 口( x ) = u ( x ) 在容差关系中，由于未知值“ 被认为是和任意已知属性值都相等，限制 较小，会导致两个个体在没有明显相同的已知属性信息时被误判定在同一个容差 类中，即容差关系的要求过于宽松。 ( 2 ) 非对称相似关系 基于缺席语义，s t e f a n o w s k i 等【8 1 提出的基于相似关系的粗糙集理论扩充方 法。非对称相似关系认为未知值不是不确定的，而是当前不存在的，不允许比较未 知值。据此观点，各对象可能有或多或少的描述，这取决于可能采用多少属性。 为此，只要2 个对象的已知属性值相同，就可以认为个个体对象x 与另一个对象 y 相似。 定义2 1 3 t 7 , 4 0 l 设s ；，爿) 是一不完备信息表，属性子集bc _ a ， s t e f a n o w s k i 给出了非对称相似关系船的定义如下： n s n ( x , y ) = ( z ，y ) k ( z ) a 口( y ) v a ( z ) = ? ，v x ，y e u ，v a e b ) ( 2 1 1 ) 显然，非对称相似关系是传递的、自反的，但不对称。相似关系s 是对象集 合u 上的偏序。对于任意个体x e u ，s t e f a n o w s k i 定义了两个非对称相似集合。 定义2 1 4 7 , 4 0 i 非对称相似于石u 的对象集合鹕o ) 及与x 非对称相似的 对象集合嬲8 0 ) 定义： 8 第2 章论文研究总体思路及相关知识 n 8 口( x ) = 工k e u & ( 础) ) ( 2 1 2 ) n s ；1 ( z ) = y l y u & ( 训) ) ( 2 1 3 ) 显然，n s 丑o ) 与n s 一1 bg ) 两个不相同的集合，s t e f a n o w s k i 给出了对象集合x 的 上近似、下近似集。 定义2 1 5 7 , 4 0 1 设s 一妙，彳) 是一不完备信息系统，对于任一对象集合x 关于 属性子集b g 彳的下近似吗( x ) 和上近似嬲口( x ) 分别定义为： 船矗( x ) x l 工e u n s b 4 0 ) 石) ( 2 1 4 ) n s 口( x ) = un s b ( x ) ( 2 1 5 在非对称相似关系中，由于相似关系的非对称性，一些明显具有大量相同的已 知属性信息，直观上就可以判定为相似的个体之间却不满足相似关系，因而不能 被划分在同一个相似类中。可见，非对称相似关系容易造成将同类对象误判为 不同类。 ( 3 ) 限制容差关系 在基于容差关系的扩充粗糙集模型中，由于未知值“木 被认为是和任意已 知属性值都相等的，会导致两个个体在没有明确相同的已知属性信息( 或者极少 相同的已知属性信息) 的情况下就被误判定在同一个相容类中；而在基于非对称 相似关系的扩充粗糙集模型中，由于相似关系的非对称性，一些明显具有大量相 同的已知属性信息，直观上就可以判定为相似的个体之间却不满足相似关系，因 而不能划分在同一个相似类中。鉴于这些扩充关系的局限性，文献 2 1 提出了一 种限制容差关系。 定义2 1 6 川设s = 妙，彳) 是一不完备信息系统，属性子集b 彳，令 兄( z ) = 口ke b 口( z ) 一) ，限制容差关系定义为： 厶( 焉力= k 纠l 口( 习= d 功= | v ( ( 弓( 习n 弓( 力纠 ( d 】9 乒对 ( 口( 功对一d 习= d 力) ) ( 2 1 6 ) 从式3 1 1 0 可知，限制容差关系l 具有自反性、对称性，但不具有传递性。 根 据限制容差关系，可以看出限制容差类k ( z ) 为：k ( x ) = ) r l y u 厶( 工，y ) ) 。 下面进一步定义在限制容差关系下的对象集合的上近似集、下近似集。 9 兰州大学硕士学位论文 定义2 1 7 【2 1 l限制容差关系下的上、下近似集定义为： 岛( x ) x 卜e u 砖卜) nx m ) ( 2 1 7 ) p ( x ) = z 卜e u 砖b ) cx ) ( 2 1 8 ) 实际上，容差关系和相似关系是对不可分辨关系的扩充的两个极端：容差关 系的条件太宽松，使得易于将根本没有相同已知属性的个体误分到同一个相容 类，而相似关系却可能将具有很多相同已知属性信息的个体分到不同的相似类 中。限制容差关系刚好介于容差关系和相似关系这两个极端情况之间。由上面对 限制容差关系的讨论可知，限制容差关系优于其他两种关系。但是限制容差关系 还存在一个缺点，就是对完全没有相同属性值对象的情况处理不够理想。如两个 对象石，y 不满足最( x ) ne ( y ) m 这个条件，即两个对象没有共同存在的已知属 性值时。基于这一点的考虑，文献 3 2 提出了一种改进的限制容差关系。文献 4 5 提出了f 限制容差关系，文献 4 4 提出了k 等价度容差关系，并给出了相应的粗 集模型。 ( 4 ) 修正容差关系 在文献 2 1 1 提出的限制容差关系的基础上，文献【2 3 】提出了一种新的二元关 系一修正容差关系。这种扩充理论既丢弃了以上扩充方法的局限性，又保留了限 制容差关系扩充的优点，因此，对不完备信息系统的处理更加有效。 定义2 1 8 【2 3 j 设s p ，a ) 为不完备信息系统，属性子集bc a ，令 弓( x ) ； 口i 口e b 口( x ) 乒宰) ，其中v x u m 口( w ) 一仁曰i 口( z ) 一口( y ) aa ( 工) 木 口( y ) 一事) ( 2 1 9 ) 虬( ) = 口b i 口( x ) oa ( y ) 口( x ) 一事 口( y ) 宰) ( 2 2 0 ) 则在【，上定义的修正容差关系d 为： d 母( 石，y ) = z 曰l ( x y ) v ( m 矗( 石，y ) m 虬( z ，y ) 一中) ) ( 2 2 1 ) 显然，d 具有自反性和对称性，但不具有传递性，个体对象x 的修正容差类 记为o b ( x ) 。 定义2 1 9 1 2 3 l 设s 一妙，a ) 为不完备信息系统，属性子集b _ ca ，对于 诋u ，x u ，d 为修正容差关系，修正容差关系下x 的上近似、下近似分别 1 0 第2 荤论文研冤总体思路及相关知识 定义为： 见( x ) 一 x u l d 口( 工) c u ) ( 2 2 2 ) d 口( x ) 一 工u i p 丑b ) n x ，西 ( 2 2 3 ) ( 5 ) 特征关系 k r y s z k i e w i c z 提出的容差关系是基于遗漏语义的，s t e f a n o w s k i 和t s o u k i a s 提出的非对称相似关系是基于缺席语义的。而在实际应用中一个不完备信息系统 中遗漏语义和缺席语义同时存在，使用上述模型处理将出现困难于是 j w g r z y m a l a b u s s e 提出了特征关系【1 6 ，1 7 1 。对于不同语义的区分定义见第三章 节。 定义2 2 0 1 6 1 7 1 设s = 妙，彳) 为不完备信息表，属性子集bc a ，v x ，y e u ， v a e b 特征关系p 定义为： 弓( 训) = 肚y ) 瞰工) z 口( y ) va ( z ) = 拳v4 ( ) ，) = 屯口( 工) ? ) ( 2 2 4 ) 显然，p 是自反的，但不是对称和传递的，并且容差关系r 和非对称相似 关系s 是特征关系p 的特殊情况。弓( 戈) ；y y e u 乞( x ，y ) ) 构成了特征类或特 征粒。如果表示分类，则并非是关系p ( 石，) ，) 对u 的划分，而构成u 的 覆盖。下面给出基于特征关系上下近似的定义。 定义2 2 1 3 6 3 7 1 设s = 妙，月) 为不完备信息表，对象集合xc a 关于属性子 集b c _ a 的下近似弓( x ) 和上近似，( x ) 分别定义为： 第1 种形式： 弓( x ) = z i x e u 尼( z ) x ) ( 2 2 5 ) p - ( x ) = z 卜u e 占( x ) n x ，m ) ( 2 2 6 ) 第2 种形式： 弓( x ) = u 弓( 工) k e e u ，尼( z ) x ) ( 2 2 7 ) p ( x ) = u 弓( z ) 卜e u ，圪( z ) n x m ) ( 2 2 8 ) 第3 种形式： 兰州大学硕士学位论文 忍( x ) = u 弓( x ) 卜x ，最( z ) gx ) ( 2 2 9 ) p 占( x ) = u 忍( 工) 卜x ，弓( 工) n x 乒西) ( 2 3 0 ) 以上3 种形式，在完备信息系统下是等价的；但是对于不完备信息系统，情 况则不同，应该根据实际情况进行选择。 下面给出特征关系下的约简与核。 定义2 2 2 设sa 缸，彳) 为不完备信息系统，p 是定义在( ，上的特征关系， 如果v x e u ，且只( x ) = 只一 口1 ( x ) ，则称口是a 中可省略的，否则称口是4 中不 可省略的。如果v a e a 都是a 不可省略的，则称a 是独立的，否则称4 是依赖 的。a 中所有必要属性构成的集合称为4 的核，记为c o i e ( a ) 。 定义2 2 3 设s = ，爿) 为不完备信息系统，曰g 么，如果y x e u ， 只( x ) 一己( x ) ，i e ! x , t t ：任意b cb ，弓( 工) 乒弓( 工) 成立，则称b 是属性集4 的 一个约简，记为r e d ( a ) 。 p 同样，可以得出以下性质。 性质2 3 c o r e ( a ) = f i r e ，d ( a ) ( 2 3 1 ) 在特征关系中，需要知道空缺值的缺失原因，并且在信息系统中根据不同的 缺失语义给以不同的标注，而实际应用中，面对大量的缺失值不知其缺失语义， 这是特征关系的不足之处。 1 2 第3 章不完备信息系统中特征关系的属性约简 3 不完备信息系统中特征关系的属性约简 对于不完备信息系统，按照缺失值的语义可将其分为三大类【6 4 j ： ( 1 ) 不存在型缺失值( 缺席语义) ：即无法填入的值，或称对象在该属性上无 法取值； ( 2 ) 存在型缺失值( 遗漏语义) ：即对象在该属性上取值是存在的，但暂时无 法知道： ( 3 ) 占位型缺失值：即无法确定是不存在型缺失值还是存在型缺失值。 不完备信息系统的特征关系是基于前两种语义并存情形下的对象关系，在实 际问题的解决中，两种语义存在很大的差异。为了解决特征关系下的属性约简， 下面对不完备信息系统基于两种语义进行描述。 3 1 两种语义下的不完备信息系统及其属性特征描述 定义3 1s = 妙，a ，v ，厂) 为一信息表，如果对于至少jae a ，致【，f ( x ，口) 缺失( 遗漏语义或缺席语义) ，分别表示为i ( x ，口) = 宰或? ( 遗漏语义缺 失值表示为扩，缺席语义缺失值表示为? ) ，则称s 一妙，a ，v ，) 是不完 备信息表，简记为s = 妙，么) 。 定义3 2s = p ，a ，v ，) 为一决策表，其中a = cud ，c 为条件属性，d 为 决策属性，对于至少j 口e c ，3 x e u ，f ( x ，口) = 或? ，且w e d ， f x e u ， ，g ，口) = 或? ，则称s 是不完备决策表。 可见，不完备决策表是带有决策属性的不完备信息表。以下如无特殊说明， 不完备信息表和决策表均指两种语义区分下的情形。 下面提出基于两种语义下的不完备信息系统的单属性局部完备特征和不完 备度。 定义3 3s 一妙，a ) 为一不完备信息表，诋【，对于任一属性 口么，u ：= x u i ，o ，口) ，e 幸 ，o ，口) 乒? ，则称集合晖是属性口的局部 完备域。 由上式可知，ugu 。从粗糙集理论可知，属性a 的不同取值可以对集合彬 兰州大莩坝士字1 互论文 构成划分。即( 口) ，这里伽d ( 口) 是属性口在e 上的不可分辨关系。 ( 口) 简亿州u c 。 定义3 4s = 妙，a ) 为一不完备信息表，v x e u ，对于4 1 = 一属性 a e a ，l ： x l f ( x ，口) = ) ，则称e 是属性口的对象遗漏集；v x e u ，对于任一 属性口彳，q ： x l f ( x ，口) = ? ，则称e 是属性口的对象缺席集。 定义3 5 s = 妙，彳) 为一不完备信息表，对于任一属性口彳，属性口的对象 遗漏度定义为： 叫= 饼 1 ) 属性口的对象缺席度定义为： 晔饼 慨2 ) 其中| i 是集合的基数。由定义可知，0 s l d 2s l ，0s l d 2s l 。 定义3 6s 一妙，a ) 为一不完备信息表，v ae u ，对于任一对象 x u ，e = 口i ， ，口) = ) ，则称o 疋对象x 的属性遗漏集；讹u ，对于任一 对象石u ，= 口l ，o ，口) = ? ) ，则称e 是对象z 的属性缺席集。 定义3 7s 一妙，彳) 为一不完备信息表，对于任一对象x u ，对象x 的属性遗 漏度l ，o 定义为： 坎= 臀 3 ， 对象x 的属性遗漏度定义为： 婚臀 4 ) 其中1 1 是集合的基数。由定义可知，o s s 1 ，0 s l d ：s l 。 由定义3 6 、定义3 7 ，可以定义不完备信息表的遗漏度和缺席度。 定义3 8 s = 妙，彳) 为一不完备信息表，毛，乞分别为属性口；的对象遗漏集 1 4 和缺席集，e ，l a z l 分别为对象的属性遗漏集和缺席集，其中f = l 2 ，h ， j f = l 2 ，p i 。不完备信息表s 的遗漏度和缺席度分别定义为： 叼莲鼎巷端 5 ， 纠莲端嘻鼎 n 们 其中i 1 是集合的基数。由定义可知，0 s l d ；，l d ：s 1 。当l 群一o r l d ；，0 时，s 是完备信息表，当彰+ = 1 时，s 是空表，当0 l d s 1 时，s 是缺 失度为甜。的不完备信息表。可见，完备信息表是不完备信息表的特例。 人们经常通过残缺数据的填补将不完备信息表转变成完备信息表，然后进行 属性约简。对于残缺数据的填补方法，主要有l i s t w i s e d e l e t i o n 方法； 手工填补 缺失值：利用一个特定的缺省值来填补：统计学的方法；r o u g h 集理论中区别矩 阵填补缺失数据等几种1 6 5 1 。 对于双重语义的不完备信息表，利用上述的方法比较困难，因为对缺失值语 义进行合理区分。不完备信息表残缺数据的填补，只是一种近似的推断，均存在 不同程度的失真。因此，从关系角度建立适合不完备信息系统属性约简的粗糙集 模型，从而直接进行属性约简。 3 2 不完备信息系统基于特征关系的粒度属性约简 3 2 1 不完备信息系统中特征关系的粒度和属性重要度 为了解决双语义并存的问题，j j 矿g r z y m a l a b u s s e 提出了特征关系，并给出 特征关系的定义及模型。特征关系是结合了容差和相似关系的一种推广形式，仅 满足自反性。由于特征关系仍然是二元关系，因此，可以利用粒度来解决基于这 种关系的约简。下面利用这种特征关系及由它建立的特征粒，继续研究基于两种 缺失语义下的不完备信息系统的属性约简。 文献 5 1 给出了不完备信息系统中基于容差关系定义的粒度、核及相应的算 法。下面是特征关系下的粒度定义。 定义3 9 设s = 妙，彳) 为不完备信息系统，只为定义在s 上的特征关系，对 兰州大字坝士学位论文 曼曼曼皇曼曼曼曼蔓曼曼皇曼寡皂曼曼曼鼍鼍皇曼皇曼曼量皇曼曼曼曼! 曼曼曼蔓曼曼曼皇量皇舅! 曼曼舅曼i i 曼皇皇皇量鼍皇曼曼舅舅暑量曼曼曼曼曼蔓蔓曼蔓鼍曼曼曼曼舅 于v x e u ， 2 只( 玉) ，只( 屯) ，只( 为) ，只( 卸i ) ，其中只( 工) 是特征粒，则 4 一 i 、o7j a 基于特征关系的的知识粒度定义为： 1 u l ( a ) 2 卉驴i ( 3 可见，彤l s g d ( 么) 虬 根据粒度的定义，可以得出以下定理： 定理3 1 设s = 妙，彳) 是一不完备信息系统，口，q 彳，如果v x e u ，有 弓( 石) 忍( x ) ，则g d ( 曰) g d ( q ) 。 溉龇q 弘删删吲办邮) = 卉f 警) i + 皆 毗，= 辅酏) i + 皆心州吲办所以皆皆， 而赤i 和阱阡1i u 犯i - i 牡所以( 眯( q ) o f g n 3 2 设s 一妙，彳) 是一个不完备信息系统，b ，qc a ，如果诋u ，有 b ( x ) z 忍( z ) ，n g d ( b ) = g d ( q ) 。 证明：( 略) 利用知识粒度，可以分析不完备信息系统中每一个属性的重要性。下面用粒 度定义属性的重要性。 定义3 1 0 设s = 妙，彳) 是一个不完备信息系统，a6 a 在a 中的重要度定义 为： 蹰彳( 以) 5 g d ( a 一 口) ) g d ( 4 ) ( 3 8 ) 定义表明，属性口在a 中的重要性是用由a 中去掉口后引起的知识粒度变化 的大小来度量。也就是说，对一个属性集合，去掉一个属性引起的知识粒度变化 量越大，则该属性对此属性集就越重要，反之亦然。可得： o s ( 口) 小i 。 定理3 3 设s = 妙，a ) 是一不完备信息系统，b 彳，如果 1 6 第3 荤不是备信思系统中特征关糸的属性约茼 g d ( b ) = 印( 么) ，且对于任意b c b , g d ( b ) 芦g d ( 曰) ，则称口是彳的一 个约简。 证明：( 充分性) 设b c a ，g d ( b ) = g d ( a ) ，则对于v x e u ， 只( z ) = 只( 石) ， 设任一个b c b ，使( b ) 一g d ( 曰) ，则专u ， 只( y ) 乒乞( y ) ，则只( y ) 乒乞( y ) ，因此v 6 口，但6 譬曰在b 中是不可省略的， 则b 是独立的。所以，b 是彳的一个约简。 ( 必要性) 设b 是4 的一个约简，则b 4 是独立的且对于v x e u ， 最( z ) 一只( x ) ，则g d ( 曰) = a o ( a ) ，bc _ a 是独立的，则对于任意b c b ， 渺曰，但y 岳b ，弓( y ) 乒b ( y ) ，所以g d ( b ) 一g d ( 曰) 。 3 2 2 特征关系下影响粒度的因素 ( 1