12.3 基于 Apriori 的序列模式挖掘算法
GSP(Generalized Sequential Patterns) [17] 是一种经典的序列模式挖掘算法,它直接从频繁模式挖掘的 Apriori 算法扩展而来。GSP 采用了水平的数据格式,通过生成候选序列及扫描数据库的方法逐层挖掘频繁序列模式。这里的水平数据格式指的是依然以序列作为主要的观察对象。此外,GSP 还采用了序列模式支持度的向下封闭性用于剪枝。与Apriori 不同的是,GSP 在生成候选序列的时候考虑了有序和无序两种情况,比频繁模式挖掘中的候选项集生成过程更为复杂。采用了类似思想的算法还有 AprioriAll [3] 和 PSP [18] 等。
SPADE (Sequential PAttern Discovery usingEquivalence classes) [19] 则是一种采用了垂直数据格式的序列模式挖掘算法。它与 GSP 等算法的最大不同是将数据库转化成了垂直格式,即以项作为核心观察对象,将包含项的序列 id 作为数据,从而将原始数据库转换为一种垂直数据集进行挖掘。在SPADE 算法中,长度为 2 的序列可以通过合并两个长度为 1 的频繁项的垂直序列 id 列表得到。以此类推,SPADE 最终可以逐层地挖掘出所有频繁的子序列。与 GSP 算法相比,SPADE 一定程度上缩小的搜索空间,具有一定的性能优势。与 SPADE 类似的算法还有 SPAM [20] 、LAPIN-SPAM [21] 等。
类似地,在频繁情景模式挖掘领域,Mannila等人提出的 WINEPI(WINdow EPIsode)算法是最早的一种基于 Apriori 思想的算法。在 WINEPI 算法中,一种基于时间窗口的情景模式频率的定义被提出,并且采用了类似 GSP 算法的流程用于频繁情景模式挖掘。但与 GSP 不同的是,WINEPI 在进行候选序列频率统计时,只在划分出的时间窗口中进行。后来,Mannila 等人又提出了 MINEPI 算法,用于挖掘频繁情景模式的最小发生(Minimaloccurrence)。在 MINEPI 算法中,除了情景模式频率的定义采用了一种新定义的最小发生外,其余流程均与 WINEPI 相同。
由于频繁情景模式挖掘存在多种频率定义,Achar 等人[16]提出了一种统一的基于 Apriori 的频繁情景模式挖掘算法,将各种常见的频率定义均可以转化为该算法的特例。