在序列模式挖掘中，FreeSpan和PrefixSpan是两个常用的算法。其中，PrefixSpan是从FreeSpan中推导演化而来的。这两个算法都比传统的Apriori-like的序列模式挖掘算法（GSP）都有效。而PrefixSpan又比FreeSpan又更有效。这是因为PrefixSpan的收缩速度比FreeSpan还要更快些。 下面将分别介绍这两种算法 1. FreeSpan算法 FreeSpan算法的核心思想是分治算法。下面通过一个例子来描述： 假设有一个序列数据库有如下四条序列记录 <(ad) c (bc) (ae)> <(ef) (ab) (df) c b> 首先求得一项频繁集合为 a(4) b(4) c(4) d(3) e(3) f(3) 然后，频繁序列肯定是以这两个元素为开始的。 下面以求 a 开头的频繁序列模式为例子， 包含六中可能 (1) 序列中只包含a (2) 序列中只包含 a , b (3) 序列中只包含 a , b , c (4) 序列中只包含 a , b , c, d (5) 序列中只包含 a , b , c, d, e (6) 序列中只包含 a , b , c, d, e , f 在求第一种可能的时候，对数据库中的每条序列记录来说，去掉不包含在一项频繁集合中的元素，并且去掉 a 以外的元素。得到映射数据库为： 这里，求二项集合，可见，次数为2，是频繁序列。就这一个二项频繁序列，没有三项或以上的频繁序列。 求第二中情况， 同样，去掉非频繁元素及 a , b 以外的其他元素。 <(ab) b> 可见，该情况下有三个频繁二项序列。 为 ab(4), ba(2), (ab)(2)。 然后，再扫描一遍该映射数据库，分别从二项频繁序列中扩展三项频繁序列集，得到一项频繁三项序列为 aba(2) 同样，将其他集中情况一次的求解。得到以a 开始的频繁序列集。然后分别求以 b, d, e, f开头的频繁序列。就得到了所有的频繁序列集合。 2. PrefixSpan 算法 还以上面这个序列数据库为例，开头还是一样， 首先求得一项频繁集合为 a(4) b(4) c(4) d(3) e(3) f(3) 然后，频繁序列肯定是以这两个元素为开始的。 下面以求 a 开头的频繁序列模式为例子， 求的 a 的映射数据库为 <(abc) (ac) d (cf)> <(_d) c (bc) (ae)> <(_b) (df) c b> <(_f) c b c> 其中_b 表示前缀（这里前缀就是指a,前缀也有可能是ab, abc等）的最后一个元素和 b组成一个元素。 然后对 a的映射数据库进行查找局部频繁项（都是一项的），有 a(2), b(4), c(4), d(2), f(2), _b(2)(要注意，第一项中的ab和_b是表示同样的元素)。 所以二项频繁序列集合是前缀(这里是a)和这些从数据库中扫描出来的局部频繁项的组合。有： aa(2), ab(4), ac(4), ad(2), af(2), ab(2). 所以，以 a开头的频繁集又可以分为以这六项频繁序列为开头的六个映射数据库中查找。 下面以前缀为(aa)的映射数据库中查找为例： 以(aa)为前缀的映射数据库为 <(_bc) (ac) d (cf)> <(_e)> 因为不可能从这个数据库中再生成更多的频繁序列了。所以对 (aa)的处理在这里结束。 下面再以前缀(ab)为例，得到的映射数据库为 <(_c) (ac) d (cf)> <(_c) a> //这里必须注意， 不是(_c) (ae), 因为在前缀为 a 时， e 已经不是频繁项了 找到四个局部频繁项， (_c)(2), c(2), a(2), (_c)a 所以，组成四个三项频繁序列的前缀为： a(bc), abc, aba, a(bc)a, 然后同样进行每一项的映射数据库的建立，一直到再也没有频繁序列项为止。 和上面一样，分别对 a, b, c, d, e, f 为前缀的映射数据库进行求解，最后得到的结果就是所有的频繁序列集。 由此可见，PrefixSpan的收敛速度比FreeSpan的收敛速度还要快，但是当频繁序列的个数很大很大时候，两个算法的速度还都比较慢的。

评论