论文部分内容阅读
随着信息产业尤其是互联网行业的高速发展,使得人们获取和存储数据的能力不断提高,数据库中存储的数据以指数形式不断增长。但在这些海量数据中,真正对于人们有决策价值的知识却相对匮乏,关联规则挖掘正是用于揭示数据集中不同的项或者属性之间的关联性,找出有价值的多个属性之间关联关系。而最大频繁项集中隐含了所有频繁项集,占用的内存空间较小,并且在挖掘的过程中只用挖掘最大频繁项集,可以有效的减少递归次数和内存应用,且有些数据挖掘应用中也只需要获得最大频繁项集,因而最大频繁项集挖掘的研究有着重要的意义。在如今面对大规模稠密数据项集时,超集检测逐渐成为最大频繁项集挖掘算法运行中耗时最多的步骤,是算法效率提升的一个瓶颈；并且现有的最大频繁项集挖掘算法大都采用基于FP-tree的模式对于空间搜索树进行遍历,在自顶向下的遍历策略中效率并不高。因此本文在查阅了大量国内外相关论文和文献的基础上,针对这两方面的问题,本文改进了基于投影的超集检测算法,提出了基于AFOPT-tree的最大频繁项集算法A-MFI,并在此基础上实现了A-MFI算法在Hadoop平台上的分布式实现。论文的主要工作如下：(1)首先对于数据挖掘尤其是关联规则挖掘和最大频繁项集挖掘的理论、特点及其主流算法进行了介绍,并对云计算和Hadoop云平台的相关知识进行了介绍。(2)针对现有最大频繁项集挖掘算法采用的FP-tree在自顶向下遍历策略中效率不高的问题,本文采用AFOPT-tree模型来构建空间搜索树；针对提升超集检测方法效率的问题,本文提出优化的基于投影的超集检测方法,采用AFOPT-tree模型对传统的MFI-tree进行改造,将基于投影超集检测方法对于MFI-tree自底向上的遍历模式改变为自顶向下的遍历模式,并在MFI-tree中加入一条相同数据项集之间的链表域,提升前瞻剪枝的效率。在这些改进的基础上,提出了基于AFOPT-tree的最大频繁项集挖掘算法A-MFI,并采用不同的数据项集对算法进行实验,验证了算法对比同类算法在超集检测优化和总体运行效率上的优越性。(3)针对面对如今大规模数据集,单机最大频繁项集挖掘算法的运行效率提升有限的问题,本文在对云计算和Hadoop平台的相关知识深入学习的基础上,对A-MFI算法进行了分布式改造,实现了对最大频繁项集挖掘的分布式挖掘。经实验验证,分布式的最大频繁项集挖掘方法相比单机在面对大规模稠密数据项集时运行效率有了明显的提升。(4)最后,对全文内容进行总结,并指出文中现有研究内容的不足,为以后的研究指明方向。