论文部分内容阅读
频繁项目集挖掘是数据挖掘研究中的基础研究内容。它在电子商务、网页查询分析、网络入侵检测和疾病诊断等领域有着广泛的应用。随着信息社会的不断发展,尤其是互联网领域的蓬勃发展,人类社会产生的数据呈爆炸式的增长,“大数据”研究应运而生。如何有效地存储和处理日益增长的数据成为目前亟待解决的问题。云计算的提出为“大数据”的存储、挖掘等问题提供了解决方案。本文对云计算环境下频繁项目集挖掘算法并行化作了较深入的研究,取得了如下成果：1.提出了两种基于Apriori的迭代式Map/Reduce频繁项目集并行挖掘算法MRApriori和TR_MRApriori。MRApriori算法在每次迭代中,先在各计算节点使用Apriori算法计算出候选的k-项集,然后对各个节点的候选结果进行合并,以得到频繁的k-项集。为了提高MRApriori的算法效率,提出了基于事务约减的改进算法TR_MRApriori。TR_MRApriori算法通过记录每次迭代中对下一次迭代中有影响的事务号,大大减少了事务的访问量。实验结果表明TR_MRApriori算法比相关文献提出的方法具有更高的效率。2.提出了一种基于FP-Growth的频繁项目集并行挖掘算法FPPM。FPPM算法先在每个计算节点上构造局部频繁模式树,并对之进行挖掘得到局部频繁项目集,接着合并局部频繁项目集以得到全局频繁项集,由于此时得到的结果并不完备,所以对合并后未达到最小支持度阈值的项目集,重新计算其支持度。实验结果表明FPPM算法具有较好的可扩展性,且能较好的解决相关文献算法网络通信量过大的问题。3.提出了一种基于FP-Growth的频繁项目集并行挖掘算法SBPFP。该算法对样本数据计算出每个项目对应的子频繁模式树的挖掘时间,并以该时间为权重的度量因子。接着按权重将项目进行分组,然后将数据均衡划分到其所对应的计算节点上。最后在计算节点上获得该组项目所对应的频繁项目集。实验结果表明SBPFP算法具有较好的运行效率和可扩展性,同时该算法的运行负载性能比相关文献提出的算法更加均衡。4.提出了一种基于Eclat的频繁项目集并行挖掘算法MREclat。MREclat首先将水平型数据库转换成垂直型数据库,然后将转换后的数据分发到各个计算节点上进行求解,在分发数据时引入了均衡策略使得负载达到平衡。实验结果表明MREclat具有较高的可扩展性和较好的加速比,且比相关文献提出的算法效率更高。