Aprior算法Hadoop上实现思路与关键部分代码

chinaab

　　本人最近研究Aprior算法，由于要实现海量数据的分析挖掘，需要在hadoop平台加以实现。
　　在网上看过一些Aprior算法Mapreduce的代码，感觉拿过来都不好直接用，而且，多数都不是原味的Aprior，或者经过改进，是FP-growth算法，或者是将数据分块，各块独立运行Aprior算法，不是严格意义上的Aprior算法。
　　本人也是几经实验，终于自己也实现了一种基于Mapreduce的原汁原味的Aprior算法的分布式实现。
　　Aprior分布式实现的问题：输入有多个，一个是事务数据库，一个是全局的候选项集，而候选项集是不能分块的，如果分块交由不同的node执行，分别统计出来的支持度肯定会有缺失。这就要求Aprior算法候选项集要做为一个完整的参数，于是想到了把候选项集存入内存。这就是我这个分布式实现的一个关键点了。
　　Aprior算法分布式实现算法思路：Mapper：k-v输入为事务数据库，外加一个内存中的数据结构，此数据结构即用来存储候选项集，保证了候选项集是完整的不会被分片。输出为候选项(key)-支持度(value)。Reducer：普通的累加求和即可。在写入文件时加一个判断，满足支持度要求才写入文件。2个基本的原子操作就有了。   
　　然后一个完整的Aprior算法流程是： 运行了一个job，即一次Mapreduce，产生相应阶次的频繁项集，将此次job的输出读取入内存中，产生高阶候选项集作为下一个job的在内存中的输入，也就是候选项集，然后，启动下一次job。接下来循环迭代，直到不能产生新的频繁集为止。
　　Mapper类如下：
　　public static class GetGlobalCandItmSupportMapper extends Mapper
{//计算出候选项集  输入：key无效,value,事务数据库全部（一次一条效率有些低。产生一个疑问，如果原始文件500m，64m一个分片，一次读入是500m还是64m呢，如果是64m那就很好。后期可以测试一下。）记录，内存中的全局候选项集，输出，Key,一条候选项，value，一条候选项的支持度
//算法概述：获取内存中的候选项集。缺点，每条记录都要进行一次从字符串转候选项集的工作。
　　int support=3;
private final static IntWritable one = new IntWritable(1);
private Text word = new Text();
　　
public void map(Object key, Text value, Context context) throws IOException, InterruptedException
{
//一个数据结构存储事务数据库，一个数据结构存储所有的候选集，从conf中传入自己想要使用的参数。
ArrayList rawDB=new ArrayList();
ArrayList CandItms=new ArrayList();
String CandItmSets=context.getConfiguration().get("CandItmSets");
System.out.println("CandItmSets are"+CandItmSets);
//构造事务数据库的内存结构
　　String[] tmpLinesRawDB=value.toString().split("\n"); //获取一行一行的数据
String[] tmpOneLineRawDB=null;
for(int i=0;i