（计算机应用技术专业论文）基于cluster结构的并行关联规则挖掘算法研究和实现.pdf

华中科技大学硕士学位论文 摘要 ( 数据挖掘中的一个重要问题是关联规则挖掘。由于进行挖掘的数据库规模都是极其 庞大的，而且以更快的速度在增长，因此迫切需要设计高效和可扩展算法来进行关联规 则挖掘。并行化成为了解决现有关联规则挖掘方法串行瓶颈问题、提供可扩展的数据规 模和改进响应时间的一个有效途径。川 数据库挖掘与并行处理技术互相渗透、互相结合，成为数据挖掘发展的重要特征， 也是并行处理技术应用发展的一个重要方面。将并行处理技术与关联规则挖掘技术相结 合，在研究了c l u s t e r 结构上的并行关联规则挖掘算法基础上，设计了p h r 算法( p a r a l l e h y b r i d r e c o l l e c t i o n a l g o r i t h m ) 和p h r g 算法( p a r a l l eh y b r i dr e c o l l e c t i o n g l o b a l a l g o r i t h m ) 两个并行关联规则挖掘算法，并在曙光3 0 0 0 进行设计实现和性能分析。 p h r 算法和p h r - g 算法是基于c l u s t e r 体系结构设计的关联规则挖掘算法。算法采 用了混合数据分布模式，有效地发挥了垂直和水平两种数据分布方式在不同迭代中效率； 算法使用一定方法，通过记忆在“l 迭代后产生的全局信息，使k 迭代中使用已载的全 局信息，从而更高效地进行候选集操作和全局修剪，生成更小的候选集，减小消息传递 量；p h r - g 算法还按频繁集的等价类进行数据重划分，以利用数据垂直分布的本地计算 性进行异步计算，消除了同步费用，提高算法的并行效率：在p h r g 算法的动态负载平 衡策略中，实现在k 3 的迭代中大颗粒负载平衡；并对算法进行了相关性能分析。 关键词：数据挖掘；关联规则；c l u s t e r 结构；数据分布；数据划分；负载平衡 华中科技大学硕士学位论文 a b s t r a c t a ni m p o r t a n tp r o b l e mo fd a t am i n i n g ( d m ) i sa s s o c i a t i o nr u l e sm i n i n g ( a r m ) t h e d a t a b a s e si n v o l v e di nd m a r e v e r yl a r g e w h a tm o r e ，t h es i z eo f t h e d a t a b a s e sw i l lg r o wa tf u l l s p e e d t h e r e f o r e ，i ti si m p e r a t i v e t od e s i g ne f f i c i e n ta n ds c a l a b l ea l g o r i t h m st om i n ea s s o c i a t i o n r u l e sp a r a l l e l i s mi sas o l u t i o nt or e l i e v ec u r r e n ta r m m e 血o d sf r o mt h es e q u e n t i a lb o t t l e n e c k t op r o v i d es c a l a b i l i t yt om a s s i v ed a t a b a s ea n dt oi m p r o v er e s p o n s et i m e t h ec o m b i n a t i o no ft h ep a r a l l e lp r o c e s s i n gt e c h n i q u ea n dd m t e c h n i q u eb e c o m e sn o t o n l y am a i nc h a r a c t e r i s t i co fd mt e c h n o l o g yb u ta l s oam a i nd i r e c f i o no fa p p l i c a t i o n d e v e l o p m e n ti np a r a l l e lp r o c e s s i n gt e c h n o l o g y b yc o m b i n i n gp a r a l l e lp r o c e s s i n gt e c h n i q u e w i t hd m t e c h n i q u e ，p a r a l l e la s s o c i a t i o nr u l e s ( p a r m ) m i n i n g i sd i s c u s s e db a s e do nc l u s t e r a r c h i t e c t u r e t o wp a r ma l g o r i t h m s 一p a r a l l e li q y b r i dr e c o l l e c t i o na l g o r i t h m ( p h r ) a n d p a r a l l e lh y b r i dr e c o l l e c t i o n g l o b a la l g o r i t h m ( p h r g ) a r ed e s i g n e d t h et w o a l g o r i t h m sa r e i m p l e m e n t e d a n da n a l y z e db a s e do n p a r a l l e lp r o g r a m m i n g e n v i r o n m e n ti nd a w n i n g3 0 0 0 p h ra l g o r i t h ma n dp h r ga l g o r i t h ma r ed e s i g n e df o rc l u s t e rs y s t e m ，w h i c hi sa s h a r e d n o t h i n ga r c h i t e c t u r e a l g o r i t h m su s eh y b r i dl a y o u tp a t t e r n t h eh y b r i dl a y o u tc a nt a k e a d v a n t a g e o ft h em e r i to ft h eh o r i z o n t a ld a t a l a y o u ta n d v e r t i c a ld a t al a y o u ti nd i f f e r e n t p a s s e s ar e c o l l e c t i o nm e t h o di su s e di np h r a l g o r i t h ma n dp h r - ga l g o r i t h m ，w h i c hr e c o r d st h e g l o b a li n f o r m a t i o ng e n e r a t e di nk - 1p a s s t h eg l o b a li n f o r m a t i o ni su s e db y k p a s sc o m p u t e t o i m p r o v et h ec a p a b i l i t yo fc a n d i d a t es e to p e r a t i o n sa n dg l o b a lp r u n i n gt og e n e r a t es m a l l e r c a n d i d a t es e ta n dr e d u c et h ea m o u n to f m e s s a g e i np h r ga l g o r i t h m ，t h ee q u i v a l e n c e c l a s so f f r e q u e n ti s u s e dt os e tt or e a l l o c a t et h ed a t a b yt h i sm e a n s ，a s y n s c h r o n i z a t i o nc o m p u t ei s a d o p t e db ye f f i c i e n t l yu s i n gt h el o c a lc o m p u t e t r a i to ft h ev e r t i c a ll a y o u t a sar e s u l to ft h i s o p t i m i z a t i o n ，t h ep a r a l l e le f f i c i e n c y o fa l g o r i t h m si s i m p m v e d ad y n a m i c t o a db a l a n c e s c h e m ei sa l s op r o p o s e dt oi m p l e m e n t a t i o nt h ec o a r s e g r a i n e dl o a db a l a n c e t h ep e r f o r m a n c e o f a l g o r i t h m s i sa n a l y z e d k e yw o r d s ：d a t am i n i n g ：a s s o c i a t i o nr u l e ：c l u s t e ra r c h i t e c t u r e ：d a t al a y o u t ：d a t a p a r t i t i o n ：l o a db a l a n t e i i 华中科技大学硕士学位论文 1 1 引言 1 绪论 数据库技术是计算机科学技术中发展最快的领域之一，也是应用最广的技术之一。 随着成千上万的大型数据库被广泛地应用在商业、政府和科研等部门，使得人们生成、 收集和存储数字化数据能力极大提高，计算机网络技术的迅速发展使得世界各地的数据 成为共享资源，当今世界面l 晦着各种原始数据的爆炸性增长。一方面，不断迅速增长和 变动的数据量已经使得传统的手工分析成为令人望而却步的事情。另一方面，大量的数 据资源也为人们从数据库中发现有用知识提供了极好的机遇，因为在较低层的原始数据 埋藏着较高层有用信息。因此能智能化地或者至少是能半自动化地帮助人们将原始数据 转化成有用信息的新技术和新工具就成为极其迫切的需要。在社会需要迅猛推动下，知 识发现技术( k d d ：k n o w l e d g ed i s c o v e r yi nd a b b l e ) 迅速发展成为一个日益重要的研 究领域f l 。j 。数据挖掘( d a t am i n i n g ) 是k d d 中最关键、最核心的技术之一，也是k d d 技术难点所在。数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。数据挖 掘使数据库技术进入了一个更高级的阶段，它不仅能对过去的数据进行查询和扫描，并 且能够找出过去数据之间的潜在联系，从而促进信息的传递 4 - 6 。 并行处理技术已经成为现代计算机的关键技术之一，其推动力来自实际应用对高性 能、低价格和持续生产力f | 益增长的需求。近十几年来，并行计算机系统的发展十分迅 速，很多大规模并行计算机系统( m p p ) 已经投入市场，基于网络的机群并行计算环境 也开始出现。m p p 和机群计算环境为高性能知识发现的实现带来了希望。很多研究者认 为，在具有数千个处理器的并行计算机上建立高性能知识发现系统是可行的，并行知识 发现系统有希望成为未来的高性能知识发现系统【7 1 。 数据挖掘中的一个重要问题就是关联规则挖掘( m i n i n g a s s o c i a t i o n r u l e s ) 。关联规则 挖掘发现有趣的规则，为决策支持提供有效模式，被广泛地应用于客户购买模式、财政 预测、医疗诊断等多个应用领域。随着计算机应用领域的迅速扩大和数据规模的不断增 长，对关联规则挖掘操作的规模可扩展性和效率要求越来越高。为了解决可扩展性和效 率问题，并行关联规则挖掘成为研究的重点。这方面是因为关联规则挖掘所处理的数 据都是海量数据，这类数据库通常有上百个属性和数百万个记录，并且数据表之| 剐包含 复杂的关系，这必然导致数据挖掘过程中搜索维数和搜索空阃的激增：另一方面，随者 华中科技大学硕士学位论文 计算机网络技术的发展和企业需求的扩张，把企业网和国际互联网上的众多数据源连接 成一个大型的分布、异构的数据库。数据库的巨大规模、异地分布及关联规则挖掘的计 算复杂性要求建立并行分布关联规则挖掘算法【l 。因此将并行处理技术与关联规则挖掘 相结合，充分开发多处理器结构的优势进行关联规则挖掘并行处理，才能够满足新的应 用需求，从而提供比传统大型机系统( m a i n f l a m e ) 高得多的性能价格比和良好的可扩 展性。 1 2 课题的来源，目的和意义 知识发现是目前国际上数据库和信息决策领域的最前沿研究方向之一。在知识发现 技术的研究中，数据挖掘技术占有十分重要的地位，体现了统计学，模式识别、机器学 习与数据库技术的高度结合，也是k d d 技术关键难点之一口】。关联规则挖掘是数据挖掘 技术中的重要问题，而并行关联规则挖掘是并行处理技术和关联规则挖掘技术结合的产 物，充分开发多处理器结构的优势进行关联规则挖掘并行处理，满足关联规则数据规模 不断增大和数据异地分布需求，从而提供比传统大型机系统高得多的性能价格比和良好 的可扩展性。 我们在国家8 6 3 项目( 8 6 3 3 0 6 一z d 一0 1 7 ) 的资助下，进行了关联规则挖掘算法和并 行关联规则挖掘算法的研究。研究工作分为三个阶段：第一阶段，在对关联规则的基本 知识和相关知识进行学习，对关联规则挖掘中著名算法进行分析研究，对其性能进行评 价分析和比较。然后对具有代表性并行关联规则挖掘算法进行研究和分析，对算法的i o 费用、通信和同步费用，存储费用等并行性能进行评价；第二阶段，利用第一阶段所学 习的关联规则的挖掘技术，结合数据分布、负载分配等并行处理技术，设计了并行关联 规则挖掘算法p h r 和p m t g ，并在曙光3 0 0 0 上进行实现：第三阶段对p h r 和p h r - g 算法进行实验。通过变动系统的节点数，节点负载，配置、数据库规模和支持度来获得 不同的实验结果，并分析实验结果。! 本文主要设计了两个基于c l u s t e r 结构的并行关联规则挖掘算法p h r 和p h r g 。其 中涉及到的侯选集产生、频繁集生成、规则生成等关联规则挖掘技术和数据划分、o 、 优化、消息优化等并行处理技术，这些都是构造一个并行关联规则挖掘的关键技术和难 点，直接影响整个算法的性能。其研究的目的有两个：( 1 ) 深入研究和分析并行关联规则 挖掘算法，提高算法的可扩展性和减少消息通信等方面在理论上有所突破；( 2 ) 设计可行 的并行关联规则挖掘算法，将其运用于曙光机系统上。本课题的研究成果将直接运用于 曙光机上，加快曙光系列服务器的推广应用。本项目是并行处理应用的重要领域，也是 数据挖掘技术中新的研究方向。 华中科技大学硕士学位论文 = = = 皇! = = = = ! ! ! ! ! ! ! ! = ! ! ! = ! = = = = = = = = = = = = = = = = ! = ! ! = ! ! 鼍= ! ! ! ! ! = ! ! = ! ! ! ! ! = = ! 1 3 国内外研究现状 关联规则挖掘问题最初是针对超级市场的事务数据而提出的，目的是发现超市顾客 - 的未知购买模式。顾客购买模式的关联规则挖掘通常被称为经典关联规则挖掘问题【6 1 。 关联规则挖掘研究工作一方面集中在对经典关联规则挖掘问题进行算法改进，另一方面 ， 则致力于对其进行各种扩展，包括提出新的关联规则挖掘问题，扩展频繁项目集法以适 应新问题等等。与此同时，在以上两方面寻求并行的，分布式的和增量式的高效算法。 其它相关工作还包括研究关联规则挖掘算法与s q l ，数据仓库等的集成。 对经典关联规则开采算法改进研究主要包括：改进频繁项目集生成过程的计算效率， 减少对事务数据库的扫描次数以改进i o 开销，以及引进抽样技术( s a m p l i n g ) 来改进i o 歼销和频繁项目集生成过程中的计算开销等等。具体来说：p a r k 等人提出了一个基于 h a s h 的d h p “i 算法。s a v a s e r e 等人提出了对整个事务数据库进行划分的p a r t i t i o n 控】算法。 t o i v o n e n 等人提出了基于抽样的s a m p l i n g i t 3 1 算法。b r i n 等人提出了对候选项目集进行动 态支持度计数的d i ce ”1 算法。b a y a r d o 等人提出了“向前看”( “l o o k a h e a d ”) 的 m a x m i n e 一”】算法。提出了针对关联规则挖掘的封闭性而改进的o n l i n e 算法f 】，使用户 可以在任何时候调整支持度。 对经典关联规则开采问题进行扩展的研究主要包括：s r i k a n t 等人以及h a n 等人讨论 了一般化的关联规则开采问题( g e n e r a l i z e d a s s o c i a t i o nr u l e s ) 【1 7 】。a g r a w a l 等人提出了事 务之间的序列模式( s e q u e n t i a lp a t t e n s ) 1 8 - ”】开采。m a n n i l a 等人提出了在事件序列之间开 采频繁插曲( f r e q u e n te p i s o d e s ) 2 0 “】。s r i k a n t 等人提出了数量化的关联规则开采问题 ( q u a n t i t a t i v e a s s o c i a t i o n r u l e s ) 【2 “。s r i k a n t 等人以及n g 等人讨论了带约束的关联规则开 采问题( a s s o c i a t i o n r u l e s w i t h c o n s t r a i n t s ) p “。l u 等人提出了n 一维交易间关联规则开采 问题州一d i m e n s i o n a li n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e s ) 2 4 】。 寻求并行的、分布式的和增量式的高效算法的研究主要包括：a g r a w a i 等人提出了 c o u n td i s t r i b u t e d ，d a t ad i s t r i b u t e d ，c a n d i d a t ed i s t r i b u t e d 三个基于无共享( s h a r e dn o t h i n g ) 并行算法【2 5 】。c h e u n g 等人提出了分布式算法d m a 2 6 1 和f d m 【2 7 】。c h e u n g 等人首先提出 了一个关联规则增量式更新问题，并提出了相应的增量式更新算法口”。 并行关联规则挖掘技术的研究在以方面取得较大的进展： 、 1 并行处理体系结构研究 并行关联规则挖掘系统的体系结构与其依赖的并行计算机的体系结构密切相关，并 行计算机硬件构成方式对挖掘并行处理系统的效率有着决定性的影响。按照计算机硬件 资源的共享程度束划分，建造挖掘并行处理系统有三种多处理机模型，即：共享主存的 s m ( s h a r e d m e m o r y ) 结构，共享磁盘的s d ( s h a r e d d i s k ) 结构和无共享的s n 华中科技大学硕士学位论文 ( s h a r e d n o t h i n g ) 结构【2 9 t 3 0 k 目前的挖掘并行处理系统研究主要是围绕着s n 结构进行 的。基于s n 结构的并行关联规则挖掘算法有a g r a w a l 等人提出了c o u n t d i s t r i b u t e d ，d a t a d i s t r i b u t e d ，c a n d i d a t ed i s t r i b u t e d 和c h e u n g 等人提出了分布式算法f d m 等算法。 2 并行关联规则挖掘算法 许多研究表明，实现关联规则挖掘的并行处理，可以充分地发挥多处理机的并行性， 大大地提高挖掘的效率和扩大挖掘的数据库的规模。并行关联规则挖掘算法的研究主要 以串行关联规则算法为基础，围绕数据划分、数据分布、消息通信、负载平衡等方面进 行。 数据划分决定算法的静态负载，对数据进行重新调整，以利用和消除数据偏移对算 法性能的影响。数据分布包括水平数据分布和垂直数据分布。数据分布将决定是否进行 数据库扫描，由于数据库规模的原因，数据库扫描的次数将大大影响算法的性能。消息 通信是基于s n 结构的算法进行同步和生成全局数据的途径，消息通信费用是影响算法 性能的一个重要因素。由于关联规则挖掘算法的迭代性和动态性，负载平衡也成为并行 关联规则挖掘一个重要方面，但现在并行算法基本上都是使用数据划分形成的静态负载， 对动态负载平衡研究较少。 自从a g r a w a l 等人于1 9 9 3 年引入关联规则挖掘的问题以来，关联规则开采引起了学 术界和工业界等各方面的广泛关注。许多项目和系统都将关联规则作为一个研究和开发 的重要目标。其中包括i b m a l m a d e n 研究中心的i n t e l l i g e n t m i n e r ，美国s t a n f o r d 大学的 m i d a s ，b e l l 实验室的s e r e n d i p 等等。与此同时，国内也进行了大量的研究工作，但 是国内尚未见成熟的数据挖掘产品的报道。 1 4 并行处理的体系结构 并行系统根据指令流和数据流的不同分为单指令多数据流( s i m d ) 系统和多指令多 m 。b ip m口 m p p 蛰 一p ； 图1 1s m 并行结构图1 2s d 并行结构图1 3s n 并行结构 数据流( m i m d ) 系统。m i m d 系统的研究一直以三种并行计算结构为基础：共享主存 4 m m po p f ，、 华中科技大学硕士学位论文 储器结构( s h a r e d m e m o r y ，以下简称s m 结构) 、共享磁盘结构( s h a r e d d i s k ，以下简 称s d 结构) 和无共享资源结构( s h a r e d n o t h i n g ，以下简称s n 结构) 1 2 9 , 3 0 。 s m 并行结构由多个处理机、一个共享主存储器和多个磁盘存储器构成。多处理机 。和共享主存储器由高速通信网络连接，每个处理机可直接存取一个或多个磁盘存储器。 s m 并行计算机结构如图1 1 所示。b m 3 7 0 多处理机系统和多处理机系统是具有 。s m 结构的典型并行计算机系统。 s d 并行结构由多个具有独立主存储器的处理机和多个磁盘存储器构成。每个处理 机都可以读写任何磁盘存储器。s d 结构并行计算机如图1 2 所示。m m 的s y s p l e x 系 统就是一个基于s d 结构的并行计算机系统。 s n 并行结构由多个处理结点构成。每个处理结点具有自己独立的处理机、主存储 器和磁盘存储器。多个处理机结点由高速通信网络连接。s n 结构并行计算机如图1 3 所 示。具有s n 结构的并行计算机系统包括n c u b 系统、较新的s m p c i u s t e r 系统和曙光 3 0 0 0 系统等。 s m 和s d 结构的缺点是系统的可扩充性不好，干扰较大。s m 结构的处理机个数由 于技术方面的限制不可能很大，否则，处理机访问共享内存的同步限制会使得整个系统 性能明显下降；s d 结构对于数据的并发读写操作不十分有效 3 ”。相比之下，s n 结构 中的共享资源最少，因而干扰也最小：s n 结构还具有对互联网带宽要求较低，易于扩 充规模和并行程序设计比较容易等优点。s n 结构成为现今最为流行的并行结构。基于 s n 结构的优点和关联规则挖掘算法自身的特点，本文采用c l u s t e r 类的s n 结构进行算 法实现。 1 5 并行处理技术 并行处理技术涉及到两个关键技术：线性加速( l i n e a r s p e e d u p ) 和线性扩展( l i n e a r s c a l e u p ) 。前者的含义是，使用n 倍多的硬件以1 n 的时间完成同一项任务：后者的含义 是，用r l 倍多的硬件以同样的时间完成n 倍多的任务【3 2 】。形式上： 加速( s p e e d u p ) = t l t 。 、 扩展( s c a l e u p ) = n t l t 。 其中，t t 为在单处理机上执行一项任务所需要的时间：t 。为同一任务在f 台处理机 上执行所需要的时间；t 。为在n 台处理机上执行n 倍多的任务所需要的时间。当加速为 t l 时称为线性加速；当扩展为l 时称为线性扩展。 华中科技大学硕士学位论文 影响线性加速和线性扩展的主要因素有四条： 1 启动时间( s t a r t u p ) ：启动一个并行操作所需要的时间。如果同时启动许多个进 程，则启动时间很容易影响实际的运算时间； 2 偏斜( s k e w ) ：各并行处理部件所负担的原始数据量或工作量严重不均衡。这时， 服务时间取决于并行系统中负载最重的处理部件所花的时间： 3 干扰( d i s t u r b ) ：当访问共享资源时，每个进程都会对其它进程构成影响，减慢 其他进程的执行速度。进程越多，这种干扰越明显。 4 通信的开销( c o m m u n i c a t i o n ) ：当各个结点进行数据交换和信号同步时，通信开 销随着规模扩大而增加。 1 6 论文的内容及组织 本课题研究基于c l u s t e r 结构的关联规则挖掘并行处理技术，重点讨论了并行关联规 则挖掘算法的研究、设计和实现技术。研究内容归纳为两方面： 1 并行关联规则挖掘算法的研究 在关联规则挖掘算法中，频繁集的生成是一个十分重要的问题在并行关联规则挖 掘算法中，整个数据库被划分到各个结点上，频繁集的生成是通过各个结点进行并行候 选集局部计数，通过消息传递产生全局频繁集。在这一个程中，数据分布、消息通信、 全局修剪和负载平衡对算法的性能有很大影响。在本文中提出了一种混合数据分布方法， 这种分布方法减少了数据库的扫描次数，提高了算法可扩展性。由于各个结点只有局部 数据库的信息，全局数据的信息只有在消息通信后才可获得。但在k 次迭代中，各个结 点已经获得频繁缸，一项集，也就是矗次迭代的全局信息，本文提出了利用舡j 次全局信 息进行k 次迭代的全局修简来减少消息传递量。本文还通过动态改变候选集的大小来减 少候选集搜索空间提高搜索效率。文中还研究了数据划分和负载动态平衡问题。 2 基于c l u s t e r 结构的并行关联规则挖掘算法的实现和性能分析 并行联规则挖掘算法设计包括数据结构的设计和消息设计。算法的性能分析包括缓 冲区管理，数据划分，算法的并行性等方面，特别进行算法的可扩展性分析算法，最后 与现有的算法进行了比较。 本文共分六章。 第一章为概述，介绍了课题的来源、目的、意义及国内外研究概况。 第二章介绍了并行关联规则挖掘算法的研究背景和所涉及的一些相关概念。 第三章是本文的重点，主要研究和设计了基于机群结构的并行关联规则挖掘算法 华中科技大学硕士学位论文 p h r 算法和p h r g 算法。 第四章介绍并行关联规则挖掘算法的实现和性能分析。 第五章是本课题的总结和展望。 华中科技大学硕士学位论文 2 关联规则挖掘算法分析 2 1 关联规则挖掘的定义 2 1 1 问题的提出 数据挖掘中的一个重要问题就是关联规则挖掘( a s s o c i a t i o nr u l e sm i n i n g ) 。而推动关 联规则挖掘迅猛发展的是大型零售组织所面临的决策支持问题。计算机和相关技术的发 展已经使得超级市场能够收集和存贮数量巨大的销售数据。一条这样的销售数据记录通 常包括与某个客户相关的交易( t r a n s a c t i o n ) 日期、所购物品项目( r e m s ) 等等。通过对大量 交易数据进行分析就能获得相关有用的客户购买模式信息，从而提高商业决策( 例如如 何选择进货品种，货物摆设策略等) 的质量 3 3 1 。关联规则其它的应用还包括附加邮递、 目录设计、追加销售、仓储规划以及基于购买模式对客户进行划分和数据清理( “】等等。 在事务数据中进行关联规则挖掘的问题是由a g r a w a l 等人于t 9 9 3 年在文献f 3 3 1 中首 先提出的。关联规则的挖掘问题可形式化描述如下： 设卢 i l ，i 2 ，i 。 是由m 个不同的项目组成的集合。 给定一个事务数据库d ，其中的每一个事务t 是i 中一组项目的集合，即t c i ， t 有一个唯一的标识符t i d o 若项目集x c _ i 且x c _ t ，则事务t 包含项目集x 。一条 关联规则就是形如xjy 的蕴涵式，其中x 量i ，y i ，xn y = 中。 关联规则xjy 成立的条件是： 1 具有最小支持度s ，即事务数据库d 中至少有s 的事务包含uy ： 2 具有最小置信度c ，即在事务数据库d 中包含彳的事务至少有c 同时也包含 y 。 关联规则的挖掘问题就是要发现所有满足用户指定的最小支持度s 和最小可信度c 的关联规则。为了获得有意义的结论，必需有足够的数据量。于是这些应用中的数据库 都是极其庞大的，由于大型零售组织等数据库本身就有分布性，因此利用高性能并行计 算机，设计关联规则挖掘并行算法来高效地进行挖掘成为研究热点。 在文献 3 3 1 a 篇开创性论文中，关联规则的挖掘采问题被分成两个子问题： 1 首先找出所有的频繁项( f r e q u e n ti t e m s e t s ) ，也就是所有支持度在用户指定的最小 支持度以上项目集； 2 然后利用频繁项目集生成满足最小可信度的关联规则。 华中科技大学硕士学位论文 由于第二个子问题较为直观，较为简单 集，对每个非空子集a ，考察规则a j ( f a ) 输出此规则。 对每个频繁项目集f ，计算其所有非空子 若该规则的置信度大于最小置信度c ，则 因此对于关联规则挖掘的研究主要都集中在如何高效地生成频繁项目集。为了发 现所有的频繁项目集，需要对事务数据库d 进行多趟( p a s s ) 扫描。在第趟扫描中，对 所有在事务数据库中出现的单个项目进行支持度计数，然后确定其中哪些单个项目最终 是频繁的，即满足最小支持度。在后续的k 趟中，首先以在k - i 趟中所发现的频繁项目 集r 作为一个种子集，然后利用这个种子集来生成k 趟潜在的频繁项目集。这些潜在的 频繁项目集被称为候选项目集q ( c a n d i d a t er c m s e t s ) 。紧接着，扫描数据库d ，计算这 些候选项目集g 的支持度，根据计算出的支持度最后确定其中哪些候选项目集是女趟的 频繁项目集。重复上述过程直到频繁项目集凡为空。上述由a g r a w a l 等人首先提出的， 后来被c c a g g a r w a l 和p s y u 称为频繁项目集法( l a r g ei t e m s e ta p p r o a c h ) 【”i 。该方法 的瓶颈是将候选项目集确定为频繁项目集，因此算法高效的关键在于高效地生成较小的 候选项目集，也就是尽可能不生成和计数那些不可能成为频繁项目集的候选项目集。 2 1 2 经典关联规则挖掘算法 r a g r a w a l 等人紧接着在1 9 9 4 年的文献 3 6 1 中提出了著名的a p f i o f i 算法及其变依 a p f i o n 算法通过引入种全新的修剪策略，极大地减小了待确定的候选项目集的规模口 这一修剪策略基于如下基本性质：“一个频繁项目集的任一子集必定也是频繁项目集，o a p f i o f i 算法同时还引入了一种基于h a s h 树的有效数据结构来对候选项目集进行支持度 计算。a p f i o f i 算法在性能上大大超过了a i s 算法。a p f i o f i 算法也成为现在关联规则挖掘 算法中经典算法，成为关联规则算法性能分析的基准。 a p n o f i 算法假定每一条事务中包含的所有项目都已经按照它们的字典顺序排序。一 个项目集中所含项目的个数被称为这个项目集的长度( s i z e ) ，而一个长度为k 的项目集就 称为一个k 项目集( k - i t c m s e t ) 。一个项目集中的所有项目也保持字典顺序。记号 i 1 】z 2 i k 被用来表示一个缸项目集i 包含项目1 ，i 【2 i l k ，并且有1 1 1 2 】 2 的迭代计算效率。对k 2 的迭代仍然使用水平数据分布，并使用事务修剪等方式减小搜索空间提高计算效率。 在算法的收集阶段，p h r 算法使用了缸j 迭代产生的全局信息进行更高效地全局修剪， 生成比f d m 算法小的候选集，消息传递次数也为o ( 月) 次。p h r g 算法在七2 迭代 使用和p h r 算法一样消息传递策略，而在k = - 3 是进行了数据重划分，将候选集的全局 t i d 列表按照缸，前缀的等价类划分到各个计算结点。在k 2 的迭代中，各个计算结点 异步计算，不再需要在每次迭代后进行同步。p h r g 算法还提出了一个动态负载平衡算 法，实现在k 3 的迭代中大颗粒的负载平衡。 本章将对p h r 算法和p h r g 算法进行详细论述。 3 1 相关定义和定理 在无共享的并行挖掘环境中，共有n 个挖掘计算结点，记为p f f i = l ，2 ，n ) 。将 数据库d 根据选定的划分策略划分为n 块，记为d j ( i - l ，2 ，n ) ，d = - d ，u d 2 u u d n 。d 为全局数据库，而d j 为局部数据库。每个计算结点p 负责其相应的局部数据库 d 。并行关联规则挖掘任务就是在分布的环境中高效地找出满足用户指定支持度m i ns u p 的频繁集f 。 以下是与p h r 并行关联规则挖掘算法相关的几个定义与定理： 定义1 项目集在局部数据库d ：( i = l ，2 ，n ) 中的支持度s ，即在局部数据库 d ，中包含x 的事务的条数，称为x 的局部支持度，用xs i 表示。 定义2 项目集在数据库d 中的支持度s ，即在数据库d 中包含x 的事务的条 数，称为x 的全局支持度，用xs 表示。 定义3 对于项集正若x s i 二，m ms u p l d 涨i - 1 ，2 ，n ) ，则称z 是相对于d 。 的局部频繁项集斥若x 中的元素为k 个，即闵瑚，则称x 为数据库d ，的局部频繁舡 项集，。 定义4 对于项目集x ，若xs r a i ns u p l d l ，则称x 是全局频繁项集f ，简称频 繁项集。若x 中的元素为k 个，即l x l = k ，则称x 为频繁“项集f k 。 定义5 若项目集x 在d ，( i = l ，2 ，n ) 是局部频繁项集，且它还是全局频繁集， 即xs i m ms u p i d ：l ，且x s 一m i ns u p i d i ，则称x 在d f ( i = l ，2 ，n ) 是稠密 的，用日表示。u 日表示d f ( i - 1 ，2 ，n ) 的稠密缸项集的集合凰。表3 1 中是上 华中科技大学硕士学位论文 面所有定义所用的符号的说明。 表3l 符号表示表 【d 全局数据库 p第i 个计算结点 d f结占p7 上的局部数据库 s最小支持度 f k全局频繁缸项集 f 结占一中局部频繁七- 项集 h k数据库d 中的稠密“项集 h |结点p l 中局部稠密缸项集 x s项目的全局支持计数 x ? s i 结点p f 上的项目x 局部支持计数 c t由f 0 ，产生的候选集 c h k由局部稠密集产生的局部候选集的并集 c h ；由局部稠密集一产生的局部候选集 定理1 若项目集肖是d ，的局部频繁集，则的任意子集y ( y c ，也是d ，的局 部频繁集。 定理2 若项目集x 是频繁集，则必存在一个局部数据库d ，( i = 1 ，2 ，n ) ，使 是其局部频繁集。 定理3 若项目集z 是频繁集，则必存在一个局部数据库d 。( i = l ，2 ，n ) ，使 和其任意子集y 是d r 的局部频繁集。 定理4 若项目集z 是频繁“项集内，则必存在一个局部数据库d 。( i = l ，2 ， n ) ，使x 和其任意子集y ( y c 在d ，是稠密的。 定理5 对任意七 1 ，频繁肛项集厶是所有数据子集上产生的局部候选七- 项集 c h ? 的并集c h k 的子集，即厶c h k = 3 c h ? = u a p r i o r i _ g e n ( 日! ，的。函数 i = i i = 1 a p r i o r i _ g e n 见文献 4