4.2　序列模式挖掘相关工作

高效率地进行日志序列分析的过程主要包括三个步骤：日志预处理、日志序列模式挖掘和日志分析。其中，日志序列模式挖掘算法的改进是近期研究的重点内容[157][158]。目前，学术界已提出大量的序列模式挖掘算法，经过归纳总结，大体可分为三类：基于Apriori特性的算法[160][161]、基于垂直格的算法[162][163]、基于投影数据库的算法[164][165]，基本序列模式研究的特点如表4.1所示。早期的序列模式挖掘算法大都是基于Apriori[160]的特性发展而来的，它们可以有效地挖掘序列模式，但算法需要多次扫描数据库，同时会产生大量的候选序列；第二类基于垂直格的算法（如SPADE[166][163]等）主要是对第一类算法进行了改进，减少了扫描数据库的次数，但该类算法将数据库由水平格式转换为垂直格式，需要额外的时间开销，而且算法同样需要维护较大的候选序列；第三类基于投影数据库的算法[164][165]将频繁序列投影到对应的投影数据库上，递归发现频繁序列，这种分治策略在缩小数据集规模的同时减少了候选序列的产生。

表4.1　基本序列模式研究的特点

以上三种序列模式挖掘算法在对大规模分布式日志进行分析时，共同的缺点是会产生大量的冗余挖掘结果，而且效率相对较低。为此，学者们提出了一些特殊的序列模式挖掘算法，如闭频繁序列模式挖掘算法[166][167]、最大频繁序列模式挖掘算法[156][157][168][169][170]。

闭频繁序列模式挖掘算法是一种减少频繁序列数量的算法。在进行闭频繁序列模式挖掘时，挖掘的闭频繁序列不包含于相同频率的父集中[166][167]。此类算法在挖掘分析日志序列时，往往不能很好地应用于大规模分布式环境下的日志序列，而且会挖掘出大量冗余序列模式。

最大频繁序列模式挖掘算法是一种基于频繁序列压缩形式的挖掘算法[156][167][168][169]。其中，最大频繁序列关注挖掘特殊的频繁序列，也隐含了一些其他频繁序列的信息，它比闭频繁序列模式挖掘算法的压缩程度更大。Fournier-Viger P等人在文献[170]中提出了一种高效率的最大频繁序列模式挖掘算法，但该算法不能很好地应用于大规模分布式日志数据集的情况。为解决分布式日志数据集序列模式挖掘的问题，Zou X等人在文献[171]中提出了快速分布式序列模式挖掘（Fast Distributed Mining of Sequential Pattern，FDMSP）算法来挖掘全局序列模式，但算法需要分配选举站点且有相当大的时间消耗。Spark技术体系中的SparkMLib包也提供了FP-Growth和PrefixSpan的分布式实现算法，但FP-Growth序列模式挖掘不能应用于日志序列，而PrefixSpan算法会挖掘出大量冗余的序列，用户难以理解挖掘结果。

针对以上问题，本章提出了一种分布式日志最大频繁序列模式挖掘算法，可以有效地克服以上缺点。