（计算机应用技术专业论文）基于网格服务的分布式数据挖掘.pdf

摘要 分布式数据挖掘的主要目的是为了减少网络通信成本和利用地理上分布的计 算资源和存储资源。论文采用网格技术将地理上分布的计算资源合并，并进行分 布式数据挖掘，从而实现该目的 论文首先介绍了一些国内外的主要网格项目及商业产品，然后解释了一些网 格的基本概念。将网格和传统的分布式技术作以比较。阐述目前流行的网格体系 结构，给出了关联规则的基本概念及其相关度量参数的定义。分析当前流行的并行 和分布式数据挖掘算法及o d a m 算法。提出对o d a m 算法的以下三点改进，改 进一：在准备生成n 项侯选集之前，如果n 1 项全局频繁集的个数小于n , n 挖掘结 束。改进- - ：在挖掘n 项集前，判断n 是否大于最大的事务项目数，如果是，则结束 挖掘。改进三：在生成侯选集时，各站点分别计算一部分侯选集，然后合并为全 局候选项集。使用雷达数据集和c o n n e c t - 4 数据集对三点改进进行了验证，实验证 明改进是有效的。 最后在g t 3 环境下，详细地论述基于网格服务实现的o d a m 改进算法，并采 用雷达数据集和c o n n e c t - 4 数据集进行实验，验证了网格可以进行计算力合并的思 想。 关键字：分布式数据挖掘网格o d a m关联规则 g t 3 a b s t r a c t t h em a i np u r p o s eo fd i s t r i b u t e dd a t am i n i n gi st or e d u c et h ec o s to fn e t w o r k c o m m u n i c a t i o na n du s et h ec o m p u t i n gr e , c g ) b l - c a n ds t o r a g er e s o u r c ew h i c ha r e g e o g r a p h i c a l l yd i s t r i b u t e d t h i st h e s i sa d o p t s 鲥dt e c h n i q u et oi n c o r p o r a t et h i s g e o g r a p h i c a l l yd i s t r i b u t e dc o m p u t i n gr e s o u r c ea n de x e c u t et h ed i s t r i b u t e dd a t am i n i n g , a n dt h e nt h ep u r p o s ei si m p l e m e n t e d f i r s t ，t h i st h e s i si n t r o d u c e ss o m em a i nn a t i v ea n df o r e i g n 鲥dp r o j e e t sa n dg r i d c o m m o d i t y , t h e ne x p l a i ns o m eb a s i cc o n c e p to fg r i d n e x t , c o m p a r eg r i dw i t hs o m e t r a d i t i o n a ld i s t r i b u t e dt e c h n i q u e s i te x p a t i a t ep r e v a i lg r i da r c h i t e c t u r e ，a n ds h o wt h e b a s i cc o n c e p ta n dc o r r e l a t i v ep e r f o r m a n c ep a r a m e t e rd e f i n i t i o no fa s s o c i a t i o nr u l e s a n a l y z ed 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 ga l g o r i t h mo d a mb a s eo nr e s e a r c h i n g c u r r e n tp r e v a i lp a r a l l e la n dd i s t r i b u t e dd a t am i n i n ga l g o r i t h m t h et h e s i sp r o p o s e st h r e e i m p r o v e m e n t so f o d a ma l g o r i t h mw h i c hs h o w a sf o l l o w f i r s to n e ：i t j u d g ew h e t h e ro r n o tt h en u m b e ro fn - ! g o h a lf r e q u e n ti t e m s e t si sl e s st h a nnb e f o r eg e n e r a t i n g1 1 c a n d i d a t ei t e m s e t s ，i fy e st h e nt h em i n i n gi se n d s e c o n do n e ：j u d g ew h e t h e ro rn o tni s b i g g e rt h a nt h em a xn u m b e ro f i t e mc o u n ti nat r a n s a c t i o n ，i f y e st h e nt h em i n i n gi so v e e t h i r do n e ：e v e r ys i t ec a l c u l a t e sp a r tc a n d i d a t ei t e m s e t s ，a n dt h e nu n i t e st h i sl o c a l c a n d i d a t ef r o me v e r ys i t et om a k eag l o b a li t e m s e t s t h et h e s i su s er a d a rd a t as e ta n d c o n a e c t - 4d a t as e td oe x p e r i m e n t ，a n dt h er e s u l t sp r o v et h a tt h et h r e ei m p r o v e m e n t sa r e e f f e c t i v e ， f i n a l l y , t h et h e s i sd i s c u s st h ei m p l e m e n t so ft h ei m p r o v e do d a ma l g o r i t h mb a s e o ng r i ds e r v i c ei nd e t a i lw i t hg t 3 ，a n d d o e se x p e r i m e n tb ya d o p t i n gr a d a rd a t aa n d c o n n e c t - 4d a t a s e t ， e x p e r i m e n tp r o v e d t h ei d e at h a t g r i d c a l l i n c o r p o r a t e c o m p u t i n ga b i l i 够 k e y w o r d s ：d i s t r i b u t e d d a t am i n i n gg r i do d a ma s s o c i a t i o nr u l e s g t 3 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：益盔 一日期望垡：2 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名： 塑壹 耋堑釜 日期型堕2 ：兰翌 日期2 竺：! ! 兰! 第一章绪论 第一章绪论 1 1 引言 数据挖掘( d a t am i n i n g ) 指“从数据库或数据仓库中发现隐藏的、预先未知 的、有趣的信息的过程，该过程可以看作是知识发现中的一个核心的步骤”i l j 。 这门新兴的科学研究领域自从诞生后就成为研究的热点，至今方兴未艾。 随着人类科学研究的深入和观测工具的日新月异，各种数据也以指数形式增 长，况且这些数据大部分在地理上都是分散的，每个站点存储各自的日积月累的 本地数据。在这种数据上使用集中式数据挖掘来发现有用的模式通常是不可行的， 因为从不同的站点合并数据集到一个集中点将会引发巨大的网络通信成本。因此 出现了分布式数据挖掘，它是数据挖掘研究的一个活跃的子领域。 网格是构筑在i n t e r a c t 上的一组新兴技术和基础设施，实现互联网上所有资源 的全面连通，包括计算资源、存储资源、通信资源、软件资源、信息资源等，其 目标是在动态变化的、广域分布的异构虚拟组织间实现协同资源共享。多领域的科 学和工程的问题求解。基于网格的这些特点，分布式数据挖掘与网格的结合使得 能够对广域分布的海量数据进行高效的处理、分析和挖掘，给科学研究领域、经济 领域和社会生活带来新的发现和巨大的价值。 1 2 1 国外网格研究现状 1 2 国内外网格研究现状 随着计算机网络和基础计算技术的发展，构造大规模的高性能网络已经成为可 能。从2 0 世纪9 0 年代开始，各国政府相继启动一些重大科研计划。主要有： 欧洲数据网格：“欧洲数据网格”涉及到欧盟的2 0 几个国家，是一种典型的 “大科学”应用平台。它主要针对高能物理应用，解决海量数据的分解存储和处 理问题，突破地理局限，允许分布在世界各地的工作者共享海量数据和贵重设备， 共同开展科学研究。整个开发过程中，有超过2 0 0 名科学家和研究者参与，项目总 投资为9 8 0 万欧元。 英国政府，企业共投资1 9 0 亿英镑的重大网格项目e s c i e n c e 计划：e s c i e n c e 是关于科学关键领域的全球协作以及下一代基础设旌。核心研究计划主要面向四 个方向：e s c i e n c e 科学家和工业界使用的基础中间件、支持各个研究理事会项目 所需的基础设施、e - s c i e n c e 和网格方面的国际合作、与工业界合作开发的工业级 网格中间件【3 】。 德国网格d e u t s c h l a n d g r i d d 。g r i d ：该项目致力于将网格计算应用于科学研究， 2 基于网格服务的分布式数据挖掘 它将多个机器连接在一起执行复杂科学研究中的计算任务。 美国自然科学基金会支持的p a c i 计划：目标是试验未来1 肛1 5 年美国社会的信 息基础设施。 美国能源部的a s c i 计划：以l o sa l a m o s 、s a n d i a 和l i v e n n o r e 三个国家实验室作 为超级节点，至2 0 0 4 年达到每秒1 0 0 万亿次的计算能力。 美国国防部建立的h p c m p 网络：供全国各地军事科技人员进行国防研究和开发 使用。它包括4 个主计算中心，1 3 个分中心，数十个远程中心。1 9 9 8 年4 个主计算 中心共装备了2 3 套计算机，速度为2 0 亿5 0 0 万亿次。 网格物理网络g r i p h y n ：资助经费为1 1 9 0 美元。该项目由芝加哥大学的i a n f o s t e r 教授和佛罗里达大学的p a u l a v e r y 教授领导，为期5 年，其目标在于使用网格技术 处理和解释由高能物理和天体物理实验中产生的海量数据。 荚围航空航天局n a s a ) 的信息动力网格( i n f o r m a t i o np o w e rg r i d ，i p g ) ： i p g 的曰杯是为国家航空航天局科学研究任务提供持续、自r 靠的计算动力源。该网 格的用户可从任何地方访问分布的异构资源。 亚太地区网格a p g r i d ：a p c , 一d 是a s i ap a c i f i cg r i d 的简称，它是亚太地区一个 的合伙网格计算项目。a p g r i d 是一个开放社团协作组织，并不仅限于一些发达国 家。在2 0 0 4 年5 月底，已有来自1 5 个国家( 包括澳大利亚、加拿大、中国、日本、 美国等) 共4 9 个组织加入a p g r i d 。 开本在2 0 0 3 年启动了投资1 0 0 亿日元的“国家研究网格”和投资2 0 亿日元的“商 务网格”。 韩国的网格计划之一是n * g r i d ，2 0 0 2 2 0 0 6 年的五年问将投资3 5 0 0 万美元。 各国政府也投巨资研究网格系统或原型，其中以下几个系统较为成功。 g l o b u s ：g l o b u s - l - 程是多个研究机构合作的研究成果。g l o b u s 的研究分三步： 首先开发计算网络需要的高级工具与基本技术；然后利用这些技术工具构建大规 模的计算网格；最后在构建的网格上运行实际的应用，获得性能结果，评估计算 网格的效率，并提出改进网格性能的方法。g l o b u s 通过服务包提供不同服务，使用 不同高级工具支持资源管理服务、信息服务、安全服务、远程数据访问服务、通 信服务和执行管理服务等【2 1 。目前全球许多用户利用g l o b u s _ e 兵包创建网格和丌发 嘲格应用。 l e g i o n ：l e g i o n 主要目标是使并行任务在工作站簇上高效的运行。它支持基于 认证的用户安全服务、面向对象的虚拟文件服务和m m p s 通信服务。 n e t s o l v e ：n e t s o l v e 系统由网络上一些松散连接的机器组成。这些机器可以位 于任何网络，并且可以被不同的机构和组织管理。 c o n d o r ：c o n d o r 是一个高吞吐量的计算环境。其目的是在长时间内提供大的 第一章绪论 吞吐量。 m o l ：m o l 是n o r t h r h i n e - w e s t p h a l i a n 的研究专家组实现的元计算机的雏形。 m o l 不是基于特定的编程模式工作，它被设计为一个包含多种软件模式的开放的、 可扩展的软件系统，每一个软件模块都完成诸如资源管理、工作控制、任务通信、 用户接口等任务 g l o b e ：g l o b e 是运行在现有主操作系统和网络协议之上的中间件超级计算系统， 支持灵活的程序执行，使用一个单一的对象模型和体系结构，并使用类对象来抽 象执行细节。 随着网格研究在学术界的日益火热，信息产业界的大公司也相继公布与网格 相关的研究计划。惠普推出t e s p e a k 、b 服务平台；i b m 用它的w e b s p h e r c 平台和 一系列中间件实现w c b 服务；微软通过其n e t 计划和c 撑语言实现万维网服务；s u n 则通过o p e nn e t w o r ke n v i r o n m e n t ( s u no n e ) 计划和j a v a 平台来实现它。另外， i b m 宣布，将投资4 0 亿美元，启动一个全公司的“网格计算创新计划”；s u n n 在2 0 0 0 年9 b 公布了其网格引擎软件。i b m 公司部署了一个内部研究网格，以便于分散在 美国、以色列、瑞士、日本等地的i b m 研究人员共享计算资源。医药、化工、通信、 电子、汽车等领域的一些大公司，如p f i z e r ( 辉瑞) 、e r i c s s o n ( 爱立信) 、h i t a c h i ( 日 立) 、b m w ( 宝马) 、u n i l e v e r ( 联合利华) 、g l a x ow e l l c o m e ( 葛兰素威康) 、 s m i t h k l i n e ( 史克必成) 等，都已经开始构造和使用内部网格i z j 。 世界最大的企业软件公司甲骨文公司于2 0 0 3 年9 月在旧金山发布了最新数 据库产品o r a c l e1 0 9 ，其中g 代表网格 s u p p o r t ( y ) ； ( 2 ) 若y 是频繁集，则x 也是频繁集： ( 3 ) 若x 不是频繁集，则y 也不是频繁集； 关联规则的集合： 事务数据库在给定最小支持盯和最小可信任度，时的关联规则集合定义为： r ( d ，盯，y 产 x j y l x ，y i , x n y = 0 ，) 【u y f ( d ，盯) , c o n f i d e n c e ( x j y ) ， 关联规则挖掘就是在给定项目集i ，事务数据库d ，最小支持度o r 和最小可信任度 ，的情况下，求解r ( d ，口，y ) 的过程。 发现关联规则需要经历如下两个步骤： ( 1 ) 找出所有频繁项集。 ( 2 ) 由频繁项集生成满足最小信任度阀值的规则。 其中挖掘和识别出所有的频繁项集是该算法的核心，占整个计算量的绝大部分【1 9 1 。 基于网格服务的分布式数据挖掘 4 2a p r i o r i 算法 a p r i o r i 算法1 2 川是关联规则中的经典算法，有很多算法都是在a p f i o h 的基础上 改进而来的。 众所周知，由m 个项目形成的不同的项集的数目可以达到2 r n 1 个，尤其是在 海量数据库中，这将是一个n p 难度的问题。为了避免计算所有项集的支持度( 实 际上频繁项集只占很少一部分) ，a p f i o f i 算法引入侯选频繁项集的概念。若侯选频 繁k 项集合记为c k 濒繁k 项集的集合记为l k ，m 个项目构成的k 项集的集合为c ， 则三者之间满足关系l k c _ c k c _ 或。根据定理1 ，可得构成侯选频繁项集所遵循的 原则是“频繁项集的子集必为频繁项集”。所以在计算支持度时只计算侯选频繁项 集的支持度，因此在一定程度上减少了计算量。侯选频繁k 项集的集合c k 是指由 已知的k 1 项频繁集生成的有可能成为频繁项集的k 项集组成的集合。 具体实现过程： 1 通过单趟扫描数据库d 计算出各个l 项集的支持度，从而得到频繁1 项集构成 的集合l 1 。 2 连接步：为了产生频繁k 项集构成的集合l k ，预先生成一个侯选频繁k 项集的集 合c k 。侯选频繁项集的集合由j o i n 运算得到。 若 p , q el k 1 p = p l , p 2 ，p k - 2 ，p k - l , q = q3 ，q 2 ，q k - 2 q k - l ，并且当l k 1 时，p 尸q i ，当 i = k 一1 时，p k j l q k - l , 则p u q - p 1 ，p 2 ，t l , - 2 ，p k i ，q k 1 是c k ( 侯选k 项集的集合) 中的 元素。 3 剪枝：由于c k 是l k 的超集，可能有些元素不是频繁的。c k 很庞大时会带来巨大 的计算量，为减少c k 的规模，根据定理l 的对于k 项集有如下性质：任何非频 繁的k 1 项集必定不是频繁k 项集的子集。所以，当侯选集k 项集的某个k l 项集不是l k i 中的成员时，则该候选频繁项集不可能是频繁的，可以从c k 中删 除。 4 通过单趟扫描数据库d ，计算c k 中各个项集的支持度。 5 将c k 中不满足最小支持度的项集删除，形成频繁k 项集构成的集合l k 。 通过迭代循环，重复上述步骤2 5 ，直到不能产生新的频繁项集的集合时为止。 a p f i o f i 算法求出所有满足最小支持度的频繁项集。 a p r i o r i 算法如下： 第四章分布式数据挖掘算法 2 1 ( 1 ) l t = 频繁l 项集，； ( 2 ) f o r ( k = 2 ；l k q o ；k 抖) d ob e g i n ( 3 ) c k = a p r i o d _ g e n ( l k t ) ；新的候选频繁项集 ( 4 )f o ra l lt r a n s a c t i o n st dd ob e g i n ( 5 ) c t = s u b s e t ( c k ，t ) ；t 中包含的候选频繁项集 ( 6 ) f o r a l lc a n d i d a t e s c ec t d o ( 7 ) c c o u n t + + ；支持度加1 ( 8 ) e n d ：，结束本此数据库扫描 ( 9 ) l k = c ec k l c c o u n t - m i n s u p ；，支持度大于最小支持度阀值的k 项候选集构 影成了k 项频繁集。 ( 1 0 ) e n d ；整个算法结束 ( 1 1 ) a n s w e r = uk k ； a p r o r i _ g e n o 函数以h 1 为参数，用h 1 和l k i 进行连接操作，主成一个超集c k 作 为候选频繁项集。 ( 1 ) i n s e r t i n t o c k ( 2 ) s e l e c t p q ，p 【2 】，p k - l l , p k 】 一 ( 3 ) f r o mk j p ，l k - l q ( 4 ) w h e r ep 1 l = q 1 , p k - 2 = q k - 2 l , p k - 1 2d ob e g i n ( 2 ) h l = l k 中规则的后件，该规则的后件中只有一个项目 ； ( 3 ) c a l la p _ _ g e m u l e s ( 1 k , h 1 ) ； ( 4 ) e n d ； ( 5 ) p r o c e d u r ea p _ g e n r u l e s ( 1 k ：频繁k 项集，h m ：m 个项目的后件的集合) 基于网格服务的分布式数据挖掘 ( 6 ) i f ( k m + 1 ) t h e nb e g i n ( 7 ) h m + l - a p r i o r i g e n ( h m ) ； ( 8 ) f o r a l lh m + l h m + ld o b e g i n ( 9 )c o n f = s u p p o r t ( 1 k ) s u p p o r t ( i k - h m + i ) ； ( 1 0 ) i f ( c o n f - m i n c o n f ) t h e n ( 1 1 )o u t p u t 规则( 1 k - h m + 1 ) j h m + 1w i t hc o n f i d e n c e = c o n fa n ds u p p o r t = s u p p o r t ( 1 k ) ； ( 1 2 ) e l s e ( 1 3 ) d e l e t eh m + lf r o mh m + l ； ( 1 4 ) e n d ； ( 1 5 ) c a l la p _ g e n r u l e s ( 1 k ，h m + 1 ) ； ( 1 6 ) e n d ； a p r i o r i 算法时间消耗的主要症结反映在两个方面，一是由于对海量数据库的多趟 扫描，另一个是用j o i n 产生候选频繁项集。 4 3 0 d a m 算法 在一些数据挖掘文献中有很多并行或分布的a r m ( a s s o c i a t i o nr u l e m i n i n g ) 算法。然而大多数是为共享内存并行环境设计的。根据种类和每个算法的 实现，可将现有的算法分为两组：并行a r m 和d r a m 4 3 1 并行算法 并行a r m 算法分为数据并行和任务并行算法。在前者中，算法在不同的节点 划分数据集；在后者中，每个站点独立的执行任务但必须访问同一个完整的数据 集。 计数分布式算法( c d ) 【6 1 是一个简单的数据并行算法。它在一个并行环境中使用 连续的a p r o r i 算法并假定数据集在不同的站点是水平分割的。c d 算法的优点在于 在处理器| 日j 不交换数据元组。它仅仅交换计数。在第一次扫描中，根据它本地分 区的项目，每个处理器产生本地侯选项集。每个阶段的算法通信费用是o ( i c t n ) ，i c i 和n 分别是侯选集大小和数据集数目。 数据分布算法( d d ) 【6 i 是一个基于任务并行算法，它在处理器问分割侯选集。每 个处理器负责计算本地存储的作为数据库中所有事务的子集的侯选集。每个处理 器必须扫描分派给其他处理器的事务分区，同时也要扫描存储在本地的事务分区。 同c d 算法相比，它因此产生了很高的通信费用并执行效果很差。 第四章分布式数据挖掘算法 4 3 2 分布式算法 d r a m ( d i s t n b u t e da s s o c i a t i o nr u l em i n i n g ) 从不同的地理分散的 数据集中发现规则，然而，这些数据集合之间的网络连接没有并行环境快，所有 分布式挖掘通常致力与最小化通信成本。 f d m ( 快速分布式挖掘) 算法【5 j 从不同站点分区的分布数据中挖掘规则。在每个 站点，f d m 找出本地支持度计数并剪掉所有不频繁本地支持度计数，在完成本地 剪枝后，每个站点广播所有留下的侯选集的支持度计数给所有其他站点。接着它 决定一个大项目集是否是全局频繁并从这些全局的频繁项目集中产生侯选项集。 f d m 比c d 好在它将通信成本减少为0 ( i c p i n ) ，i c p l 和n 分别是大侯选项目集 和站点数目。与c d 相比，当位于不同站点的不相关的侯选集数目越大时，f d m 产生侯选项目集越少f d m 的信息优化技术要求一些函数来决定轮流检测站点， 当每个站点的本地频繁集很大时，这将产生额外的计算成本。另外，与起始站点 不同，每个检测节点必须向其他远程节点发送信息来找到一个项集的全局支持度 计数，当存在大量的远程节点时，就会增加消息的大小 4 3 3o d a m 的基本设计原理 o d a m ( o p t i m i z e dd i s t n b u t e da s s o c i a t i o nr u l em i n i n g ) 算法1 2 l j 通过最小化侯 选集来获得更好的性能它把注意力集中在两个主要的d a r m 问题上通信和同 步。如果可以减少通信成本，将大大提高d r a m 算法性能。同步就是迫使所有的 参与站点等待一段时间直到全部的频繁集都产生完成如果计算支持度花费的时 间越多，则每个站点等待的时间越长。因此减少计算侯选频繁支持度的时间，将 会使同步时间相应缩短。 在减少通信成本方面，有两种信息优化技术方法可以考虑，直接的和间接的 支持度计数交换。每个方法都有不同的目的，优点和缺点，第一种方法相互交换 频繁集支持度计数来产生全局的频繁集( c d 和f d m ) 。其他所有的站点共享一个公 共的全局的具有相同支持度的频繁集，所以在不同参与站点产生的规则具有相同 的信任度。这种方法侧重于规则的确切性和正确性。 第二种方法只发现信任度大于阕值的关联规则。它目的是为了减少通信成本， 所以它不考虑一个项集的确切的全局支持度。所以，如果一个用项集部分支持度 产生的规则，将可能会在最终形成的规则集中出现相互矛盾的情况。为维护一个 规则的正确性和紧密性，o n a m 采用第一种方法。 另外，我们知道a p r i o r i 算法有很多缺陷，其中之一就是它产生一个i i 项集时， 需要扫描数据库n 次，如果具有相同项集的事务没有同时装入到内存孛，它不能 基于网格服务的分布式数据挖掘 识别这些数据。例如，如果一个数据集有1 0 个相同的事务，在每次遍历中，a p d o f i 算法不仅枚举这些相同的侯选集1 0 次而且更新这些侯选项集的支持度1 0 次。另 外，直接装入原始数据到内存中找到相同事务的的效果可能不太理想( 与数据集 有关) ，医为每个原始数据集的事务舍有频繁和不频繁项目。 为克服这些问题，在第一次扫描后，o d a m 不再从原始数据集中产生支持度计 数。这是因为在第一趟扫描中不频繁的项集在后面的扫描中不会产生出频繁项目 集。为在以后的扫描中高效率地产生侯选集支持度计数。在第一趟扫描后，o d a m 除去所有的不频繁的项目，将新的事务放入内存中。这种技术不仅减少了平均事 务项目数，而且减少了数据集大小，所以可以在内存中放置更多的事务，数据集 中的项数可能很大，但只有一小部分满足支持度阀值。另外，不频繁项目集的数 目与支持度阀值基本同比例增长。 同时，当从每个事务移除不频繁1 项集，找到相同事务的概率就变大了。让我 们来看表4 1 中示例事务数据库，如果装载这个数据集合到内存，只能找到相同的 事务a b c d ，表4 2 所示然而，在消除了每个事务的不频繁项( 支持度为5 0 ，即 项目e ) 后的事务数据集中将会发现更多的相同事务，如表4 3 所示。这种技术不仅 减少了事务中的项目数也找到更多的相同事务，从而完成对数据库的合并和约简 操作。 裹4 1 原始数据库 襄42 合并了事务的数据库 事务序号 项目 1 a b c d 2b c 3 a b 4a b c d e 5a c d 6 a b e 7c d e 8 a d 9b c e 1 0 a b c d 事务序号项目 l 。1 0a b c d 2b c 3 a b 4a b c d e s a c d 6 a b e 7c d e 8a d 9b c e 表4 3 除j e 频繁单项集 后并合并了事务的数据库 事务序号硬且 1 ，1 0 a b c d 2 , 9b c 3 , 6 a b 5 a c d 7 c d 8a d o d a m 算法是一个数据并行算法，各站点有同样的关联规则挖掘任务。 图4 1 显示了o d a m 的伪代码，o d a m 首先像a p d o d 算法一样为每个站点计算1 、 第四章分布式数据挖掘算法 项集的支持度。它接着广播这些1 项集到其他站点并发现全局频繁集。接着每个 站点广播这些项集给其他站点。然后，每个站点继续产生2 项集并计算支持度。 同时o d a m 也从每个事务中消除所有的全局不频繁1 项集，并插入新事务( 没有 不频繁项目) 到内存中，在插入新事务时，检测该事务是否已在内存中，如果是， 该事务的计数加1 。否则，将增加一个事务并计数为1 。在每个站点产生侯选2 项集的支持度计数后，o d a m 产生全局频繁2 项集。接着遍历内存( 其中的事务 没有不频繁2 项集) 并产生各自的侯选项集支持度计数。下来，通过广播该站点 的支持度，产生全局的频繁项集。 n f = n o n - f r e q u e n tg l o b a l1 - i t e m s e t f o ra l lt r a n s a c t i o nt e d f o ra l l2 - s u b s e t sso f t i f ( s c 2 )s 鲫p + + ； t f d e l e t en o n f r e q u e n t _ i t e m s ( t ) ； t a b l e a d d ( t 1 s e n d _ t or e c e i v e r ( c 2 ) ；发送局部2 项集 广在r e c e i v e r 处计算全局支持度，并发送全局频繁项集搴， f 2 f r e c e r v ef r o mr e c e i v e r ； c 3 = ( c a n d i d a t ei t e m $ e t ； t = t a b l e g c m c 曲bo ；k - 3 ； w h i l c ( c 净0 ) f o ra l lt r a n s a c t i o nt e t f o ra l lk - s u b s e t sso f t i f ( s e c js s u p + + ； k + + ： s e n d _ t o _ r e c e i v e r ( c j ； ，产生k + l 项侯选集， c a + i f c a n d i d a t ei t e m s e t ； 图4 1 0 d a m 的伪代码 基于网格服务的分布式数据挖掘 信息交换优化 在c d 算法中，每个局部站点产生支持度计数并向其他站点广播来让每个计算 全局频繁项集。所以，从每个站点播出的信息为( n 一1 ) + i c l ) 。所有的信息大小为： 萨2 荟以川c n 是站点总数，c 是侯选项集数。与c d 对比，o d a m 将侯选项集的支持度计数发 送到一个站点，该站点计算全局频繁项集。将发送本地支持度的站点叫s e n d e r , 产 生全局频繁项集的站点叫r e c e i v e r 例如，有3 个站点，两个广播其本地支持度计数 给第三个，第三个站点负责产生全局频繁集。从一个s e n d e r 到一个r e c e i v e r 站点的 信息广播总数为l l c i _ 一旦r e c e i v e r 站点产生出了全局频繁项集，它将向所有s e n d e r 广播。从r e c e i v e r 播出的信息总数为( n - 1 ) i f e i 计算总信息( s e n d e r 和r e c e i v e r 之和) 的公式如下： n = 站点数，c = 侯选项集，r 全局频繁项集。 例如，有3 个站点s 1 ，s 2 ，s 3 。在第一次遍历后，假设频繁1 项集为 氏b ，c 在下次 遍历时，每个站点都有侯选项集 a b ，a c ，b c ，假设s 1 ，s 2 为s e n d e r , s 3 为r e c e i v e r , 在第二遍历结束后，s 1 的支持度计数是( a b ，a c ，b c ) ，s 2 是 a b ，a c ，b c 。这些将 会被发送到r e c e i v e r 站点s 3 。它将产生本此遍历的全局频繁项目集合。如果本次遍 历的全局频繁项集是( a b ，b c ，站点s 3 将广播这些项集给所有s e n d e r 站点。计算总 的通信量，发现o d a m 算法仅广播1 0 次，而c d 广播1 8 次。 有人可能会说这种优化在参与的站点总数增加时，会在r e c e i v e r 站点处形成瓶 径。r e c e i v e r 站点从所有s e n d e r 接收与c d 算法中同样数目的侯选集。例如，对于 四个站点，每个有四个侯选集，在c d 算法中每个站点将发送自己的四个侯选集给 其他站点并接收1 2 ( 3 4 ) 个从其他站点来的侯选集。在o d a m 中，r e c e i v e r 站点 也接收1 2 个侯选集，并广播最大的全局频繁项集给s e n d e r 。另外，在大多数情况 下( 即当全局频繁项集小于侯选项集) ，r e c e i v e r 发送更少的频繁项集给s e n d e r 站 点。 当前趟全局频繁项集的数目很大时，侯选集数目也变大。如果有5 0 0 个1 项 频繁集，侯选集将为1 2 4 7 5 0 。然而所有这些侯选项集不都是全局频繁的。基于这 种原理，如果每个站点只发送它本地频繁项集面不是整个侯选集给r e c e i v e r , 将进一 步减少信息交换量。 第四章分布式数据挖掘算法 4 4 改进的o d a m o d a m 算法是对a p r i o d 算法的改进。它在挖掘中逐渐减少数据集的大小，同 时对站点之间的信息交换进行了大幅度的优化。但在其他方面基本上是一个分布 式的a p r i o r i 算法，待改进的地方还很多。本节对o d a m 进行下列优化。 4 4 1 基于频繁集个数的挖掘结束判断 在生成侯选集之前判断挖掘是否可以结束。在准备生成n 侯选集之前，如果 n 1 项全局频繁集的个数小于n 则挖掘结束，而不用先生成n 项侯选集，然后再判 断其n 个n 1 项子集是否都是频繁集来判断该n 项集可否作为侯选集。甚至需要判 断1 1 项侯选集的集合是否为空来决定挖掘是否结束。原因是n 项集的n 1 项子集有 n 个，如果n - 1 项全局频繁集的个数小于n ，则没有一个1 1 项集有1 1 个n 1 项子集。 所以所有n 项集都会被剪掉，从而结束挖掘。这种方法适用于数据集较小，事务 中项目数较大的情况。 4 4 2 基于最大的事务项目数的挖掘结束判断 根据事务的最大项目数，判断是否进入下一轮挖掘。在扫描单项集后，记录 下所有事务的最大项目数t l e n m a x 。在挖掘1 1 项集前，判断n 是否大于t l e n m a x 。 如果是，则结束挖掘；否则，继续。原因是事务数据库中没有项目数为n 的事务， 所有n 项侯选集合的支持度都为零。这种方法适合于数据集较大，而事务最大项 目数较小的数据源。如下面的雷达源识别数据集就是一个事务项目数最小为3 ，最 大为6 ，而有5 0 0 0 条样本的数据集。 4 4 3 增加任务并行 增加了任务并行的o d a m 算法。o d a m 算法的生成候选集是r e c e i v e r 站点生 成并整理，然后广播给其他站点，在r e c e i v e r 生成侯选集时，其他站点都处与等待 状态，未能充分利用计算资源。本文对此部分进行了改进，由各站点分别计算一 部分侯选集，然后由一个站点统一将所有侯选集整理并发给其他站点。 在基于a p r i o r i 算法的所有算法中，连接和剪枝操作也是非常耗时的。本文在 实现时，根据两台计算机的能力各计算一部分，然后合并。假设有a ，b ，c ，d ，e ，f 六 个n 1 项集。可能的1 1 项集有a b , a c , a d ，a e ，a f ( 此处a b 表示由项集a 和b 连接 产生的n 项集，而非2 n 2 项集，其他类似1 等，假设两台计算机各分担5 0 ，则可 算出任务分割点为： 基于网格服务的分布式数据挖掘 喊。p ，西1 d 为分割点的序号，从0 开始。k 为n - 1 项集的个数。 当k = 6 时，d = 2 ；即从项目c 分开。图4 2 显示了任务分割情况。 。矽坳 共瞅连接撬作 站点l 共6 次连接攘作 站点2 图4 。2 任务分割 因为索弓l 号必须为整数，所以不可能做到任务量完全相等。 4 4 4 举例 假设有如表4 4 所示的数据集 表4 4 事务数据库 事务d事务的项目集 t 1 a b ，e t 2b d 1 3b c i 4a b d 1 5a c 1 6b c 1 7丸c t 8 凡b ，c e 1 9 a ，b 。c 在支持度为2 0 的情况下，其中3 项频繁集有 a b ，c ， 凡b ，e 两个，用改 进1 判断，不用进行4 项侯选集的生成，直接可以结束。因为4 项目侯选集合要 求至少有4 个3 项频繁集。 改变上述数据集，向t 1 中增加项目c ，t 3 中增加e ，t 5 中增加e 。则3 项频繁 第四章分布式数据挖掘算法 集有 a ，b ，c ， a ，b 。e ， 凡c ，e ， b ，c ，e ) 四个，4 项频繁集有 a b ，c ，e ) ，而该数 据集的事务最大项目数为4 ，此时使用改迸方法2 ，直接结束挖掘，不用生成5 项 侯选集。 4 4 5 实验及结果分析 本文该部分的实验环境如下： 1 硬件：两台p 1 4 g 1 2 8 内存，通过局域网连接 2 软件：l i n u xr e dh a t 9 0 ，g l o b u st o o l s3 0j a v as d k 3 环境建立：基于l i n u x 平台的网格环境搭建过程比较复杂，详细过程见参考 文献 2 2 2 3 1 1 2 4 1 。 采用雷达辐射源测试仿真数据集，数据集含5 0 0 0 个样本，每个样本l o 个属性。 进行了下列实验： 实验一：将基于网格服务编写的o d a m 算法部署在这两台计算机组成的网格环境 中。运行并记录运行时间和所挖掘出的规则。 实验二：将基于网格服务编写的o d a m 算法部署在一台计算机上，运行并记录运 行时间和所挖掘出的规则。 实验三：将基于网格服务编写的基于4 4 2 的o d a m 的改进算法部署在这两台计 算机组成的网格环境中。运行并记录运行时间和所挖掘出的规则。 实验四：将基于网格服务编写的基于4 4 3 的o d a m 的改进算法部署在这两台 计算机组成的网格环境中。运行并记录运行时间和所挖掘出的规则。 表4 5 实验结果 输入参数输出参数 实验编号支持度信任度样本数输出属性 运行时间关联规则条数 实验一 8 8 0 5 0 0 0雷达型号 1 8 7