（应用数学专业论文）随机信息系统的知识约简.pdf

i 摘要 波兰学者p a w l a k 于1 9 8 2 年提出的粗糙集( r o u g hs e t ，r s ) 理论是一种刻画不完整性和不确定 性的数学工具，能有效分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的 知识，揭示潜在的规律该理论与其它处理不确定和不精确问题理论的最显著的区别是它无需提供 问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理可以说是比 较客观的由于这个理论未能包含处理不精确或不确定原始数据机制，所以这个理论与概率论、模 糊数学和证据理论等其它处理不确定或不精确问题的理论有很强的互补性本文将粗糙集与概率 论、证据理论相结合，主要完成了以下工作 首先，研究了一般关系下的概率粗糙集的模糊性，用模糊集来描述一般关系的概率粗糙集用 由粗隶属函数决定的模糊集的截集和强截集来描述一般关系的概率粗糙集的上、下近似，并用模糊 集的截集的特征来描述变精度粗糙集的性质 其次，在优势关系的基础上，以证据理论中的m a s s 函数为基本工具，提出了基于优势关系的随 机信息系统，研究了优势关系下随机信息系统的属性约简问题分别考虑了随机信息系统和目标随 机信息系统两种情况，并给出了实例说明约简方法的有效性 最后，提出了基于优势关系的随机信息系统的卢一近似约简和目标随机信息系统的卢一近似约 简的概念，分析了它们与已有约简概念的关系，证明了卢一近似约简是信息系统和目标信息系统的 属性约简概念的推广 关键词：粗糙集；信息系统；优势关系；证据理论；属性约简；卢一近似约简 宁夏大学硕士学位论文邱旭琴：随机信息系统的知识约简 a b s t r a c t t h ec l a s s i c a lr o u g hs e tt h e o r yi n t r o d u c e df i r s t l yi n1 9 8 2b yp a w l a kw h oi sas c i e n t i s ti np o l a n d ，i sa m a t h e m a t i c a lt o o lu s e dt oa n a l y z ea n dd e a lw i t ha l lk i n d so fi n c o m p l e t ei n f o r m a t i o ns u c ha si m p r e c i s e ， i n c o n s i s t e n t ，i n c o m p l e t ei n f o r m a t i o na n d 缸d 8i m p l i c i tk n o w l e d g e i tr e v e a l st h ep o t e n t i a lr u l e s t h e s i g n i f i c a n td i f f e r e n c ea m o n gt h et h e o r ya n do t h e rt h e o r i e sa b o u ti m p r e c i s e ，i n c o n s i s t e n ti st h a ti t i s n o tn e e dt op r o v i d ea n yp r i o ri n f o r m a t i o ne x c e p tt h ed a t as e t s oi t i so b j e c t i v et od e s c r i b eo rd e a l w i t ht h eu n c e r t a i n t yo ft h ep r o b l e m j u s tb e c a u s ei m p r e c i s eo ru n c e r t a i no r i g i n a ld a t am e c h a n i s m f a i l st ob ec o n t a i n e di nt h et h e o r y ，t h et h e o r yh a ss t r o n gc o m p l e m e n t a r yw i t hp r o b a b i l i t yt h e o r y , f u z z ym a t h ，e v i d e n c et h e o r y , a n do t h e rt h e o r i e sd e a l i n gw i t hu n c e r t a i n t yo ri n a c c u r a c y r o u g hs e t s ， p r o b a b i l i t yt h e o r ya n de v i d e n c et h e o r ya r ec o n n e c t e dh e r e t h em a i nw o r ki sf o l l o w i n g ： f i r s to fa l l ，f u z z i n e s si ng e n e r a l i z e dp r o b a b i l i s t i cr o u g hs e tm o d e li ss t u d i e d t h a ti st op o r t r a y p r o b a b i l i s t i cr o u g hs e t sb yf u z z ys e t s h o wt h ec o n c e p to fv a r i a b l ep r e c i s i o nl o w e ra n du p p e ra p p r o x - i m a t i o no fag e n e r a l i z e dp r o b a b i l i s t i cr o u g hs e tc a nb eg e n e r a l i z e df r o mt h ev a n t a g ep o i n to ft h ec u t s a n ds t r o n gc u t so faf u z z ys e tw h i c hi sd e t e r m i n e db yt h er o u g hm e m b e r s h i pf u n c t i o ni ss h o w e d a sa r e s u l t ，t h ec h a r a c t e r so ft h e ( s t r o n g ) c u to ff u z z ys e tc a nb eu s e dc o n v e n i e n t l yt od e s c r i b et h ef e a t u r e o fv a r i a b l ep r e c i s i o nr o u g hs e t s e c o n d ，r a n d o mi n f o r m a t i o ns y s t e m sb a s e do nd o m i n a n c er e l a t i o ni sr a i s e da n dt h ek n o w l e d g e r e d u c t i o no ft h er a n d o mi n f o r m a t i o ns y s t e m si sr e s e a r c h e db ym e a n so ft h em a s sf u n c t i o ni nt h e e v i d e n c et h e o r y t h er a n d o mi n f o r m a t i o ns y s t e m sa n dt h eo b j e c t i v er a n d o ms y s t e m sa r es t u d i e d t o i l l u s t r a t eo u ra l g o r i t h m ，ar u n n i n ge x a m p l ei sp r e s e n t e d f i n a l l y , t h ec o n c e p to ft h ef l - a p p r o x i m a t er e d u c t i o no f r a n d o mi n f o r m a t i o ns y s t e m sa n do b j e c t i v e r a n d o mi n f o r m a t i o ns y s t e m sb a s e do nd o m i n a n c er e l a t i o na r ep u tf o r w a r d t h er e l a t i o n s h i pb e t w e e n t h e ma n dt h ef o r m e rc o n c e p to ft h er e d u c t i o no fi n f o r m a t i o ns y s t e m si sa n a l y z e d t h a tf l - a p p r o x i m a t e r e d u c t i o ni st h ee x t e n s i o no ft h ea t t r i b u t er e d u c t i o no fi n f o r m a t i o ns y s t e m sa n do b j e c t i v ei n f o r m a t i o n s y s t e m si sp r o v e d k e yw o r d s ：r o u g hs e t ；i n f o r m a t i o ns y s t e m ；d o m i n a n c er e l a t i o n ；e v i d e n c et h e o r y ；a t t r i b u t e r e d u c t i o n ；f l - a p p r o x i m a t er e d u c t i o n 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得宁夏大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 研究生签名： 鲆7 丛琴时间：文，c 矿年，月如日 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定，即：学校有权保留送交论 文的复印件和磁盘，允许论文被查阅和借阅，可以采用影印、缩印或扫描等复制手段保 存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位论文的 全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名： 导师签名： 弁魍男 j 乳主为 时间：文舯年f 月加日 时间：硝盱月如目 宁夏大学硕士学位论文 邱旭琴：随机信息系统的知识约简 1 第一章引言 1 1 选题背景及意义 在计算机与网络信息技术飞速发展的今天，各个领域的信息与数据急剧增加，并且由于人的参 与使数据与信息中的不确定性更加显著，信息与数据中的关系更加复杂如何从大量的、杂乱无章 的、强干扰的数据( 海量数据) 中挖掘出潜在的、有用的信息，这给人类的智能信息处理能力提出了 前所未有的挑战，由此产生了人工智能研究的一个崭新的领域一数据挖掘( d a t am i n i n g ，d m ) 和 数据库知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ，k d d ) 数据挖掘将人工智能技术、数据库技术、统计学技术、可视化技术交叉融合形成一个具有广泛 应用前景的研究领域1 9 8 9 年8 月，在美国底特律召开的第l l 届国际人工智能联合会议的专题讨 论会上，提出了数据库的知识发现从1 9 9 1 年开始每年召开数据挖掘的专门会议，并于1 9 9 7 年出版 了专门杂志。k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ”f a y y a d 等人于1 9 9 6 年出版专著“a d v a n c e s i nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ”( m i t p r e s s ) 1 1 ，明确定义“k d d 是从数据集中识别出有效 的、新颖的、潜在有用的以及最终可为人们理解的非平凡知识的过程” k d d 也简称为知识发现或知识获取等，是在一个广义的数据库中挖掘潜在的规律，它可以使 用完全不同的工具所得到的结果可以是规则，也可以是关系基于案例库的知识发现一般称为归 纳学习，它以分类为玉具，得到的结果一般情况下表现为规则归纳学习是通过大量数据分类来获 得新概念和建立新规则的， 在d m 和k d d 诸多的方法中，由波兰学者p a w l a k 于1 9 8 2 年提出的粗糙集( r o u g hs e t ，硒) 理论与方法对于处理复杂信息系统不失为一种有效的方法在2 0 世纪8 0 年代初，粗糙集理论的研 究人员主要局限于东欧各国，因此当时没有引起国际学术界的重视到了2 0 世纪9 0 年代，由于该 理论在人工智能领域的成功应用，特别是1 9 9 1 年p a w l a k 出版粗糙集的第一本专著f 1 ) 以来，这个理 论引起了世界各国学者的广泛注意1 9 9 2 年，第一届关于粗糙集理论的国际学术会议在波兰召开 从1 9 9 2 年至今，每年都召开以r o u g hs e t 为主题的国际会议，推动粗糙集理论的拓展和应用 粗糙集理论是经典集合论的推广形式其主要思想就是在保持分类能力不变的前提下，通过知 识约简，导出问题的决策或分类规则该理论与其它处理不确定问题理论的最显著的区别是它无需 提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描述或处理可以说 是比较客观的然丽由于这个理论未能包含处理不确定原始数据机制，所以这个理论与概率论、模 糊数学和证据理论等其它处理不确定问题的理论有很强的互补性由于粗糙集理论能够分析处理 不精确、不协调和不完备信息，因此作为一种具有极大潜力和有效的知识获取工具受到了人工智能 工作者的广泛关注目前粗糙集理论已被成功的应用在机器学习与知识发现【1 1 、数据挖掘、决策支 持与分析【3 】、过程控制、模式识别等领域中【4 ，5 1 在粗糙集理论与其它处理不确性的理论研究中，主要集中在它与概率论、统计学、模糊数学、d s 证据理论和信息论的相互渗透和补充在信息系统中知识库的知识的类型一般有两类：类是库 中所有对象的描述是完全已知的，p a w l a k 粗糙集模型和一般二元关系下的粗糙集模型就是属于这 一种；另一类是库中对象的描述只有部分是已知的，即知识库中的知识是不确定的，它只能通过训 宁夏大学硕士学位论文 邱旭琴：随机信息系统的知识约简 2 练样本所提供的信息来刻画概念，为了使从训练样本获得的规则符合整个论域的对象，在抽取样本 时应符合统计规律性，粗糙集理论不管这一类工作，因此概率统计作为研究自然界、人类社会以及 技术过程中大量随机现象的规律性的一门学科，它与粗糙集理论的结合就显得非常自然 j 粗糙集和模糊集理论在处理不确定性问题方面都推广了经典集合论具有一定的相容性和相 似性，然而它们的侧重点不同模糊集通过对象关于集合的隶属程度来近似描述，而粗糙集通过一 个集合关于某个可利用的知识库的一对上、下近似集来描述；模糊集强调边界的不分明性，而粗糙 集强调对象间的不可分辨性；模糊集研究的是不同对象间的隶属关系，粗糙集研究的是不同类中的 对象组成的集合关系；模糊集的隶属函数大多是由专家凭经验给出，带有很强的主观性，而粗糙集 的粗糙隶属函数的计算是从被分析的数据中直接获得的，非常客观目前所见的模糊粗糙集模型和 粗糙模糊集模型 6 是二者结合的成功范例 证据理论，又称信度函数论，它是研究认识不确定性问题的另一种理论1 9 7 6 年，s h a r e r 出版了 证据理论方面的专著【7 1 ，这标志着证据理论的诞生几十年来，证据理论已经得到国际学术界的承 认为证据理论做出重大贡献的第一个人物是d e m p s t e r d e m p s t e r 于1 9 6 7 年给出了上、下概率的 概念 8 】第一次明确给出了不满足可加性的“概率”1 9 6 8 年，d e m p s t e r 针对统计问题给出了两批 证据合成的原则【9 】s h a r e r 证据理论就是在d e m p s t e r 工作的基础上产生的因此证据理论也称为 d e m p s t e r s h a f e r 理论或d s 证据理论另外，d u b o i s 、p r a c l e 、z a d e h 等也为证据理论做出了大量贡 献 1 0 t1 1 1 粗糙集理论与d s 证据理论在处理不确定性问题方面的研究方法是不同的，但却有某种相容 性，粗糙集理论是为开发规则的机器自动生成而提出的，而d s 证据理论是在给定证据下用一对信 任函数和似然函数对假设进行估计和评价粗糙集理论中的下近似和上近似概率恰好分别是信任 函数和似然函数，然而生成信任函数和似然函数的基本概率分配函数方法是不同的，前者来自系统 中数据本身，比较客观，而后者往往来自于专家的经验，带有很强的主观性粗糙集理论与d s 证据 理论有很强的互补性 人类已步入全新的时代，社会已发展成为一个宏观复杂的大系统，预测和决策所要考虑的因素 越来越多，也越来越复杂，同时科学技术达到了非常高的水平，问题的研究和解决都需要借助宏观 复杂的大系统，大系统理论和方法的研究必须有能够描述系统的数学工具，由于经典数学不能满足 这个要求，且由于人卫智能的迅猛发展，粗糙集和模糊集【1 2 ，1 3 ，1 4 , 1 引、集对分析【16 1 、v a g u e 1 7 集 等新兴理论相继产生，认识和分析它们之间的联系与区别对今后的理论和应用研究都有非常重要 的意义 1 2粗糙集理论的研究现状及趋势 近年来，由于粗糙集理论在数据库知识发现、数据挖掘、故障诊断、机器学习、知识获取、专 家系统和决策支持系统等领域的广泛应用已引起许多学者的重视因此，粗糙集模型的研究与推广 是粗糙集理论研究的一个重要方面目前，对粗糙集理论的研究主要集中在粗糙集模型的推广、问 题的不确定性研究及其它处理不确定性、模糊性问题的数学理论的关系与互补、纯粹数学理论方 面的研究等 宁夏大学硕士学位论文邱旭琴：随机信息系统的知识约简 3 1 2 1粗糙集理论研究的主要内容 ! 粗糙集的理论研究主要有如下三个方面： 第一：粗糙集代数结构【18 1 、粗糙集拓扑结构【19 1 、粗糙逻辑【2 0 1 以及粗糙哲学【2 1 】等粗糙集数 学性质方面的研究 第二：粗糙集理论模型方面的拓展研究对于粗糙集的推广研究主要集中在以下三个方面： ( 1 ) 从论域方向推广的目前主要是双论域的情形，这时的二元关系就变成了两个论域笛卡尔乘 积的一个子集对于将论域推广到多个的情形来研究粗糙集理论的文献很少，这种讨论也将随着维 数的增加变的越复杂 ( 2 ) 从关系方向推广目前有两种，一种是将论域上的二元等价关系推广为任意的二元关系得到 一般关系下的粗糙集模型【2 2 ，2 3 , 2 4 】；另一种是将对象z 所在的等价类看成是z 的一个邻域，从而推 广导出了基于邻域算子的粗糙集模型【2 5 1 也有将关系导出的划分推广成为一般的布尔代数的，以 此出发去定义粗糙集和近似算子的；更一般的有将普通关系推广成模糊关系或模糊划分而获得模 糊粗糙集模型【6 ，14 1 。 ( 3 ) 从集合和近似空间的推广，这一类推广是与其它处理不确定的知识( 概率论、模糊数学、信 息论、证据理论等) 结合起来进行研究的f 1 3 ，1 4 , 2 4 ，2 5 ，2 6 ，2 7 ，29 1 当知识库中的知识是由于随机原因或经统计得到的，即知识库中的知识很可能是不确定的，有 学者提出了概率粗糙集模型【1 4 ，3 0 ，3 1 ，32 1 ，变精度粗糙集模型【3 3 ，3 4 】实际上也可以归入这类模型， 寻求具有最小风险的贝叶斯决策问题【3 5 】也可以转化为这类模型，决策理论模型【3 6 】也可以归入这 类模型中 第三：粗糙集理论属性约简方法的研究我们经常面临的一个问题就是我们能否在保留数据表 基本性质的前提下从中移除一些数据，也就是说数据表中是否有一些冗余数据这个问题在粗糙集 理论中体现为属性约简问题所谓属性约简，就是在保持信息系统的分类能力不变的前提下，删除 其中的冗余属性，保留必要属性国内外的学者从不同角度出发，给出了信息系统属性约简的众多 方法这些方法分为以下两类： ( 1 ) 以属性的重要性作为依据【1 4 】信息系统的属性对于知识分类所起的作用不是同等重要的 有些属性是绝对不必要的，去掉这些属性不影响知识分类；有些属性是绝对必要的，去掉这些属性 必然影响知识分类；有些属性是相对必要的，它们与所有绝对必要属性放在一起构成了信息系统的 属性约简 ( 2 ) 以信息系统中任意两个对象的熵分布间的距离作为依据如果从属性集中移除某个属性， 能使该信息系统中任意两个对象的熵分布间的距离不超过某个阈值，我们就可以移除这个属性，直 到不能再移除为止，剩下的所有属性构成了该信息系统的属性约简 1 2 2 粗糙集理论的研究热点 粗糙集理论的研究热点主要包括以下几个方面： 大数据集问题现实中的数据库已经越来越大，如何降低算法的执行效率和复杂度，从众多的 数据中寻找最有用的数据，是粗糙集理论需要应对的一个挑战，虽然目前这方面已有一些研究成果 塑坠丝型兰堡壑| 些垒堕墅塑型些丝型丝一4 【3 7 ，3 8 】，但是还不完善，仍需进一步研究 缺失值处理方法在对样本数据进行处理时，往往会遇到数据丢失的问题，一般把含有丢失数 据的信息系统称为不完备信息系统造成数据丢失的原因很多，如对数据测量的误差，数据处理和 数据获取的限制等等由于经典粗糙集理论是基于完备信息系统的，为了使这一理论适合于不完备 信息系统的处理，需要采用某种方法对缺失值进行处理，建立处理不完备信息系统的扩展粗糙集模 型 3 9 1 高效的约简算法约简的求解是一个n p 难问题，导致n p 难问题的主要原因是属性的组合爆 炸高效的约简算法是粗糙集应用于知识发现的基础要在可接受的时间内获得约简的通常做法是 基于启发式知识的约简方法，国内外的学者在这方面做了研究 4 0 1 ，现在尚不存在一种非常有效的 方法因此寻求快速的约简方法及其增量版本这一问题仍是粗糙集理论的研究热点之一 多方法融合由于粗糙集理论在处理数据时存在一定的缺点，因此有必要把粗糙集和其它不确 定方法结合起来目前比较常用的做法是粗糙集与神经网络及模糊集的结合应用1 2 3 ，2 4 ，4 1 ，4 2 1 虽 然在这方面已经取得了一定的成绩，但是还有很多难点并没有解决，仍需进一步研究 1 2 3 粗糙集理论的应用研究 粗糙集主要应用在人工智能领域和数据挖掘方面，具体表现在： ( 1 ) 粗糙集应用于决策分析【4 3 1 粗糙集理论的决策规则是在分析以往经验数据的基础上得到 的，它允许决策对象存在一些不太明确的属性； ( 2 ) 粗糙集应用于智能控制【4 4 】粗糙集根据观测数据获得控制策略，称为从范例中学习，属于 智能控制的范畴； ( 3 ) 粗糙集应用于股票数据分析【4 5 】即运用粗糙集理论分析股票价格与经济指数之间的依赖 关系，并获得预测规则； ( 4 ) 粗糙集应用干医疗诊断【4 6 1 在医疗诊断方面，用粗糙集方法根据以往病例归纳出诊断规 则，用来指导新的病例； ( 5 ) 粗糙集和模糊集在文本挖掘中的应用【4 7 1 采用粗糙集和模糊集的结合，研究了信息检索中 一种新的文本挖掘机制，指出文本查询既可以使用权重表示，也允许使用基于粗糙集的近似表示 1 3本文工作要点及结构安排 粗糙集理论是一种处理不确定性知识的数学工具该理论与其它处理不确定问题理论的最显 著的区别是它无需提供问题所需处理的数据集合之外的任何先验信息，所以对问题的不确定性的描 述或处理可以说是比较客观的由于这个理论未能包含处理不确定原始数据机制，所以这个理论与 概率论、模糊数学和证据理论等其它处理不确定的理论有很强的互补性本文将粗糙集与概率论、 证据理论相结合，研究了一般关系下概率粗糙集的模糊性以及随机信息系统的约简问题，具体组织 结构如下： 第二章介绍了粗糙集理论中的基本概念，如信息系统、等价关系、约简与核、近似空间等，为后 宁夏大学硕士学位论文 邱旭琴：随机信息系统的知识约简 5 续章节对粗糙集扩展模型进行进一步探讨奠定了基础 第三章研究了一般关系的概率粗糙集的模糊性，用模糊集来描述广义概率粗糙集用由粗隶属 函数决定的模糊集的截集和强截集来描述一般关系的概率粗糙集的上、下近似，并用模糊集的截集 特征来描述变精度粗糙集的性质 第四章首先介绍了随机信息系统及证据理论的基本概念，然后介绍了随机信息系统上的优势 关系定义了基于优势关系的粗糙集近似并给出了基于优势关系的知识约简，分别考虑了信息系统 与目标信息系统两种情况，并分别给出实例说明约简的有效性此外还提出了基于优势关系下随机 信息系统的卢一近似约简和目标随机信息系统的卢一近似约简的概念，分析了它们与已有约简概念 的关系，证明了p 一近似约简是信息系统和目标信息系统的属性约简概念的推广， 第五章对本文的内容做了总结并给出对未来工作的展望 宁夏大学硕士学位论文邱旭琴：随机信息系统的知识约简 6 第二章粗糙集与信息系统 粗糙集作为一种处理不确定与不完全数据的新的数学理论，最初是由波兰数学家p a w l a k 于 1 9 8 2 年提出来的【2 】它是针对f r e g e 的边界线区域思想提出来的，p a w l a k 把那些无法确认的个体 都归属于边界线区域，而这种边界线区域被定义为上近似集和下近似集之差集由于它有确定的数 学公式描述，完全由数据决定，所以更有客观性粗糙集理论的主要优势之一就是它不需要任何预 备的或额外的先验信息 模糊集理论是由z a d e h 引入的( 4 8 1 模糊集理论与粗糙集理论都是描述不确定问题的数学工 具它们都是经典集合论的推广，虽然它们有一定的相容性和相似性，然而它们的侧重面不同从知 识“粒度”的描述上看，模糊集是通过对象关于集合的隶属程度来近似描述的，而粗糙集是通过一 个集合关于某个可利用的知识库的一对上、下近似来描述；从集合对象间的关系来看，模糊集强调 的是边界的不分明性，而粗糙集强调的是对象间的不可分辨性；从研究的对象来看，模糊集研究的 是属于同一类的不同对象间的隶属关系，重在隶属程度，而粗糙集研究的是不同类中的对象组成的 集合关系，重在分类 r 粗糙集理论是建立在分类基础上的，主要是利用已知的知识库将不确定的知识用已知的知识 库中的知识来描述它很好的反映了人们处理不确定问题的常规性，即以不完全信息或知识去处理 一些不确定现象的能力本章主要介绍经典粗糙集理论的一些概念 2 1信息系统与等价关系 信息系统是数据库的抽象描述，它在实际生活中大量存在信息系统中的信息可以是数字、语 言也可以是声音、图像人们利用已掌握的信息面对不断变化的环境和条件进行决策，同时又从成 功的决策中不断获取知识从而丰富自己的知识库因而在海量信息中提取知识，识别出正确、新颖、 有潜在应用价值的、最终可为人们理解的模式，就成为人类的特殊需要首先我们给出信息系统的 形式定义l m j t 定义2 1 1 称( 阢a ，f ) 为一个信息系统，或者数据库系统，其中【厂为对象集，即 u = z 1 ，x 2 ，2 n ) ， u 中的每个元素z i ( i 扎) ，称为一个对象而a 为属性集，即 a = 0 1 ，a 2 ，n m ) ， a 中的每个元素n z ( fsm ) ，称为一个属性f 为u 和a 的关系集，即 f = i t ：l m ) ， 其中五：u 。( f m ) ，为属性集a t 的值域 在信息系统中，关系集是非常重要的如果f 不存在，对象集u 与属性集a 之间是孤立的关 系集f 表述了对象集u 与属性集a 之间的联系，这正是知识发现所需要的信息基础属性值域 宁夏大学硕士学位论文 邱旭琴：随机信息系统的知识约简 7 ( f m ) 可以是定量值，也可以是定性值由于在知识发现的问题中主要是分类问题，我们用不同 的数值表示不同的定性属性并不会影响知识发现的过程与结果这里一般取有限个数值，并且 取 m v = u ， l - - - - l 这样使五：u 0 m ) 定义2 1 2 称( u ，a ，f ，d ，g ) 为目标信息系统或决策表，其中( 以4 ，f ) 是信息系统，a 为条件 属性集，d 为决策属性集，即 d = ( d l ，d 2 ，d p ) ， g 为u 和d 的关系集，即 g = 肌：f p ) ， 其中g t ：u - 4k ( f p ) ，v 为决策属性d f 的值域它可以是定量的也可以是定性的 在目标信息系统中，关系集g 同关系集f 一样，同样是重要的可见目标信息系统是将信息系 统中的属性分为条件属性与决策属性两类，研究它们之间的关系问题从信息系统中仅仅可以得到 分类，而从目标信息系统中可以获得决策知识 在信息系统( 以a ，f ) 中，对于属性子集j e 7 a ，记 l i b = ( z i ，z j ) ：f t ( z t ) = ，f ( z j ) ，v a t b ) 显然r b 是由属性b 确定的u 上的一个等价关系( 满足自反性，对称性，传递性) 在目标信息系统( 以a ，f d ，g ) 中，若r a r d ，则称( 以a ，f ) d ，g ) 为协调决策表 2 2信息系统的约简 信息系统中的属性并不是同等重要的，属性约简是指可以找到一个较小的属性集b a ，使得 可用a 描述的对象集合必然可用b 描述，从而消除冗余属性属性约简简化了分类的标准，同时使 得人们更加深入地认识分类的实质【13 1 定义2 2 1 设( 阢a ，f ) 是一个信息系统对于b a ，若r b = r a ，称b 是划分协调集；若 b 是划分协调集，而b 的任何真子集均不是划分协调集，则称b 为划分约简集 若r b = r ，则u j r b = u r a 从而用属性b 对u 的分类与用属性a 对u 的分类完全相 同于是用捌分协调集b 和划分约简集b 可以描述由a 描述的对象集 定义2 。2 2 设( 阢a ，f ) 是一个信息系统，记 u r a = z 】 i z u ) ， d ( x i l a ，【：g j a ) = o z a l f l ( x i ) ( ) ) 称d ( z i a ，h 】a ) 为【z d a 与 x j a 的划分辨识集，称 d = ( d ( x i a ，【。j l 4 ) i 【z i 】a ，【z j 】 u r a ) 宁夏大学硕士学位论文邱旭琴：随机信息系统的知识约简8 为信息系统的划分辨识矩阵 定理2 2 1 = 设口是信息系统( 【，a ，f ) 的划分辨识矩阵，则b 为划分协调集当且仅当对于任 意 x d an 【x j a = 0 ，有 bnd ( x i a ，p j 】 ) o 证明b 为划分协调集等价于r a 三r b ，即对于任意的( z i ，x j ) r a ，必有( 3 c i ，x j ) 车r b ，也即 k 】an z j a = 0 时必存在a l 口，使五( z i ) ，l ( q ) ，于是r a = r b 等价于bnd ( x i a ，b a ) 毋 成立 例2 1 表2 1 给出了一个信息系统 对于例2 1 可得 表2 1 信息系统 u a la 2a 3a 4 t 1 1221 x 2 3 1 2 2 x 3 1321 x 4 1 2 2 1 x 5 1212 x 6 3122 2 7122 1 x 8 1321 z 9 l 2 2 1 【z 1 a = z l ，x 4 ，x 7 ，z 9 ) ，【x 2 a = x 2 ，z 6 ) ，【x 3 a = z 3 ，z 8 ) ，【x s a = z 5 ) 于是可得到例2 1 的信息系统的简化( 见表2 2 ) 表2 2 例2 1 的信息系统的简化 u r a a la 2a 3a 4 【x t a = 【x 4 a = 【x 7 a = 【x 9 i a 1221 z 2 】a = p 6 】a 3 1 22 【x 3 a = 【x s a 1321 x s a 12l2 这里的划分辨识矩阵为 d= 0 0 1 a 2 ，c t 4 ) 0 2 ) 口1 ，a 2 ，0 4 ) 0 0 1 ，a 2 ，0 4 ) 口2 ) b l ，a 2 ，a 4 ) 0 0 3 ，口4 ) g 1 ，a 2 ，a 3 ) a 2 ，a 3 ，n 4 ) 取j e i l = 口2 ，0 3 ) 和反= 口2 ，n 4 ) ，则b 1 和b 2 都满足定理2 2 3 ，于是b l ，b 2 均为划分协调集，而 b 3 = 0 2 ) ，b 4 = 0 3 ) ，b 5 = 0 4 ) 都不满足定理2 2 3 ，即b 3 ，鼠，曰5 都不是划分协调集，因此 b 1 ，b 2 是划分约简集 宁夏大学硕士学位论文 邱旭琴? 随机信息系统的知识约简 9 定义2 2 3 设( 阢a ，f ) 是一个信息系统，b k ( k t ) 为所有划分约简集，记 c = nb k ，k = ub k c ，i = a u 鼠 k 0 ，称 p ( a i b ) = 竺善若孚为在事件b 发生的条件下事件a 发生的条件概率 定义3 1 3 【2 7 1 设u 是有限对象构成的论域，冗是u 上的等价关系，其构成的等价类为u i r ： x l ，x 2 ，) ，仍记z 所在的等价类为嘲，令p 为u 的概率分布，三元组a p = ( u ，r ，尸) 称为 概率近似空间u 中的每个子集称为概念，它代表了一个随机事件，p ( x i y ) 表示事件y 发生下x 出现的条件概率，也可解释为随机选择的对象在概念y 的描述下属于x 的概率设0 q ) ， b n ( x ，a ，p ) = 。u i 卢p ( xj x ) q ， n e g ( x ，卢) = u 预口= z u i p ( x i x ) q ) ， 分别称为a 的n 截集和n 一强截集 s u p p a = z u i a ( x ) o ) = 山， k e r a = z u i a ( x ) = 1 ) = a 1 ， 分别称为a 的支集与核 定义3 2 2 若映射d ：f ( u ) + 【0 ，l 】满足条件： 1 ) d ( a ) = 0 当且仅当a 为u 上的普通集合，即a f ( u ) ； 2 ) 当且仅当a ( u ) 三1 2 时，d ( a ) 取到最大值； 3 ) 若a ，b f ( u ) ，对v u u ，l a ( u ) 一0 5 l l b ( u ) 一0 5 1 ，则有d ( b ) d ( a ) ； 4 ) d ( a ) = d ( a 。) ，其中a 。( 乜) = l 4 0 ) ，v “u 则称d 为f ( u ) 上的一个模糊度，d ( a ) 是a 的模糊度 定义3 2 3 设“= u 1 ，? 2 2 ，u 3 ，u 。) ，a f ( u ) ，a o 5 为a 的0 5 一截集，则 ， n n d l ( a ) = 署t ) 一a o s ( 毗) i d 口( a ) = 而2 宁夏大学硕士学位论文邱旭琴：随机信息系统的知识约简 1 3 分别称为模糊集a 的线性模糊度和二次模糊度 e ( a ) = 丽1 s ( 地) ) 称为模糊集a 的模糊熵，其中s h a n n o n 函数 s c z ，2 i z l n z 一( 1 一z ) l n ( 1 一z ) z z ：e ( 。o ，】| l 定义3 2 4 设矗是u 上的二元关系，对于z ，y u ，若( z ，y ) r ，则称z 是y 的前继，y 是z 的 后继，r 。( z ) = y t = n y ，r p ( z ) = y l y n x ，r v 。( z ) = y l x r yf 马y r z ) = r v ( z ) ar 。( z ) ，曼p v 。( z ) = y l x r y 或y r x ) = r ，( z ) vr 。( z ) ，则它们分别称为z 的后继邻域、前继邻域、下继邻域、上继邻域 显然这些邻域算子有以下性质 1 ) r p 。( z ) r p ( z ) r p v 。( z ) ； 2 ) r p s ( z ) r s ( z ) r p v 。( z ) ； 3 ) r p ( z ) = r f l ( z ) ； 4 ) r q 营v x u ，r 。( z ) q 。( z ) v x u ，r p ( z ) q p ( z ) ； 5 ) ( 一r ) 。( z ) = 一r 。( z ) ，( 一r ) ，( z ) = 一r p ( z ) ； 6 ) ( rnq ) 。( z ) = r 。( z ) nq 。( z ) ，r ， 。( z ) = ( rnr 一1 ) 。( 。) ； 7 ) ( ruq ) 。( z ) = r 。( z ) uq 。( z ) ，r p v 。( z ) = ( rur 一1 ) 。( z ) 一个二元关系和邻域算子r 。和砬是相互唯一确定的，即 x r y z j c p ( 可) 甘y r 。( z ) 定义3 2 5 2 4 1 设u 是有限非空论域，r 【，u 为u 上任意二元关系，则称a = ( 阢r ) 为 广义近似空间，a 常表示为可利用的已知信息库，对任意的x 矿，x 不一定能用近似空间的知识 来精确地描述，于是就用x 关于近似空间a = ( u ，r ) 的下近似鱼匕( x ) 和上近似页a ( x ) 来近似描 述 显a ( x ) = z u i r 。( z ) x ) ， 一r a ( x ) = 。u t r 。( z ) nx 口) 本文中关于近似空间a 的正域e o s a ( x ) ，负域n e g a ( x ) 和边界b n a ( x ) 分别为 p o s a ( x ) = 显a ( x ) = z u i n 。( z ) x ) ， b n a ( x ) = 页a ( x ) 吼( x ) ， n e g a ( x ) = 一瓦a ( x ) = z c 厂i r 。 ) nx = 0 ) 。 当旦a ( x ) = p t - a ( x ) 时，则称x 关于近似空间a 是可定义的，否则称x 关于a 是不可定义的这 时称x 为粗糙集 宁夏大学硕士学位论文 邱旭琴：随机信息系统的知识约简 1 4 经典的粗糙集模型是建立在绝对精确的包含关系上的，这限制了粗糙集理论的应用一般关系 下的粗糙集模型克服了经典p a w l a k 粗糙集模型由于等价关系带来的缺陷，但仍然没有充分考虑集 合之间的定量信息，已有的概率粗糙集模型从概率论的观点出发，充分考虑了集合之间的信息，但 仍然没有克服经典p a w l a k 粗糙集模型由于等价关系带来的缺陷所以我们将一般关系下的粗糙集 与概率粗糙集模型融合起来，这样既能克服经典p a w l a k 粗糙集模型对可用信息的完全性的要求， 叉能推广粗糙集模型的适用范围：下面给出广义概率近似空间的概念 定义3 2 6u 为有限对象构成的论域，r 为u 上的一个二元关系，p 为u 上的子集类构成的 盯代数上的概率测度，则三元组a = ( u ，r ，p ) 称为广义概率近似空间u 中的每个子集称为概念， 它代表了一个随机事件，p ( y i x l c ) 表示事件x t 发生下y 出现的条件概率，也可以解释为随机选择 的对象在概念y 的描述下属于x t 的概率设0 a ， b n ( x ；q ，芦) = z u l p p ( x i r 。( z ) ) a ， n e g ( x ；) = 矿一p a z = z