挖掘关联规则的并行算法

挖掘关联规则的并行算法SC02011028苏媛媛摘要：挖掘关联规则是数据挖掘领域的一个重要问题。文中对挖掘关联规则问题进行了简单的回顾，对已提出的挖掘关联规则的并行算法进行了较全面的总结,对他们的性能进行了分析，并提出了三种新的挖掘关联规则的并行算法,对他们的性能作了简要分析,给出了优化策略。第一种：设计了一个效率较高的并行挖掘关联规则的算法PMAR;并与其它相应算法进行了比较。实验证明,算法PMAR是有效的。第二种：提出一种新的并行算法NA,不管大项集的最大长度是多少,他只需2次同步就能得到结果,当大项集的最大长度比较大时,NA会显示出更好的性能。第三种：介绍了一种改进的基于Apriori算法的挖掘关联规则的并行算法，并和以前提出的DD算法进行了比较。这种改进的算法IDD克服了以前提出的DD算法的缺点，消除了DD算法中的工作冗余。关键字：并行算法关联规则大项集集群格1．引言数据挖掘(DataMining)就是从大量的日常业务数据中发掘出有用的信息。关联规则的挖掘(ARM)是数据挖掘的一项重要的任务。其目的就是从事务数据库、关系数据库中发现项目集或属性之间的相关性,关联关系,因果关系。关联规则可描述如下:D是一个事务数据库,其中每一个事务T由一些项目(Item)构成,并且都有一个唯一的标识(TID)。项目的集合简称项目集(itemset),含有k个项目的项目集称为k_项目集。项目集X的支持度(support)是指在事务数据库D中包含项目集X的事务占整个事务的比例,记为sup(X)。可信度(confidence)是指在事务数据库D中,同时含项目集X和Y的事务与含项目集X的事务的比,即sup(X∪Y)/sup(X)。项目集中长度为k的子集称为k_子项目集。如果一个项目集不是任何其它项目集的子集则称此项目集为极大项目集。如果项目集的支持度大于用户指定的最小支持度(min_sup)则称此项目集为频繁项目集(frequentitemset)或大项集(largeitemset)。关联规则可形式化表示为X=Y,它的含义是(X∪Y)的支持度sup(X∪Y)大于用户指定的最小支持度min_sup,且可信度conf大于用户指定的最小可信度min_conf。关联规则挖掘就是在事务数据库D中找出满足用户指定的最小支持度min_sup和最小可信度min_conf的所有关联规则。挖掘任务可分为两个子问题:1．找出事务数据库中所有的大项集。2．从大项集中产生所有大于最小可信度的关联规则。相对来说,第二个子问题比较容易,目前大多数研究主要集中于第一个子问题。关联规则描述虽然简单,但它的计算量是很大的。假设数据库含m个项目,就有2m个子集可能是频繁子集,可以证明要找出某一大项集是一个NP问题。当m较大时,要穷尽搜索每一个子集几乎是不可能的,另一方面,处理数据库中存储的大量记录要求繁重的磁盘I/O操作。因此,随着数据库规模的不断增大,数据属性向高维发展,传统的顺序挖掘算法很难适应大规模、可扩展(scalability)的挖掘需要,发展高性能的并行算法是解决这一问题的关键。2．相关工作2．1Apriori算法及其并行化Apriori算法是由Agrawal等人〔1〕提出的,算法思想主要依据支持度有“向下封闭”的特性。即,如果一个项目集是大项集,那么它的子集也是大项集。所以k_大项集的候选项目集可通过合并(k-1)_大项集构成。算法首先对数据库进行搜索,找出所有的频繁项目,即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。k1: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算法相同。k1:1)Pi从Lk-1中产生Ck。根据Pi个数把项目集分割成N份,Pi仅保留1份来构成Cik。处理器可根据其ID号来决定保留哪一部分而不需要与其它处理器通信。其中∩Ni=1Cik=,∩Ni=1Cik=Ck。2)利用本地数据和其它处理器传来的数据,Pi计算在Cik中项目集的支持数。3)在一次数据搜索结束时,各Pi用本地的Cik来计算Lik,∩Ni=1Lik=,∪Ni=1Lik=Lk。4)处理器之间相互通信获取其它Lik,之后每个Pi得到完整的Lk,用以下一趟产生Ck+1。这一步要求处理器同步。获得完整的Lk后,每个Pi能独立的决定是否终止或继续下一次搜索。·CandidateDistribute算法CandidateDistribute算法综合了DataDistribution和CountDistribution算法,以弥补它们各自的不足。在前l步采用DataDistribution算法或CountDistribution算法。到第l步(其中l由启发而定),为了减少各处理器之间的数据依赖,算法对大项集Ll-1进行分配,同时,也对数据进行重新分配,使Pi能独立于其它处理器生成Cim(ml,Cim∩Cjm=,i≠j);为了减少处理器对候选集的依赖,CandidateDistribute算法不等待从其它处理器传来完整的剪枝信息,它尽可能快的剪枝,而滞后到达的剪枝信息在下一次剪枝时使用。kl时沿用DataDistribution算法或CountDistribution算法。k=l时1)在N个处理器间分配Lk-1(简单的方法是根据Lk-1的前k-2项前缀进行分配)。2)处理器Pi利用分配得到的Lik-1生成Cik。3)根据Cik将数据库重新分割成DRi。4)Pi根据Cik计算出Lik,并发送到其它各处理器。kl时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_项目集(k2)时,就直接利用前一次生成的大项集了。候选集都是并行生成的。各节点产生自己本地的候选集,通过广播,进行交换,以此生成大项集。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从逻