基于Hadoop的改进的并行Fp-Growth算法

发布时间：2018-12-25 07:44

【摘要】：频繁模式挖掘是数据挖掘领域的重要算法。频繁模式挖掘在事务数据库、时间序列数据库和许多其他类型数据库的挖掘研究中都得到了广泛的应用。然而,传统的Frequent-pattern Growth算法(简称Fp-Growth算法)在处理大规模数据时,无论是存储上还是计算上都会遇到瓶颈,这就需要对Fp-Growth算法进行并行化处理。现有的并行Fp-Growth算法已经解决了如何划分数据库事务集这一问题,并保证了划分后的事务集彼此之间相互独立,但是现有的并行Fp-Growth算法和对事务集进行划分的时候缺乏了对负载均衡的考虑。因此,实现负载均衡的并行Fp-Growth算法是本文的主要问题。 Hadoop是Apache基金会下的一个开源的分布式并行编程框架,允许计算机集群通过使用简单的编程模型分布式的处理大型数据集。Hadoop解决了并行计算存在的工作调度、分布式存储、容错处理、网络通讯等问题,这就使得开发者只需要关注算法本身,而系统本身的调度等问题都交由Hadoop处理。基于上述原因,所以本文使用Hadoop框架来实现并行化的Fp-Growth算法。本文主要完成了以下两个工作,一个是对现有的并行Fp-Growth算法提出了改进,另一个是将本文提出的并行算法应用于频繁用户访问序列的挖掘上。首先,本文在国内外的并行Fp-Growth算法的研究基础之上,利用估算每一个频繁项的负载的方法,对现有的并行Fp-Growth算法的分组策略进行了改进。实验证明本文提出的改进的并行Fp-Growth算法优于现有的并行Fp-Growth算法,本文提出的算法具有更好的负载均衡能力和执行效率。其次,由于Web服务器日志上存储了海量的用户访问信息,因此,可以从海量的数据中发现那些隐藏起来的、有价值的用户行为信息。所以,本文将提出的算法应用于Web日志挖掘这一领域,用来挖掘频繁的用户访问序列。基于这一应用方向所得到的结果可以对日志的来源网站提供指导和参考意见,具有实际的应用价值和商业价值。
[Abstract]:Frequent pattern mining is an important algorithm in the field of data mining. Frequent pattern mining is widely used in the research of transaction database, time series database and many other kinds of database. However, the traditional Frequent-pattern Growth algorithm (Fp-Growth algorithm for short) will meet the bottleneck in both storage and computation when dealing with large-scale data, which requires parallelization of Fp-Growth algorithm. The existing parallel Fp-Growth algorithms have solved the problem of how to partition database transaction sets, and ensured that the partitioned transaction sets are independent of each other. However, the existing parallel Fp-Growth algorithms and transaction set partitioning lack of load balancing considerations. Therefore, the parallel Fp-Growth algorithm for load balancing is the main problem in this paper. Hadoop is an open source distributed parallel programming framework under the Apache Foundation, which allows computer clusters to deal with large data sets distributed by using simple programming models. Hadoop solves the problem of scheduling and distributed storage in parallel computing. Fault-tolerant processing, network communication and other problems, which make developers only need to pay attention to the algorithm itself, while the system itself scheduling problems are handled by Hadoop. For the above reasons, this paper uses Hadoop framework to implement parallel Fp-Growth algorithm. The main work of this paper is as follows: one is to improve the existing parallel Fp-Growth algorithm, the other is to apply the parallel algorithm to mining frequent user access sequences. Firstly, based on the research of the parallel Fp-Growth algorithm at home and abroad, this paper improves the grouping strategy of the existing parallel Fp-Growth algorithm by using the method of estimating the load of each frequent item. Experiments show that the improved parallel Fp-Growth algorithm is superior to the existing parallel Fp-Growth algorithm, and the proposed algorithm has better load balancing ability and execution efficiency. Secondly, because a large amount of user access information is stored in the Web server log, the hidden and valuable user behavior information can be found from the massive data. Therefore, the proposed algorithm is applied to the field of Web log mining, which is used to mine frequent user access sequences. Based on this application direction, the results can provide guidance and reference for the source websites of the log, and have practical application value and commercial value.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP338.6

【参考文献】