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

第一章 绪论

1.1 课题研究背景与意义

随着信息化时代的发展，人类的社会生产活动产生了大量有用的数据，尤其是随着数据库的发展和互联网时代的到来，导致了海量数据的产生。在这些海量数据里，隐含着有价值或有潜力的信息。快速地从这些海量数据中提取有用的信息，以辅助上层决策，对国家和企业来说，都是很有意义的。有了这些信息，决策者们再也不用像以前那样光靠经验来做决策，而是多了一个可靠的参考信息。所以，如何有效地充分利用这些数据，就成了国家和企业决策者们迫切关心的问题。在这样的大背景下，数据挖掘（Data Mining，DM）技术孕育而生，，有时也称之为知识发现（Knowledge Discovery in Database，KDD）技术。由于各个领域都急需利用数据挖掘技术来处理数据，以此获取数据中蕴含的知识和信息，所以数据挖掘技术得到了学术界和工业界的高度重视，并展开了广泛而深入的研究，涌现出了大量优秀的算法。

...............

1.2 国内外研究现状为了从已有的海量数据中提取有用的信息，数据挖掘技术孕育而生。关联规则分析是数据挖掘任务中的一个子任务，其目的是从大量的数据中发现项之间有趣的关联和相关关系，而频繁项集挖掘是关联规则分析中最为关键和耗时的一步。随着研究的不断深入，关联规则分析技术已经发展得相当成熟。数据挖掘（Data Mining，DM）[21]有时候也称之为知识发现（KnowledgeDiscovery in Database，KDD）技术，它的一个简单定义是：从数据库中提取或“挖掘”知识。它兴起于上世纪的 80 年代末，并在 90 年代获得了重大发展。1989年，在第 11 届国际人工智能联合会议 IJCAI 上，首次举办了以数据库知识发现为专题的讨论。1995 年，在加拿大的蒙特利尔召开了首届知识发现与数据挖掘国际学术会议（The ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining，SIGKDD’95），正式提出了数据挖掘的概念。

...............

第二章 相关技术分析

2.1 Spark

Spark 诞生于伯克利大学的 AMP 实验室，它是当今大数据领域最为活跃、热门和高效的大数据通用计算平台，Apache Spark 官方对 Spark 的定义是：Spark是一个通用的大规模数据快速处理引擎[64]。因此，可以简单地把 Spark 理解为是一个大数据分布式处理框架。Spark 是一个基于内存计算的大规模数据快速处理引擎，因为它不具备管理计算任务的能力，所以 Spark 需要第三方资源管理平台（如 YARN、Mesos）来调度和分配任务。从图 2-1 可以看出，Spark 可与多种文件系统兼容，如 HDFS、Amazon S3 等。从某种意义上讲，Spark 的出现并不是要消灭 Hadoop。相反，Spark充分利用了 HDFS 和 YARN，可以看作是为了弥补 Hadoop 的缺点而产生的。RDD（Resilient Distributed Datasets）是弹性分布式数据集的简称，它是分布式只读且已分区的集合对象。这些对象是弹性的，即如果数据的某部分丢失，则还可以对它们进行重建，因此它具有自动容错、位置感知调度和可伸缩性。图 2-1 显示的是 Spark 的体系结构。

...............

2.2 频繁项集挖掘算法

关联规则挖掘的整个过程主要分两步来完成：第一步是找出数据库中所有满足最小支持度阈值的频繁项集；第二步是由频繁项集产生所有满足最小置信度阈值的关联规则[1]。由于关联规则挖掘的整体性能主要是由第一步的性能所决定，因此，关联规则挖掘的关键和难点都集中在了频繁项集的挖掘上。随着关联分析技术的不断发展，众多的研究学者提出了许多优秀的频繁项集挖掘算法，包括单机（single-machine）挖掘算法、基于 MPI（Message Passing Interface）的挖掘算法、基于 MapReduce 的挖掘算法和基于 Spark 的挖掘算法，接下来分别简要介绍一些优秀的频繁项集挖掘算法。

