《中国人工智能学会通讯》——12.4 基于模式增长的序列模式挖掘算法

FreeSpan [15] 和 PrefixSpan [22] 都是由 Han 和 Pei等人提出的基于模式增长的序列模式挖掘算法。它们都是基于频繁模式挖掘中的 FP-growth [23] 思想而被提出的。其中，FreeSpan 基于频繁项将数据库划分成若干投影子数据库，然后在各个子数据库中进行序列模式的挖掘。PrefixSpan 则优化了构建投影数据库的过程，它首先检查前缀序列的位置并且只对后缀子序列进行投影，从而进一步缩小了搜索空间。当挖掘出长度的 l 的频繁序列模式后，FreeSpan 和 PrefixSpan 都会以该模式作为前缀，并根据各自的投影数据库构建方法构建新的投影数据库，然后挖掘长度为 l+1 的频繁序列模式。与 GSP等基于 Apriori 的算法相比，FreeSpan 和 PrefixSpan的优势是仅通过短的频繁序列模式扩展出更长的子序列，而不会产生投影数据库中不存在的候选序列集合。

在频繁情景模式挖掘领域，基于模式增长的思想特别适合挖掘以最小发生作为频率定义的频繁情景模式，因此有相关算法被提出。MINEPI+ [24]是一种改进的 MINEPI 算法，它采用了与 SPADE算法相近的垂直数据格式，以事件作为观察核心将事件序列进行切分和投影，并通过事件发生时间列表的合并，发现情景模式的最小发生。这里，MINEPI+ 将短的频繁情景模式作为前缀挖掘更长的频繁情景模式，因此是一种典型的基于模式增长的算法。EPT [25] 算法则提出了一种情景模式前缀树的结构，并通过一种前缀扩展的方式挖掘基于最小发生的情景模式。Wu 等人提出的 UP-Span [26]算法和 Achar 等人提出的 DFS 算法[27]虽然都是面向的其他频繁情景模式挖掘任务，但通过模式增长的方式找到情景模式的最小发生都是其一项重要步骤。