FreeSpan算法

FreeSpan（frequent pattern-projected sequential pattern mining，频繁模式投影的序列模式挖掘）算法是由Jiawei Han等于2000年提出的，它利用已产生的频繁集递归产生投影数据库，然后在投影数据库中增长子序列。

算法不仅可以挖掘所有序列模式，还减少了产生候选序列所需开销，提高算法效率。

算法挖掘过程

（1）对于给定的序列数据库S及最小支持度阈值min_sup，首先扫描S，找到S中所有频繁项的集合，并以降序排列生成频繁项表即f-list表，设f-list=（x1，x2，…，xn）。

（2）将S中所有的序列模式集合可以划分成n个互不重叠的子集，即根据生成的f-list表把序列数据库S分成几个不相交的子集即i投影数据库：

只包含项x1的序列模式集合。

包含项x2，但不包含（x3，…，xn）中项的序列模式集合。

包含项x3，但不包含（x4，…，xn）中项的序列模式集合。

……

包含项xn-1，但不包含项xn的序列模式集合。包含项xn的序列模式集合。

（3）在<xi>投影数据库中通过扫描找出频繁2-序列集合，对于其中的每个频繁2-序列，再次扫描<xi>投影数据库生成该频繁2-序列的投影数据库，从中找出频繁3-序列集合，…依此类推，直到某个投影数据库中找不到更长的序列为止。