论文部分内容阅读
数据挖掘是应用一定的算法发现隐藏在数据中事先未知的、用户感兴趣的知识的过程。网络信息化时代,数据爆炸式增长,传统的串行算法在处理海量数据时,效率很低,如何提高海量数据挖掘的效率成为一个急需解决的问题,并行数据挖掘是解决这一问题的有效方法。增量挖掘利用已经挖掘出来知识对更新后的数据集进行挖掘,是提高挖掘效率另一个思路。MapReduce是Google提出的一种的简单编程模型,采用分布式并行方式处理海量数据。与其他并行编程模型相比,它在进行程序设计时无需考虑数据的划分、分配以及调度等问题,同时还能处理集群中节点失效。关联规则已经广泛的应用于电子商务、医疗诊断、气象预测、银行、电信等行业,一直都是数据挖掘研究的热点。本文以关联规则中发现频繁项集为出发点,在并行编程模型MapReduce的基础上对并行关联规则及其增量挖掘算法进行研究,旨在提高从海量数据中发现频繁项集的效率。本文首先对关联规则算法进行分析,针对Apriori算法的不足,结合向量的逻辑运算从扫描次数、候选项集生成、事务压缩三个方面对该算法进行改进,设计一种改进算法Apriori_M。其次对MapReduce并行编程模式进行深入分析,为提高Apriori_M算法处理海量数据能力,结合Partition的思想,提出该算法的并行化改进思路,并用MapReduce编程模式实现。然后对关联规则增量挖掘算法进行研究,在FUP算法的基础上,提出两种处理数据集动态增加的并行关联规则增量挖掘算法。整个算法分为产生候选项集与验证候选项集是否频繁两个部分,MFUP1算法串行产生候选项集,再并行地从候选项集中选出频繁的,适合新增数据集规模较小的情况,而MFUP2算法并行产生候选集,再并行验证是否频繁,适合新增数据集规模较大(与原数据集相比仍然较小)的情况。最后对提出的基于MapRedece的并行关联规则算法及并行增量挖掘算法的性能进行分析。为验证算法的性能,在开源的Hadoop云平台上进行仿真分析,实验结果表明并行Apriori_M算法、MFUP1和MFUP2算法能够高效的从海量数据中发现频繁项集,改进后的算法是可行的、有效的。