（计算机软件与理论专业论文）基于粗糙集的并行约简研究.pdf

暑 鼍 究 粗糙集理论是数据挖掘的重要工具，也是粒计算理论的一个重要分支。经典 粗糙集是由波兰学者p a w l a k 于上世纪8 0 年代提出来的。粗糙集理论通过对象间 的不可区分关系( 等价关系) ，为不完全和不充分信息的处理提供了一套系统的 方法。当前粗糙集理论已经成为计算机科学、信息科学、人工智能等领域的研究 热点。 知识约简是粗糙集理论的重要应用，也是其核心问题之一。知识约简是指在 不改变整个数据集的分类能力的情况下，消去信息系统或者决策表中的冗余。由 于数据集本身的复杂性和传统约简方法的局限，在处理海量数据时，粗糙集理论 没有体现出它应有的活力。许多学者在知识约简方法的改进上做了大量的探索。 例如并行约简的概念。 并行约简是近两年出现的知识约简研究的热点，它利用并行计算的思想和方 法，应用到基于粗糙集的数据挖掘当中。并行约简的概念比较新，理论体系、方 法和技术等均有待完善，目前还没有一种高效的并行属性约简算法，值得研究和 探索。本文围绕基于粗糙集的并行约简定义、性质的讨论，对不同形式的数据集 进行子表抽样，子表并行约简和提取决策规则展开。 论文所做的工作有： ( 1 ) 针对不同的数据特点，引入相应的并行约简定义，并进行局部的扩展和 算法研究。本文一共定义了三种类型的并行约简：基于正域的并行约简、基于差 别矩阵的并行约简以及基于属性重要度的并行约简，并同时完成了这三种形式的 并行约简算法设计。 ( 2 ) 针对基于正域的并行约简的条件限制，提出了变精度并行约简概念，并 t 对变精度并行约简的性质进行了讨论。 ( 3 ) 针对不同性质的数据集，设计了不同的子表抽取策略。并在如何对海量 数据进行子表抽样问题中，提出了一种聚类抽取子表的方法。 ( 4 ) 对现有的决策规则提取方法的局限性进行了分析，针对增量式规则提取， 给出了一种解决方法。 关键词：粗糙集；并行约简；变精度并行约简；子表抽取策略；规则提取 i i 1 1 擎 r l a b s t r a c t s e do n r o u g h s e tt h e o r y , p r o p o s e db yp o l a n ds c h o l a rp a w l a ki n19 8 2 ，i sa p o w e r f u lt o o l f o rd a t am i n i n ga n da ni m p o r t a n tb r a n c ho fg r a n u l a rc o m p u t i n g t h er o u g hs e tt h e o r y p r o v i d e s as y s t e m a t i cm e t h o df o r d e a l i n g w i t h i m p e r f e c t a n di n s u f f i c i e n c y i n f o r m a t i o nb yi n d i s t i n g u i s h a b l er e l a t i o n s h i p r o u g hs e th a sb e c o m eah o tt o p i ci n c o m p u t e rs c i e n c e ，i n f o r m a t i o ns c i e n c ea n da r t i f i c i a li n t e l l i g e n c ee t c k n o w l e d g er e d u c t i o ni sa ni m p o r t a n ta p p l i c a t i o na n dac o r ei s s u ei nr o u g hs e t t h e o r y k n o w l e d g er e d u c t i o nd e l e t e st h er e d u n d a n c yi n f o r m a t i o ni ni n f o r m a t i o n s y s t e m so rd e c i s i o nt a b l e sw h i l ei td o e sn o tc h a n g et h ec l a s s i f i c a t i o no fw h o l ed a t a s e t b e c a u s eo ft h ec o m p l e x i t yo ft h ed a t a s e ta n dt h el o c a l i z a t i o no ft r a d i t i o n a lr e d u c t i o n s ， r o u g hs e t c a n ts h o wi t sv i t a l i t yw h i l ew ed e a lw i t ht h em a s sd a t a m a n ys c h o l a r s m a k ea na t t e m p to ni m p r o v e m e n to fk n o w l e d g er e d u c t i o na l g o r i t h m ，s u c ha sp a r a l l e l r e d u c t i o n p a r a l l e lr e d u c t i o nh a sb e c o m eah o tt o p i ci nr e c e n ty e a r s i tm a k e su s eo ft h ei d e a a n dm e t h o do f p a r a l l e lc o m p u t i n g ，a n dc a nb eu s e di nd a t am i n i n gt h a tb a s e do nr o u g h s e t b e c a u s ep a r a l l e lr e d u c t i o ni san e w l yc o n c e p t ，i t sp a r a d i g ma n dm e t h o da n d t e c h n o l o g ys h o u l db ei m p r o v e d b u tn o wt h e r ei s n ta ne f f i c i e n tp a r a l l e lr e d u c t i o n m e t h o d t h er e s e a r c ho ft h i st h e s i si sm a i n l ya b o u tt h ep a r a l l e lr e d u c t i o nd e f i n i t i o n ， p r o p e r t i e sb a s e do nr o u g hs e ta n ds u b t a b l es a m p l i n gf o rd i f f e r e n tt a b l e s t h em a i nc o n t r i b u t i o n sa n di n n o v a t i o n so ft h i st h e s i sa r ea sf o l l o w s i a tf i r s t , a c c o r d i n gt ot h ec h a r a c t e r i s t i co fd i f f e r e n td a t a ，w ei n t r o d u c e dt h e d e f i n i t i o no fp a r a l l e l r e d u c t i o n ，a n de x t e n di t sc o n c e p t w ei n t r o d u c e dt h r e et y p e s p a r a l l e lr e d u c t i o n ：p a r a l l e lr e d u c t i o nb a s e do np o s i t i v ea r e a ，p a r a l l e lr e d u c t i o nb a s e d o nd i s c e r n i b i l i t ym a t r i x ，p a r a l l e lr e d u c t i o nb a s e do ni m p o r t a n c ed e g r e eo fa t t r i b u t e m e a n w h i l ew e d e s i g n e dt h r e ea l g o r i t h m sf o rt h et h r e ep a r a l l e lr e d u c t i o n s s e c o n d l y , b e c a u s eo ft h es t r i n g e n to ft h ep a r a l l e lr e d u c t i o nb a s e do np o s i t i v ea r e a ， w ep r o p o s e dt h ed e f i n i t i o no fp a r a l l e lr e d u c t i o nb a s e do nv a r i a b l ep r e c i s i o n ，a n d i n v e s t i g a t e di t sp r o p e r t i e s t h 硼l y ，w ep r o p o s e dd i f f e r e n ts a m p l i n gs t r a t e g i e sb a s e do nd i f f e r e n td a t es e t ；w e a l s op r o p o s e dac l u s t e r i n gm e t h o df o rs u b t a b l ee x t r a c t i o n f i n a l l y , w ea n a l y z e dt h el i m i t so fd e c i s i o nr u l e se x t r a c t i o n ，a n dp r o p o s e da l l e f f e c t i v ei n c r e m e n t a le x t r a c t i o no fd e c i s i o nr u l e st os o l v e t h e s ep r o b l e m s k e yw o r d s ：r o u g hs e t ；p a r a l l e lr e d u c t i o n ；v a r i a b l ep r e c i s i o np a r a l l e l r e d u c t i o n ；d e c i s i o nr u l e s ；s u b t a b l ee x t r a c t i o ns t r a t e g i e s i v 目录 摘要i a b s t r a c t i 目录v 1 绪论l 1 1 研究的内容和目的1 1 2 粗糙集理论概述一3 1 2 1 粗糙集基本概念3 1 2 1 1 知识与分类3 1 2 1 2 粗糙集的上下近似集4 1 2 2 粗糙集理论的研究与应用现状5 1 3 文章内容组织结构7 2 决策表的属性约简9 2 1 决策表的基本概念一9 2 2 传统决策表属性约简算法一9 2 2 1 基于差别矩阵的决策表属性约简算法1 0 2 2 2 基于信息熵的属性约简算法1 2 2 3 动态数据、增量数据属性约简算法1 4 2 3 1 动态数据特点分析1 4 2 3 2 属性约简增量算法1 5 2 3 3 动态约简1 9 2 4 小结一2 1 3 并行约简2 2 3 1 并行约简概念2 2 v 3 1 1 基于正域的并行约简2 2 3 1 2 基于差别矩阵的并行约简2 4 3 1 3 基于属性重要度的并行约简2 5 3 2 变精度的并行约简2 6 3 3 并行约简子表生成策略2 7 3 3 1 增量式数据子表计算策略2 7 3 3 2 分布式数据子表计算策略2 8 3 3 3 海量数据集子表抽取策略一2 8 3 3 3 1 痕迹抽取法一2 9 3 3 3 2 概率抽取法3 0 3 3 3 3 聚类构造法3 1 3 4 并行约简算法及实验分析3 2 3 4 1 增量数据并行约简算法3 2 3 4 2 分布式数据以及海量数据并行约简算法实验3 3 3 4 3 并行约简算法实验3 6 3 4 4 并行约简算法与其他约简算法效率比较3 6 3 5 小结3 9 4 基于并行约简的决策提取4 1 4 1 常用决策规则提取方法4 1 4 2 增量式决策规则提取算法4 3 4 3 增量式决策规则提取算法实例4 6 4 4 小结5 0 5 总结与展望5 l 5 1 全文总结5 1 5 2 研究展望5 l 参考文献5 3 致谢5 7 攻读硕士学位期间主要的研究成果一5 9 l 6 0 6 0 6 1 畸 摹 j 1 绪论 伴随着互联网的快速发展，网络数据量呈爆炸性增长，知识也以日新月异的 速度更新。然而与数据快速增长速度相对应的是，在海量数据中，发现有用的信 息越来越难 1 1 。因此，如何在海量数据中发现有用的信息就成为信息时代的一个 重要课题，为此数据挖掘这门学科应运而生【2 】。但是在海量数据库中的数据通常 含有冗余特征及噪声，这不仅导致数据挖掘的代价高，而且导致规则提取的质量 低。所以自从数据挖掘理论产生之日起，国内外许多专家学者都致力于研究如何 能降低数据挖掘的代价同时又能提高规则提取的质量问题。现有的数据挖掘实现 方法主要有：决策树方法 3 5 】、神经网络方法 6 9 1 、遗传算法 1 0 - 1 2 】、模糊集方法 1 3 1 5 】 以及粗糙集理论 1 6 - 2 0 1 等等。其中由波兰学者p a w l a k 提出的粗糙集理论在不改变 海量数据分类能力的情况下，对数据进行进行知识约简，导出决策规则或者对规 则进行分类有很好的效果。 粗糙集理论与方法能够有效的处理复杂系统中的数据和信息，尤其是对具有 模糊性，不确定性和不完全性的信息，粗糙集能表现出很大的优势。粗糙集理论 与其他不确定性问题处理工具和方法最大的差别在于：无须提供所处理数据的任 何先验信息，可以基于现有的知识库进行数据挖掘。 1 1 研究的内容和目的 粗糙集是波兰数学家p a w l a k 为开发自动规则生成系统，以及研究软计算问题 于1 9 8 2 年提出的，它是一种处理具有模糊性、不确定性与不完全数据的新的数据 分析理论。它的主要思想是利用已知的知识库，将不精确或不确定的知识用现有 的知识库中的知识来近似刻画。 粗糙集理论无需提供问题所需处理的数据集合之外的任何先验信息，通过在 内部数据建立等价类，用上下近似集来逼近数据库中的不精确或者边界信息。粗 1 1 绪论 糙集理论包含处理不精确或不确定原始数据的机制，所以与概率论、模糊数学和 证据理论等其他处理不确定或不精确问题的理论有很强的互补性。 知识约简【2 l 】是粗糙集理论的主要应用方向，也一直是粗糙集理论的研究热 点。知识约简通常包括属性约简和属性值约简。一般认为属性值约简是建立在属 性约简的基础上的。属性约简是针对全数据集的处理，在不改变整个数据集的分 类能力的情况下，消去信息系统或者决策表中的多余属性，通常也看做是对数据 集的降维；而属性值约简是对数据集的中的每个对象进行处理，在不改变对象的 分类能力的情况下，消去对象内的冗余值。 当前，在属性约简研究方面已经取得了很多成果，例如由s k o w r o n 2 2 3 等提出 的通过构造差别矩阵，求差别函数之间的最小析取范式方法；由吕跃进【2 3 1 等提出 的遗传算法；由j a ngb a z a n 冽提出的动态约简等方法都在各自的研究领域取得 了成果。但是在当前网络飞速发展，数据量呈爆炸性增长的现实面前，运用这些 方法对动态数据或者海量数据进行属性约简都有或多或少的局限性。为了寻求针 对动态数据或者海量数据属性约简更好的方法，我们提出了并行约简概念，以求 更有效的获得属性约简集。 属性值约简通常也称为规则提取方法，虽然现今存在许多种属性值约简方 法，例如归纳值约简方法，基于决策矩阵的决策表的值约简方法等都很好的解决 了决策表的规则提取，但是这些方法基本上都是处理静态数据集，当有新的数据 添加到原有数据集时，若仍用这些属性值约简方法进行规则提取，则是非常繁琐 的，需要做很多重复工作。因此决策规则的增量式更新算法的研究也是粗糙集应 用的一个新的热点。 本文主要的工作内容是在总结现有基于粗糙集的属性约简模型的基础上，分 析当前动态数据和海量数据的性质，引入并行约简概念，并初步研究了其性质以 及与其他属性约简的关系，最后将其应用到动态数据和海量数据的属性约简当中 去。同时针对不同的数据特点，我们设计了不同的子表抽取策略，并基于这些子 表抽取策略设计并实现了不同的并行约简算法。同时我们也分析了决策规则的增 量式更新遇到的局限性，给出了解决的主要思想，并进行了算法描述。 2 1 绪论 1 2 粗糙集理论概述 1 9 8 2 年波兰学者p a w l a k 首次提出粗糙集概念，最初并没有受到很多专家学 者的关注，研究只局限于波兰及周边一些东欧国家。直至1 9 9 1 年p a w l a k 的专 著粗糙集一关于数据推理的理论的出版，以及1 9 9 2 年第一届关于粗糙集理 论的国际学术会议在波兰召开，粗糙集的发展才逐渐受到各国学者的关注，粗糙 集理论的研究应用也逐渐趋热。近些年来由于粗糙集理论在数据挖掘、知识发现、 模式识别、决策支持与分析等领域的成功应用，使得粗糙集理论成为计算机科学 理论研究的一个热点。 1 2 1 粗糙集基本概念 1 2 1 1 知识与分类 ”知识”这个概念，在不同的范畴中会有不同的含义。在数据挖掘、知识发现 以及粗糙集理论中，”知识”被认为是一种分类的能力。人们的行为是基于分辨现 实的或抽象的对象的能力，如医生给病人诊断，必须辨别出患者得的是哪一种病。 这里的对象可以指能够想象到的任何事物，比如实物、状态、抽象概念、过程和 时刻等等，所有对象的集合被统称为全域或论域( u n i v e r s e ) ，用u 表示。论域u 中 的一个元素就是一个对象，任何对象的集合z u ，则称为u 中的一个概念或 者范畴。粗糙集理论主要是对在论域【，上能形成划分的知识进行研究。 定义1 1 假设u 是论域，u o ，r 是u 上的一个等价关系( e q u i v a l e n c e r e l a t i o n ) ，则u r 构成了u 上的一个划分，称足= 似固为u 中关于r 的近似空 ( a p p r o x i m a t es p a c e ) 。 划分在某种程度上体现了知识分类( g r a n u l e s ) 的存在，它表明在已知的有限 信息条件下，某些对象具有相似性，它们之间是不分明的( i n d i s c e r n i b i l i t y ) 。 定义1 2 任意的x u 称为论域u 上的一个概念( c o n c e p t ) 。u 中的概念族 c = 五，置，e ) 称为关于u 的知识( k n o w l e d g e ) ，石u ，石o ，石n 为= g ， 3 1 绪论 ( f j ，i , j = 1 , 2 ，n ，u 置= u ) 。形式上，空集。也视为一个概念。一个知识库 ( k n o w l e d g eb a s e ) 是指u 上的一个分类族k = ，彤，其中，r 是u 上的等价关系族。 定义1 3 设尸冬q ，且尸q ，肿所有等价关系的交集n p 也是一种等价关系， 记作i n d ( p ) ，即 x i n d ( p ) = n t x ， r e p 其中 x p 表示由p 所确定的包含有元素珀勺等价类。 定义1 4 给定近似空间k = ( u ，r ) ，非空子族集psr 所产生的不分明关系 i n d ( p ) 的所有等价关系的集合即u i n d ( p ) ，称为基本知识( b a s i ck o n w l e d g e ) ，相 应的等价类称为基本概念( b a s i cc o n c e p t ) ；特别地，若关系per ，则关系p 就称为初 等知识( e l e m e n t a r yk o n w l e d g e ) ，相应的等价类就称为初等概念( e l e m e n t a r y c o n c e p t ) 。 定义1 5 设k = ( u ，尸) 和k = ( u ，q ) 为两个知识库，如果i n d ( p ) = i n d ( q ) ( 或者u p = u q ) ，则称k 和k 是等价的，记做奎k 。若i n d ( p ) c i n d ( q ) ， 则称知识p 是知识q 的细化。 由以上定义可知，概念即对象的集合，概念的族集( 分类) 就是u 上的知识， u 上分类的族集可以认为是u 上的一个知识库，或说知识库即是分类方法的集 合。 不分明关系( 通常是等价关系) 是粗糙集理论的起点，分类的观点是粗糙集理 论的基本观点。 1 2 1 2 粗糙集的上下近似集 在粗糙集理论中，知识库k 中的有些类是可定义的，有些类是不可定义的，还 有些类是可近似定义的。设x u ，r 是u 上的等价关系，若x 是一些尺基本类的并 集，则称x 是r - 可定义的( r - d e f i n a b l e ) ，否则称x 是r 不可定义的( r - u n d e f i n a b l e ) 。 r 可定义集也称为r 一精确集( r e x a c ts e t s ) ，r 一不可定义集也称为r 不精确集或 r 一粗糙集( r - i n e x a c ts e t s ，r - r o u g hs e t s ) 。 4 r ( x ) = x u ， x r n x a ) 或 r ( x ) = u y u r ：】，n x g ) 称为x 关于r 的上近似集( u p p e ra p p r o x i m a t i o n ) ，或者称为上近似算子。则论域u 上的二元组( 墨( x ) ，页( x ) ) ) 构成了一个粗糙集。 定义1 7p o s r ( x ) = 堡( z ) 被称做x 的r 一正区域，n e g r ( x ) = u r ( x ) 被称做 x 的r 一负区域，b n r ( x ) = r ( x ) 一旦( x ) 被称做x 的尺一边界区域。 如果边界域b r ( 石) = 彩，则x 被称做是可定义的，否则被称作是粗糙的。 正域尸d 敛( x ) 或星何) 是指在知识尺下，论域w e e 所有必定能归入x 的元素的集合； 负域n e g 月( x ) 是指在知识r 下，u 中所有必定不能归入x 的元素的集合；边界 b n r ( x ) 是指在知识r 下，u 中所有既不能肯定归入x 又不能肯定归入- 1 x 的 元素的集合。显然若边界域非空，则x 便带有某种程度的不确定性，即x 具有 模糊性。 上、下近似是粗糙集的基础。粗糙集的粗糙性是一种基于边界的概念，即一 个粗糙的概念，具有模糊性，不可被明确划分的边界。一般地，在给定近似空间中 并非所有的对象子集都可以用给定的知识来表示成概念，这样的的子集就认为 是粗糙概念( 即不精确或近似的概念) ，它可由上，下近似集这样一来两个精确集合 来描述，这使得我们可以精确的描述不精确的概念。 1 2 2 粗糙集理论的研究与应用现状 粗糙集理论由波兰数学家p a w l a k 于1 9 8 2 年提出，到现在经历了2 0 多年的 发展壮大，已经成为了一门跨数学与计算机的交叉性学科，无论是在理论方面还 s 1 绪论 是在应用方面都取得了很大的进展，并且仍是计算机学科的研究热点。 其中在粗糙集理论研究方面，国际和国内的专家学者进行过很多研究，取得 了长足的发展。其中大多数专家学者致力于粗糙集模型的推广以及数学理论方面 的研究。 粗糙集模型的推广【2 5 - 2 8 1 。p a w l a k 经典粗糙集的运算是建立在等价关系的基 础之上，需要满足自反、对称和传递三种关系，但是在实际过程中传递性很难得 到满足，因此如何推广粗糙集模型一直是粗糙集理论研究的主流方向。目前为止 主要用两种研究方法：构造性方法和代数性( 公理化) 方法。构造性方法研究较为 普遍，主要思想是从己知的近似空间去研究粗糙集和近似算子( 上下近似集) 。它 以论域上的二元关系或布尔代数作为基本要素，导出粗糙集的代数系统。目前 已有许多学者在一般关系下来推广粗糙集模型，相继提出基于覆盖的粗糙集理 论、模糊粗糙集理模型、粗糙模糊集理模型等；代数方法亦称为公理化方法， 它是基于粗糙集的代数系统的两个算子( 上下近似集) ，该方法可以深入描述近 似算子的代数结构。 数学理论方面的研究 2 9 - 3 1 】。粗糙集的产生主要是为了解决数学中的边界线 区域的问题，后来经过各国学者的研究发展，逐渐引入到计算机理论当中来。现 今粗糙集在数学理论方面主要讨论粗糙集的代数结构、拓扑结构，以及粗糙集的 收敛性问题。 从代数结构观点研究粗糙集的数学理论，与之关系比较紧密的有数理逻辑、 格与布尔代数、模态逻辑、算子代数等。粗糙集的拓扑结构也一直是粗糙集理 论数学方面研究的热点问题。传递关系下的粗糙集模型，证明了其中的上、下 近似算子恰为一个拓扑空间的闭包与内部算子。对于p a w l a k 近似空间来说，所 有的下近似集构成一个拓扑空间。 随着粗糙集理论方面的研究取得很大进展，粗糙集理论的应用也越来越广 泛。其中最广泛的算法研究主要集中在：约简的启发式算法；导出决策规则 的增量式算法；粗糙集基本运算的并行算法。 约简的启发式算法的基本步骤都是：由信息系统或决策表的核属性为起始 点，然后根据属性重要性的计算，依次选择最重要的属性加入核属性中，直到满 6 粗糙集约简表达的是信息系统或者决策表属性间的确定性关系，正域之外等价类 族表达的属性间关系并不被粗糙集认可，因此除要求属性满足确定性关系外，挑 选有强烈概率因果关系的属性集是必须的。为了描述概率因果关系，处理这类数 据时在约简算法中引入信息熵来度量属性重要度。 导出决策规则的增量式算法，是粗糙集理论一个重要应用方向。在决策表中 要进行决策规则的提取，通常是通过知识约简的方法实现。决策规则提取的一个 基本思想是在保持原有的信息系统或者决策表的分类与决策能力不变的情况下， 运用属性约简的方法把原来数据表中冗余的属性消去，得到一个属性约简集，然 后从这个属性约简集中进行属性值约简进而提取决策规则。传统的属性约简算法 是在固定的数据集上进行的，当决策表有数据增加时，若通过传统属性约简算法 和属性值约简方法导出决策规则是非常复杂的。利用增量式算法对传统规则进行 修正，从而得到关于增量数据集的规则是粗糙集的一个新的应用方向。 粗糙集基本运算的并行方法：粗糙集的性质决定它的很多运算都可以实现 分布式或者并行计算，随着计算机网络的飞速发展，大量相关的数据分布在世界 各地，粗糙集可实现分布式或并行计算的性质就显得尤为重要。 由于粗糙集在有效算法应用中取得很大进展，使得粗糙集理论在人工智能科 学飞速发展，尤其对机器学习、知识发现、决策分析、专家系统、决策支持系统、 模式识别等方面的发展具有十分重要的意义。 1 3 文章内容组织结构 本文一共包括五章，简单的介绍了粗糙集理论及其思想，深入研究了基于粗 糙集的属性约简方法，并提出了并行约简概念，同时在并行约简的基础上研究了 7 1 绪论 基于增量式决策规则更新方法。 第一章主要介绍了本文的写作目的，研究的内容并简单介绍了粗糙集理论的 研究状况，最后给出了文章的结构安排。 第二章主要综述决策表知识约简的基本知识，分别介绍了传统属性约简和增 量、动态属性约简理论知识，最后分析了这些属性约简的特性。 第三章是本文的重点内容，提出了基于正域的并行约简、基于差别矩阵的并 行约简、基于属性重要度的并行约简三个概念，同时针对基于正域的并行约简的 局限性，提出了变精度并行约简的概念，研究了变精度并行约简的性质。另外根 据数据集的不同性质，分别给出了不同的子表抽取策略。在海量数据的子表抽取 策略中，我们提出了一种新的子表抽取策略，即聚类子表抽样方法。此外，在这 章内容的最后，我们设计实现了基于正域的并行约简算法，并同动态约简进行了 效率比较，同时设计实现了基于差别矩阵的并行约简算法，比较了该算法与x h u 差别矩阵属性约简算法和d e n g 增量式属性约简方法的效率。 第四章是本文研究的最后内容，本章首先介绍了决策规则的概念，并介绍了 如何通过归纳值约简方法进行规则提取。最后针对决策规则增量式更新过程中遇 到的问题，提出了基于差别矩阵并行约简的决策规则增量式更新方法，并通过实 例进行了算法描述。 第五章，总结与展望。对本文的研究内容做最后总结，并指出进一步研究工 作的重点与方向 8 2 决策表的属性约简 2 1 决策表的基本概念 定义2 1 设s = ( u ，a ，v ，) 是一个信息系统，其中u = 工。，x ：，x 。) 是论域，么为属性集合，y 是属性值集合，f 是u a _ v 的映射。 定义2 2 设s = ( u ，a ，v ，) 是一个信息系统，a = c ud ，cnd = 彩，c 称为 条件属性集，j d 称为决策属性集。具有条件属性和决策属性的信息系统称为决策 表。多数决策问题都可以用决策表形式来表达，这一工具在决策应用中起着重要 的作用。 属性约简是粗糙集理论的重要应用之一，也是其赖以存在的重要基础。基于 粗糙集理论的数据约简有多种分类方法。从信息系统是否包含决策属性来看分为 绝对约简和相对约简。不包含决策属性的数据约简称为绝对约简，包含决策属性 的约简称为相对约简。由于绝对约简可以转化为相对约简，所以一般情况下的约 简都是指相对约简。在本文中所讨论的约简是基于决策表的，所以都是相对约简。 2 2 传统决策表属性约简算法 从约简泛化能力的角度来看，可以将约简分为静态约简和动态约简。静态约 简往往是处理一些固定数据或者数据量比较小的约简，所以我们通常称静态约简 为传统的属性约简；而假如要计算海量数据或动态变化数据的属性约简，通常要 寻求动态约简方法。目前对约简的研究工作主要在静态约简上，然而也有越来越 多的人关注动态约简、增量式约简以及其他形式的约简。下面我们首先简单介绍 几种常见的静态属性约简算法。 9 2 决策表的属性约简 2 2 1 基于差别矩阵的决策表属性约简算法 差别矩阵和差别函数由a s k o w r o n 和c 。r a u s z e r 3 2 1 于1 9 9 1 年提出的，主要是用 来计算约简和推理的方法。虽然这种方法因为计算复杂度问题受到了一些研究者 的质疑，但是这种方法易于推理和解释，尤其是计算核属性简单方便，容易被人 们接受，而且基于遗传算法的约简算法都是以差别矩阵差别函数为基础，并且许 多规则提取的方法也是基于差别矩阵方法，所以还是有不少研究者对其进行研 究。 a s k o w r o n 和c r a u s z e r 最初对差别矩阵、差别函数的定义如下： 定义2 3 设d s = ( u , c u d ) 是一个决策表，则决策表d s 的差别矩阵为， m ( d s ) = m ( x ，y ) x ，y u 其中， m ( x ，y ) = 口c ：口( x ) 口( y ) ) 对应于差别矩阵m ( d s ) 的差别函数为， f ( d s ) = ( v ，z ( x ，y ) ) ，m ( x ，y ) 0 在实践过程中，由a s k o w r o n 和c r a u s z e r 提出的差别矩阵和差别函数有一定 的局限性，由此许多专家学者对他们的定义进行过改进。当中由x h u 和 n c e r c o n e 3 3 】改进的差别矩阵、差别函数是应用最广泛的差别矩阵和差别函数， 它的定义如下： 定义2 4 设d s = ( u ；c u d ) 是一个决策表，则决策表d s 的差别矩阵为， m ( d s ) = m ( x ，y ) z ，y u 其中， i a c ：口( 石) 口( y ) )矿d ( 功a ( y ) 【a o t h e r w i s e 对应于差别矩阵m ( d s ) 的差别函数为， f ( d s ) = “毗瑚，如力0 上述两个定义在定义差别矩阵和差别函数时都没有考虑决策表的一致性，这 个定义进行了改进， 的差别矩阵为， 吣棚= 力删硝删色戮黧议力 。1 对应于差别矩阵m ( d s ) 的差别函数为， f ( d s ) = 小，如瑚，r e ( x , 力囝 从上面几个差别矩阵的定义可以得到差别矩阵的一个重要性质：决策表的核 属性是差别矩阵中所有单个元素组成的集合，即： c o r e ( a ) = c 7 1 c i m ( x ，y ) = 口) ，其中x ，y u 利用上面差别矩阵以及差别函数的定义，设计基于差别矩阵的决策表属性约 简算法如下： 输入：一个决策表d s = ( u ，c u d ，a ，f ) 。 输出：决策表d s 的所有相对约简r e d c ( d ) 。 步骤1 ：根据决策表差别矩阵的定义，计算坂h ( d s ) = ( ) 砌的下三角矩阵 ( 或上三角矩阵) ，其中= 1 , 2 ，2 。 步骤2 ：搜索差别矩阵的所有元素，若没有囝，则转到步骤3 ，否则退出。 步骤3 ： 搜索决策表差别矩阵中的所有单属性元素，将其赋给c o r e c ( d ) ， 输出c o r e c ( d ) = ai ( a c ) a ( 3 c o ，( ( c f a 厶一( d 丁) ) a ( c f = 口) ) ) ) 。 步骤4 ：求出包含相对d 核的所有可能的属性组合，判断是否满足 0 v c u 坛一( d s ) ，当c q o 时，是否有b n c _ f j f 2 j ? 不考虑c f ，= g v 一的情形； 召是否为独立的? 若满足上述两个条件，则将其赋给啦( d ) ，遍历所有包含相对d 核的属性 组合。 2 决策表的属性约简 步骤5 ： 输出r e d c ( d ) ，算法结束。 从上面的算法可以看出，该方法需要构件一个l u 川u i 的矩阵，当决策表的 记录非常庞大时，该方法的时空复杂度就非常大，效率低下。刘清3 5 1 针对以上问 题对基于差别矩阵的属性约简算法进行了改进，即简化算法中一定要生成差别矩 阵这个中间环节，在决策表中提取关于属性值具有差别的属性构造差别合取范 式，一边做这种逻辑公式的等价交换，直到得到最小析取范式，既是该决策表的 约简。 2 2 2 基于信息熵的属性约简算法 定义2 6 设d s = ( u ；c u d ) 是一个决策表，p c ，q c ，设尸，q 在论域u 上 导出的划分分别为x = x 1 ，x 2 ，) ，y = y 1 ，】，：，k ，则p ，q 在u 上的子集组成 的概率分布为 x ：p 】_ ， x 2 l p ( x 2 ) p ( ) j l ， r v ， y ：p 1 1 。 。l p ( y 1 ) 其愀耻_ 丽l x , t 小1 ，2 ，棚叫】；) = 鼢乒1 ，2 ，一 y 2y 。 p ( y 2 ) p c ：n ) j 定义2 7 对于决策表傩= ( u ；c u d ) ，p c c 且p ( w l 脚( 尸) ) = ，置，以) ， 则属性集p 的熵h ( p ) 定义为： 日( 尸) = 一p ( a s ) l o g ( p ( a 5 ) ) t = l 其中，p ( 置) = l 置i i u i 由定义2 7 中可知，h ( p ) 0 ，它反映了知识尸对决策表d s 的分类能力的 强弱。若h ( p ) 越大，则说明论域u 经过知识尸分类后，各等价类r 中的决策属 性值分布就越均匀，表明知识p 对决策表d s 的分类能力越弱。反之，则说明知 识p 对决策表d s 的分类能力越强。 定义2 8 对于决策表d s = ( u ；c u d ) ，则条件属性集合q ( q c ) 的熵 1 2 集p ( p c ) 的熵 石) ) 集，则q c 是c 相对于 ( 1 ) 日( d ) l q ) = 日( d ) l c ) ( 2 ) 对于q 中任意一个属性口，都有日( d ) jq ) 日( d iq - a ) 成立。 则依据定义2 9 可以设计两个基于信息熵的属性约简算法。 基于信息熵的属性约简算法1 ： 输入：一个决策表d s = ( u ，c u d ，么，f ) 。 输出：决策表d s 的所有相对约简r e d c ( d ) 。 步骤1 ：计算决策表d s 中决策属性d 相对条件属性集c 的条件熵h ( d ic ) ； 步骤2 ：计算条件属性集c 中相对决策属性d 的核属性集c o r e c ( d ) ，将非 核条件属性记入集合a r t 中，即a t t = c c o r e c ( d ) ； 步骤3 ：令b = c o r e c ( d ) ， ( 1 ) 如果i b l _ 0 ，则计算条件熵h ( d l b ) ，转( 4 ) 。 ( 2 ) 对每个属性a i a t t ，计算决策属性集d 相对条件属性集b u 口矗的条 件熵h ( d i 口u 口j ) 。 ( 3 ) 选择使h ( d l b u 口f ) ) 最小的属性a j ( 若同时有多个属性达到最小值， 则从中选取一个与b 属性值组合数最少的属性作为a j ) ，并且a t t 一国，b = b u a j 。 ( 4 ) 若h ( d i b ) = h ( d i c ) 则输出r e d c ( d ) ，并终止，否则转( 2 ) 。 算法1 的主要思想决策属性集d 相对于条件属性集c 的条件熵；然后计算条 件属性的核集是，在核集的基础上，依据属性重要度从d , n 大逐渐将各个条件属 性添加属性集b ( 初始为核集) 中，直到h ( db ) = h ( dc ) 终止。 13 2 决策表的属性约简 基于信息熵的属性约简算法2 ： 输入：一个决策表d s = 缈，c u d ，么，f ) 。 输出：决策表d s 的所有相对约简r e d c ( d ) 。 步骤l ：计算决策表d s 中决策属性d 相对条件属性c 的条件熵h ( dc ) ； 步骤2 ：计算决策属性相对每个条件属性的条件熵h ( di a i ) ) ( q c ) ，将口f 按h ( dl q ) ) 的大小降序