一种基于Spark平台的带有时间约束的频繁序列挖掘算法

发布时间：2024-06-02 03:31

　　序列模式挖掘问题,由于其在实践中广泛的应用,已引起学术界的持续关注。虽然目前已经有一些序列模式挖掘算法,但因为它们需要多次扫描整个数据库,所以效率相对较低,并且大多数算法都没有考虑到时间因素对序列模式挖掘的影响,它们并不能对有时间限制要求的序列模式进行出现频率的统计和挖掘。在对各个序列模式的出现频率进行统计的算法中,ONCE算法可以在只扫描一次数据库的情况下,统计出带有时间约束的序列模式在序列流中出现的频率。但该算法只能应用于处理序列模式之间无交叉的情况,当序列模式之间存在某种交叉时,使用ONCE算法统计出的结果就是不准确的。在本文中,我们对ONCE算法进行了修改,可以在序列模式之间存在交叉的情况下,也得到准确无误的结果。随着因特网,电信,工业系统的迅速发展,每天都会产生海量的信号序列和流式数据。一方面,由于海量序列中信号的数量十分巨大,分析这些序列是一件非常耗时的事情,所以要求处理的算法必须是高效的,可以并行化计算的。另一方面,由于流式数据是无限的,非匀速产生的,因此对于流式数据的计算方法,必须是可以动态更新和存储的,也同样要是高效的,当前的多数算法都无法达到要求。为了解决对海量数据...

【文章页数】：69 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
符号对照表
缩略语对照表
第一章 绪论
    1.1 研究背景与意义
    1.2 研究现状和发展方向
        1.2.1 研究现状
        1.2.2 发展方向
    1.3 本文主要贡献
    1.4 论文组织结构
第二章 序列挖掘算法和相关概念
    2.1 序列的基本概念
    2.2 本文相关算法
        2.2.1 Apriori算法
        2.2.2 FP-growth算法及FP-tree结构
        2.2.3 ONCE算法
    2.3 Spark的相关介绍
        2.3.1 弹性数据集RDD
        2.3.2 Spark Streaming组件
第三章 有交叉序列模式的统计方法
    3.1 无交叉序列模式统计方法ONCE
        3.1.1 建立OccMap
        3.1.2 更新OccMap
        3.1.3 寻找选中事件
        3.1.4 判断选中事件组成的序列模式是否满足时间限制
        3.1.5 初始化OccMap
    3.2 有交叉序列模式统计方法ONCE+
    3.3 ONCE和 ONCE+对比实验
    3.4 本章小结
第四章 基于Spark的海量数据序列模式挖掘算法 . . . . .
    4.1 基于Spark的海量数据序列模式频率计算
        4.1.1 边界处理
        4.1.2 并行频率挖掘模型
        4.1.3 SparkONCE的完整算法
    4.2 SparkONCE的实验结果
        4.2.1 |S|的影响
        4.2.2 分区数量的影响
    4.3 SparkONCE算法的适用性
        4.3.1 SparkONCE结合FP-growth进行序列挖掘
        4.3.2 SparkONCE算法与Apriori算结合进行序列挖掘
    4.4 本章小结
第五章 基于Spark Streaming的流式数据序列模式挖掘算法. .
    5.1 基于Spark Streaming的流式数据序列模式频率计算
    5.2 实验结果
    5.3 使用StreamingONCE对流式数据进行频繁序列挖掘
        5.3.1 时间倾斜窗口
        5.3.2 结合时间倾斜窗口的FP-tree结构
        5.3.3 FP-tree的剪枝
    5.4 SparkONCE和 StreamingONCE的正确性
    5.5 本章小结
第六章 总结与展望
    6.1 总结
    6.2 进一步工作
参考文献
致谢
作者简介



本文编号：3986788