（控制科学与工程专业论文）不完备模糊决策信息系统粗糙集模型与知识约简研究.pdf

博士论文不完备模糊决策信息系统租糙集模型与知识约简研究 摘要 本文以不完备模糊决策信息系统为主要研究对象，以粗糙集与模糊集理论为工 具，以知识约简为目的，在对不完备信息系统粗糙集扩展模型与知识约筒研究的基础 上，进一步研究了不完备模糊决策信息系统的粗糙集模型与知识约简，并开发了一 个基于不完备模糊决策信息系统知识约简算法的原型系统。主要成果与创新点如下： 1 在不完备信息系统与完备模糊决策信息系统的基础上，给出了不完备模糊决 策信息系统的概念；进一步研究了基于相容关系、非对称相似关系、限制容差关系 和包含度的不完备模糊决策信息系统粗糙集模型与知识约简 2 提出了改进型相容关系、，一相容关系、对称相似关系及其在不完备信息系统 与不完备模糊决策信息系统的粗糙集摸型与知识约简。 3 提出了不完备模糊决策信息系统的可变粗糙集模型与知识约筒，它是基于一 般二元关系的粗糙集模型，相容关系、( 非) 对称相似关系、限制相容关系、改进型 相容关系、量化( 限制) 容差关系、y 一相容关系等都可作为其特殊情形基于包含 度的思想，研究了不完备模糊多决策信息系统的租糙集模型；借助于( 上、下) 分布 协调约简、最大( 小) 分布约简，讨论了不完备模糊多决策信息系统的知识约简。 4 研究了不完备模糊决策信息系统中各类粗糙集模型的性质，并对模型进行比 较。其结果是：限制容差关系与改进相容关系的粗糙集模型是对相容关系的租糙集模 型的严格，对称相似关系的粗糙集模型是对限制容差关系的租糙集模型的严格，而非 对称相似关系的粗糙集模型是对对称相似关系的租糙集模型的严格；，一相容关系的 粗糙集模型是相容关系粗糙集模型在有效可变参数意义下的推广；可变粗糙集模型与 包含度下的租糙集模型是更一般意义下的不完备模糊决策信息系统租糙集模型。针对 各种粗糙集模型的知识约简，主要考虑了精度约简算法、( 上、下) 协调约简算法、 最大( 小) 分布约简算法和分辨矩阵算法等四种。从研究的结果看，协调约简算法、 最大( 小) 分布约简算法适合各种相糙集模型的知识约简，其时间复杂度都与 d ( 1 a j 3 1 【，f ) 同阶；但分辨矩阵算法不一定都可行，只适合基于相容关系，非对称相 似关系和对称相似关系粗糙集模型的知识约简。 5 开发了一个不完备模糊决策信息系统知识约简原型系统，并对本文提出的部 分算法进行了验证和测试 关键词：粗糙集模糊集不完备信息系统不完备模糊决策信息系统知识约简 博士论文 不完备模糊决策信息系统粗糙集模型与知识约简研究 a b s t r a c t r o u g hs e tm o d e l sa n dk n o w l e d g er e d u c t i o n sf o ri n c o m p l e t ea n df u z z yd e c i s i o n i n f o r m a t i o ns y s t e mo f d i si ns h o r t ) 勰s y s t e m a t i c a l l ys t u d i e di n t h i sd i s s e r t a t i o no nt h e b a s i so fr e s e a r c h e so l le x t e n d e dm o d e lo fr o u g hs e ta n dk n o w l e d g er e d u c t i o nf o r 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 ，w i t hi f d i sa st h em a i nd i s c u s so b j e c t r o u g hs e tt h e o r y a n df u z z ys e tt h e o r ya st o o l s a n dk n o w l e d g er e d u c t i o na so b j e c t i v e ap r o t o t y p es y s t e mo f k n o w l e d g er e d u c t i o n s f o ri f d i si sd e v e l o p e db a s e do nt h ev a r i o u sa l g o r i t h m s n 圮 d f i m a r yc o n t r i b u t i o n sa g e 丛f o l l o w s ： 1 1 1 地c o n c e p to fi f d i si sp r o p o s e db yt h ed e f i n i t i o n so fi n c o m p l e t ei n f o r m a t i o n s y s t e ma n dc o m p l e t ef u z z yd e c i s i o ni n f o r m a t i o ns y s t e m 1 1 圮r o u g h s e tm o d e l sa n d k n o w l e d g er e d u c t i o n s ，b a s e do nt o l e r a n c er e l a t i o n , n o n - s y m m e t r i c a ls i m i l a r i t yr e l a t i o n , l i m i t o dt o l e r a n c er e l a t i o na n di n c l u s i o nd e g r e e , a l ef t l r t h e rs t u d i e d 2 i m p r o v e d - t o l e r a n c er e l a t i o n , ，一t o l e r a n c er e l a t i o n a n ds y m m e t r i c a ls i m i l a r i t y r e l a t i o na r es u g g e s t e d ；r o u g hs e tm o d e l sa n dr e d u c t i o n sf o ri n c o m p l e t ei n f o r m a t i o n s y s t e ma n di f d i sb a s e d0 1 1t h e s er e l a t i o n sa r es t u d i e d 3 v a r i a b l er o u g hs e tm o d e la n dk n o w l e d g er e d u c t i o nf o ri f d i sa l ep r o p o s e d 1 1 v a r i a b l er o u g hs e tm o d e li sb a s e do nt h eg e n e r a lb i n a r yr e l a t i o n , t h u st o l e r a n c er c l a d o n , n o n - s y m m e t r i c a l ( s y m m e t r i c a l ) s i m i l a r i t yr e l a t i o n , l i m i t e d t o l e r a n c e r e l a t i o n , i m p r o v e d - t o l e r a n c er d a t i o mv a l u e dl i m i t e dt o l e r a n c er e l a t i o na n d ，一t o l e r a n c e r e l a t i o n m a yb ec o n s i d e r e da si t ss p e c i a lo a s e s i n c l u s i o nd e g r e e - b a s e dr o u g hs e tm o d e lf o ri f d i s i sd e f i n e d , a n dk n o w l e d g er e d u c t i o n s ，b a s e do n ( u p p e r , l o w e r ) d i s t r i b u t i v ec o m p a t i b l e r e d u c t i o na n dm a x i n l u m ( m i n i m u m ) d i s t r i b u t i v er e d u c t i o n , a r es t u d i e d 4 1 1 坞p r o p e r t i e so fv a r i o u sr o u g hs e tm o d e l sa l er e s e a r c h e da n da l lm o d e l sa l e c o m p a r e dw i t he a c ho t h e r , w h i c hb r i n gt h ec o n c l u s i o n s ：t h ei m p r o v e d - t o l e r a n c er e l a t i o n a n dl i m i t e dt o l e r 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 sa r em o r er i g o r o u st h a nt o l e r a n c e r e l a t i o n - b a s e dr o u g hs e tm o d e l , n o n - s y m m e t r i c a ls i m i l a r i t yr e l a t i o n - b a s e dm o d e li sm o 糟 r i g o r o u st h a ns y m m e t r i c a ls i m i l a r i t yr e l a t i o n - b a s e dm o d e lw h i c hi sm o r er i g o r o u st h a n l i m i t e dt o l e r a n c er e l a t i o n - b a s e dm o d e l r o u g hs e tm o d e lb a s e do n ，- t o l e r a n c ei st h e g e n e r a l i z a t i o no ft o l e r a n c er e l a t i o n - b u s e dr o u g hs e tm o d e lu n d e rv a l i dp a r a m e t e r b o t h v a r i a b l er o u g hs e tm o d e la n di n c l u s i o nd e g r e e b a s e dr o u g hs e tm o d e la r eg e n e r a lr o u g hs e t m o d e l sf o ri f d i s f o u ra l g o r i t h m sf o rv a r i o u sk n o w l e d g er e d u c t s - a r cm a i n l ys t u d i e d ： p r e c i s i o nr e d u c t i o na l g o r i t h m , ( u p p e r , l o w e r ) c o m p a t i b l er e d u c t i o na l g o r i t h m , m a x i m u m ( m i n i m u m ) d i s t r i b u t i v er e d u c t i o na l g o r i t h ma n dd i s c e r n i b i l i t ym a t r i xa l g o r i t h m r e s u l t s s h o wt h a tp r e c i s i o nr e d u c t i o na l g o r i t h m , c o m p a t i b l er e d u c t i o na l g o r i t l m aa n dm a x i n m m ( m i n i m u m ) d i s t r i b u t i v er e d u c t i o na l g o r i t h ma r es u i t a b l ef o ra l lk n o w l e d g er e d u c t i o n s w h o s ec o m p u t a t i o n a lc o m p l e x i t i e sa r ea l m o s t 硼爿r iu f ) ，w h i l ed i s c e r n i b i l i t ym a t r i x a l g o r i t h mi so n l ys u i t a b l ef o rk n o w l e d g er e d u c t i o n sf 研巧d i sb a s e do nt o l e r a n c er e l a t i o n a b s t r a c t 博士论文 a n dn o n - s y m m e t r i c a l ( s y m m e t r i c a l ) s i m i l a r i t yr e l a t i o n 5 ap r o t o t y p es y s t e mo fk n o w l e d g er e d u c t i o n sf o ri f d i si sd e v e l o p e db a s e do nt h e a b o v e m e n t i o n e dv a r i o u sa l g o r i t h m s ，a n ds o m eo f t h ea l g o r i t h m sa r ev a l i d a t e d k e y w o r d s ：r o u g hs e t f u z z ys e t 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 i f d i s k n o w l e d g er e d u c t i o n 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 沙叼年d f 月莎1 3 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：弛川年口，月日 博士论文不完各模糊决策信息系统粗糙集模型与知识约简研究 1 绪论 1 1 本文研究的背景与意义 从2 0 世纪9 0 年代以来，由于计算机技术的迅速发展，大规模数字网络的普遍使 用，使人们更容易、更方便、更廉价地获取和存储数据，许许多多的数据库被用于科 学研究、技术开发、企业管理、政府办公等，这种态势仍将持续发展下去，进而导致 各个领域的数据急剧增长。于是就出现了一个新的难题：在这被称之为信息爆炸的时 代，信息过量几乎成为人人面对的问题一方面大量的数据成为包袱，甚至成为 垃圾，人们被数据淹没；而另一方面，人们却找不到自己所需要的信息，忍受着缺乏 “知识”的煎熬。怎样才能不被这大量的信息所束缚，从中及时发现有用的信息，提 高信息的利用率? 当然，人们希望通过分析和处理数据，得到隐藏的有价值的重要信 息，支持各类智能决策。但是由于这些数据是海量的，传统的数据库技术、统计技术 及其相结合的方法都无法从这杂乱无章的、强干扰的海量数据中挖掘出潜在的、新颖 的、正确的、有用的知识：并且由于人类的参与使得数据的不确定性更加显著，数据 中的关系更加复杂，这给智能信息处理提出了严峻的挑战。在这样的背景之下，人工 智能研究中的一个崭新领域数据挖掘d m ( d a t am i n i n g ) 和数据库知识发现k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 1 , 2 1 技术就应运而生并蓬勃发展。 d m 和k d d 都是从大量数据中提取可信的、新颖的、有效地、并最终能被人们 理解的模式的处理过程吼。这些原始数据可能是不确定的，即不完全的、模糊的、随 机的和有噪声的；也可能是结构化的、半结构化的，甚至是分布在网络上的异构型数 据。发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可以是归纳 的。基于数学方法的k d d 技术，使用着不同的数学工具，有基于网络结构的神经网 络算法，基于训练选优的遗传算法，基于统计理论的数据挖掘与支持向量机方法，基 于归纳学习的机器学习方法，基于范例的推理方法，基于生物信息的知识发现方法【2 】， 基于粗糙集理论的数据分析法等。 粗糙集理论成为知识发现的一种工具，在较短的时间内得到了广泛的应用并取得 相当的成功，其原因是在处理不确定性问题上具有很多优点：( 1 ) 粗糙集理论不需要 任何预备的或额外的数据信息，即先验性知识，可以直接对数据进行处理；( 2 ) 粗糙 集理论提供了一套严格的数学方法对样本进行分类，进而消除冗余的属性；( 3 ) 粗糙 集理论分析隐藏在数据中的事实时，不会校正数据的不确定性，但可以产生简洁准确、 易于验证的确定的或可能的规则知识；( 4 ) 基于粗糙集理论的算法容易在并行计算机 上运行，适合大规模数据库知识发现的需要1 4 , 5 1 基于粗糙集理论的k d d 研究对象是信息系统( - - 维数据表) ，最基本的概念是 第一章绪论博士论文 不可分辨关系( 等价关系) ，即由相同信息所标识的对象是不可分辨的。在此基础上， 引入上近似集和下近似集分别刻画知识的确定性和可能性，引入边界集来描述知识的 不确定性与模糊性，引入约简与求核等方法对知识进行约简。而知识约简已成为利用 粗糙集理论进行数据分析的基本任务。传统的租糙集理论研究的对象是没有数据缺省 的完备信息系统，其知识约简是在基于不可分辨关系的前提下确保分类不变而消除冗 余的属性。然而，在现实世界中，由于各种各样的原因，常常使得系统中某些数据缺 省，即存在不完备的信息系统。此时粗糙集理论必须要进行扩充。目前，针对不完备 信息系统，粗糙集理论扩充主要有两类方法：一类是通过领域专家把所缺的数据补齐， 间接地将不完备信息系统转化为传统的粗糙集理论能够处理的完备信息系统( 称为间 接法) 6 - i o 】；另一类是直接把粗糙集理论中的相关概念在不完备信息系统中进行适当 的扩充( 称为直接法) 。直接法较之于间接法而言，没有领域专家主观因素的参与， 更具有客观性，因此引起了许多学者的极大必趣，其研究结果令人满意。比如， k r y s z k i e w i c zm 提出了基于相容关系( 也称为容差关系) 的粗糙集扩展模型【l l ，1 2 】， s t e f a n o w s k ij 等人u 3 - 1 5 】提出了基于非对称相似关系和量化容差关系的粗糙集扩展模 型，王国胤提出了基于限制容差关系的粗糙集扩展模型l 。 在不完备信息系统中，还存在这样一类问题：不仅系统中的数据有缺损的，而 且决策( 目标) 是模糊的情形。这类问题在现实中更加普遍，本文把它称为不完备模 糊决策信息系统i f d i s ( i n c o m p l e t ea n df u z z yd e c i s i o ni n f o r m a t i o ns y s t e m ) 。对此， 人们既需要对海量数据进行有效的理解和分析，同时要对不完备信息进行操作处理， 还要考虑对模糊决策的要求，因此，不完备模糊决策信息系统的粗糙集模型和知识约 简的研究具有重要的理论和实际意义。 本文将在前人对不完备信息系统粗糙集模型及其知识约简研究的基础上，继续 研究不完备信息系统的粗糙集扩展模型及其约简方法；并进一步将粗糙集理论从不完 备信息系统扩展到不完备模糊决策信息系统中去，根据不同的要求，建立其粗糙集扩 展模型，并研究其相应的约简方法。这些研究将极大地丰富租糙集理论的内涵，又将 促使粗糙集理论向应用性方向发展，从而为拥有海量数据的不完备模糊决策信息系统 的数据挖掘奠定坚实基础。 1 2 粗糙集理论概述 1 2 1 粗糙集理论发展与研究现状 2 0 世纪7 0 年代初期，波兰数学家z p a w l a k 和华沙大学、波兰科学院的科学家 们对信息系统逻辑特性进行了深入的基础研究，针对从试验中得到的并以数据形式表 达的不精确、不确定、不完整的信息和知识进行了分类分析，其研究成果就是粗糙 集理论产生的源泉。1 9 8 2 年z p a w l a k 在此基础上，提出了粗糙集理论，它是一种处 2 博士论文不完备模糊决策信息系统粗糙集模型与知识约简研究 理不精确、不确定和不完全数据的非经典数学理论。由于当时关于粗糙集理论的文章 大部分是用波兰语发表的，因此没有引起国际计算机和数学界的重视，研究的地域也 仅局限于东欧一些国家，直到2 0 世纪8 0 年代末才引起世界各国学者的注意。近几年 来，由于它在机器学习【1 7 - 2 2 l ，知识发现 2 3 - 2 a 1 、数据挖掘【6 7 , 2 9 - 3 7 1 、决策支持与分析1 8 ， 3 8 - 4 2 1 、近似推理f 4 3 州等方面的广泛应用，成为当前计算机科学、人工智能以及信息科 学等领域研究的热点之一 1 9 9 1 年p a w l a k 教授第一本粗糙集专著 4 3 1 和1 9 9 2 年s l o w i n s k i 粗糙集论文集嗍 的出版，奠定了粗糙集理论的基础，推动了国际上对粗糙集理论和应用的深入研究。 1 9 9 2 年在波兰k i e k r z 召开了第一届关于粗糙集理论的国际学术会议，并成立了国际 r o u g hs e t 学会( i r s s ) ，这次会议主要讨论集合近似定义的基本思想与应用，以及粗 糙集环境下的机器学习的基础研究；从此以后，每年召开一次以粗糙集研究为主要内 容的国际学术会议。到目前为止，已先后在波兰，加拿大、美国、日本、中国、瑞典 等国家举办过关于粗糙集的国际研讨会，波兰华沙大学、工业大学、信息技术与管理 大学和o p o l e 大学、加拿大r e g i n a 大学和圣玛丽大学、日本s h i m a n em e d i c a l 大学、 英国e d i n b u r g h 大学、u 1 s t e r 大学和c a r d i f f 大学、意大利c a t a n i a 大学、印度统计研 究院、美国s a nj o s e 州立大学等对粗糙集理论有着深入研究。如今，美国、波兰、加 拿大、日本等国都建立了粗糙集研究的专门机构。以r o u g h 集为主题的国际期刊l n c s t r a n s a c t i o n so nr o u g hs e t s 也正式出版。这一系列工作，进一步推动了粗糙集理论和 应用的发展。在国内，2 0 0 3 年，第九届国际粗糙集、模糊集、数据挖掘与粒度计算 学术研讨会在重庆召开。2 0 0 5 年7 月，以粗糙集理论为主要内容的首届国际粒度计 算大会在清华大学召开。2 0 0 6 年7 月，第一届粗糙集与知识技术( r s k t ) 国际学术 会在重庆召开。从2 0 0 1 年以来，粗糙集与软计算学术研讨会已经连续举办了六届， 分别在重庆、苏州、重庆、舟山、鞍山和金华召开；中国人工智能学会已于2 0 0 3 年 1 1 月成立了粗糙集与软计算专业委员会。清华大学、上海交通大学、西安交通大学、 南京大学、同济大学、武汉大学、南昌大学、复旦大学、浙江大学、哈尔滨工业大学、 香港城市大学、合肥工业大学、四川师范大学、重庆邮电大学、浙江海洋学院、山西 大学和中国科学院自动化研究所等大学和研究机构对租糙集理论有较为深入的研究， 有些高校，如西安交通大学形成了从硕士、博士到博士后的一支研究梯队。在粗糙集 理论研究的初期，研究人员大多来自数学和计算机科学领域；但随着租糙集理论的广 泛应用，越来越多的其它领域，如信息科学、系统科学、管理科学、控制科学等领域 的学者参与。从研究地域来看，欧洲学者比较注重理论研究，北美比较注重应用，日 本在粗糙集与概率论相结合方面以及在环境、医学的应用上比较突出；我国学者在粗 糙集扩展模型，公理化体系、知识约简、与信息论的结合、粗糙逻辑、粒计算、知识 的不确定性等方面的研究取得了较大成功，在粗糙集理论某些方面的研究水平己接近 国际同行的先进水平1 4 7 1 3 第一章绪论博士论文 粗糙集理论的研究由于其历史较短，所以至今为止，对粗糙集概念的定义还没有 完全统一，有原始的p a w l a k 意义下的，也有由上、下近似构成的一对集合来命名的， 还有以下近似和上近似构成的区间集合来定义的。定义观点的不同往往带来研究的侧 重面的不同。目前，对租糙集理论的研究主要集中在以下几个方面【4 s o l ：( 1 ) 粗糙集 模型的推广，这方面的研究一直是粗糙集理论研究的主流，主要有构造性方法和公理 化方法，其中也包括连续属性的粗糙集模型、变精度租糙集模型和不完备粗糙集模型； ( 2 ) 不确定性问题的理论研究；( 3 ) 与其他处理不确定性方法的理论研究，主要集 中在与概率统计、模糊数学、证据理论和信息论的相互渗透与互补；( 4 ) 纯数学理论 方面的研究；( 5 ) 粗糙集理论的有效算法研究，主要集中在规则提取的增量式算法、 属性约简的启发式算法、一般算法、并行算法以及与粗糙集有关的神经网络与遗传算 法等；( 6 ) 粒计算与粗计算；( 7 ) 与机器学习、人工智能中其它方向( 如神经网络、 智能决策、遗传算法和智能计算等) 关系的研究。这些研究有的是受应用的推动而产 生的，有的是纯理论发展的要求。 1 2 2 粗糙集理论的特点 粗糙集理论作为一门新兴的数学工具，在较短的时间内得到迅速的发展和广泛的 应用，是因为它在处理不精确、不确定和模糊性方面具有众多的特点。 粗糙集理论是建立在分类机制的基础之上的，它将分类理解为在特定空间上的等 价关系，而等价关系构成了对该空间的划分。将知识理解为对数据的划分，每一被划 分的集合称为概念。粗糙集理论的主要思想是利用已知的知识库，将不精确或不确定 的知识用已知的知识库中的知识来近似刻画。该理论与其他处理不确定和不精确问题 理论的最显著的区别在于它无需提供问题所需处理的数据集合之外的任何先验信息， 所以对问题的不确定性描述或处理可以说是比较客观的。由于这个理论未能包含处理 不精确或不确定原始数据的机制，所以这个理论与概率论( 需要知道概率分布) 、模 糊数学( 需给定隶属函数) 和证据理论( 需要信度函数) 等其他处理不精确或不确定 问题的理论有很强的互补性1 4 0 i ；另外粗糙集理论还可以从不同的抽象层次对数据建模 和分析，以便更好地揭示数据间的依赖关系，发现数据间的规律【4 j 。 1 3 粗糙集理论的基本概念 1 3 1 信息系统 。 信息系统是粗糙集理论研究的主要对象，通常用一个数据表来表示。 定义1 1 称s = ( u ，a ，矿，) 是一个信息系统，或者数据库系统。其中u 是非空的 对象集，即u = 如，而，矗 ，u 中的每个薯o 玎) 称为个对象；a 是非空的属性集， 即彳= “，吗，) ，一中的每个吩( _ ，历) 称为一个属性；，是u 和一的关系集，也 4 博士论文不完备模糊决策信息系统粗糙集模型与知识约简研究 称信息函数集，即f = i j 分别称为x 关于近似空闻( u ，r ) 的上近似集与下近似集。 定义1 4 说明：曼( x ) 是包含于x 中的最大r 精确集，它是由知识月判断肯定属 于x 的u 中对象组成的集合；而r ( x ) 是包含x 的最小r 精确集，它是由知识r 判断 可能属于工的u 中对象组成的集合。 集合b n r ( x ) = r ( x ) - r _ ( x ) 称为工的r 边界( 域) ；p o s r ( x ) = 星( 工) 称为z 的r 正域；n e g r ( x ) = u r ( z ) 称为x 的尺负域。 显然，巩( 幻，p o s r ( x ) 和n e g , ( x ) 都是r 精确集；r ( x ) = b n r ( z ) u 星( 朋； 边界域中的元素可能属于x 也可能不属于z ，当b n r ( x ) 时，j 为粗糙集，否则， z 为精确集；正域中的元素必属于x ；负域中的元素一定不属于z 。 上近似集和下近似集有如下性质。 定理1 1 设( u ，盖) 是p a w l a k 近似空间，x ，y c _ u 。则： ( 1 ) 星( ) = 置( 妒) = 妒；星( = 胄( u ) = u ，表示空集。 ( 2 ) 豇：j ) z r ( 幻 ( 3 ) r ( x u y ) = r ( 柳o r ( y ) ；_ r ( x n 】，) = 星( 柳n 星( y ) 。 ( 4 ) 豇x u d 2 星( z ) u 豇y ) ；r ( x n d r ( x ) n r ( d 。 ( 5 ) x y 毒型聊曼( d ；r ( a o 量r ( y ) 。 ( 6 ) r ( r ( z ) ) = 星( 五( ：j ) ) = 胄( x ) ；胄( 墨( r ) ) = 星( 星( x ) ) = ：6 1 ( x ) 。 ( 7 ) 页( z 。) = 馑( ) 。；星( j ，c ) = ( 飘_ ：i ) ) 。，表示x 的余集。 以上性质在大部分粗糙集专著中都有证明，此处从略。 r o u g h 集的不可定义性( 不确定性) 是由于边界的存在而引起的，集合并的边界 越大，其不确定性也越大，确定性就越小，从而精确性也就越低，粗糙性越大。下面 引入集合x 的粗糙性与近似精确性的准确描述。 定义1 5 设( 【，胄) 是p a w l a k 近似空间，z u 。集合x 的粗糙度定义为 p r ( x ) = l 删j ( 柳i i r ( 幻i = 1 - l 豇柳i t r ( l ， 集合x 的近似精度定义为 ) = 陋( 柳i 似( 柳| - 1 - 岛( 的 其中x 妒，j x j 表示集合z 的基数；如果j = ，定义( 幻= l 。 6 博士论文不完备模糊决策信息系统租糙集模型与知识约简研究 显然，0 a r ( x ) ，岛( 肖) 1 ；当( x ) = l ，j 的r 边界域为空，集合是足可 定义的：当( j ) 表示对象集，彳= 他，吒9o 0 0 9 表示属性集，= ，所 是信息函数集，对4 中的每个口，u ，1 ) ，有，( 而) 声，毛u ，i s 。这一假设看 似合理，但与现实又有很大的差异。在实际情况中，常常由于某种原因，一部分属性 值不可能得到，即遗漏( m i s s i n g ) 或缺席( a b s e n t ) ，这就出现这样一种情况一属性 对每个对象的描述是不完全的，即对某个口，和五有，( ) = 妒。 设s = ( 玑4 ，以乃是一个信息系统，其中u 是对象的非空集合，彳是条件属性集 合，对于每个a 彳有，：( ，_ 圪，f f ，圪为a 的值域，矿= ur o 艇 定义1 1 4 若至少有一个属性a e b 彳使得圪含有空值( n u l lv a l u e ) ，则称s 是 一个不完备信息系统，用木表示空值；否则称为完备信息系统。在不致引起混淆的情 况下，完备信息系统与不完备信息系统都用s = ( u ，爿，以f ) 表示。 定义1 1 5 设r ( 功= 瓴y ) u x u ：v b e e 6 ( 功= b ( y ) v b ( x ) = * v b ( y ) = ) ，其中 l o 竖主堡兰至塞查堕塑盗苎笪星墨竺塑堡壁型兰塑堡丝笪! 壅 b a ，则t ( b ) 称为m k r y s z l d e w c z 的一个相容关系，简称为相容关系【1 1 ，嘲。 令瓦0 ) = 抄u ：0 ，y ) 丁( 曰) ，则五o ) 表示在相容关系下u 中与x 可能不可区 分的对象的最大集合。 令- u t ( b ) = 乃 ) ：工u 表示分类，u t ( b ) 中的元素o ) 称为x 的相容类。 u t ( b ) 中的相容类一般不构成u 的划分，但构成u 的覆盖，即u u t ( b 1 = u 。 显然，有：r ( 口) 5 q r ( 6 ) ，且相容关系具有自反性，对称性，但不具有传递性 从定义1 1 5 知，同一相容类中元素在相同属性下的属性值要么相等要么为空值， 即空值与任意属性值相等。 一 1 3 4 2 分辨矩阵 定义1 1 6 设s = ，a ，矿，f ) 是不完备信息系统，b c _ a ，t ( b ) 是论域 u = “，而9 0 0 ，毛) 上的相容关系，瓦( 力是x 的相容类。则： g = ( g ) 。 称为系统s 在相容关系下的分辨矩阵，其中 q 篁 q a i q ( 毛) q ( x j ) a a ，( x j ) q ( ) 称为对象五与石，的可分辨属性集。 定理1 4 分辨矩阵与可分辨属性集具有以下性质： ( 1 ) q = ( v i 行) ，即分辨矩阵主对角线上元素为。 ( 2 ) q = c ，o ，j s 功，即分辨矩阵是对称矩阵。 ( 3 ) 若五与属同一个相容类，则g = ；否则q 妒。 1 3 5 模糊集的粗糙近似 1 3 5 1 模糊集合 定义1 1 7 设给出论域u 上的映射 矿：c ，斗【o ，1 】， 或x 专r r ( x ) ，i e u 则形称为u 上的一个模糊集合，简称为f ( f u z z y ) 集，矿( x ) 为工的隶属函数。用f ( 表示u 上的f 集的全体。 设，( u ) ，帆u ，则与的包、并、交、补定义为： 皇( x ) ； ( 形u ) ( j ) = m a x ( 工) ，( 力 ； ( n x x ) = m i n 形( ，( 功) ； 暇。( 曲= 1 - 彤( 第一章绪论博士论文 定义1 1 8 设w f ( u ) ，v 2 o ，1 】。 降：= x u l w ( x ) 五) 称为形的旯一截集；而 = x u i w ( x ) m 称为形的a 一强截集。 1 3 5 2 模糊粗糙集模型1 叫 定义1 1 9 设( u ，r ) 是p a w l a k 近似空间，即r 是u 上的等价关系， x k 表示包含工 的等价类。v w f ( u ) ，模糊集合矿关于，r ) 的上、下近似的隶属函数分别定义 为： r ( 阡7 ) ( 工) = m a x w ( y ) ly 【工】r 星( f 矿) ( 工) = m i n w ( y ) iy 【x 】r ， 则- ( 形) 与曼( ) 分别称为模糊集合矿关于近似空间( u ，r ) 的上、下近似集合；而瓦： ，( 一，( 与垦：f ( u ) 专，( 分别称为上、下近似算子。 当形是经典的c o n t o r 集合时，则有：r ( w x x ) = 1 铮 x l r n 形妒且型形) ( x ) = l 营【x l r 互肜进一步，胄( 矿) = x u ：r ( w x x ) = 1 = x e u ： x r n 矿 ，g r ( w ) = x e u ：盟矽) ( j ) = 1 ) = ，u ：【工k 矽 因此经典集的上、下近似集是模糊集的上、 下近似集的特殊情形。 定理1 5 设( 玑五) 是p a w l a k 近似空间，矽是u 上的f u z z y 集，则形的上、下近 似算子具有如下性质： ( 1 ) 墨( 形) 矿r ( 矿) a ( 2 ) 胄( u w d = r ( 彤) u 矗( ) ，曼( 形n ) = 星( ) f l 豇) 。 ( 3 ) 五( n ) 胄( ) n r ( w d , 烈u ) 型彤) u 豇) 。 ( 4 ) r ( 胄( 矿) ) = 星( 震( 矽) ) = r ( 形) ，置( 豇矿) ) = 墨( 点( 形) ) = 墨( 矿) 。 ( 5 ) _ ( 形。) = ( 星( 形) ) 。，星( 矽。) = ( - ( ) ) 。 其中，e f ( ，矿。为形的余集。 1 3 5 3 模糊近似粗糙度与近似精度i z l 设口，p 【0 ，1 】，w ，( u ) 。令 r ( w ) p = 扛u l r ( 形x 功所， 烈矿) 。= 扛e u l r ( w x x ) 口 。 则以下性质成立： ( 1 ) r ( 矽) ，= u b k l r ( w x x ) 2 r ( ) 。 1 2 博士论文 不完备模糊决策信息系统粗糙集模型与知识约简研究 ( 2 ) 量( 肜) 。= u 【工ki 堡( ) ( 力口) 2 星( 睨) ( 3 ) 若口卢，则且( 形) 口2 星( 形) 。 ( 4 ) 曼( 形) 。睨胄( 矿la 定义1 2 0 设( u ，胄) 是p a w l a k 近似空间，矿是u 上的f u z z y 集，o 口1 ，w 关于( c t ，) 的近似粗糙度与近似精度分别定义为： p ( a ，) = 1 一 ，盯位，) = 并规定：r ( ) 口= 时，p ( a ，) = o a ( a ，) = 1 。 定理1 6 设0 - a l ，矿f ( u ) 。则： ( 1 ) o 盯 ，) ，p ( a ，刃l 。 ( 2 ) 从口，刃关于口不减，关于不增；盯( 盯，) 关于口不增，关于不减。 ( 3 ) 若v x u ，w i = 6 ( 常数) ，则 鹏舻淼 1 3 6 信息系统中的度量关系 为进一步研究的方便，引入一些与信息系统中度量相关的指标。 1 3 6 1 包含度1 2 , 1 4 哪 设z 是集合，称( x ，s ) 是偏序集。若对任意x , y ，z x 满足：( 1 ) 自反性：工x ； ( 2 ) 反对称性：工儿y 工j x = j ，；( 3 ) 传递性：x 茎弘y z j x - z 。 定义1 2 1 设( x ，s ) 是一个偏序集。若对任意x , y ，z x ，存在一个实数0 0 ，力满 足：( 1 ) 0 o o 肛) i ；( 2 ) x s y 1 0 ，x ) = 1 ；( 3 ) x y z j 烈叫z ) s o 纠) ，) 则 称毋是定义在x 上的包含度。 如果z 是u 上的模糊集，则类似于定义1 2 1 的定义如下。 定义1 2 2o 称为定义在模糊集，( u ) 上的包含度，对于任意j ，b , c e ，( u ) ，若 下列各式成立：0 ) 0 - o ( 否j ) s 1 ；( 2 ) j 吾j o ( 彰两= l ；( 3 ) i 吾0 j ( 衫西s 似衫否) 。 例1 1 设u 是非空有限的集合，彳，b ，( u ) ，p 为u 上的一个概率分布，“” 为集合的包含关系。则妒) ，) 为偏序集，且 删= 訾 ( 1 1 ) 第一章绪论 博士论文 a s 舻等 为p ( u ) 上的包含度。 例1 2 设j ，b f ( u ) ，彳为j 的余集。则 n ( 否7 0 = a ( j 。( 工) v 否( 工) ) n ( 彰j ) = y ，( j ( x ) 否( 工) ) 竹( 否7 0 = 等 ( 1 2 ) ( 1 3 ) ( 1 4 ) ( 1 5 ) 为f ( u ) 上的包含度，“a ”与“v ”分别为“取小”与“取大”符号。 1 3 6 2 属性的依赖度与重要度 属性间的依赖关系是数据分析中的重要内容。在无决策的信息系统中，若属性集 c 的属性值完全依赖于属性集b 的属性值，习惯上就称属性集c 完全依赖属性集b ， 记为b 专c 。更一般地有： 定义1 2 3 d 61 设s = ( 爿，u ，以叼是一个完备信息系统，b ，c a 。属性集c 依赖 于属性集b 的程度，即依赖度定义为： 肥c ) = 等掣， 其寺p o s b = 。x 骁k p 岱b q l 定义1 2 4 设s = ，a ，v ，f ；d ，w ，g ) 是决策信息系统，4 是条件属性集，d 是决 策属性集，p a ，q 三d 。则q 对p 的依赖度定义为： 肥q ) = 墚掣 其中p o s e ( q ) = u 砟( 柳为q 的一正域。 定义1 2 5 1 3 6 l 设s = ( u ，a ，v , f ；d ，w ，g ) 是决策信息系统，a 是条件属性集，d 是 决策属性集，条件属性子集csa 关于条件属性