论文部分内容阅读
目前,随着数据规模的急剧增长,如何在这些海量的数据中挖掘出有效的信息已经成为了全世界备受瞩目的话题,因此,数据挖掘成为了极其热门的研究领域。关联规则挖掘作为数据挖掘领域中非常重要的研究方向之一,国内外许多学者对关联规则挖掘技术进行了诸多的研究,但仍有很多问题需要完善。作为关联规则挖掘最经典的算法,Apriori算法能够有效地挖掘出事务数据库的频繁项集,根据挖掘出的频繁项集可以快速准确地找出关联规则。然而,Apriori算法具有两大显著的缺陷,该算法需要多次扫描数据库和产生大量无用的候选项集,也正是因为这两大缺点,给关联规则挖掘技术的发展带来了极大的挑战。在对Apriori算法深入研究和分析的基础上,本课题的主要研究工作集中在对Apriori算法的改进,主要体现在以下几个方面:1)针对传统Apriori算法I/O开销大,产生大量多余的候选项集和运行效率低等问题,改进了一种基于映射的Apriori改进算法—Mapping_Apriori。该算法首先采用映射结构来存储数据库中的事务,对事务数据库进行有效压缩,降低大量的I/O负担,提出一种新的降低映射维度的策略;同时,通过映射这种数据结构可以快速地计算出候选项集的支持度,降低计算复杂度;最后,根据频繁项集的相关性质,可以对频繁项集k-1L实现预先瘦身的效果,有效地避免无用的候选项集的产生。通过实验,验证该算法的有效性,提高了算法的运行效率。2)通过对频繁模式增长算法FP-Growth的深入研究,该算法可以通过不产生候选项集来找出频繁项集,该算法的核心是频繁模式树FP-tree可以对事务数据库进行高效压缩。基于FP-tree的优势,改进了一种基于频繁模式树的Apriori的改进算法—FP_Apriori。该算法将整个事务数据库投影到FP-tree上,避免大量的I/O开销;同时,提出一种更加有方向和有针对性地对FP-tree的搜索策略,降低了算法的运行时间;最后同样采用Mapping_Apriori算法的原理对频繁项集k-1L进行预先瘦身。通过实验,对比分析Apriori算法、Mapping_Apriori算法和FP_Apriori算法的运行效率,得到了比较满意的效果。3)针对传统串行算法固有的局限性,将利用MapReduce计算框架来实现算法的并行化。为了将Apriori更好地适应MapReduce计算框架,改进了一种基于位阵矩阵的BM_Apriori算法并移植到Hadoop平台上,实现算法的并行化,并通过实验来验证算法的并行效率,为处理海量数据提供借鉴意义。