（计算机应用技术专业论文）基于不完备信息系统的vprsm的规则获取方法研究.pdf

摘要 目前知识发现不能有效地处理不完备、不确定性数据以及知识的可解释性比较差， 而变精度粗糙集( v a r i a b l ep r e c i s i o nr o u g hs e t ，v p r s ) 理论是一种处理模糊的、不确 定性知识的数学工具，不需要先验知识，并且决策树具有表示直接的优点。因此，采 用v p r s 理论先进行属性约简，再利用v p r s 理论构建决策树来获取规则对于知识发 现具有十分重要的意义。 针对在不完备信息系统内属性约简准确性比较低的情况，定义了新的属性重要性 算子作为启发式信息和新的约简定义作为约简终止条件，并将相对核计算方法扩展到 不完备信息系统中，从而给出了在不完备信息系统中基于v p r s m 的属性约简算法。 该算法在保证得到一个属性约简集的同时，可以提高属性约简的准确性及灵活性；由 于决策树的构建过程中未考虑到结点选择中属性的重要性，因此针对如何将属性核与 分类质量相结合应用到决策树的构建中，以及当两个( 或两个以上) 属性的分类质量量 度相等时，如何选择最合适的属性作为结点，本课题提出基于属性核的v p r s m 的决 策树构造算法。该算法能够产生树结点少、分类准确率较高的决策树，从而最终获得 规则。 通过理论分析和在u c i 数据集上的实验验证，证明提出的基于不完备信息系统的 v p r s m 的属性约简算法和基于属性核的v p r s m 的决策树构造算法都达到了预期效 果，最终获得了有效的规则，对今后进一步的研究和实际应用具有重要的意义。 关键词：不完备信息系统，v p r s m ，属性约简，决策树，规则获取 r e s e a r c ho fr u l e se x t r a c t i o nm e t h o db a s e do nv p r s mi ni n c o m p l e t e i n f o r m a t i o ns y s t e m s w a n gl i n ( c o m p u t e ra p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f e s s o rd u a ny o u x i a n g a n da s s o c i a t ep r o f e s s o rg o n ga n a b s t r a c t n o wk n o w l e d g ed i s c o v e r yf a c e s d e a l i n gw i mi n c o m p l e t e a n du n c e r t a i nd a t a i n e f f i c i e n t l ya n dt h ep o o re x p l a n a t i o no fk n o w l e d g e v a r i a b l ep r e c i s i o nr o u g hs e t ( v p r s ) t h e o r yi sak i n do fm a t h e m a t i ct o o lf o rt h ea n a l y s i so fv a g u e a n du n c e r t a i nk n o w l e d g ew h i c h i sn or e q u i r e m e n t so fp r e v i o u sk n o w l e d g e ，a n dd e c i s i o nt r e ec a nd i r e c t l ya n a l y s i sd a t a 。 t h e r e f o r e ，u s i n gv p r st h e o r yf o ra t t r i b u t er e d u c t i o na n dc o n s t r u c t i o no fd e c i s i o nt r e et o o b t a i nr u l e sf o rk n o w l e d g ed i s c o v e r yh a st h ee x t r e m e l yv i t a ls i g n i f i c a n c e a c c o r d i n gt ot h el o wa c c u r a c yo fa t t r i b u t e sr e d u c t i o ni nt h ei n c o m p l e t ei n f o r m a t i o n s y s t e m ，t h i sp a p e r d e f i n e san e wa t t r i b u t ei m p o r t a n c eo p e r a t o ra sh e u r i s t i ci n f o r m a t i o na n da n e wr e d u c t i o nd e f i n i t i o na sr e d u c t i o nt e r m i n a lc o n d i t i o n s ，a n de x p a n dr e l a t i v e l yn u c l e a r c a l c u l a t i o nm e t h o dt oi n c o m p l e t ei n f o r m a t i o ns y s t e m f i n a l l y , t h i sp a p e rp r o p o s e sa n a t t r i b u t er e d u c t i o na l g o r i t h mb a s e do nv p r s mi ni n c o m p l e t ei n f o r m a t i o ns y s t e m s t h i s a l g o r i t h mg u a r a n t e e dt og e ta na t t r i b u t er e d u c t i o ns e t ，a n dc a ni m p r o v e t h ea c c u r a c ya n dt h e f l e x i b i l i t yo ft h ea t t r i b u t er e d u c t i o n b e c a u s ei nt h ep r o c e s so fb u i l d i n gad e c i s i o nt r e eh a s n o tc o n s i d e r e dt h ep r o b l e m so fa t t r i b u t ei m p o r t a n c ei nt h en o d e sc h o i c e t h e r e f o r eh o wt o c o m b i n ea t t r i b u t en u c l e a ra n dc l a s s i f i c a t i o nq u a l i t yt od e c i s i o nt r e ec o n s t r u c t i o n ，a n dw h e n t w o ( o rm o r e ) a t t r i b u t e sc l a s s i f i c a t i o nq u a l i t yi se q u a l ，h o wt o s e l e c tt h em o s ta p p r o p r i a t e a t t r i b u t e sa sn o d e ，t h i sp a p e rp r o p o s e st h ec o n s t r u c t i o no fd e c i s i o nt r e ea l g o r i t h mb a s e do n v p r s mo fa t t r i b u t ec o r e t h i sa l g o r i t h mc a ng e n e r a t ed e c i s i o nt r e ew i t hl e s st r e en o t e s ， h i g h e rc l a s s i f i c a t i o na c c u r a c y , t h u sf i n a l l yo b t a i n r u l e s t h e o r e t i c a la n a l y s i sa n de x p e r i m e n t a lr e s u l t so nu c id a t as e tp r o v et h a ta t t r i b u t e r e d u c t i o na l g o r i t h mb a s e do nv p r s mi ni n c o m p l e t ei n f o r m a t i o ns y s t e m sa n dc o n s t r u c t i o n o fd e c i s i o nt r e ea l g o r i t h mb a s e do nv p r s mo fa t t r i b u t ec o r ec a na c h i e v et h ee x p e c t e d r e s u l t s ，a n dg e te f f e c t i v ek n o w l e d g er u l e s 。t h ea l g o r i t h m sh a v ei m p o r t a n ts i g n i f i c a n c ef o r f u t u r es t u d i e sa n dp r a c t i c a la p p l i c a t i o n s k e yw o r d s ：i n c o m p l e t ei n f o r m a t i o ns y s t e m ，v p r s m ，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 r e e ， r u l ee x t r a c t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致i j l t j , b ， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志对 研究所做的任何贡献均己在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：垒 ， 日期：卅年s 贺嘭日 j ， 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版和 电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学 位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印， 将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手 段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签 指导教师签名： f 1 期：卅年岁月哆呙 嗍呵年r 月谚向 中国石油大学( 华东) 硕i ：学位论文 第一章绪论 1 1 引言 当今计算机和网络通讯技术的飞速发展使得各个领域的信息正在急剧增长，而丰 富的数据与贫乏的知识之间的矛盾日益突出。这就迫切要求人们采取有效措施对数据 进行提取，从而获取有用的信息，知识发现和数据挖掘也就应运而生了。 在现实生活中，经常存在一些不完整和不充分的信息，并且数据挖掘涉及分类、 概念形成和数据分析，他们需要对这些信息进行处理，因此围绕这个问题产生了许多 理论，如模糊理论、神经网络、粒计算、形式概念分析、粗糙集理论等。其中经典粗 糙集理论是波兰数学家z p a w l a k 教授提出来的一种新型的处理模糊和不确定性知识的 数学工具。它具有很强的分析能力，可以直接从给定问题的信息系统出发，通过不可 分辨关系和不可分辨关系类确定给定问题的近似域，从而得到问题的内在规律，并且 它已在决策分析、模式识别、专家系统及数据挖掘等领域取得了很大的成功1 4 】。 而现实中，由于数据采集能力有限、测量误差等原因，往往得到对象属性值是未 知的不完备信息系统。而经典粗糙集的一个局限性是它建立在完备信息系统之上的， 即它所处理的分类必须是完全正确的或肯定的，而没有某种程度上的“包含”或“属 于”；另一个局限性是它所处理的对象是已知的且从模型中得到的所有结论仅仅适用于 这些对象集【3 1 。z i a r k o 提出的可变精度粗糙集模型( v a r i a b l ep r e c i s i o nr o u g hs e tm o d e l ， v p r s m t 5 1 ，简称v p r s m 或v p 模型) 弥补了经典粗糙集模型的局限性，增强了模型 的容噪能力，是对经典粗糙集合理论进行的扩展。本文将围绕v p r s m 的相关理论进 行规则获取的研究。 1 2 课题的提出及意义 属性约简的目的是导出相关决策表的决策规则，而约简后的属性能否表达与原属 性集完全一致的信息直接影响着决策规则的有效性和正确性。基于不完备信息系统的 v p r s m 的属性约简作为粗糙集理论的一个重要研究方向，近年来取得了很多的成果， 但仍然存在约简准确度不高的问题。寻找有效的高准确度的约简算法，并使约简后结 果适应更多的对象集对于最终的规则获取具有重要的意义。因此针对目前在不完备信 息系统中属性约简算法的准确度比较低的情况，本课题提出了基于不完备信息系统的 v p r s m 的属性约简算法。该算法可以保证得到一个属性约简集的情况下，提高算法 的准确度及灵活度。 第一章绪论 属性约简的最终目的是获取有效的、正确的规则。目前，规则获取大多采用神经 网络、统计模型、贝叶斯分类器、决策树等。由于决策树模型具有易构造、结构简单、 易于理解、分类精度高、鲁棒性强等特点，因此选择基于决策树模型的规则挖掘。 基于v p r s m 的决策树的构造常见的是以分类质量量度作为信息函数，对条件属 性进行选择。然而他们并未考虑到在结点选择中属性的重要性问题，即如何将属性核 与分类质量相结合应用到决策树的构造当中，此外当两个( 甚至两个以上) 属性的分类 质量量度相等时，如何选择最合适的属性作为结点。而构造一棵好决策树的关键是选 择合适的属性作为结点，从而提高决策树的分类精确度，最终获得分类精度较高的规 则。所以本课题提出将决策树的构造与v p r s m 相结合的基于属性核的v p r s m 的决 策树构造算法。该算法可以解决以上不足并且能够产生结点少、准确率较高的决策树， 从而最终获得规则。 综上，本课题首先通过基于不完备信息系统的v p r s m 的属性约简算法对决策表 进行属性约简，然后通过基于属性核的v p r s m 的决策树构造算法在约简后的决策表 上构造决策树，最终得到有效的、分类精度较高的规则，为规则获取方法的研究提供 一定的帮助。 1 3 国内外研究现状 1 3 1 粗糙集理论研究现状 粗糙集理论是一种新的处理模糊和不确定性问题的新型数学工具，虽然历史比较 短，但是发展比较迅速。1 9 8 2 年，z p a w l a k 发表了经典论文r o u g hs e t s ，宣告了粗糙 集理论的诞生。1 9 9 0 年前后，粗糙集理论在机器学习与知识发现、数据挖掘、决策支 持与分析等方面被广泛应用，逐渐引起了世界各国学者的广泛关注。 国内各高校和研究机构从上世纪9 0 年代后期开始了对粗糙集理论的研究。1 9 9 6 年，出版了第一部旨在介绍粗糙集理论的专著。到上个世纪末基本上国内的主要计算 机刊物都发表有关于粗糙集的学术论文，粗糙集理论已逐渐引起国内学术界的关注。 2 0 0 1 年5 月在重庆召开了中国第一届粗糙集与软计算学术研讨会。2 0 0 6 年7 月首届粗 糙集与知识技术国际会议在重庆举行，粗糙集己逐渐吸引了国内计算机科学界和数学 界的关注。现在我国也成立了中国人工智能学会粗糙集与软计算专业委员会。 国际上研究拳h 糙集的一些高校和研究机构在基于粗糙集理论的数据分析软件的开 发上取得了很大的进步【6 】。波兰华沙大学和挪威科技大学联合开发的r o s e t t a 是基于粗 糙集理论框架的知识发现和数据挖掘软件系统，它包含了从数据的预处理、约简计算、 2 中国石油大学( 华东) 硕上学位论文 规则生成到规则的验证和分析的知识发现全过程。美国肯萨斯大学开发了一套基于粗 糙集的实例学习系统l e r s ，它能从大量经验数据中抽取规则。除上述经典系统外， 粗糙集研究人员还开发了很多其他粗糙集系统，如英国u l s t e r 信息与软件工程研究所 开发的g r o b i a n ，波兰工业大学的r o s e ，挪威t r o l ld a t ai n c 的r o u g he n o u g h 和加拿 大r e g i n a 大学的k d d - r 7 1 等。 1 3 2 基于不完备信息系统的r o u g h 集模型及v p r s m 研究现状 经典粗糙集理论研究的对象是完备信息系统，即所有对象在任意属性下属性值是 确定的。但在实际应用中，由于各种条件和因素的影响，某些属性值暂时无法得到( 遗 漏，但可以与任意已知的属性值进行比较) ，或者肯定无法得到( 缺省，不能与任意已 知的属性值进行比较) 。因此，对于不完备信息系统经典粗糙集理论中采用的等价关系 ( 不可分辨关系) 必须泛化，建立适合处理更多实际问题的一般二元关系。 为此，许多学者针对不同的情形，提出了各种不同的二元关系。m k r y s z k i e w i c z 把未知的属性值理解为暂时遗漏，但可以与己知的属性值比较而提出了容差关系峭j ； j s t e f a m o w s k i 和a t s o u k e a s 认为对象被不完全描述的原因不仅可能是由于知识不精 确，还可能是由于根本不能用已有的属性来描述，不允许比较未知值，从而提出了非 对称相似关系f 9 】。m k r y s z k i e w i c z 的相容关系过于宽松，很容易使本不是同一类的对 象归为同一类，而j s t e f a m o w s k i 的非对称相似关系过于严格，会误使同一类的对象属 于不同类。王国胤针对这种情况，提出了限制容差关系【l0 1 ，这种关系改变了相容关系 的过于宽松性和非对称相似关系的过于严格性。 基于上面所说的二元关系就有必要对传统经典粗糙集理论进行扩充来适应不完备 系统。目前已有的r o u g h 集模型主要有：m k r y s z k i e w i c z 提出的基于容差关系的 r o u g h 集模型、j s t e f a m o w s k i 提出的基于非对称相似关系和量化容差关系下的r o u g h 集模型、王国胤提出的基于限制容差关系下的r o u g h 集模型。以上的模型也都存在 一定的缺点，所以现在基于以上的模型又提出了一些别的模型，如限制容差关系的集 对粗糙集模型【1 、修正容差关系的粗糙集模型【1 2 l 、限制非对称相似关系的粗糙集模型 1 1 3 1 熊 寸。 为增强粗糙集模型的抗干扰能力，加拿大科学家z i a r k o 对经典粗糙集理论进行扩 展，z i a r k o 于1 9 9 3 年提出了可变精度粗糙集模型。v p r s m 是在经典粗糙集理论的基 础上引入了分类正确率目，即允许一定程度的错误分类率存在，从而具有一定的容错 性，增强了对噪声数据的适应能力。因此，v p r s m 在对不确定信息的处理上具有较 3 第一章绪论 大的研究空间。所以近几年，相应的提出了基于变精度容差关系的扩展粗糙集【1 4 1 及一 些基于相容关系，限制容差关系和集对分析等的v p r s m 。 1 3 3 基于粗糙集的决策树研究现状 基于粗糙集的决策树挖掘算法层出不穷，它们把粗糙集和决策树两种方法进行优 势互补，产生的新方法既保留了原始数据的内部特点又能加快知识获取的进程，能很 好的提高模型的分类准确率。 1 9 9 4 年，r a g r a w a l 提出了应用粗糙集理论来构造决策树的方法，应用该方法所 构造的决策树明显优于传统的基于信息熵的i d 3 算法。1 9 9 7 年，苗夺谦提出了基于粗 糙集的多变量决策树构造方法【1 5 】。该方法可以同时检验多个属性，并且能够产生新的、 更相关的属性，以及修改或去掉初始提供的不相关的属性。2 0 0 4 年，王益玲考虑了训 练数据中噪声数据的存在，将变精度粗糙集引入到决策树的构造中，允许在构造决策 树的过程中划入正域的实例类别存在一定的不一致性，提高了决策树的泛化能力。同 年，蒋云【1 6 】提出了基于粗糙集理论的加权平均粗糙度的概念。在同一信息表所对应的 决策树里，基于加权平均粗糙度的方法比基于信息熵的方法所占用的空间少，且同时 避免了在决策树的一条路径上多次检验某一属性的问题。2 0 0 7 年，孙洁在应用变精度 粗糙集模型构造决策树的研究基础上，提出了具有置信度规则的决策树的构造方法i ”】。 该方法是对决策树生成方法的一个改进，所构造的决策树具有更强的实用性以及更高 的可理解性。2 0 0 8 年黄宇颖1 8 1 提出以变精度加权平均粗糙度作为构造决策树的属性选 择标准，并通过在体检系统的实例应用，可以看到提出的决策树构造算法可以有效地 弱化少数实例对决策树造成的不良影响，虽然决策中存在一定的误差，但决策树总体 分类是比较好的，最终生成的决策树也比较简洁，泛化能力也大大提高。 1 4 研究目标和主要研究内容 1 4 1 研究目标 针对目| j 数据的特点和数据库技术发展的需求，本文对基于不完备信息系统的 v p r s m 的规则获取方法进行研究。结合v p r s m 本身的特性，提出一种有效的基于不 完备信息系统的v p r s m 的属性约简算法和基于属性核的v p r s m 的决策树构造算法， 最后得到符合人们需求的、有效的、正确的规则。 1 4 2 研究内容 本课题的主要研究内容包括以下几个方面： 4 中国石油人学( 华东) 硕l 学位论文 ( 1 ) 研究不完备信息系统、v p r s m 及决策树的研究现状，提出基于不完备信息系 统的v p r s m 的规则获取方法研究，并对主要过程提出相应的解决方法。 ( 2 ) 深入分析各种基于不完备信息系统的属性约简算法，并对其进行比较，得出 各种算法的优缺点。 ( 3 ) 在理论分析的基础上，重新定义属性重要性算子，并作为启发式信息来提高 属性约简算法的准确度。 ( 4 ) 针对目前属性约简算法的准确度比较低的情况，将新定义的属性重要性算子 应用到属性约简中，同时结合新定义的约简定义，提出基于不完备信息系统的v p r s m 的属性约简算法。该算法在保证得到一个属性约简集的情况下，提高算法的准确度及 灵活度，同时在u c i 数据集上进行实验验证，达到预期效果。 ( 5 ) 比较各种构造决策树算法的优缺点，提出基于属性核的v p r s m 的决策树构造 算法。通过实验验证和结果比较，证明所提算法能够产生结点少、规则简单、准确率 较高的决策树，从而能满足人们对规则获取的要求。 1 5 论文的组织结构 本文围绕基于变精度粗糙集理论的相关算法展开论述，在算法研究的基础上进行 实例验证，组织结构如下： 第一章绪论。 主要介绍本课题的提出、目的及意义，对当前粗糙集理论、基于不完备信息系统 的粗糙集模型和v p r s m 以及决策树的国内外研究现状进行研究，并提出基于变精度 粗糙集理论研究的规则获取方法的内容与思路，阐明了本文的研究意义和学术价值。 第二章粗糙集理论概述。 重点研究经典粗糙集理论以及变精度粗糙集理论的有关概念、特点及应用等相关 理论知识。 第三章基于不完备信息系统的属性约简。 本章主要对在不完备信息系统中经典r o u g h 集不可分辨关系的扩充以及基于这种 关系的属性重要性的属性约简算法进行了总结、分析和比较。 第四章基于不完备信息系统的v p r s m 的属性约简。 在不完备信息系统内针对约简准确性比较低的情况，定义了新的属性重要性算子 作为启发式信息和新的约简定义作为约简终止条件，并将相对核计算方法扩展到不完 备信息系统中，从而给出了基于不完备信息系统的v p r s m 的属性约简算法。该算法 5 第一章绪论 在保证得到一个属性约简集的同时，可以提高算法约简的准确性及灵活性。并对其在 u c i 数据集上进行实验验证，证明所提算法有效。 第五章基于v p r s m 的决策树规则提取研究。 分类和约简是粗糙集理论的重要研究内容之一，目的在于获得较好的规则集。在 对决策表进行了属性约简后，本章在约简后的决策表上构造决策树，从而通过决策树 获取规则。本章将对决策树算法进行研究，提出基于属性核的v p r s m 的决策树构造 算法，降低决策树的复杂度，提高决策树的分类精确度。同时，本章也将给出算法的 实例分析及实验验证。 总结 最后总结本文的工作和创新点，并针对本课题中未完成的问题做下一步的规划。 6 中国石油大学( 华东) 硕上学位论文 第二章粗糙集理论概述 粗糙集理论是研究不精确、不完备信息处理的有力工具。目前粗糙集已经被成功 地运用于机器学习、决策分析、过程控制、模式识别与数据挖掘等领域。本章将介绍 经典粗糙集理论以及变精度粗糙集理论的有关概念、特点及应用，作为后续章节的研 究基础。 2 1 经典粗糙集理论 2 1 1 经典粗糙集理论概述 经典粗糙集理论是一种新的处理模糊和不确定性知识的数学工具。其主要思想就 是在保持分类能力不变的前提下，通过知识约简导出问题的决策或分类规则。粗糙集 并没有确切、统一的定义，目前基本上采用z p a w l a k 教授于1 9 9 5 年最早提出的相关 定义【6 ，1 9 , 2 0 】。下面将阐述经典粗糙集思想及基本概念。 1 信息系统 定义2 1 ：信息( 知识表达) 系统s = ( u ，a ，v ，厂) ，其中u 为对象的非空有限论域；a 为属性非空有限集合；v y 圪是对象属性的值域，圪表示属性口a 的属性值范围； 厂是信息函数，指定每个对象属性的属性值，且厂：u x 么一y ，f ( x ，a ) 圪。 定义2 2 ：s = ( u ，a ，v ，厂) 是一个信息系统。如果其中a 可以分两个不交的子集的 并集，即a = cud ，其中c ，d o ，cr 、d = ，则称s = ( u ，a ，v ，f ) 为一个 决策表或决策系统，记为s = ( u ，c u d ，v ，f ) ，并将c 称为条件属性集，d 称为决策 属性集。 决策表是一类特殊而重要的信息表达系统，它反映了当满足某些条件时，决策( 行) 应当怎样进行。决策表可以有效直观地表示大多数的决策问题，因此这一工具在决策 应用中起着重要的作用。 2 粗糙集的定义 设x 为u 的一个子集，当x 为某些r 的等价类的并时，称x 是r 可定义的，否则 x 为r 不可定义的。足可定义集是论域的子集，它可在k 中被精确地定义，而尺不可 定义集不能在k 中被定义。r 可定义集也称为r 精确集，只不可定义集也称为非精确 集或r 粗糙集。 3 不可分辨关系 不可分辨关系是粗糙集的起点，它意味着由于缺乏信息，不可能通过已有信息辨 7 第= 章粗糙集g 论概述 识对象。换句话说，不能将单一的元素作为处理对象，而是将不可分辨对象族作为一 个整体即知识的一部分进行处理。比如物体集合中的元素具有“颜色”、“形状”、“大 小”三种属性，则两个同等大小红色的圆球就不可以分辨，即在现有的知识下不能将 它们细分，形成了二者间的不可分辨关系。 定义2 3 设s = ( u ，矿，) 是一个决策系统，那么任意子集8 4 所对应的不可 分辨关系i n d ( 研可定义为：i n d ( b ) = o ，y ) u x u ：v a e 毋，( 墨n ) = f ( y ，曲 。 4 上近似和下近似 对于一个样例集，也称为一个概念。根据一个条件属性子集所确定的不可分辨关 系，有可能准确地判定一些样例是否属于该概念，也有可能不能判定某些样例是否属 于该概念。为了描述这个问题，粗糙集采用了上近似和下近似的概念。 定义2 4 设s = ( u ，a ，v ，f ) 是一个决策系统，矗为u 上的等价关系，j u ，则 x 的上近似：置一( ) = 缸i 竹e u ) ( p l 。n x 中) 。 的下近似：噩( = 忸i 扛e u ) ( 叫。量肖) 。 z 的边界区域：b n r ) = r 一( x ) 一也( z ) 。 若b n 。( x ) o ，则集合就是一个租糙概念。下近似包含了所有使用知识胄可 确切分类到x 的元素，上近似则包含了所有可能属于z 的元素。概念的边界区域 b n 。( x 1 是根据知识r ，u 中既不能肯定归入集合，又能肯定不归入集合x 的元素 构成的集合。p o s r ( 膏) = 置一( j f ) 称为集合j 的置正域，n e g r ( x ) = u r - ( x ) 称为集 合的置负域。对于z 的上近似和下近似可形象的表示为圈2 - 1 。 一x 的f j 旺1 | = 【】e 域) 厂l 地摊域 口x 的i 近似( 负域) ，x 图2 - 1x 的上近似、下近似 f 噼lt h e u p p e r a p p r o x i m a l i o na n d l o w e r a p p m x i m a t i o no f x 5 属性依赖度 定义25 设属性集曰c ，u i n d ( r ) = d ，d 2 ，q 为由决策属性j d 所决定 中国石油人学( 华东) 硕七学位论文 的u 的划分，如果由b 划分的每个等价类都包含于由d 划分的等价类中，则称d 完全 依赖于b ，可表示为i n d ( b ) i n d ( d ) ，否则称d 不完全依赖于b ，d 对b 的依赖度 可以表示如下：御) = 等掣。 2 1 2 经典粗糙集理论的扩展【3 】 1 关系的推广 经典粗糙集模型的基础是不可分辨关系( 等价关系) ，这个条件是很强的。在实际 生活中获得的系统很难满足经典的等价关系。为此，人们从关系的推广出发，提出了 许多粗糙集的扩展模型： 一种是将论域上的二元等价关系推广为相似关系，得到基于相似关系的粗糙集模 型，更一般是将论域上的二元等价关系推广成为任意的二元关系得到了一般关系下的 粗糙集模型，另一种是将对象x 所在的等价类看成是x 的一个领域，从而推广导出基 于领域算子的粗糙集模型，如在第四章将详细介绍的基于集对分析的可变精度粗糙集 模型【2 1 】。 2 可变精度粗糙集模型 3 论域的推广 在实际情况中，我们经常碰到要在不同的论域下做出决策，另外涉及的问题中常 有数据丢失和信息不完备的情况，因此有必要对粗糙集模型进一步的扩充。 2 1 3 经典粗糙集理论的特点【2 2 】 粗糙集理论作为一种新的处理不精确、不确定与不完全数据的数学方法，与其他 处理不确定与不精确问题理论最显著的区别是它无需提供问题所需处理的数据集合之 外的任何先验信息，所以可以说对问题不确定性的描述或处理是比较客观的。模糊集 和概率统计方法是处理不确定信息的常用方法，但这些方法需要一些如模糊隶属函数 和概率分布等的数据附加信息或先验信息，这些信息并不容易得到。而粗糙集理论方 法只是利用数据本身提供的信息，不需要任何先验知识，这是和模糊集及证据理论最 主要的区别。 2 2 变精度粗糙集理论 粗糙集理论的中心问题是分类分析。p a w l a k 粗糙集模型的一个局限性是它所处理 的分类必须是完全正确的或肯定的，因为它严格按照等价类来分类的，因而它的分类 9 第_ 二章粗糙集理论概述 是精确的，办即“包含”或“不包含”，而没有某种程度上的“包含”或“属于”。 p a w l a k 粗糙集模型的另一个局限性是它所处理的对象是已知的且从模型中得到的所有 结论仅仅适用于这些对象集。但在实际应用中，往往需要将一些小规模的对象集中得 到的结论应用到大规模的对象集中去【3 】。 因此为增强粗糙集合模型的抗干扰能力，加拿大科学家z i a r k o 对经典粗糙集理论 进行扩展，z i a r k o 于1 9 9 3 年提出了可变精度粗糙集模型【5 j 。v p r s m 是在经典粗糙集 理论的基础上引入了分类正确率，即允许一定程度的错误分类率存在，从而具有一定 的容错性，增强了对噪声数据的适应能力。变精度粗糙集模型是p a w l a k 粗糙集模型的 扩充，它是在基本粗糙集模型的