4.4 分布式日志最大频繁序列模式挖掘算法描述
本章针对大规模分布式日志数据集下的最大频繁序列模式挖掘问题，结合分布式计算框架Spark，改进PrefixSpan算法机制，提出了分布式日志最大频繁序列模式挖掘算法。
4.4.1 基于Spark的分布式计算框架
在对日志数据集进行日志预处理、日志会话生成以后，利用基于Spark的分布式计算框架在PrefixSpan算法基本思想的基础上，提出了日志序列模式分析的二阶段最大频繁序列挖掘算法。该算法的主要框架如图4.1所示。
图4.1 日志序列模式分析的二阶段最大频繁序列挖掘算法的主要框架
一般来说，基于迭代的分布式数据集RDD的设计过程可分为两个阶段。
（1）在各节点并行提取局部最大频繁序列阶段，首先读入事务数据集（分布式数据集RDD），RDD可以被分为n个数据块，然后数据块被分发到m个节点上进行迭代处理，其中将频繁前缀的数量作为2次迭代的增量，在支持度的计算上相互不影响，而判断当前构建的候选序列是否为局部最大频繁模式，其结果将会影响子节点。
（2）在提取全局最大频繁序列阶段，从各节点收集挖掘出的局部最大频繁序列，按照不同序列长度缓存在内存中。此时，必须对各相邻节点进行超集检测，删除非子集频繁序列，才能获得全局最大频繁序列的集成结果。
4.4.2 算法总体描述
本章算法分为以下两个步骤。（1）提取局部最大频繁序列：利用前缀投影来划分搜索空间，递归地提取出局部最大频繁序列，其中，利用频繁1序列可删除日志数据集中的非频繁项，减小了扫描数据库的规模，同时利用频繁序列模式与最大频繁序列模式之间存在的特殊性质来减少候选序列。（2）提取全局最大频繁序列：首先把局部最大频繁序列按长度进行保存，然后对相邻长度进行超集检测，删除冗余序列，提取出全局最大频繁序列。根据以上描述，可在分布式计算框架Spark上实现算法，同时使用Master/Worker工作模式。SparkMFPs算法的伪代码如算法4所示。
算法4 SparkMFPs算法的伪代码
假设1频繁项集的个数为q，L是最大频繁序列长度，其主要的时间复杂度来自递归迭代过程。计算得到的c频繁项集是c−1频繁项集的超集，其可作为最大频繁模式。设c频繁序列的个数为N，算法的时间复杂度为O(Nc2)，前面提取局部最大频繁序列的时间复杂度为O(qL)，所以总的时间复杂度为O(qL)+ O(Nc2)。本算法提前挖掘出局部最大频繁序列，减少了冗余，所以在支持度较低和大规模数据集应用中，c频繁序列的个数N远小于现有算法挖掘出的频繁序列个数，运行效率较高。
4.4.3 算法第一阶段：各节点提取局部最大频繁序列
首先从HDFS（分布式文件系统）中读入原始日志数据集，过滤出频繁1序列。然后，利用过滤出的频繁1序列对原始日志数据集进行处理，删除非频繁序列，其中利用Spark内存缓存机制缓存原始日志数据集。假定支持度阈值为0.5，则频繁1序列为<a,b,e>。删除非频繁序列后的序列如表4.2所示。
表4.2 删除非频繁序列后的序列
在递归构造频繁序列时，保存递归到最长搜索路径的序列模式，过滤部分候选频繁序列，提取出局部最大频繁序列<b>、<e>，投影数据库和序列模式如表4.3所示。
表4.3 投影数据库和序列模式
4.4.4 算法第二阶段：各节点集成，提取全局最大频繁序列
以下算法描述了从冗余的局部最大频繁序列中提取出最大频繁序列。首先对局部最大频繁序列按照长度进行保存，然后对相邻序列长度的序列模式进行超集检测，判断是否存在超集关系，若存在，则删除子集频繁序列。MaxFi算法的伪代码如算法5所示。
算法5 MaxFi算法的伪代码
对于算法5的挖掘过程，其时间复杂度主要来自超集的检测过程。对于该算法的时间复杂度来说，假设长度为c的频繁序列为N，频繁序列的最大长度为L，那么算法的时间复杂度为O(LN2)。