12.2 大数据环境下序列模式挖掘及应用

模式发现问题诞生于 1993 年[1] ，与分类、聚类和异常点检测并称为数据挖掘四大问题[2] 。它指的是从数据库找出频繁共现的“项”，被称为频繁模式。模式发现问题在数据挖掘领域地位重要，有大量关于模式发现的论文发表在重要数据挖掘、数据库会议。Google Scholar 记录的 Agrawal 等人[1]提出的经典模式发现算法 Apriori 的论文单篇 , 被引用次数近 1.8 万次，已成为数据挖掘领域引用最多的论文之一。

序列模式 (Sequential pattern) [3] （及其扩展情景模式 (Episode) [4] ）是引入了时间关系和约束的数据模式，它指的是从时序数据中挖掘频繁出现的子序列。这类模式因为蕴含了时间维度的补充信息，为推荐或者预测提供了潜在的帮助[2] 。序列模式挖掘曾成功应用于网络挖掘[5-6] 、设备故障检测 [7] 、软件 bug 检测[8] 、时空数据分析 [9] 、股票趋势预测 [10] 、化学与生物模式[11-12]和新闻分析[13-14]等。由于其广泛的应用，它逐渐成为数据挖掘领域中一个专门的研究主题。

由于序列模式挖掘是从频繁模式挖掘[1]演化而来，因此 Agrawal 和 Srikant [3] 最初提出该问题也是为了挖掘用户购物数据中行为模式来辅助决策。这个挖掘问题的问题描述如下：

设 I={I 1 , I 2 , …, I m } 是所有项的集合。给定一个序列集合 D，其中任意一条序列 S i 由一个元素列表组成，每一个元素则由 I 中的项组成，以及一个用户指定的最小支持度阈值 min_sup，序列模式挖掘是指从D中挖掘出现频率不低于min_sup的子序列，它们被称为频繁序列模式。

如表 1 所示的一个序列集合中，字母代表项，括号中的项视为无序，若设置最小支持度 min_sup为 2，子序列〈(bc)a〉是一个频繁序列模式，它共出现了 2 次，分别位于 s 1 和 s 2 中。
频繁情景模式挖掘，作为序列模式挖掘的扩展，则考虑的是从一条长事件序列中挖掘频繁的子序列，其问题描述如下：

设 E={E 1 , E 2 , …, E m } 是所有事件的集合。情景模式发现问题是指从一条单一的事件长序列 S 中挖掘出现频率不小于 min_sup 的子序列，min_sup 是用户指定的最小支持度阈值参数。其中，S 中的任意一个事件集合均由 E 的事件组成。挖掘出来的频繁子序列被称作频繁情景模式。

如图 1 所示的一条事件序列中，字母代表事件，数字代表事件发生的时间，若设置最小支持度 min_sup 为 3，子序列〈A, B〉是一个频繁情景模式，它共出现了 3 次，在序列中用虚线矩形框标注。
由于序列模式挖掘（及其扩展频繁情景模式挖掘）和频繁模式挖掘的相关性，其算法多数也是由频繁模式挖掘算法改进而来，这些算法大致可以分为基于 Apriori 的算法[3]和模式增长算法[15]两类。其中，基于 Apriori 思想的算法主要思想是通过生成候选集，以及扫描数据库进行逐层挖掘。这些算法通常还基于 Apriroi 算法的支持度的向下封闭性（downward closure）进行剪枝，即任何不频繁模式的超模式也不会频繁。但是在频繁情景挖掘问题中，这种性质不一定适用[16] 。这些算法虽然可以使用剪枝技术提升效率，但是它们实际的缺点是生成了大量的候选序列并需要重复扫描数据库对每一个候选序列计算支持度，这样的迭代过程使得挖掘效率低下。为了缓解这些问题，基于模式增长的算法开始涌现。它们大多采用了分治思想，以当前的频繁序列模式作为前缀将原始序列分割成若干个投影数据库（projected databases），并在这些投影区域内进行挖掘。相较于前一大类算法，基于模式增长的方法的好处是不需要生成序列的候选集合，并且缩小了数据库扫描的范围，在性能上具有一定的优势。

近年来，为了能够处理持续快速增长的大数据，序列模式挖掘（及其扩展频繁情景模式挖掘）在并行、增量和近似算法上也取得了显著进步。本文将从算法角度综述主要的序列模式挖掘（以及频繁情景模式挖掘）算法，并且回顾适用于大数据的序列模式挖掘（频繁情景模式挖掘）代表性算法。