基于SPARK的海量数据频繁模式挖掘算法研究

摘要

频繁模式挖掘的目的是从数据中找出出现频率较高的内容，它是数据挖掘领域众多研究方向中最重要的其中一个。按照数据集的不同，频繁模式分为频繁项集和频繁子序列。由于挖掘频繁模式是一个很消耗计算资源的过程，随着数据量的增加，人们必须借助于分布式的计算框架来保证处理的效率。本文第一部分专注于挖掘事务数据集上的频繁项集，研究基于分布式计算框架Spark的频繁项集挖掘算法。本文首先设计实现了与经典频繁项集挖掘算法Apriori和FP-Growth相对应的基于Spark的分布式版本，然后又提出了一个基于Spark的具有FP-Growth和Apriori两个算法特点的两阶段频繁项集挖掘算法。通过实验我们发现了每个算法的优缺点，并找到不同算法的适用范围。这些算法能够充分应用集群的计算资源，快速解决大规模数据集上挖掘频繁项集的需求。除此之外，这一部分还介绍了如何使用挖掘频繁项集的思路在Spark上挖掘序列数据集上的频繁模式。
　　除了研究在Spark上挖掘频繁模式的算法，为了能够在数值型的时间序列数据集上挖掘频繁模式，本文第二部分的主要内容是时间序列的压缩。时间序列的压缩不仅能够有效减少数据量，还能够减少序列里的噪音。噪音的减少能够凸显出时间序列的趋势，从而有利于挖掘出有意义的频繁模式。本文从感知重要点的概念出发，通过对以往工作的扩展，设计并实现了两种基于感知重要点的时间序列压缩算法,基于全局感知重要点的压缩算法和基于局部感知重要点的压缩算法。这两种算法适用于不同类型的时间序列，并且通过实验对比了它们的运行效率和压缩的失真度。可视化是运用时间序列时一个很重要的需求，基于感知重要点的压缩算法能够很好的保留序列的趋势，具有非常好的可视化效果。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.2 相关理论的发展概况

1.3 本文的主要研究内容

第2章 基于SPARK的频繁项集挖掘算法

2.1 引言

2.2 Spark上的并行Apriori挖掘算法

2.3 Spark上的并行FP-Growth挖掘算法

2.4 Spark上的两段式挖掘算法

2.5 三种算法的比较

2.6 基于Spark的频繁子序列挖掘

2.7 本章小结

第3章 基于感知重要点的时间序列压缩算法

3.1 引言

3.2 时间序列上数据点的感知重要性

3.3 基于感知重要点压缩时间序列

3.4 两种算法的对比

3.5 基于Spark平台的压缩

3.6 在压缩的时间序列上寻找频繁模式

3.7 本章小结

第4章 实验结果与分析

4.1 引言

4.2 基于Spark的频繁项集挖掘算法实验

4.3 基于感知重要点的时间序列压缩算法实验

4.4 本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致谢