（应用数学专业论文）随机信息系统知识发现研究.pdf

西南交通大学硕士研究生学位论文第顷 第1 章绪论 本章将介绍本文的写作背景及本文的主要研究工作。 1 1 引言 二十世纪七十年代初，波兰科学学院、华沙大学的学者组成了研究小 组。开始了对信息系统逻辑特性的长期基础性研究。针对从实验中得到的 以数据形式表述的不精确、不确定、不完整的信息和知识，进行了分析， 这一研究成为粗糙集理论产生的基础。1 9 8 2 年z p a w l a k 发表了经典论文 r o u g hs e t 【”，宣告了粗糙集理论的诞生。由于最初的研究大多是以波兰文发 表的，因此在当时并未引起国际上数学界和计算机界的重视，研究地域仅 局限于东欧各国。到了八十年代末，这一理论终于引起了各国学术界的注 意，许多数学家、逻辑学家和计算机研究人员对粗糙集理论及其应用产生 极大兴趣并做了大量研究工作。1 9 9 1 年z 王 a w l a k 出版的专著【1 2 】成为粗糙 集理论研究的第一个里程碑。1 9 9 2 年应用专著【3 1 的出版对这一时期的工作 成果作了极好的总结，也进一步促进了粗糙集理论的应用发展。1 9 9 2 年， 第一届关于粗糙集理论的国际学术会议在波兰召开。目前我国也有众多的 学者在研究粗糙集。我国从2 0 0 1 年开始，已经分别在重庆、苏州、舟山、 鞍山等地召开了五届中国r o u 曲集与软计算学术研讨会，多位国际著名学 者也应邀出席了这些会议并作了学术报告，为本领域研究人员提供了一个 良好的学术交流平台。这些表明了粗糙集理论与应用的研究有着广泛的发 展前景。 西南交通大学硕士研究生学位论文第2 页 粗糙集是z p a w l a l 【针对g f r e g c 的边界线区域思想提出来的。p a w l a k 把那些无法确认的个体都归属于边界线区域，而这种边界线区域被定义为 上近似集与下近似集之差集。由于上近似集和下近似集都可以通过等价关 系给出确定的数学公式描述，所以含糊元素数目可以被计算出来，从而实 现了g f r e g e 的边界线思想。粗糙集理论把一个不可定义的集合转换为可以 定义的集合，也即在集合z 上不可定义的问题，而在z 的下和上近似集上 可精确的定义。因此，在x 上不能或不方便讨论的问题，可把它移到下和 上近似集上讨论。从粗糙集理论的研究和应用的成功结果可以看出，粗糙 集理论是处理许多不完备和不确定性问题的理论工具，特别是数据挖掘和 信息聚类的理论工具。粗糙集理论的创立和发展也大大的影响和推动了粒 计算的研究和发展嗍。 粗糙集理论的发展主要有两种方法【2 6 】：构造性方法和公理化方法。构 造性方法认为下近似和上近似并非最基本的概念，它们被论域上的二元关 系、论域的划分或覆盖、邻域系统和布尔代数等更为基本的概念所刻画。 公理化方法把下近似和上近似视为最基本的概念，将注意力放在研究粗糙 集理论所产生的代数系统上，利用一个公理集来刻画上、下近似算子，揭 示公理集与此条件下所产生的代数系统之间的联系。基于构造性方法， p a w l a l 【粗糙集模型得到了推广。在p a w l a l 【粗糙集模型中，等价关系是一个 关键和原始的概念。然而，这个等价关系实际上是一个很严格的条件以至 于会限制粗糙集模型的应用领域。许多学者从理论和实际应用两方面出发 对p a w l a l 【粗糙集模型进行了扩展，主要有一般二元关系下的粗糙集模型、 变精度粗糙集模型、概率粗糙集模型、模糊粗糙集模型、基于随机集的粗 糙集模型【3 2 瑚垮。与构造性方法的研究相比较，公理化方法上的工作要少 西南交通大学硕士研究生学位论文 第3 页 些。下、上近似算子在模态逻辑中对应于必要性和可能性算予；在拓扑空 间中对应于内部和闭包算子。蜘s l 【i 研究了近似算子的公理集，c o m e r 研究了关于圆柱形代数的近似算子的公理。这些研究是在z p a w l a k 信息系 统中进行的。u n 和l i u 在拓扑空间的框架中提出论域的幂集上的一对抽象 算子的六个公理。在这些公理下，存在一个等价关系使导出的下、上近似 算子与抽象算子相同。随着研究的深入，学者们还研究了任意二元经典关 系、模糊粗糙集等的情况，取得了一些成果。 粗糙集理论作为处理模糊、不精确分类问题的新型数学工具，它能有 效的分析和处理不精确、不一致、不完整等各种不完备信息。在粗糙集理 论中使用上近似和下近似的概念，隐藏在信息系统中的知识可以被解释， 并且以决策规则的形式表达出来。目前，粗糙集理论已经被成功地应用于 机器学习、决策分析、过程控制、数据挖掘等领域。粗糙集理论作为一种 处理不精确，不确定与不完全数据的新的数学理论，是建立在分类机制基 础上的，其主要思想是利用已知的知识库，将不精确或不确定的知识用已 知的知识库中的知识来( 近似) 刻画。但是这个理论未能包含处理不精确或不 确定原始数据的机制，因此这个理论与模糊数学、伊一s 证据理论等其他处 理不确定或不精确问题的理论有很强的互补性。 粗糙集理论和模糊集理论在处理不确定性和不精确性问题方面都推广 了经典集合论，具有一定的相容性和相似性，然而它们的侧重面不同。模 糊集通过对象关于集合的隶属程度来近似描述，而粗糙集通过一个集合关 于某个可利用的知识库的一对上、下近似集来描述；模糊集强调边界的不 分明性，而粗糙集强调对象间的不可分辨性；模糊集研究的是不同对象间 的隶属关系，粗糙集研究的是不同类中的对象组成的集合关系；模糊集的 西南交通大学硕士研究生学位论文 第4 页 隶属函数大多是由专家凭经验给出，带有很强的主观性，而粗糙集的粗糙 隶属函数的计算是从被分析的数据中直接获得的，非常客观。目前所见的 模糊粗糙集模型【5 一“q 和粗糙模糊集模型是二者结合的成功范例。 粗糙集理论与d s 证据理论在处理不确定性的问题方面也具有某种 相容性粗糙集理论中的下近似集和上近似集的概率恰好分别是d s 证据 理论中的信任函数和似然函数【7 牾】，然而生成信任函数和似然函数的基本 概率分配函数( 即m 硒s 函数) 方法是不同的，前者来自于系统中数据本身， 比较客观，而后者往往来自于专家的经验，带有很强的主观性，因此粗糙 集理论与d s 证据理论有很强的互补性。 粗糙集理论与其它数学理论也有联系，并且随着对粗糙集理论研究的 不断深入。它与这些数学分支的联系也会更加紧密。例如，从算子的观点 看粗糙集理论，它与拓扑空间、数理逻辑、模态逻辑、格与布尔代数、算 子代数等联系较为紧密；从构造性和集合的观点来看，它与概率论、模糊 数学、证据理论、图论、信息论等联系较为密切。粗糙集理论研究不但需 要以这些理论作为基础，同时也相应地带动了这些理论的发展。目前，数 学理论与粗糙集理论结合起来进行研究已有文章出现，如“粗糙逻辑”【9 _ 1 “粗糙理想”、“粗糙半群”【8 】等等。随着粗糙结构与代数结构，拓扑结构， 序结构等各种结构的不断整合，必将不断涌现出新的富有生机的数学分支。 作为人工智能和认知科学中新的研究热点，粗糙集理论的有效性已被 计算机学科的基础研究人员所认可。目前，粗糙集理论已经在机器学习、 知识获取、决策分析、数据库中知识发现旧13 1 、专家系统、决策支持系统 【1 5 1 7 。1 ”、归纳推理、模式识别、智能控制等领域得到了广泛应用。 到目前为止，关于粗糙集理论与应用方面的文章很多，有关书籍也正 西南交通大学硕士研究生学位论文 第5 页 在陆续出版。一些粗糙集理论与应用综述方面的文章详细介绍了粗糙集理 论在各个阶段理论研究与应用研究方面的成果。 1 2 写作背景 不确定性可以分为随机性、模糊性和认识不确定性三种。随机性在自 然界中大量存在，它可以通过由历史资料得到的统计数字来描述，研究随 机性的理论是概率论和数理统计。模糊性通常指发生在概念上的模糊，如 大、中、小的界线模糊等，模糊集理论是处理这方面问题的有力工具。认 识的不确定性是由于人们认识水平的局限以及知识缺乏所造成。如果说随 机性和模糊性都是客观的不确定性，则认识的不确定性是主观的不确定性。 最早用于解决认识不确定性问题的方法是贝叶斯主观概率理论，但是这个 理论反映不出对知识的不知道信息。 证据理论，又称信度函数论，它是研究认识不确定性问题的另一种理 论。1 9 7 6 年，s h a f e r 出版了专著【2 】，这标志着证据理论的诞生，几十年来， 证据理论已经得到了国际学术界的承认。为证据理论作出重大贡献的第一 个人物是a p d e m p s t c r od c m p s t c r l 9 6 7 年在【7 】中给出了上、下概率的概念， 第一次明确给出了不满足可加性的概率。1 9 6 8 年，d e m p s t e r 在【1 0 】中针对 统计问题给出了两批证据合成的原则。s h a f e r 证据理论就是在d c m d s t e r 工 作的基础上产生的。因此证据理论也称为d e m p s t c r - s h a f c r 理论或d s 证据 理论。另外，d d u b o i s 、h p r a d e 、l a z a d e h 等也为证据理论作出了大量贡 献2 7 1 。证据理论广泛应用于数据处理、决策等领域。 证据理论对数据或知识的局部信念函数的计算需要凭借系统设计者的 经验事先给定，因此证据理论对不确定性的描述带有强烈的先验( 主观) 西南交通大学硕士研究生学位论文 第6 页 色彩。而粗糙集理论无需提供问题所需处理的数据之外的任何先验信息“ 从而无需对数据或知识的局部给予主观评价。因此，粗糙集理论对不确定 性的描述相对客观。所以，证据理论与粗糙集理论有一定的相容性和互补 性。 1 3 本文具体研究工作简介 粗糙集理论与证据理论都是处理不确定性知识的数学工具。近年来， 将粗糙集理论与证据理论相结合，研究随机信息系统的知识发现问题，成 为一个有活力的研究方向。在这种研究背景下，本文以证据理论中的m a s s 函数为基本工具，研究随机信息系统的知识约简与知识发现问题，具体组 织结构如下： 第一部分为绪言部分，对粗糙集理论的研究动态及本论文的选题意义 和研究目标进行了综合论述。 第二部分介绍了粗糙集理论和d s 证据理论的基本概念及关系。 第三部分介绍了粗糙集理论中的粗糙度不等式，提出了用证据理论中 的信任测度和似然测度定义p a w l a k 近似空间( u ，r ) 中粗糙度的方法，分别 研究了p a w l a k 近似空间中被近似的概念是经典集和模糊集时证据理论中的 粗糙度的性质，证明了粗糙度不等式。 第四部分首先介绍了随机信息系统的属性约简和协调的目标随机信息 系统的属性约简。本文对他们的属性约简方法作了一点修改，并在此基础 上继续讨论了不协调的目标信息系统基于正域的约简与不协调的目标随机 信息系统的信任测度的关系，并由此得到了不协调的且标随机信息系统基 于证据理论的正域约简方法；讨论了不协调的目标信息系统的分配约简与 西南交通大学硕士研究生学位论文第7 页 不协调的目标随机信息系统中的似然测度的关系，并由此得到了不协调的 目标随机信息系统基于证据理论的分配约筒方法。最后本文提出了随机信 息系统的卢一近似约简和目标随机信息系统的芦一近似约简的概念，分析了 它的一些特性及其与已有约简概念的关系，证明了口一近似约简是信息系统 和目标信息系统的属性约简概念的推广，并通过实例说明了约简方法。 堕塑奎望盔堂塑主堑塞皇堂竺量窒 蔓堕! 一 第2 章粗糙集理论和证据理论的基本概念 本章介绍本文所用到的粗糙集理论和证据理论的一些基本概念。 2 1 粗糙集理论的基本概念 2 1 1 知识与知识库 设u 一彩是有限论域，任何子集x u ，称为u 中的一个概念或范畴。 u 中的任何概念族称为关于【，的抽象知识，简称知识。p a w l a l c 粗糙集模 型中讨论的知识都是对u 形成划分的概念族。一个划分6 定义为； 6 _ x x 2 j 。 ，其中盖f 量e ，x f _ o ，置n x j l 0 ，对于i 一， f ，j 一聃川g 置l u u 上的一族划分称为，的一个知识库( h o w l e d g eb e ) h ”。 设r 是u 上的个等价关系族，【，月表示尺的所有等价关系类( 或者 u 上的分类) 构成的集合。若p r ，且p - o 则n p ( p 中所有等价关 系的交集) 也是一个等价关系，称为p 上的不可区分( i d i s c c 】f n i b i m y ) 关 系，记为加d ( 尸) 设q 也是【，上的一个等价关系族，若胁d ( p ) 互训( 口) ， 则称p 比q 细，或q 比p 粗，记为p 豆y - u y u r i y n 盖_ 彩 一 x u i x ln z - l 彩 分别称它们为z 的r 下近似集和r 上近似集。分别称星和r 为下近似算子 和上近似算子。 集合6 h 。僻) - 麟一墼称为x 的r - 边界域；胛。( x ) 一酗称为z 的 r - 正域；n 昭。( x ) - 【，一趔称为x 的搀负域。显然， 冗y = p d 僻) u 砌 僻) 令乃表示空集，x 表示u 中z 的补集。下面是p a w l a k 粗糙集模型的 上、下近似算子的一些性质【蛔： ( 1 l ) 墨( u ) - ( ，( 1 h ) r g ，) 一u ； ( 2 l ) 星( 彩) - g ，( 2 h ) 尺( g ) 一g ； ( 3 l ) 星( x ) x ，( 3 h ) x a ( x ) ； ( 4 l ) 星僻n y ) - 尽( x ) n 墨( y ) ，( 4 h ) r u y ) 一r 暖) u r 口) ： ( 5 l ) 星哩僻) ) t 丑皑) ，( 5 h ) 尺( r ) ) 一r ) ； ( 6 l ) 星僻) - 僻僻) ) ，( 6 h ) r 僻。) - ( r 僻) ) 。； ( 7 l ) z y = ，墨( z ) 星( y ) ，( 7 h ) x y = r ( 肖) 月( 1 ，) ： ( 8 l ) 墨( r ( x ) ) 一( r ( x ) ) 。，( 8 h ) r ( r 伍) ) c 一( r 晤猡： ( 9 l ) v k u r ，尽僻) j ( ，( 9 h ) v k u ，r ，r ( k ) - 足 定理2 1 2 1 【4 5 】( 1 ) x 为r 可定义集尊盈 ) 一页 ) ； ( 2 ) z 为r 不可定义集营垦 ) ，r ( 并) 西南交通大学硕士研究生学位论文 第1 0 页 2 1 3 信息系统与目标信息系统 定义2 1 3 1 “”称( u ，爿，f ) 为一个信息系统或者数据库系统，其中，u 为对象集，即： u 一缸。，而，薯) u 中的每个而( i ) 称为一个对象。a 为属性集，即： 4 一 口l ，4 2 ，) 4 中的每个口，( ，s m ) 称为一个属性f 为u 和4 的关系集，即： ，- ，：，s 肼 其中 ：u 一( ，s m ) ，为属性4 的值域 定义2 1 3 1 “”称，彳，f ，d ，g ) 为目标信息系统或决策表，其中， 缸，一，f ) 是信息系统，一称为条件属性集，d 称为目标属性集或决策属性 集，即： d 怯，d z ，d ， g 为u 和d 的关系集，即： g t g ，：，p 其中g j ：u 一叫( j 妄p ) ，巧为目标属性d 的值域。 一个信息系统对应一个知识库，其中的每一个属性决定一个等价关系。 因此，每一个属性为一知识。本质上讲，一个信息系统就是一个赋予了具 体含义的知识库。信息系统就是知识库的表格化。目标信息系统是一类特 殊的信息系统。 西南交通大学硕士研究生学位论文 第1 l 页 2 1 4 约简与相对约简 粗糙集是依赖其对属性的分类能力进行数据挖掘、知识发现的，但在 大部分情况下，属性对其分类所起作用是不同的，甚至有的属性是冗余的， 因此有必要删除冗余属性，寻找简洁的决策规则。 定义2 1 4 1 【4 5 1 设k 一( u ，尺) 是一知识库，尸r ，称p p 为_ p 中不必 要的，若猁( p ) 一加d ( p 一扫) ；否则称j p 为p 中必要的。若任一p p 是p 中必要的，则称p 为独立的，否则称p 是依赖的。 定理2 1 4 1 1 4 5 培p 是独立的，q p ，则q 是独立的。 设q p ，如果q 是独立的，且胁d ( p ) 一伽d ( q ) ，则称q 为p 的一个约 简。于是，q p 为p 的约简当且仅当q 是满足砌( p ) 一猁( q ) 的极小集。 p 的所有约简构成的集合记为r 甜( p ) 。p 中所有必要关系构成的集合记为 c d r e ( p ) ，称为p 的核。约简与核有如下关系； 定理2 1 4 2 【4 5 】c d ，e ( p ) = n r 耐( 尸) 在应用中，一个分类相对于另一个分类的关系十分重要，因此下面介 绍知识的相对约简( r e l a t i v er e d u c t ) 和相对核( r e l a t i v ec o r e ) 的概 念。首先定义一个分类相对于另一个分类的正域。 令p 和q 为【，中的等价关系，q 的p 正域记为p 啤( q ) ，即 脚( q ) 2u 麟 t 叫，0 q 的p 正域是u 中所有根据分类u p 的信息可以准确地划分到关系 q 的等价类中去的对象集合。 令p 和q 为等价关系族，r p ，如果 p 。崞“( p ) ( 觑d ( q ) ) 一p d s 耐护 r ) 沏d ( q ) ) ， 西南交通大学硕士研究生学位论文 第1 2 页 则称尺为p 中q 不必要的；否则r 为尸中q 必要的。 为简单起见，也用p d 斗( q ) 代替p d ( 即 d ( q ) ) 如果p 中的每个尺都为q 必要的，则称p 为q 独立的( 或p 相对于q 独 立) 。 设s p ，s 为p 的q 约简当且仅当s 是尸的q 独立子族且 p o s ，( q ) 一p ，( q ) a 尸的q 约简简称为相对约简。 p 中所有q 必要的原始关系构成的集合称为p 的q 核，简称为相对核， 记为c 0 7 ( p ) 相对核与相对约简有如下关系： 定理2 1 4 2 ( p ) - n r 缸口( p ) ，其中r e d 口尸) 是所有p 的q 约简 构成的集合。 定理2 1 4 3 设p ，q 是u 上的等价关系族，则s p 是p 的q 约简当且 仅当s 是p 的q 独立子集且对于任意有豇x ) 一点暖) 2 1 5 区分矩阵与区分函数 对于信息系统s 一，爿，f ) ，设i u l n ，s 的区分矩阵是一个h 万矩阵， 其中任一元素为口( x ，_ ) ，) 一如爿：，：o ) 一( y ) ) 。即口( x ，) ，) 是区分对象x ，) ， 的所有属性的集合。 对于任一属性口爿，指定一个布尔变量( 仍记为口) 与4 对应。 若a ( x ，y ) _ 0 ，则记口( 石，y ) = 口1v 口2v v ( a 0 ，y ) 一 4 1 ，4 2 ，吒) ) 若a ( z ，y ) 一g ，贝0 记a ( 石，) ，) * 1 信息系统s 的区分函数是如下的布尔函数： 扣扛，唇。口芝口o ，_ ) ，)扛，y ) 巨，x 口 西南交通大学硕士研究生学位论文第1 3 页 这是一令合取范式，其中n 表示合取。 定理2 1 5 1 【4 5 】若日量4 是满足条件“b n a 0 ，) ，) 一彩，若口g ，y ) - d ” 的极小子集( 关于集合包含关系) 当且仅当口是4 的一个约简。 定理2 1 5 2 c o 旭a ) 一伽一i 存在x ，y u ，使口0 ，y ) 一 口) ) ，即核是 区分矩阵中所有单元素组成的集合。 定理2 1 5 3 1 4 5 】区分函数的极小析取范式中的所有合取式是属性集4 的所有约简。 此定理给出了由区分矩阵构成区分函数，再由区分函数的极小析取子 式得到的所有约简的方法。 决策表s 一，4 ，d ，g ) 的区分矩阵是一个n ，l 矩阵，其任一元素为 a + 0 ，) ) t 口爿：无扛) _ ，4 ( ) ，) 且口0 ，) ，) ) 对于，_ ) ，矿，埘0 ，) ，) 满足 x p d ( d ) 且y 隹p a 如 ) 或 x 隹p d 翟) 抄p d ( d ) ，或 x p ) ，) ，p 。 ) 且o ，y ) 售f 以a ) 决策表s 的区分函数a 定义为a 一 兀口( x ，_ ) ，) 社y ，掣x u 定理2 1 5 4 【4 5 】若c c 是满足条件c n 口0 ，y ) - 彩， v a 0 ，y ) 一g ”的极小子集( 关于集合包含关系) ，则c 是c 的d 约简( 相 对约简) 。 定理2 1 5 5 1 4 5 1c o r ( c ) ； 口c i a 0 ，y ) 一扣 ，其中工，y u ) 定理2 1 5 d 【4 5 】区分函数的极小析取范式中的所有合取式是c 的所 有d 约简。 西南交通大学硕士研究生学位论文 第1 4 页 2 2 证据理论的基本概念 证据理论是s h a f c r 在d 锄p s t c r 工作的基础上于1 9 7 6 年正式提出的， 因此证据理论又称为d e 唧s t c r s h a f e r 理论，它也是一种处理不确定性问题 的工具。概率推理模型中，必须给出先验概率，而证据理论则能处理这种 由不知道引起的不确定性。证据理论满足比概率论更弱的公理系统，当概 率值已知时，证据理论就变成了概率论。 2 2 1 基本概率分配函数 定义2 2 1 1 【( 辨识框架) 设有一个判决问题，对于该问题所能认识到 的所有可能的结果用一个有限集合表示，那么人们所关心的任一命题都 对应于缈的一个子集，则称该集合为辨识框架( 缸皿co fd i s c 锄e n o 。它 的建立依赖于人们的认识水平。 定义2 2 1 2 2 刀设矽是辨别框架，集函数m ：p ( 形) 一【0 ，1 】若满足： ( m 1 ) 肌( y ) 芑o ( y p ( 缈) ) ， ( m 2 ) 罗朋) - 1 ， 则称小是对应于辨别框架矽的m 鹤s 函数或基本概率分配函数( b p a f ) 称 肌( y ) 为l ，的基本概率数。肌( y ) 的意义为： 若y c 矽且i y i 一1 ，则m ) 表示对y 的信任程度；若i y l 一1 ，则m p ) 表 示对y 的精确信任程度；若j ，一形，则玳( 1 ，) 表示这个数不知如何分配。其 中l y l 表示集合】，中元素的个数。 定义2 2 1 3 【卅 若y p ( 缈) 满足_ i ，l o ，) ，0 ，则称y 是m 的一个焦元， 的焦元的全体称为研的焦集，记m 的焦集为 西南交通大学硕士研究生学位论文第1 j 夏 m ； y 尸( 形) ：m ( n o 】 例2 1 设形= 红，黄，白，尸( 矽) 上的基本概率分配函数m 为： m ( 红) ， 黄) ， 白) ， 红，黄 ， 红，白) ， 黄，白) ， 红，黄，白 ， g ) = ( o 3 ，o o ，0 1 ，0 2 ，o 2 ，0 o ，o 2 ，0 o ) 其中m ( 红 ) = o 3 表示对命题 红) 的精确信任程度； m ( 红，黄，白) ) = o 2 表示不知道这o 2 如何分配； 坍( 红，黄 ) = o 2 表示这o 2 是对命题 红，黄 的信任程度，但不知道这 0 2 如何分配给 红) ， 黄) 。 值得注意的是 研( 红) ) + m ( 黄 ) + m ( 白) ) = o 3 + o o + 0 1 = o 4 1 因此m 不同于概率p ，因为p ( 红 ) + p ( 黄 ) + p ( 白) = l 。 2 2 2 信任测度与似然测度 证据理论用信任测度和似然测度来描述信息的不确定性。 定义2 2 2 1 嗍命题z 的信任测度& f ：尸( 矽) 一【0 ，1 】为： 删僻) 。善删 占p ，僻) 表示对x 的总的信任的最小值。 由于证据理论不满足叠加定律，因此，命题石的信任测度鼬z 僻) 并不 表示其否命题的信任测度值为1 一b e z 僻) 。如在例2 1 中 曰e z “红，黄) ) = 坍( 红 ) + 历( 黄) ) + m ( 红，黄) = 0 3 + o 0 + o 2 = o 5 b e f ( f 与，) lo 2 - 1 一o 5 西南交通大学硕士研究生学位论文 第1 6 页 定义2 2 2 2 【4 6 1 命题z 的似然测度只：p ( 矿) 一n 1 】为： 尸f 僻) = 1 一眈2 暖) i ，墨。m ) p ? 僻) 表示对z 的总的信任的最大值，或不否定命题z 的程度。 显然，p f 僻) 苫占p f ( x ) 。 眈z ( x ) 和科( z ) 分别为命题工的信任度的下限和上限，记作 z 【曰e z 倦) p f 僻) 1 。如在例2 1 中 舵f ( 红) ) = m ( 红) ) + m ( 乃) ) = 0 3 + o 0 = 0 3 肼( 红) ) = 1 一丑“( 黄，白) ) = 1 一( 埘 黄) + m 白) + 埘 黄，白 ) = 1 一( o + 0 1 + 0 ) = o 9 命题的信任度的上限和下限反映了命题的许多重要的信息。下面对一些 典型值进行讨论。 x 【0 ，1 】：说明对z 一无所知。 工【1 ，1 】：说明z 为真。 x 【o ，0 】：说明x 为假。 z 【o 6 ，1 】：说明z 比较真( 对x 部分信任) 。 x 【0 ，o 4 】：说明x 比较假( 对j 部分信任) 。 x 【o 3 ，0 9 】：说明对置和j 都部分信任。 对于同样的证据，由于来源不同，会得到不同的概率分配函数。证据理 论用正交和来组合这些函数。 定义2 2 2 2 4 q 设，m ：，为尸( ) 上的，1 个基本概率分配函数，它 们的正交和m 一0 m 。o o n 为 西南交通大学硕士研究生学位论文第1 7 页 f 胁( 0 ) 一o 1 m 似) _ “。摹。卫啊) 彳_ g 式中肌龇1 1 一蒜卫镌) i 。荟。n 嘶) 决定。若七。1 0 之 2 3 证据理论与p a w ia k 粗糙集的关系 在证据理论中有一对重要的数值型测度：信任测度与似然测度。而在 粗糙集理论中有一对非数值型的算子：下近似算子与上近似算子。它们之 间有着密切的联系。 在粗糙集理论中，上、下近似算子满足关系星僻) 。( - 僻) ) c ( v y u ) ， 则称下、上近似算子耳是对偶的。在证据理论中，如果信任铡度与似然 测度满足关系丑e f ( z 。) - l 一州僻) ( 珏u ) ，则称信任测度艇f 与似然测度 p f 是对偶的。 定理2 3 1 h 6 l 设，胄) 是p a w l a k 近似空间，则由它导出的下近似算子星 和上近似算子画是对偶的，对于，d r ) ) 上的任何正规概率测度p ( 即 盯( u r ) ，p 僻) 一0 当且仅当e a ) ，记 ! 僻) _ p ( 墨( 肖) )g ( z ) - p ( r ) )僻u ) 则里，留是u 上的一对对偶的信任测度与似然测度，其对应的m a s s 函数为 胁o ) 一脾 焦点集为m = u ，r 定理2 3 2 1 4 q 若b 8 f 与p f 是u 上一对对偶的信任测度与似然测度且6 e z 的m a s s 函数的焦元全体m 构成了【，的分划，则存在p a w l a l 【近似空间，r ) 西南交通大学硕士研究生学位论文第1 8 页 和定义在代数口( 吖) 上的一个正规概率测度p ，使对于任意置尸( u ) ， 留) 一p f 僻) ，叮僻) 一眈z 僻) 定理2 3 。3 】设，固是p 8 w l l l 【近似空间，p 是定义在口缈，r ) 上的正 规概率测度，记 只( 盖) - s u p p ( y ) ：y 盯( u r ) y z ) ( x u ) 尸+ ( z ) i n f p ( y ) ：】，盯( ( ，月) y x ) ( x u ) 则 p ( 足( x ) ) 一只( 石)p ( r ( x ) ) 一p ( x ) ( x u ) 西南交通大学硕士研究生学位论文第1 9 页 第3 章粗糙度不等式 本章首先介绍了粗糙集理论中当被近似的概念是经典集合时和被近似 的概念是模糊集合时的粗糙度不等式，然后提出了用证据理论中的信任测 度和似然测度定义p a w l a k 近似空间( u ，r ) 中粗糙度的方法，分别研究了 p a w l a k 近似空间中被近似的概念是经典集和模糊集时证据理论中的粗糙度 的性质，证明了粗糙度不等式。 3 1 粗糙集理论中的粗糙度不等式 3 1 1 被近似的概念是经典集合时的粗糙度不等式 给定知识库k - ( u ，旯) ，其中u 是有限非空论域，r 是一个等价关系的 集合，对于搬u ， 集合z 的下、上近似集分别为： 蟹一u ( y ，r i y x 卜缸u i p k 垡x r z - u 侈u 胄l y n x ，l 彩) 一 x u l 防k n z g ) 它们满足下列性质： 定理3 1 1 1 【4 5 】( 1 ) zg j 讶 ( 2 ) r ( x u l ，) _ r z u r y尽( x n y ) l 墨z n 尽y ( 3 ) 星( z u y ) 星z u 尽y 瓦( 盖n y ) 夏膏n 瓦y 集合的不精确性是由于边界域的存在而引起的。集合的边界域越大， 其精确性越低。为了更准确地表达这一点，引入精度的概念。 由等价关系r 定义的集合并的近似精度为【蛔： 西南交通大学硕士研究生学位论文第2 0 贾 州卜斛， 其中盖一d ，陋i 表示集合x 的基数。 精度( x ) 用来反映对集合z 的知识的了解的完全程度。显然，对每 一个等价关系尺和集合x u 有o s 僻) s 1 。当僻) 一1 时，工的月- 边界为空集，集合工为r - 可定义的：当a 。) c 1 时，集合x 有非空尺一边 界域，集合z 为r 不可定义的。 还可以用粗糙度来定义集合x 的不精确程度。集合x 的r 粗糙度 m 瞄) 定义为： 风僻) - 1 一暖) 集合z 的r - 粗糙度与精度恰恰相反，它表示的是对集合x 的知识的了 解的不完全程度。 由此定义可以看出，粗糙集理论与概率论和模糊集合论不同，不精确 性的数值不是事先假定的，而是通过表达知识不精确性的下、上近似集概 念计算得到的，这样不精确性的数值具有客观性。 集合x ，y ，x u y ，z n y 之间的粗糙度满足如下的定理： 定理3 1 1 2 设渺，r ) 是p a w l a k 近似空间，z ，y u ，则关于集合 x ，y ，肖u y ，石n y 之间的粗糙度有关系 p 僻u y ) p u 时b p ( 盖) 障l + p ) 1 豇i _ p 僻n y ) 陋n 时i 证明由定理3 1 1 1 的( 2 ) 和( 3 ) 有 p ( x uy ) 一1 一 p 僻n y ) 一1 一 幽小幽小幽 l r ( xu y ) 11 月u 月y 1l 翩u r y i 幽。一鞘s ，一幽 t = t 每1 一t ：叶5 1 一t = _ i r ( 盖ny ) li r ( 石n y ) ll r yn r y l 西南交通大学硕士研究生学位论文第2 1 页 因为对于任意有限经典集合x 和y 有 防u y ie 防i + p i 一防n y i 从而 旭恤u j i y | 廿糊杠豇i = 【1 一 】| 砑u 西i = 降u 豇l 一| r 瞄u y ) j 降u 露i 一瞄u 星y i 2 障h 别一p n 厨i 一阻h 垦y i + 世n 星y i s 刚+ 刚一瞄| _ i 尽y i p 暖n y ) 降n 静l 2 p 啤) 障i + p o ，) l 露| _ p 瞵n d | 豇n 豇i 因而不等式得证。 3 1 2 被近似的概念是模糊集合时的粗糙度不等式 设口，r ) 是p a w l a l 【近似空间，对于u 上任意的f i l z z y 集合肖，z 关于 近似空间p ，尺) 的下近似星( 盖) 与上近似i ( z ) 是u 上的一对f i l z z y 集合，其 隶属函数分别是【4 司 垦( x ) 0 ) = m i n 仁( ) ，) ：y 陋k )( x u ) 舟【x ) 0 ) - i a 】( z ( y ) ：) ，【z k )( x u ) 则墨僻) 和月僻) 分别称为f u z z y 集合x 关于近似空间秽，r ) 的下近似和上近 似，而照：，) 一f ) 和月：f p ) 一，) 分别称为下近似算子和上近似算 子。 定理3 1 2 1 1 4 q 设缈， ) 是p a w l a k 近似空间，近似空间p ，月) 的f l l z z y 渊 西南交通大学硕士研究生学位论文第2 2 页 下近似算子与f u z z y 上近似算子有以下性质： ( 1 ) 丛肖厨 ( 2 ) 尺( 盖u y ) _ r z u r y星( z n y ) l 6 n 尽y ( 3 ) 8 ( x u y ) 墨y u 尽y瓦僻n y ) 豆r n 再y 设，r ) 是p a w l a 】c 近似空间，对于任意的o s 口，卢s 1 ，及u 上任意的 f l j z z y 集合盖，记 r ( z ) 。t 忸u ：星( 盖) o ) 口 r ( x ) ，一缸u ：胄( 工) o ) 卢) 对0c 卢口s 1 ，定义u 上的f l l 踞y 集合z 的粗糙度和精度分别为； m 位，卢) - l 一 ， a z ( 口，卢) i 约定当i 僻) 。一g 时p 。( 口，卢) - o ，从而有如下定理： 定理3 1 2 2 【4 6 】设z ，y 为【，上的f u z z y 集合，则关于集合 z ，y ，xu y ，xn y 之间的粗糙度有关系 p ，。，( 口，卢) i 瓦( z ) ，u 瓦( y ) ，i s 以( a ，卢) i 瓦僻) 小- n ( 口，卢) 陋f ) ，| - 以。，( a ，卢) i 豆僻) ，n 瓦侈) ，l 3 2 证据理论中的粗糙度不等式 3 2 1 被近似的概念是经典集合时证据理论中的粗糙度不等式 设( u ，r ) 是p a w l a l 【近似空间，r 是论域u 上的等价关系，u r 是相应 的分划，则由它导出的下近似算子星与上近似算子瓦是对偶的，对于 ，仃( u r ) ) 上的任何正规概率铡度p ，对z u ，记 曰e k ( 石) 一p 哩僻) ) 州。( x ) = 尸( - ( x ) ) 西南交通大学硕士研究生学位论文第2 3 页 则b e f 。与p f 。是u 上对偶的信任测度与似然测度l 蜘。 称( z ) 一器是z 关于近似空间，r ) 的精度； 称 岛僻) = 1 一晤) 是置关于近似空间，r ) 的粗糙度。精度a 。僻) 反映了在 关系尺下对集合z 的信任程度。 规定僻) - o 时，攻暖) - o ，并且在不会引起混淆的情况下可以省 略下标r 。 定理3 2 1 1 设( u ，r ) 是p a w l a k 近似空间，x ，y u ，则关于集合 z ，y ，zu y ，zn y 之间的粗糙度有关系 户( x u y ) p f ( x uy ) p ( z ) 用僻) + p ) p j 口) 一p ( x n y ) 科暖n y ) ( 3 - 1 ) 证明由尺僻n 】，) 麟n 口和测度的单调性有 | p ( r ( z n y ) ) s p ( 足z n r r ) 由旦何u y ) 蹦u 掣和测度的单调性有 p ( 尽( zu y ) ) 苫p u 星印 于是 p ( 并u y ) p f ( zu y ) ；【l 一勰】p 佤( 孑u y ) ) 。尸似( z u y ) ) 一p 哩( z u y ) ) p 时) p f 僻) + p ( y ) p f ) 一p 僻n y ) 科 n y ) = p ( r x ) 一p ( 骚) + p ( 幽一p ( y ) + p ( 星( z n y ) ) 一p ( r ( x n y ) ) = 【p ( r x ) + p ( 肼) 一p 僻( 并n y ) ) 】1 p ( 墨z ) + p ( 量y ) 一p ( 墨( 置n y ) ) 】 苫 p ( 尼z ) + p ( 腰) 一p ( r z n 盯) 】一【尸( 鲋) + 尸( 尽y ) 一p ：n 】 ( 3 2 ) 因为对于任意有限经典集合x 和l ，有 西南交通大学硕士研究生学位论文第2 4 页 p ( x u y ) 一p ( 盖) + p ( y ) 一p ( xn y ) ， 从而 ( 3 - 2 ) 式= 2p ( r xu 月y ) 一p ( u1 8 y ) 苫p ( r ( zu y ) ) 一p 乜至( zu y ” 2 p 仁u y ) p f uy ) 因而不等式得证。 定理3 2 1 2 设，r ) 是p a w l a l 【近似空间，盖，y u ，若 p ( 星僻u y ) ) 一尸 u 拶) 且_ p ( 瓦僻n 】，”一p 皿n ：两 则( 3 - 1 ) 式中等号成立。 证明由定理3 2 1 1 ，此定理显然成立。 3 2 2 被近似的概念是模糊集时证据理论中的粗糙度不等式 设，r ) 是p a w l a l 【近似空间，对于【，上任意的比z y 集合盖，x 关于 近似空间缈，尺) 的下近似星僻) 与上近似i 僻) 是u 上的一对f i l ：琵y 集合，其 隶属函数分别是 墨( x ) 0 ) a m i n 石0 ) ：_ ) ，臣k ) u ) r ( x ) ( 砷一m a x x ( _ ) ，) ：_ y 胁k 0 u ) 设尸为u 上的正规概率测度，对任意x f ) ，定义u 上的模糊集合 星( z ) 与- ( j ) 的概率为 p 哩僻) ) 。互p ( 缸 逑瞄) 。) p 函僻) ) 。互尸( 扛) ) 承x ) ) 记 眈k 僻) - p 逸僻) ) ，p f 。僻) - p ( _ 僻) )僻f ( u ) ) 则舵与p k 也是u 上的信任测度与似然测度 4 6 1 。 西南交通大学硕士研究生学位论文第2 5 页 设( u ，r ) 是p a w l a k i 丘似空间，对于任意的o a ，卢1 ，及u 上任意的 f u z z v 集合盖，记 r ( x ) 。一忸u ：星( 盖) ) 口r ( x ) 。- x 【，：r 僻) 0 ) 土卢 设p 为u 上的正规概率测度，若对z f ) ，记 丑( x ) = p 噬( x ) 。) ，j 堞( z ) 一p 僻( z ) 。) 则现瑶与p f f 显然也是u 上的信任测度与似然测度。 称响胁器是z 关于近似空间) 的精度；称 既 ，卢) - 1 一口。 ，卢) 是z 关于近似空间( u ，胄) 的粗糙度。 定理3 2 2 1 设( u ，r ) 是p a w l a l 【近似空间，z ，y f ) ，则关于集合 z ，l ，zu y ，zn y 之间的粗糙度有关系 岛u r ，卢) j 哗( x u y ) s p ，扣，卢) 础c x ) + m ，卢) p 瑶) 一办n r ( 口，卢) 硝( y n y ) 证明类似定理3 2 1 _ 1 可证。 西南交通大学硕士研究生学位论文 第2 6 页 第4 章随机信息系统的属性约简 属性约简是信息系统知识发现研究的核心内容之一。信息系统的属性 约简是要在属性集中寻找一个最小的属性集，它能完全确定知识发现，也 即由这个最小属性集确定的分类知识与用全体属性集确定的分类知识是相 同的。目标信息系统的属性约简是在条件属性中寻找一个最小的属性集， 可以完全确定目标分类。对完备的目标信息系统的属性约简问题，目前学 术界进行了大量的研究，学者们依据不同标准提出了多种约简方法，如基 于正域的约简，基于信息熵的约简，基于包含度的约简等。由于约简的标 准不同，约简的方法与结果也不尽相同。总地来说，信息系统地约简是在 保持知识库地分类能力或决策能力不变地条件下，删除其中不相关或不重 要地知识。 文献 4 6 讨论了等价关系下随机信息系统和协调的目标随机信息系统 基于证据理论的约简。本章对文献 4 6 中提出的约简方法作了一点修改， 并在此基础上继续讨论了不协调的目标信息系统基于正域的约简与不协调 的目标随机信息系统的信任测度的关系，并由此得到了不协调的目标随机 信息系统基于证据理论的正域约简方法；讨论了不协调的目标信息系统的 分配约简与不协调的县标随机信息系统中的似然测度的关系，并由此得到 了不协调的目标随机信息系统基于证据理论的分配约简方法。最后本章提 出了随机信息系统的卢一近似约简和目标随机信息系统的口