基于Spark的分布式频繁项集挖掘算法研究

摘要

自20世纪80年代以来，尤其是互联网技术的兴起，导致了海量数据的产生。如何自动、充分利用这些海量数据，顺利解决海量数据中存在的“数据丰富，知识困乏”问题，成为一个迫切需要解决的难题，数据挖掘技术正是在这样的背景下孕育而生的。
　　频繁项集挖掘技术是数据挖掘研究课题中一个很重要的研究基础，它是关联规则分析、序列项集、相关性分析等许多重要数据挖掘任务的基石。随着大数据时代的到来，如何快速、有效地从海量数据中挖掘出有用的信息就变得尤为重要了。近几年，大数据处理引擎Spark的出现，为海量数据的高效处理提供了一个新的解决思路。本文针对频繁项集挖掘技术，充分利用Spark计算引擎的优势，研究基于Spark的分布式频繁项集挖掘算法，主要工作如下：
　　首先，设计一个数据分区策略，使算法能够达到数据独立。针对基于多处理器系统和Hadoop集群的频繁项集挖掘算法通信负载高的问题，通过本文的分区策略，将原始数据进行转换，使得集群中各个节点的数据彼此相互独立，进而可以并行地挖掘频繁项集，从而避免了节点之间的通信，提高了算法的效率。
　　其次，提出均衡分配任务的方法，使集群达到负载均衡。针对传统频繁项集挖掘算法没有负载均衡能力的问题，本文根据原始数据集的划分，通过对数据的重分区和任务的合理分配，将子任务合理地分配到各个计算节点，使集群能够达到负载均衡。
　　然后，研究和选择合适的大数据处理平台，设计分布式频繁项集挖掘算法。针对基于多处理器系统的频繁项集挖掘算法没有容错机制，而基于Hadoop集群的频繁项集挖掘算I/O开销大，不适合迭代计算的问题，我们采用了Apache Spark大数据快速处理引擎来设计分布式频繁项集挖掘算法，从而使算法在高效处理、可伸缩性、负载均衡和容错机制上拥有着优秀的表现。
　　接着，提出两个优化策略以优化本文提出的DFPS算法，使得它在面对大规模计算集群的时候能够充分利用集群的资源。针对本文提出的DFPS算法运行在大规模集群上可能会出现的并行度不够高、没有充分利用集群的计算能力的问题，本文提出了用户自定义和集群自适应两种优化策略来完善DFPS算法。通过将任务划分为更加细小的子任务这种方式，提高了算法的并行度，充分利用了集群的计算能力，使得算法的效率更高。
　　最后，将本文提出的DFPS算法应用到实际的科研项目中。为了验证DFPS算法的实用性和性能，我们将它应用在《SAP大数据技术平台的搭建和技术研究》项目中。项目包括大数据平台的研究设计和搭建、HANA与 R语言的集成，以及基于大数据平台的相关技术研究。DFPS算法是本项目研究的数据挖掘技术之一，在项目的实施过程中，检验了DFPS算法的实用性和挖掘效率。

目录

声明

第一章 绪论

1.1 课题研究背景与意义

1.2 国内外研究现状

1.3 研究的主要内容和创新点

1.4 论文的结构安排

第二章 相关技术分析

2.1 Spark

2.2 频繁项集挖掘算法

2.3 本章小结

第三章 基于Spark的分布式频繁项集挖掘算法

3.1 FP-growth算法

3.2 基于Spark的分布式频繁项集挖掘算法设计

3.3 本章小结

第四章 面向大规模Spark集群的DFPS优化策略

4.1 面向大规模Spark集群的DFPS优化策略概述

4.2 用户自定义优化策略

4.3 集群自适应优化策略

4.5 本章小结

第五章 实验与分析

5.1 实验环境与数据集概述

5.2 PFP算法和YAFIM算法

5.3 DFPS算法验证实验

5.4 本章小结

第六章 DFPS算法在项目中的应用

6.1 项目概述

6.2 项目实施

6.3 本章小结

第七章 总结与展望

7.1 全文总结

7.2 展望

参考文献

攻读学位期间的研究成果目录

致谢