基于MapReduce的分块压缩矩阵Apriori的并行化研究

Parallel Study on the Apriori Algorithm of Compression Matrix Based on MapReduce Programming Mode

针对经典的Apriori算法需要多次扫描数据库,不适合大规模数据这个问题,提出了一种改进的Apriori算法.该算法采用布尔向量关系运算思想,将事务数据库扫描后转化成压缩矩阵,在MapReduce框架下将压缩矩阵进行分块,每块分别被做并列式处理.利用分压缩矩阵快速计算所有的候选项集,从中产生频繁K-项集,降低了Apriori算法的时间复杂度.

In view of the problem of the classic Apriori algorithm need to scan the database re-peatedly and it is not suitable for large-scale data, in this paper, an improved Apriori algorithm was proposed, which used the relationship operation of the Boolean vector, and transformed the transaction database after scanning into a compression matrix. Under the MapReduce frame-work, the compression matrix was divided into blocks for distributed processing. Sub-com-pression matrix was used to do fast calculation for all candidate sets, and the frequent K sets had been generated from all of above, finally, the time complexity of Apriori algorithm was reduced.