基于MapReduce的序列模式挖掘算法  

Sequential pattern mining algorithm based on MapReduce programming framework

作　　者：余啸[1] 马传香[1] 李伟亮[1] 金聪[2] 

机构地区：[1]湖北大学计算机与信息工程学院,武汉430062 [2]华中师范大学计算机科学学院,武汉430062

出　　处：《计算机应用研究》2015年第11期3312-3314,共3页Application Research of Computers

基　　金：湖北省自然科学基金资助项目(2011CDB072);国家社会科学基金资助项目(13BTQ050)

摘　　要：针对传统GSP算法需要多次扫描数据库、I/O开销巨大的缺点,提出了一种基于MapReduce编程框架的序列模式挖掘算法MR-GSP(GSP algorithm based on MapReduce)。MR-GSP算法将原序列数据库划分为多个子序列数据库并分发到多个Map节点,Map函数扫描存放在Map节点内存中的子序列数据库,产生局部序列模式,Reduce函数对所有局部序列模式合并,扫描原序列数据库,计算局部序列模式的支持度,得到最终的序列模式。相比于传统GSP算法,MR-GSP算法只需扫描两次原始数据库即可得到所有序列模式。实验结果表明,MRGSP算法在对大数据集进行序列模式挖掘时,可充分利用云计算技术的优势,提高挖掘效率。For the disadvantages that traditional GSP algorithm need to scan the database repeatedly and the I/O overhead is huge, this paper proposed a sequential pattern mining algorithm MR-GSP（ GSP algorithm based on MapReduce） based on MapReduce programming framework. The MR-GSP algorithm divided the original sequence database into some sub-sequence databases and distributed them to Map workers, Map function scanned sub-sequence databases stored in memory to generate partial sequence patterns. Reduce function merged all partial sequence patterns and scanned the original sequence database to calculate the support of partial sequence patterns and gained the final sequence patterns. Compared with traditional GSP algorithm, the MR-GSP algorithm gained all sequential patterns by scanning the original database just twice. Experimental results show that the MR-GSP algorithm can take advantages of cloud computing technology to improve the efficiency of sequential pattern mining in big data.

关 键 词：数据挖掘 GSP算法 序列模式 MAPREDUCE 子序列数据库 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程] TP301.6[自动化与计算机技术—控制科学与工程]