PrefixSpan算法

PrefixSpan算法和FreeSpan算法一样，也是采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。

但PrefixSpan算法克服FreeSpan算法中序列模式在任何位置增长问题，它只基于频繁前缀投影，确保序列向后增长，同时也缩减投影数据库的大小。

定义6.8  设序列中每个事件中的项按字典顺序排列。给定序列α=<e1e2…en>（其中ei对应序列数据库S中的一个频繁事件），β=<e1'e2'…em'>（m≤n），如果ei'=ei（i≤m-1），em'⊆em，并且(em-em')中的所有频繁项按字母顺序排在em'之后，则称β是α的前缀。

例如，<a>、<aa>、<a(ab)>和<a(abc)>都是序列s=<a(abc)(ac)d(cf)>的前缀，而<ab>和<a(bc)>却不是s的前缀。

定义6.9   给定序列α=<e1e2…en>（其中ei对应序列数据库S中的一个频繁事件），β=<e1e2…em-1em'>（m≤n）是α的前缀。

序列γ=<em''em+1…en>称为α的相对于β的后缀，记为γ=α/β。这里e''=(em-em')，如果e''非空，则该后缀记为<(_em''中的项)em+1…en>。也可以记为α=β·γ。

注意，如果β不是α的子序列，则α的相对于β的后缀为空。

例如，若序列s=<a(abc)(ac)d(cf)>，则<(abc)(ac)d(cf)>是s的相对于前缀<a>的后缀。<(_bc)(ac)d(cf)>是s的相对于前缀<aa>的后缀，其中(_b)表示该前缀的最后一个事件是a，a与b一起形成一个事件。<(_c)(ac)d(cf)>是s的相对于前缀<a(ab)>的后缀。如图6.14所示。

定义6.10  设α是序列数据库S中的一个序列模式。α投影数据库记为S|α，它是S中所有以α为前缀的序列相对于α的后缀的集合。

投影数据库中的支持度：设α为序列数据库S中的一个序列，序列β以α为前缀，则β在α的投影数据库S|α中的支持度为S|α中满足条件β⊆α·γ的序列γ的个数。

定理6.11   基于前缀和后缀的概念，挖掘序列模式的问题可以分解成一系列子问题：

（1）设{<x1>，<x2>，…，<xn>}是序列数据库S中长度为1序列模式的集合。S中序列模式全集可以划分成n个互不相交的子集。第i（1≤i≤n）个子集是以<xi>为前缀的序列模式集合。

（2）设α是一个长度为l的序列模式，{β1，β2，…，βm}是所有以α为前缀的长度为(l+1)的序列模式的集合。除α本身外，以α为前缀的序列模式集合可划分为m个不相交的子集，第j（1≤j≤m）个子集是以<βj>为前缀的序列模式集合。

PrefixSpan算法的其本过程是：

扫描序列数据库S，生成所有长度为1的序列模式；根据长度为1的序列模式，生成相应的投影数据库S1、S2、…、Sn，在各投影数据库上重复上述步骤，直到在该投影数据库上不能产生序列模式为止。