基于Spark的频繁序列情节挖掘算法研究

摘要

在现今的信息化时代，如何对各种设备采集到的各类信息进行有效分析和处理已成为众多研究者关注的焦点。频繁情节挖掘技术从诞生起，便在处理这些信息时发挥了重要的作用。在工程应用中，只有那些发生在短时间段内的情节才对实际生产有较好的指导作用，但现有的大部分研究成果在挖掘频繁序列情节时并未考虑情节的时间跨度这一因素，故由其挖掘到的频繁情节存在数量庞大、质量低下等不足，以致难以满足实际需求。鉴于此，本文在引入时间约束的基础上，通过利用情节发生的第一个事件与最后一个事件存在的最大时间间隔特性，提出了相应的序列情节频繁度计数算法和频繁序列情节挖掘算法，以提升序列情节挖掘的质量和算法的执行效率。另外，由于Spark平台是基于内存计算的，故本文将其引入到新提出的算法中以加快运行速度。 本文主要工作如下： 1.提出了带时间约束的序列情节频繁度计数算法。针对许多研究成果在设计算法时未考虑时间约束的问题，本文专门为带时间约束的序列情节eτ设计了一种基于双重字典内嵌双端队列的数据结构OccDict，以存储和统计目标序列情节中事件发生的时间戳，在对事件序列S进行一次扫描时，通过维护该数据结构的状态、验证情节的候选最小发生及对无效状态的清理等过程来求出eτ在S中的频繁度。通过在移动网络告警数据集和人工数据集上进行的多组实验分析了各因素对本文算法性能的影响，并验证了该算法与其他算法相比具有高效性、能满足实时监测的要求。 2.针对文中提出的带时间约束的序列情节频繁度计数算法具有串行化的特点：一个事件该如何处理依赖于前一个事件的处理结果，创新性地通过将事件序列S分段的形式，完成了对该问题的基于Spark的并行化算法设计，并通过实验验证了其性能。 3.以文中提出的序列情节频繁度计数算法为基础，通过采用迭代方式不断将一项频繁情节中的任一事件插入到k项频繁情节的任意位置来生成的k1项候选情节，进一步提出了带时间约束的频繁序列情节挖掘算法。使用移动网络告警数据集和人工数据集上的测试结果表明，本文算法可有效提高频繁序列情节的质量和算法效率。 4.针对带时间约束的频繁序列情节挖掘算法在处理数量庞大的序列情节时效率不佳的问题，本文利用Spark的一个执行者来完成一个序列情节的发生计数，对该算法进行了基于Spark的并行化设计，实验结果表明了该方案的有效性。

目录

第一个书签之前