挖掘关联规则的并行算法教案资料

挖掘关联规则的并行

算法精品文档挖掘关联规则的并行算法SC02011028苏媛媛摘要：挖掘关联规则是数据挖掘领域的一个重要问题。文中对挖掘关联规则问题进行了简单的回顾，对已提出的挖掘关联规则的并行算法进行了较全面的总结，对他们的性能进行了分析，并提出了三种新的挖掘关联规则的并行算法，对他们的性能作了简要分析，给出了优化策略。第一种：设计了一个效率较高的并行挖掘关联规则的算法PMAR;并与其它相应算法进行了比较。实验证明，算法PMAR是有效的。第二种：提出一种新的并行算法NA,不管大项集的最大长度是多少，他只需2次同步就能得到结果，当大项集的最大长度比较大时，NA会显示出更好的性能。第三种：介绍了一种改进的基于Apriori算法的挖掘关联规则的并行算法，并和以前提出的DD算法进行了比较。这种改进的算法IDD克服了以前提出的DD算法的缺点，消除了DD算法中的工作冗余。关键字：并行算法关联规则大项集集群格1.引言数据挖掘(DataMining)就是从大量的日常业务数据中发掘出有用的信息。关联规则的挖掘(ARM)是数据挖掘的一项重要的任务。其目的就是从事务数据库、关系数据库中发现项目集或属性之间的相关性，关联关系，因果关系。关联规则可描述如下:D是一个事务数据库，其中每一个事务T由一些项目(Item)构成，并且都有一个唯一的标识(1口)。项目的集合简称项目集(itemset),含有k个项目的项目集称为k_项目集。项目集X的支持度(support)是指在事务数据库D中包含项目集X的事务占整个事务的比例，记为sup(X)。可信度(confidence)是指在事务数据库D中，同时含项目集X和收集于网络，如有侵权请联系管理员删除精品文档Y的事务与含项目集X的事务的比，即sup(XUY)/sup(X)。项目集中长度为k的子集称为k_子项目集。如果一个项目集不是任何其它项目集的子集则称此项目集为极大项目集。如果项目集的支持度大于用户指定的最小支持度(min_sup)则称此项目集为频繁项目集(frequentitemset)或大项集(largeitemset)。关联规则可形式化表示为X=>Y,它的含义是(XUY)的支持度sup(XUY)大于用户指定的最小支持度min_sup,且可信度conf大于用户指定的最小可信度min_conf。关联规则挖掘就是在事务数据库D中找出满足用户指定的最小支持度min_sup和最小可信度min_conf的所有关联规则。挖掘任务可分为两个子问题：,找出事务数据库中所有的大项集。.从大项集中产生所有大于最小可信度的关联规则。相对来说，第二个子问题比较容易，目前大多数研究主要集中于第一个子问题。关联规则描述虽然简单，但它的计算量是很大的。假设数据库含m个项目，就有2m个子集可能是频繁子集，可以证明要找出某一大项集是一个NP问题。当m较大时，要穷尽搜索每一个子集几乎是不可能的，另一方面，处理数据库中存储的大量记录要求繁重的磁盘I/O操作。因此，随着数据库规模的不断增大，数据属性向高维发展，传统的顺序挖掘算法很难适应大规模、可扩展(scalability)的挖掘需要，发展高性能的并行算法是解决这一问题的关键。.相关工作.1Apriori算法及其并行化收集于网络，如有侵权请联系管理员删除 精品文档 Apriori算法是由Agrawal等人〔1〕提出的，算法思想主要依据支持度有“向下封闭”的特性。即，如果一个项目集是大项集，那么它的子集也是大项集。所以k_大项集的候选项目集可通过合并（k-1）_大项集构成。表1算法中使用的符号及它们的意义由匕大项集构成的集合,集合的每个成员有两个域：U项目集支持数.由候选匕项目集构成的集合，集合的每个成员有两Cfc 个域项目集，2）支持数.P1' [D号为i的处理器D1' 分配到的数据集DR， 重新分配后，分到P，的数据集.第k次搜索.厂所产生的当地候选集的集合.（其中每O' 个候选集包含k个项目）算法首先对数据库进行搜索，找出所有的频繁项目，即1_大项集。接着从1_大项集中产生2_大项集的候选集。然后进行第二次数据库搜索得出候选项目集的支持度，保留那些支持度大于min_sup的项目集，搜索结束时，得出2_大项集。这个过程重复进行，每一次迭代，保留大项集用于生成下一次迭代的候选集。直到找出所有的大项集。基于Apriori、Agrawal和Shafer在〔2〕中提出了三种并行算法：CountDistribution算法、DataDistribution算法和CandidateDistribute算法。这些算法的前提是处理器有专用内存和磁盘，而结构上没有任何共享。处理器用通信网络连接，靠消息传递进行通信。数据平均分配到每个处理器的专用磁盘上。这些算法需要用到的符号意义如表1。CountDistribution算法收集于网络，如有侵权请联系管理员删除精品文档CountDistribution是Apriori的一个简单并行化算法。算法是通过分割数据库来完成并行化的。如果有N个处理器节点，则各节点获得数据库的1/N,然后分别在各数据库子集上完成类似于Apriori的算法。k=1:1)Pi根据本地数据集Di产生本地Ci1。2)Pi将各自的Ci1与其它处理器交换。3)各处理器合并所有的Ci1得出完整的C1。k>1:1)Pi根据完整的大项集Lk-1产生完整Ck。2)Pi对Di进行搜索，计算Ck中候选项目集在本地的支持数。3)各Pi与其它所有处理器交换本地对Cik中候选项目集集支持数之后，算出Ck中完整的候选项目集支持数。在这一步，处理器被强制同步。4)Pi用Ck来计算Lk。5)各Pi独立的决定是否终止或继续进行下一次搜索。由于所有的Pi都有同样的Lk,所以每个Pi的决定是一致。DataDistribution算法DataDistribution是在各节点之间分割大项集的候选集，各节点分别计算各自所得候选项目集的支持度。k=1:与CountDistribution算法相同。k>1:1)Pi从Lk-1中产生Ck。根据Pi个数把项目集分割成N份，Pi仅保留1份来构成Cik。处理器可根据其ID号来决定保留哪一部分而不需要与其它处理器通信。其中GNi=1Cik=,nNi=1Cik=Ck。收集于网络，如有侵权请联系管理员删除精品文档2）利用本地数据和其它处理器传来的数据，Pi计算在Cik中项目集的支持数。3）在一次数据搜索结束时，各Pi用本地的Cik来计算Lik,nNi=1Lik=,UNi=1Lik=Lko4）处理器之间相互通信获取其它Lik,之后每个Pi得到完整的Lk,用以下一趟产生Ck+1。这一步要求处理器同步。获得完整的Lk后，每个Pi能独立的决定是否终止或继续下一次搜索。CandidateDistribute算法CandidateDistribute算法综合了DataDistribution和CountDistribution算法，以弥补它们各自的不足。在前l步采用DataDistribution算法或CountDistribution算法。到第l步（其中l由启发而定），为了减少各处理器之间的数据依赖，算法对大项集Ll-1进行分配，同时，也对数据进行重新分配，使Pi能独立于其它处理器生成Cim（m>l,CimnCjm=,iW））;为了减少处理器对候选集的依赖‘CandidateDistribute算法不等待从其它处理器传来完整的剪枝信息，它尽可能快的剪枝，而滞后到达的剪枝信息在下一次剪枝时使用。k<l时沿用DataDistribution算法或CountDistribution算法。k=l时1）在N个处理器间分配Lk-1（简单的方法是根据Lk-1的前k-2项前缀进行分配）。2）处理器Pi利用分配得到的Lik-1生成Ciko3）根据Cik将数据库重新分割成DRio4）Pi根据Cik计算出Lik,并发送到其它各处理器。收集于网络，如有侵权请联系管理员删除精品文档k>l时1)Pi收集所有从其它处理器发送来的频繁项目集，用于对候选集剪枝。2)Pi用本地的Lik生成Cik。如果Pi没有收到其它处理器传来的Ljk-1,则Pi剪枝时要作相应的处理。3)Pi搜索DRi,对Cik中的项目计数。然后根据Cik计算出Lik并把它传到其它处理器。从以上三个算法可以看出：CountDistribution算法目标是减少通信量获得较好的任务分布性，使各处理器只对本地数据并行地进行处理。但算法的I/O量较重，数据结构重复，没有有效利用整个内存。DataDistribution算法目标是尽量减小计算冗余，充分利用各节点之间的带宽。它在节点间分割当前最大频繁项目集的候选集，然而要获得全局支持度，各处理器必须搜索整个数据库，通信量较大。上述两种算法每次搜索结束时，都要求所有处理器必须同步。与DataDistribution算法相似,CandidateDistributuon算法也是在各节点间分配候选集，但它有选择地对数据库进行分割，使每个节点可以根据本地的数据来处理它的候选集，减少处理器之间对数据和各候选集的依赖，从而减少同步，减少通信量。2.2DHP算法及其并行化在生成大项集的过程中，候选项目集集合越大，生成大项集的开销越多，特别是最初几次迭代要占整个过程的大部分开销。针对于这一问题，Park等人提出了DHP(DirectHash-ingandPruning)算法。与Apriori算法相同,DHP也是从(k-1)_大项集Lk-1中产生k_大项集的候选集Ck。但是,DHP算法利用哈希技术来检查k_项目集是否满足要求。DIH算法只对哈收集于网络，如有侵权请联系管理员删除精品文档希表中项目数大于min_sup的单元进行处理，将这些单元中的k_项目集加入Ck,这对减少候选2_大项集的数目尤为有效。另一方面，算法通过缩减事务本身的大小和对数据库中事务剪枝，来缩减数据库规模。DHP算法能有效地生成大项集，显著地减少事务数据库规模。但DHP对数据库进行的是物理剪枝，而不是逻辑剪枝，每次迭代对数据库的剪枝将涉及对数据库的重写，增加了I/O负担。基于DHP的思想，Park等人提出了PDM算法。大体上说,PDM算法是由并行生成候选项目集和并行确定大项集两部分构成。PDM算法描述如下：首先，每个节点分别计算分数据库中1_项目集的支持度，并利用哈希表计算2_项目集的支持数。各节点通过广播(all-to-allbroadcast)交换本地的1_大项集，计算产生全局1_大项集。而对于2_项目集，其哈希表一般很大，直接通过广播交换，通信量很大。PDM利用优化的方法，仅交换哈希表中那些大于min_sup的单元。各节点利用了全局2_项目集的哈希表，生成本地的候选2_项目集。然后，生成候选k_项目集(k>2)时，就直接利用前一次生成的大项集了。候选集都是并行生成的。各节点产生自己本地的候选集，通过广播，进行交换，以此生成大项集。PDM算法有一些局限性。首先，为构成完整的候选项目集各节点都要进行广播通信，通信的开销可能会抵消掉并行生成候选项目集的优势。其次，和DHP一样,PDM对非大项集的项目和事务的物理剪枝要涉及大量磁盘I/O操作。2.3DIC算法及其并行化收集于网络，如有侵权请联系管理员删除精品文档DIC(DynamicItemsetCounting)算法是由Brin等人提出的，算法的主要思想是在同一次数据库搜索中，对k值不同的候选k_项目集计数。DIC将数据库分成N个大小相等的几段Di进行搜索。首先搜索D1,计算1_项目集的支持度，所得本地1_大项集用来产生2_项目集的候选集。然后搜索D2,获取1_项目集和候选2_项目集，即当前所有的候选项目集，计算它们的支持度，所得2_大项集用于产生3_大项集的候选集。重复这一过程，直到Dn完成。在对数据库的第一次搜索中，当搜索到Dk时，DIC就开始计算候选k_项目集的支持数。所有分块都处理完之后，开始第二次搜索。当算法回到数据库第k段Dk进行搜索时，就能得出k_项目集的全局支持度。每一次搜索完成后，开始新的一次，直到当前Dk没有新的候选集产生，且所有的候选集都已经计算完成,DIC终止。如果大部分的Dk是匀质的(homogeneous),即大项目集在Dk中有相似的分布,DIC算法减少对数据库搜索非常有效。而如果数据是非匀质的,DIC可能会在某些Dk中得出一些局部而非全局的大项集，反而增加了搜索次数。基于DIC思想，Cheung等人提出了APM(Asyn-chronousParallelMining)算法。算法的前提是多处理器共享内存。APM采用了一种全局剪枝技术(GlobalPruning)来约减候选2_项目集的规模。当在各分数据库中数据分布不均时，这种剪枝很有效。而要在各节点上利用DIC算法，则要求数据库各个分块数据均匀分布。为了解决这一矛盾,ARM进行一次预处理。APM从逻辑上把数据库分割成大小相等的一些分块。假设分成n块(n与处理器个数无关，但通常n大于处理器个数),APM计算m个项目在各分块的支持度，构成一个nm的数据表，表示在m维空间的n个项目支持度的矢收集于网络，如有侵权请联系管理员删除精品文档量。将这n个矢量聚成k个不同的类，使类与类之间的差别尽量大，而类中各项目之间差别尽量小。这k个聚类构成了k个子数据库，这使得它们之间的数据分布尽可能的不均匀。用它们可产生较小的候选2_项目集的集合。经过以上预处理，数据库按处理器个数化分为匀质的子数据库。APM开始并行实施DIC算法，即每一个处理器独立地对本地的子数据库使用DIC算法。由于所有处理器共享一个trie树来存储候选项目集的支持度，而trie树是异步构造的。所以只有当处理完所有的侯选项目集，没有新的候选集产生，APM才结束。虽然，数据分布不均匀有利于APM算法的全局剪枝，但它却加重了负载不平衡。.4Eclat/MaxEclat,Clique/MaxClique算法及其并行化Zaki等人在〔8〕中提出了Eclat、MaxEclat、Clique、Max-Clique四种算法。这些算法主要采用了三种技术：算法首先用等价类或最大完全子图集(maximalhypergraphclique)方法对项目集聚类。然后用从底至上遍历或混合遍历(从顶至底与从底至上结合)的方法从每个聚集中生成大项集。算法还利用了纵向数据库格式(verticaldatabaselayout)对事务聚类。这四种算法的基本思想相同，只是所使用的搜索策略和划分等价类技术不同而已。这些算法对项目聚类，产生一些项目集，这些项目集可能是极大项目集。每一个聚集包含一个子格(sublattice),对其用从底至上的搜索遍历找到所有的大项集，或用混合遍历法仅找出极大项集。由于用数据库的纵向格式来对事务聚类，所以仅对数据库搜索一遍，因此大大减少了I/O操作量。算法使用简单的事务TID表交集来求大项集。不需要构造和检索复杂的数据结构。此收集于网络，如有侵权请联系管理员删除精品文档外，由于在任何时候一个聚类中仅k_大项集保留在内存中，所以算法对内存要求较低。基于以上四种算法，Zaki等人提出了ParEclat、Par-MaxEclat、ParClique、ParMaxClique四种并行算法。算法前提条件是系统有n个主机，每个主机有P个处理器。这些算法采用纵向数据库格式。在各主机间以一定的方式分配数据库，使得每个主机能获得的所有事务的TID表长度总和大致相当，且每个TID表都是一事务完整的TID表。各主机进一步根据本地的ID表将数据库分成P个纵向分数据库，这样，系统中的每一个处理器都仅处理自己的纵向分数据库。同顺序算法一样，这四种算法只是所使用的搜索策略和划分等价类技术不同。算法分三个阶段：在初始化阶段，主要完成数据分割，分三个子步骤。首先，读入（预处理阶段得到的）2_项目集的支持数，把大项集加入L2。其次，应用等价类或最大完全子图集的方法聚类，产生可能是极大频繁项目集的项目集。然后，所有处理器之间将这些项目集在按一定策略进行分配，使各处理器尽量负载平衡。对数据库进行重新分配，使得所有和聚类相连系的1_项目集的TID表，都能在聚类所在处理器的本地磁盘获得。随后进入异步处理阶段，在这个阶段，由于每个处理器都能在本地获得分配给它的等价类和所有项目的TID表，所以能独立地产生大项集，不要求通信和同步。最后的约简阶段，主要将最终的结果进行整理。.挖掘关联规则的几种新并行算法.1采掘关联规则的并行算法PMRA在介绍算法PMRA之前先弓［入与之有密切关系的几个定义与定理。收集于网络，如有侵权请联系管理员删除精品文档定义1。项集X在数据库DBi(i=1,2,…，n)中的支持数(supportcount),即在DBi中包含X的事务的条数，称为X的局部支持数，用X。supi表示。定义2。项集X在数据库DB中的支持数称为X的全局支持数，用X。sup表示。定义3。对于项集X,若X。supi2minsupxDBi(i=1,2,…，n),则称X是相对于Pi的局部大项集。若X中的元素为k个，则称X为局部大k项集。定义4。对于项集X,若X。sup2minsupxD,则称X是全局大项集，简称大项集。若X中的元素为k个，则称X为大k项集。定义5。若项集X在Pi(i=1,2,…，n)是局部大项集，且它还是大项集，即X。supi2minsupxDi,且X。sup2minsupxD,则称X在Pi(i=1,2,…，n)是稠密的，用HL表示。如HLik表示Pi(i=1,2,…，n)的k稠密集(其中元素为k个)的全体。定理1。若项集X是大k项集(XELk),则必存在一个计算机Pi(i=1,2,…，n),使任意YX的项集Y在Pi是稠密的。定理2。对任意k>1,大k项集Lk是所有计算机产生的局部候选大k项集CHik的并集的子集，即LkCHk=Uni=1CHik=Uni=1Apriorigen(HLik-1,k)。函数Apriorigen见文献［5］。定理1与定理2的证明见文献［18］。定理3。设CAk=Apriorigen(Lk-1,k),CHk=Uni=1Apriorigen(HLik-1,k),则CHkCAk。收集于网络，如有侵权请联系管理员删除精品文档证明：设函数Apriorigen的第(1)步对Lk-1,HLik-1作用的结果分别为ALk,AHLik,对XEAHLik,根据定义4与定义5有Lk-1=Uni=1HLik-1,于是HLik-1ELk-1,由函数Apriorigen的第(1)步作用过程我们可得XEALk,于是有AHLikALk,所以ALkAHLk=Uni=1AHLik。函数Apriorigen的第(2)步作用于ALk,AHLik,删除它们中的不符合条件的元素，使它们分别变为CAk,CHk。对XEALk,若它被删除，则必存在X的元素为k-1个的子集Y,有YLk-1,由于Lk-1=Uni=1HLik-1,贝1JY必不属于任意一个HLik-1(i=1,2,…，n),所以若XEAHLk,则也必被函数Apriorigen的第(2)步所删除。于是有CHkCAk。证毕。算法PMRA需要每个计算机Pi(i=1,2,…，n)对其本地事务数据库DBi或本地候选事务数据库CBi进行多遍扫描。在第k(k=1,2,…)趟扫描中，计算机Pi(i=1,2，…，n)都进行生成候选大项集、支持数计算、交换支持数、生成稠密集等步骤，具体情况可描述如下(见算法1)O(1)生成候选大k项集CHik。根据计算机Pi(i=1,2,…，n)在k-1次循环所生成的稠密集HLik-1,生成循环k所需用的候选大k项集CHik,据定理2有CHik=Uni=1Apriorigen(HLik-1,k)。设XECHik,p为生成X的两个(K-1)稠密集中的支持数较小的那一个，令X。ocount=p。supi。(2)支持数计算。扫描本地事务数据库DBi计算候选大k项集CHik中的每个元素X的局部支持数X。supi。我们可以对CHik做如下剪枝：当扫描到DBi的某一条记录时，记X的支持数为X。count,若X。count=X。ocount,则X的支持数将不会再增加，对数据库的以后的扫描中不必考虑其中的事务是否包含X。若X是局部大k项集，则置CHik。LL=1。收集于网络，如有侵权请联系管理员删除 精品文档 (3)交换支持数。计算机Pi(i=1,2,…，n)广播候选大k项集CHik,然后收集由计算机Pj(iWj)传来的CHjk,计算项集X的全局支持数X。sup,若X。supNminsupxD,则置CHik。GL=1。(4)生成稠密集HLik。对计算机Pi(i=1,2,…，n),若项集XECHjk,且有CHjk。LL=1和CHik。GL=1,则X是HLik的元素。算法LPMAR输入①存储在计算机lI,2 ,记硬盘中的I,2, ,n：@最小支持度mincup输出大项集L=UL方法在计算机F「= —口)执行如下操作forfk.=I；；R++】if(k-I)ths扫描数据库DD•瑜定候选大IR集CHi]sfCH=」Apribi-循£口〔止L,k)^dcifforal：trailsac1ionsfEDdofnrs11it?nf: Cf-iHeitt.c. h!andc'=:thenc.二。以日工七十fora.]',item氏CHdeifc.匚口口日£》minsup*Dthfnc.LL=IDr-DcidvastCfi中,Li素'的支R£cf 从,计算机P发来的二H(芦。中兀素的支井赞fora】：itfmsc€CHdeforl；'=I;洛ri,Nf；产+]C-CDUTft在中为攵杆数itc.sDt<nfj^ii]insli?^Utti^DJc.jL=；_+=cforI/=I；f%出产+)ifc.GL=I且亡在匚H中的LL坂丸IthwuHL+=cifL=0thf口ekitL+=Lendfor并行采掘关联规则的算法高效的关键在于如何能生成较小的候选大项集和如何有效地剪枝候选大项集。根据定理2与定理3,我们可以知道算法PMAR所产生的候选大项集要小于算法CD所产生的候选大项集。算法PMAR在第(2)步弓1入特殊的剪枝技术，提高了算法的效率。3.2挖掘关联规则的并行算法NA收集于网络，如有侵权请联系管理员删除精品文档并行计算的关键性能是负载平衡与同步。在前面介绍并行算法中，如果大项集的最大长度为k,至少需要k次同步才能得到结果，影响了响应时间。在这部分里，我们提出一种新的并行算法NA,不管大项集的最大长度是多少，他只需2次同步就能得到结果，当大项集的最大长度比较大时，NA会显示出更好的性能。3.2.1设计思想定理1设N个事务平均分布到P个处理器上，每个处理器上有N/P个事务，在这N/P个事务上直接计算最小支持度为sup的大项集(称他为局部大项集)。把所有处理器上的局部大项集合并到集合S',他一定包含了S中所有的项目集合，即S'是S的超集。证明考察S中任意一个项集s。因为s是大项集，所以至少有Nxsup个事务中包含s。这Nxsup个事务被分布到P个处理器上。根据鸽巢原理，至少1个处理器有:(Nxsup-1)/P]+1个包含项集s的事务。根据大项集的定义，只要在某个处理器上有Nxsup/P个事务包含s,s就成为该处理机上的局部大项集。所以s一定会包含在某个处理器的局部项集中，sES‘中，由此可得S',一定是S的一个超集。注意，集合S'中的项集的计数是不完全的。试想在处理器P0上｛AB｝是局部大项集有5个事务支持他，由于数据分布不均造成了P1只有1个事务支持｛AB｝,并且他因为没有达到最小支持度而被删除。当汇总之后得到只有5个事务支持｛AB｝,漏掉了一个计数，这可能导致漏掉一些大项集。所以必须要对这点作弥补。局部大项集得到之后用广播的方式使得每个处理器上都得到了S的超集S'。然后各处理器在本收集于网络，如有侵权请联系管理员删除精品文档地数据上对S'中的项集重新计数，最终再把S'中的项集的计数汇总，得到全局计数。于是，最终得到了完整的大项集S。本算法让各处理器在不知道其他处理器的任何信息的情况下独立地计算局部大项集，直到所有的处理器都计算出了局部大项集后，才开始交换数据，增加或删除项集，得到最终结果。3.2.2算法描述NA算法可以简单地描述如下：(1)每个处理器Pi在本地N/P个数据上各自独立地计算支持度为sup的局部大项集S'i;(2)各处理器与其他处理器交换计算所得的大项集局部集S'i,使得每个处理器都拥有S的超集S1;(3)每个处理器在本地数据上对S'中的项集进行重新计数，得到局部计数;(4)各处理器把S'上的计数与其他处理器交换，每处都得到了全局计数；(5)检查是否达到最小支持度，得到最终的大项集S。3.2.3实现策略NA算法思想简单，实现起来很容易。在(1)中可以启用任何一种好的串行算法，Apriori,DIC或是抽样算法，因为计算局部大项集的过程是独立完成的，不需要同步和交换数据，只要响应时间快，用什么方法都可以。DIC算法在最小支持度较小时比Apriori有更好的性能，所以支持度小时可以考虑使用DIC方法计算局部大项集，会得到较好的响应时间，而且他使用的数据结构也比较适合该算法。收集于网络，如有侵权请联系管理员删除精品文档抽样算法对样本的依赖性较强，若每个处理器抽样的质量不同，就有可能造成负载不均衡，所以建议不要使用。Apriori算法仍然算得上是个好的选择，因为在支持度不变，数据量减少的情况下，他的响应时间是呈线性减少，这一点对NA算法很重要。我们可以对Apriori算法改进之后应用于NA中。考虑C2是一个特殊的集合，由L1xL2所得，而且在计算候选集时的删除一步中不会有任何项集被删除，第2步计算的时间会突然增加，所以把前2步优化会得到更好的性能。既然C2的项集中仅包含两个项目，索性用1个二维阵列存储C2,而不用再去维护1个hashtree。让行和列上都是不同的项目，二维阵列上的每个点代表1个项集，大大减少对内存的需求。由于事先约定事务中的项目是有序的，实际上C2的存储只是1个上三角阵。可以用1个二维数组a来存储这个阵列，他的下标恰好是项目的标识。当i^j时，a[i][j]中是项集｛ij｝的计数；当i=j时，a[i][j]中是单个项目｛i｝的计数。当从数据库中读出1个事务时，可以很方便地同时为单个项目和2itemsets项集计数，所有的数据都处理一遍之后，开始检查最小支持度，满足条件的保留原有的计数，取出项集和计数。在检测最小支持度的同时还可以得到C3,并把他存储到hashtree中，为后面的计算作好准备，由于要检测的计数全部存储在二维数组中，可以通过下标很快地找到想要的数据，只须花很少的时间就可以完成计算。由于NA算法可以不管其他处理器而独立运行，他恰好可以使用上面介绍的优化方法。但在其他并行算法中却不能使用，原因是他们在第1步与第2步之间必须做一次同步，交换数据之后才能得到C2,继续后面的计算，所以L1和L2不可能在同步中被得到。收集于网络，如有侵权请联系管理员删除精品文档在NA算法中计算局部大项集的工作完全可以异步执行，只是在最后结束时才进行一次同步。另外（2）和（4）中，需要一些数据通信，这里可以借用其他并行算法中的好的通信机制，降低通信开销。而且在（4）中，由于各处理器上拥有相同的候选集S',所以与CD算法一样，只需交换计数即可。在第（3）步上存在冗余的工作。因为Pi在上已经对S'中的一些项集进行计数了，而这步又要全部重新计算，这无疑是冗余计算。对此作一下改进，在（2）中为处理器记录原来本地没有而新增加的项集，这样在（3）中只须要为新增加的项集计数，避免不必要的重复计算，在（4）中只须交换各自的新增加候选项集的计数，就能得到全局计数。.3一种改进的基于Apriori算法的挖掘关联规则的并行算法IDDIDD算法弥补了DD算法的不足。在IDD算法中，局部存储数据库通过一种基于环的多对多广播方式传送给其它所有处理器。这项操作不会产生像算法那样的竞争问题，同时它的时间复杂度为O（N）。这项数据移动的伪码如下：收集于网络，如有侵权请联系管理员删除 精品文档 while(!done)(FillBuffen；f(i,SBuf);for(k=0,k<P-1+4k)(/*send/receivedatainnan-blockingpipeline+7MPI_It■巳c就RBufJeft);MPI_Isaid(SBufnnght),泮processtransactioninSBufanupdatehashtree*/Suhset(Htree?SBuf);MPI_WaitalX)；产swaptwobuffertemp=SBuf;SBuf^=RBuf;RBuf^SBuf;产processtraiisactiotLSinSBufanupdatehashtree忤Subset(HtrejSBuf);在该算法中，处理器形成一个局域的环，每一个处理器决定它左右相邻的处理器。每一个处理器都有一个发送缓冲区(Sbuf)和一个接收缓冲区(Rbuf)。开始时，SBuf中充满数据，接着每一个处理器在SBuf中初始化一个异步发送操作为它右边的处理器)，在RBuf中初始化一个异步接收操作(为它左边的处理器)。当这些异步操作执行时，每一个处理器处理SBuf中的事务并收集分配给这个处理器的候选的个数。然后，每一个处理器等待这些异步操作的完成。这时把SBuf和RBuf互相交换，然后执行以上操作，直到循环p-1次为止。和DD算法相比，在所有的处理器发送数据给其它所有的处理器时，该算法在相邻处理器间执行的是点到点的通信，这样就减少了通信竞争。更进一步，如果处理一个缓冲区的时间变化不大的话，该算法中处理器的空转时间将很少。为了消除分割候选项目集的工作冗余，算法运用了一个快速检查给出的事务是否是潜在的存储在每一个处理器中的候选的方法。算法在处理器中用这种收集于网络，如有侵权请联系管理员删除精品文档方法分割Ck,这样每一个处理器可以得到从所有可能项目的子集开始的项目集。如果哈希树包含了从这些项目开始的候选，就检查一个事务的项目是否与该子集相符。当事务中的项目属于这个子集时，遍历哈希树。这样通过这种智能的分割，就解决了DD算法中的工作冗余问题。图是算法的示例。在这个示例中，处理器0中是从项目1和7开始的所有候选，处理器1中是从项目2和5开始的所有候选，以此类推。每一个处理器把候选的第一个项目放在一个位图中。在Apriori算法中，在哈希树的根部，每一个处理器通过检查这个位图来确定处理器是否包含从这个项目开始的候选以此来过滤事务的所有项目。如果处理器没有包含，从这个项目开始的候选则从这个项目开始的候选的处理步，骤将会跳过。这样就减少了计算量。如假设,{12345678}是一个事务集合。在哈希树的顶部，处理器0将从项目1和7开始执行。当包含这个事务的页转移到处理器1时，处理器1将只从项目2和5开始执行。图所示的就是这样的一个方案的执行过程。这样对于数据库中的每一个事务，算法把工作在处理器间分割，消除了DD算法的大部分工作冗余。从以上可知，分割哈希树和过滤都是消除处理器间的工作冗余所必需的。收集于网络，如有侵权请联系管理员删除精品文档在IDD算法中智能的分割候选集合能够在处理器上达到负载平衡，也就是说，在所有的处理器上的候选的数目是相等的。为了达到候选项目集的相等分布，该算法运用了一种基于bin-packing的分割算法。对于每一个项目，首先计算从这个项目开始的候选项目集的数目。接着运用bin-packing算法把这些项目分割到个桶中，这样就可以使从这些项目开始的候选项目集的数目在各个桶中是相等的。一旦候选项目集的位置确定了，每一个处理器都可以存储自己的候选项目集。在IDD算法中的每一步中都用了bin-packing算法，并且花在bin-packing算法上的时间跟整个运行时间相比是较少的。图中显示了候选哈希树的分割和在每一个处理器上相应的位图。.结束语本文对采掘关联规则问题进行了简单地回顾，给出了一种提高顺序采掘关联规则算法效率方法。对在分布式事务数据库中采掘关联规则问题进行了研究，提出了一个效率较高的并行算法PMAR。实验证明，算法PMAR是有效的。算法PMRA也可以对设计并行地采掘一般关联规则、序列模式及关联规则的增量式更新等问题提供借鉴。NA算法的思想有些像抽样算法，先通过某种方法得到一个候选集，只不过抽样算法利用样本得到一个候选集，而该方法是利用多个处理器的并行计算得到候选集S'。但不同的是后者得到了大项集的超集，所以再扫描一遍数据库即可得到最终的大项集；而前者得到的候选集无法保证是超集，有可能报告失效，这时还须扫描数据一遍或多遍，直到不再报告失效为止。NA在计算局部大项集是利用前面介绍的优化方法，而且只需2次同步，在计算方法和同步次数都要优于CD算法。NA算法的设计思想虽然简单，但却有很好的性能。IDD算法在创建哈希树的过程中有很高的效率，而且随着候选收集于网络，如有侵权请联系管理员删除精品文档集合规模的增长它是可扩展的。该算法在D