基于Hadoop的并行关联规则算法研究

在数据挖掘中,关联规则的挖掘是一个非常重要的研究方向。关联规则算法处理的对象基本是大型数据库,计算量和I/O量非常大。大型数据库的数据通常达到了TB级甚至PB级。处理这样庞大的数据集,串行算法不能满足及时处理的要求,因此,研究适合的并行算法是必须的。传统的并行计算一般基于MPI(Message Passing Interface)实现的。基于MPI实现的平台无法处理节点失效,而节点失效对于由普通计算机组成的集群来说很难避免。 Google在2004年提出的MapReduce架构能处理节点失效。MapReduce是云计算的主要基础架构。MapRedue通过把数据划分为很多块,启动多个map同时处理实现并行计算。Hadoop是MapReduce架构的开源实现。本文提出基于Hadoop的并行关联规则算法.本文提出的Hadoop的并行关联规则算法是在并行关联规则算法CD(计数分布)算法基础上实现的。对CD算法进行了改进,主要是从频繁项集推出候选集的计算只需有主进程计算一遍,候选集频度统计也只需由主进程计算一遍。 为了评估算法的性能。编写了一个基于Hadoop的并行关联规则挖掘程序。搭建了一个基本的Hadoop平台。通过改变系统map能力配置和数据集规模,运行评估计算。实验结果表明,基于Hadoop的并行关联规则算法在处理超大规模的数据集时具有优势。在处理小规模的数据集时,由于每次计算集群部署和退出任务要花掉一些时间,计算资源浪费比较严重,因此基于Hadoop的并行关联规则算法不太适合小规模数据集的计算。由于Hadoop平台本身能够处理节点失效,因此基于Hadoop平台的并行关联规则算法也能够避免节点失效。从试验时的监控输出来看,基于Hadoop的并行关联规则算法做到了动态负载均衡。 理论和试验表明,基于Hadoop的并行关联规则算法能够处理节点失效,能够做到动态负载均衡,能够适应挖掘超大规模数据集的关联规则。