（应用数学专业论文）基于云模型和粗糙集的分类挖掘方法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 作为数据挖掘的一个重要研究领域，分类有着非常广泛的应用前景判定 树是分类中常用模型之一，自从被提出以来己经得到广泛的研究和应用然而， 由于其不能很好地处理空缺值和连续值以及在知识表达上的不精确性和复杂 性等问题，使判定树的研究继续是人们关注的热点 为表示概念的不确定性，云模型被提出，它有机地结合了模糊性和随机性， 实现了定性语言值与定量数值间的不确定性转换；另一方面，在不完备信息系 统中，人们对经典粗糙集进行了扩展，提出了特性关系粗糙集模型，它能有效 地处理空缺值 本文以云模型和基于特性关系的粗糙集扩展模型为基础，对分类挖掘中若 干关键问题进行了深入研究主要工作如下： 1 提出特性关系下粗糙集中概念的上下近似的增量更新方法和规则提取 方法并通过系列实验对该方法做了性能分析。结果表明该方法确实可以有效 地动态支持属性推广和提取规则 2 对云模型作了讨论，包括云模型的概念、云模型的理论基础和用来离 散化连续属性的云变换等 3 提出基于云模型和粗糙集扩展模型的一个新的判定树算法d t c c r s ， 该算法首先利用云变换离散化连续属性，再选择能够使得特性关系下加权平均 粗糙度最小的属性作为当前结点的分裂属性，然后递归下去直至判定树终止生 长实验表明，该算法可妥善处理空缺值、合理离散连续属性与c 5 0 相比， 该算法得到的判定树不但结构简单、分类准确率高，而且分类规则也容易理解 关键词：数据挖掘；判定树；分类；粗糙集；云变换 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t a s 趾i m p o r t a n tr e s e a r c h f i e l do fd a t am i n i n g , c l a s s i f i c a t i o nh a sw i d e a p p l i c a t i o n s d e c i s i o nt r e ei so n eo f t h em o d e l st h a ta r eo f 【e nu s e di nc l a s s i f i c a t i o n i th a sb e e nw i d e l yi n v e s t i g a t e da n da p p l i e ds i n c ei tw a si n t r o d u c e d h o w e v e r , d e c i s i o nt r e ec a l ln o th a n d l em i s s i n gd a ma n dc o n t i n u o u sd a me f f e c t i v e l ya n dt h e r e e x i s tt h ec o m p l e x i t ya n du n c e r t a i n t yi nk n o w l e d g ee x p r e s s i o n i n v e s t i g a t i o no f d e c i s i o nt r e ei ss t i l lo n eo f h o tt o p i c si nd a t am i i l i i l g i no r d e rt or e p r e s e n tt h eu n c e r t a i n t yo ft h ec o n c e p t , c l o u dm o d e lt h a tc o m b i n e s t h ep r o p e r t i e so ff u z z i n e s sa n dr a n d o m n e s sw a si n t r o d u c e d rr e a l i z e dt h e u n 印r t a i n t yt r a n s i t i o nb e t w e e nq u a l i t a t i v ec o n c e p ta n dq u a n t i t a t i v ed e s c r i p t i o n i n a d d i t i o n , i nt h ei n c o m p l e t ei n f o r m a t i o ns y s t e m ，a ne x t e n s i o no f c o n v e n t i o n a lr o u g h s e t s ，t h ec h a r a c t e r i s t i cr e l a t i o n - b a s e dr o u g hs e t s ，w a sp r o p o s e dt h a tc a nd e a lw i t h i n c o m p l e t ed a t ad i r e c t l y t h i st h e s i sf o c u s e so ns o m ek e yp r o b l e m so fc l a s s i f i c a t i o ni nd a t am i n i n gb a s e d o nc l o u dm o d e la n dt h ec h a r a c t e r i s t i cr e l a t i o n - b a s e dr o u g hs e t s t h em a i n c o n t r i b u t i o n so f t h i st h e s i sa r ea sf o l l o w s 1 a na p p r o a c hf o ri n c r e m e n t a l l yu p d a t i n ga p p r o x i m a t i o n so f ac o n c e p ta n dr u l e e x t r a c t i o nu n d e rt h ec h a r a c t e r i s t i cr e l a t i o n - b a s e dr o u g hs e t si sp r e s e n t e d as e r i e s o fe x p e r i m e n t ss h o w st h a tt h ep r o p o s e da p p r o a c hm a yh a n d l ea d y n a m i ca t t r i b u t e g e n e r a l i z a t i o na n dp e r f o r mr u l ee x t r a c t i o ne f f e c t i v e l yi nd a t am i l l i n g 2 c l o u dm o d e li sd i s c u s s e d ，i n c l u d i n gs e v e r a lr e l a t e dc o n c e p t si nc l o u dm o d e l ， t h e o r e t i c a lf o u n d a t i o no f c l o u dm o d e la n dc l o u db a n s f o r n lf o rd i s c r e t i z i n g c o n t i n u o u sd a t a 3 an e wa i g o r i t h md t c c r sb a s e do nc l o u dm o d e la n dt h ec h a r a c t e r i s t i c r e l a t i o n - b a s e dr o u g hs e t sf o rc o n s t r u c t i o no f t h ed e c i s i o nt r e ei sp r e s e n t e d i tf i r s t l y u t i l i z e sc l o u dw a u s f o 姗i od i s c r e t i z ec o n t i n u o u sd a t a t h e n , t h ea t t r i b u t ew h o s o w e i g h t e dm e a nr o u g h n e s su n d e rt h ec h a r a c t e r i s t i cr e l a t i o n - b a s e dr o u g hs e t si st h e s m a l l e s tw i l lb es e l e c t e da st h es p l i t t i n gn o d e e x p e r i m e n t ss h o wt h a tt h ea i g o r i t h m c a nh a n d l ei n c o m p l e t ed a t aa n dd i s e r e t i z ec o n t i n u o u sd a t ae f f e c t i v e l y t h ed e c i s i o n t r e e sc o n s t r u c t e db yd t c c r st e n dt oh a v es i m p l e rs t r u c t u r e ，h i g h e rc l a s s i f i c a t i o n 西南交通大学硕士研究生学位论文第1 ii 页 a c c u r a c ya n dm o r eu n d e r s t a n d a b l er u l e st h a nc 5 0 k e y w o r d s ：d a t am i n i n g ；d e c i s i o nt r e e ；c l a s s i f i c a t i o n ；r o u g hs e t ；c l o u dt r a n s f o r m 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 数据挖掘 1 1 1 数据挖掘研究背景 近半个世纪以来，计算机和信息技术的高速发展给人类社会带来了巨大的 变化与影响，数据成为了最重要的战略资源随着科技的进步，人们能以更快 速、更廉价的方式获取和储存数据，这使得数据库应用的规模、范围和深度不 断扩大现在，成千上万个数据库被用于商业管理、政府办公、科学研究和工 程开发等，并且这一势头仍将持续发展下去据估计，早在2 0 世纪8 0 年代， 全球信息量每隔2 0 个月就要增加一倍而进入2 1 世纪，全世界所拥有的数据 库及其所存储的数据规模增长更快一个中等规模企业每天要产生1 0 0 m b 以 上的商业数据美国政府部门的一个典型大数据库每天要接收约5 t b 数据 量在科研方面，以美国宇航局的数据库为例，每天从卫星下载的数据量就达 3 t b , - - 4 t b 之多，而为了研究的需要，这些数据要保存七年之久9 0 年代互联 网的发展与普及，使整个世界互联形成一个小小的地球村，人们可以跨越时空， 在网上交换信息和协作工作这样展现在人们砸前的已不是局限于本部门、本 单位和本行业的庞大数据库，而是浩瀚无垠的信息海洋在这个被称之为信息 爆炸的时代，信息过量几乎成为人人都需要面对的问题由于海量数据的复杂 性和数据处理的滞后性，人们陷入了“数据丰富，但知识贫乏”的困境这些 大量数据的背后，隐藏了很多具有决策意义的信息，如何及时得到这些有用的 知识? 如何才能不被信息的汪洋大海所淹没，提高信息利用率呢? 面对这一严 竣挑战，数据挖掘技术应运而生 数据挖掘( d a t am i n i n g ) 是从存放在数据库、数据仓库或其它信息库中 的大量数据中挖掘有趣知识的过程【删它已经引起了国内外学术界和工商界 广泛的关注通过数据挖掘，有价值的知识、规则或高层次的信息就能从数据 库的相关数据集合中抽取出来，并从不同角度展示给用户 特别需要指出的是，数据挖掘技术从一开始就是面向应用的它不仅是面 向特定数据库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏 西南交通大学硕士研究生学位论文第2 页 观的统计、分析、综合和推理，以试图发现事件问的相互联系，指导实际问题 的求解，甚至利用已有的数据对未来的活动进行预测这样一来，就把人们对 数据的应用，从低层次的查询操作，提高到为各级经营决策者提供决策支持这 种需求驱动力，比数据库查询更为强大 从上面的叙述可以看出：数据挖掘研究和探索的内容是极其丰富和具有挑 战性的我们正是在这样的背景下，开展相关研究工作的 1 1 2 数据挖掘面临的挑战 经过近二十年的发展，数据挖掘在研究和应用方面取得丰硕的成果，但同 时也面临着以下各方面的挑战 1 数据挖掘结果的表示和显示 发现的知识应当用高级语言、可视化表示形式或其它表示形式表示，这样 能够使得知识易于理解，可以直接被人使用在交互的数据挖掘系统中，这一 点尤为重要 2 处理噪音和不完备数据 存放在数据库中的数据可能含有噪音或不完备的数据对象这些对象会影 响分析过程，导致数据与所构造的知识模型过分适应其结果是，所发现的模 式的精确性可能很差于是我们迫切需要能够处理噪音和不完备数据的清理分 析方法 3 并行、分布和增量挖掘算法 许多数据库的大容量、数据的广泛分布和一些数据挖掘算法的计算复杂性 是促使开发并行和分布式数据挖掘算法的因素此外，利用已有的信息可以提 高挖掘效率导致了对增量数据挖掘算法的需要将增量算法与数据库更新结合 在一起，就不必重新挖掘全部数据这种算法能渐增地进行知识更新，修正和 加强先前业已发现的知识 4 复杂的数据类型的处理 数据库中可能包含复杂的数据对象，比如：超文本和多媒体数据、空间数 据或时间数据等由于数据类型的多样性和数据挖掘的目标不同，所以指望一 个算法能挖掘所有类型的数据是不现实的这样，对于不同类型的数据，我们 就需要有不同的数据挖掘算法 西南交通大学硕士研究生学位论文第3 页 1 2 分类挖掘 分类是数据挖掘中的一项非常重要的任务，目前在商业上应用很多，也一 直是数据挖掘领域的研究热点之一在从大规模数据库获得知识的过程中必然 涉及到数据分类问题所谓分类，就是根据确定的概念外延导出概念的内涵， 即描述、区分数据类的模型或者分类函数，以便能够用模型或函数预测那些类 标记尚未可知的对象，以便区分新的概念外延这里导出的模型或分类函数是 基于对类标记已知的训练数据集的分析，因此，分类是一种有类标记指导的学 习方法1 下面介绍一些与本论文相关的分类方法 1 判定树归纳 判定树归纳的基本算法是贪心算法，它采用自顶向下递归的划分控制方式 构造判定树，如j i lq u i n l a n 提出的基于信息熵的经典分类算法i d 3 t 2 1 、c 4 5 t l l 和c 5 0 1 6 5 1 下面是构造判定树的一般性描述： ( 1 ) 开始时是一个训练集和空树，接下去对当前结点应用该结点的测试将 其划分 ( 2 ) 如果所有的当前结点的训练样本属于同一个类别，创建一个带有该类 的标签的叶子结点并停止 ( 3 ) 否则，使用最优度量计算每一个集合的每一个可能的划分 ( 4 ) 选择最优划分作为当前结点的测试创建与该划分的不同输出数同样 多的子结点 ( 5 ) 使用该划分的输出标注父结点和子结点之间的边并使用该划分把训 练数据划分到子结点中 ( 6 ) 把子结点作为当前结点，循环进行2 5 步骤，直到不存在可以划分的 结点为止 2 粗糙集 、 粗糙集是一种处理不确定性问题的强有力工具其主要思想是在保持分类 能力不变的情况下，通过知识约简，推导出概念的分类规则，从而获得规则知 识它直接从给定的数据样本出发，通过不可区分关系和等价类划分所确定的 西南交通大学硕士研究生学位论文第4 页 问题的近似域，从而找到隐含在数据中的内在规律粗糙集可以用于分类 2 9 1 ， 可以根据分类任务评估每个属性的贡献或意义l 卿，还可以作为属性选择的依 据，如m b e y n o n 提出的基于属性约简原理的分类算法1 6 3 1 ，j w 西提出的基于 粗糙集选取分裂属性的判定树构造法【卯l ，苗夺谦的多变量判定树构造法1 6 l 】 3 云分类 在数据挖掘与知识发现的研究中，不能只注重对各种挖掘算法的研究，而 忽视对知识表达、定性定量相互转换等重要问题的考虑，忽略用户和领域专家 对数据挖掘的指导作用因而，李德毅院士在传统模糊数学和概率统计的基础 上提出了定性定量的互换模型云模型，它把自然语言中的模糊性和随机性 有机地综合在一起，实现了定性语言值与定量数值之间的自然转换 云分类的基本思想就是采用云变换和基于泛概念树的概念跃升技术来降 低分类复杂度 4 4 1 文献【5 6 ，6 2 】先利用云变换对连续型属性进行离散化，然后 将连续型属性的基本概念提升到合适的概念层次上，接着根据所得的概念集， 使用极大判定法对连续属性值进行软划分，最后借助于i d 3 算法构造出判定 树 1 3 研究内容 本文在分析、归类现有分类挖掘研究成果的基础上，对云模型和粗糙集在 分类挖掘中的应用进行了系统研究，主要包括以下一些内容： 1 提出粗糙集扩展模型中概念的上下近似的增量更新方法和提取规则的 方法在给出租糙集基本概念的基础上，详细讨论了基于特性关系的粗糙集扩 展模型，深入研究了特性关系下粗糙集扩展模型中概念的上下近似的动态增量 更新方法并通过系列实验对该方法做了性能分析，结果表明该方法确实可以 有效地动态支持属性推广和提取规则( 详见第二章) 2 云模型的分析与讨论在介绍云模型基本概念的基础上，对云模型的 不确定性原理机制进行了讨论，对正态云模型的数字特征的含义及相互关系等 问题做了深入地介绍，对用于离散化连续数据的云变换算法进行了深入讨论 ( 详见第三章) 3 提出基于云模型和粗糙集扩展模型的一个新的判定树算法d t c c r s ， 西南交通大学硕士研究生学位论文第5 页 该算法首先利用云变换离散化连续属性，再选择能够使得特性关系下加权平均 粗糙度最小的属性作为当前结点的分裂属性，然后递归下去直至判定树终止生 长最后。通过实验说明了该算法具有妥善处理空缺值、合理离散连续属性等 优点与c 5 0 相比，该算法得到的判定树不但结构简单清楚、分类准确率高， 而且分类规则也容易理解( 详见第四章) 1 4 本章小结 本章介绍了论文的选题依据、研究背景以及主要研究内容数据挖掘作为 二十一世纪信息处理的骨干技术之一，正以一种全新的概念改变着我们利用数 据的方式经过十几年的研究和实践，数据挖掘已经融合了许多学科的最新研 究成果而形成独具特色的一个研究领域目前的数据挖掘正处于蓬勃发展时 期可以预见，在今后各类数据库的深层次运用中，数据挖掘将会得到充分的 发展分类是数据挖掘研究中的一个重要分支，有关分类的研究也将继续成为 研究人员关注的热点 西南交通大学硕士研究生学位论文第6 页 第2 章粗糙集扩展模型中概念上下近似动态更新方 法和规则提取 粗糙集是一种处理不确定和含糊信息的数学方法如何有效地利用粗糙集 来更新知识是数据挖掘中一个热点研究课题在实际信息系统中，数据缺失是 很常见传统的粗糙集模型无法处理数据缺失问题基于特性关系的粗糙集模 型扩展了传统的粗糙集模型，可以有效处理数据缺失本章主要研究当属性集 变化时，特性关系下粗糙集扩展模型中概念的上下近似动态更新方法和规则提 取主要内容安排如下：2 1 节是引言部分，介绍了研究内容的背景；2 2 节给 出了粗糙集的基本概念，详细介绍了基于特性关系的粗糙集扩展模型等预备知 识；2 3 节深入研究了特性关系下粗糙集中概念的上下近似的动态增量更新方 法；2 4 节描述了如何在特性关系下的粗糙集扩展模型中进行规则提取；在2 5 节，通过系列实验对该方法做了性能分析；最后，在2 6 节利用上述结果，设 计了一套增量式更新上下近似和提取决策规则的软件系统 2 1 引言 2 0 世纪8 0 年代，波兰科学家z p a w l a k 基于边界区域的思想提出了粗糙 集的概念，成为粗糙集理论的奠基人 2 5 1 粗糙集直接从给定的数据样本出发， 通过等价类划分来确定问题的近似域，以此找到隐含在数据中的内在规律现 在许多基于粗糙集的方法都已经被成功地应用到数据挖掘的方向上1 2 6 3 蜘比 如：j f p e t e r s 等将租糙集方法用来分类夏天恶劣天气引起的飓风事件【2 9 】j g d y 等使用基于近似域的粗糙集方法来聚类w e b 访问日志的w c b 事务f 2 引利 用这些方法，用户就能够有效的挖掘w e b 日志记录以发现最频繁的网页访问 模式现实中，数据的体积在以不可预料的速度增长( 包括对象的个数和属性 的数量) 例如，在基因信息数据库中，可能包含了待考察对象的上千个特征； 在技术应用领域，来自于不同数据源的数据可能会被连接在一起，从而导致属 西南交通大学硕士研究生学位论文第7 页 性数量的激增p o 正是基于这些考虑，增量更新知识成为了数据挖掘中最流 行的主题之一文献 2 6 。3 1 详细讨论了在传统的粗糙集理论中，如何利用增 量挖掘算法有效地学习新的分类规则文献 3 2 】主要研究了基于粗糙集和规则 树的增量知识获取算法但以上这些方法都是基于完备信息系统的而在许多 现实应用中，信息系统存在缺失数据是很常见的于是在面临不完备信息系统 ( i i s ) 的时候，传统粗糙集理论的不可区分关系受到了限制为了能够直接 处理不完备数据，m k r y s z k i e w i c z 在【3 3 】中对粗糙集进行了扩展，提出了容差 关系该方法的核心思想是将空缺值考虑成为“一切皆有可能”的值，文献【3 4 】 中，一个针对s 动态属性集，以容差关系为基础，增量更新概念上下近似的 方法被提出，另外基于该方法的分类规则挖掘算法也在文献 3 5 】中得以研究 最近，j w g r z y m a l a - b u s s e 在丢失值和“不关心值”共存于信息系统的 假设条件下，对粗糙集做了新的扩展，提出了特性关系粗糙集模型比起以前 的方法，这个扩展更好地反映了璐的实际条件文献【3 6 】详细描述了一个可 以将丢失值和“不关心值”作为输入数据的规则归纳算法本章我们讨论在 s 中，当属性集随着时间变化时，如何更新一个概念的上下近似，以及如何 提取决策规则 2 2 预备知识 2 2 1 粗糙集理论的基本概念 下面简单叙述本论文涉及到的粗糙集及扩展模型的基本概念和结论 定义2 - l 【2 5 】信息系统的一般表示形式为：s = ( u ，彳) ，其中，c ，是由 对象组成的非空有限集合，a = c u d 为属性集合，这里的c 为条件属性，d 为决策属性并且c n d = a 对于v 4 a 都有一个a 的取值集合吒与之关联， 圪被称为口的域 容易看出，一个属性对应一个等价关系，一个信息系统可以看作是定义的 一族等价关系，即知识库 定义2 - 2 2 5 】令b e a 是一个属性子集，只是( ，上的一个等价关系当x 为r 的某些等价类的并时，称工是只可定义的( r - d e f i n a b l e ) ，否则称石是r 不可定义的( r - u n d e f m a b l e ) r 可定义集称作为r 精确集，屁不可定义集称 西南交通大学硕士研究生学位论文第8 页 为r 租糙集 粗糙集可以用两个精确集( 即下近似和上近似) 来描述 定义2 - 3 2 5 】包含在x 中的最大可定义集称为z 的r 下近似( l o w e r a p p r o x i m a t i o n ) ： 墨) = 扛【，l b l j l x ( 2 1 ) 包含z 的最小可定义集称为x 的r 上近似( u p p 盯a p p r o x i m a t i o n ) ： 页似) = b c ，l b 】 n x 妒( 2 2 ) x 的边晃域： 只= i 一星 ( 2 3 ) 星) 表示在知识足下( ，中所有一定能归入x 的元素的集合，页( ) 表示 在知识r 下【，中可能归入x 的元素的集合e 伍) 是表示在知识足下u 中既 不能肯定归入x 也不能肯定归入一x 的元素的集合 1 、t _ _ j r 、 丫 乒 ，一 | l ， i 图2 1 粗糙集基本概念示意图 r x x r x 定义2 _ 4 【“】在信息系统s = ( 【，一) 中，如果设z u ，口a ， ( 幻= 耐馑( x ) ) ，耐伍( z ) ) 是x 在集合曰上的精确度( o ( 柳1 ) ，那 么关于集合b 的加权平均粗糙度定义为： 西南交通大学硕士研究生学位论文第9 页 声( 曰) = l 一( 哆。( ) ) ( 2 - 4 ) 其中- ，表示决策属性的第，个决策类别，= l ，2 ，掰，胁是决策类别的数 目；表示决策属性的第，个决策类别集合；哟表示x j 在整个论域( ，上所占 的比例哆= 删( 乃) c a r d ( u ) 2 2 2 特性关系下的粗糙集扩展模型 定义2 5 【3 7 在信息系统s = ( 以彳) 中，如果存在空缺值4 ( 力，其中口a ， 工u 。则称s 为不完备信息系统( s ) 系统中所有空缺值可以用“? ”或 “木”表示，其中，“7 ”表示缺失值，“搴”表示不关心的值 在【3 7 】中，j w g r z y m a l a - b u s s e 提出了特征集和特性关系的概念，特征集 和特性关系可以用下面的属性值对的思想来定义 定义2 - 6 【3 7 】在不完备信息系统s = ( 【，4 ) 中，令b 是属性， ，是b 的一 个属性取值，t = ( 6 ，v ) 是属性值对，如果v ? 和乖，那么可以按照 【t 】= 仁c ，i b ( x ) = v ) 形式定义i t 】，如果存在一个x u 使得b ( x ) = ? ，那么对于 b 的任意属性值，( v ? 和奉) ，都有工叠 ( 6 ，”】；如果存在一个j e u 使得 6 ( 工) = ，那么对于b 的任意属性值，( v ? 和宰) ，都有x 【( 6 ，例 定义2 7 【3 7 】在不完备信息系统s = 缈，彳) 中，令占e 彳是一个属性子集， 工u ，那么特征集巧( x ) 被定义为如下形式： 巧= n ( 6 ，“曲) 】 ( 2 - 5 ) 6 t j 在有了特征集的概念以后，下面我们给出特性关系的定义 定义2 - 8 3 8 】在不完备信息系统s = ( u ，4 ) 中，令b e a 是一个属性子集， x , y e u ，那么特性关系g 被定义为如下形式： ( ) ，) c ：亨y ，；( 曲( 2 6 ) 显然，特性关系只具有自反性，而并不满足对称性和传递性 西南交通大学硕士研究生学位论文第1 0 页 对于不完备信思系统中的租糙集，我们仍然可以用两个精确集，即特性关 系下粗糙集的下近似和上近似来描述 定义2 - 9 【3 8 】特性关系意义下，相对于属性子集占而言，x 的下近似和 上近似分别是： 群= u 巧i 工e 石，巧o ) x ( 2 - 7 ) 霹= u 巧( 力i 工e x ，( 力n x a = u 巧( 工) i 工e x ( 2 - 8 ) 可以类似地定义彳的边界域： 色( x ) = 群一霹 ( 2 - 9 ) 定义2 一l o 3 8 】特性关系意义下，相对于属性子集丑而言，x 的下边界集 ( l o w e rb o u n d a r y ) 和上边界集( u p p e rb o u n d a r y ) 分别是； 硝；= x x ； ( 2 1 0 ) 鲥：= 雕一肖 ( 2 - 1 1 ) 类似地，我们也可以定义不完备信息系统中的加权平均粗糙度 定义2 - 1 l 在基于特性关系的不完备信息系统s = 缈，4 ) 中，如果设 x g u ，口a ，( 幻= 翻耐( 矸) 耐( 硭) 是z 在集合曰上的精确度 ( o u 。( j ，) 1 ) ，那么关于集合丑的加权平均粗糙度定义为： ( 却= l 一( 哆( 乃) ) ( 2 1 2 ) j i 其中，表示决策属性的第j 个决策类别- - 1 ，2 ，m ，m 是决策类别的数 目；t 表示决策属性的第，个决策类别集合；q 表示乃在整个论域( ，上所占 的比例q = r d ( x j ) 阳埘) 西南交通大学硕士研究生学位论文第”页 2 3 粗糙集扩展模型中概念的上下近似的增量更新 在不完备信息系统中，我们提出了特性关系下粗糙集扩展模型的增量更新 上下近似的方法，即：利用下面列举的性质，借助于原始信息，可以有效的增 量更新概念的上下近似p 们 设x 是u 的一个子集，称为是一个概念 引理2 - 1 【3 8 】设p q 4 ，则x c e z ，霹j 引理2 - 2 【3 8 】设p q e a ，则郜m 筝，铲e 酗鼍 性质2 - 1 【3 8 】设p ，q 彳和q n p = a ，那么x = 母u 砭u y ，这里 】，= d m 譬n m 莒i n 。刚口 o ) e 性质2 - 2 【3 8 】设q c p c = 4 那么z 岛一- - n p c 一峨，这里 从岛= 臼n 。脚从： i n 。蛐j 仁椰 性质2 - 3 3 8 】设p , q g a 和q n p = a ，那么硭垤= x u ( 蛾一z ) ，这里 z = x ga 埘 j 口站in 。 垃 ( 功量n 。，l j 口x ? 性质2 - 4 3 8 】设q c p c _ a 那么样屯= 群u z 。，这里 z 。= 协en # e p - o 砧in 。呻巧i ( 力cn 。m 砧 以上各性质的证明过程请参见论文【3 8 】 2 4 规则提取 利用对象集以及它们对应的上下近似，可以提取出确定规则和可能规则 西南交通大学硕士研究生学位论文第12 页 定义2 1 2 在特性关系的意义下，如果相对于属性子集口而言，对象集x 的上下近似分别是群和，那么x 的确定规则集和可能规则集分别定义为 霹和群一霹，即，在下近似中导出的规则是确定规则，在边界域中导出的 规则是可能规则 下面给出一个具体的例子，假设对象集为x = l ，2 ，5 ) ( 相当于决策属性 c l a s s = i 时的一个分类) ，数据表如下： 表2 1 演示规则提取功能的数据表 i d a 1a 2a 3c l a s s 1lo?l 2ll l l 3 07 o 4ool0 51lo1 6 1olo 经计算知：x 的下近似和上近似分别为 l ，2 ) 和 l ，2 ，5 那么由定义2 1 2 知道： a i = i ，a 2 = 0 ，a 3 - - ? ，c l a s s = i 是确定规则； a i = i ，a 2 = l ，a 3 = l ，c l a s s = l 是确定规则； a i = i 。a 2 = i ，a 3 = 0 ，c l a s s - l 是可能规则 2 5 实验验证 2 5 1 实验数据特性描述 本章所用的实验数据均来自于u c i ( w w w i t s u c i 州c a r n m l r c p o s i t o r y h t m l ) 我们选择了9 个数据集作为实验数据实验数据的基本 特性如表2 - 2 所示 西南交通大学硕士研究生学位论文第13 页 2 5 2 实验环境 奔腾p c 机，c p u 为4 0 0 m i - i z 、主存5 1 2 m 、操作系统w i n d o w s2 0 0 0 ，数 据库采用s q ls e r v e r 2 0 0 0 ，所有程序使用饼开发 表2 - 2 实验数据特性描述表 数据集名称记录条件属? 值值 总数性数目 s o y b e a n 6 8 33 5有有 b r e a s t - c a n c e r2 8 69 有 原没有，随机替换 a g a r c u s - l e o i o t a 1 5 0 02 2有原没有，随机替换 b u l y a 3 4 5 6原没有，随机替换原没有，随机替换 c 拭 6 9 01 5有原没有，随机替换 h a y e s - r o t h 1 3 25原没有。随机替换原没有，随机替换 h e a r t - d i s e a s e5 71 5有原没有，随机替换 l u n g - c a n e , e r 3 2 5 6有 原没有，随机替换 s p o n g ei n f o 7 64 4 有 原没有，随机替换 2 5 3 实验结果与分析 1 上下近似中所含对象个数与相应的边界集中所含对象个数的比较 一般说来，数据集的大小决定了计算速度，越大的数据集将会消耗越多的 计算时间，而本章提出的方法实质上是利用了边界集来间接计算相应的上下近 似，以期望减少消耗时间因此在第一个实验里，我们将上下近似中所含的对 象个数与相应的边界集中所含的对象个数做比较实验结果表明：边界集中的 对象数量远远少于相应的上下近似中的对象的数量这里选择的是s o y b e 锄 数据库原因在于它含有两个属性值：一个是“d n a ”( 可看作丢失值) ，另 一个是”( o - j 看作不关心的值) 该数据集一共有3 5 个条件属性，一个决 策属性，6 8 3 条记录，这6 8 3 条记录共分为1 9 个类别，即d i a p o r t h e - s t e m - c a n k e r , c h a r c o a l - r o t , r h i z o c t o n i a - r o o t - r o t , p h y t o p h t h o r a - r o t , b r o w n s t e m - r o t ， p o w - d e r y - m i l d e w ，d o w n y - m i l d e w ，b r o w n - s p o t , b a c t e r i a l - b l i g h t ，b a c t e r i a l - p u s t u l e ， 西南交通大学硕士研究生学位论文第1 4 页 p u r p l e - s e e d - s t a i n ，a n t l l r a c n o s e , p h y l l o s t i c t a - l e a f - s p o t , a l t e r n a r i a l e a f - s p o t ， f l o g - e y e l e a f - s p o t , d i a - p o r t h e , - p o d - & - s t e m - b l i g h t , c y s t n e m a t o d e ，2 - 4 d i n j u r y ， h e r b i c i d e 嘲i 町在实验中，我们分别用x 1 ，x 1 9 来表示这1 9 个类别 我们在数据库中任意选择1 3 个属性，即b = d a t e ，p l a n ts t a n d ，p r e c i p ，t e m p ， h a i l ，c r o p _ h i s t ，s e v e r i t y , s e e d _ t r o t , s t e m _ c a n k e r s ，c a n k e r _ l e s i o n , s c l e r o t i a , h i t _ p o d s ，s e e d 表2 3 记录了特性关系下，相对于b 的1 9 个类别的上下近 似和边界集中所含对象的数量 表2 - 31 9 个类别的上下近似和边界集中所包含的对象数量 c 1 a 8 $ e sn 1n 2 n 3 n 4 z l2 81 684 x 22 02 0 o o 32 0 2 0oo x 49 38 553 z 54 54 2l2 x 6 2 21 921 x 1 2 l1 92l 石8 9 68 448 x 92 l1 9il z 1 0 2 31 832 x 1 12 02 0oo z 1 2 4 44 4oo x 1 32 02 0oo x 1 4 9 9 8 289 x 1 5 1 8 596 x 1 61 8936 石1 71 41 4oo x 1 8 6 8 3o6 6 71 6 x 1 9 2 201 48 西南交通大学硕士研究生学位论文第1 5 页 其中， n i ：上近似中所含对象的数量； n 2 ：下近似中所含对象的数量； n 3 ：上边界集所含对象的数量； n 4 ：下边乔集所含对象的数量 从表2 - 3 中，我们可以得到以下结果： ( 1 ) 在绝大多数的类别中( 有1 5 个类别) ，上下近似和边界集的对象数 量之问有较大的差距 ( 2 ) 在x 1 ，x 1 6 ( 即d i a p o r t h e s t e m - c a n k e r , d i a - p o r t h e p o d - & s t e m - b l i g h t ) 这两个类别中，边界集中对象的数量几乎只有上下近似中对象数量的一半 ( 3 ) 只有在x 1 8 ，x 1 9 ( 即2 - 4 七- i n j u r y , h e r b i c i d e - i n j u r y ) 两个类中t 上下 近似和边界集之间的对象数量差距最小 2 计算上下近似时的时间性能比较 为了验证本文提出的增量更新方法( 记作：d c r s a ) 的有效性，我们继 续了第二个实验：使用直接计算粗糙集中概念的上下近似的方法( 记作： d c r s a ) 与其做时间性能的比较在这里使用了全部9 个数据集，它们分别 是( s o y b e a n ，b r e a s t - c a n c e r ，a g a r i c u s - l e p i o t a ，b u p a , 弧，h a y e s - r o t h ，h e a r t - d i 8 e a s e ， l u n g - c a n c e r ，s p o n g e _ i n f o ) 以下的实验结果表明：在不完备信息系统中， i d c r s a 确实比d c r s a 的性能要高，前者所耗费的计算时间要比后者少得 多我们将实验分成三种情况 ( 1 ) 当原始属性集的属性增加时，d c r s a 与i d c r s a 的性能比较 设p 为原始属性集。q 为欲增加的属性集，以下计算p u q 关于这九个数 据集的某些类别的上下近似 西南交通大学硕士研究生学位论文第1 6 页 d 虹a s e tc l a s sd c r s am c r s a s o 叫o e a n c l m s s = v u r v l c - s c c d - _ s t a i n 1 5 60 b r e a s t - c a n c e rc l a s s = n o 嗽u 唧e v e 鹏6 8l a g a r i c u s l e p i o 诅 c i a s f = e9 7 3 b u d a 盛a n u n a g t = g a m m a - g l u t a m y l 5 50 c r xa 1 6 = +8 5o h a y c s - r o t hc l a s s = g a n m m - g l u t a m y i 6 7l h e a r t - d i s e a s e x h y p o f f i l 1 3 1o l u n g - c a n c e rc l a s s y 2 1 4 62 s p o n g ei n f o e p s e u d o r a i c e s = n o1 6 54 表2 - 5 计算上近似时d c r s a 与i d c r s a 的时间性能比较( 秒) d a t a s e tc l a s sd c r s am l c r s a s o y b e a nc l a s s - - - p u r p l e - s e e d - s t a i n 1 5 62 6 b r e a s t - c a n c e rc l a s s = n o - r e c t t r r e n c e - e v e n t s7 16 a g a r i c u s l e p i o t a c l a s s = e9 82 b u p a g a m m a g t = g a m m a - g l u t a m y l 5 5o c r xa 1 6 = 十8 5l h a y e s - r o t h c l a s s = g a m m a g l u t t o n y l 6 73 h d r b d i s e a s e h y p o = l 1 3 11 l u n g - c a n c e r c l a s s - - - - 21 4 62 s 1 3 0 n g ei n f op p s e u d o r a i c e s = n 0 1 6 57 对于s o y b e