数据挖掘中的关联规则发现

数据挖掘中的关联规则发现

相关规则是r.agrawal等人首次提出的cdd的重要研究内容，近年来引起了数据库界的关注。关联规则是寻找在同一个事件中出现的不同项的相关性,即找出事件中频繁发生的项或属性的所有子集,以及它们之间应用相互关联性。关联规则最早用于发现顾客交易数据库中不同商品间的联系,后来诸多的研究人员对关联规则的挖掘问题进行了大量的拓展和研究。他们的工作包括对原有算法的优化,如引入并行的思想,以提高算法的效率,对关联规则的应用进行扩展。关联规则挖掘具有计算量大,I/O负载集中的特点。而且许多关联规则的实际应用涉及到海量数据。在这种情况下,即使对算法进行了优化,在单处理机上使用串行算法进行挖掘所需要的时间可能也是无法接受的。其主要原因在于单处理器本身受到内存和I/O带宽的限制。因此,必须依靠高性能并行计算来有效地完成挖掘任务。1关联规则的挖掘关联规则的形式化描述如下:一个关联规则是形如X⇒Y的蕴涵式,这里X⊂I,Y⊂I,并且X∩Y=ф。规则X⇒Y在交易数据库D中的支持度(support)是交易数据库中X和Y的交易数与所有交易数之比,记为support(X⇒Y),即规则X⇒Y在交易数据库D中的可信度(confidence)指包含X和Y的交易数与包含X的交易数之比,记为给定一个交易集D,关联规则的挖掘问题就是产生支持度和可信度分别大于用户给定的最小支持度(minsupp)和最小可信度(minconf)的关联规则。关联规则的发掘分为两个步骤:(1)找出所有支持度大于最小支持度的频集;(2)从频集中产生期望的规则。2提取网络关联规则的算法目前所有并行关联规则算法都是在相应的串行算法的基础上提出的。本文首先对这些串行算法进行介绍和分析。2.1基于数据库的限制竞争函数在各种关联规则挖掘算法中,最经典、最广泛使用的就是Agrawal等设计的Apriori算法,其核心思想是基于频集理论的递推方法。首先产生频繁1-项集,然后是频繁2-项集,直到有某个r值使频繁r-项集为空,算法停止。这里在第k次循环中,过程先通过对两个只有一个项不同的属于k-1的频集做(k-2)-连接产生候选k-项集的集合。然后验证候选k-项集中的每个元素来决定是否将其加入k-频集,这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描数据库,这就需要很大的I/O负载。Park等提出了一个高效地产生频繁集的基于杂凑(hash)的算法:DynamicHashingandPruning(DHP)算法。通过实验可以发现寻找频集的主要计算是在生成频繁2-项集上。DHP利用一个杂凑表在计算频繁1-项集时先大概计算出2-项集的支持度,从而减少了候选2-项集的数量。DHP还采用了数据库修剪技术,通过修剪掉那些不包含频集的事物集以减小下一次循环中数据库的大小。然而,这种修剪技术的优化并不显著。其主要原因在于只能通过过滤对数据库执行逻辑上的修剪,任何物理上的修剪意味着在每次循环中要改写数据库,这是不切实际的。Savasere等提出了一种基于划分(partition)的算法。这种算法把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集。然后把产生的频集合并,用以生成所有可能的频集,最后计算这些频集的支持度。Partition算法很大程度上减小了I/O负载。然而在处理高项集时存在一些问题,而且它还有频集的错误处理的缺陷。Brin等提出的DynamicItemsetCounting(DIC),也是基于划分的一种算法。它通过在一个循环中生成不同长度的候选集以减少数据库扫描的次数,有效地改进了算法在低层的效率。然而该算法在同构数据的情况下具有较好的性能。例如,多数分块有相似的频集分布。否则,DIC可能需要比Apriori更多的对数据库的扫描。Muellel在他的硕士论文中提出了4种基于Apriori和Partition的算法:SEAR算法,基于TID划分的SPTID算法,基于划分的SPEAR算法和SPINC算法。SEAR算法与Apriori算法相似,只是该算法用一个前缀数(prefixtree)取代杂凑数(hashtree)来存储候选项集,而且引入了一个循环绑定(passbunding)的优化策略,即只要内存允许在一个循环中可生成不同长度的候选集,这样在对数据库的一次扫描中就可以计算所有当前候选集的支持度。实验表明,SEAR算法优于其他算法,具有较好的性能。Zaki等在论文中提出了基于数据的垂直分布的关联规则发现算法。其中最简单的是Eclat算法,性能最好的是MaxClique算法。当前多数关联规则挖掘算法采用的是水平数据分布方式,即数据由一系列事物构成。使用这种格式,计算负载主要集中在支持计数上。而且,数据的水平分布迫使每次循环均需遍历整个数据库或每个局部划分。数据的垂直分布是指数据集由一系列项目构成。数据垂直分布的优点在于可以通过简单地链接任意两个(k-1)-子集生成候选k-项目集,不需要复杂的hash数据结构,无须对数据库进行遍历。以上介绍的都是基于Apriori的关联规则挖掘算法。即使已经进行了一定的优化,但是Apriori方法仍存在一些固有的无法克服的缺陷:(1)可能产生大量的候选集;(2)对数据库进行多次扫描。2.2频繁模式树的fp-g水质数据库的构建Han等提出了一种富有创新性的方法,即FP-growth方法。这种算法采用了分而治之的策略,经过第1次扫描之后,把数据库中的频集压缩到一棵频繁模式树(FP-tree)中,同时依然保留其中的关联信息。随后再将FP-tree划分为一些条件库,每个库和一个长度为1的频集相关。然后再对这些条件库分别进行挖掘。FP-growth只需对数据库进行二次扫描,而且避免了产生大量候选集的问题。实验表明,FP-growth对不同长度的规则具有很好的适应性,同时在效率上较之Apriori算法有很大的提高。3多处理器关联规则的研究尽管关联规则的描述很简单,但是它却是一个计算和I/O集中的任务。假设给定m个项目集,那么存在2m个子集可能是频集。处理如此指数级的数据需要大量的磁盘I/O。实验证明,在限定交易长度的情况下,关联规则的挖掘和数据库的大小呈线性递增的关系。而且,随着项目集的数量和维度的增加,以及交易数据库大小的增加,串行算法显然不具有良好的性能。因此必须依靠高性能并行计算来有效地完成挖掘任务。然而利用多处理器系统进行关联规则发现,要想获得好的性能并非易事。其中涉及到的问题包括:减小同步和通信,负载平衡,数据放置和减小磁盘I/O。下面从并行度、负载平衡、以及实现平台等方面对当前主要的并行关联规则发现算法进行介绍和分析。3.1cd和pdm算法多处理器体系结构有3种形式:共享内存系统(sharememorysystem),共享磁盘系统(share-disksystem)和不共享系统(share-nothingsystem)。在共享内存系统中,所有处理器共享一个通用的,非常大的内存。这样任何一个处理器都可以访问所有的数据,具有动态负载平衡。在这种系统中,想要获得好的并行性能,关键在于处理好数据的同步问题。在共享磁盘和不共享系统中,数据分布在各个处理器节点上,它们之间的通信和I/O是通过消息传递来实现的。因此获得好的并行性能的关键就在于合理分布数据,以取得好的负载平衡,减小通信代价。Agrawal等提出了3种基于Apriori的并行关联规则挖掘算法:CountDistribution(CD),DateDistribution(DD)和CandidateDistribution算法。它们是在不共享的IBMPOWER并行SP2系统上实现的。Apriori算法的主要计算代价是候选集的生成及其支持度的计算。因此高度并行地完成此过程必然可以大大地降低算法执行的时间,提高算法的性能。一种并行的方法是复制候选集(CD算法)(见图1),另一种方法是划分候选集(DD算法)(见图2),再就是将两种方法合成,即部分划分候选集的方法(CandidateDistribution)。CD算法将生成候选集的过程复制到所有处理器上。每个处理器生成一个完整的候选杂凑树,根据本地数据库分块独立地计算出候选项的局部支持计数,然后通过在所有处理器之间交换局部支持计数来得到全局支持计数。因为在处理器间只需交换支持数而不是合并不同的杂凑树,这种算法具有较小的通信负载。然而它并没有实现杂凑树构成过程的并行化,在处理器数量增加的情况下,将成为算法执行的瓶颈,而且它也没有有效地利用内存。DD算法用一种循环的方式将候选集划分到每个处理器中,然后由每个处理器负责计算本地存储的候选子项集的支持计数。这个过程需要每个处理器既要扫描分配给该处理器的数据库,还要扫描其他处理器上的数据库,从而导致了很高的通信负载,降低了该算法的性能。为了交换各自的支持计数或频集,CD算法和DD算法都需要在每次循环结束时进行处理器之间的同步。CandidateDistribution算法,在l循环中划分候选集,同时选择性地复制数据库以便每个处理器可以独立地生成候选集和全局支持计数。实验表明,较之其他两种算法,CD算法的性能最好。PDM算法是Park等提出的并行DHP算法。该算法类似于CD算法,所有处理器含有相同的杂凑表和候选集。并行候选集生成的过程,是通过每个处理器生成一个候选子项集,然后交换所有处理器上的子项集生成全局候选集来实现的。每个处理器通过一个杂凑表(hashtable)生成k-项集的局部支持数和k+1-项集的近似局部支持数,然后通过全局广播的方式交换k-项集的局部支持数而得到k-项集的全局支持数。由于2-项集杂凑表很可能非常大,直接交换的代价将是非常高。该算法采用了一种优化策略,即只交换那些支持数大于最小支持数的项集。PDM算法实现了杂凑表构成的并行,性能优于CD算法。Shintani等提出了3种类似文献的算法:NonPartition,Simple-Partition和Hash-PartitionApriori算法,是在不共享的有64个节点的FujitsuAP1000DDV系统上实现的。Non-PartitionApriori算法本质上和CD算法相同,不同之处在于它使用了一个控制处理器完成全局支持数的累计过程。Simple-PartitionApriori算法和DD算法一样。Hash-PartitionApriori算法类似于CandidateDistribution算法,采用杂凑函数将候选集分配给处理器,减小了处理器间发送局部数据库分块的通信负载。Zaki等提出的CommonCandidatePartitionDatabase(CCPD)算法,以及Cheung等提出的AsynchronousParallelMining(APM)算法是在共享内存的系统上实现的。在CCPD算法中,所有处理器共享一个候选杂凑树,而数据库被逻辑划分为大小相等的分块。该算法采用锁机制来实现杂凑树生成过程的并行。论文中指出,由于杂凑本身的特点,杂凑树具有很差的数据放置,加之共享杂凑树可能会造成支持计数时产生错误的结果。针对上述问题,他们提出了一些优化策略,如杂凑树平衡(hashtreebalancing)、优化内存布置(memoryplacementoptimization)等。APM算法是基于DIC的并行算法,对数据扭曲非常敏感,并且认为数据是同构的。在APM算法中,采用全局修剪技术来减小候选2-项集的大小,这在存在大的数据扭曲的时候非常有效。在第一次循环中,数据库被逻辑划分为大小相等的块,对每个分块执行局部支持计数,然后对它们进行群集,用以生成候选2-项集。接下来,数据库被划分为同构的分块,每个处理器在局部分块上独立地执行DIC算法。这些在共享内存系统上实现的基于Apriori并行算法存在着一些严重的缺陷,如极高的I/O负载、磁盘竞争和欠佳的数据放置。3.2数据库mlfptZaiane等提出了基于FP-growth的MultipleLocalFrequentPatternTree(MLFPT)算法,它是在共享内存的有64个处理器的SGI系统上实现的。MLFPT算法只需对数据库进行二次扫描,避免了生成大量候选集的问题,而且通过在挖掘过程的不同阶段采用不同的划分策略实现最佳的负载平衡。在频繁模式树(FPtree)生成阶段,数据库被划分为大小均等的分块,每个处理器生成一个局部频繁模式树(localFPtree)(见图3)。在挖掘阶段,所有处理器共享这些局部频繁模式树,并生成相应的频繁1-项集的条件库,很大程度上减少了资源竞争的现象。4并行关联规则挖掘算法本文讨论了现有的关联规则挖掘算法,并从实现平台、并行度和负载平衡等方面对并行关联规则算法进行了分析。依靠高性能的并行计算挖掘海量数据库是一种理想的方法,然而想要获得良好的性能并非易事。关于这方面的研究已经取得了很大的成绩,但仍存在许多问题有待进一步地深