algorithm - 如何优化Apriori算法？

Question

我已经在hadoop中使用 map-reduce 框架在数据集上实现了先验 算法。

谁能指导我如何优化先验算法(在hadoop map-reduce中)？

我将非常感谢。

谢谢!

编辑代码:

//MAPPER 
public void map(LongWritable key, Text value, Context context)
        throws IOException, InterruptedException {
    Utils.count++;
    String line = value.toString();
    String[] items = line.split(" ");

    Arrays.sort( items );
    LinkedHashSet myPowerSet = powerset(items);
    for (Iterator iterator = myPowerSet.iterator(); iterator.hasNext();) {
        Object i = iterator.next();
        String _key = i.toString().replaceAll("\\[|\\]| +", "");
        context.write(new Text(_key), new IntWritable(1));
    }
}
//COMBINER
public void reduce(Text key, Iterable<IntWritable> values, Context context)
        throws IOException, InterruptedException {

    int localSum = 0;

    for (IntWritable value : values) {
        localSum += value.get();
    }
    context.write(key, new IntWritable(localSum));
}
//REDUCER
public void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException
{
    int minSupportCount = 3;
    int supportCount = 0;

    for(IntWritable value : values) {
        supportCount += value.get();
    }
    if (supportCount >= minSupportCount) {
        context.write(key, new IntWritable(supportCount));  
    }
}

Answer 1

首先:

您发布的代码不是Apriori

它缺少Apriori的所有重要思想。与其执行这些聪明的优化，不如执行一个非常昂贵的实现，它将使您的数据消耗成倍增加。不要这样

避免:

LinkedHashSet(非常慢)

powerset(使用真正的Apriori算法，避免使用powerset!)

无类型迭代器(使用泛型)

正则表达式(慢，尤其是未预编译时)

不必要的物化(洗牌成本)

重新创建IntWritable(垃圾回收成本)

首先，请尝试对应用程序进行性能分析。
还将其与ELKI和SPMF中已知的良好实现进行比较。与代码(在群集上)相比，您可以在这些工具(在单个内核上；也可以尝试FPgrowth)上处理的最大数据集是多少。
如果这些工具可以在单个CPU上处理比您的代码大10000倍的数据，我不会感到惊讶。