（系统理论专业论文）变精度广义粗糙集模型.pdf

摘要 粗糙集理论是上世纪八十年代初由波兰数学家p a w l a k 首先提出的一种用于 数据分析的数学理论。其主要思想是利用已知的知识或信息来近似不精确的概念 或现象。自上世纪九十年代以来，粗糙集在理论上不断完善，在应用上广泛扩展， 已逐渐成为国际学术界的研究热点之一。 变精度粗糙集是对p a w l a k 粗糙集理论的一种扩充，它通过设置闽值参数 ( 0 5 卢s 1 ) ，放松了对标准粗糙集理论近似边界的严格定义，增强了粗糙集模型 的抗干扰能力和对新数据的预测能力。n ic kc e r c o n e ，w o j c i e c hz i a r k o 等人已利 用此模型成功地对北美一个中等城市的用水需求进行了预测。 本文从p a w l a k 粗糙集、变精度粗糙集的理论入手，主要介绍了作者的三部分 工作： ( 1 ) 讨论了变精度粗糙集模型中卢值与分类质量的关系，给出了由分类质量阈 值睐确定芦取值的两种算法。 ( 2 ) 针对文献 5 4 伸提出的几种属性约简，给出了声上、下分布约简的两种新 的可辨识矩阵，与文献 5 4 】中的可辨识矩阵是等价的。 ( 3 ) 在不同的论域下，讨论了串行的广义近似算子，并将变精度粗糙集模型 推广到不同的论域下来讨论，得到了变精度广义粗糙集模型。 关键词粗糙集理论，变精度粗糙集，分类质量，芦上、下分布约简，可辨识矩 阵，广义近似算子，变精度广义粗糙集 a b s t r a c t r o u g hs e tt h e o r y ，p r o p o s e db yp a w l a ki nt h ee a r ly1 9 8 0 s ，i sa m a t h e m a t ic a lt h e o r yf o rr e a s o n i n ga b o u td a t a t h em a i ni d e ao ft h et h e o r y ist oa p p r o x i m a t ei n e x a c t ，u n c e r t a i nc o n c e p t sb yu s i n go fa v a i l a b l e k n o w l e d g eo ri n f o r m a t i o n s i r i c e1 9 9 0 s ，i th a sa t t r a c t e dm u c ha t t e n t i o n o fr e s e a r c h e r sa r o u n dt h ew o r l d ，a n dh a sb e e nw e l ld e v e l o p e da n da p p l i e d n o w ，t h ist h e o r yh a sb e c o m eaf l a s hp o i n ti nt h er e s e a r c ha r e ao fc o m p u t e r s c i e n c ea n di n f o r m a t i o ns c i e n c e v a r i a b l ep r e c is i o nr o u g hs e ti sa f te x t e n s i o no fp a w l a k r o u g hs e t t h e o r y ，i tr e l a x e st h er e s t r ic t e dd e f i n i n go fa p p r o x i m a t i 0 1 3b o u n d a r yi n s t a n d a r dr o u g hs e tt h e o r ya n di m p r o v e st h ea n t i i n t e r f e r e n c ea b i l i t ya n d p r e d i c t i o i la b i l i t yt ot h en e wd a t ao fr o u g hs e tm o d e lb ys e t t i n gu p t h r e s h 0 1 dv a l u ep a r a m e t e r ( 0 5 卢5 1 ) ，n i c kc e r c o n e ，w o j c ie c hz i a r k oh a v e a l r e a d yu t i l i z e dt h i sm o d e lt op r e d i c tw a r e rd e m a n df o ram e d i u m s i z e d c i t yi nn o r t ha m e r i c as u e c e s s f u l l y t h isp a p e rb e g j n sw i t hp a w l a k r o u g hs e ta n dv a r i a b l ep r e c is i o nr o u g h s e tt h e o r y ，t h e ni n t r o d u c e st h r e em a i np a r t so ft h ea u t h o r sw o r k t h e y a r e ： ( 1 ) i t a n a l y s e s t h er e l a t i o nb e t w e e n芦v a l u ea n dq u a l i t yo f c l a s s i f i e a t i o ni nv a t i a b l ep r e c i s i o i lr o u g hs e t 。a n dp r o v i d e st w ok i n d s o fa l g o r i t h m st oc o n f i r mt h er a n g eo f 芦t h r e s h 0 1 dv a l u eb yt h ert h r e s h o l d v a l u eo fq u a li t vo fo l a s s i f i c a t i o l l ( 2 ) i nt h er e f e r e n c e 5 4 ，s e v e r a lk in d so fa r t r ib u t er e d u c t i o nh a y e b e e np u tf o r w a r d ：w ek n o wp r e y i d et w ok i n d so fn e wd is c e r n i b i l i t ym a t r i x o f 芦l o w e ra n du p p e rd i s t r i b u t i o f fr e d u c t i o n w h i c ha r ee q u i v a l e n c et o d i s c e r n i b i l i t ym a t r i xi nt h er e f e r e n c e 5 4 ( 3 ) i td is c u s s e ss e r i a lg e n e r a l iz e da p p r o x i m a t io no p e r a t o r se v e r d i f f e r e n tu n i v e r s e sa n dt h ev a r i a b l ep r e c i s i o nr o u g hs e tm o d e lo v e r d i f f e r e n tu n iv e r s e st h e ng e t st h ev a r i a b i ep r e c i s i o ng e n e r a l iz e dr o u g h s e tm o d e l k e yw o r d sr o u g hs e tt h e o r y ，v a r i a b l ep r e c is i o nr o u g hs e t ，q u a l i t yo f c l a s s i f ic a t i o n ，卢u p p e ra n dl o w e rd is t r i b u t i o nr e d u c “o n ，d i s c e r n i b i l i t y m a t r i x ，g e n e r a l iz e da p p r o x i m a t i o no p e r a t o r s ，v a r i a b 】ep r e c is i o n g e n e r a l i z e dr o u g hs e t 1 l 昆明理工大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下( 或 我个人) 进行研究工作所取得的成果。除文中已经注明引用的内 容外，本论文不合任何其他个人或集体已经发表或撰写过的研究成 果。对本文的研究做出重要贡献的个人和集体，均已在论文中作了明 确的说明并表示了谢意。本声明的法律结果由本人承担。 学位论文作者签名：废慧灰 日期：列对年月，学日 关于论文使用授权的说明 本人完全了解昆明理工大学有关保留、使用学位论文的规定，即： 学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布 论文的全部或部分内容，可以采用影印或其他复制手段保存论文。 ( 保密论文在解密后应遵守) 导师签名：鲁锋论文作者签名：蔓蔓廷 日 期：2 竺兰生f 月 笙旦 第一章绪论 1 1 粗糙集理论的国内外发展现状 粗糙集( r o u g hs e t ，r s ) 作为一种处理不精确、不确定与不完全数据的新的数 学理论，最初是由波兰数学家z p a w l a k 于1 9 8 2 年提出的。它的主要目的是对不 完整数据进行分析、推理，发现数据间的关系，提取有用的特征，简化信息处理， 进而研究不精确、不确定知识的表达、学习、归纳方法等。由于最初关于粗糙集 理论的研究大部分是用波兰语发表的，因此当时没有引起国际学术界的重视，研 究集中在东欧一些国家，直到2 0 世纪8 0 年代末期才逐渐引起各国学者的注意。 1 9 9 1 年z p a w l a k 出版了专著r o u g hs e t s t h e o r e t i c a la s p e c t so fr e a s o n i n g a b o u td a t a 。1 。该著作系统全面的阐述了r s 理论，奠定了严密的数学基础。1 9 9 2 年第一届关于r s 理论的国际会议在波兰召开，以后每年一次。1 9 9 5 年，a c m c 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 i ls c i e n c e s 出版了一期r s 理论研究的专辑。近几年以来，由于它 在机器学习与知识发现、数据挖掘和决策支持与分析等方面的应用，逐渐成为人 工智能领域中一个新兴的学术热点。 目前，国际上基于粗糙集理论的数据分析软件的开发也取得了很大的进步， 比较著名的有以下几种： 美国k a n s a s 大学开发的基于粗糙集理论的学习系统l e r s ( l e a r n i n gf r o m e x a m p l e sb a s e do nr s ) 。 波兰p o z n a n 科技大学开发的r o u g hd a s & r o u g hc l a s s 。 挪威科技大学和波兰华沙大学数学研究所开发的r o s e t t a 系统。 英国u 1 s t e r 信息与软件工程研究所开发的g r o bj a n 。 这些软件的开发使得粗糙集理论作为一种工具被更多的人广泛的使用。 我国对粗糙集的研究虽然起步较晚，但发展迅速。2 0 0 1 年5 月在重庆召开了 中国第一届粗糙集与软计算学术研讨会。2 0 0 2 年9 月在苏州召开了第三届粗糙集 会议。2 0 0 3 年5 月，在重庆召开第九届粗糙集、模糊集、数据挖掘与粒度计算国 际研讨会会议。这对我国粗糙集的研究起到推动作用。粗糙集己逐渐吸引了国内 计算机科学界和数学界的关注，并出版了一些专著。“，引起了越来越多的科研 人员的兴趣”。 1 2 粗糙集理论主要研究方向 目前，对粗糙集理论的研究主要集中在：粗糙集模型的扩展、粗糙集数学性 质的研究、问题的不确定性研究、粗糙逻辑和粗糙推理、以及与其它处理不确定 性、模糊性问题的数学理论的关系等方面。 ( 1 ) 粗糙集模型的扩展 p a w l a k 粗糙集模型的推广一直是粗糙集理论研究的主流方向，文献 9 总结 了目前主要有两种方法一一构造性方法和代数( 公理化) 方法。 关系的推广 经典粗糙集模型的基础是不可分辨关系( 等价关系) ，这个条件是很强的。在 实际生活中，经典的等价关系很难满足。为此，人们从关系的推广出发，提出了 许多粗糙集的扩展模型： 种是将论域上的二元等价关系推广成为相似关系，得到基于相似关系的粗 糙集模型“】，更般的是将论域上的二元等价关系推广成为任意的= 元关系 得到了一般关系下的粗糙集模型n “；另一种是将对象石所在的等价类看成是z 的 一个邻域，从而推广导出了基于邻域算子的粗糙集模型“”；也有将由关系导出的 划分推广成为一般的布尔代数，以此出发来定义粗糙集和近似算子“；还有的是 将普通关系推广成为模糊关系或模糊划分“5 ”1 而获得模糊粗糙集模型。 可交精度模型 经典粗糙集模型的一个局限性是它处理的分类必须是完全正确或肯定的，因 而它的分类是精确的，亦即只考虑完全“属于”与“不属于”，而没有某种程 度上的“属于”或“不属于”。当在数据集中存在噪音等干扰情况下，经典粗 糙集模型的这种局限性会使其对新对象的预测能力大为降低。而在实际应用中， 噪音是在所难免的。为增强粗糙集合模型的抗干扰能力，z i a r k o 提出了一种可 变精度r s 模型“2 ”。该模型通过引入分类精度，使模型具有一定的容错性。n i c k c e r c o n e ，w o j c i e c hz i a r k o 等人已利用此模型成功地对北美一个中等城市的用 水需求进行了预测。 论域的摧厂 在实际情况中，我们经常碰到要在不同的论域下做出一些决策，另外所涉及 的问题中常有数据丢失和信息不完备的情况，因此有必要对粗糙集模型进行进一 步的扩充。w o n g ，w a n g 和y a o 等人“1 给出了在不同论域下的粗糙集模型( 在本文 中称之为广义粗糙集模型) ，这时的二元关系就变成了两个不同论域迪卡尔乘积 的一个y - 集；文献 2 5 ，2 6 提h j 的基于随机集的粗糙集模型也是对论域的推广： 2 ( 2 ) 褪糙集数学性质的研究 r s 数学健震方瑟静研究，主要毒寸论r s 昀代数缤梅、瘀羚结构、毅缴r s 豹牧敛 性等阏题。文献 2 7 ，2 8 ，2 9 讨论丁r s 的代数结构和拓扑问题：文献 3 0 ，3 1 讨论了 糖糙涵数豹一魏经瓣：文献 3 2 提壅t 专模糊索耩添数稠对褒豹耀糙隶属爨数： 文献 3 3 讨论了实数粮糙离敖化葶n 实函数粗糙窝敖化方面的问题：在文献 3 4 ，3 s j 串，支l 文寄、昊熬壹箨教授又绘出粳集理论孛粗糙蓉绞豹抽象形式帮p a w l a k 弋数，用公理化方法给如了p a w l a k 粗集代数的格形式。 3 ) 不确定健磷究 翘糙集理论中知识的不确定性主要由两个方筒来刻碱。一怒和埔税糙往测度 或迓钕精度来翔疆强“。另一耱是月雷农倍患壤袋刻疆，知识黝粳糙热与蕊惑爝 的关系比较密切，知识的粗糙性实质上题其所含信息多少的更深层次的刻画”“； 钛这个燕凌来看，耱糙集璎论与傣惑谂豹关系裁比较密切，不少学者程这方蕊做 了研究工作船8 。“”】。 ( 4 ) 耀糙逻辑与粳爨按理 糖糙逻辑是措定义在属性值为邻域的决策表上酌一种逻辑。它在数据约篱串 蠢罄广泛浆疫熙藏疑。p a w l a k 建立了糖耩逻辑熬五个逻辑真值“”。0 r l o w s k a 提蹴 了以等价关系确鏊石赉的新谓词，扩充了经典的= 篷逻辑“”。l i n 和l i u 基于撼抖 学双点定义了类似予下秘上近似的冀予l 靼h ，势建立了基子两个薄予豹近似推联 演绎系统“”。l i u 在文 4 2 提出丁带l 和 l 静糨糙逻辑熹蠹仪推理模式秘归结原理， 并诞盟了它的归结完备牲定理。掰鸯这些研究都为经典逻辑在近似推邂中的成用 开辟了新途径。 ( 5 ) 粗糙集约筛算法 设计高效豹豹篱算法遂怒一个需要避一步谤究的闯题，望裁提如驰一些算法 主要集中在导出规则的增鳖式算法、约简的癀发式算法、穰糙集基本并行算法 h 3 14 4 , 8 ) ，以及嚣粗糙巢鸯美豹遗鼗算法”“3 等。 ( 6 ) 粗糙巢理论与其食方法的融合 强嚣糨糙集理论与其他处璎模糊牧或不确定性方法的理论研究，主要集中程 与概率统计、模糊数学和d - s 诞攒理论和信息论的相互渗透与补充n 7 。“”1 。 1 3 本文的知识简介 从1 。2 节中我们剪知：交精度糨橙集模型和广义糨糙集模型献不越的兔发接 广了p a w l a k 粳糙集模型。本文就是围绕这两种模艇来研究的，共分为五章： 第一章楚貉论，介绍了粮糙集的国内外发糙状况及烹要研究方穗。 第二章简要介绍了p a w l a k 粗糙巢、信患系统、信患系统的属性约简苏及变精 3 度粗糙集的基本概念。 第三章针对变精度粗糙集模型中值的选取问题，讨论了由分类质量阈值来 确定声取值范围的两种算法。 第四章讨论了变精度粗糙集模型的知识约简问题，给出了口上、下分布约筒 的另外两种可辨识矩阵。 第五章先讨论了串行关系下的广义粗糙集，再将变精度粗糙集模型推广到不 同的论域上来讨论，得到了变精度广义粗糙集模型，扩充了在不同的论域下的粗 糙集近似算子。 4 第二章与本文有关的粗糙集理论基本概念 粗糙集理论是建立在分类机制的基础上的，它将分类理解为特定空间上的 等价关系，而等价关系构成了该空间的划分。粗糙集理论将知识理解为对数据的 划分，每一个被划分的集合称为概念。粗糙集理论的主要思想是利用已知的知识 库，将不精确或不确定的知识用已知的知识来( 近似) 刻画。知识约筒也是粗糙集理 论的核心内容之一，所谓知识约简就是在保持数据库分类能力不变的前提下，删 除其中不相关或不重要的知识。通过知识约简，导出决策规则或分类规则，去除 冗余信息。 2 1p a w ia k 粗糙集 设u 是非空有限论域，尺ux u 是u 上的一个等价关系，序对k = ( u ，r ) 称为 近似空间。v 0 ，y ) e u x u ，若“y ) e r ，则称对象z 和y 在近似空间足中是不可分辨 的。u r 是u 上由r 生成的等价类全体，它构成了u 的一个划分，用【x 】。表示包含 元素x e u 的尺等价类。若称u r 中的集合为原子集或基本集，任何子集z 【， 称为u 中的一个概念或表示知识，则k = ( u ，r ) 称为知识库。任意有限的基本集 的并和空集均称为可定义集或精确集，否则称为不可定义集或粗糙集。 对于论域u 上的任意一个子集z ，z 不一定能用知识库中的知识来精确地描 述，即x 可能是粗糙集，这时就用一对糟确集即z 的上近似和下近似来描述。 定义2 1 1 ”1 给定知识库k - ( v ，r 1 ，r 为【，上的等价关系，设x 互u ，集合x 的上近似集和下近似集可分别表示为： a p r 。僻) = r ( x ) = u 口e u ri l ，n x m ， ( 2 1 ) a p r ，( x ) = 星( x ) = u 】，【，r i l ，盖 上近似、下近似也可以用下砸的等式来表达： a p r 。( z ) = n ( x ) = x e u l r 】。n x 垂) ， ( 2 2 ) a p r 。( x ) = 丛( x ) = x u l 旺】。石) 同时，定义p o s 。( x ) = 星( x ) 为x 的r 正域；n e g r 暖) = u r ( x ) 为x 的r 负域； b n d 。僻) = n ( x ) 一星僻) 为x 的r 边界域。直观的讲：的r 正域是根据知识尺判 断肯定属于工的那些对象构成的集合；盖的尺上近似集是根据知识尺有可能属于 工的对象构成的集合；盖的尺边界域是根据知识尺不能确定是否属于x 的对象构 成的集合；x 的尺负域是根据知识尺判断肯定不属于x 的那些对象构成的集合。 称( 2 。，n ，u ，! ，a p r 。，a p r r ) 为粗集代数系统。 定理2 1 1 侣1 ( d x 为r 可定义集一星僻) = 五( x ) b n d r ( x ) = 中。 ( 2 ) x 为r 宣僻) r ( x ) 一b n d r 僻) 中。 2 2 信息系统 为了夏好地进行知识表达，我们引进知识表达系统( 信息系统) t = ( u ，a ，v ，) ， 其中 u ：对象的非空有限集合，称为论域； a ：属性的非空有限集合； v = u k ，k 是属性a 的值域； d e 一 ，：u 爿一y 是一个信息函数，它为每个对象的每个属性赋予一个信息值， 即对任意的口e a ，x e u ，( x ，口) 圪 知识表达系统的数据以关系表的形式，关系表的行对应要研究的对象，列对 应对象的属性，对象的信息是通过指定对象的各属性值来表达。 对于这样的知识表达系统，每个属性子集就定义了论域上的一个等价关系， 一个表可以看作是定义的一族等价关系，即v p 彳，定义属性集p 的不可区分 关系i n d ( p ) 为： i n a ( p ) = ( x , y ) e u u i v a p f ( x ，口) 一f ( y ，口) ) ( 2 3 ) 如果( y ) e i n d ( p ) ，则称x 和y 是p 不可分辨的。易知i n d ( p ) 是u 上的等价关系， 在不引起混淆的情况下，通常用p 代替如d ( p ) 。 若a = c u d ，c f ) d * 中，c 称为条件属性集，d 称为决策属性集，具有条件属性 和决策属性的知识表达系统称为决策表或决策信息系统。 2 3 信息系统的属性约简 设t = ( u ，a ，v ，) 为一信息系统，v b a 为属性集，删啤) 和珈d 口) 是如( 2 3 ) 式 定义的等价关系。 定义2 3 。1 设bc _ a 为一属性子集，属性r e b ，如果i n d p ) 一抽d 印一，) ，则称r 为 口中不必要的，否则称r 为且中必要的。若对任意的，e b 都为口中必要的，则称口 黾独立的。 定义2 3 2 设q 口彳为属性集，如果q 是独立的，且i n d ( q ) = i n d ) ，则称 q 为口的一个约简。 定义2 33b 中所有必要关系的集合称为口的核，记为c o r e ( b ) ，且 = o r e ( b ) = n r “) ，其中r e d c r ) 表示尺的所有约简a 6 定理2 1 1 g * l ( 1 ) j 为月可定义集讳旦( 丑) = 再) 讳锄如( z ) = m 。 ( 2 ) z 为r 尊曩瞄) 面( 置) 讳b n a ( x ) 中。 2 2 信息系统 为了更好地进行知识表达，我们引进知识表达系统( 信息系统) t = ( u ，a ，v ，f ) 其中 u ：对象的非空有限集合，称为论域； ：属性的非空有限集合： v = u k ，k 是属性n 的值域； d ，：【，一一y 是一个信息函数，它为每个对象的每个属性赋予一个信息值， 即对任意的b 哇，x u ，o ，口) v o 知识衰达系统的数据以关系表的形式，关系表的行对应要研究的对象，列对 应对象的属性，对象的信息是通过指定对象的各属性值来表达。 对于这样的知诎表达系统，每个属性子集就定义了论域上的一个等价关系， 一个表可以看作是定义的一族等价关系，即v p 4 ，定义属性集p 的不可区分 关系缸d ( p ) 为： i n a c p ) = t ( z ，y ) u u i q a e p ，( z ，4 ) z f ( y ，口) ) ，( 2 3 ) 如果( ，) 抽d 俨) ，则称z 和y 是p 不可分辨的。易知_ n d ( e ) 是u 上的等价关系， 在不引起混淆的情况下，通常用p 代替如d f p l 。 若a = c u o ，c n d 西，c 称为条件属性集，d 称为决策属性集，具有条件属性 和决策属性的知识表达系统称为决策表或决策信息系统。 2 3 信息系统的属性约简 设t = ( u ，a ，v ，) 为一信息系统，vb c a 为属性集，f 趔( 口) 和i n d ( a ) 是如( 2 3 ) 式 定义的等价关系。 定义2 31 设b 爿为一属性子集，属性r b ，如果胁d ) 一抽d ( 目一r ) ，则称，为 b 中不必要的，否则称r 为且中必要的。若对任意的，口都为口中必要的，则称口 是独立的。 定义2 32 设q b a 为属性集，如果q 是独立的，且；耐( 0 ) = i n d ) ，则称 q 为b 的一个约简。 定义233b 中所有必要关系的集合称为b 的核吐为，p 旧) ，且 c o r e ( b ) = n r 州( 丑) ，其中r e d c 尺) 表示r 的所有约简。 c o r e ( b ) = n r e d ( b ) ，其中r e d c 尺) 表示r 的所有约简。 6 s k o w r o n ”给出了利用可辨识矩阵计算约简与核的方法 定义2 3 4 设t = ( u ，a ，v ，) 为一信息系统，u = 怯，工：，) 是论域，定义r 的 可辨识矩阵是一个n r 的矩阵，矩阵的第i 行第j 列位置上的元素为： d ，z ，) 一 e a ：，“，a ) f ( x j ，口) ( 2 4 ) 可以看出d “，x f ) 是区别对象蕾和x ，的所有属性的集合。 定理2 3 p “趵设t - - ( u ，a ，v ，厂) 为一信息系统，口爿为一属性子集，则： ( 1 ) b 是系统的一个约简当且仅当曰满足条件矗n d ( x ，y ) * 垂的在包含意义下的 极小子集，这里v d ( x ，y ) t 中 ( 2 ) c o r e ) = p e a ：d o ，) ) 一和 ，工，y u 下面我们引入可辨识函数，它是一个布尔表达式，由一些析取式的合取构成 其每一个析取式为d 0 ，y ) ，然后由这些析取项再合取我们用来记辨识函数， 则 。d ( x 棚 q _ 的 其中丌和分别表示合取和析取。 我们看到可辨识函数是一个布尔合取范式，当将可辨识函数等价地转化为它 的标准析取范式时，析取范式中的每一项就是原来信息系统的一个约简析取范式 的所有的项也就表达了原信息系统的所有约简。 2 4 决策表信息系统的相对约简 定义2 4 1 设p 和q 为u 中的等价关系，q 的p 正域记为p o s ，( q ) ，它满足： p o s ，( q ) = up ( y ) ( 2 6 ) r h ，u p o s ，( q ) 表示论域u 中所有通过分类u p 表达的知识能够确切的归入u q 类的对 象的集合。 我们知道，在决策信息系统中，属性有条件属性与决策属性之分，而条件属性 和决策属性按照它们所决定的等价关系分别给论域作了两个分类。如果从一组条 件属性中去掉一些属性后不会改变决策属性在其下的正域，就可以从条件属性集 中删除这些多余的属性。这就是相对约简的思想。 定义2 4 2 设t = ( u ，a = c t a d ，v ，f ) 为一决策信息系统，p c 为条件属性集，d 为决策属性集，a e p ，如果 p o s p ( d ) = p o s 川。 ( d ) ( 2 7 ) 则称。为p 中d 不必要的，否则称n 为p 中d 必要的。若对任意的口c p 都为p 中d 必要的，则称p 为d 独立的。 定义2 4 3p c _ c 5 自条件属性，d 为决策属性集，p 是d 独立的，且 p o s ，p ) ：p o s c p ) ，则称p 为c 的相对( j d ) 约简。c 中所有d 必要属性构成的集合 称为c 的d 核。记为c o r e 。( c ) ，且有c o r e d ( c ) = f l r e d 。( c ) ，其中r e d 。( c ) 是所有c 的 d 约简构成的集合。 类似于信息系统的约简和核，下面的定理给出了计算决策信息系统相对约简 和相对核的方法 定理2 4 1 强设t - - ( u ，a = c u d ，矿，) 为一决策信息系统，p c 为条件属性 集，d 为决策属性集，定义 a “ ，中f 薹c 卜吒h 三譬；：譬； c 2 固 则： ( 1 ) p 是系统的一个相对约简当且仅当p 满足条件p n 口“，z ，) 一m 的在包含意 义一f 的极小子集，这里对任意的口“，x j ) ，垂 ( 2 ) c o r e d ( c ) 一 口c ：口“，) 一 口) ，而，x ，u 下面我们定义决策信息系统的可辨识函数( d ) ： ( d ) 2 婶，玛。毗) ，) q 则可辨识函数( d ) 的标准析取范式中的每一项就是原来决策信息系统的一个 相对约简，并且标准析取范式的所有的项也就表达了原信息系统的所有相对约 简。 2 5 变精度粗糙集模型 z i a r k o “钉提出的变精度粗糙集模型是对p a w l a k 粗糙集理论的扩充，它是在基 本粗糙集模型的基础上引进了阈值霹( 0 s 口 0 5 ) ，即允许一定程度的分类错误 率存在。变精度粗糙集模型的主要任务是解决属性间无函数或不确定关系的数据 分类问题，这给研究者处理由于噪声所引起的数据不一致性问题提供了很好的方 法。后来a n 等人托”又将卢定义为分类正确率( 0 5 o o ，, ( 2 1 。) 其中l x l 表示集合x 的基数4 ，称p r ( y x ) 为集合x 关于集合y 的相对分类正确率 也称为集合y 基于集合盖的条件概率。 2 5 2 j ；b 近似集 定义2 5 2 1 设t = ( u ，az c u d ，v ，) 为一决策信息系统，p _ c c 为条件属性 集，q c ：d 为决策属性集，u p = x ，x ) ，o 5 声墨1 ，对任意的y g u q ，定义 y 的卢下近似为翌：( y ) = r _ ；0 9 = u 仁；e u p i p r p x f ) 之卢) ， y 的芦上近似为印- - r ，p ( y ) = 彭f r ) = u x ；e u f p l p r c y x ；) ，l 一芦) ， y 的卢负域为, , e g f f r ) 一u x ；u p i ( y z ，) s 1 - 卢) ，( 2 1 1 ) y 的卢边界域为b n d f l ( 】，) ；u x ，g u i p a 一卢 p r p x ；) 芦 群( y ) 也称为正域，记为p ；( y ) ，将近似集合对 称作y 的变精 度粗糙集合或芦粗糙集合y 的下近似或卢正域可理解为将u 中的对象以不小 于卢的正确分类率分于y 的集合y 的口负域相应的理解为将u 中的对象以不小 于卢的正确分类率分于y 的补集的集合 当卢= 1 时，变精度粗糙集即为经典的p a w l a k 粗糙集。随着卢的减少，卢粗糙 集的近似边界区域变窄，即变精度粗糙集意义下的不确定区域变小因此，口粗 糙集对数据不一致性有定的容忍度，在某些场合可以更好的抗噪声，增强产生 规则的鲁棒性 第三章变精度粗糙集模型中芦取值范围的确定 变精度粗糙集是对p a w l a k 粗糙集理论的一种扩充，它通过设置阈值参数 ( 0 5 卢s 1 ) ，放松了对标准粗糙集理论近似边界的严格定义。当条件类关于决策类 的分类正确率大于某一闽值芦时，就认为此条件类可以归类于决策类中。阈值口 的选择对规则集会产生一定的影响h ”。而大量的文献“”。“。”5 ”都是在假定某个 特定的阈值芦的基础上来讨论的。在现实生活中，决策分析者往往并不知道口的 取值，但有可能知道用户所要求的分类质量“”“不得低于某一阈值r 。如何根 据睐确定j 8 的取值范围是本章研究的重点。 3 1 分类质量n9 ，2 0 ”3 、可信度_ 5 2 1 设t = ( u ，4 一c u d ，v ，) 为一决策信息系统，p _ c c 为条件属性集，q c _ d 为决策 属性集，定义分类质量为y 9 僻q ) 蚴= 掣， ( 3 i ) 其中p o s ( e ，q ，, 0 - - u 即) ( 3 2 ) 分类质量r p ( p , q ) 表示的是条件类以不低于卢的分类正确率归入决策类的对象的 百分比，代表了决策表的分类能力。在有的文献中y 4 ( 只q ) 也称为决镶属性集q 与条件属性集p 的口近似依赖性。 若z u p 为条件类，y u q 为决簸类，对于一个概率决策规则： d e s ( j ) 一d e s ( y ) ，妒p r x ) 芦， 而言，x 表示的是规则前件，y 表示的是规则后件，p r x ) 表示的是此决策规 可信度( 准确度) ，卢为可信度阈值。 3 2 分类质量与可信度阈值的关系 定理3 ，2 1 ( 1 ) 设o 5 芦1s 卢s 1 ，若x p d s ；( 】，) ，则盖p o s s e ( y ) a ( 2 ) 设o 5 口宣卢。s 1 ，若盖譬p ：( y ) ，则x 芒p o s ； ( y ) 。 证明：由定义2 5 2 1 可直接得到。 定理32 2 当0 5 r “一( p ，q ) ，选择算法l 时，循环时间 复杂度为o ( ( f + 1 ) 2 ) ，选择算法2 时，循环时间复杂度为o ( f ) ，所以此时应选 择算法i ：如果， r “t ( p q ) ，选择算法1 时， 循环时间复杂度为o ( ( f ，2 ) ) ，选择算法2 时，循环时间复杂度为o ( z ) ，所以此 时应选择算法1 ：如果r 0 8 ， 再取k = 3 ，y “( p q ) = 0 7 2 0 6 ，应选择算法2 ， 求得( o 5 , i 2 1 3 】。 3 5 结论 交精度粗糙集模型对处理带有噪声的数据是十分有效的，该模型通过引入 一个可信度阈值o 5 卢s 1 ，从而具有一定的容错能力。我们只知道卢( 0 5 ，1 ， 当然j i b 值得越大，规则的可信度就越高，但这样就有可能满足不了用户对r 的 要求f 即要求保证一定的分类质量) 。本文给出了由，确定卢的两种算法，这样得 到的芦值即能满用户对r 的要求，又相应的可以提高所获取的规则库中规则的 可信度( 取卢7 时规则的可信度最高) ；并讨论了根据r 的取值来选择不同的算法。 实例证明这两种算法是有效的。 第四章变精度粗糙集模型上的知识约简 属性约简是粗糙集模型中最重要的概念之一，基于交精度粗糙集理论，文 献 1 9 ，2 0 ，5 1 ，5 3 给出了p 近似约简，文献 5 4 给出了属性约简的另外几种形式： 芦上、下近似约简和j b 上、下分布约简，并给出了芦上、下分布约简的可辨识矩 阵和可辨识函数。本章在分析这些约简的基础上给出了卢上、下分布约茼的另外 两种可辨识矩阵，与文献 5 4 中所讨论的可辨识矩阵是等价的。从而得到了变精 度粗糙集模型上知识约简的新方法这为不协调日标信息系统的知识约简提供了 理论依据与算法 4 1 芦近似约简。芦上、下近似约简和芦上、下分布约简 定义4 1 1 口近似约简曲” 条件属性集p 关于决策属性d 的移约简或近似约简是尸的一个子集 r e d 4 ( p ，d ) ，且满足：( 1 ) y 9 ( p ，d ) = y 4 ( r e d 4 ( 尸，d ) ，d ) ( 2 ) 从r e d 9 ( 只d ) 中去掉任意一个属性，都将使( 1 ) 不成立。 其中的y 4 ( p ，d ) 在( 3 1 ) 式给出。 定义4 1 2 声上、下近似约筒和卢上、下分布约简膳” 设t = ( u ，a = c u d ，v ，厂) 为一决策信息系统，p c 为条件属性集，d 为决策 属性集，u d = y 1 ，y 。 ，0 5 卢s 1 ，记： 咖逊铲，砟= 砸铲， 砟= ( 印，：( k ) ，p , 0 0 ，印r ：( k ) ) ，抒；= ( - - 印，a ( x ) ，石：( y 2 ) ，面：( 匕) ) ( 1 ) 若仃# = 仃暑，则称p 是c 的卢下近似协调集。若p 是c 的卢下 近似协调集，但p 的任何真子集不是c 的卢下近似协调集，则称p 是c 的p 下近 似约简。 ( 2 ) 若砟= a ，则称p 是c 的芦上近似协调集。若p 是c 的卢上近似协调集， 哩p 的任何真子集不是c 的口上近似协调集，则称p 是c 的卢上近似约简。 ( 3 ) 若职= ，则称p 是c 的芦下分布协调集。若p 是c 的p 下 分柿协调集，但p 的任何真子集不是c 的芦下分布协调集，则称p 是c 的卢下分 竹约简。 ( 4 ) 若h ；= h g ，则称| p 是c 的上分布协调集。若p 是c 的声上分布协调集， 1 4 但p 的任何真子集不是c 的卢上分布协调集，则称p 是c 的p 上分布约简。 c 的口下、上近似协调集是保持决策类的下、上近似中的对象总数不变， 由它产生的命题规则与由c 产生的命题规则可能不同，但支持这些命题规则的 对象个数相同。卢上、下分布协调集是保持每个决策类的卢上、下近似不变的 属性集，它与c 产生相同的不确定性命题规则。 4 2 几种约