4.3　动机与背景

4.3.1　使用分布式计算框架的动机与背景

现有的序列模式挖掘算法在解决大规模日志数据集时，往往存在大量冗余频繁事件序列，使最大频繁序列模式的挖掘效率较低，用户对挖掘结果不易理解。因此，现有的序列模式挖掘算法在直接应用到大规模分布式日志数据集进行分析挖掘时，是非常困难的。

传统的序列模式挖掘算法很难处理大规模日志数据集，算法挖掘效率不高，扩展性较差。因此，使用分布式计算框架是一种解决方案[173][174][175][176]，它更适合处理大规模数据集，扩展性较好。近年来，使用分布式计算框架MapReduce是一种趋势，它利用HDFS（分布式文件系统）来存储分布式数据，同时利用机器集群来处理大量数据计算。文献[174]、文献[175]和文献[176]利用分布式计算框架MapReduce重新设计了现有的序列模式挖掘算法。Wang X等人在文献[177]中提出了PTDS算法，它将事件序列数据划分为较小的数据区域，将分布式计算框架MapReduce结合PrefixSpan算法，很好地应用于大规模数据集。但MapReduce在处理数据时会把中间结果保存到HDFS，挖掘效率不高。GITAM University的Sarla P等人在文献[178]中提出Spark的弹性分布式数据集RDD有别于MapReduce，虽然将分布式计算进行了封装，但是其计算本质仍然是一些映射（Map）和规约（Reduce）函数。

Spark是新一代基于内存计算的处理平台[170]，其计算效率高，具有非常好的并行计算性能，因此，本章利用Spark分布式计算框架，实现分布式日志最大频繁序列模式挖掘，可以高效率地挖掘出高质量的日志序列。

4.3.2　使用PrefixSpan算法挖掘序列模式的动机与背景

序列模式挖掘算法有一个基本的假设——频繁模式的子模式也是频繁的，依据这个理论可以挖掘出所有频繁序列。但算法需要多次扫描序列数据集，这会产生大量的候选集。为克服这些缺点，一些研究者提出基于投影数据库的FreeSpan算法和PrefixSpan算法，采用分治策略，利用投影数据库减小搜索空间，可以较好地进行序列模式的挖掘分析，已有的研究表明，PrefixSpan算法的收缩速度比FreeSpan算法快。

PrefixSpan算法的基本思想是使用频繁前缀划分搜索空间，在划分搜索空间时不考虑所有可能出现的频繁子序列，只基于频繁前缀序列构造投影数据库，频繁子序列都可以被递归地挖掘出来。

本章在结合Spark分布式计算框架解决大规模日志数据集问题时，由于Spark是基于内存计算的，因此当数据量大时，内存中不能构建一个全局的数据集，而PrefixSpan算法通过分治策略可减小数据集的规模，可以很好地结合应用于大规模日志数据集的研究与分析[25]。算法应用了序列、前缀、后缀、频繁序列等概念，并给出了如下相关定义。

定义1（事件、事件序列、子序列）：给定事件类型，其中的事件是一个关于时间的二元组合 (e,t) ，其中e∈ε，t表示该事件的发生时间。把发生时间按照先后顺序排列并定义为ε上的一个发生的事件序列，即（，）。如果两个序列的关系是或是由删除某些事件序列后得到的剩余序列，则称是的子序列。

定义2（前缀、后缀、投影，投影数据库）：给定序列和，当时，若，则β是α的前缀；若序列，，则序列γ为序列α关于前缀β的后缀。若j是β在α中首次出现的结束位置，则删除序列α中第1～j个事件序列后剩余的序列称为β在α上的投影，事件数据库中所有的这种投影称为投影数据库。

定义3（最大频繁序列）：数据库D频繁序列集合中的一个序列s，若不存在任何序列是s的超集，则称s为一个最大频繁序列。

定义4（向前扩展）：若序列为k序列，e为1序列，则序列称为序列α向前扩展。

4.3.3　改进PrefixSpan算法提取局部最大频繁序列的动机与背景

现有的PrefixSpan序列模式挖掘算法一般在发现频繁项集阶段需要维护较大的候选序列，当数据集较小和支持度阈值较小时，运行时间代价较大，运行效率低。PrefixSpan算法[165]是一种高效率的序列模式挖掘算法，但在利用该算法挖掘最大频繁序列时，在发现频繁项集阶段同样需要维护较大的候选序列，挖掘效率较低，因此有必要对PrefixSpan算法进行改造。利用非频繁序列不会出现在局部最大频繁序列和全局最大频繁序列中这一重要特征，可以构建一个重要的策略：在生成频繁1序列时，可利用频繁1序列删除数据库中的非频繁序列，据此可以减小生成投影数据库的规模，缩短扫描投影数据集的时间，而且在并行递归挖掘频繁序列时，算法会递归到最长的搜索路径，过滤掉部分候选频繁序列，生成局部最大频繁序列，减小了维护候选序列的规模。

4.3.4　改进PrefixSpan算法提取全局最大频繁序列的动机与背景

现有的序列模式挖掘算法在应用于大规模日志数据集时，由于在提取目标序列阶段会提取出大量冗余的频繁序列，而过多的频繁序列会使用户难以理解用户或系统的行为并耗费大量时间。因此，研究者通过改进提取目标序列的方法，可以获得较好的效果。当前人们提取目标序列，通常是先对目标序列进行排序，再进行检测，以提取出符合需求的序列模式。但这种方式需要多次遍历，算法的时间效率低。

因此，需进一步快速提取全局最大频繁序列模式，先对局部最大频繁序列按长度排序后保存，对相邻长度频繁序列进行超集检测，然后从中提取出最大频繁序列，可以高效率地挖掘出高质量的频繁序列。