（计算机应用技术专业论文）不完备信息系统中粗糙集理论研究.pdf

博士论文不完备信息系统中租糙集理论研究 摘要 粗糙集理论是由波兰学者p a w l a k 提出的一种新型数据分析工具，对于研究如何 应用数学工具模仿人脑的思维活动和认知过程具有重要的作用。由于经典粗糙集理论 是建立在不可分辨关系( 等价关系) 上的，要求过于严格，因而研究粗糙集的各种扩 展模型对于粗糙集理论的发展具有极其重要的意义。本文主要针对不完备信息系统中 的各种扩展粗糙集模型进行了系统而又深入的研究。 在具有缺席型未知属性值的不完备信息系统中，提出了差异关系粗糙集模型以获 取否定决策规则。在一般情形中的不完备信息系统中，提出了基于可变精度分类关系 的粗糙集模型，证明了基于容差关系、非对称相似关系的粗糙集模型是可变精度分类 关系粗糙集模型的特例。 研究了同时具有遗漏型和缺席型未知属性值的广义不完备信息系统，讨论了原有 特征关系的不足之处，进而提出了3 种新的特征关系，并对基于这些特征关系的粗糙 集模型进行了对比分析。 在具有遗漏型未知属性值的不完备信息系统中，考虑属性值的顺序特性，进而提 出了t 和、l 描述子的概念，讨论了t 和【描述子约简的分辨矩阵方法，根据t 和【描述子， 研究了如何从不完备决策系统中获取最优可信规则，与原有基于扩展优势关系粗糙集 模型的方法相比，使用t 和j ，描述子的方法，不仅可以消除决策规则中的未知属性值， 而且可以获得包含信息更为丰富的决策规则。 在具有缺席型未知属性值的不完备信息系统中，考虑属性值的顺序特性，提出了 相似优势关系的概念，根据基于相似优势关系的粗糙集模型，提出了4 种近似分布约 简的概念，并对这些约简之间的关系进行了讨论。将基于相似优势关系的粗糙集模型 引入不完备模糊决策系统中，对其中的知识约简与知识获取问题进行了研究。 在区间值信息系统中，首先根据已有的优势关系提出了6 种不同形式的相对约简 以获取最优决策规则；接着考虑对象与对象之间的优势程度，定义了区间值决策系统 中的模糊粗糙集模型以进行知识获取。 关键词：不完备信息系统，粗糙集，优势关系，描述子，知识约简，决策规则 a b s t r a c t r o u g hs e tt h e o r yi s an e wd a t aa n a l y s i st o o l ，w h i c hw a sf i r s tp r o p o s e db yp o l a n d r e s e a r c h e rp a w l a k s u c hat h e o r yp l a y saf u n d a m e n t a lr o l e i nt h ei m i t a t i n go fh u m a n b r a i n st h i n k i n ga n dc o g n i t i o n s i n c et h et r a d i t i o n a lr o u g hs e tm o d e li sc o n s t r u c t e do nt h e b a s i so fas t r i c ti n d i s c e m i b i l i t yr e l a t i o n ( e q u i v a l e n c er e l a t i o n ) ，r e s e a c ho nh o wt oe x p a n d t h er o u g hs e tm o d e li sv e r yi m p o r t a n tf o rt h ed e v e l o p m e n to fr o u g hs e tt h e o r y i nt h i s t h e s i sf o r t h ed o c t o r a t e ，s e v e r a le x p a n d e dr o u g hs e tm o d e l sa red e e p l yi n v e s t i g a t e di nt h e 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 i nt h ei n c o m p l e t ei n f o r m a f i o ns y s t e mi nw h i c ha l lu n k n o w nv a l u e sa l ec o n s i d e r e d 硒 “l o s t ”，an e wr o u g hs e tm o d e li sp r o p o s e db a s e do nt h ec o n c e p to f d i f f e r e n c er e l a t i o n ，f r o m w h i c hw ec a ng e n e r a t ea l ln e g a t i v er u l e sf r o mt h ei n c o m p l e t ed e c i s i o ns y s t e m i ng e n e r a l 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 ，t h ev a r i a b l ep r e c i s i o nc l a s s i f i c a t i o nb a s e dr o u g hs e tm o d e l i sp r o p o s e d i ti sp r o v e dt h a tt h er o u g hs e tm o d e l sb a s e do nt o l e r a n c er e l a t i o n ，s i m i l a r i t y r e l a t i o na r es p e c i a lf o r m so ft h ev a r i a b l ep r e c i s i o nc l a s s i f i c a t i o nr o u g hs e t i nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mi nw h i c hu n k n o w na t t r i b u t e s v a l u e sa r e c o n s i d e r e da sn o to n l y “i o s t b u ta l s o “d on o tc a r ec o n d i f i o n ，t h r e en e wc h a r a c t e r i s t i c r e l a t i o n sa r ep r o p o s e dt om a k eu pf o rt h el i m i t a t i o n so ft h eo r i g i n a lc h a r a c t e r i s t i cr e l a t i o n t h er e l a t i o n s h i p sb e t w e e nt h e s ec h a r a c t e r i s t i cr e l a t i o n sb a s e dr o u g hs e tm o d e l sa r ea l s o i n v e s t i g a t e d i nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mi nw h i c ha l lu n k n o w nv a l u e sa r e d on o tc a r e c o n d i t i o n ”，t h ec o n c e p to fta n d 【d e s c r i p t o r s a r e p r o p o s e db yc o n s i d e r i n gt h e p r e f e r e n c e - o r d e r e dd o m a i n so ft h ea t t r i b u t e s t h ed i s c e r n i b i l i t ym a t r i xa p p r o a c ht oo b t a i n t h eta n dj ，d e s c r i p t o r s r e d u c t i o n sa r et h e ns t u d i e d w i t hr e s p e c tt ot h ep r o p o s e d d e s c r i p t o r s ，t h ep r a c t i c a la p p r o a c ht og e n e r a t ea l lo p t i m a lc e r t a i nr u l e sf r o m t h ei n c o m p l e t e d e c i s i o ns y s t e mi s i n v e s t i g a t e d b yc o m p a r i n gw i t ht h ee x p a n d i n gd o m i n a n c er e l a t i o n b a s e dr o u g hs e tm o d e l ，w ec a l lo b t a i nt h ed e c i s i o nr u l e s ，w h i c hi n c l u d i n gm o r eu s e f u l i n f o r m a t i o nf r o mt h ev i e w p o i n to fta n d 上d e s c r i p t o r s i nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e mi nw h i c ha l lu n k n o w nv a l u e sa l e “l o s t ，t h e c o n c e p to fs i m i l a r i t yd o m i n a n c er e l a t i o ni sp r o p o s e db yc o n s i d e r i n gt h ep r e f e r e n c e o r d e r e d d o m a i n so ft h ea t t r i b u t e s b yt h es i m i l a r i t yd o m i n a n c e b a s e dr o u g hs e tm o d e l s ，n o to n l y f o u rt y p e so fa p p r o x i m a t ed i s t r i b u t i o nr e d u c t sa r ep r o p o s e db u ta l s ot h er e l a t i o n s h i p s b e t w e e nt h e s er e d u c t sa r ed i s c u s s e d m o r e o v e r t h es i m i l a r i t yd o m i n a n c e b a s e dr o u g hs e t i i i m o d e li si n 仃o d u c e di n t ot h ei n c o m p l e t ef u z z yd e c i s i o ns y s t e mf o rk n o w l e d g er e d u c t i o n a n dk n o w l e d g ea c q u i s i t i o n i l lt 1 1 ei n t e r v a j v a l u e di n f o r m a t i o ns y s t e m ，s i xt y p e so fr e l a t i v er e d u c t sa l ep r o p o s e d ， 疳o mw 1 1 i c ho n ec a no b t a i nt h eo p t i m a ld e c i s i o n r u l e ss u p p o r t e db yas p e c i a lo b j e c t m o r e o v e r ，b yc o n s i d e r i n g t h ed o m i n a n c ed e g r e eb e t w e e no b j e c t s ，t h ef u z z yr o u g h a p p r o a c hi se m p l o y e df o rk n o w l e d g ea c q u i s i t i o ni n t h ei n t e r v a l 。v a l u e dd e c i s i o ns y s t e m k e yw o r d ：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 ，r o u g hs e t ，d o m i n a n c er e l a t i o n , d e s c r i p t o r , k n o w l e d g er e d u c t i o n ，d e c i s i o nr u l e i v 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：盘口逡 2 夕一年，j 弓be t 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：盔复：! 堕z 口，口年月弘日 博士论文不完备信息系统中粗糙集理论研究 1 绪论 1 1粗糙集的历史与现状 1 1 1粗糙集理论历史发展过程 经典集合论对应于经典逻辑，因而适用于描述确定性问题。值得注意的是，在自 然科学、社会科学和工程技术等众多领域中，不确定、不精确信息是广泛存在的。不 确定性可以理解为在缺少足够信息的情况下做出判断，是智能问题的本质特征。不确 定性实际上起源于量子力学，例如海森堡不确定原理：一般地，一个粒子的位置和它 的动量不可被同时确定，换句话说，只有当位置确定的时候，粒子的动量才能被度量， 反之亦然。 多年来，众多研究人员一直致力于寻找科学地处理不确定问题的有效方法。例如， 模糊集【l 】与概率论 2 1 是处理不确定性问题的两种代表性方法，然而这两种方法有时需 要一些关于数据的附加信息或先验知识，如模糊隶属度，概率统计分布等，这些信息 有时并不容易得到。 粗糙集理论【3 。8 】( r o u g hs e tt h e o r y , 简称r s t ) 是近年来计算智能领域出现的一个 新的分支，具有坚实的数学基础，可用于处理不确定性问题。粗糙集理论对于研究如 何应用数学工具模仿人脑的思维活动和认知过程具有重要的作用，它最为突出的特点 是无需提供除问题所需处理的数据集合之外的任何先验信息。作为数据处理工具，粗 糙集与模糊集理论最主要的区别是【9 】：粗糙集以不可分辨关系为基础，侧重分类；而 模糊集则基于元素对集合隶属程度的不同，强调集合本身的含混性。从粗糙集的观点 来看，集合不能被清晰定义的原因是缺乏足够的领域知识，但可以用一对清晰集合逼 近。 粗糙集理论是在八十年代初由波兰学者z d z i s t a wp a w l a k 首先提出的，由于最初的 研究成果是用波兰文发表的，因此，粗糙集理论当时并未引起国际学术界的重视，研 究地域仅局限在东欧各国。八十年代末，由于粗糙集理论在人工智能领域得到了成功 的应用，特别是1 9 9 1 年p a w l a k 教授的第一本关于粗糙集的专著【3 】和1 9 9 2 年s t o w i f i s k i 主 编的关于粗糙集应用与相关方法比较研究的论文集【1 0 1 的出版，粗集理论逐渐引起了世 界各国学者的关注。 自1 9 9 2 年第一届关于粗糙集方法的国际学术会议在波兰召开以来，每年都有关 于粗糙集理论及其应用的国际学术会议召开。2 0 0 5 年，国际上正式成立了粗糙集研 究学会一i n t e m a t i o n a lr o u g hs e ts o c i e t y , 并创立了粗糙集理论的国际期刊 一t r a n s a c t i o n so nr o u g hs e t ，所有这些工作都加速了粗糙集理论在国际学术舞台上的 l 绪论博士论文 交流与发展，为进一步推动了粗糙集理论的深入研究起到了决定性的作用。 目前，我国学者在粗糙集扩展模型，公理化体系，粗糙逻辑，粗糙数学等方面的 研究取得了较大成功，在粗糙集理论某些方面的研究水平已达到或接近国际先进水 平，可以说我国学者正在成为粗糙集理论研究的主导力量。2 0 0 3 年1 1 月，在中国广 州举行的全国人工智能学会的年会上，中国粗糙集与软计算专委会正式成立。自2 0 0 1 年在重庆邮电大学成功召开“第一届中国r o u g h 集与软计算学术研讨会”以来，每 年都召开一次中国粗糙集与软计算学术会议，每年的学术会议在规模和质量上均呈良 好的增长趋势，“第九届中国r o u g h 集与软计算学术研讨会”于2 0 0 9 年8 月在河北 石家庄召开。所有这些学术活动都为我国学者在粗糙集理论与应用方面的研究提供了 良好的学术交流平台。 1 1 2粗糙集理论研究现状 粗糙集理论自提出以来，其理论模型得到不断完善和发展，并渗透到很多学科， 成为研究数据挖掘、知识约简和粒计算的理论基础，同时，粗糙集理论自身也已成为 完整、独立的科学领域。目前国内外对于粗糙集理论的研究主要集中在以下几个方面： 1 ) 关于粗糙集模型的推广研究，这一直是粗糙集理论的热点研究问题，对于将粗糙 集理论进一步推向实用有着极其重要的意义； 2 ) 关于粗糙集理论数学性质方面的研究，主要集中在粗糙集的代数结构和拓扑结构 上，涌现了一大批新的概念，如粗糙代数 1 1 , 1 2 ，粗糙群【1 3 1 ，粗糙环【1 4 1 ，粗糙模【15 1 ， 粗糙理想 1 6 , 17 】等等； 3 ) 关于与其他处理不确定性问题理论的关系研究，如粗糙集理论与概率统计【1 8 , 1 9 、 模糊数学【2 0 1 、证据理论【2 1 1 等理论的相互渗透与互补； 4 ) 关于粗糙集理论的算法研究，寻找一个信息系统的所有约简或最小约简是一个 n p 难问题，因而寻求高效的可行的约简算法仍然是粗糙集理论中尚未完全解决 的问题。 不确定性是粗糙集理论的关键词，它涉及集合论定义中的许多实质性内容。集合 的近似定义是现代数学中的重要概念之一，而与布尔逻辑非常相关的经典集合论又是 数字计算机运算的核心。众所周知，许多实践问题不能满足现存计算机的求解条件， 特别是机器学习、模式识别以及某些控制问题等，这种困难常常使得不能建立描述个 体的算法。而粗糙集理论及其扩充对于建立此类个体的近似描述，提供了一种精确的 数学技术。粗糙集方法对于处理这类问题提供了一种通用的由精确数学语言支持的哲 学框架。 2 博士论文不完备信息系统中粗糙集理论研究 1 2粗糙集理论的数学基础 p a w l a k 所提出的粗糙集理论是建立在分类机制的基础上，它把知识看作是一种对 现实的或抽象的对象进行分类的能力，而分类则是推理、学习与决策中的关键问题【9 1 。 这里的“对象 是指我们所能言及的任何事物，比如实物、状态、抽象概念、过程和 时刻等等。粗糙集模型的最本质特征是根据已知的知识，对未知的知识( 不精确或不 确定知识) 进行近似刻画。粗糙集理论与其他处理不确定和不精确问题理论相比，无 需提供问题所需处理的数据集合之外的任何先验知识，所以对问题的不确定性描述或 处理显得较为客观。由于粗糙集理论未能包含处理不精确或不确定原始数据的机制， 因而这个理论与概率论( 需要知道数据的概率分布) 、模糊数学( 需要给定隶属度函 数) 和证据理论( 需要信度函数) 等其他处理不精确或不确定问题的理论具有很强的 互补性。 要了解什么是粗糙集理论，首先定义如下概念： 1 ) 令u a 为一论域，r 为吐的一族等价关系的集合，则称k b = 为一个知 识基； 2 ) 对于v r e r ，r 表示u 上的一个二元等价关系( 满足自反性、对称性和传递性， p a w l a k 称其为不可分辨关系) ，对于帆，y 配若o ，力r ，则称x 与y 之间是不可分 辨的； 3 ) 对于v r e r ，k s = 称为一个知识结构或近似空间。 由离散数学的相关知识可以证明，驴上的一个划分与吐的一个二元等价关系之 间一一对应，若令u r 表示由二元等价关系尺所产生的论域划分，则u j 6 c 中的元素称 为欠一基本集或原子集。在近似空间k s 中，对于v x c _ 配若艉一些r 基本集的并集， 则称艉r 一可定义的，否则称为是尺一不可定义的。 1 2 i粗糙近似集 为了近似地定义粗糙集，p a w l a k 建立了的下、上近似集的概念。 定义1 1 【3 1 设u 为一论域，r r ，对于v 逛配堪于等价关系r 的下近似集合墨 ( l o w e r a p p r o x i m a t i o n ) 与上近似集合尺( u p p e r a p p r o x i m a t i o n ) 分别定义如下： 墨2u y eu r ：】，互毋= x eu ：b 】r 田；( 1 1 ) ra f ) 2u y eu r ：y n x # 彩 = x u ：b 】尺n y f 2 j ) ； ( 1 2 ) 其中k 】r = y e u ： ，力r ) 表示u 中所有与x 具有等价关系尺的对象的集合，即由x 决定 的等价类。 墨实际上是由那些根据已有知识判断肯定属于椭对象所组成的最大集合， 而页则是由那些根据已有知识判断可能属于x 的对象所组成的最小集合【3 1 。事实 l 绪论博士论文 上，星是包含于彳中的最大r 一可定义集，类似于点集拓扑中的内点；r 是包含彳 的最d , r 一可定义集，类似于点集拓扑中的闭包；故有人称其为p a w l a k 拓扑。因此近 似概念能使我们精确地讨论关于不精确的东西。 确r 一正区域记y g e o s r ( x ) = 堡，它是如此一些个体元素的集合，这些元素完全 属训成员。 椭r 一负区被记为n e g r ( x ) = 班r ，它是如此一些个体元素的集合，这些元素 肯定不属于x 确r 一边界被记为删k = r 一星，它是那些通过等价关系r 既不能砒被 分类，也不能在m 被分类的元素的集合。 若边界域为空，则通过等价关系尺可以恰当地观察集合置反之若引囝，我 们只能通过下、上近似集粗糙地观察集合x p a w l a k 构建的粗糙集具有如定理1 1 所示的性质。 定理1 1 1 3 1设嘞一论域，r r ，五y c u 下、上近似集具有下列性质： 墨x c r ；( 1 3 ) 星( o ) = r ( 囝) = 囝；( 1 4 ) 墨( = r ( = 矾( 1 5 ) 墨uy ) 2 星u 墨( y ) ；( 1 6 ) 墨nd = 星n 墨( d ；( 1 7 ) r ud = r0 dur ( d ；( 1 8 ) 尺ny ) r0 0nr ( 功； ( 1 9 ) z 冬】厂墨墨( d ；( 1 1 0 ) x 】厂jr r ( y ) ； ( 1 1 1 ) 星( 、的= 1r ； ( 1 1 2 ) 足( 1 的= 1 星；( 1 1 3 ) 墨( 星) = 星；( 1 1 4 ) 尺( r ) = 尺；( 1 1 5 ) 1 2 2近似精度 由于存在边界线区域，即有些元素既不能在论域的某个子集上被分类，也不能在 它的补集上被分类，而这些元素归于这种边界线区域，它的大小是衡量该子集关于论 域上的等价关系r 的近似精度，为了更精确地表示这种r o u g h 的思想，p a w l a k 定义了 近似精度3 】的概念；而y a o 【2 2 1 使用m a r c z e w s k i s t e i n h a u s 距离来度量下、上近似之间的 距离，得到了粗糙度的概念，并证明了近似精度与粗糙度之间是互补的。 定义1 2 t 3 】设嘞一论域，r e r ，对于v a _ c 以x 的近似精度及粗糙度分别记为a r ( x ) 4 博士论文不完备信息系统中粗糙集理论研究 和脚且： 翰2 渊， ( 1 1 6 ) 胁= 1 - a r ( x ) ，( 1 1 7 ) 其中lxl 表示集俐基数。 a r ( x ) 表示我们获得关于集绷知识是否完全的程度，很明显，0 蚴1 成立。当翰= 1 时，有b n r ( x ) = g ，此魄精确可定义的；当a r ( x ) 0 1 ；( 1 2 0 ) b n r ( x ) = x eu ：0 ( x ) l ( 1 2 1 ) 定理1 2 2 3 1 令蚋一论域，r e r ，对t v x e u , 粗糙隶属度函数呈( x ) 具有下列性质： 1 ) 如果r = ，功：x u ) ，则至( x ) 删特征函数； 2 ) 如果 ，y ) e r ，则x r l x j 一_ x r ( 少) ； 3 ) 占一z ( x ) 2 1 羔( x ) ； 4 ) 彬u ，( x ) m a x ( 群( x ) ，( x ) ) ； 5 ) 皇n ，( x ) r a i n ( 娄( x ) ，罗( x ) ) ； 6 ) 如果p = 蜀，噩， 是【，上的一族互不相交的子集，那么就有 嘁( x ) = 蜀。p 彬，( x ) 1 3 信息系统中的基本概念 1 3 1知识表示 知识表示是认知科学和人工智能两个领域共同存在的问题。在认知科学里，它关 系到人类如何储存和处理资料；在人工智能里，其主要目标为储存知识，使得计算机 程序能够处理知识，达到人类的智慧。 要理解知识表示，首先要知道什么是知识。在粗糙集理论中，p a w l a k 将把知识看 作是一种对现实的或抽象的对象进行分类的能力。由于经典粗糙集理论是建立在不可 分辨关系，即等价关系的基础上的，因而知识就是划分。 p a w l a k 采用知识表示系统来描述知识。知识表示系统实际上是一个数据表，表中 的行代表数据对象，而表中的列则表示关于数据对象的信息【3 1 。 形式化地，一个知识表示系统可被定义为二元组s = ，其中 镰示所有对象的集合，称为论域； a 骧示所有属性的集合。 对于v a e a t , 定义映射a ：圪，圪表示属性a 的值域，耳p a ( x ) e 令k b = 为一个知识基，如何将知识基中的知识表示为知识表示系统? 可 以通过以下两个步骤来实现【3 】： 1 ) 对于v r e r ，得到论域上的一个划分u r = 蜀，恐，) ； 2 ) 给定一个属性a ，其中a e a t , 若令圪= 1 ，2 ，历) ，则有a ( x ) = f ( 1 f 历) 当且仅 当x 五 知识表示系统s = 实际上是用来描述知识基k b = e p 的知识的。它 将知识基中的知识转化为计算机可以接受的用于描述知识的数据结构。对于知识基中 的每个等价关系，知识表示系统中必有一个属性与之对应；而对于每个等价类，在知 6 博士论文不完备信息系统中粗糙集理论研究 识表示系统中必有一个属性值与之对应【3 1 。 为了简便起见，如无特殊说明，下文中将知识表示系统s = 以彳p 统一称为信 息系统。 1 3 2知识依赖 在信息系统s 中，根据属性集合a c a t , 可定义个不可分辨关系【3 】，即二元等价 关系形如 i n d ( 么) = 0 ，y ) e 酽：v a e a ，口( 力2 口( y ) ) ( 1 2 2 ) 由于根据属性集合4 ，可以定义论域上的一个等价关系，而等价关系或等价关系 生成的划分在粗糙集理论中被看作知识，因而此处将属性集合么亦看作知识。 定义1 5 【3 1设s 为一信息系统，其中尸，q _ c a r , 定义如下： 1 ) 称知识q 依赖于知识p ( i e 做pjq ) 当且仅当n r d ( p ) s n d ( q ) ； 2 ) 称知识p 与知识q 等价( 记做p = q ) 当且仅当p q 且qj 尸； 3 ) 知识尸与知识q 独立( 记做p q ) 当且仅当尸q 且qjp 均不成立。 显然，p = q 当且仅当删d ( p ) = n d ( q ) 当知识q 依赖于知识p 时，我们也说知识 q 是由知识p 导出的。 通过简单推导可得到下列性质。 定理1 3 【3 1设s 为一信息系统，其中尸，q ，丑，r 4 乃有 若pjq 且q r ，则户r ； ( 1 2 3 ) 若pj r 且q r ，贝j j p u qjr ； ( 1 2 4 ) 若尸qur ，则p r 且pjq ；( 1 2 5 ) 若pjq 且q urj 正贝u e urj r ； ( 1 2 6 ) 若pj q 且r l 则pu 尺jq u r ；( 1 2 7 ) 若p q 且p 3p ，则尸q ； ( 1 2 8 ) 若p q 且q7 cq ，则pjq ( 1 2 9 ) 有时候知识的依赖性可能是部分的【3 1 ，这意味着知识q 仅有部分是由知识尸导出 的，部分导出可由知识的正域来定义： p o s e ( q ) = u e ：x e u i n d ( q ) ) ( 1 3 0 ) 其中p 2 幽 p o s p ( q ) 的含义是u 中所有根据分类u d ( 尸) 的信息可以准确地划分到q 的等价 类中去的对象集合。 q 部分依赖于尸的依赖度定义为【3 】： k = y e ( 9 ：ip o 百s 丁p ( q 一) 1 ( 1 3 1 ) l 绪论博士论文 很明显0 七1 我们用尸j 女q 表示q 是k 度依赖于尸的。当七= 1 时，称q 完全依赖 于p ；当o k l 时，称q 部分依赖于尸；当七= o n ，称q 完全独立于尸 1 3 3知识约简与核 知识约简是粗糙集理论的主要内容，通过约简，可以除去冗余知识，获得简化的 决策规则，以下将引入一些知识约简的基本概念。 定义1 6 1 3 1设s 为一信息系统，对于v a e a t , 若有i n d ( a t - a ) = i n d ( a 乃，则称口枷r 中是可约去的( 不必要的) ，否则称a 是不可约去的( 必要的) 。 不必要的属性在信息系统中是多余的，如果将它从信息系统中去掉，不会改变信 息系统的分类结果；相反，若从信息系统中去掉一个必要的属性，则一定改变信息系 统的分类结果。 定义1 7 1 3 1设s 为一信息系统，对于v a e a t , 口都是么r 中不可约去的，则称知诎r 是 独立的，否则称为相关的。 对于相关知识来说，其中包含多余知识，需要对其进行约简。 定义1 8 t 3 】设s 为一信息系统，a _ c a l 若满足 1 ) 1 n d ( a ) = 1 n d ( a t ) ； 2 ) 彳是独立的； 则称么黝丁的一个约简( r e d u c t ) 很明显，对于相关知识所求得的约简并非唯一的，因此可以引入以下定义。 定义1 9 t 3 令s 为一信息系统，彳r 中所有不可约去的知识称为彳丁的核( c o r e ) ，记为 c o r e ( a t ) 约简与核有如下关系。 定理1 4 【3 】设s 为一信息系统，则 c o r e ( a t ) 2n 氏 ( 1 3 2 ) i = l 其中4 0 f ( 1 f s ) 表示么确所有约简。 可以看出，核这个概念的用处有两个方面2 4 】：首先它可以作为计算所有约简的基 础，因为核包含在所有的约简中，并且计算可以直接进行；其次可解释为在知识约简 时不能消去的知识特征的集合。 例1 1对于表1 1 所示的一个信息系统， u = 缸l ，x 2 ，x 3 ，x 4 ，x d 为论域， a t = 口，b ，c ，田为所有属性集合。 根据定义1 8 可以看出表1 1 有两个约简 口，6 ， 6 ，田，所以核属性为 6 ) 约简和核这两个概念是粗糙集的精华所在1 2 4 。约简计算的复杂性随着信息系统规 模的增大呈指数增长，是一个n p 完全问题。在实际问题应用中，没有必要求出所有的 r 博士论文 不完备信息系统中粗糙集理论研究 约简，引入启发式搜索可以找到较优的约简。文献【2 5 】给出了区分矩阵和区分函数来计 算约简和核，给出了约简和核的结构表示，该方法用于信息系统规模较小时较为有效。 表1 1 信息系统示例 1 3 4决策系统 决策系统是一类特殊而又重要的信息系统，多数决策问题都可以用决策系统的形 似来表达，这一工具在决策分析问题中起着重要的作用。 一个决策系统是一个信息系统s = ，其中彳瞰称为条件属性集合，d 称为决策属性集合助丁n d 1 2 j 【3 】若d 中含有两个或两个以上的决策属性，则称s 为一个多属性决策系统；若d = , t 3 ，即d 中仅含一个决策属性，则称s 为一个单属性决 策系统，记为s = 以a t u 痧若无特殊说明，本文所讨论的决策系统都是单属性决 策系统。 定义1 1 0 【3 】设沩一决策系统，对于坛，y 以若伍力e l n d ( a ) j = ，则称这个 决策系统是一致的，否则称为不一致的。 例1 2表1 2 是一个不一致决策系统，其中 u = x i ，x 2 ，x s 为论域， a t = 口，b ，c 为所有条件属性集合， d 为决策属性。 表1 2不一致决策系统 9 l 绪论博士论文 对于任何一个不一致决策系统s 都可以分解成两个子系统两，& ，在s l t ：p ，对于v x ， y 以若 ，y ) e l n d ( a ) ，则有荆= m ) ，n n s l 是一个一致决策系统；在在& 中，对于 坛，y 以若x y 且 ，y ) i n d ( a ) 则有撒) ，称& 是一个全不一致决策系统【9 】。 例1 3对于表1 2 所示的不一致决策系统，可以分解为以下两个子系统分别如表1 3 和1 4 所示： 表1 3一致决策系统 定义1 1 1 3 】设s 为一决策系统，v a e a 瓦如果 p o s a r ( d ) = p o s a r - 口 ( d ) ， ( 1 3 3 ) 则称a 为彳丁中环必要的，否则称口为a t 中秘要的。 定义1 1 2 3 设s 为一决策系统，如果对于v a e a l 口为彳丁中秘要的，则称属性集钔r 为融立的( 黝瑚对于抛立) ，否则椭功拥依的。 定义1 1 3 t 3 】设s 为一决策系统，彳丁中所有秘要的属性组成的集合称为彳r 的獭，简称 为相对核，记为c o r e 爿r ( d ) 定义1 1 4 t 3 1 设s 为一决策系统，a _ c a t , 若满足 1 ) p o s a r ( d ) = p o s a ( d ) ； 2 ) 么相对于抛立； 则称彳黝r 的一个锄简。 定理1 5 3 1 设s 为一决策系统，则 三 c o r e a r ( d ) 5f 1a( 1 3 4 ) i f f i l 其中中彳l f ( 1 i s ) 表示彳r 的所有蹦简。 l o 博士论文不完备信息系统中粗糙集理论研究 1 4本文的研究背景及主要内容 1 4 1研究背景 经典粗糙集理论是建立在等价关系基础上的，等价关系要求满足自反、对称和传 递性，因而要求较为严格。根据等价关系的特性，经典粗糙集一般可用来处理具有离 散属性值的完备信息系统，即信息系统中的所有属性值都是知道并且是确定的。然而 值得注意的是，在现实世界中由于各种原因，数据库管理人员经常会遇到数据缺损情 况。例如，根据传感器获取故障诊断信息，若由于传感器故障或数据传送堵塞等原因， 就无法及时地获取获得有用的数据，这种情形在医学诊断，供应链管理及交通管理等 众多领域都是不可避免的。因而如何使用粗糙集理论处理具有缺损数据的信息系统， 对于粗糙集理论的发展具有极其重要的意义，同时这也是进一步将粗糙集理论推向实 用的关键步骤之一。本文将具有缺损数据的信息系统称为不完备信息系统，这种不完 备信息系统正是本文的主要研究对象。 1 4 2主要研究内容 本文在不完备信息系统中，以知识获取为目的，以粗糙集理论为数学工具，对不 完备信息系统中的各种拓展粗糙集模型进行了研究。主要内容总结如下： 1 ) 当不完备信息系统中所有的未知属性值都是缺席型时，提出了差异关系及基于差 异关系的粗糙集模型，据此可以用来获取不完备决策系统中的否定规则； 2 ) 在不完备信息系统中提出了可变精度分类粗糙集模型的概念，证明了基于容差关 系、非对称相似关系的粗糙集模型是可变精度分类关系粗糙集模型的特例； 3 ) 在同时具有遗漏型和缺席型未知属性值的广义不完备信息系统中，分析了原有特 征关系分类的不足之处，进而提出了3 种不同形式的特征关系，并对基于不同特 征关系的粗糙集模型进行了对比分析； 4 ) 在具有遗漏型未知属性值的不完备信息系统中，提出了t 和、【描述子的概念，讨论 了如何求得t 和、 约简描述子的分辨矩阵方法，相对于原有的扩展优势关系来说， 使用t 和上描述子的概念，不仅可以消除决策规则中的未知属性值，还可以获得包 含更为丰富信息的决策规则； 5 ) 在具有缺席型未知属性值的不完备信息系统中，提出了相似优势关系的概念，相 似优势关系融合了传统非对称相似关系和优势关系的特性，是这两种关系的广义 化表现形式；根据基于相似优势关系的粗糙集模型，提出了几种近似分布约简的 概念； 6 ) 将基于相似优势关系的粗糙集模型引入不完备模糊决策系统中，进而讨论了知识 约简与最优规则获取的问题； l 绪论博士论文 7 ) 由于区间值也代表了一种形式的不完备信息，因而研究了区间值信息系统中的优 势关系粗糙集模型问题。在区间值信息系统中，不仅提出了6 种形式的相对约简 以获取最优决策规则，而且进一步考虑对象与对象之间的优势程度，据此构建了 模糊粗糙集模型以进行区间值信息系统中的知识获取。 1 4 3本文组织结构 全文共分七章。 第一章绪论 概述了粗糙集理论的、发展历程，介绍了其基本理论和方法，阐述了本文的研究 背景和研究内容。 第二章不完备信息系统 在不完备信息系统中提出了基于差异关系，可变精度分类的粗糙集模型；分析了 集值信息系统中基于不同二元关系的粗糙集模型的关系。 第三章广义不完备信息系统与特征关系 对于同时具有遗漏型和缺席型未知属性值的广义不完备信息系统，提出了3 种不 同形式的特征关系及相应的粗糙集模型。 第四章不完备信息系统中的扩展优势关系与最优可信规则 在具有遗漏型未知属性值的不完备信息系统中，提出了t 和j ，描述子的概念，讨论 了如何根据t 和i 描述子获取不完备决策系统中的最优“a tl e a s t ”和“a tm o s t ”确定规则。 第五章基于相似优势关系的粗糙集模型 在具有缺席型未知属性值的不完备信息系统中，提出了相似优势关系的概念，根 据基于相似优势关系的粗糙集模型，提出了4 种形式的近似分布约简：在具有缺席型 未知属性值的不完备模糊系统中，研究了基于相似优势关系的粗糙模糊集与知识约简 等问题。 第六章区间值信息系统中的优势关系粗糙集模型 在区间值决策系统中，首先根据优势关系，提出了6 种不同形式的相对约简以获 取简化的决策规则；接着，考虑对象与对象之间的优势程度，将模糊粗糙集模型引入 区间值决策系统以进行知识获取。 第七章结束语 总结了全文并对下一步的研究工作进行了展望。 1 2 博士论文不完备信息系统中粗糙集理论研究 2 不完备信息系统 p a w l a k 所提出的经典粗糙集理论是建立在不可分辨关系( 自反、对称和传递) 的 基础上的，因而主要用来处理具有离散属性值的完备信息系统。然而遗憾的是，在现 实世界中，由于数据测量的误差、对数据的理解或获取的限制等众多原因，所面临的 信息系统往往是不完备的。因此，如何使用粗糙集理论从不完备信息系统 2 6 - 3 5 】 ( 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 ，简称l i s ) 中挖掘知识对于粗糙集的发展具有举足轻 重的作用。 目前利用粗糙集数学模型处理i i s 的常用手段有2 种： 1 ) 间接处理【3 6 1 ，这种方法有两种情形：第一种情形是删去带有未知值的实例，但是 这将会丢失数据中很多有用的知识；第二种情形是通过一定的方法把不完备信息 系统转化为完备信息系统，即数据补齐，但是，补齐处理只是将未知值补以我们 的主观估计值，这或多或少改变了原始的信息系统中的信息分布，因此不一定完 全符合客观事实； 2 ) 直接处理，其特点是对经典粗糙集理论中相关概念在不完备信息系统下进行适当 扩充。 值得注意的是由于间接处理方法会损害到数据的原有分布特征，挖掘出的规则往 往带有不确定性