数据挖掘-序列模式挖掘-FreeSpan算法总结

FreeSpan是一种基于频繁模式投影的序列模式挖掘算法，通过递归地对每个频繁序列进行投影来发现所有可能的序列模式。该算法的主要步骤包括：(1) 生成频繁项；(2) 构建频繁矩阵；(3) 处理长度为2的序列模式项；(4) 处理重复项标记；以及(5) 生成投影数据库。FreeSpan能够高效地从大规模数据集中提取出所有满足最小支持度条件的序列模式，并且在数据挖掘和分析中有广泛的应用。

一：论文位于：

标题 ：FreeSpan: 频繁模式投影序列模式挖掘

基于频繁模式投影的序列模式挖掘

二：FreeSpan算法

该算法主要采用基于频繁模式投影的方法，在每一次迭代过程中筛选出当前最长序列中的所有长度为二的频繁子序列，并递归地对这些子序列及其生成的所有可能投影进行深入分析。系统能够完整地提取出所有潜在存在的序列模式。

算法流程：

（1）生成频繁项

基于序列数据库S以及给定的最小支持度sup值，在系统运行的第一阶段遍历整个序列数据库S以识别并收集所有单个项目的频繁项集，并按照这些项的支持度从高到低进行排序处理。例如，在以下提供的序列数据中： S = \{b\rightarrow5,\ c\rightarrow4,\ a\rightarrow3,\ d\rightarrow3,\ e\rightarrow3,\ f\rightarrow3\} 时

(2) 生成频繁矩阵

扫描S,构建频繁项矩阵,是一个三角矩阵

该指标由有序三元组(A, B, C)组成。其中x和y被视为频繁项，

F(x, y) = \frac{A + B}{2n}

其中n = |S|代表序列总长度，

A = \sum_{i=1}^{n-1} I(x_i > x_{i+1}), \quad B = \sum_{i=1}^{n-1} I(y_i > y_{i+1})

并且，

C = \sum_{s=1}^m I(\text{term } s \text{ 包含 } x \text{ 和 } y)

这些定义有助于量化 x
与 y
之间的顺序依赖关系。

该矩阵的处理方式是基于行的数据组织形式。在处理每条数据时，在计算所有可能的组合时（即对于每条数据而言），其所需的时间复杂度为O(n^2)（即O(n^2)），这种计算模式能够有效生成所有的组合结果）。

（3）生成长度为2的序列模式项

由于F[x,y]包含了由x和y构成的三个序列模式项，在处理过程中首先通过计数值与最小支持度比较筛选出不满足条件的组合。接着将这些组合逐一列举出来：例如F[b,e]对应的三项分别是be、eb以及(be)be、eb、(be)等。该步骤对应于表3中第二列的位置，在该列表中第一列为基于频繁一项集的支持度进行排序的结果。

（4）生成重复项标记

重复项的符号标记由第二列的数据结果决定，在没有重复项的情况下（即第二列为非b序列），当模式F[b,b]F[b,b]F[b,b]达到所需支撑度时，则应在对应的符号标记位置标注b+b^+b +。值得注意的是，在符号标记中使用{}的形式可灵活搭配（如{b+f+}{b^+f+}{b +f + }），而<>类型的具体形式则保持不变（如<bbf,fbf,(bf)b,(bf)f, (bf)bf)）。具体模式识别则需遍历数据集。

（5）生成投影数据库

在第一列中存在2-sequence时，则计算其前缀投影以获得第四列的结果。如果不存在前缀，则该序列模式已在第三阶段被确定。否则需对第四列执行递归操作以获取结果：每次将当前阶段的数据库中的项目与已知的所有频繁序列连接起来再继续递归运算。整个过程总共进行了三次扫描：第一次获取所有单项集；第二次构建频繁矩阵；第三次提取重复模式并建立投影数据库

三：转载：

文章版权说明：本文由博主「很吵请安青争」原创的文章，请在转载时注明出处及使用本声明

原文链接