(应用数学专业论文)基于粗糙集的贝叶斯分析.pdf_第1页
(应用数学专业论文)基于粗糙集的贝叶斯分析.pdf_第2页
(应用数学专业论文)基于粗糙集的贝叶斯分析.pdf_第3页
(应用数学专业论文)基于粗糙集的贝叶斯分析.pdf_第4页
(应用数学专业论文)基于粗糙集的贝叶斯分析.pdf_第5页
已阅读5页,还剩26页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 摘要 糙集理论是波兰科学家z p a w l a k 在1 9 8 2 年提出的一种新的分析数据的数学理论如今它在 计算机应用的很多领域,如数据挖掘,机器学习,知识发现等,有着重要的应用对其理论方法及 其应用的研究成为当前的一个热点 本文基于粗糙集理论,做了下面的工作: 首先,介绍了几种常见的粗糙集模型,包括p a w l a k 粗糙集模型,变精度粗糙集模型,以及贝 叶斯粗糙集模型基于多数包含关系,给出一种新的贝叶斯粗糙集模型举例说明了该模型的有效 性 其次,将含有两个决策类的贝叶斯粗糙集的情况推广至含有多个决策类的情况,讨论了相关 的性质以全局增益作为启发式信息,给出了基于该模型的属性约简的一个启发式算法,举例说 明该算法是可行的 最后,研究了决策规则,决策算法的概念,说明每个决策表都满足一定的概率性质,特别是满 足全概率公式和贝叶斯定理 本文的研究成果对贝叶斯粗糙集模型的进一步研究和应用具有重要性 关键词:粗糙集;贝叶斯;属性约简;决策表 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 i i a b s t r a c t t h er o u g hs e tt h e o r y , p r o p o s e db y 。p o l a n ds c i e n t i s tp a w l a k ,i san e wm a t h e m a t i ct o o lf o rd e a l i n g w i t ht h ei n d e f i n i t em e s s a g e a tp r e s e n t ,i tp l a y sa ni m p o r t a n tr o l ei nm a n ya r e a sc o n c e r n i n gt h e u s eo fc o m p u t e r ,s u c ha sd a t am i n i n g ,m a c h i n el e a r n i n ga n dk n o w l e d g ed i s c o v e r i n g t h er e s e a r c ho f t h e o r e t i cm e t h o da n di t sa p p l i c a t i o ni sah o tt o p i cn o w b a s e do nt h er o u g hs e tt h e o r y , t h et h e s i sd o e st h ef o l l o w i n gr e s e a r c h f i r s t l y , t h et h e s i si n t r o d u c e s s e v e r a lc o m m o n l yu s e dr o u g hs e tm o d e i s ,i n c l u d i n gp a w l a kr o u g h s e tm o d e l ,v a r i a b l er o u g hs e tm o d e l ,b a y e s i a nr o u g hs e tm o d e l b a s e do nm o s to ft h ec o n t a i n r n e n t r e l a t i o n s h i p ,an e wb a y e s i a nr o u g hs e tm o d e li sp r o p o s e da n dt h ev a l i d i l i t yo ft h em o d e li si l l u s t r a t e d b yn u m e r i c a l s e c o n d l y , b a y e s i a nr o u g hs e tm o d e lf o rt w od e c i s i o nc l a s s e si se x t e n d e dt om o r ed e c i s i o nc l a s s e s c o r r e s p o n d i n gp r o p e r t i e sa x ed i s c u s s e da n dah e u r i s t i ca l g o r i t h mi sp r o p o s e dw h i c hr e g a r d e sg l o b a l r e l a t i v eg a i na st h eh e u r i s t i ci n f o r m a t i o n t h i r d l y , t h et h e s i ss t u d i e st h ec o n c e p to fd e c i s i o nr u l ea n dd e c i s i o na l g o r i t h m f o rt h ed e c i s i o n t a b l e ,i ti sr e v e a l e dt h a te v e r yd e c i s i o nt a b l es a t i s f y i n gac e r t a i np r o b a b i l i t yp r o p e r t y , e s p t o t a l p r o b a b i l i t yt h e o r e ma n db a y e s i a nt h e o r e m t h es t u d yo ft h et h e s i si si m p o r t a n tt ot h ef u r t h e rs t u d ya n da p p l i c a t i o no ft h eb a y e s i a nr o u g h s e t m o d e l k e y w o r d s :r o u g hs e t ;b a y e s i a n ;a t t r i b u t er e d u c t i o n ;d e c i s i o nt a b l e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰 写过的研究成果,也不包含为获得宁夏大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示 了谢意。 研究生签名:萃雪盈 时间:m年夕月如日 , 关于论文使用授权的说明 本人完全了解宁夏大学有关保留、使用学位论文的规定,即:学校有权保留送交论 文的复印件和磁盘,允许论文被查阅和借阅,可以采用影印、缩印或扫描等复制手段保 存、汇编学位论文。同意宁夏大学可以用不同方式在不同媒体上发表、传播学位论文的 全部或部分内容。 ( 保密的学位论文在解密后应遵守此协议) 研究生签名:挛雪乙时间: 矽 年上月功日 跏签名:巍之夕 帅。即年朋 宁夏大学硕士学位论文栾云飞:基于粗槌集的贝叶斯分析 1 第一章引言 1 1粗糙集的研究历史和现状 1 1 1 粗糙集的研究历史 粗糙集理论是波兰科学家z p a w l a k 在1 9 8 2 年提出的一种新的分析数据的数学理论【1 1 1 9 9 1 年p a w l a k 教授的第一本关于粗糙集的专著【2 j 和1 9 9 2 年r s l o w i n s k i 主编的关于粗糙集应用及其 与相关方法比较研究论文集【3 】的出版,推动了国际上对粗糙集理论与应用的深入研究1 9 9 2 年在 波兰召开了第一界国际粗糙集讨论会,这次会议着重讨论了集合近似定义的基本思想及其应用, 其中基于粗糙集的机器学习的基础研究是这次会议的四个专题之一经过几年的发展,1 9 9 9 年1 1 月在日本,2 0 0 0 年1 0 月在加拿大又分别召开了第一届和第二届“c u r r e n tt r e n do fr o u g hs e ta n d c o m p u t a t i o n ”学术会议,来自波兰,美国,加拿大,日本,挪威,俄罗斯等国家的研究人员参加 了会议,会议阐述了当前粗糙集,模糊集的研究现状和发展趋势,指出将着重在软计算,数据库, 近似推理等理论和应用方面发展目前,许多关于人工智能,模糊集理论,信息管理与知识发现等 国际学术会议上经常可以看见涉及粗糙集的论文f 4 】一【9 j 我国自2 0 0 1 年起每年召开粗糙集软计算为主题的全国性学术会议,这系列会议对我国的粗糙 集和软计算理论与应用的研究有很大的促进作用2 0 0 3 年还成立了中国人工智能学会粗糙集与 软计算专业委员会,这对我国粗糙集理论的传播与发展产生了积极的作用 我国对粗糙集理论的研究虽然起步较晚,但也取得了一系列的研究成果西安交大的张文修 教授对粗糙集理论和概念格理论都有深入探讨【4 卜悯6 ,重庆邮电的王国胤教授,南昌大学的刘清教 授先后出版专著来介绍粗集1 7 1 使得对粗集的研究成为学者们普遍重视和高度关注的热点 粗糙集不但在理论上得到不断完善,在应用方面的研究也在不断涌现 ( 1 ) 在数据库知识发现方面 8 j :k d d ( 数据库知识发现) 是当前人工智能和数据库技术交叉学 科的研究热点之一粗糙集方法已成为k d d 的一种重要方法,其导出的知识简洁且便于存储和使 用,与其它知识发现的方法比较,粗糙集方法有如下的特点:粗糙集方法的伸缩性强;鲁棒性和抗 噪音能力强;知识的可理解性和开放性较好;比较适合于符号信息此外,粗糙集方法可以数据进 行预处理,去掉多余属性,可提高发现效率,降低错误率 ( 2 ) 在模式识别方面【9 】:粗糙集理论可用在模式识别的特征选取中,选择那些确实能表征该模 式的特征项 ( 3 ) 在医疗诊断方面1 1 0 】:粗糙集方法根据以前的病例归纳出是否得病的决策规则,并用这些 决策规则来诊断新的病例 ( 4 ) 在人工神经元网络应用方面【1 1 】:训练时间过于漫长的固有特点是制约人工神经元网络实 用化的因素之一应用粗糙集化简神经网络训练样本数据,可使训练速度提高许多倍,获得了较 好的效果 ( 5 ) 在粗糙控制方面| 1 2 1 :粗糙集根据观测数据获得控制策略的方法被称为从范例中学习,属 于智能控制的范畴 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 2 ( 6 ) 在决策分析方面1 1 3 :粗糙集的决策规则是在分析以往经验数据的基础上得到的粗糙集 允许决策对象中存在一些不太明确,不太完整的属性,弥补了常规决策方法的不足 除此之外,还有图像处理,故障诊断等等 虽然粗糙集理论至今只有二十几年的发展历史,但取得的研究成果是令人瞩目的,它是一种 非常有前途的软计算方法,为处理不确定信息提供了强有力的分析手段具有广阔的发展空间, 今后会在更多的实际领域中发挥作用 1 1 2 粗糙集的研究现状 对粗糙集理论的研究主要集中在:粗糙集的算法研究;粗糙集模型推广;问题的不确定性研 究;与其它处理不确定性问题的数学理论的关系与互补;和人工智能其它方向关系的研究等这 些研究有的是应用型的,有的是理论型的| 9 l 【幻】 ( i ) 粗糙集模型的拓展 粗糙集理论在应用于数据分析时,会遇到噪声,数据不齐,海量数据等一系列经典理论解决 不够理想的问题而经典粗糙集理论是建立在等价关系的基础之上由于实际中传递性的条件很 难得到满足,因此一些学者对经典粗糙集模型进行了扩充拓展方法主要有构造性方法和代数方 法 代数方法是基于粗糙集代数系统的算子,利用拓扑学的观点研究近似算子对某些公理的适应 程度,研究的范围大多是经典的集合论,公理与二元等价关系相对应,后来y y y a o 在总结p a w l a k 粗糙集代数系统理论的基础上将其拓展到一般意义下的粗糙集系统,建立了粗糙集代数空间与拓 扑空间的映射关系,完善了近似算子的代数结构,其理论性较强,但实际应用还不多见 构造性方法的研究较为普遍,主要以论域上的二元关系和布尔代数为要素,导出粗糙集代数 系统,其拓展方向主要包括论域方向拓展,关系推广及近似空间的延拓 ( 2 ) 不确定性问题的理论研究 粗糙集理论中知识的不确定性主要由两个原因产生的一个原因是直接来自论域上的二元关 系及其产生的知识模块,即近似空间本身如果二元等价关系产生的划分越粗,每一块知识模块 越大,知识库中的知识越粗糙,相对于近似空间的概念和知识就越不确定这时处理知识的不确 定的方法往往用信息熵来刻画知识的粗糙性与信息熵的关系比较密切,知识的粗糙性实际上是 其所含信息多少的更深层次刻画 粗糙集理论中知识的不确定性的另一个原因来自给定论域里粗糙近似的边界,当边界是空集 时知识是完全确定的,边界越大知识就越粗糙寻求一个合适的度量来刻画知识的不确定性也是 粗糙集理论研究的一个重要方面 ( 3 ) 与其他处理不确定方法的理论研究 与其他处理不确定方法的理论研究主要有:粗糙集与神经网络1 1 l 】;粗糙集与模糊集1 1 2 ;粗糙 集与概率统计 1 4 1 ;粗糙集和粒计算1 6 j 等 ( 4 ) 算法研究 约简是粗糙集用于数据分析的重要内容约简包括两个方面:属性约简和值约简然而对于 宁夏大学硕士学位论文栾云飞;基于粗糙集的贝叶斯分析 3 一个信息系统来说,找出其所有约简和最小约简都已被证明是n p h a r d 问题( 1 5 | 故一般采用启发 式信息找出最优或次优约简 ( 5 ) 属性值的离散化 经典粗糙集只能处理离散型的数据,而连续属性在现实中普遍存在,连续属性的离散化是制 约粗集理论实用化的难点之一这个问题一直是人工智能界关注的焦点连续属性离散化的根本 出发点,是在尽量减少决策表信息损失的前提下( 保持决策表不同类对象的可分辨关系) ,得到简化 和浓缩的决策表,以便用粗集理论分析,获得决策所需要的知识 虽然目前在有关粗糙集理论及其相关的研究中取得了一些令人瞩目的成果,但是仍然存在一 些至今还没有很好解决的问题f 8 j ( 1 ) 在粗糙集理论中,由粗糙集产生的决策规则很不稳定而且有较差的分类精确性因此为得 到精确的决策规则,必须把粗糙集理论和其它数据挖掘方法结合起来常用的方法是把粗糙集和 神经网络及模糊集等软计算方法结合应用 ( 2 ) 约简的有效计算问题,如何处理数据中的噪音和丢失值等问题虽然目前在这些方面已经 有了初步的研究,但是到目前为止还没有找到真正令人满意的方法 ( 3 ) 粗糙集理论所处理的分类必须是完全正确的或肯定的,因而它的分类是精确的,亦即完全 包含或不包含,而没有某种程度上的包含或属于另一方面它所处理的对象是已知的,且从模型 中得到的结论仅适用于这些对象但在实际应用中,往往需要把从小规模对象集中得到的结论应 用于大规模对象集上去因此,这些局限性限制了粗糙集在实际中的应用 ( 4 ) 粗糙集的数学基础是集合论,难以直接处理连续的属性,而连续属性在现实中普遍存因 此,连续属性的离散化变得极为重要,已成为制约粗糙集实际应用的一个很大障碍 1 2 粗糙集的基本内容 1 2 1 粗糙集的研究对象 粗糙集的研究对象是由一个多值属性( 特征,症状,特性等) 集合描述的一个对象( 观察,病历 等) 集合,对于每个对象及其属性都有一个值作为其描述符号对象,属性和描述符是表达决策问 题的三个基本要素这种表达形式也可以看成一个二维表格,表格的行与对象相对应,列对应于对 象的属性;各行包含了表示相应对象信息的描述符通常,关于对象的可得到的信息不一定足以 划分其类别,这样就导致了对象的不可分辨性给定对象间的一个等价关系,即导致由等价关系 构成的近似空间的的不可分辨关系,粗糙集就是用不可分辨对象类形成的上近似和下近似描述 这些近似分别对应了确定属于给定类的最大的对象集合和可能属于给定类的最小的对象集合上 近似和下近似的差是一个边界集合,它包含了所有不能确切判定是否属于给定类的对象这种处 理可以定义近似的精度和质量粗糙集方法可以解决重要的分类问题所有冗余对象和属性的约 简包含属性的最小子集,能够很好的近似分类,得到可以接受质量的分类而且,它还可以用决策 规则集合的形式表示最重要属性和特定分类之间的所有重要关系 4 1 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 4 1 2 2 粗糙集的理论特点 ( 1 ) 粗糙集不需要先验知识模糊集和概率统计方法是处理不确定信息的常用方法,但这些方 法需要一些数据的附加信息或先验信息,如模糊隶属函数和概率分布等,这些信息并不容易得到 粗糙集分析方法仅利用数据本身提供的信息,无需任何先验知识 ( 2 ) 粗糙集是一个强大的数据分析的工具它能表达和处理不完备信息;能在保留关键信息的 前提下对数据进行化简并求得知识的最小表达式;能识别并评估数据之间的依赖关系,揭示出概 念简单的模式;能从经验数据中获取易于证实的规则知识,特别适用于智能控制 ( 3 ) 粗糙集与模糊集不同粗糙集与模糊集分别刻画了不完备信息的两个方面从粗糙集的观 点看,粗糙集合不能清晰定义的原因是缺乏足够的论域知识,但可以用一对清晰集合逼近虽然 粗糙集和模糊集的特点不同,但它们之间有着密切的关系,有很强的互补性;粗糙集和证据理论 也有一些相互交叠之处,在实际应用中可以相互补充 ( 4 ) 粗糙集具有数学意义将知识定义为不可分辨关系的一个族集,使得知识具有了清晰的数 学意义,便于用集合运算处理 1 2 3 粗糙集理论的基本概念 首先我们研究粗糙集的一些基本概念 1 知识与知识库 在粗糙集理论中,知识被认为是一种分类能力根据事物的特征差别,将其分门别类的能力, 均可以看作是某种知识 定义1 1 1 4 】k = ( 阢r ) 称为知识库,其中u 为全体对象的集合称为论域,冗为论域u 上的 等价关系可以根据不同的r 对u 进行不同的分类 设u 是一个论域,兄是u 上的一族等价关系,u r 表示u 上由r 导出的所有等价类 2 不可分辨关系和上下近似集 对于粗糙集可以近似定义,我们使用两个精确集,即粗糙集的上近似和下近似来描述 定义1 2 【4 】设k = ( 阢r ) 为一个知识库,若p r ,且p 0 ,称二元关系i n d ( p ) g ( z ,y ) : 6 ( z ) = 6 ( 耖) ,v b p ) 为p 一不可分辨关系 容易证明i n d ( p ) 是u 上的一个等价关系( 满足自反性,对称性和传递性) 由论域中相互不 可分辨的对象组成的集合称之为基本集合,它是组成论域知识的颗粒 定义1 3 1 4 】设k = ( 阢r ) 为一个知识库,v xsu ,定义两个集合: 0 r 全 z u :【。】冗x ) = u 纠r :f z 】r x , ( 1 2 1 ) r x = a z u :【x rnx 0 ) = u k j r :陋j rnx o ( 1 2 2 ) 它们分别称为x 的r 下近似集和r 上近似,其中阁r 是z 所在的等价类 是由那些根据现有知识r 判断出肯定属于x 的u 中对象所组成的集合,称为x 的r 正 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 5 域,记作p o s r ( x ) ;趸x 是由那些根据现有知识r 判断出可能属于x 的u 中对象所组成的集 合;u 一再x 是由那些根据现有知识r 判断出肯定不属于x 的u 中对象所组成的集合,称为x 的r 负域,记作n e g r ( x ) ;积一路是由那些根据现有知识r 判断出可能属于x 但又不能 完全肯定是否一定属于的x 的u 中对象所组成的集合,称为x 的r 边界域,记作b n d a ( x ) 如果b n d r ( x ) 是空集,则称集合x 关于r 是可定义的;反之,如果b n d n ( x ) 不是空集, 则称集合x 关于r 是粗糙的因此,粗糙集中的“粗糙”主要体现在边界域的存在集合x 的 边界域越大,其确定性程度越小 对于属性r ,样本子集x 的不确定性程度可以用近似精度a r ( x ) 来表示为 。私) = 矧 ( 1 2 3 ) 式中i 木l 表示集合的基数( 集合中的元素个数) 显然,0 a r ( x ) 1 ,如果a a ( x ) = 1 ,则称集合x 相对于r 是确定的,如果a n ( x ) 1 ,则 称集合x 相对于r 是粗糙的 3 知识的依赖性【4 】 知识库中的知识并不是同等重要的,有些知识可以由其它的知识导出,下面我们研究知识之 间的依赖关系 知识的依赖性可定义如下:设k = ( 以r ) 是一个知识库,p ,q r ,则 ( 1 ) 知识q 依赖于知识p ( 记作p 辛q ) 当且仅当i n d ( p ) c _ i n d ( q ) ( 2 ) 知识q 与知识p 等价( 记作p 三q ) 当且仅当p 号q ,且o 号p ( 3 ) 知识q 与知识p 独立( 记作p o ) 当且仅当p 净q 与q 号p ,均不成立 当知识q 依赖于知识p 时,也可以说知识q 是由知识p 导出的 有时候知识的依赖性可能是部分的,这意味着知识q 仅有部分是由知识p 导出的,这可以由 知识的正域来定义: 定义1 4 【4 】设k :( 以j 5 c ) 是一个知识库,只q r 当k :饰( q ) :塑监i u i 时,我们称知 识q 是k 度依赖于知识p 的,记作p 号kq 当k = 1 时,我们称q 完全依赖于p ;当0 k 1 时,称q 粗糙依赖于p ;当k = 0 时,称q 完全独立于p 系数饰( q ) 可以看作q 和p 之间的依赖度 4 知识约简和核 在知识库中可能含有冗余的知识,知识约简是研究知识库中那些知识是必要的,以及在保持 分类能力不变的前提下,删除冗余的知识下面我们研究知识约简的一些基本概念 定义1 5 【4 lk = ( 以r ) 是一个知识库,对于a r ,如果i n d ( r ) = i n d ( r 一 n ) ) ,则称a 在 等价关系r 中是不必要的,否则称a 为r 中必要的 如果每一个a 都为- r 中必要的,则称r 为独立的;否则称r 为依赖的 定理1 1 1 4 】设k = ( 配r ) 是一个知识库,当p q r 时,i n d ( q ) f i n d ( p ) 说明当属 性越多时,等价关系越少,划分越细 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 6 定义1 6 f 4 】设k = ( 玩r ) 是个知识库,q 和p 是矽上的两个等价关系族,且q p ,若 q 是独立的,且i n d ( p ) = i n d ( q ) ,则称q 是p 的一个约简,记作r e d ( p ) 显然,p 可以有多种 约简 p 中所有必要关系组成的集合称为_ p 的核,记作c o r e ( p ) 定理1 2 【4 】等价关系族p 的核等于p 的所有约简的交集,即c o r e ( p ) = n r e d ( p ) 在应用中一个分类相对于另一个分类的关系十分重要,因此引入相对约简和相对核的概念 定义1 7 【4 1 设p 和q 是论域u 上的等价关系,q 的p 正域p o s p ( q ) 定义为: p o s p ( q ) = 【j 麟 x e u q 定义1 8 1 4 设p 和q 是论域u 上的等价关系,r p ,若有 p o s p ( q ) = p o s e 一,( q ) , 则称r 为p 中q 不必要的,否则称r 为p 中q 必要的若p 中的任一关系r 都是q 必要的, 则称p 为q 独立的 定义1 9 4 1设s p 称s 为p 的q 约简,当且仅当s 是p 的q 独立子族,且 p o s s ( q ) = p o s p ( q ) p 中所有q 必要的关系构成的集合称为p 的q 核,记作c o r e q ( p ) p 的q 核是知识p 的本质部分p 的q 约简是p 的子族,且是独立的它具有与知识p 相同的分类能力 定理1 3 f 4 jp 的q 核等于p 的所有q 约简的交集,即c o r e q ( p ) = n r e d q ( p ) 核这个概念有两方面的作用,一方面由于核包含在所有的约简中,所以它可以作为所有约简 的计算基础;另一方面,核可以解释为当知识约简时它是不能消去的特征集合 一般约简是在不改变对论域中对象的分类能力的前提下消去冗余知识,而相对约简是在不改 变将对象划分到另一个分类中去的分类能力不变的前提下消去冗余知识 5 知识表达系统和决策表 知识表达系统在智能数据处理中占有十分重要的地位 一个知识表达系统【4 】指四元组s = ( 阢a ,k ,) ,其中u = x l ,z 2 ,x n ) 为论域,它是全体 对象的集合;a = c u d 为属性集合,其中子集c 是条件属性集,反映对象的特征,d 为决策属性 集,反映对象的类别;v = u ,rw 为属性值的集合,w 表示属性r 的取值范围;,:u r _ y 为一个信息函数,用于确定u 中每一个对象z 的属性值,即任一瓢u ,r r ,则,( 翰,r ) k 知识表达系统也称为信息系统,通常用s = ( 以a ) 代替s = ( 玑a ,k ,) 信息系统的数据以关系表的形式表示关系表的行对应要研究的对象,列对应对象的属性, 对象的信息是通过指定对象的各属性值来表达的 一个属性对应一个等价关系,一个关系表可以看作是定义的一族等价关系,即知识库。那么 前面讨论的问题( 知识的依赖性,知识约简等) 都可以用属性及属性值引入的分类来表示,知识约 简可转化为属性约简 定义1 1 0 4 】设s = ( 玑a ) 是一个信息系统,a = c u d ,c n d = o ,那么这个信息系统叫 作决策表 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 7 决策表的属性约简,即相对约简,就是要从条件属性集合中发现部分必要的条件属性,使得 根据这部分条件属性形成的相对于决策属性的分类和所有条件属性相对于决策属性所形成的分类 一致,即和所有条件属性相对于决策属性有相同的分类能力 1 3本文主要工作及安排 本文第一章介绍了粗糙集的研究历史及现状,粗糙集的理论概况并给出了粗糙集的基本概念 第二章介绍了几种常见的粗糙集模型,包括p a w l a k 粗糙集模型,变精度粗糙集模型,以及贝 叶斯粗糙集模型基于多数包含关系,给出一种新的贝叶斯粗糙集模型举例说明了该模型的有效 性 第三章研究了含有多个决策类的贝叶斯粗糙集的概念,讨论了相关的性质以全局增益作为 启发式信息,给出了基于该模型的属性约简的一个启发式算法,举例说明该算法是可行的 第四章研究了决策规则,决策算法的概念,说明每个决策表都满足一定的概率性质,特别是 满足全概率公式和贝叶斯定理 第五章是全文工作的总结及展望 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 8 第二章几种常见的粗糙集模型 经典粗糙集模型是p a w l a k 于1 9 8 2 年提出的,它的一个局限性是它处理的分类必须是完全正 确的或肯定的,而没有某种程度上的”包含”或”属于”这限制了它在实际中的应用为信息更 多的得到利用,z i a r k o 提出了变精度粗糙集模型【2 7 l ,变精度粗糙集模型比经典粗糙集模型灵活的 同时,也产生了一定的限制:一旦参数卢确定,上下近似同时受到一个参数的制约为此,s l e z k 和z i a r k 又提出了一种贝叶斯粗糙集模型【3 2 】,该模型以概率表示为基础,简单实用基于多数包 含关系,本章给出一种新的贝叶斯粗糙集模型 2 1p a w l a k 粗糙集模型 设k = ( 仉r ) 是一个知识库,论域u 为非空有限集合, r 是u 上的等价关系, u r = e l ,e 2 ,晶】为r 的等价类对任意的集合x u ,有 r _ x = u e u n :e x ) , 一r x = u e v n :enx 味 ( 2 1 1 ) r x 和瓦x 分别称为x 的r 下近似集和r 上近似p o s r ( x ) 全,称为x 的r 正域; n e g n ( x ) 全u 一取,称为x 的r 负域;b n d r ( x ) 全取一r x ,称为x 的r 边界域 显然,r x 和一r x 还可以写为下列形式: r r _ x = u ( f u r :p ( x i e ) = 1 ) , 夏x = u ( e c r n :0 p ( x f e ) s l ,( 2 1 2 ) 其中,p ( x i e ) = i ( xne ) i i e i ;i 丰i 表示集合的基数 定义2 1 【2 3 】设k = ( 阢r ) 是一个知识库,叫兄= e 1 ,e 2 ,e n 为r 的等价类,对于 x u ,x 的p a w l a k 正域,负域,边界域还可以写为下面的形式: p o s r ( x ) = u e u n :p ( x i e ) = 1 ) , n e g n ( x ) = u ( e u r :p ( x l e ) = o ) , ( 2 1 3 ) b n d r ( x ) = u e v n :0 p ( x i e ) 1 事件x 和其补事件一x 之间存在如下关系: p o s n ( x ) = n e g r ( ,z ) ,p o s n ( - 、x ) = n e g n ( x ) ,b n d n ( x ) = b n d r ( , x ) 2 2 变精度粗糙集模型 p a w l a k 粗糙集模型由等价类严格限制了边界的范围,为信息更多的得到利用,z i a r k o 提出了 带有一个参数的变精度粗糙集模型( 简称v p r s 模型) 宁夏大学硕士学位论文 栾云飞:基于粗糙集的贝叶斯分析 9 设x 和y 表示有限论域u 的非空子集,记 c c x ,y ,= :,一i x n y i i x | 篙1 三: 称c ( x ,y ) 为集合x 关于集合y 的相对错误分类率 定义2 2 【4 1 设0 口 0 5 ,多数包含关系定义为: y 。x 甘c ( x ,y ) o “多数”要求隐含着x 与y 中的公共元素的数目大于x 中元素数目的5 0 定义2 3 ( 4 1 设k = ( 阢r ) 是一个知识库,q 【0 ,0 5 ) ,对于x u ,x 的q 下近似定义为: x = u e 叫r :c ( e ,x ) a ) x 的o t 上近似定义为: 瓦x = u e u r :c ( e x ) 1 一n , 定义2 4 1 2 9 1 设k = ( 阢r ) 是一个知识库,q 【0 ,0 5 ) ,对于x v ,x 的基于n 错误分类 率的变精度正域,负域,边界域分别为: p o s 。( x ) = u e u r :c ( e ,x ) q 】, n e g 。( x ) = u e u n :c ( e ,x ) 之1 一q , ( 2 2 1 ) b n d 。( x ) = u e u n :o t c ( e ,x ) 1 一q x 的o t 正区域( 或x 的o t 下近似) 可以理解为将u 中的对象以不大于o t 的分类误差分于x 的集合x 的o t 负区域可以理解为将u 中的对象以不大于q 的分类误差分于x 的补集( 即,x ) 的集合,后者的解释可由定理2 1 给出 定理2 1 1 4 】对于v x u ,有 p o s 。( ,x ) = n e g 。( x ) x 的q 边界域是由那些以不大于o t 的分类误差既不能分类于x 又不能分类于一x 的u 中对 象所构成的集合 如果b n d 。( x ) = 谚,则 p o s 。( x ) un e a 。( x ) = 阢 x 的q 上近似可以理解为将u 中的对象以不大干q 的分类误差分于,x 的u 中的对象所构 成的集合 将上面近似集的定义与p a w l a k 粗糙集模型相比较,我们发现,如果a = 0 ,那么p a w l a k 粗 糙集模型就变成了变精度粗糙集模型的特殊情况这个事实可由下列定理来解释 定理2 2 【4 】设k = ( 阢r ) 是一个知识库,对于x 扩,有 ( 1 ) 岛x = r _ x ,其中_ r x 是由型= u e v r :v ( x l e ) = 1 ,定义的下近似集 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 l o ( 2 ) 瓦x = 融,其中积是由积= u 【e 【厂r :0 p ( x i e ) s1 ) 定义的上近似集 ( 3 ) n e g o x = n e g ( x ) ,其中n e g ( x ) 是由n e g ( x ) = 矿一瓦x 定义的负区域 ( 4 ) b n d o x = b n d ( x ) ,其中b n d ( x ) 是由b n d ( x ) = 积一r x 定义的边界域 对于0 o t 1 一卧 定义2 5 | 2 6 l 设k = ( 配r ) 是一个知识库,卢( 0 5 ,1 】,对于x u ,x 的变精度( v p r s 口) 正域,负域,边界域分别为: p o s e ( x ) = u e u r :p ( x i e ) p ) , n e g 卢( x ) = u e u r :p ( x i e ) 1 一p ) , ( 2 2 2 ) b n d p ( x ) = u e g r :1 一p p ( x i e ) p ) 定理2 5 设k = ( r ) 是一个知识库,卢( 0 5 ,1 】,对于x 冬矽,有 p o s p ( x ) = n e g 口( 、x ) 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 1 1 证明: p o s ( x ) = 岛僻) = u e u l r :p ( x i e ) 肼 = u e u i r :酉p ( x n e ) p = u eu r :帮1 一p ) = u e u i r :p ( - x i e ) 1 一p ) = n e g 卢( - - , x ) 将上面近似集的定义与p a w l a k 粗糙集模型相比较,我们发现,如果卢= 1 ,那么变精度粗糙 集模型就变成了p a w l a k 粗糙集模型这个事实可由下列定理来解释 定理2 6 设k = ( 阢r ) 是一个知识库,对于x u ,有 ( 1 ) 旦1 x = r _ x ,其中宣x 是由= u e 叫r :p ( x i e ) = 1 ) 定义的下近似集; ( 2 ) 1 x = 了,其中面x 是由取= u e u r :0 , b n d p ( x ) 叶b n d o 5 僻) = u e v r :p ( x i e ) = o 5 ) , n e g 卢( x ) 叶n e g o 5 伍) = u e 叫r :p ( x i e ) p ( x ) , n e g ( x ) = u e 叫月:p ( x i e ) p ( x ) 的所有等价类都成了正域的集合,这就意味着正 域中有些等价类含有很少的x 中的元素这不符合定义正域的思想 ( 2 ) 当p ( x ) 很大时,使用负域的定义会损失大量的信息这也不符合改进传统粗糙集模型以 获得更多信息的思想 ( 3 ) 对于边界域的定义,s l e z k 和z i a r k 认为边界区域完全与x 无关,并且从概率事件的角度 认为x 与其它等价类事件e 是相互独立的事实上这样的认为是不合理的,因为边界区域中存在 着与x 有关的信息,而信息量的比例与等价类有关在该模型中,边界的定义在的另一个问题是 满足p ( x i e ) = p ( x ) 条件的等价类在实际计算中很少,因此在很多情况下,边界区域是空集这 不符合改进传统粗糙集模型更柔性化的思想 基于以上考虑,我们结合多数包含关系,给出了一种新的贝叶斯粗糙集模型( b r s ,) 定义2 7设k = ( 以r ) 是一个知识库,设等价关系r 在论域矿上的等价类为叫r = e l ,e z ,e k x u ,令p 7 僻) = m i n p ( x ) ,1 一p ( x ) ) ,集合x 的正域,负域,边界域分别 宁夏大学硕士学位论文栾云飞:基于粗糙集的贝叶斯分析 1 3 为: p o s 7 ( x ) = u e t r :c ( e ,x ) sp ,) ) , n e g ( x ) = u e u r :c ( e ,x ) 1 一p 7 ( x ) , ( 2 3 2 ) b n d 7 ( x ) = u e u a :p ,( x ) c ( e ,x ) , b n d ( x ) = u e u r :4 9 p ( x d ,i = 1 ,2 ,r ) , n e g ( x d = u 【z 】b :p ( 冠j 【司b ) 0 甘b p o s + ( 五) ,i = 1 ,2 , 9 ( 五b ) 0 ,i = 1 ,2 ,r ) , n e g + ( 蕊) = u h b :g ( 五悯b ) 0 5 ,则当变 精度粗糙集模型中的参数卢= p ( x k ) 时,有p o s 售( x k ) = p o s 备( x k ) u b n d 刍( x k ) 证明:在变精度粗糙集模型中p o s 鲁( x k ) = u 4 8 :p ( x k i x l b ) p ) ;在贝叶斯粗糙集模型 中有: p o s 刍( x k ) u b n d ;( x k ) = ( um b :p ( x 七i 【z 】b ) p ( x k ) ) u ( u b :p ( x k l x

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论