关联规则算法用来描述事物之间的联系和挖掘事物之间的相关性，其核心是通过统计数据项获得频繁项集，被广泛应用于分类设计、捆绑式销售、仓储货存配置等领域，涌现出了Apriori、Partition、fp-Growth、CD、DD、CaD等诸多频繁项集挖掘算法，随着大数据时代的到来，传统的挖掘算法无论运算能力还是并行效率都不能满足人们的要求，云计算和并行计算的出现给频繁项集挖掘带来了新的契机。

传统的Apriori算法过程：

采用逐层迭代的方法，从k项集推出k+1项集。首先发现频繁项集，然后生成关联规则，查找频繁项集会消耗大量计算机资源

D为数据集，设L _k是k项频繁项集，C _k是k项候选集

传统Apriori算法过程：

1. 求频繁1项集L₁，以集合I作为候选集C₁,扫描数据集D，获取候选项集C₁的支持度，找出最小支持度min_sup的元素作为频繁1项集L₁；

2. 扫描数据集D，获得候选集C_k的支持度，中出最小支持度min_sup的元素作为频繁k项集L_k

3. 通过频繁项k项集L _k产生k+1项候选集C_k+1

4. 迭代执行步骤（2）和步骤（3），知道不能找到k+1项候选集

传统Apriori缺陷：需要多次扫描数据集，每次扫描都会涉及相当规模的逻辑运算

Apriori的Mapreduce并行化

随着数据规模的增大，传统并行方案因资源需求过大或因通信消耗过多而变得低效，基于云计算的MapReduce编程模型能很好地解决海量信息并行处理的通信问题，同时还具有负载均衡和强大的容错能力。

普通Apriori的Mapreduce并行化思想：首先利用MapReduce并行编程模型的键值进行特性对输入的原始数据集进行Map分块处理，主进程将这些数据分块分布到Hadoop集群中的每台计算机上，然后并行算法对每台计算机上的分块数据进行如下处理：

1. 主进程通过分块数据集与原始数据集的对比产生1项候选集

2. 由1项候选集与原始数据集进行对比，可以算出没想事务的支持度，这些支持度与程序中给定的支持度进行对比，得出1项频繁项集

3. 由1项频繁项集产生2项频繁项集

4. 主次迭代直到产生k项候选集，k项候选集与原始数据集对比，如果存在k项候选集，则继续迭代执行，如果不存在，则最终得到k-1项候选集

由于MapReduce的机制，上述过程为每台计算机上的Map进程计算出的分块候选集，接下来MapReduce编程模型中的Reduce进程把每台计算机上的Map进程获取的每个分块的k项候选集支持数合并获取全局k项候选集的支持数，由全集候选集的支持数计算出全集k项频繁项集。当一个数据分块的全局k项频繁项集计算出以后，每台计算机会启动下一个Map进程处理第二个数据分块，这样一次循环，知道架构处理完所有数据分块。

基于Hadoop平台改进Apriori算法有效解决了节点失效和负载均衡问题

1. Hadoop集群中，当一台计算机出现故障而停止计算时，这台计算机上的计算任务会被转移到集群中的其他空闲计算机上继续执行未完成的计算任务

2. 在Hadoop上处理的计算任务无论大小，通过配置文件的修改可以决定每个Map数据块的大小，可以做到数据分块数远大于计算节点数，计算资源不会被浪费，做到了负载均衡。

Apriori算法MapReduce并行化改进

上述Apriori算法的MapReduce并行化是在候选项集支持数的统计阶段并行扫描数据库，没遇到一条事务包含候选项集就产生一个<itemset,1>的键/值对，在处理海量数据且支持度较低时，算法产生了大量值为1的键/值对，增加了mapReduce 系统的负担，影响算法执行效率。

改进的Apriori算法MapReduce化将Apriori数据分割的分组思想应用在候选项集的支持数统计阶段，实现候选项集支持数的分组统计。过程如下：

1. 采用类似单词计数的过程并行扫描数据库，找出满足最小支持度的1－频繁项集L1

