FP-Growth是一种常被用来进行关联分析，挖掘频繁项的算法。与Aprior算法相比，FP-Growth算法采用前缀树的形式来表征数据，减少了扫描事务数据库的次数，通过递归地生成条件FP-tree来挖掘频繁项。参考资料[1]详细分析了这一过程。事实上，面对大数据量时，FP-Growth算法生成的FP-tree非常大，无法放入内存，挖掘到的频繁项也可能有指数多个。本文将分析如何并行化FP-Growth算法以及Mahout中并行化FP-Growth算法的源码。
1. 并行化FP-Growth
并行化FP-Growth的方法有很多，最早提出使用MapReduce并行化FP-Growth算法的应该是来自Google Beijing Research的Haoyuan Li等（见参考资料[2]）。他们提出使用三次MapReduce来并行化FP-Growth，整个过程大致可以分为五个步骤：
Step 1：Sharding
为了均衡整个集群的读写性能，将事务数据库分成若干个数据片段（shard），存储到P个节点中。
Step 2：Parallel Counting
与WordCount类似，通过一次MapReduce来计算每一个项(item)的支持度。具体来说，每一个mapper将从hdfs中取得事务数据库的若干个数据片段(shards)，所以mapper的输入是<key, value=Ti>，Ti表示数据片段中的一条数据。对于Ti中的每一个项aj，mapper输出<key=aj, value=1>。当集群中的所有mapper处理完数据之后，所有key=aj的键值对将被分配到同一个reducer，所以reducer的输入是<key=aj, value={1, 1, ... , 1}>。reducer只需要进行一次求和，然后输出<key=aj, value=sum{1, 1, ... , 1}>。最终将得到一张按照支持度递减排序的列表，称之为F-List：
图1
Step 3：Grouping Items
将F-List中的项（item）分为Q个组（group），每一个组都有一个唯一的group-id，我们将所有项以及其所对应的group-id记为G-List。
Step 4：Parallel FP-Growth
这一步骤是并行化FP-Growth的关键，也是整个算法中相对难以理解的部分。这一步骤中将用到一次MapReduce。每一个mapper的输入来自第一步生成的数据片段，所以mapper的输入是<key, value=Ti>。在处理这些数据片段之前，mapper将读取第三步生成的G-List。G-List其实是一张Hashmap，键是项，值是项所对应的group-id，所占空间一般并不会很大，可以放入内存中。从Ti的最后一项开始向前扫描，或者说从右向左扫描，如果aL在G-List中对应的group-id是第一次被扫描，则输出{a0，a1，…，aL}，否则不输出任何数据。以图1中所示的数据为例，假如支持度阈值为1，Q为3，那么将得到G-List：
图2
其中，第三列是group-id。假如mapper的输入是{牛奶，鸡蛋，面包，薯片}，从最后一项开始扫描，输出<key=1，value={牛奶，鸡蛋，面包，薯片}>。之后的两项是面包和鸡蛋，其所对应的group-id和薯片相同，所以不输出任何数据。第一项是牛奶，其所对应的group-id未曾出现过，所以输出<key=2，value={牛奶}>。
所有group-id相同的数据将被推送到同一个reducer，所以reducer的输入是<key=group-id，value={{ValueList1}，{ValueList2}，…，{ValueListN}}>。reducer在本地构建FP-tree，然后像传统的FP-Growth算法那样递归地构建条件FP-tree，并挖掘频繁模式。与传统的FP-Growth算法不一样的是，reducer并不直接输出所挖掘到的频繁模式，而是将其放入一个大小为K，根据支持度排序建立的大根堆，然后输出K个支持度较高的频繁模式：<key=item，reduce={包含该item的Top K Frequent Patterns}>。
Step 5：Aggregating
上一步挖掘到的频繁模式Top K Frequent Patterns已经包含了所有频繁模式，然而上一步的MapReduce是按照groupID来划分数据，因此key=item对应的频繁模式会存在于若干个不同groupID的reduce节点上。为了合并所有key=item的键值对，优化结果展现形式，可利用MapReduce默认对key排序的特点，对挖掘到的频繁模式进行一下处理：依次将Top K Frequent Patterns的每一个item作为key，然后输出包含该key的这一条Top K Frequent Patterns。所以，每一个mapper的输出是<key=item, value={该节点上的包含该item的频繁模式}>，reducer汇总所有mapper的输出结果，并输出最终的结果<key=item, value={包含该item的所有频繁模式}>。
2. Parallel FP-Growth源码分析
Mahout提供了一些机器学习领域经典算法的实现。Mahout0.9之后的版本已经移除了Parallel FP-Growth算法。本文将分析Mahout0.8中Parallel FP-Growth的源码。
图3
FPGrowthDriver.Java