一种基于MapReduce架构的并行矩阵Apriori算法.PDFVIP

优先出版 计 算 机 应 用 研 究 第34 卷 一种基于MapReduce 架构的并行矩阵Apriori 算法* 1 2, 3 谢志明 ，王 鹏 (1．汕尾职业技术学院 信息工程系，广东 汕尾 516600 ；2 ．成都信息工程学院 并行计算实验室，成都 610225 ；3．中 国科学院成都计算机应用研究所，成都 610041) 摘 要：传统数据挖掘关联规则 Apriori 算法直接移植到云计算平台，数据挖掘效率虽然有了数量级的提升，但由于需 要频繁地扫描事务数据库，增加了系统I/O 、内存和通信的开销。提出一种基于矩阵的并行关联规则算法Apriori_MMR ， 该算法结合了数据划分的思想进行并行化改进，简化了生成候选项的连接步骤，仅需对事务数据库扫描两次，同时在计 算过程中还能对事务进行压缩从而进一步提高了算法的性能。通过两种算法在不同数据规模下算法性能对比分析实验和 两种算法在相同数据集不同节点数对比实验，共同验证了Apriori_MMR 的运算效率至少要比Apriori_MR 高出两倍左右， 且设置的支持度阈值越小，效果愈明显。 关键词：数据挖掘；关联规则；Apriori 算法；云计算；矩阵 中图分类号：TP301.6 Parallel matrix apriori algorithm based on MapReduce architecture 1 2, 3 Xie Zhiming , Wang Peng (1. Dept. of Information Engineering, Shanwei Polytechnic, Shanwei 516600, Guangdong, China; 2. Parallel Computing Lab, Chengdu University of Information Technology, Chengdu 610225, China; 3. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China) Abstract: By migrating traditional data mining association rules based Apriori algorithm to cloud computing platform , data mining efficiency can be improved significantly. In this manner ，transaction database should be scaned frequently and the I/O , memory and communication overhead increase simultaneously. Apriori_MMR is proposed which is a matrix based parallel association rule algorithm. Data partition is used in Apriori_MMR to simply the connection step of candidate item generation . We only need to scan the transaction database twice , and a transaction is compressed