2014-11-29
排列组合的非递归算法 这篇文章中介绍了如何以非递归的形式获取多个元素的组合。在此基础上，很容易实现频繁项集挖掘的MaprReduce版本。
数据与需求
假定输入数据是商场中购物者的购买记录，这些数据存放在文本文件中，每一行代表某个人的某次购买记录，这些购买记录由商品对应的id组成，例如如下两次购买记录：
1 2 13 45
2 7 8 19 12 17
需求是找到相对支持度为80%的频繁2项集。假设共有1000条记录，则如果两个商品属于频繁2项目，则需要这两个商品同时在1000×80%=800个购买记录中同时出现。
Map
输入：
一条购买记录，例如“1, 2, 13, 45”
通过生成组合的算法生成所有由两个商品id构成的组合并根据id的值从小到大排序，若购买记录中商品数量小于2，则不输出。 输出：
key: id_x, id_y
value: 1
Reduce
输入：
key: id_x, id_y
values: 1, 1, 1, 1, ...
根据输入的values，计算res = sum(values)，若res >= 800，则输出。
输出：
key: id_x, id_y
value: res
至此，MapReduce job结束。
补充
在一个MapReduce job中也可以同时获取多个大小的频繁项集，例如同时获取相对支持度为80%的频繁2项集、频繁3项集。具体操作是在Map Task中计算2个商品的组合、3个商品的组合。
在计算多个大小的频繁项集时，其结果可以混合地输出到文件按中，也可以将不同大小的频繁项集输出到不同文件，相同大小的频繁项集输出到同一个文件。关于多个输出，在Hadoop中需要了解MultipleOutputFormat类和MultipleOutputs类，可以参考《Hadoop权威指南 第2版》第7章中的“多个输出”这一节。