...............

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

3.1 FP-growth 算法 ................19

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

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

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

4.2 用户自定义优化策略..................32

第五章 实验与分析.................39

5.1 实验环境与数据集概述......................39

5.2 PFP 算法和 YAFIM 算法 ................40

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

6.1 项目概述

项目将主要基于 SAP 技术，搭建 SAP 技术大数据应用平台，做大数据技术的前瞻性研究和开发应用。利用 SAP 技术，搭建从数据抽取、数据存储到数据应用的大数据技术平台，对其中的技术点进行前瞻性研究，同时该技术平台可以做为培训和学习的操作环境，具体包括：1）基于互联网大数据的采集利用甲方现有产品万网智能平台，进行互联网大数据的采集，对采集的数据进行处理和整合，做为后继数据存储和数据挖掘的数据集；2）HANA 和 Hadoop 的大数据多层存储架构搭建 HANA 和 Hadoop 的集成环境，实现大数据的分层存储，满足查询性能和存储空间的平衡需求；3）基于 SAP PA 的数据挖掘技术基于大数据的分层存储，对加工好的数据进行数据挖掘技术的研究，包括预测、分类、社交网络和推荐功能；4）基于 R 语言的数据挖掘技术集成 HANA 和 R 的环境，基于大数据以 R 语言进行数据挖掘的探究，实现SAP PA 同样的功能，并对数据挖掘结果进行比对分析。

...............

6.2 项目实施

在项目的实施阶段，首先，根据项目的具体要求，设计出一个大数据研发平台，实现 HANA 和 Hadoop 的集成；然后，根据设计要求，搭建大数据平台并集成 HANA/Hadoop 和 R 的环境；最后，基于 SAP PA 技术、R 语言和本文的研究算法——DFPS 算法，对淘宝的交易数据进行频繁项集挖掘，得到频繁地被客户一起购买的商品组合。根据要求，我们需要设计一个 HANA 和 Hadoop 集成的方案，实现大数据的分层存储，满足查询性能和存储空间的平衡需求。最终，我们设计的方案是：结构化数据存储在 Hive 上，而非结构化数据存储在 HDFS 上，利用 Map Reduce计算框架，可以实现海量数据简单的自定义分析逻辑；由于 Hadoop 所擅长的是批处理，对于迭代计算的问题则显得力不从心，所以我们利用 Apache Spark 来弥补 Hadoop 的不足，实现非实时作业的分布式迭代计算；对于实时性要求较高的作业，则将这些作业移动到 HANA 中完成。通过 SAP HANA 和 Hadoop 的连接器，将 Hadoop 上的数据抽取到 HANA 中，并保存在原始表里，通过计算层得到的结果则存储在结果表或分析视图中。

...............

总结

随着信息化时代的发展，人类逐步进入了大数据时代，在这些海量数据里，隐含着有价值或有潜力的信息。快速地从这些海量数据中提取有用的信息，以辅助上层决策，对国家和企业来说，都是很有意义的。频繁项集挖掘是数据挖掘研究领域中的一个重要课题，它是关联规则、因果关系、相关性分析、情节片段、序列项集、局部周期性等许多数据挖掘任务的基础。而目前已有的基于多处理器系统的并行频繁项集挖掘算法，以及基于 Hadoop 等分布式集群的分布式频繁项集挖掘算法，在面对海量数据的时候，表现得并不是很理想。因此，本文基于Apache Spark 计算引擎，设计了一个高效且具有良好可伸缩性的分布式频繁项集挖掘算法——DFPS 算法，并针对它在面向大规模 Spark 集群的时候可能出现的并行度不高、没有充分利用集群的计算能力，以及面对海量数据可能会出现栈溢出的问题，提出了两种优化 DFPS 算法的策略——用户自定义优化策略和集群自适应优化策略。

参考文献（略）