序列模式挖掘(Sequential Pattern Mining)--核心算法学习

1. Suffix Tree(ST)----Ukkonen's Algorithm(UA)

$|S| = m$

• Prefix of S : $S[1,i]$
• Suffix of S : $S[i,m]$

Key: 如果 P 是 S 某个后缀的前缀，那么 P 是 S 的 substring

1 预先构造一个 Suffix trie

• Contruct

  • 每个边都有字符标签
  • 同一节点分出来的两个边不同一个标签
  • 每个 Substring 对应一个 叶子 (Leaf)

• Compress

  • 有根书 T 有 m 个叶子
  • 除去 root ；内部节点 有两个以上的child
  • T 的每个边使用字符串进行 label
  • 同一节点分出来的边 ，以不同的 字符开头
  • 对于每一个 Leaf(i),其中 $i$ 根据路径上的 label 在 S 的起始位置标定 $S[i,m]$

• Problem

  • 一个后缀是另一个后缀的前缀，那么该后缀的路径不会以叶节点结束

• Solve

  • 假定最后一个字符只出现在末尾，不出现在其他的地方
  • 加入一个新的字符 $ 在 S 的末尾

PS: 叶子数 = 后缀的数目

2 构建隐式 ST

• 从所有的边中 移除 $
• 移除所有没有 label 的边
• 移除只有一个 child 的节点

3 UA

$I_{i} = S[1,i]$    ##Prefix of S
construct I_{1}
## 从 I_{i} 构建I_{i+1}
for i = 1 to m-1
    for j = 1 to i + 1 
        找出P 从根部开始结束位置的label，逐一使用 S[i+1] 对P进行 extend
convert I to ST

• Extend 原则
  
  • 结束在 叶节点，直接加入
  • 不终止在叶节点，而且后面的字符不是 $S[i+1]$
    
    • 分割一个新的边
    • 或者可能创建一个 Internal node
  • 已经存在在，无需变动

4 减少 Runtime ---> O(m)

• Suffix link
• Count Trick
• ....
*

1 Suffix link

扩展后，直接跳转到下一个需要扩展的地方，而不是从根部开始搜索查询

• 隐式ST 每个内部节点都有一个 suffix link (在下一个扩展结束的时候)

2 Count

• Key : 每个节点只需要搜索首字符
• 计数，counter 小，skip

5 使用的数据结构

• An Array
• A linked list
• A balanced Tree
• A hashing scheme

6 广义后缀树

Define ： A set of Strings S.

2 Apriori-like 算法

Key： 不频繁的子序列的额超集也不频繁

1 Apriori Alg

• 1. 评估标准： 支持度(Support) or 置信度(Confidence)
• 1. 迭代的思想
     
     • 找出所有的包含1项的集合，小于支持度的去除
     • 将剩余的 1 项集 进行 连接（按照顺序），构成2 项集
     • 直到出现空，或者剩1

2 GSP

• 加入时间约束： 满足[min,max] 之间的都符合连续
• 加入 time-windows-size,在size内的 认为是同一个 itemset

3 FP-Tree

• 建立项目头表

  • 扫描数据，得到所有1项频繁的计数，除去小于support的，降序排列
  • 再次扫描，原始数据中除去 小于的，，字符降序排列
    PS： 降序排列有利于更多的使用祖先节点

• 建立FP-tree

  • 按照顺序插入 树，靠前的是祖先节点，后是子节点
  • 插入序列
    
    • 共同祖先 ： 祖先计数+1
    • 新节点出现

• 建立link

  • 建立项目头表和节点的link
  • 建立新节点和已经存在的节点的link

• 挖掘

  • 从项目头表的底部向上挖掘
  • 找每一项的 条件模式基

3 PrefixSpan 前缀投影的模式挖掘

• 输出：所有满足支持度要求的频繁序列集

• 从长度为1的前缀开始挖掘序列模式，搜索对应的投影数据库得到长度为1的前缀对应的频繁序列，

• 然后递归的挖掘长度为2的前缀所对应的频繁序列，

• PrefixSpan算法由于不用产生候选序列，且投影数据库缩小的很快，内存消耗较小
• PrefixSpan可以优化构造投影数据库

针对特定的实际情况优化算法

刘闯
2018/10/30