（计算机应用技术专业论文）rough集理论及其在数据挖掘中的应用.pdf

摘要 本文研究的内容集中在r o u g h 集理论，以及r o u g h 集理论中的粒度计算理论 在数据挖掘领域中的若干应用。r o u 。g h 集理论是一种处理不确定性知识的数学工 具，围绕着数据挖掘领域中的问题，本文利用r o u g h 集理论与粒度计算理论，提 出了若干解决方案。本文对数据挖掘及r o u g h 集理论进行了基本概述，完成的主 要工作包括： 1 针对以往的基于r o u g h 集理论发现知识方法的绝对化，以及推出的规则过于肯 定或过于否定，提出了基于可信度函数的知识量化方法。 2 知识约简是在决策表上进行的，而决策表一致与否在约简之前要加以判断并进 行区分。本文提出了基于条件概率的对非一致决策表的划分，在将属性分为条 件属性和决策属性的基础上，把每个个体的条件属性作为条件，决策属性作为 在该条件下要发生的事件，然后通过对概率的值来判断该个体是属于一致决策 表的，还是非一致决策表的。这种方法避免了以往对非一致决策表划分时要进 行等价类的划分，结合交运算以及求其正域，因此起到了简化的作用。 3 提出了基于二进制粒度计算的量化方法。首先，按照决策属性值对决策表进行 重新整理，决策值相同的个体放在一起；建立一个二进制表；根据决策表推出 规则，再由给出的可信度值计算所需求满足的个体的个数；然后按照规则所给 出的属性值上的二进制数进行a n d 运算，通过判断“1 ”出现的个数来进行判 断该规则的准确性。 4 在建立了粒与二进制数的对应关系的基础上，定义了粒度包含和粒度基数，并 给出了相应的属性值约简算法。该方法通过二进制数的a n d 运算及粒度包含 来判断哪个个体的哪个属性可被约去，不仅速度快，而且效率高，还有利于在 计算机上实现。 最后，对全文进行了概括性总结，并指出了有待进一步研究和完善的问题。 关键词：r o u g h 集，数据挖掘，粒度计算，知识约简，属性值约简 a b s t r a c t t h ec o n t e n t so ft h i sp a p e rc o n c e n t r a t eo nt h er o u g hs e tt h e o r ya n d a p p l i c a t i o n so fi t sg r a n u l a rt h e o r yi nd a t am i n i n g r o u g hs e tt h e o r yi s am a t h e m a t i c a lt o o l ，w h i c hd e a l sw i t hi n c o m p l e t ek n o w l e d g e ，a n dd e a l sw i t h t h ep r o b l e m si nt h ef i e l d so fd a t am i n i n g t h i sp a p e rp r o m o t e ss e v e r a l p r o g r a m so fs o l u t i o nb a s e do ng r a n u l a rt h e o r ya n ds u m m a r yo fd a t am i n i n g a n dr o u g hs e tt h e o r y ，a n da c c o m p l i s h i n gs o m em a i nw o r ka sf o l l o w s ： 1 f o rt h ea b s o l u t e n e s so ft h em e t h o do fd i s c o v e r i n gk n o w l e d g eb a s e do nr o u g h s e t ，a n df o rt h en e g a t i o na n da f f i r m a t i o no ft h er u l e s ，t h e r ep r o m o t et h e m e t h o do fq u a n t i t a t i r ek n o w l e d g eb a s e do nt h ec o n f i d e n c ef u n c t i o n 2 w er e d u c et h ek n o w l e d g eo nt h ed e c i s i o nt a b l e ，a n dw es h o u l dt e l li fi t i si d e n t i c a la n dd i f f e r e n t i a t ei t i nt h i sp a p e r ，t h e r e p r o m o t et h e d i f f e r e n t i a t i o no fi n c o n s i s t e n td e c i s i o nt a b l eb a s e do nt h ec o n d i t i o n a l p r o b a b i l i t y ，o nt h eb a s eo fd i f f e r e n t i a t i n ga t t r i b u t e si n t oc o n d i t i o n a t t r i b u t e sa n dd e c i s i o na t t r i b u t e s ，t a k et h ed e e i s i o na t t r i b u t e so fe a c h o b j e c ta sc o n d i t i o n ，a n dt a k et h ed e c i s i o na t t r i b u t e sa st h ei n s t a n c ew h i c h h a p p e n so nt h i sc o n d i t i o n ，a n dt e l lt h eo b j e c tb yt h ev a l u eo fi t s p r o b a b i l i t yi f i tb e l o n g st ot h ec o n s i s t e n tt a b l eo ri n c o n s i s t e n td e c i s i o n t a b l e t h i sm e t h o di sm o r ec o n c i s et h a nb e f o r e 3 t h e r ep r o m o t e st h eq u a n t i t a t i v em e t h o db a s e do nt h eb i n a r yg r a n u l a r c o m p u t a t i o n f i r s t l y ，a c c o r d i n gt ot h ev a l u eo fd e c i s i o na t t r i b u t e ，p u t t h ed e c i s i o nt a b l ei no r d e r ，a n dp u tt h eo b j e c t st o g e t h e rb yt h es a m ev a l u e ： c o n d u c tab i n a r yt a b l e ：a c c o r d i n gt ot h ed e c i s i o nt a b l e ，w ec a nd e d u c et h e r u l e s ，f u r t h e rm o r e ，b yt h ev a l u eo fc o n f i d e n c ew ec a nc o m p u t et h en u m b e r s a t i s f y i n gt h ec o m p u t a t i o n ：a f t e r w a r d sa c c o r d i n gt ot h er u l e so ft h e a t t r i b u t ev a l u eo fb i n a r y 。w eh a v e “a n d ”b e t w e e nn u m b e r s a n dw ec a nt e l l t h ea c c u r a c yo ft h er u l eb yt h en u m b e ro f “1 ” 4 o nt h eb a s eo fc o n d u c t i n gt h er e l a t i o nb e t w e e nt h eg r a n u l a ra n db i n a r y i | 一 n u m b e r ，t h ep a p e rd e f i n et h eg r a n u l a ri n c l u s i o na n dg r a n u l a rb a s i c ，a n d p r o m o t et h em e t h o do fr e d u c t i o no fa t t r i b u t e s t h i sm e t h o dt e l lw h i c ho b j e c t s h o u l dr e d u c ew h i c ha t t r i b u t eb yb i n a r y “a n d ”a n dg r a n u l a ri n c l u s i o n ， n o to n l yi t sv e l o c i t yi sr a p i d ，b u ta l s oi t se f f i c i e n c yi sh i g h ，a n di t i sc o n v e n i e n tt or e a l i z ei to nt h ec o m p u t e r f i n a l l y ，t h e r ei sg e n e r a lc o n c l u s i o nf o rt h ep a p e r ，a n dp r o m o t i n gt h e p r o b l e m sw h i c hw o u l db ec o m p l e t e da n ds t u d i e df u r t h e r k e y w o r d ：r o u g hs e t ，d a t am i n i n g ，g r a n u l a rc o m p u t a t i o n ，k n o w l e d g er e d u c t i o n ， r e d u c t i o no ft h ev a l u eo fa t t r i b u t e s i l l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得鞍山科技大学或其它教育机构的学位或证书而使用过的材料，与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 签名：塑是日期：坌2 芝! 占：。口 关于论文使用授权的说明 本人完全了解鞍山科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅：学校 可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手 段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：益皇导师签名： g 垣 日期：迦：叁少 鞍山科技大学硕士论文l 引言 1 引言 1 1 数据挖掘与数据库知识发现概述 随着数据库和网络等技术的迅猛发展，数据产生和收集的能力已经迅速提 高，大量的数据储存在数据库和数据仓库中，数据使用者己被淹没在数据和信 息的汪洋大海中。我们需要用更新的、更有效的手段对各种大量数据进行挖掘以 发挥其潜能。数据挖掘正是在这样的应用需求环境下产生并迅速发展起来的，它 的出现为自动和智能地把海量的数据转化为有用的信息和知识提供了手段“1 。 数据库知识发现( k d d ，k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 简称为知识 发现是指从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的处 理过程。数据挖掘( d m ，d a t am i n i n g ) 简单地说就是从大量数据中“挖 掘”或提取知识。一种比较公认的定义是：数据挖掘是指从数据库的大量数据中 揭示出隐含的、先前未知的、潜在有用的信息的非平凡过程，这是由 g p i a t e t s k y s p a p i o r ，w j f r a w l a y 等人提出的。有些人认为数据挖掘是数据库 知识发现过程的一个关键步骤。 数据库知识发现过程的步骤如图1 1 所示 图1 1 一般数据库知识发现过程的步骤 从上述步骤可以看出，数据挖掘只是整个数据库知识发现过程的一个步骤。 然而，在大多数场合，采用广义的数据挖掘的观点，即数据挖掘是指从存放在数 据库、数据仓库以及其他信息库中的大量数据中挖掘出有价值的知识的过程。由 上述可知，数据挖掘是知识发现整个过程中最本质、也是最重要的步骤，因此人 鞍山科技大学硕士论文 1 引言 们也往往将知识发现和数据挖掘作同义语使用而不加区分。这样我们可以不加区 分地使用数据挖掘和数据库知识发现这两个术语。基于这种观点，典型的数据挖 掘系统如图1 2 。 数 图1 2 典型的数据挖掘系统的框架 数据库或数据仓库服务器，存储着用户将要挖掘的，所感兴趣的数据。知识 库是领域知识的一个应用，它用于引导搜索或评估挖掘的结果模式是否有意义， 是知识的不同属性或属性值进行不同层次的抽象。数据挖掘引擎是数据挖掘系统 所必不可少的部分，理想的是由一系列面向任务的功能模块组成，如：特征分析、 相关分析、分类、评估以及偏差分析。模式评估模块运用各种兴趣尺度对得到的 模式进行评估同时还与数据挖掘模块进行交互，使挖掘的方向集中在感兴趣的模 式上。用户的图形界面接口是用户和数据挖掘系统交互的接口。允许用户指定有 关参数的值，直接参与到数据挖掘的查询、搜索中。 鞍山科技大学硕士论文1 引言 1 2 用r o u g h 集来研究数据挖掘的背景和意义 1 2 1 背景 r o u g h 集理论是2 0 世纪8 0 年代由波兰科学家p a w l a k 提出。1 ，其主要思想就是在 保持分类能力不变的前提下，通过知识约简，导出概念的分类规则。它从一个新 的角度将知识定义为对论域的划分能力，并将其引入数学的等价关系来进行讨论， 从而为数据分析，特别是不精确、不完整数据分析提供了一套新的数学方法。 同时，r o u g h 集理论的特点是不需要预先给定问题外的任何先验信息，如某些 特征或属性的数量描述，具体的像统计学中的概率分布，模糊集理论中的隶属度 或隶属函数等，而是直接从给定问题出发，通过不可分辨关系和不可分辨类确定 问题的近似域，从而找出该问题中的内在规律。r o u g h 集理论同模糊集、神经网络、 证据理论等其它理论均成为不确定性计算的一个重要分支。r o u g h 集理论是根据目 前已有的给定问题的知识，将问题的论域进行划分，然后对划分后的每一个组成 部分确定其对某一概念的支持度，即肯定支持此概念或不支持此概念。 1 2 2r o u g h 集理论可作为数据挖掘方法的依据 r o u g h 集理论可作为数据挖掘方法的依据有：( 1 ) 数据挖掘研究的对象多为关 系型数据库，关系表可被作为r o u g h 集理论中的信息表或决策表，这给r o u g h 集方 法的应用带来极大的方便；( 2 ) r o u g h 集的约减理论可用于高维数据的预处理，以 去除冗余属性从而达到降维的目的；( 3 ) 现实世界中的规则有确定的，也有不确定 的。从数据库中挖掘不确定的知识，为数据挖掘提供了用武之地：( 4 ) 运用r o u g h 集方法得到的数据挖掘算法有利于并行执行，这可以极大地提高大规模数据库中 的数据挖掘的效率。 1 2 3r o u g h 集理论在数据挖掘中的应用要点 现实世界中数据的不完整、有噪声和不一致是很普遍的现象。在不完全信息 下的数据挖掘是一个困难的问题，但它在数据决策中是不可避免的。因为传统的 数据挖掘技术对数据的质量要求较高，只能在精确集下进行数据挖掘，如模糊集 鞍山科技大学硕士论文 1 引言 理论、证据理论和概率统计理论等，因需要数据的附加信息或先验知识( 难以得 到) ，有时在处理大量数据的数据库方面无能为力，不仅如此，对一些模糊信息的 数据需要进行改变后或抛弃之后才可以挖掘，这样很容易造成信息的丢失，而 r o u g h 集理论却可以对这一类信息进行挖掘，可以克服传统不确定处理方法的不 足，并且和它们有机结合，可望进一步增强对不确定、不完全信息的处理能力。 目前，成熟的关系数据库管理系统和新发展起来的数据仓库管理系统为r o u g h 集的 数据挖掘奠定了坚实的基础。 数据库中，将列元素看成属性( 条件属性和决策属性) 。等价关系r 定义为不同 个体在某个( 或几个) 属性上取值不同，这些满足等价关系的个体组成的集合称为 该等价关系尺的等价类。条件属性上的等价类e 和决策属性上的等价类r 2 _ 间有三种 情况：( 1 ) 下近似，y 包含e ：( 2 ) 上近似，y 和e 交非空；( 3 ) 无关，掰口e 交为空。 对下近似建立确定性规则，对上近似建立不确定性规则( 含可信度) ，无关情况不 存在规则。 1 2 4r o u g h 集在数据挖掘中的应用展望 r o u g h 集是数据挖掘的有效工具，具有坚实的理论基础。r o u g h 集理论自1 9 8 2 年p a w l a k 提出以来，已在许多领域得到了应用。但作为一种新事物，r o u g h 集在使 用中也遇到了许多困难。目前的有效途径有两条：一是r o u g h 集理论的拓展，如 z i a r k o 的变精度粗糙集模型；其次是r o u g h 集与其它方法的结合。基于r o u g h 集的 数据挖掘在下述方面有待深化：( 1 ) 高效约减算法，高效约减算法是r o u g h 集理论 应用于数据挖掘的基础，目前尚不存在一种非常有效的方法。因此，寻求快速的 约减算法及其增量版本仍然是主要研究方向之一；( 2 ) r o u g h 集和其它软计算方法 的进一步结合问题；( 3 ) r o u g h 集知识挖掘的递增算法，这实际上是一个二次数据 挖掘问题，即在过去已挖掘知识的基础上，修正或补充不合理的部分，以便适应 新的数据，而不是重新开始；( 4 ) r o u g h 集基本运算的并行算法及硬件实现，将大 幅度改善数据挖掘的效率；( 5 ) 扩大处理数据的范围：( 6 ) 现代信息系统具有分布 异构的特点，解决的办法之一是分解，即将用户提出的全局挖掘要求分解为不同 节点的子数据库挖掘要求，然后在各个节点上单独挖掘，最后集成【3 j 。 鞍山科技大学硕：i ：论文 1 引言 1 3 本文的组织结构 本文组织如下：第二章将介绍r o u g h 集的基本概念，在这一章中，提出了知识 量化的概念，并对非一致决策表提出了新的划分方法；第三章中详细地介绍了 r o u g h 集中的一些重要理论在数据挖掘中的应用，其中对粒度计算理论是概要介 绍，为下一章做了铺垫；第四章重点介绍了粒度计算的知识和应用于数据挖掘中 的相关理论，在这一章中，提出了基于二进制粒度计算的知识量化方法以及基于 二进制粒度对属性值约简的方法，并介绍了粒度计算在其他数据挖掘理论中的应 用；第五章是有关本论文的重点难点，以及总结和展望。 鞍山科技大学硕士论文 2r o u 曲集理论概述 2 r o u g h 集理论概述 2 1 r o u g h 集中的一些基本概念 r o u g h 集( r o u g hs e t 粗糙集) 理论是针对不确定性问题提出的，r o u g h 集方法与 传统的统计及模糊集方法不同的是：后者需要依赖先验知识对不确定性的定量描 述，如统计分析中的先验概率、模糊集理论中的模糊度等等；而前者只依赖数据 内部的知识，用数据之间的近似来表示知识的不确定性。用r o u g h 集理论来处理不 确定性问题的最大优点在于，它不需要关于数据的预先或附加的信息，而且容易 掌握和使用。 r o u g h 集方法属于数学方法，但又不同于数学中一般的集合概念。它从“知识” 的角度处理客观事物的不确定性，认为知识是将个体进行分类的能力，即将分类 与知识联系在一起；并且用一个术语“等价关系”r 来形式化地表示分类，这样 知识就可以理解为等价关系r 对论域u 的划分( 所得的u 中的子集称作基本概念或 范畴) 。它们的关系如图2 1 。 图2 1 知识与分类示意图 r o u g h 集理论是建立在分类机制的基础之上的，不可区分关系的概念是r o u g h 集理论的基础，并且r o u 曲集理论中的基本概念是其处理思想和算法的基础，下面 介绍几个主要概念。 鞍山科技大学硕士论文 2 r o u g h 集理论概述 定义2 1 论域u ，集合x u ，关系r 是集合u 上的等价关系，a = ( u ，r ) 是一个 近似空间，在近似空间a 上，如果集合x 是一些r 一基本类的并集，则称x 是r 一可定 义；否则称x 是r 一不可定义的。r 一可定义集被称做r 一一致集或r 一恰当集，而r 一不 可定义集也被说成是r 一不一致集或r r o u 曲集，简称不一致集或r o u 曲集嘲。 定义2 2 设i n d ( u ) 是论域u 上给定的所有等价关系的交集，r i n d ( u ) ， 集合x u 是r 一一致的，则集合x 被称做论域u 中一致集；如果集合xc u 对 任意关系r i n d ( u ) 都是r r o u g h 的，则集合x 被称做论域u 上的不一致集或 r o u g h 集。 定义2 3 设集合x u ，关系r 是u 上的等价关系，则有 r 。( x ) = u q ，u r i y x ， r + ( x ) = u 侈u r i y n x o 分别称为x 的r 一下近似和r 一上近似，下近似和上近似也可以写成下面等价的形式： r + ( x ) = 缸u r | 【x 】r x ， r + ( x ) = 并定义： b n r ( x ) = r + ( x ) - r 。( x ) 为r 一边界线集，其中。表示在等价关系r 下，包含元素x 的等价类，若 b n 。( x ) = o ，则通过等价关系可以恰当地观察x ；相反，若b n 。( x ) o ，只能 r o u g h 地观察x 。前者是分明的，而后者是r o u g h 的。 凡( x ) 是包含于x 中的最大尺可定义集，类似于点集拓扑中的内点；r + ( x ) 是 包含x 的最小r 一可定义集，类似于点集拓扑中的闭包，故有人称其为p a w l a k 拓扑。 并且还定义： x 的r 一正域：p o s r ( x ) = r 。( x ) ， x 的r 一负域：n e g 。( x ) = u - r + ( x ) 。 参见下图： 鞍山科技大学硕士论文2 r o u g h 集理论概述 r + ( x ) 图2 2 r o u g h 示意图 n e g r ( x ) p o sr ( x ) ，r 。( x ) 为了便于理解，下面我们来看一个例子。 例2 1 论域皓 ，x 2 屯，x 4 ，x 5 ，x 6 ，x 7 ，x 8 ) ，r = i n d ( u ) ，r 上的等价类为 e i = x i ，x 4 ，x s ，e 2 = 虬( d ) = 矿，( d ) ，则称该决策表是一 致的，否则是不一致的，其中吼( c ) 为x 在条件属性上的取值，虬( d ) 为x 在决策 属性上的取值。 定义2 6 设$ ( u ，a ，c ，d ) 是一个决策表，其条件属性和决策属性分别为c 、 r 鞍山科技大学硕士论文 2 r o u g h 集理论概述 d ，称d 在s 中以程度女( o 七1 ) 畋a - t - c ，记成c _ d ，其中k = i p o sc ( d ) ) i i u i ， 圜表示集合x 包含的个体的个数，p o s 。( d ) 是d 的c - i e 域。 定理2 1 每个决策表姑( u ，a ，c ，d ) 都能惟一地分解成两个决策表，一致决 策表s l = ( u l ，a ，c ，d ) 和全不一致决策表s 2 = ( u 2 ，a ，c ，d ) ，使得在s 中c _ n ld ， 而在s 2 中c _ h od ，其中 u l = p o s c ( d ) = x e u ，u 肋( 。) p o s c ( x ) 和u 2 = b n c ( d ) = x e u ，u 粕( 。) b n c ( x ) 荆a 例2 2 将表2 1 划分为一致决策表和全不一致决策表，其中肚 ，c ：= ，b ，c ，d = 。 表2 1 非一致决策表 u口扫cd已 11o22o 2ol1l2 32 o o11 41l0 2 2 51o2 01 6220 11 7211 12 8o1l0l 解：首先计算出论域u 对每个属性划分的等价类如下： u a = 1 ，4 ，5 ， 洲培“1 ，3 ，5 ， ， 叫c = “1 ，5 ) ， 2 ，7 ，8 ， ，卅拈 u e = 1 ， ， ： 论域u 对整个条件属性c 以及决策属性d 下划分的等价类如下： u i n d ( c ) = ， u i n d ( d ) 一 ， 。 由定理2 1 可知个体 被划分到一致决策表中，个体 l ，2 ，5 ，8 被划 分到全不一致决策表中，如下： 鞍山科技大学硕士论文2 r o u g h 集理论概述 表2 2 一致决策表 u l 乜6cd已 320 o11 4llo22 62 2 o11 721112 表23 全不一致决策表 u 2 口6cd已 llo 22o 2oll12 51o2o 1 8o1101 在文献【5 中提出的对非一致决策表的一些划分方法，都并不是快速便捷的，因此 提出了基于条件概率的对非一致决策表的划分，参见下节。 2 2 概率论在r o u g h 集理论中的应用 2 2 1 基于条件概率的对于非一致决策表的划分奉 在本节( 该节理论发表于计算机科学3 2 ( 8 a ) 2 0 0 5 ) 中提出了基于 条件概率划分非一致决策表的方法：在将属性分为条件属性和决策属性的基础上， 把每个个体的条件属性作为条件，决策属性作为在该条件下要发生的事件，然后 通过对概率的值来判断该个体是属于一致决策表的，还是全不一致决策表的。 由定义2 5 我们再给出下面的符号表达： i 妒i 。表示在r 中所有满足矿的个体x u 的集合，i 矿i 。表示在r 中所有满足矿的 个体x u 的集合。 定义2 7 p ( 矿i 咖= 紫为基于粗糙决策的条件概率，其中闭表示集合x 鞍山科技大学硕士论文2 r m ：i g h 集理论概述 的基数。 对非一致决策表进行划分之前，要确定条件属性和决策属性，对于每个个体 都要求出其相应的条件概率，如果条件概率的值等于1 ，则把该个体归到一致决策 表中：如果条件概率小于1 ，则把该个体归到全不一致决策表中。下面还以2 1 节 中的表2 1 非一致决策表为例，对该算法进行详细说明。 其中( u ，r ，c ，d ) ，c ：o ，b ，c ，d = ，r = c u d ，再令妒( 拈) 表 示在条件属性a ，b ，c 上取值分别为i ，k 的个体的集合，v ( n m ) 表示在决策属 性d ，e 上取值分别为n ，m 的个体的集合，l 妒( i j k ) l ，ig t ( n m ) i 表示包含的个体的 个数，基于条件概率的对非一致决策表划分的方法如下： ( 1 ) 对于决策属性如n ，e = m 以及a = i ，b = j ，c = k 计算出相应的条件概率 如t 炉等端掣； ( 2 ) 进行判断：如果p ( g t i p ) = 1 ，则把相应的个体归到一致决策表中，否则归到 全不一致决策表中。 现以表2 1 为例，对该方法进行详细说明： 对于个体1 ： 如= 等裟产= 觜掣= 器= i 1 i q ，所以个体归到全不一 l 妒( 1 0 2 ) i li 2 致决策表中： 对于个体2 ： 加= 晋i 舞掣= 等= 器ii 2 q ，所以傩z 删全不 “ p ( 0 1 1 ) il i 。 一致决策表中： 对于个体3 ： 删加等器掣= 鼍铲= 黑乩所以个体s 删一致决黻 “ 1 9 ( 2 0 0 ) ll 3 ) ll 3 ) l 。 中；最后通过该方法可把个体4 ，6 ，7 归到一致决策表中，把个体5 ，8 归到全不 一致决策表中。该表划分后的结果与表2 2 和表2 3 的结果一样，但比其要方便 鞍山科技大学硕士论文 2r o u g h 集理论概述 快捷。 2 2 2 基于概率的r o u g h 集模型 r o u g h 集模型是基于划分的，忽视了可能存在的统计信息，为此需要从概率论 的角度研究r o u g h 集理论，从而提出了概率r o u g h 集模型。 定义2 8a = ( u ，尺) 是近似空间，集合x ，( x u ) 的概率测度为 p ( x u ) ：ix i 。 l u 定义2 9a = ( u ，r ) 是近似空间，p 为2 “上的概率测度，称( u ，r ，p ) 为概率 近似空间，对于0 卢口1 及x u ，记 p ( ) = ， 称p ( j ) ，f b ( x ) 为( u ，r ，p ) 在参数a ，芦下的下近似算子与上近似算子。 定理2 2 设o d 1 ，x ，y 2 “，则( u ，r ，p ) 在参数口，下的下近似算子 与上近似算子具有以下性质： ( 1 ) 皇。( o ) 2 易( o ) = 既p 一。( u ) 2 易( u ) = u ； ( 2 ) p ( x ) ( x ) ； ( 3 ) 0 。( x ) = “只一“( x ) ，乃( x ) 2 “? 。口( x ) ； ( 4 ) x y 时，0 。( x ) p 一。( y ) ，0 ( x ) 0 ( y ) ： ( 5 ) 若口，盯2 ，属晟，则对于任意x 2 “，有 p ( x ) c p q ( x ) ，吃( x ) 吆( x ) 。 例2 3 设沾 x i l i 2 0 ) ，p ( x ) = 等，( x u ) ，u r = x i l i ，x4 = z 1 3 ，x 1 4 ) 鳖坐型垫查兰堡主堡苎兰旦竺韭兰翌鲨：! ! 垄 x5 = q 1 5 ，x 1 6 ，x 1 1 ，x 1 8 ，x 6 = 取x = 0 6 ，x ，z 8 ，工1 3 ，x 1 1 ) ，有 l i m p ( x ) = x ，p ( x ) = x2 u x 。 口地5 一口、 一0 5 舶l i m 易( x ) = x 2 u x 。，r 5 ( x ) 2 x2 定理2 3 设o y l ，则对于任意x u ，有 ( 1 ) l i m p ( x ) = up = 只( x ) ： 口o y 一口口) y 口 ( 2 姆巧( x ) 2 易易5 1 ，( x ) a 定理2 4 设o y 1 ，则对于任意x u ，有 ( 1 ) l i m p ( x ) = np = p ( x ) ； c t ir 口 口 r ( r 2 i x 。) ，则d 2 。 13 鞍山科技大学硕：l 论文 2 r o u g h 集理论概述 由于 。 五：，p ( d 。 x 】。) + p ( d ：【z 】。) = 1 ，则得到最小风险决策规则的 简洁形式： ：若p ( d j x r ) 盯，贝u d l ； r 2 ：若p ( d l r ) 盯，则d 2 。 其中 拈瓦i ( 0 t r ， n e g ( x ，d ) = u ，d = 埘，p 其决策规则如下： ( 1 ) 口l b o c 2 _ d i e l ( 2 ) a z b l c o - d z e o ( 3 ) a z b l 。2 _ d o e 2 ( 4 ) a l b 2 c 2jd l e l ( 5 ) 1 6 2 c oj d o e 2 逐条消去不精确条件属性的值，然后检查它在决策表上能否保持一致，其中符号 ( w ，x ) 表示在属性w 上的取值为x 。 ( 1 ) 中a j c 2 _ d l 巳，a , b oj d l p l ，c 2 - d l p l 均保持为真或称一致。这条规则的 核是空集，即( 口，1 ) ，( 6 ，o ) ，( c ，2 ) 均可被约去。 ( 2 ) 中n 2 c 0jd 2 e o ，b l c 0 _ d 2 保持一致，a 2 b l _ d 2 岛与( 3 ) 矛盾，所以( 6 ， 1 ) ，( n ，2 ) 可被约去。 同理( 3 ) ，( 4 ) ，( 5 ) 中的( c ，2 ) 和( c ，o ) 分别在起相应的规则中不能被约去， 而其余在其相应的规则中均可被约去。如下表 表2 5 经过属性值约简后的决策表 鞍山科技大学硕士论文 2 r o u g h 集理论概述 ud6cdp 1 l 1 2o2 0 3 20 2 421l 5o o2 本节对基于r o u g h 集的属性值约简作了探讨，它可使某一决策的条件属性达到 最小化，从而使我们用最少的信息量即可做到一个正确的判别。 2 4 知识量化 2 4 1 知识量化的提出 以前基于r o u g h 集发现知识的方法有点太绝对化，推出的规则都是确定性的， 或者是肯定的，或者是否定的，而且有些还不完全代表事实，还不完全可信。在 一个信息系统中如果有1 0 0 0 个条件属性相同的个体属于同一个决策表，但有一个 个体的条件属性与这1 0 0 0 个相同，不属于同一个决策类，那么就推不出规则，而 且在现实生活中也有许多可能和不确定的情况。还有些条件属性取值相同的个体 在整个论域中只有少数几个，但它们在同一决策类中，因此也可以推出规则，但 由这些属性推出的规则很不准确也不可信( 该部分内容发表于计算机科学 2 0 0 4 v 0 1 3 1 n o 1 0 a ) 。 基于以上分析