Hadoop框架下的一种改进的Apriori算法

An Improved Aprior Algorithm under Hadoop’s Framework

常见的基于Hadoop框架的Apriori改进算法在统计支持度时有扫描数据集、候选项集剪枝等方面效率低下且集群间的数据传输有较大的时间开销的问题,提出了一种Apriori的改进算法Apriori_Ind.算法运用Hadoop集群,使用先按事务对数据集分块,再将数据集的格式转换为<项,事务集>的分块处理策略,使算法充分利用分布式计算优势,实现各节点并行的实现候选项集生成与剪枝操作.并利用前项与后项的新结构表示频繁项集,新结构在各节点进行候选项集生成和剪枝时提高算法效率.Apriori_Ind具有减小集群传输代价、加速剪枝等优势.实验表明新算法适合大规模数据挖掘,特别是项的数量较大的情况下,算法性能有明显的提高.

The common Apriori improved algorithm based on Hadoop framework has the problems of inefficient data scanning,candidate set pruning,etc.,and large time overhead of data transmission between clusters.An improved Apriori algorithm,Apriori_Ind,is proposed.The algorithm uses Hadoop cluster to divide the data set into blocks by transaction,and then converts the format of the data set into a block processing strategy of<item,transaction set>,so that the algorithm makes full use of the advantages of distributed computing and realizes the parallel implementation of each node.The candidate set is generated and pruned.The new items are used to represent frequent itemsets.The new structure improves the efficiency of the algorithm when generating candidate sets and pruning at each node.Apriori_Ind has the advantage of reducing the cost of cluster transmission and speeding up pruning.Experiments show that the new algorithm is suitable for large-scale data mining,especially in the case of a large number of items,the performance of the algorithm is significantly improved.