（计算机应用技术专业论文）基于变精度粗糙集的近似集动态更新方法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 粗糙集理论是一种处理分析不确定或者模糊知识的数学工具，已经在模式识别、 专家系统、故障诊断和决策分析等方面有了较为成功的应用。由于数据库中的数据是 动态变化的，数据库中原有的知识已经不能够满足人们的需求。因此，如何在动态变 化的数据库中根据原有的知识高效地获取人们所需要的知识，从而指导决策分类，具 有重要的意义。 当信息系统中属性动态变化的时候，传统的方法更新近似集是重新对论域进行划 分，花费了重复计算的时间。本文分别讨论属性增减时，对原有的等价类进行划分， 避免了对论域的重新划分，提高了效率。并通过讨论等价类与原有近似集之间的关系， 给出了动态更新之后的近似集与原来近似集之间的相关定理，提出了在经典粗糙集模 型中，属性增减时近似集动态更新方法。实验结果验证了该方法的有效性，而且效率 优于原始的方法。 由于在经典粗糙集模型下对数据的要求是精确的，没有噪音或不含有缺失值的。 但是，现实生活中，许多原因可能导致数据不精确或者含有噪音。由此z i a r k o 提出了 变精度粗糙集模型。它允许有一定的噪音存在，数据的适应能力较强，这样对有噪音 的数据处理更加有效。本文在变精度粗糙集模型中，讨论了在属性增减时近似集的动 态更新方法。先通过研究信息系统中等价类的变化情况，给出属性增减时相应的定理 和推论，并分别提出了属性增减时，变精度粗糙集模型中近似集的动态更新方法，最 后通过实验验证了方法的有效性。 关键词：粗糙集；知识发现；动态更新；粒计算 西南交通大学硕士研究生学位论文第l i 页 a b s t r a c t r o u g hs e tt h e o r yi sak i n do fm a t h e m a t i c a lt o o l sf o rd e a l i n gw i t ha n da n a l y z i n g u n c e r t a i na n df u z z yk n o w l e d g e i th a sb e e ns u c c e s s f u l l ya p p l i e di np a t t e r nr e c o g n i t i o n ， e x p e r ts y s t e m s ，f a u l td i a g n o s i s ，d e c i s i o na n a l y s e sa n do t h e ra s p e c t s w i t ht h ev a r i a t i o no f d a t ai nd a t a b a s e ，t h eo r i g i n a lk n o w l e d g ei nd a t a b a s ec a n ts a t i s f yp e o p l e sd e m a n d s t h e r e f o r e ，i ti sm e a n i n g f u lt os t u d yh o wt oe f f i c i e n t l yo b t a i nk n o w l e d g ea c c o r d i n gt ot h e o r i g i n a li n f o r m a t i o ni nd a t a b a s ea n db e t t e rs u p p o r t0 1 1 1 d e c i s i o nm a k i n g w h e nt h ea t t r i b u t ed y n a m i c a l l yc h a n g e si ni n f o r m a t i o ns y s t e m s ，t h et r a d i t i o n a la p p r o a c h f o ru p d a t i n ga p p r o x i m a t i o n si sr e - d i v i s i o no ft h eu n i v e r s e i tc o s t sal o to fr e c a l c u l a t i n gt i m e h e r e ，a na p p r o a c hw h i c ha v o i d sr e d i v i s i o no ft h eu n i v e r s ei sp r o p o s e d t h ee f f i c i e n c yo f d y n a m i c a l l yu p d a t i n ga p p r o x i m a t i o n si si m p r o v e d b ya n a l y z i n gt h er e l a t i o n s h i pb e t w e e n e q u i v a l e n tc l a s s e sa n do r i g i n a la p p r o x i m a t i o n s ，t h ec o r r e s p o n d i n gt h e o r e m sb e t w e e nu p d a t e d a p p r o x i m a t i o n sa n do r i g i n a la p p r o x i m a t i o n sa r eg i v e n t h e n ，t h ea p p r o a c h e sf o rd y n a m i c a l l y u p d a t i n ga p p r o x i m a t i o n sw h i l ea d d i n go rd e l e t i n ga na t t r i b u t ea l er e s p e c t i v e l yp r o p o s e di n c l a s s i c a lr o u g hs e tm o d e l t h ee x p e r i m e n t a lr e s u l t sv e n f yt h ev a l i d i t yo ft h ea p p r o a c h e sa n d t h ee f f i c i e n c yo ft h ep r o p o s e da p p r o a c h e sa r eb e t t e rt h a nt h a to ft h eo r i g i n a la p p r o a c h i nc l a s s i c a lr o u g hs e tt h e o r y , t h ed a t am u s tb ea c c u r a t e ，n a m e l y , t h e r ei s1 1 0n o i s ed a t a o rd a t aw i t ham i s s i n gv a l u e h o w e v e r ，i nr e a la p p l i c a t i o n s ，t h e r ea r em a n yr e a s o n sw h i c h m a yl e a dt ot h ee x i s t e n c eo fn o i s eo ri n c o m p l e t ed a t a t h e r e f o r e ，t h ev a r i a b l ep r e c i s i o n r o u g hs e tm o d e lw a sp r o p o s e db yz i a r k o t oa i ma tm o d e l l i n gc l a s s i f i c a t i o np r o b l e m s i n v o l v i n gu n c e r t a i no ri m p r e c i s ei n f o r m a t i o n i nt h ev 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 ，b y s t u d y i n go nt h ec h a n g e so fe q u i v a l e n tc l a s s e si ni n f o r m a t i o ns y s t e m s ，s e v e r a lt h e o r e m sa n d c o r o l l a r i e sa r eg i v e n t h e n , t h ea p p r o a c h e sf o rd y n a m i c a l l yu p d a t i n ga p p r o x i m a t i o n sa r e r e s p e c t i v e l yp r o p o s e di nt h ev a r i a b l ep r e c i s i o nr o u g hs e tm o d e lw h i l ea d d i n go rd e l e t i n ga n a t t r i b u t e e x p e r i m e n t a lr e s u l t ss h o w t h ev a l i d i t yo ft h ep r o p o s e da p p r o a c h e s k e yw o r d s ：r o u g hs e t ；k n o w l e d g ed i s c o v e r y ；d y n a m i c a lu p d a t i n g ；g r a n u l a rc o m p u t i n g 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授 权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在 年解密后适用本授权书； 2 不保密因使用本授权书。 ( 请在以上方框内打“4 ”) 学位论文作者签名：芒问) 吱春军指导老师签名： 日期：2 0 f b 茸舅习弓1 日 日期： 二缴1 d 堋率一矛；f 臼 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： ( 一) 在经典粗糙集理论中给出了在属性增减时近似集的动态更新理论方法。在 属性增加时，该方法只需要在原来等价类基础上进行细分，通过原来等价类中对象的 增加属性的属性值进行比较，从而判断是否产生新的等价类，若产生新的等价类，根 据新的等价类与集合的关系，得到动态更新之后的近似集。在属性减少时，提出了属 性减少时近似集的动态更新方法，通过比较原来等价类中对象的减少属性之后属性的 属性值，判断原等价类是否合并成新的等价类，若合并产生新的等价类，讨论原来等 价类与集合的关系，得到动态更新之后的近似集，并经过仿真实验验证了方法的有效 性。 ( 二) 在变精度粗糙集模型中，讨论了在属性增减时近似集的动态更新方法。先 通过研究信息系统中等价类的变化情况，给出属性增减时相应的定理和推论，并分别 提出了属性增减时，变精度粗糙集模中近似集的动态更新方法，并通过实验验证了方 法的有效性。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成 果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰 写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确的说明。 本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：；罚戒乃青 日期加l 。舞r 同咖 西南交通大学硕士研究生学位论文第1 页 1 1 论文的研究背景 第1 章绪论 在现实生活中，随着社会的发展，各个领域的数据都在不断地增长。如何从这些 庞大的数据中获取潜在的、有用的知识，已经成为当今各个领域研究者进行科学研究 的热点问题。粗糙集理论是波兰数学家p a w l a k 于1 9 8 2 年提出的一种处理模糊和不确 定性知识的数学工具【1 】。其主要思想就是在保持分类能力不变的前提下，利用等价关系， 通过属性约简和决策规则约简，得到知识的过程。它从一个新的角度将知识定义为对 论域的划分能力，并且将其引入到数学的等价关系中进行讨论，从而为数据分析，特 别是不精确、不完整的数据分析提供了新的数学方法。 粗糙集理论具有无需提供除问题所需处理的数据集合之外的任何先验信息，仅根 据观测的数据，就可以删除冗余信息，比较不完整知识的程度粗糙度、属性间的 依赖度与重要性和提取分类规则等。对粗糙集理论的研究目前主要集中在不确定性推 理、规则提取、属性约简和粗糙集模型的扩展及应用等。经过3 0 多年的发展，粗糙集 理论已经在知识发现、机器学习、决策分析、归纳推理和模式识别等方面得到了较为 成功应用，引起了各国学者的广泛关注【14 1 。 由于经典粗糙集理论不能处理某种程度上的“包含和“属于”，所以z i a r k o 提 出了变精度粗糙集模型【5 】。它是经典粗糙集模型的扩展。它的基本思想是在经典粗糙集 模型中引入参数( 0 0 5 ) ，即允许一定程度的错误分类存在。当= 0 时，就退 化为经典粗糙集模型。对经典粗糙集理论的这种扩展有利于从数据中发现更加广泛的 数据之间的关联和决策规则，得到了许多研究学者的广泛关注，在实际问题中的应用 也越来越广泛 】。 1 2 论文的研究意义 目前对信息系统的研究大都是针对静态数据的。而在现实生活中，随着社会经济 的发展，各个领域的数据都在不断变化，因此信息系统中属性和对象都是在不断动态 变化的。随着信息系统中属性和对象的不断变化更新，如果人们每次利用粗糙集方法 更新知识时都重新通过原有的方法来获得等价类和上、下近似集直至决策规则等信息， 这样会浪费大量重复计算的时间，而且通常情况下效率也很低。因此，如何根据已有 的知识，获取人们所需要的有用知识，提高获取知识的效率，是近年来人们关注的热 点问题之一。目前，利用粗糙集方法对信息系统进行增量式更新的研究主要集中在对 象增减时，通过设计相应的算法进行获取规则。当属性增减时，对动态知识获取方法 西南交通大学硕士研究生学位论文第2 页 的研究还不多见。因此，面对各个领域不断增长的数据，在属性增减时，研究如何利 用粗糙集理论有效地处理不断变化的信息系统，从中获取有用的知识，具有重要的理 论意义和实际应用价值。 1 3 国内外研究现状 1 3 1 粗糙集理论的研究现状 粗糙集理论的研究内容主要包括不确定性推理问题、粗糙集扩展模型、属性约简 算法和应用研究等。 ( 1 ) 不确定性推理问题 陈湘晖等给出了适合数据对象具有不同重要性情况下粗糙集决策规则集合的不确 定性度量，作为规则评价的标准f 6 】。王国胤等通过对决策表和决策规则的不确定性研究， 建立了基于粗糙集表示、度量和处理不确定性信息和知识的理论，提出了一种不确定 性条件下数据自主式学习模型和方法用。刘清给出了在非等价关系下的知识不确定性问 题的描述【8 】。米据生等研究了模糊粗糙集的不确定度量问题并提出了广义模糊粗糙集的 不确定性【9 1 0 】。 ( 2 ) 粗糙集扩展模型 粗糙集理论在进行数据的分析和处理时，往往会遇到噪音或者数据缺失的情形， 此时，经典的粗糙集方法就不能够满足求解问题的需要。因此，对粗糙集的扩展模型 的研究，尤为重要。如z i a r k o 提出了变精度粗糙集模型【5 。姚一豫等提出了一般关系 下的粗糙集模型1 11 2 】。王基一等提出了概率粗糙集模型【1 3 】。d u b o i s 等提出了粗糙模糊集 和模糊粗糙集模型 1 4 1 。k r y s z k i e w i c z 提出了容差关系粗糙集模型【1 5 】。s t e f a n o w s k i 等提 出基于量化容差关系的r o u g h 集扩充模型【1 6 】。w i l l i a m 等提出了一种新的覆盖粗糙集模 型【17 】。王国胤提出了限制容差关系粗糙集模型【1 8 】。尹旭日等提出约束相似关系的扩充 r o u g h 集模型【1 9 】等。 ( 3 ) 属性约简算法 属性约简算法是粗糙集理论的核心之一，国内外的许多研究学者对此做了大量的 研究工作。s k r o w r o n 提出了差别矩阵法对属性进行约简，利用差别矩阵得到差别函数， 然后求解析取范式，从而计算出所有的属性约简【2 0 】。t s a n g 等给出了一种在模糊粗糙集 模型中用辨识矩阵来进行属性约简的方法【2 1 】。王国胤等以条件熵为启发知识，给出了 决策表的启发式知识约简算法【2 2 1 。刘振华等提出了决策表中决策属性集相对于条件属 性集的条件信息量的概念，得到了约简过程中的启发式搜索的条件，并以此为基础给 出了一种基于信息量的属性约简算法【2 3 】。梁吉业等通过知识的信息量定义了属性的重 要度，以此为基础提出了一种基于信息量的属性约简算法【2 4 】。杨明在对象动态增加情 西南交通大学硕士研究生学位论文第3 页 况下提出了基于改进差别矩阵的属性约简算法幽。 ( 4 ) 粗糙集理论的应用研究 粗糙集理论在专家系统、决策支持系统、机器学习、知识发现、归纳推理、模式 识别和故障诊断等方面都有了非常成功的应用【l 舶】。张东波等提出了一种基于粗糙集约 简的神经网络集成分类方法并将其应用到遥感图像的分类中【2 6 1 。 f a y 等将粗糙集模型应 用到经济和金融预测领域，通过对历史数据的模式分类，准确的预测将来金融投资状 态鲫。w a n g 通过模糊粗糙集系统给出了一个有效的方法，通过虚拟可视化a g e n t 来帮 助股票持有人监测当前的股票价格，在任何给定的时间对股票价格进行预测，帮助股 票持有人做出决策【2 8 】。周洪宝等利用粗糙集理论对神经网络的训练样本进行属性约简， 提取训练样本的重要特征，从而减少维数，提高网络训练速度和识别率 2 9 1 。 1 3 2 变精度粗糙集模型的研究现状 自从z i a r k o 提出变精度粗糙集模型以来，许多学者对该模型进行了研究。研究的 内容主要集中在基于变精度粗糙集模型中的知识约简理论与方法、精度值的确定方 法、模型的推广和应用等方面。 ( 1 ) 基于变精度粗糙集模型的知识约简方法研究 基于粗糙集理论的信息系统知识发现问题本质上是按照属性特征将对象进行分类 的问题。知识约简是在保持分类能力不变的情况下，删除其中不必要属性的过程。目 前人们已经从不同角度出发提出了一些约简概念，具体包括：约简 3 0 】；上( 下) 近似约简f 3 】；上( 下) 分布约简【3 】；不协调目标信息系统的上、下近似分布约简 3 1 1 ；基于结构的约简方法【3 2 l 。王加阳等通过引入条件类包含度阈值的概念，描述了 包含度和分类率的区间关系，提出了消除异常的区间约简思想，并构造了区间约简算 法，完善了可变精度粗糙集模型的约简【3 3 】。蔡娜等从属性依赖度增量、互信息增量及 条件属性相对于决策属性的覆盖度和准确度相结合的量度对属性重要度进行分析来解 决变精度粗糙集理论的属性约简问题【3 4 1 。i n u i g u c h i 提出了变精度粗糙集模型中一种基 于结构的属性约简方法【3 5 】。w u 给出了一种基于变精度粗糙集模型的不完备信息系统知 识获取方法【3 6 1 。 ( 2 ) 变精度粗糙集模型中的精度值的确定方法研究 在变精度粗糙集模型中，精度的取值，对于近似分类质量和确定性规则的提取 等有重要的作用。s u 等在变精度粗糙集模型中提出了一种确定精度值的方法【3 7 1 。吉 阳生等提出了一种增量计算值的方法，这种方法能够选取合适的值，而且具有动 态增量和计算开销显著降低的优点 3 8 】。周爱武等提出了在确定近似分类质量下取值 范围的确定方法，根据近似分类质量，通过对正确分类率集合的不同查找方法，能够 快速查找的范围f 3 9 1 。 西南交通大学硕士研究生学位论文第4 页 ( 3 ) 变精度粗糙集模型的推广 巩增泰等定义了般关系下的多数包含关系，并提出了一种一般关系下的变精度 粗糙集模型 4 0 1 。z h a o 等将模糊粗糙集模型与变精度粗糙集模型结合提出了模糊变精度 粗糙集模型【4 1 】。w a n g 等讨论了不完备信息系统中基于容差关系和非对称相似关系的变 精度粗糙集模型的性质【4 2 】。颜锦江等提出了不完备信息系统中一种基于相似度的变精 度粗糙集模型，并给出求约简的相关算法 4 3 1 。 ( 4 ) 变精度粗糙集模型的应用 刘盾等在变精度粗糙集模型和g r e c o 扩展粗糙集模型中引入不相容信息决策系统， 给出了基于偏好关系的不完备信息系统变精度粗集模型，并且将此模型用于检测通信 设备的性能】。c h e n g 等采用变精度粗糙集模型对信息系统的风险规则进行挖掘【4 5 1 。刘 立军等提出了集合的二进制表示方案，成功地解决了变精度粗糙集模型的m a t l a b 实现 问题，这种方案对变精度粗糙集理论在工程中的具体应用有重要的推动作用 4 6 1 。陶志 等提出一种基于变精度粗糙集理论的规则挖掘算法，该算法得到的规则既有一定的噪 声容忍度又有较高的准确度和覆盖度，从而能在一定程度上保证预测和分类的准确性 1 4 7 。谢刚等设计一个基于变精度粗糙集模型的算法，用于调整软件项目投标风险群决 策表中的分类误差，计算投标项目和风险指标的综合风险当量，讨论相应的风险规避 措施、风险规避力度排序和风险规避流程【4 8 】。张登峰等将变精度粗集模型应用于故障 诊断专家系统的知识更新和获取，实现了最简诊断知识的获取 4 9 1 。赵亮等提出基于变 精度粗糙集的多属性群决策安全评估方法，对信息系统进行安全评估f 5 0 1 。 1 3 3 基于粗糙集的增量式知识更新的研究现状 目前对基于粗糙集模型的增量式知识更新的研究主要包括以下几种情况。 ( 1 ) 属性集不变，对象增减的情况 在经典粗糙集模型中，对于属性集不变，对象增减的情况研究成果较多。s h a n 等 首次提出基于粗糙集的增量式规则获取算法，要求新对象与原决策表相一致，不出现 新决策类，并且不能同时对规则的参数进行更新【5 l 】。蒋思宇提出的约简模型下的增量 算法，能够根据决策表新增样本与原有的最简规则集的关系，快速推出新决策表的最 简规则集【5 2 】。l i u 等给出基于改进的分辨矩阵规则增量提取的并行算、法【5 3 1 。s h u s a k u 等 在医学数据库信息获取中提出增量式学习可能规则的方法，对确定规则获取问题没有 涉及【5 4 1 。b a n g 等提出的动态获取算法是相对于条件类和决策类的，而不是相对于经过 约简且极小化后的规则剿5 5 1 。在扩展粗糙集模型下，王利等从变精度粗糙集模型出发， 讨论了新增记录与已有条件属性等价类的关系及对规则集的影响，在此基础上提出了 基于变精度粗集模型的增量式规则获取算法 5 6 】。z h e n g 等提出基于规则树的增量式高效 知识获取r r i a 算法其特点是在原有的决策树规则集基础上进行规则的增量式更新， 西南交通大学硕士研究生学位论文第5 页 避免了重复学习，提高了效率【5 7 】。g u o 等给出基于搜索树的规则增量提取方、法，优点 是不需要创建区分矩阵 5 8 】。在变精度粗糙集模型下，c h e n 等讨论了单个对象增减时近 似集的变化情况，提出了增量更新近似集的方法，提高了计算近似集的效率1 5 9 1 。安利 平等定义了a 不可分辨关系的概念，从而建立a 决策矩阵，并在a 决策矩阵上建立决 策函数从而实现增量式获取规则。 ( 2 ) 对象集不变，属性增减的情况 c h a n 在经典粗糙集框架下通过边界集等相关知识提出了单个属性的增加与删除时 近似集的增量式更新方法和规则提取方法【6 1 1 。l i 等实现了多个属性同时增删时近似集 的增量式更新方法和规则提取方法【6 2 】，并推广到在相似关系和特性关系的粗糙集模型 中近似集的动态更新，进而获取确定性规则与不确定性规则 6 36 4 。胡成祥等在传统方法 的基础上，将近似集增量更新理论推广到限制容差关系粗糙集模型中【6 5 】。邹维丽等在 集值信息系统中提出了近似集增量更新的方法嗣。然而，在属性集改变时，变精度粗 糙集模型下的动态知识更新方法还未解决。 ( 3 ) 对象集和属性集均不变，属性值变化的情况 这种情况相当于对某个或者某些属性的属性值细化或粗化，此时，再对信息系统 进行知识约简和动态更新等相关研究。c h e n 等在经典粗糙集模型中定义了属性值细化 和粗化的概念，在属性集和对象集不变时，研究了在属性值粗化细化时近似集的增量 更新方法 6 7 1 。z o u 等研究了在集值粗糙集模型中属性粗化细化时近似集的增量更新方 法【6 8 】。 ( 4 ) 对象集和属性集同时改变的情况 目前，在基于粗糙集模型的动态知识发现的研究中，当对象集和属性集同时改变 时，对信息系统进行增量式规则提取、属性约简方法的研究，还未见到有这方面的研 究成果。 1 4 本文的研究工作及组织结构 本文的研究内容来源于国家自然科学基金项目“基于粒计算的动态知识发现中若 干关键问题研究 ( n o 6 0 8 7 3 1 0 8 ) 。对动态环境下近似集增量更新的研究，是利用粗糙 集理论进行动态知识更新研究的重要基础。本文通过研究属性增加或者减少时近似集 动态更新方法，根据已知信息系统中存在的等价类和属性的增减，对论域进行重新划 分，得到原来近似集与动态更新之后近似集之间的关系，可以提高对近似集动态更新 的效率。通过研究原来信息系统中近似集与动态更新之后近似集之间的关系，给出了 原有近似集与动态更新之后近似集之间的相关定理，分别提出了属性增减时在经典粗 糙集模型中和变精度粗糙集模型中近似集动态更新方法。 西南交通大学硕士研究生学位论文第6 页 论文的组织结构如下： 第l 章介绍论文的研究背景、研究意义、粗糙集理论和增量式知识更新的国内外 研究现状及本论文的主要研究内容。 第2 章介绍经典粗糙集模型中和变精度粗糙集模型中相关的基本概念。 第3 章从属性增减的角度考虑，研究经典粗糙集模型中近似集动态更新方法，通 过仿真实验，验证了算法有效性，并对实验的结果进行分析。 第4 章从属性增减的角度考虑，给出原有近似集与动态更新之后近似集之间的相 关定理，提出基于变精度粗糙集模型的近似集动态更新方法，通过仿真实验验证了算 法的有效性，并对实验的结果进行分析。 最后，总结本文的研究工作，提出其中的不足之处和需要改进的地方，并给出以 后可以进一步研究的内容。 西南交通大学硕士研究生学位论文第7 页 2 1 引言 第2 章粗糙集理论基础知识 粗糙集理论是建立在分类基础上的，将分类理解为论域空间上的等价关系，这个 等价关系构成了对这个论域空间的完整划分。本章主要介绍经典粗糙集模型和变精度 粗糙集模型中相关的基本概念，为后续章节作铺垫。 2 2 经典粗糙集理论相关概念 定义2 1 t 1 1 四元组s = ，a ，y ，) 称为知识表达系统，其中u 是表示对象的非空有限 集合，称为论域；a 是表示属性的非空有限集合，y 表示属性域集合，v o 表示属性口的 值域；厂：u xa _ y 表示的一个信息函数，它为每个对象在每个属性上赋予一个信息值， 即v aa ，z u ，f ( x ，口) v o 。若存在一个工u ，口c ，y ( x ，力未知( ( x ，口) = 幸) ，则 称该知识表达系统是不完备的；否则称该知识表达系统是完备的。 定义2 2 t 3 】设s = ( u ，a ，v ，f ) 为知识表达系统，a = cu d ，c nd 囝，c 称为条件 属性集，d 称为决策属性集，具有条件属性和决策属性的知识表达系统成为决策信息 系统。 由于知识表达系统也可称为信息系统，所以，若信息系统是完备的，称为完备信 息系统，若信息系统是不完备的，称为不完备信息系统。 定义2 3 t 1 】对于每一个属性子集b a ，我们定义一个不可分辨二元关系i n d ( b ) ， 即： l v d ( b ) = ( x ，y ) i ( x , y ) u 2v b b ( 6 ( 工) = 6 ( y ) ) ( 2 - 1 ) 显然，1 - n d ( b ) 是一个等价关系，且 1 n d ( b ) = n 肼d ( 6 ) )( 2 - 2 ) o e b 由于粗糙集可以近似的定义，我们可以用下近似和上近似两个近似算子来描述， 它们的定义分别如下。 定义2 4 t 1 】对于给定的信息系统s = ( u ，a ，v ，) ，对于任意子集x u 和其中一个等 价关系r 1 n d ( p ) ，x 的r 下近似集和上近似集分别由尺的基本集定义如下： g ( x ) = u r u r i 】，x ( 2 - 3 ) 尺( 又) = u 】厂u r i y n x o ( 2 - 4 ) 西南交通大学硕士研究生学位论文第8 页 它们的等价形式可表示为： 旦( j ) = 剐u 【z l x ( 2 - 5 ) r ( ) = 则ufjknxo(2-6) x 的r 下近似集被解释为所有包含在集合里面的等价类的并集，j 的r 上近似 集被解释为所有那些与集合并的交集不为空集的等价类的并集，也就是说下近似集是 论域u 中，所有通过等价关系定能被划分到集合j 中的元素构成的集台，而上近似 集是论域u 中，所有通过等价关系可能被划分到集合中的元素构成的集合。 的r 上近似集和下近似集的差被称为x 的r 边界域，即：抽_ ( x ) = 页( ) 点( 卫) 。 边界域是某种程度上论域的不确定域。对于边界域中的元素，通过等价关系，既不能 准确地被划分到集合肖中，也不能准确地被划分到集台互的补集中。 定义2 5 集台并的r j 下域p o s 。( ) = 点( j ) ，x 的r 负域n e g r s ( x ) = u 再( ) 。正域 是论域中根据属性b 所有一定能划分到集合盖中的元素构成的集台，而负域是根据论 域中根据属性b 所有不能被划分到集合x 中的元素构成的集合。 定3 ( 2 6 杠1 令x u ，五是论域u 上酌一个等价关系。当x 是r 的某些等价类的并 时，称并是月可定义的，否则称爿是r 不可定义的。r 可定义集称为r 精确集，r 不可 定义集称为r 粗糙集。 图2 1 表明了一个论域空间中，集合与上近似集、下近似集、边界域和负域之问 的关系。 幽2 - 1 粗糙集的示意图 r f z 、 旦( z ) b n r ( x ) h e 掣、x 、 下面通过具体实例来简单说明如何求解一个集台的上、下近似集、边界域和负域。 例2 - 1 给定论域空间u = “，t ，_ ，h ， ，气，* ， ，x = i ：，耳， ，x b ， 。等价关系r 对 西南交通大学硕士研究生学位论文第9 页 论域u 划分的等价类为u r = 饵，最，e ，e ) ，其中互= “，恐，屯 ，e 2 = ) ，岛= 玩，x 6 ， e = ，黾) 。根据上近似集、下近似集、边界域和负域的定义，可知x 的上近似集为 页) = 而，而，x 3 ，毛，x 6 ，x 7 ，而) ，彳的下近似集为墨( x ) = 玩，) ，x 的边界域为 b n r ( x ) = 如，恐，x 3 ，而，黾) ，x 的负域为n e g r ( x ) = _ ) 。 由于集合的边界域的存在，从而引起集合的不精确性。边界域越大，说明它的精确 性越低。为了能够准确地用上近似集和下近似集来度量集合的精度，人们引入近似精 度的概念【8 。等价关系尺定义的集合彳的近似精度表示为 啪卢( x ) i p 7 ) 其中工不为空集，i 义i 表示集合x 的基数。 精度a r ( x ) 用来表示集合x 的知识的完全程度。显然，对于每个等价关系r 和 xcu 有o ( x ) 1 。当( x ) = 1 时，垦( x ) = 页( x ) ，集合x 的r 边界域6 行( x ) 为空， 集合x 为r 可定义的；当口。( x ) 1 时，集合x 有非空r 边界域，集合x 为r 不可定义 的。 定义2 7 团设集合簇，= 五，五，咒) ( u = u 五) 是论域u 上定义的知识，b 是一个 属性子集，定义b 对f 近似分类的精度以( ，) 为 d s ( f ) = f 星( 置) i i 页( 五) i ( 2 - 8 ) 定义2 8 嘲设集合簇f = 五，五，鼍) ( u = u 工) 是论域u 上定义的知识，b 是一个 属性子集，定义b 对f 近似分类的质量旷) 为 ( f ) = i 墨( 置) l | u l ( 2 9 ) 召对f 近似分类的精度描述的是当使用属性子集b 对对象进行分类时，所有可能的 决策中，确定决策所占的比例；召对，近似分类的质量是运用属性子集b 对对象进行 分类时，能够确定决策的对象在论域中所占的比例。 2 3 变精度粗糙集理论相关概念 变精度粗糙集模型是在经典粗糙集模型的基础上引入了( 0 f l 0 5 ) ，允许一定 程度的错误分类率存在。一方面完善了近似空间的概念，另一方面也有利于发现人们 感兴趣的有关知识。它的主要任务是解决属性间无函数或者不确定关系的数据分类问 题。下面介绍变精度粗糙集模型中相关的基本概念。 西南交通大学硕士研究生学位论文第1 0 页 定义2 9 【3 1 设x 和】，表示有限论域u 的非空子集。如果对于每一个元素e x ，有 e y ，则称y 包含x ，记作y2x ，令 c ( x ，y ) = 1 - l x n y p i x l f 高f 三： ( 2 一，。) 其中lxl 表示集合x 的基数，称c ( x ，】，) 为集合x 关于集合y 的相对错误分类率，即 如果我们将集合x 中的元素分到集合】，中，则做出分类错误的比例为c ( x ，y ) x 1 0 0 。 真正错误分类的元素数目为c ( x ，1 0 ixi ，称c ( x ，】，) ixl 为绝对分类误差。令0 o 5 ， 称多数包含关系定义为y d _ 。x 营c ( x ，即。“多数”要求隐含着工与j ，中的公共元素的 数目大于x 中的元素数目的5 0 。 定义2 1 0 t 3 】设( u ，尺) 为近似空间，其中论域u 为非空有限集合，r 为u 上的等价关 系， u r = 她，最，e ) 为r 的等价类或者基本集构成的集合。令o o 5 ，对于 x u ，定义x 的下近似集为： 彤( x ) = u e u r i 五彳 ( 2 1 1 ) 或者 ( 石) = u e u r ic ( e ，x ) 辟 ( 2 - 1 2 ) r p ( x ) 也称为正区域，记作：p o s r b ( x ) 。 定义x 的上近似集为： ( x ) = u e u r i c ( e ，x ) 1 一 ( 2 1 3 ) x 的的边界域为： b n r p ( x ) = u e u r i f l c ( e ，x ) 1 一 ( 2 1 4 ) x 的的负区域为： n e g r a ( x ) = u e u r f c ( e ，z ) 1 一肼 ( 2 1 5 ) x 的正区域又称为石的下近似集，可表示为心( x ) ，理解为将论域u 中的对象 以不大于的分类误差分类于集合彳的集合；彳的边界域可表示为b n r s ( x ) ，理解为 将论域u 中的对象以不大于的分类误差，既不能分类于集合x 又不能分类于集合x 的补集的集合；x 的负区域可表示为n e g r p ( x ) ，相应的理解为将论域u 中的对象以不 大于的分类误差分类于集合x 的补集的集合。 定义2 1 1 【3 1 给定信息系统s = ( u ，a = c u d ，g ，厂) ，c 和d 分别为决策信息系统的条 件属性集和决策属性集。设属性集合尸c 为条件属性集，9 d 为决策属性集，i n d ( e ) 、 西南交通大学硕士研究生学位论文第11 页 加d ( q ) 表示由p 、q 决定的不可区分关系，夕为依赖噪音程度的数，卢的取值范围为 o 0 5 ，定义分类质量为： ( 尸，q ) = p o s r ( p , q , f 1 ) u l ( 2 - 1 6 ) 其中 p o s r ( p ，q ，历= u r e - u ，q 塑塑口y ( 2 1 7 ) 近似分类质量表示的是条件类以不大于的分类误差归入决策类的对象的百分 比，表示决策表的分类能力。 2 4 本章小结 本章主要介绍了经典粗糙集理论中上、下近似集、边界以及精度等相关定义和变 精度粗糙集模型中相对错误分类率、近似集以及相对分类质量等相关定义，为后续章 节进一步的理论研究打下一定的基础。 西南交通大学硕士研究生学位论文第12 页 第3 章基于经典粗糙集模型的近似集动态更新方法 3 1 概述 随着数据的不断增加，使得绝大多数数据库中对象的个数和属性的个数都在不断 地发生着变化。因此，如何有效地对不断变化的数据库中隐含的知识进行动态更新的 研究具有重要的意义，也得到了人们越来越多的重视。目前，在粗糙集理论的研究中， 对动态知识发现的研究主要集中在信息系统中对象增减的情况下来讨论，而对于属性 增减时知识的动态更新研究还不多。c h a n 从边界域的角度考虑，研究近似集的更新方 法，通过研究信息系统中每个属性的等价类和上、下边界域对近似集的影响，得到动 态更新之后的近似集 6 l 】。这种方法在进行计算信息系统中每个对象对应单个属性边界 域过程中，具有较高的算法复杂性，但并没有分析算法的复杂度，也没有给出实验仿 真结果。l i 等从多个属性边界域角度考虑，采用讨论原近似集与已知单个属性的上、 下边界域之间关系的方法，研究近似集的增量更新理论，并且把这种方法引入到不完 备信息系统中基于特性关系的粗糙集模型中，给出了不完备信息系统中近似集增量式 更新方法，但并没有分析算法的复杂度等【6 26 3 1 。本章主要讨论信息系统中属性增减时等 价类的变化情况，动态更新近似集，分析属性增减时动态更新前后近似集之间的关系， 给出近似集动态更新的相关定理，提出了属性增减时经典粗糙集模型中近似集动态更 新方法，降低了算法的复杂性。 3 2 属性增加时近似集动态更新 在信息系统中，当属性增加的时候，传统的方法是对信息系统进行重新计算，获 取等价类和上、下近似集再得到决策规则。这样做会重复计算整个信息系统，需要花 费大量的时间，效率比较低。因此，从单个属性增加的角度考虑可以减少动态更新信 息系统所花费的时间，避免不必要的开销，提高效率。 当属性增加时，通过等价关系对整个论域的划分可能发生变化，从而导致等价类 也可能发生变化( 如图3 1 所示) 。此时，对于经典粗糙集模型中近似集的变化情况而 言，动态更新之后的上、下近似集可能会发生一定的变化。如果原来的等价类包含于 下近似集，那么，随着属性的增加，对原等价类进行细分而形成的新的等价类子集也 包含于下近似集；如果原等价类是包含于上近似集，那么随着属性的增加，对原等价 类细分而形成的新的等价类，有可能仍然被划分到上近似集，也有可能被划分到下近 似集，还有可能被划分到负域；如果原等价类是包含于负域，那么由它细分而形成的 新的等价类子集仍然被划分到负域。当属性增加的时候，原来的上近似集中的等价类 西南交通大学硕士研究生学位论文第13 页 有可能被划分到下近似集中。因此，对下近似集而言，有增大的趋势，对上近似集而 言，有减少的趋势。接下来给出当属性增加时，近似集动态更新的相关定理。 图3 1 属性增加时等价类变化示意图 3 2 1 增加单个属性时近似集更新方法 对于给定的信息系统，当增加单个属性的时候，等价类被细化，等价类的种类增 加，下近似集有增大的趋势，上近似集有减小的趋势。在这里给出经典粗糙集模型中， 属性增加时近似集动态更新的相关推论和定理。 定义3 1 设信息系统s = ( u ，a ，y ，厂) ，对论域u 进行划分形成的等价类为 u r = 饵，最，e ) ，属性增加之前原信息系统中集合x 的尺上近似集和r 下近似集分 别记为尺( x ) 和星( ) 。当属性增加之后，如果厶，；e ( d ) 厶两( d ) ( f ，= 1 ，2 ，刀，f ) ，那 么等价类互( i = 1 , 2 ，刀) 被细化。令等价类置被细化之后形成新的等价类为 乓( k = l ，2 ，工) ，属性增加之后集合x 的r 上近似集和r 下近似集分别记为r 。) 和 鱼( x ) 。 推论3 1 设信息系统s = ( u ，a ，v ，f ) ，等价类e ( f = 1 ，2 ，聆) 是对论域u 进行划分的 等价类，d 为信息系统中增加的单个属性，厂为信息函数。 ( 1 ) 如果氏。丘( d ) = 尢一( d ) ( f ，= 1 ，2 ，刀，f 歹) ，那么属性增加之后，等价类巨不 发生细化，此时，墅( x ) = 墨( x ) ，( x ) = r ( x ) 。 ( 2 ) 属性增加之后，若等价类发生细化，等价类互( f 1 , 2 ，刀) 细化所形成的新的 等价类记为毛( j j = 1 ，2 ，z ) ，如果置墨( x ) ，那么层。丛) 。 ( 3 ) 属性增加之后，如果信息系统中每个对象对应的增加属性的属性值都不相等， 西南交通大学硕士研究生学位论文第14 页 那么筻( x ) = r 。( x ) = x 。 一 ( 4 ) 属性增加之前，等价类互与z 交集为空集，即置n x = o ，那么属性增加之 后，此等价类是否发生细化不影响近似