（基础数学专业论文）一些不确定性推理方法的研究.pdf

摘要 不确定性问题一直成为人们关注和研究的焦点。目前常用的不确定推理方 法有：基于概率论的概率推理方法、基于证据理论的证据推理方法、基于模糊集 理论的可能度方法和基于粗集理论的粗集方法，这些方法各有优缺点，在当今不 确定推理方法中并存，且在不断的发展中，本文分别从证据理论、粗糙集理论和 概率理论方面对不确定性推理方法进行了讨论。 在基于证据理论推理中，数据融合是将几个来自不同证据源的信任函数组 合成一个信任函数，d e m p s t e r 组合规则是人们常用的方法，后来，许多研究者 提出了许多新的组合规则，本文对一些典型的合成模型的优缺点做了研究，并重 点研究了可传递信任模型。 在粗糙集理论中，精度是量化由粗糙集边界引起的不精确性的一种重要数 字特征。然而，传统精度并没有考虑到由等价关系导出的划分的颗粒大小。本文 在分析传统精度和由x ub a o w e n 等人提出的精度的基础上，提出了一种新的精 度定义。并给出了它的一些好的性质，而且通过例子说明了它是一种更优的精度 定义，并且算法上比x ub a o w e n 等人的更简单。 贝叶斯网是用来表示不确定变量集合联合概率分布的图形模式，它反映了 变量间潜在的依赖关系。使用贝叶斯网建模己成为解决许多不确定性问题的强有 力工具。本文对贝叶斯网络推理中复杂的网络结构给出了一种基于向内的二叉树 模型，使推理计算大为简化，取得较好的效果。 关键词：信任函数；数据融合模型；粗糙集；精度；离散度；贝叶斯网； 概率计算；不确定推理 a b s t r a c t u n c e r t a i n t yr e a s o n i n gi so n eo ff o c u sr e s e a r c hd o m a i ni na r t i f i c i a li n t e l l i g e n c e a tp r e s e n t ，s o m eu n c e r t a i n t yr e a s o n i n gm e t h o d su s e df r e q u e n t l ys u c ht h a tp r o b a b i l i t y r e a s o n i n g ，e v i d e n c er e a s o n i n g ，v a g u er e a s o n i n g ，r o u g hs e tr e a s o n i n g ，e a c ho ft h e s e m e t h o d sw h i c he x i s t si nu n c e r t a i n t yr e a s o n i n gm e t h o d sh a si t sa d v a n t a g e sa n d d i s a d v a n t a g e sa n dh a sb e e na l w a y sd e v e l o p e d i nt h i sp a p e re v i d e n c et h e o r y , r o u g h s e tt h e o r ya n dp r o b a b i l i t yr e a s o n i n gm e t h o dh a v eb e e nd i s c u s s e d w i t h i nt h ee v i d e n c er e a s o n i n g ，d a t af u s i o nc o n s i s t si no b t a i n i n gas i n g l eb e l i e f f u n c t i o nb yt h ec o m b i n a t i o no fs e v e r a lb e l i e ff u n c t i o n sr e s u l t i n gf r o md i s t i n c t i n f o r m a t i o ns o u r c e s t h em o s tp o p u l a rr u l eo fc o m b i n a t i o ni sd e m p s t e r sr u l eo f c o m b i n a t i o n a n dt h e ns o m eo u t s t a n d i n gn e wm o d e l sh a v eb e e ng i v e n t h e m e r i t sa n dd e m e r i t so ft h e s em o d e l sa r es t u d i e d , e s p e c i a l l yt h et r a n s f e r a b l eb e l i e f m o d e lh a sb e e ns t u d i e di nt h i sp a p e r i nr o u g hs e tt h e o r y , t h ea c c u r a c ym e a s u r ei sa ni m p o r t a n tn u m e r i c a lc h a r a c t e r - i z a t i o nt h a tq u a n t i f i e st h ei m p r e c i s i o no far o u g hs e tc a u s e db yi t sb o u n d a r yr e g i o n h o w e v e r , t h et r a d i t i o n a la c c u r a c ym e a s u r ed o e sn o tt a k ei n t oc o n s i d e r a t i o nt h eg r a n u l a r i t yo ft h ep a r t i t i o ni n d u c e db ya l le q u i v a l e n c er e l a t i o n t h i sp a p e rf i r s ta n a l y z e st h e l i m i t a t i o no ft h et r a d i t i o n a la c c u r a c ym e a s u r ea n dt h eo n ep r o p o s e db yb a o w e nx u e t c a n dt h e np r o p o s e san e wk i n do fd e f i n i t i o no fa c c u r a c ym e a s u r e a n ds o m eg o o d p r o p e r t i e so fi th a v eb e e np r o v e d ，w h a t 7 sm o r e ，i ti sm o r es u i t a b l et om e a s u r et h e i m p r e c i s i o no fr o u g hs e t sa n di t sa l g o r i t h mi ss i m p l e rt h a nb a o w e nx ue t c sw h i c ha r e i l l u s t r a t e db ye x a m p l e s ， a b a y e s i a nb e l i e fn e t w o r k ( b b n ) i sag r a p h i cm o d e lt h a te n c o d e sj o i n t p r o b a b i l i t yd i s t r i b u t i o na m o n gu n c e r t a i nv a r i a b l e s ，i te x p r e s sap o t e n t i a ld e p e n d e n t r e l a t i o n s h i pb e t w e e nv a r i a b l e s m o d e l i n gw i t hb a y e s i a nb e l i e fn e t w o r kh a sb e e na p o w e r f u lt o o lt os o l v em a n yu n c e r t a i n t yp r o b l e m s t h i sp a p e rp r o p o s e san e w a p p r o a c hf o rc o m p u t i n gp r o b a b i l i t i e s o fe v e n t si n b a y e s i a nn e t w o r k i tm a k e s p r o b a b i l i t yr e a s o n i n go fe v e n t se a s i e ra n dt h er e s u l t sm a k e s u ss a t i s f i e d k e y w o r d s ：b e h e ff u n c t i o nm o d e l so fd a t af u s i o n ；r o u g hs e tt h e o r y , ；a c c u r a c y m e a s u r e ；d i s c r e t em e a s u r e ；c o m p u t i n gp r o b a b i l i t i e s b a s e do nb a y e s i a nb e l i e f n e t w o r k ；u n c e r t a i n t yr e a s o n i n g 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名：目呷彳签字日期：知滞么月午日 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者张m 哞 签字日期：砂。8 年6 月牛日 导师签名：罢书烤 签字日期：伽扩年乡月牛日 引言 在当今信息时代，我们所面对的信息中不确定信息远比确定信息要多，确 定信息的处理已有较成熟的理论和方法，不确定信息的处理还处于百家争鸣的 时代，研究不确定信息的表达和处理是当今信息时代研究的一个主要方向。人们 最早接触的不确定性是随机性，对随机性的研究已经形成概率论、数理统计、 信息论等重要学科，其发展已经成熟，应用非常广泛。随着生产科技的发展， 由定义的不清楚、度量尺寸的模糊性、或者决策者不能完全把握事物的真实状 态和数量关系，造成了有别于随机性的不确定性。为了解决这些不确定性，目 前常用的不确定推理方法有：基于概率论的概率推理方法、基于证据理论的证 据推理方法、基于模糊集理论的可能度方法和基于粗集理论的粗集方法，这些 方法各有优缺点，在当今不确定推理方法中并存，且在不断的发展中。本文分 别从证据理论、粗糙集理论和概率理论方面对不确定性推理方法进行了讨论。 证据推理是一种重要的人工智能方法，广泛应用于数据融合、数据挖掘和 智能决策。近年来，信息融合受到人们越来越多的研究，由于信息本身具有不 确定性、不精确性和不完备性，在信息融合时必须把这些因素考虑进去，因此， 数据融合有许多模型，在当今，并且有许多研究人员对它们作出了各种评价， 本文在他们的基础上进一步综合，而且重点讨论了可传递信任模型。 由p a w l a k 与他的同事们在8 0 年代初发展起来的粗糙集理论已受到国内外 学者越来越广泛的重视，是一种新的软计算方法，是处理数据的不确定性和模 糊性的数学工具。它是经典集合理论的推广，它给出了集合的上近似集和下近 似集。在过去的几十年里，已经提出了粗糙集的许多推广并且广泛研究了在粗 糙集理论，模糊集合论，概念格理论和证据理论之间的联系 4 4 ，4 5 ，4 6 ，4 7 ， 4 8 1 。目前，粗糙集理论在许多领域得到广泛应用，如信息检索，数据挖掘，人 工智能，模式识别，控制理论和信号分析等。 粗糙集理论中，在决策推理时，一个决策规则的可靠性是由本文讨论的精 度来描述的，粗糙集数据分析是以承认可用的知识为一定的颗粒状为前提的， 而颗粒块是通过划分和与划分相应的等价关系来表示的。x ub a o w e n 等人在考 虑颗粒块的大小的基础上对p a w l a k 定义的近似精度进行了改进，但改进工作没 有限制到具体的x 并且算法极其复杂。 本文在 4 2 ，4 3 的基础上，提出了论域u 关于等价关系r 的划分中两个元 素之间的距离和两个等价类之间的距离，再利用距离定义了划分的散度来刻画 划分的颗粒块的大小，进而利用所定义的散度重新定义了近似精度。 概率推理方法中，有基于p r o s p e c t o r 专家系统的推理方法，s h o r t - 1i f e 和b u c h a n a n 于1 9 7 5 年提出的确定性因子法，等1 9 7 6 年提出的主观贝叶斯方法， 1 9 8 5 年提出的信息网络方法，1 9 8 6 年提出的概率逻辑方法，本文在概率推理方 法中，重点研究了贝叶斯推理，由于贝叶斯网是用来表示不确定变量集合联合概 率分布的图形模式，它反映了变量间潜在的依赖关系。使用贝叶斯网建模已成为 解决许多不确定性问题的强有力工具。本文对贝叶斯网络推理中复杂的网络结构 给出了一种基于向内的二叉树模型，使推理计算大为简化，取得较好的效果。 2 第一章绪论 一 1 1 基本知识简介 不确定推理是智能系统开发实现中的一个重要问题，也是解决传统的专家 系统知识的脆弱性和推理的单调性的一个重要手段。 ， 不确定理论是概率论、可信性理论、信赖性理论的统称，同时还包括模糊 随机理论、随机模糊理论、随机粗糙理论、粗糙随机理论、双重随机理论、双 重模糊理论、双重粗糙理论。目前己提出不少确定推理的模型，如基于概率论 的主观b a y e s 方法、基于模糊集的可能性理论、d e m p s t e r - s h a f e r 的证据理论方 法、粗糙集方法、数据挖掘的方法、模糊逻辑推理等。 证据推理适合于无先验信息的融合，而且在不确定性的表示、度量和组合 方面的优势受到广泛的重视，先后推广到概率范围和模糊集，不仅可以象贝叶 斯推理那样结合先验信息，而且能够处理象语言一类的模糊概念证据。在各个 领域的数据融合不同层次上应用证据推理，取得了较好的结果。 粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想 就是在保持分类能力不变的前提下，通过知识约简，导出问题的决策或分类规 则。目前，粗糙集理论已被成功地应用于机器学习、决策分析、过程控制、模 式识别与数据挖掘等领域。 在d m 和k d d 诸多方法中，粗糙集理论与方法对于处理复杂系统不失为 一种较为有效的方法，因为它为概率方法、模糊集方法和证据理论方法等其他 处理不确定性问题理论的最显著的区别是它无需提供问题所需处理的数据集合 之外的任何先验信息。当然，由于该理论未能包含处理不精确或不确定原始数 据的机制，所以与其他处理不确定性问题的理论有很强的互补性。 贝叶斯网( b a y e s i a nn e t w o r k s ) 是用来表示变量间概率依赖关系的图形模 式，它以概率理论为数学基础，用节点表示变量，有向边表示变量间的依赖关 系，具有直观的表达能力和强大的推理能力，近年来在专家系统、数据挖掘、 决策支持等领域了成功的应用。 1 2 本文的内容结构 本文的主要工作和研究成果有如下几个方面： 3 1 第二章和第三章对基于证据理论的常见的推理方法进行了研究，重点分 析了这些推理方法的优点和存在的缺馅，并着重研究了可传递信任模型及其应 用。 。 2 第四章对描述粗糙集理论中在决策推理时一个决策规则的可靠性的精度 进行了研究，并且给出了一种新的计算方法，通过比较说明此方法更优，算法 更简单，从而使得基于粗糙集理论的推理方法更加完善。 3 第五章在给出两种概率推理方法的基础上，提出了计算贝叶斯网中事件 概率的一种新方法二叉树和超图的方法，即先利用超图和超树找出贝叶斯网 的根结点，再利用向内传播的方法及二叉树的方法计算根结点中表示的事件的概 率。通过和以前的方法体系比较，这一方法显示了它的优越性。 4 第二章基于证据理论的证据推理方法 2 1 证据理论基本概念+ 在证据理论中，一个有限样本空间称为个识别框架( f r a m eo f d i s c r i m i n a t e ) 常用o 表示，o 由一系列对象构成，对象之间两两互斥，且包 含当前要识别的全体对象。即 o = 嘏，包，幺 其中，i e i 的子集称为命题，只含一个对象的集合称为单点集( s i n g l e t o n s e t ) 。在分类专家系统中，这种单点集就是专家系统需要作出决策或判断的结 论。 ， 定义2 1给定识别框架o ，称b e l 是2 e 专【0 ，1 的一个信任函数 ( f u n c t i o no fb e l i e f ) 。若它满足 ( 1 ) b e l ( o ) = 0 ，b a ( o ) = 1 ，且对于2 e 中的任意元素a ，有0 b e i ( a ) 1 ( 2 ) 任给4 ，4 ，4 2 e ， 占d ( u 4 ) b e l ( 4 ) 一b e l ( a i a j ) + + ( 一1 ) 斛1 b e t ( 4 4 4 ) i = li = l l i 0 ，则在组合时就有冲突 ( 彳) 7 ，l ：( 丑) ，此冲突应该局部处理分配给组合后的a 和b ，而不分配给其其它 焦元。又若m ( 彳) o ，m ：( b uc ) 0 ，则在组合时就会产生冲突m ( 彳) 7 l ：( b uc ) ， 此冲突应该局部处理分配给组合后的a 、b 、c 和buc ，而不分配给其它焦元。 这种冲突处理办法被称为局部冲突处理，其一般形式为： 9 c ( 彳) 2 ( 锄+ e m n ( 瓦a ) 面x m , ( b ) m z ( b 或t a k c c ) e厶n 7 ， b 膏n r c 广= 日q 6 d 面) c 矗，c e 一。一 v 彳0 k ( 矽) = 0 其中怖( 彳) = ( n m ：) ( 彳) 全碍( 曰) 聊：( c ) 式中 m n ( 彳) r a n ( d ) x 确( 丑) 班：( c ) 部分是某一具体冲突值分配给a 的部分，而： _ 丕e c l r a n ( a ) 而，1 1 赢2 ( a 1 厶f。，n 、l 、一，、一 籍“。e 急c c 刀叫 是所有含a 的冲突按a 在其中所占比例分配给a 的冲突m a s s 值。在应用 此公式时，若有二- 局部冲突其各个子假设集在组合后均不是新的信任函数的焦 元，则此时可把此冲突平均分配给各子假设。 2 8上、下概率模型推理方法 s m i t h ( 1 9 6 1 ) g o o d ( 1 9 6 2 ) 和w a l l e y ( 1 9 9 1 ) 提出：有时个人的信度不能用一个数 表示但是他可以用包含他们信度的区间来估计，此时则可以用上、下概率模型推 理方法，即通常假定集族为凸集，则其下包络可以完全定义一族概率测度i t 的 下包络函数，记作尸( 彳) 称作下概率，定义为 、 尸( 彳) = m 诤p ( 彳) v a q ， 该函数通常是单调的，仅仅在一些特殊的情况下才是信任函数，通常不合适用 d e m p s t e r 合成规则。同理可以定义上概率，( 彳) = m a x p ( a ) 。 p e n 除了上述的一些推理方法外，许多学者研究了基于可传递信任模型( t b m ) 的推理方法，下一章将讨论基于可传递信任模型( t b m ) 的推理方法。 1 0 第三章基于可传递信任模型( t b m ) 的推理方法 3 1 基本介绍 1 简介：可传递信度模型( t b m ) 是s m e t s 于1 9 9 4 年提出的，它是一个双层 模型：一个是“c r e d a l ”层，在这层获取信度并对其进行量化、赋值和更新处理； 另一个是 p i g n i s t i c ”层，它将c r e d a l 层上的信度转换成p i g n i s t i c 概率，并由此做 出决策。c r e d a l 层先于p i g n i s t i c 层，在c r e d a l 层上随时可对信度进行赋值和更新， 而只有必须做出决策时，p i g n i s t i c 层才出现。所以，t b m 包括两个部分：一个 是静态的，即基本信度分配b p a ；另一个是动态的，即信度的传递过程。 2 适应范围：可传递信任模型为量化信度的表示提供了模型，假设有几个 可能的世界，它们中必有一个与真实世界相对应，但研究者【研究者可能是机器， 专家，】不知道可能世界哪个是真实世界，研究者说出自己的信度。b e l ( a ) 的值就代表了研究者对真实的世界a q 的信度。考虑到没有概率测度的概念来 描述可传递的信任模型，我们提出一种量化信度描述的理论。该量化信度在没有 概率函数概念的情况下也能存在。我们仅仅假设信度用一个数来代表，如：b e l ( a ) = o 6 7 ，满足某人的信度，则可使用信任函数。 3 基本术语：在可传递信度模型( t b m ) 中借用了d e m p s t e r 条件合成推理方 法中的许多概念，如： ( 1 ) 合取合成规则( 也就是d e m p s t e r 的合成规则) ：合成6 d o ( e 1 ) 和b e o ( e ) ， 为6 p ，o ( 巨k 垦) 。 ( 2 ) 析取合成规则：合成6 p ，o ( e 1 ) 和b e l o ( 最) 为6 p ，o ( 巨v 岛) 。 ( 3 ) 专有名词：m a s s 函数( 基本信任指派) 。 ( 4 ) 最小约定原则：即对于每一个a q 选取的信任函数赋值b e l ( a ) 要尽可 能小而p l ( a ) 要尽可能大。 ( 5 ) 谨慎合成规则：即合取合成规则必须满足：结合律、交换律和幂等律 且要接受证据源间的所有可能关系。 ( 6 ) 应用广义贝叶斯理论计算6 酣e ( 力对于 b e t z ( q ) ：包0 ) 。 ( 7 ) 条件独立概念。 ( 8 ) 对p i g n i s t i c 转换建立概率函数时必须应用期望效用理论取最优化决策。 可传递信任模型是s h a f e r 很看重的一个扩展模型，下一节我们将具体的对 其方方面面进行研究讨论。 4 可传递的信任模型中的信度：在可传递的信任模型中，基本信度分配获 得自然的解释，对于a q ，叫a ) 既为支持信度的那部分，既你认为真实世界 属于a 的程度。并且由于缺少信息，m ( a ) 不支持a 的任何真子集。如果可获 得进一步的证据并且认为是正确的，如新证据对q 的影响是认为真实世界不 属于口，则m ( a ) 对a 转换为a n b ，此时可通过： b e l a ) = b e l ( b u 么) 一b e l ( a ) 获得新的基本信度分配，信任程度b e l ( a ) 量化为调整到具体支持a 的总数 3 2 基于可传递信任模型( i b m ) 的推理方法 在可传递信任模型推理方法中第一层是“c r e d a l ”层，在这层获取信度并对其 进行量化、赋值和更新处理，常见的处理方法为： 1 两个信任函数的合取合成推理方法 在可传递的信任模型中，如果码和m ：是由两个不同的的信息源所产生的基 本信度指派，并且认为这两个信息完全可靠，那么可合取和扰： m t n 2 ( 爿) = ( b ) 聊：( c ) b f c = a 其中m a n 2 ( 彳) = ( 玛n m ：) ( 彳) 全，啊( b ) ，l ：( c ) 。 b n c = a 这一规则可通过“特化”的概念论证，假设不管何时接受一条新信息，基 本信度m ( a ) ( 先给a ) 可在a 的子集中进行分配，事实上，i n ( a ) 代表支持 假设a 的信度部分，也许支持比假设a 更具体的，我们应该获得某一新信息。 如果我们获得了新的信息，m ( a ) 将分配给a 的子集，如此一个运算叫做“特 化。如果假定已知a q 为真，那么必须在q 上定义一个新的基本信度指派， 作为期初基本信度指派的特化，令九彳】( 功表示获得证据a 下的函数( 此时f 可 以是：m , b e l ，p i ，c o r n , 中的任何一个) ，这样可得关系： 石n ：( 彳) = 石【召】( 彳) 耽：( 丑) ，v a q 。 丑o 2 两个信任函数的析取合成推理方法 合取合成并不是结合信任函数的唯一方法，有时，当获得两个基本信度指 派，但不认为两种信息都可靠。但知道其中至少有一个可靠，则可用析取的方法 合成，此时4n4 应设为4u 鸣，u 为析取符号。其中 m a u 2 ( 彳) = 鸭( 曰) 珑：( c ) ， v aa q 1 2 其中m u ：( 彳) = ( u m ：) ( 彳) 全m ( 口) ，z ：( c ) ，w q 。 b i j c = 4 3 谨慎合取推理方法 本文考虑另一种情况谨慎合取法，该方法是不仅满足结合律和交换律， 而且满足幂等律。，可以应用于处理相关的信息源。 假设有两个关于现实世界的信息的信度，令，l l 和m ，是q 上的两个信任指派 函数，如果对信息没有把握，即不知道两个信息是否有明显差异，它们也许相关， 甚至是同一个信息重复两次，为了解决这个问题，可以建立一个新的信任指派函 数，记作碍：。对于f = l 和2 ，应用合取合成规则，令 曩= 加：删q ，m = m i n l 7 , 1 , m 舛 其中m 。为信任函数。 易知，砚和的合成结果一定在中置n 吃。尤其是，l in 扰：属于该族中， 但不知道是垦n 垦中哪个元素。所谓谨慎的态度就是在该族中最小的可以接受 的元素，这就是“谨慎合取合成规则的想法。该方法在许爹隋况下已经用到， 但是对于一般的情况，如何找到最小可接受解是没有完全解决。 4 折算推理方法 如果从信息来源知道在q 上的信任函数为l n 但不相信信息来源可靠，如果 认为有柳( q ) = 1 一口+ 口坍( 9 ，a ( a ， a 、1 3 ， b 、c ) 和 a 、b 、c ，根据下面比例：( o 1 o 4 ) 、 ( 0 7 0 8 ) 、( 0 3 o 4 ) 、( o 7 0 8 ) 、( 0 i o 4 ) 、( o i o 8 ) 和( o 3 o 4 ) 、( 0 1 o 8 ) ， 信度值m 。 8 nm ：【冽( 彩= o 6 8 ，分配给 a 、b 。 在这个例子中，第一位专家支持x 是a ，而第二位专家支持x 是b ，如 果x 是b ，那么第一位专家为何不说是b ? 因此第二位专家支持很有可能看到 的就是a 而说是b ，是因为他不知道a 是什么。表1 ( 说明) ，在两个部分相交 1 4 的框架上的基本信度分配为铂和，结合为r n ，及m 相关的似真度和怀疑 度。 qm p 1b e t p 铂m 2 a0 10 o oo 9 20 4 5 5 b0 10 7o 0 70 3 2o 1 9 co 2o o o0 7 20 3 5 5 a bo 3o 2 l1 a c o 6 8o 9 3 b c0 10 0 11 a b c o 0 3 1 3 4 小结 ( 表一) 在许多应用中，信息处理需要用到概率方法是不可行的，人们当然尽可能 找回一些失去的信息，结果的效果将直接和修正的效果相联系。 相反，信任函数模型能够很好地应用于解决真正可用的信息，这是由于信 任函数能够表示任何形式的不确定性，完全知道，部分知道，。完全无知，但概率 函数则不行，等概率不是完全无知，它己经是知识的非常精确形式。 在应用这些模型之前应有很好的理论基础和对应用工具的确切理解。当面 临不确切证据时使用者不必仅限于概率模型，甚至可以考虑模糊理论。 第四章基于粗糙集理论的推理方法 4 1 引言 由p a w l a k 与他的同事们在8 0 年代初发展起来的粗糙集理论已受到国内外 学者越来越广泛的重视，是一种新的软计算方法，是处理数据的不确定性和模 糊性的数学工具。它是经典集合理论的推广，它给出了集合的上近似集和下近 似集。在过去的几十年里，己经提出了粗糙集的许多推广并且广泛研究了在粗 糙集理论，模糊集合论，概念格理论和证据理论之间的联系 4 4 ，4 5 ，4 6 ，4 7 ， 4 8 。目前，粗糙集理论在许多领域得到广泛应用，如信息检索，数据挖掘，人 工智能，模式识别，控制理论和信号分析等。 在粗糙集理论中，推理的好坏主要通过推理的近似精度来描述，而p a w l a k 提出的近似精度考虑了具体的x ，但对划分的知识颗粒块没有给予充分的考虑。 x ub a o w e n 等人在考虑颗粒块的大小的基础上对p a w l a k 定义的近似精度进行了 改进，但改进工作没有限制到具体的x 并且算法极其复杂。 本文在 4 2 ，4 3 的基础上，提出了论域u 关于等价关系r 的划分中两个元 素之间的距离和两个等价类之间的距离，再利用距离定义了划分的散度来刻画 划分的颗粒块的大小，进而利用所定义的散度重新定义了近似精度。并给出了 该测度的一些性质，从而这样定义的精度是合理的，通过具体例子对新方法和 文中提到的两种方法做了比较，进一步说明该方法的优良性。 4 2 粗糙集理论的基本知识 设u 是对象的有限非空集合，称为论域。任何子集x c u ，称为u 中的一 个概念或范畴。设r 是u 上的一个等价关系，u r 表示r 的所有等价类( 或者u 上的分类) 构成的集合， x r 表示包含元素x e u 的r 等价类。一个知识库就 是一个关系系统k = ( u ，r ) ，其中u 为非空有限集，称为论域，r 是u 上的一族 等价关系。 给定知识库k = ( u ，r ) ，对于每个子集x c u 和一个等价关系r i n d ( k ) ， 定义两个子集： 一r x = u r u r l y c 石) ， 尼z = u y e u r i 】，n z o ) 分别称它们为x 的r 下近似集和r 上近似集。 1 6 下近似、上近似也可用下面的等式表达： 型雄刮h 。n 冠= 仁c _ u l x 卫n x f z i ) 显然，砑是由那些根据知识r 判断肯定属于x 的u 中元素组成的集合；丛 是那些根据知识r 判断可能属于x 的u 中元素组成的集合。 不确定区域或边界区域定义为： 一 b n ) = r x 一丛 显然，砌。是那些根据知识r 既不能判断肯定属于x 又不能判断肯定属 于一x ( 即u x ) 的u 中元素组成的集合。 集合( 范畴) 的不精确是由于边界域的存在而引起的。集合的边界域越大， 其精确性则越低。为了更准确地表达这一点，p a w l a k 引入了精度的概念，由等 价关系r 定义的集合x 的近似精度为： d 。盯) = i _ 麟l p | ， 其中互。，陋i 表示集合x 的基数。 精度以( x ) 用来反映我们了解集合x 的知识的完全程度。显然，对每一个r 和xc _ u 有o 以( x ) l 。当时d r ( x ) - - 1 ，x 的r 边界域为空集，集合x 为r 可定 义的；当以( 柳 1 时，集合x 有非空r 边界域，集合x 为r 不可定义的。 4 3 一种基于离散度的精度 4 3 1p a wia k 精度的局限性 首先定义论域u 的所有划分所组成的集上定义一个偏序2 1 ，设p 和q 为非 空有限集u 的两个划分，如果满足下述条件： 尸受叩p ，了q ，q 一只s g 则称划分q 比划分p 更粗或划分p 比划分q 更细。 如果幽且p q ，则称q 严格粗于p ( 或p 严格细于q ) ，记作p q 。 事实上，我们对论域u 中的对象的知识是以由等价关系r 导出的划分的颗 粒表现出来的。划分越细，对某一个特定对象我们就获得更多信息，然而，p a w l a k 1 7 定义的精度并没有考虑完全包括在下近似集内的颗粒的大小，即在p a w l a k 粗糙 集中当墨恐时，对锻s u 有噍( 柳s 噍( 但当蜀cr 2 时却没有氏( 柳 噍( 固。 如例1 ： 例1 u = 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ) 和五= 1 ，2 ，3 ，4 ，5 ，8 ) ，三个等价关系足， 恐，马及导出的划分分别为： u 足= “1 ，2 ，3 ，4 ) ，( 5 ，6 ，7 ) ，( 8 ，9 ) ) ， u 恐= “1 ，2 ) ， 3 ，4 ) ， 5 ，6 ，7 ) ，( 8 ，9 ) ) ， u 足= “1 ) ， 2 ，( 3 ) ， 4 ) ，( 5 ，6 ，7 ) ， 8 ，9 ) ， 则易知，五关于墨，恐，玛的下近似集和上近似集分别为： r 五= 恐五= 恐五= l ，2 ，3 ，4 ) ， 墨- - 五= i r ：五= 取= 1 ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ) ， 由p a w l a k 的近似精度定义可得， 噍( 五) 2 噍( 五) 2 噍( 五) = 4 9 ， 则可得出x 关于墨，恐，墨所获得的信息相同，但由于墨 恐 r ，然而，从上面的 分析知足获得的信息应更多 4 3 2x ub a o w e n 等人提出的改进( 基于过剩熵的精度( a ne x c e s s e n tr o p yb a s e da c c u ra c ym e a s u r e ) 。 为了改进p a w l a k 定义的精度的不足，x ub a o w e n 等人通过以下三步： l 对定义在u 上的等价关系r 构造一个等价关系图g ( r ) 。 2 计算g i 的过剩熵。 3利用过剩熵重新定义精度。 对p a w l a k 定义的精度改进如下： 精度计算定理 1 ， 定理l 设僻l o 和r = ( 置i l s f m ) ，其中u 。_ 置= u 且置n 巧= a ，( 1 s f ，j m ， i j ) 。 ( 1 ) 如果k 卜o ，那么 h n ，怪q 舷z 一帅品1 叩卜卜班n j l - _ 可再而玎一f ( 2 ) 如果k l ：0 ，那么 一一 1 - 写等 | 其中，= y ( i u i - y ) l o g ：( 1 u 卜力，丑一 五r i 阻i = l ，b = 五尺l 阻i - 2 ) ， 与= r j i ：r , j 冰腺阶l 一篆 五关于r 的精度为： - 0 7 7 1 ， 五关于是的精度为： 九( 五) ：0 8 5 9 ， 五关于玛的精度为： 如( 五) ：0 9 1 7 ， 因此 噍( 五) 叱) - j 某一范畴x 时，如果砑= 劢内粒度完全一样时， 如例2 ， 。 例2 设u = l ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 ) ，u 上的等价关系心，愿，民确定的划分 为： r s = “1 ，2 ，3 ，4 ) ， 5 ，6 ) ， 7 ，8 ) ，( 9 ) ) ， 民= “1 ，2 ，3 ，4 ) ， 5 ，6 ) ， 7 ) ， 8 ) ， 9 ) ) ， 1 9 由传统精度可得： x 2 2 1 ，2 ，3 ，4 ，5 ) - 墨置= 足五= r 置= 1 ，2 ，3 ，4 ) r 五= 足五= 民五= 1 ，2 ，3 ，4 ，5 ，6 ) 氐( 置) = 呔( x 2 ) = 噍( 置) = 詈= 了2 应用基于过剩熵的精度可得： 跣) = 1 一( 1 一争( 坐等拦渺) = 0 8 6 2 7 ( 置) = 卜( 1 一势( 她鼍麓辫) = 0 8 9 6 8 战( 置) = 1 一( 1 一多( 型避搅学咝) = o 9 1 2 由我们在本节开头的分析可知，对于此例而言，用传统精度计算比用基于 过剩熵的精度计算更合理一些。为了结合这两种定义的优点，下面给出了一种 基于划分粒度的新精度。 4 3 4 基于限制在上近似考虑划分粒度的精度 为了使本节的讨论更加方便，对近似空间k = ( u ，r ) ，令划分 r = 足，心，屯) 并称臼) = z ) l 【，) 为离散划分，q ( 【，) = ) 为全体划分。 定义4 1 设u 为非空有限集，且i u l = n ，r 为u 的一个划分且 r = 墨，r ，a m ) ( 1 m n ) ，定义u 中任意两个元素x ，y 的距离为： d ( z ，y ) = 。甑5 墨母5 乓( 1 k 聊) d ( z ，y ) = 。 当，；瓦而，。墨 ( 聊) 定义4 2 设u 为非空有限集，且l u i = 力，r 为u 的一个划分且 r = r i ，恐，如) ( 1 m 刀) ，对任意b ，墨r ，r = “，而，以) ，b = 饥，儿，m ) 其中l d i s ( q ) 命题2 对于论域u 的任意两个划分p ，q 如果户 d i s ( q ) 。 证明反复应用引理l 可得d i s ( p ) d i s ( q ) 。 定义4 4 论域u 上的等价关系r 离散度归一化称为r 的散度，记为历v 似) ： 2 1 d f v ( r ) ：望坚盟 、7 d i s ( o ( u ) ) 显然有： 刚弓i 肋2 午 命题3 设u 为非空有限集，且m = 力，r 为u 的一个划分且 r = r ，r ，心) ( 1 m n ) ，则0 d i v ( r ) 1 。 证明当r = 以彤) = 缈 时，d 括( 哟= 0 ，则取最小值d i v ( r ) = 0 。 当r - 目缈) = “j ) i 膏，d i s ( o ) = c 高，则取最大值d 加( r ) = l 由命题2 知，当p d i s ( q ) ，有d i v ( p ) d i v ( q ) ，所以对 任意p ( r q g 厂) 有0 d 匆( r ) 1 。 定义4 5 设u 为非空有限集，且m = 刀，r 为u 的一个划分且 r = r 1 ，r ，如) ( 1 m ，z ) ，对任意xc _ u ，x 关于r 的上近似为 砑= 墨7 u 恐u u 墨，k m ，碍7 r ，1 f k ，则定义r 在砑上的限制为： rb = 科，r 2 ，尺。7 ) 显然，rb 是砑的一个划分，因此，d i v ( rl 斯) = 肪俾k ) 腑( 口( 砑”。 即d i v ( r ) 有的性质，d i v ( rk ) 仍然具有。 下面利用离散度来重新定义精度为： ( z ) = l 一住( x x l 一跏( r l 豇) ) ( 店( x ) = 1 一参 4 3 5 实例分析 应用珥( 柳计算例l 得： ( 墨) = 卜吾( 卜她等邀) = o 8 4 5 7 ) = l 一吾( 1 一丝幽型挚哟= o 9 0 7 4 ( x o - - 1 一s x ( 1 1 2 + 6 ) + 6 8 + 6 ，、= 0 9 3 8 3 从例1 说明基于过剩熵的精度可区分的，用基于离散度的精度同样可区分， 并且效果相同( 即后者与前者兼容) 。 应用珥( 计算例2 得： 7 ( 互) = ( 置) = ( 置) = o 8 6 2 7 从例2 说明基于离散度的精度比基于过剩熵