基于Spark的FP-Growth算法的研究

发布时间：2023-02-19 17:05

　　随着信息时代的数据量高速增长,人们越来越热衷于从海量数据中发现有价值的信息。数据挖掘技术越来越成熟,数据挖掘理论与算法也日臻完善。随着数据量爆炸式的增长,算法的运行对计算机内存的要求越来越高,FP-Growth算法本身也存在着算法逻辑复杂和需要多次迭代等缺点,难以完成对海量数据的挖掘任务,这就需要开发全新的算法或者对传统的算法进行改进。本文基于Spark并行计算框架,从存储和分组两个方面提出了FP-Growth算法的改进策略,有效地提高了算法的性能。主要工作如下:第一,对存储策略的改进。Spark是基于内存的并行计算框架,将产生的中间结果存储于RDD中。面对海量数据,RDD不能满足存储所有的中间结果时,会释放暂时不需要的RDD,需要时再进行重新计算。本文结合Spark自身的特点,提出一种对中间计算结果缓存的方法。针对产生条件模式基时需要对分区后的事务集重复计算的问题,将分区后的事务集进行缓存;针对产生关联规则时需要对频繁项集重复计算的问题,将每一棵FP-Tree进行挖掘时产生的频繁项集进行缓存。通过对上述中间结果的缓存,有效地避免了重复计算带来的额外开销。第二,对分组方式的改进。在并行...

【文章页数】：57 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第1章 绪论
    1.1 选题背景与研究意义
    1.2 国内外研究现状
        1.2.1 国外研究现状
        1.2.2 国内研究现状
    1.3 本文的研究内容
    1.4 本文的组织结构
    1.5 本章小结
第2章 基本理论和相关技术介绍
    2.1 关联规则的基本概念
        2.1.1 关联规则的定义
        2.1.2 关联规则的挖掘步骤
        2.1.3 关联规则的挖掘分类
    2.2 关联规则的经典算法
        2.2.1 Apriori算法
        2.2.2 FP-Growth算法
    2.3 Hadoop的相关技术
        2.3.1 HDFS分布式文件管理系统
        2.3.2 MapReduce并行计算框架
    2.4 Spark的相关技术
        2.4.1 Spark的特点
        2.4.2 Spark生态系统
        2.4.3 Spark架构
    2.5 本章小结
第3章 基于Spark的 FP-Growth算法的优化
    3.1 引言
    3.2 基于MapReduce的 FP-Growth算法
    3.3 基于MapReduce的 FP-Growth算法缺陷
    3.4 基于Spark的 FP-Growth算法
        3.4.1 基于Spark的 FP-Growth算法流程
        3.4.2 基于Spark的 FP-Growth算法步骤
    3.5 基于Spark的 FP-Growth算法优化
        3.5.1 存储的优化
        3.5.2 存储方式改进后算法的实现
        3.5.3 分组策略的优化
        3.5.4 分组策略改进后算法的实现
    3.6 基于Spark改进后的FP-Growth算法
    3.7 本章小结
第4章 实验过程及结果分析
    4.1 实验环境和数据集
        4.1.1 实验环境
        4.1.2 实验数据集
    4.2 并行化评价指标
    4.3 实验结果与分析
        4.3.1 节点数量的影响
        4.3.2 支持度的影响
        4.3.3 数据规模的影响
        4.3.4 加速比
    4.4 本章小结
第5章 总结与展望
    5.1 本文总结
    5.2 展望未来
致谢
参考文献



本文编号：3746616