秦 军，郝天曙，董倩倩

(1.南京邮电大学 教育科学与技术学院，江苏 南京 210003；2.南京邮电大学 计算机学院，江苏 南京 210003)

基于MapReduce的Apriori算法并行化改进

秦 军1，郝天曙2，董倩倩2

(1.南京邮电大学 教育科学与技术学院，江苏 南京 210003；2.南京邮电大学 计算机学院，江苏 南京 210003)

基于MapReduce的并行Apriori算法解决了传统Apriori算法多次扫描数据库的问题，但是其候选集仍然由频繁项集经过串行自连接产生,并产生了大量的候选集中间数据。为了提高Apriori算法挖掘频繁项集的效率，在基于MapReduce的Apriori算法的基础上对连接步进行并行化改进，提出大数据环境下挖掘频繁项目集的新算法—CApriori算法。新算法通过Map、Reduce过程从频繁k-项集中并行得到k+1项候选集，使得Apriori算法产生频繁项集的整个过程并行化，减少了迭代过程中候选集数目，节约了存储空间和时间开销。通过对时间复杂度进行分析比较，改进算法在处理大规模数据时会大大减少连接步的时间消耗。将CApriori算法在Hadoop平台上进行了实验，结果表明改进算法在大数据和较小支持度环境下都具有更高的效率，且能取得优异的加速功能。

关联规则；数据挖掘；MapReduce；Apriori

0 引 言

关联规则[1]挖掘用于从大量数据中挖掘出有价值的数据项之间的相关关系。关联规则揭示了数据项间未知的依赖关系，根据所挖掘的关联关系，可以从一个数据对象的信息来推断另一个数据对象的信息。关联规则最为经典的是Apriori算法，该算法采用逐层迭代方法，通过连接和剪枝得到频繁项集。其缺点是重复扫描数据库，产生大量的候选集，算法效率较低。……