基于MapReduce的top-k高效用模式挖掘算法

摘要

High utility pattern mining has been widely applied in the field of data mining.Some top-k high utility pattern mining algorithms based on tree-like and list-like structures were proposed.However,tree-like algorithms generated a large number of candidates,and comparing operation was costly during the process of utility pattern growth in list-like algorithms.In addition,the amount of information data increased exponentially in information society.Thus,it required memory usage and computational cost in mining process,especially the dataset size was huge.In order to address above issues,this paper proposed top-k high utility pattern mining algorithm based on MapReduce,called TKHUP_MaR.TKHUP_MaR needed to scan database twice and used three MapReduce phases to parallelize top-k high utility pattern mining.The experiment results show that TKHUP_MaR is effective in the process of mining top-k high utility patterns on parallel environment.%高效用模式挖掘被广泛地应用于数据挖掘领域.为了挖掘指定数量的高效用模式,一些基于树结构和效用表结构的top-k高效用挖掘算法被提出,但前者在挖掘过程中产生了大量候选模式,后者在效用模式增长时需要进行多次比较;同时,由于在信息社会,数据量呈爆炸性增长,所以在数据集过大的情况下,挖掘高效用模式需以大量存储空间以及计算开销为代价.为了解决这两个问题,基于MapReduce的top-k高效用模式挖掘算法(TKHUP_MaR)被提出.该算法通过两次扫描数据库,利用三次MapReduce来实现并行top-k高效用模式的挖掘.通过实验表明TKHUP_MaR算法在并行挖掘top-k高效用模式的过程中是有效的.