2. L1 通过自身连接产生2－候选项集C2，采用候选项集支持数的分组统计算法统计C2 的支持数，形成2－频繁项集L2; 相同步骤，L2 产生L3，如此迭代循环，直到没有新的k－频繁项集产生．

步骤1) 可以定义Combiner方法，提升Job的速度; 步骤2) 的候选项集支持数的分组统计不适合定义Combiner方法，因为无法定义一个与Map输出类型一样的Combiner函数．候选项集支持数的分组统计步骤如下:

1. 将原数据库划分为n组，使各组数据足够载入内存运行，并分别统计候选项集在各组数据中的支持数，称为候选项集的局部支持数;

2. 合并候选项集在各组数据中的支持数，形成最后候选项集的全局支持数．以下是候选项集在各组数据中的支持数统计伪码，其中count%N标识事务所分配的组id

   算法：候选项集在各组数据中的支持数统计

   输入: 数据库，分组数N，k－候选项集

   输出: 局部的k－候选项集支持数

   count 0;

   Map( key1= unused，value1 = transaction)

   count ++;

   output(key2 = count%N，value2 = transaction) ;

   Setup( )

   candidatesetlist读取k－候选项目集;

   Reduce(key2 = id，iterable( value2) = iterable( transaction) )

   transactionListiterable( transaction) ; //读取被分配到本组的事务

   foreachitemsetincandidatesetlist do

   output(key3 = itemset，value3 = supp_count_local( itemset) ) ;

   end

基于候选集产生的关联规则挖掘，在海量数据且支持度较低时，所产生的( k－1) －频繁项目集数是相当大的．因此，有必要实现候选项集生成的MapReduce并行策略．由于k－候选项集是由前k－2项相同的两个( k－1) －频繁项集的连接产生的，根据MapReduce模型，可以将( k－1) －频繁项集的前k－2项作为键最后一项作为值，然后再作为Map的输出．键相同的就规约到同一个reduce中，这样就可以很容易地处理前k－2项相同的两个( k－1) －频繁项集的连接操作．例如假设Map的输入是以下5个3－频繁项集:

＜1，2，3＞，＜1，2，4＞，＜1，2，5＞，＜1，3，4＞，＜1，3，5＞

于是Map输出为:

＜＜1，2＞，3＞，＜＜1，2＞，4＞，＜＜1，2＞，5＞，＜＜1，3＞，4＞，＜＜1，3＞，5＞;

MapReduce系统经过排序分组后，结果为:

＜＜1，2＞，［3，4，5］＞，＜＜1，3＞，［4，5］＞;

作为Reduce的输入，假定( k－1) －频繁项集所产生的k－候选项集均已满足频繁项目集的性质，则Reduce最后的输出为:

＜1，2，3，4＞，＜1，2，3，5＞，＜1，2，4，5＞，＜1，3，4，5＞

算法：根据（k-1）-项频繁项集产生k-候选项集

输入: ( k－1) －频繁项集．

输出: k－候选项集．

Setup( )

hashtable 读取( k－1) －频繁项目集;

Map( key1 =frequent( k－1) _itemset，value1 = support_count)

p = frequent( k－1) _itemset;

output( key2 = (p［0］，p［1］，，p［k－3］) ，value2 = p［k－2］) ;

Reduce( key2 = (p［0］，p［1］，，p［k－3］) ，iterable( value2) = iterable( value2) )

item［］ iterable(value2) ;

sort( item) ;

for i : 0 item． lengthdo

for j : i +1item． lengthdo

itemset = ( p［0］，p［1］，，p［k－3］，item［i］，item［j］) ;

if all ( k－1) －subset ofitemset inhashtablethen

//itemset 的所有k－1项子集都是频繁集

output( key3 =itemset，value3 =0) ;

end

end

end

参考文献：博文http://blog.csdn.net/lizhengnanhua/article/details/9061887

               论文：基于迭代式MapReduce的Apriori算法设计与实现 章志刚

                         基于MapReduce并行的Apriori算法改进研究    黄立勤

                         基于支持度矩阵的关联规则挖掘算法在公安情报分析中的应用 李为