基于MapReduce的频繁项集挖掘

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章中的“多个输出”这一节。

( 完 )