第4章　分布式日志的最大频繁序列模式挖掘算法

4.1　引言

随着云计算、物联网、大数据等技术的快速发展，分布式服务器系统已成为各种应用业务的主流系统，各类用户访问及服务提供使对系统应用的可靠性要求越来越高，对用户日志或系统服务日志信息的分析越来越重要[158]。系统中的日志信息呈分布式状态，传统方法是把分布式环境下的日志信息集中到一台计算机上进行分析与处理，通过挖掘频繁序列模式，以获得系统运维所需要的各种状态信息，但集中式分析与挖掘方式有巨大的通信开销。同时，从用户隐私保护和数据的安全性出发，不应该对大规模分布式环境中的各类日志数据进行异地保存，也不应该占用网络带宽将其传输到同一地点以进行集中式处理。从以往的文献来看，有效地保证系统的可靠性与安全性，对日志序列分析与挖掘非常重要。如何有效地从大规模分布式日志数据中挖掘有用的模式并应用于日志序列分析，具有非常重要的意义。

学术界与工业界经常采用序列模式挖掘（Sequential Pattern Mining，SPM）来发现集群系统日志数据中隐藏的规律。SPM是指从海量事件序列中挖掘出重复频率较高的序列模式[147]，其关键是将时间属性或其他具有顺序的属性融入模型中，是数据挖掘的一个热点研究领域[148][149]。序列模式挖掘主要应用于日志序列分析[150][151]、购物篮行为分析[152]、DNA[153]和蛋白质序列分析[154]等。日志序列模式分析是从应用程序中挖掘用户的访问行为，以便预测用户后续可能的访问模式[155]，可以应用于异常检测[151]，如从日志数据中挖掘用户行为模式，再将用户行为模式与正常模式库进行比较来检测异常[156]。

现有方法在应用于分析大规模分布式日志数据集时，已经取得了一定的进展，但依然存在如下三个方面的问题。

问题1：从巨量的分布式日志数据中提取序列模式，存在的主要问题是效率非常低，缺少有效的并行提取序列模式的方法。

问题2：现有的序列模式挖掘算法一般在发现频繁项集阶段需要维护较大的候选序列，当支持度阈值较小时，运行时间代价较大，运行效率较低。

问题3：现有的序列模式挖掘算法研究大多研究的是挖掘频繁序列模式和闭频繁序列模式的算法，但这些算法在数据量大时会挖掘出大量的频繁序列。过多的频繁序列会使用户难以理解用户或系统的行为。

针对上述问题，本章提出一种新颖的分布式日志数据中挖掘最大频繁序列的新算法SparkMFPs，该算法能够在给定最小的支持度阈值时挖掘出最大频繁序列。

本章的贡献主要有以下三点。

（1）在算法框架选择上，本章的主要亮点在于采用分布式解决方案，通过构建高效率的分布式计算框架，实现对大规模事件序列集的最大频繁序列模式挖掘。现有算法一般都采用单机模式，很难应用于大规模日志数据集的分析。利用分布式框架的特点，对各节点迭代进行挖掘局部最大频繁序列模式，并把中间运算结果输出并保存在内存中，以解决大规模数据集的挖掘问题，有利于算法中数据规模的扩展。

（2）在提取局部最大频繁序列阶段，本章的主要亮点在于利用频繁序列删除序列数据集中的非频繁项，向前扩展的一致性检测可以很好地避免局部最大冗余的产生，减小了需要维护候选序列的规模，提高算法运行效率。而一般序列模式挖掘需要维护大量的候选序列，算法运行效率较低。

（3）在提取全局最大频繁序列阶段，本章的主要亮点在于打破了先排序、再检测、后提出全局最大频繁序列模式的传统做法，而是先对局部最大频繁序列按长度排序后保存，对相邻长度进行超集检测，然后提取出的最大频繁序列就可以高效率地挖掘出高质量的频繁序列。

我们进行了大量的有关对比实验，采用了NASA数据集、World Cup数据集、合成数据集这三类数据集作为本章的实验数据集，采用了两种对比形态：（1）本章提出的算法与经典PrefixSpan算法、SDD_UDDAG算法运行效率的对比，以及在集群环境下与SparkMLib中分布式PrefixSpan算法的对比；（2）频繁序列模式与最大序列模式挖掘算法的挖掘质量的对比。实验证明了SparkMFPs算法能高效地挖掘最大频繁序列，而且对数据规模有很好的扩展。

本章的其余部分组织如下：4.2节介绍序列模式挖掘相关工作，4.3节详细介绍本章提出算法的动机与背景，4.4节详细介绍本章提出的算法，4.5节设计相关的实验，并对实验结果进行分析，4.6节对本章进行总结。