（计算机应用技术专业论文）基于高级sql查询的分布式多维关联规则挖掘算法的研究.pdf

t h e s i ss u b m i t t e dt ot i a n j i n u n i v e r s i t yo ft e c h n o l o g y f o r t h em a s t e r sd e g r e e r e s e a r c ho nm u l t i d i m e n s i o n a l a s s o c i a t i o nr u l e sm i n i n gi nd i s t r i b u t e d e n v i r o n m e n t sb a s e do na d v a n c e d s q l q u e r y b y l e iz h a n g s u p e r v i s o r m e iq i a o j a n u a r y2 0 1 0 独创性声明 摘要 多维关联规则挖掘是数据挖掘的重要研究内容。与此同时，随着i n t e m e t 的迅猛发 展，分布式数据库得到广泛应用。因此，迫切需要一种方法解决分布式环境下多维关联 规则挖掘的问题。 本文提出了一种基于高级s q l 查询的m d m a ( m u l t i d i m e n s i o n a ld i s t r i b u t e dm i n i n g a s s o c i a t i o nr u l e s ) 算法。本算法基于星型网络拓扑结构，由中心站点和分站点组成，中 心站点负责控制挖掘过程和显示挖掘结果，分站点负责挖掘局部频繁项集和对全局频繁 模式进行局部支持度计数。本算法利用了s q l 新标准中的c u b e 运算符，能够通过一 次扫描局部数据库产生全部的局部频繁项集，使得在挖掘过程中不必通过多次迭代产生 频繁项集。本算法采用两次知识融合技术来实现分布式频繁模式挖掘。首先，从各个分 站点挖掘出的局部频繁项集中提取出全局候选频繁模式，然后，中心站点根据筛选出的 全局候选频繁项集构建全局扩展频繁模式树。此全局扩展频繁模式树会从中心站点发往 各个分站点。各个分站点接收到全局扩展频繁模式树之后，利用本地局部数据库中的数 据计算各个全局候选频繁项集的局部支持度计数并把计算结果发往中心站点。中心站点 会对各个分站点发送过来的计数结果进行汇总统计并根据统计结果找出全局频繁项集。 因此，不管分站点数量为多少，各个分站点局部数据库规模如何，此算法始终只需两次 扫描数据库和三次网络通信就可产生全部的全局频繁项集。为高效地实现多维全局频繁 模式的知识融合，本算法提出了一种全新的数据结构，即全局扩展频繁模式树。该树中 引入了复合结点，复合结点由若干元结点组成。同一复合结点内的元结点是逻辑或的关 系。这种数据结构简化了多维全局频繁模式验证过程中遍历树搜索匹配结点的过程，并 提高了挖掘结果的可视化程度。m d m a 算法还充分考虑了用户的偏好，用户可以自由 决定对哪几个属性进行挖掘。本算法具有网络通信量小，耗时少，简单易行，扩展性好 和考虑用户偏好的特点。 为了便于用户利用m d m a 算法进行分布式多维关联规则数据挖掘，本文开发了基 于w e b 的分布式关联规则挖掘系统，该系统不仅能够以可视化的方式显示挖掘结果， 还能够根据用户给定的前后件条件，交互式的产生相应的关联规则。 关键词：分布式数据库多维关联规则c u b e a b s t r a c t m u l t i d i m e n s i o n a la s s o c i a t i o nr u l em i n i n gi s8 1 1 i m p o r t a n t t a s ko fd a t a m i n i n g m e a n w h i l e ，w i t ht h er a p i dd e v e l o p m e n to fi n t e m e t ，d i s t r i b u t e dd a t a b a s eh a sb e e nb e c o m ea b r o a d l yu s e de n v i r o n m e n t t h e r e f o r e ，t h e r ei sa nu r g e n tn e e df o ram e t h o dt os o l v et h e p r o b l e mo fm u l t i - d i m e n s i o n a la s s o c i a t i o nm l em i n i n gi nd i s t r i b u t e dd a t a b a s es y s t e m t h ea u t h o rp r o p o s e st h em d m a ( m u l t i - d i m e n s i o n a ld i s t r i b u t e dm i n i n ga s s o c i a t i o nr u l e s ) a l g o r i t h mb a s e do na d v a n c e ds q lq u e r yi n t h i sp a p e r t h ea l g o r i t h mw o r k so nt o p o l o g i c a l s t r u c t u r eo fs t a r - s t y l en e t w o r k t h es t r u c t u r ec o n s i s t so fc e n t r a ls i t ea n dl o c a ls i t e s c e n t r a l s i t ec o n t r o l st h ep r o c e s so fm i n i n ga n ds h o w st h er e s u l t so fm i n i n g l o c a ls i t em i n e so u tl o c a l f r e q u e n ti t e m s e t sa n dc a l c u l a t e sl o c a ls u p p o r tc o u n tf o re v e r yg l o b a lc a n d i d a t ef r e q u e n t i t e m s e t t h ea l g o r i t h mu s e sc u b eo p e r a t o ri nn e ws t a n d a r ds q lt om i n eo u tl o c a lf r e q u e n t i t e m s e t s i tn e e d so n l yo n et i m e so fs c a n n i n gt h ed a t a b a s et og e n e r a t ea l lt h el o c a lf r e q u e n t i t e m s e t s t h e r ei sn on e e df o ri tt oc o n d u c tag r e a td e a lo fi t e r a t i o n st og e n e r a t ef r e q u e n t i t e m s e t s t h ea l g o r i t h mm a k e su s eo ft w ot i m e so fk n o w l e d g ef u s i o nt om i n eo u td i s t r i b u t e d f r e q u e n tp a t t e r n f i r s to fa l l ，g l o b a lc a n d i d a t ef r e q u e n ti t e m s e t sa r ec h o o s e no u tf r o ml o c a l f r e q u e n ti t e m s e t s i na d d i t i o n ，c e n t r a ls i t eu s e sg l o b a lc a n d i d a t ef r e q u e n ti t e m s e t st oe s t a b l i s h g l o b a le x p a n d e df r e q u e n tp a t t e r nt r e ea n dt h et r e ei ss e n tt oe v e r yl o c a ls i t e a f t e re v e r yl o c a l s i t er e c e i v e st h et r e e ，m e yw i l lc a l c u l a t el o c a ls u p p o r tc o u n tf o re v e r yg l o b a lc a n d i d a t e f r e q u e n ti t e m s e ta n dt h er e s u l t sa r es e n tt oc e n t r a ls i t e t h e nc e n t r a ls i t ea d d su pa l lt h er e s u l t s a n dp i c k so u tg l o b a lf r e q u e n ti t e m s e t s t h e r e f o r e ，n om a t t e rw h a tt h en u m b e ro ft h es i t ea n d t h es c a l eo ft h el o c a ld a t a b a s ei s ，t h ea l g o r i t h ma l w a y sn e e d so n l yt w ot i m e so fs c a n n i n gt h e d a t a b a s ea n do n l yt h r e et i m e so fn e t w o r kc o m m u n i c a t i o n s i no r d e rt oe f f e c t i v e l yc a r r i n go u t k n o w l e d g ef u s i o n , an e wk i n do fd a t as t r u c t u r ei s c r e a t e d i ti sc a l l e dg l o b a le x p a n d e d f r e q u e n tp a t t e r nt r e e ak i n do fc o m p o u n dn o d ei si n t r o d u c e di n t ot h et r e e c o m p o u n dn o d e c o n t a i n ss o m em e t a - n o d e sw h o s er e l a t i o n s h i pi s l o g i c a lo r a c c o r d i n g l y , t h ep r o c e s so f t r a v e r s i n gt h et r e ei ss i m p l i f i e di nt h ep r o c e s so fv a l i d a t i n gm u l t i d i m e n t i o n a lg l o b a lf r e q u e n t p a t t e r n w h a ti sm o r e ，i te n h a n c e st h ed e g r e eo ft h ev i s u a l i z a t i o no ft h er e s u l t so fd a t am i n i n g m d m aa l g o r i t h mt a k e su s e rp r e f e r e n c ei n t oa c c o u n t t h eu s e rc a nf r e e l yc h o o s ew h i c h a t t r i b u t e st ob em i n e d c o n s e q u e n t l y , i th a st h em e r i t so fl i g h tn e t w o r kt r a f f i c ，l o wt i m ec o s t ， m o r es i m p l i c i t y , b e t t e rs c a l a b i l i t ya n dc o n s i d e r i n gu s e rp r e f e r e n c e t h i sp a p e rd e v e l o p e dt h ed i s t r i b u t e dm u i t i - d i m e n t i o n a la s s o c i a t i o nr u l e sm i n i n gs y s t e m b a s e do nw e b t h es y s t e mc a n v i s u a l l ys h o w t h er e s u l t so fd a t am i n i n g m o r e o v e r , a c c o r d i n g t ot h ea n t e c e d e n ta n dt h ec o n s e q u e n tw h i c ht h eu s e rs e t s ，t h es y s t e mi sa b l et oi n t e r a c t i v e l y g e n e r a t er e l e v a n ta s s o c i a t i o nr u l e s k e yw o r d s ：d i s t r i b u t e dd a t a b a s e ，m u l t i - d i m e n s i o n a la s s o c i a t i o nr u l e ，c u b e 目录 第一章绪言1 1 1 研究背景及意义1 1 2 研究内容及创新点2 1 3 论文结构2 第二章关联规则挖掘算法3 2 1 关联规则挖掘3 2 1 1 基本概念及理论4 2 1 2a p r i o r i 算法4 2 2 多维关联规则5 2 3 分布式关联规则挖掘5 2 3 1 分布式关联规则挖掘的c d 算法5 2 3 2 分布式关联规则挖掘的f d m 算法6 第三章分布式多维关联规则挖掘算法m d m a 7 3 1 网络拓扑结构7 3 2 算法的基本思想8 3 3 局部频繁项集的生成9 3 4 全局频繁项集的生成1 4 3 5 算法性能测试2 5 3 6 算法特性分析2 7 第四章基于n e tr _ e m o t i n g 技术创建远程通信2 8 4 1 n e tr e m o t i n g 的含义2 8 4 2 n e t r e m o t 烈g 远程通信2 8 4 3 通道2 9 4 4 串行化2 9 4 5 构建远程对象2 9 4 5 1 远程对象的激活方式3 0 4 5 2 远程对象的实现、发布和获取3 0 4 6 n e tr e m o t i n g 分布式编程3 2 4 6 1 构建服务器端3 2 4 6 2 构建客户端3 3 第五章基于w e b 的分布式关联规则挖掘系统设计3 5 5 1 总体结构3 5 5 2 系统主界面设计3 8 5 3 挖掘分站点设置模块3 9 5 4 挖掘结果及显示模块4 0 5 5 关联分析模块4 2 第六章总结与展望4 5 6 1 总结4 5 6 2 展望4 6 参考文献4 7 发表论文和科研情况说明5 0 致谢5 1 第一章绪言 1 1 研究背景及意义 第一章绪言 如今随着各个部门信息化程度的不断提高，人们所拥有的数据量急剧增大，如何从这 些海量的数据中提取出人们感兴趣的知识己成为人们迫切需要的一项数据分析技术。 数据挖掘就是这样一种技术，它是近年来人工智能技术和数据库技术彼此结合快速 发展的结果。简单地说，数据挖掘就是从用户收集的大量数据中，提取出潜在的用户感 兴趣的知识。目前，数据挖掘已成为国内外信息决策领域的最热门的研究方向之一，并 且已经在工商界和学术界引起了从业人员广泛地关注。 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是数据挖掘领域中的一项重要技术，该项技 术可以提取出数据集中若干数据项之间的依赖关系。 与此同时，随着网络技术的发展，许多大型企业诸如跨国公司，它们的数据库在地 理上是分布的，于是就产生了分布式数据库。在分布式数据库中，各个数据库之间通过 网络彼此连接，它们在物理上是分散的，而在逻辑上是统一的。这种数据库的组织方式 可以有效解决集中式数据库负载过大的问题。 但是，由于分布式数据库中的数据分散存储以及分布式系统自身的特点，现有的关 联规则挖掘算法不能直接应用于分布式环境下。因此，要想对大量的分布式数据进行分 布式关联规则挖掘就需要一种专门的分布式关联规则挖掘算法。 目前，国内外数据挖掘领域的研究人员已经提出了一些分布式关联规则挖掘算法， 例如c d 1 j 和f d m 2 j 等。c d ( c o u n td i s t r i b u t i o n ) 算法是并行化的a 研o r i 【3 】算法，为了产生 频繁项集需要多次迭代且网络通信量大，其原因在于c d 算法不管候选项集是否频繁， 各个站点之间都要传递候选项集。因此，c d 算法不是一种具有良好可扩展性的分布式 关联规则挖掘算法。f d m ( f a s td i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n g ) 算法主要利用了局部 频繁项集和全局频繁项集之间的关系，采用了全局剪枝和局部剪枝的策略，减少了各站 点候选项集的数量，尽量减少扫描数据库的次数和网络通信量，在一定程度上提高了算 法的效率。但是，它的计算过程仍然很复杂。究其原因在于无论算法怎样提高效率，算 法始终需要对候选项集多次迭代才能生成频繁项集，因此需要多次扫描局部数据库，从 而导致各个站点之间频繁的网络通信。 由此可见，这些已有的分布式关联规则挖掘算法还存在一定的问题，其问题主要在 于算法的时间开销上面。 分布式关联规则挖掘的时间开销主要体现在两个方面，一是如何挖掘频繁项集，二是 网络的通讯量。实际上，第一个问题是产生第二个问题的直接原因。所以，如何高效地 生成频繁项集，对提高分布式关联规则挖掘算法的效率十分重要。【4 1 综上所述，分布式数据库可以有效解决集中式数据库负载过大的问题，同时关联规 第一章绪言 则挖掘能够透过数据的表层信息，对数据进行深层次的处理，从而获得数据之间内在的 有价值的关系。但是，由于已有的分布式关联规则挖掘算法都不同程度地存在自身固有 的局限性，且普遍存在算法计算过程复杂和时间丌销大的缺点。因此，迫切需要研究一 种全新的分布式关联规则挖掘算法，这种算法应该具有计算过程简单，网络通讯量低， 时间丌销小的特点，从而提高分布式关联规则挖掘的效率。 1 2 研究内容及创新点 在上节所述的研究背景之下，本文提出了一种基于高级s q l 查询的m d m a ( m u l t i d i m e n s i o n a ld i s t r i b u t e dm i n i n g a s s o c i a t i o nr u l e s ) 算法。此算法基于星型网络拓扑结 构，不但能够对分布式数据库中的数据进行关联规则挖掘，而且利用带有c u b e 运算符 的s q l 查询简单高效地从局部数据库中挖掘多维频繁项集，同时提出一种新的数据结 构一全局扩展频繁模式树来对全局候选频繁模式进行局部支持度计数。这种数据结构还 可以提高挖掘结果的可视化程度。算法采用两次知识融合技术从分站点的挖掘出的局部 频繁项集中提取全局候选频繁模式和全局频繁模式，在整个挖掘过程中，只需两次扫描 数据库和三次网络通信，所以可明显降低站点间网络通信量，降低算法的时间开销，使 挖掘过程得以简化。 m d m a 算法的创新之处： ( 1 ) 利用带有c u b e 运算符s q l 查询简单高效地挖掘多维频繁项集。 ( 2 ) 减少了扫描数据库的次数。各个分站点只需扫描两次数据库。 ( 3 ) 降低了站点间网络通信量。总站和分站之间只需进行三次网络通信。 ( 4 ) 构建了一种全新的数据结构一全局扩展频繁模式树来对多维频繁项集进行有效 验证。 ( 5 ) 考虑了用户的偏好。用户可以自由决定对哪几个属性进行挖掘。 ( 6 ) 挖掘结果的可视化。 同时，本文创建的基于w e b 的分布式关联规则挖掘系统，不仅能够从各个分站点 中挖掘出全局频繁项集并以可视化的树形结构加以显示，还能够根据用户给定的前件和 后件条件，交互式的产生相应的关联规则。 1 3 论文结构 本论文主体共分为六章。第一章介绍了课题的研究背景和研究内容及创新点。第二 章介绍了关联规则挖掘的概念和目前主要的分布式关联规则挖掘算法，比较了这些算法 的优缺点。第三章提出了一种基于高级s q l 查询的m d m a ( m u l t i d i m e n s i o n a ld i s t r i b u t e d m i n i n g a s s o c i a t i o nr u l e s ) 算法。为了构建本文提出的m d m a 算法的分布式结构，第四章 介绍了基于n e tr e m o t i n g 技术构建远程通信的方法。第五章是基于w e b 的分布式关 联规则挖掘系统的设计。第六章是对本文所完成的工作的总结和展望。 第二章关联规则挖掘算法 2 1 关联规则挖掘 第二章关联规则挖掘算法 关联分析( a s s o c i a t i o na n a l y s i s ) 技术用于提取海量数据集中数据项之间有价值的依 赖关系，这种依赖关系是对现实世界中若干事物之间的联系的表现，提取出来的关系称 作频繁项集( f r e q u e n ti t e m s e t ) 或着关联规贝, l j ( a s s o c i a t i o nr u l e ) 。 关联规则挖掘( a s s o c i a t i o nr u l em i n i n g ) 是关联分析技术中一项重要的方法，它可以 把数据集中数据项之间有价值的依赖关系挖掘出来，并给出这种关系在数据集中出现的 频繁程度和可信度。如果挖掘出的关联规则满足用户规定的最小支持度( 它表示了若干 数据项关联在一起需要满足的最低频繁程度) 和最小置信度( 它反映了若干数据项关联在 一起的最低可信度) ，那么就称此关联规则是有趣的。 举一个简单的例子，如果我们把某个商店中的全部商品的集合当作全域，每种商品 用一个布尔变量来表示，0 表示该商品未出现，1 表示该商品出现，那么每个购物篮则 可用若干布尔变量的值构成的布尔向量表示。例如表2 1 所示： 表2 1 购物篮数据的二元0 1 表示 t i d 电脑手机香皂啤酒毛巾茶叶 llloo0o 2l01110 30l11o1 4l1110o 511l001 表2 1 中每一行表示一个事务，这些事务称作购物篮事务( m a r k e tb t r a n s a c t i o n ) ，每个事务由一个唯一的标识t i d 和顾客购买的商品集合组成，每一个 对应一项，每个事务就是若干项的集合。例如表2 - 2 所示： 表2 2 购物篮数据的项集表示 t i d项集 1 电脑，手机) 2 电脑，香皂，啤酒，毛巾 3 手机，香皂，啤酒，茶叶) 4 电脑，手机，香皂，啤酒 5 电脑，手机，香皂，茶叶 对表2 1 中的数据进行分析，可以得到反映商品依赖关系的购买模式，这些模 以用关联规则的形式表示。例如，购买电脑也趋向于同时购买手机的购买模式可以 第二章关联规则挖掘算法 下关联规则表示： 电脑 手机) s u p p o r t = 2 ，c o n f i d e n c e = 6 0 】 2 1 1 基本概念及理论 设项集l = i j , i ：，i 。) 是由若干数据项组成的集合，项集i 上的每个元素称为项 ( i t e m ) 。事务数据库d 由一系列事务组成，每个事务都对应项集i 上的一个子集。 定义2 1 集( i t e m s e t ) i i 的支持度可以表示为 ( 2 - 1 ) 其中，i i 量i ，s u p p o r t _ c o u n t ( d ) 表示事务数据库d 中所包含的事务个数，s u p p o r t _ e o u n t ( i i ) 表示事务数据库d 中包含项集i ；的事务个数。 定义2 2 满足用户指定的最小支持度的项集称为频繁项集( f r e q u e n ti t e m s e t ) 。 定义2 3 关联规则i i 1 2 的支持度s u p p o r t ( i i = 1 2 ) n - j 表示为 s u p p o a ( i ij1 2 ) = s u p p o r t _ c o u n t ( i lu1 2 ) s u p p o r t _ c o u n t ( d ) ( 2 - 2 ) 其中，i l ，1 2 i ，i ln 1 2 = a ，s u p p o r t _ c o u n t ( i lu 1 2 ) 表示事务数据库d 中包含项集 i 。u i ：的事务个数。 定义2 4 关联规则i i 1 2 的置信度c o n f i d e n c e ( i i = 1 2 ) n - - j 表示为 c o n f i d e n c e ( i lj1 2 ) = s u p p o r tc o u n t ( i lu1 2 ) s u p p o r t _ c o u n t ( i i ) ( 2 3 ) 设在分布式环境下有若干个站点，各个站点上的局部数据库逻辑同构。局部数据库 中生成的频繁项集称为局部频繁项集。全局范围内确定的频繁项集称为全局频繁项集。 定理2 1 ：如果一个项集在某一站点是局部频繁项集，则该项集的所有子集在该站 点上也均为局部频繁项集。 定理2 - 2 ：如果一个项集是全局频繁项集，那么它至少在某一个站点上是局部频繁 项集。 2 1 2a p f i o f i 算法 a p f i o f i 算法【3 】是a g r a w a l 等人提出的关联规则挖掘的经典算法。这个算法基于以下 两个定理： 定理2 3 如果一个项集是频繁项集，那么它的所有非空子集也都是频繁项集。 定理2 4 如果一个项集是非频繁项集，那么它的所有超集也都是非频繁项集。 假设l k 为频繁k 项集的集合，c k 为l k 1 通过自身连接产生的候选k 项集的集合， 具体的a p f i o n 算法为： 输入：数据库，最小支持度 第二章关联规则挖掘算法 输出：频繁项集 ( 1 ) 扫描数据库找出频繁1 项集l 1 。 ( 2 ) 如果l k 的频繁项集的长度满足要求，则输出频繁项集，否则k 加l 并转到步骤 3 。 ( 3 ) 如果厶一。囝，则通过l k i 自身连接产生的候选k 项集的集合c k 。 ( 4 ) 如果c k 某个成员的k 1 项子集不在l k i 中，则删除该成员。 第二章关联规则挖掘算法 c d 算法有两个缺陷： 1 为了产生频繁项集需要多次迭代。 2 不管候选项集是否频繁，各个站点之间都传递候选项集的信息，从而导致网络通 信量大。 由于c d 算法有以上两点缺陷，所以当候选项集数量很大时，算法的执行效率不高， 并容易造成网络通讯量的过载。因此，c d 算法不是一种具有良好可扩展性的分布式关 联规则挖掘算法。 2 3 2 分布式关联规则挖掘的f d m 算法 为了减少各个站点间的通讯量问题d w c h e u n g 在1 9 9 6 年提出了f d m 2 ( f a s t d i s t r i b u t e da s s o c i a t i o nr u l e sm i n i n g ) 算法，该算法针对c d 算法站点间数据通信量大的缺 陷进行了改进，通过局部剪枝和全局剪枝两种剪枝技术，对候选项集进行剪裁。 f d m 算法的剪枝技术利用了局部频繁项集与全局频繁项集之间存在的一些有价值 的关系。只要最大限度地利用这些关系，就可以减少信息的传输量。 在分布式数据库中的站点之问，局部频繁项集与全局频繁项集之间有三个重要关系： 1 每一个全局频繁项集必定在某个站点是局部频繁项集。 2 每一个局部频繁项集的子集在本地站点也是局部频繁项集。 3 每一个全局频繁项集的子集在本地站点也是全局频繁项集。 如果一个项集在某个站点既是全局频繁项集又是局部频繁项集，可称该项集在该站 点是全局大的，一个站点所有的全局大的数据集作为该站点的候选项集的源数据集。每 个站点的源数据集是f d m 算法的计算的起点。 f d m 算法首先在每个站点中运行a p r i o r i 算法找出每个站点的候选项集，然后，在 每个站点对候选项集进行局部剪枝和全局剪枝，最后把经过裁剪的候选项集发往其它站 点，进行全局支持度计数。 f d m 算法的优点在于它减少了站点间的数据通信量，但是它仍然需要进行多次迭代 来产生全局频繁项集。 第二章分布式多维关联规则挖掘算法m d m a 第三章分布式多维关联规则挖掘算法m d m a 正如第二章所介绍的，分布式关联规则挖掘算法是在计算机网络环境下进行的，利 用网络在不同地点进行分布式计算，所以分布式关联规则挖掘的时间开销主要体现在两 个方面，一是如何挖掘频繁项集，二是网络的通讯量。 针对这些问题，本章提出了一种基于高级s q l 查询的分布式多维关联规则挖掘算 法，以下简称m d m a ( m u l t i d i m e n s i o n a ld i s t r i b u t e dm i n i n ga s s o c i a t i o nr u l e s ) 算法。该算 法采用星型网络拓扑结构，采用两次知识融合技术从分站点的挖掘结果中提取全局候选 频繁模式和全局频繁模式。由于利用s q l 新标准中的c u b e 运算符来从各个分站点的 局部数据库中挖掘局部频繁项集，使得在挖掘过程中不必通过多次迭代产生频繁项集。 因此，不管分布式站点数量为多少，各个分站点局部数据库规模如何，此算法始终只需 两次扫描数据库和三次网络通信就可产生全部的全局频繁项集。所以这种算法具有网络 通信量小，耗时少，简单易行和扩展性好的特点。 、 3 1 网络拓扑结构 m d m a 算法基于星型网络拓扑结构。中心站点负责控制挖掘过程并显示挖掘结果。 各个分站点负责产生局部频繁项集并把局部频繁项集发往中心站点。首先，中心站点把 用户设定的挖掘条件发往各个分站点，让各个分站点从本地局部数据库中挖掘出局部频 繁项集。然后，各个分站点把局部频繁项集发往中心站点。中心站点根据相关策略从各 个分站点发送过来的局部频繁项集中筛选出全局候选频繁项集，并根据筛选出全局候选 频繁项集构建全局扩展频繁模式树。此全局扩展频繁模式树会从中心站点发往各个分站 点。各个分站点接收到全局扩展频繁模式树之后，利用本地局部数据库中的数据计算各 个全局候选频繁项集的局部支持度计数并把计算结果发往中心站点。中心站点会对各个 分站点发送过来的计算结果进行汇总统计并根据统计结果找出全局频繁项集。m d m a 算法的网络拓扑结构如图3 - 1 所示。 第三章分布式多维关联规则挖掘算法m d m a l o c a ls i t e 3 2 算法的基本思想 l o c a ls i t e l o c a ls i t e l o c a ls i t e s i t e l o c a ls i t e 图3 1m d m a 算法的网络拓扑结构 本算法的基本思想是采用二次知识融合，即根据用户设定的挖掘条件，m d m a 算法 首先让各个分站点从本地局部数据库中挖掘出局部频繁项集。然后，各个分站点把局部 频繁项集发往中心站点。中心站点根据相关策略从从各个分站点发送过来的局部频繁项 集中筛选出全局候选频繁项集并根据筛选出全局候选频繁项集构建全局扩展频繁模式 树。此全局扩展频繁模式树会从中心站点发往各个分站点。各个分站点接收到全局扩展 频繁模式树之后，利用本地局部数据库中的数据计算各个全局候选频繁项集的局部支持 度计数并把计算结果发往中心站点。中心站点会对各个分站点发送过来的计算结果进行 汇总统计并根据统计结果找出全局频繁项集。最后，中心站点根据用户设定的挖掘条件， 从全局频繁项集中找出全局关联规则。 m d m a 算法的基本思想如下： 输入：局部数据库，最小支持度。 输出：全局关联规则 ( 1 ) 各个分站点利用c u b e 运算符扫描数据库( 各个分站点第一次扫描局部数据 库) ，生成局部频繁项集，并传送到中心站点( 各个站点间第一次网络通信) 。 ( 2 ) 中心站点按照一定策略生成全局候选频繁项集。 ( 3 ) 中心站点根据全局候选频繁项集生成全局扩展频繁模式树。 ( 4 ) 中心站点把生成的全局扩展频繁模式树发往各个分站点( 各个站点间第二次网 络通信) 。 ( 5 ) 在各个分站点利用本地数据对全局扩展频繁模式树进行局部支持度计数( 各个 分站点第二次扫描局部数据库) ，并把统计结果发往中心站点( 各个站点间第三次网络通 信) 。 第三章分布式多维关联规则挖掘算法m d m a ( 6 ) 中心站点根据各个分站点发送过来的全局扩展频繁模式树的支持度计数生成全 局频繁项集。 ( 7 ) 总站根据全局频繁项集生成全局关联规则。 3 3 局部频繁项集的生成 挖掘出局部频繁项集是整个分布式数据挖掘算法的重要步骤。为了高效地获得局部 频繁项集，m d m a 算法使用s q l 语句中的c u b e 运算符来挖掘局部频繁项集。 在s q l 语句中，g r o u pb y 子句可以根据某- - n 或者某几列的属性值将数据集划 分为多个分组。如果在g r o u pb y 子句中加入h a v i n g 子句，就可对g r o u pb y 子 句分组出来的结果进行筛选。 在s q l 语句中，c u b e 运算符能够对一个包含n 个属性( n 维) 的集合能够生成它的2 个子集。将该运算符用于s e l e c t 语句上的g r o u pb y 子句中，就可以产生对一个集 合的所有子集的分组统计结果。 通过在s q l 语句的g r o u pb y 子句中指定关键字w i t hc u b e ，并在该语句的选 择列表应包含维度列和聚合函数表达式，那么结果集中将包含维度列中各值的所有可能 组合，以及与这些维度值组合相匹配的聚集值。 下面举一个简单的例子。假设有一个简单的表c o m m o d i t y ，其内容如表3 - 1 所示。 表3 1c o m m o d i t y i t e mc o l o r q u a n t i t y p e n c i l b l u e1 2 4 p e n c i l r e d2 2 3 e r a s e rb l u e1 0 l e r a s e r r e d2 1 0 在查询分析器中输入如下的s q l 语句： s e l e c ti t e m ，c o l o r , s u m ( q u a n t i t y ) a sq t y s u m f r o mc o m m o d i t y g r o u pb yi t e m ，c o l o rw i t hc u b e 其查询结果如表3 - 2 所示。 第三章分布式多维关联规则挖掘算法m d m a 表3 - 2c o m m o d i t y 的查询结果 i t e mc o l o r q t y s u m e r a s e rb l u e1 0 1 0 0 e r a s e r r e d 2 1 0 0 0 e r a s e r 3 1 1 o o p e n c i l b l u e1 2 4 0 0 p e n c i l r e d2 2 3 0 0 p e n c i l 3 4 7 0 0 6 5 8 o o b l u e 2 2 5 o o r e d4 3 3 0 0 从这个表中，我们可以看出，通过在s q l 语句的g r o u pb y 子句中加入关键字 w i t hc u b e ，使得查询后所得到的数据集合刚好是关于i t e m 维度和c o l o r 维度的所有 组合。 下面我们着重考察下列各行。首先来看表3 2 中的第三行记录。 这一行显示了i t e m 维度中值为e r a s e r 的所有行的小计。对e r a s e r 维度返回了n u l l 值，表示该行所显示的聚集包括c o l o r 维度为任意值的行。 其次，再来看表3 2 中的第六行记录。 这一行显示了i t e m 维度中值为p e n c i l 的所有行的小计。 然后，再来看表3 2 中的第七行记录。 这一行显示了多维数据集的总计。i t e m 维度和c o l o r 维度的值都是n u l l ，表示两 个维度中的所有值都汇总在该行中。 最后，再来看表3 2 中的最后两行记录。 i l b l u e2 2 5 0 0 i il r e d l 4 3 3 0 0 i 这两行显示了c o l o r 维度的小计。这两行中的i t e m 维度值都是n u l l ，表示聚集数 据来自i t e m 维度为任意值的行。 下面再举一个相似的例子，但是在这个例子中，将使用h a v i n g 子句来从分组的结 果中筛选行。 假设有一个简单的表g r a d e ，其内容如表3 3 所示。 表3 - 3g r a d e 学号课程代号课程成绩学期 x 0 0 3 c 0 3 9 0 1 x 0 0 5c 0 29 32 x 0 0 3c 0 59 81 x 0 0 4c 0 48 72 x 0 0 2c 0 28 82 x 0 0 1c 0 l9 6l 在g r a d e 表中，按“学期 和“课程代号 分组求课程的平均成绩，并且用c u b e 运 第三章分布式多维关联规则挖掘算法m d m a 算符进行小计，s q l 语句如下： s e l e c t 学期，课程代号，a v g ( 课程成绩) a s 平均成绩 f r o mg r a d e g r o u pb y 学期，课程代号w i t hc u b e h a v i n ga v g ( 课程成绩) 8 0 其查询结果如表3 4 所示。 表3 - 4g r a d e 的奄询结果 学期课程代号平均成绩 1c 0 19 6 1c 0 39 0 lc 0 59 8 2c 0 29 0 2c 0 48 7 c 0 l9 6 c 0 29 0 c 0 39 0 c 0 48 7 c 0 59 8 从查询结果中，我们可以看出h a v i n g 子句对g r o u pb y 子句设置了条件，对分组的 结果进行了筛选。 如上所述，通过在s q l 语句中加入c u b e 运算符，能够对一个包含1 1 个属性( n 维) 的集合，也就是n 维数据集，生成该数据集的2 以个子集。将该运算符与s e l e c t 语句 上的g r o u pb y 子句结合使用，就可以产生对2 以个子集的分组统计结果。因此使得查 询后所得到的结果刚好是所选维度的所有组合，而这些组合又刚好是我们进行关联规则 挖掘所需要的一项集、二项集等。这说明c u b e 运算符能够对任意项集进行统计，即 c u b e 运算法可以求出各项集，如果对分组统计结果施以支持度的约束，就可以直接求 出多维表中满足最小支持度约束的频繁项集。通过这种方法就可以克服已有的分布式关 联规则挖掘算法扫描数据库次数多和各个站点之间网络通信频繁的缺点，只需对数据库 扫描一次，就可以产生我们所需要的候选频繁项集，从而省去了对候选项