4 种序列模式挖掘算法的比较分析

  • AprioriAll 算法属于 Apriori 类算法,其基本思想为首先遍历序列数据库生成候选序列并利用 Apriori 性质进行剪枝得到频繁序列。每次遍历都是通过连接上次得到的频繁序列生成新的长度加1的候选序列,然后扫描每个候选序列验证其是否为频繁序列。
  • GSP(generalized sequential pattern)算法是 AprioriAll 算法的扩展算法,其算法的执行过程和 AprioriAll 类似,最大的不同在于 GSP 引入了时间约束、滑动时间窗和分类层次技术,增加了扫描的约束条件,有效地减少了需要扫描的候选序列的数量。此外 GSP 利用哈希树来存储候选序列,减少了需要扫描的序列数量。
  • FreeSpan 算法是基于模式投影的序列挖掘算法,其基本思想:利用当前挖掘的频繁序列集将序列数据库递归地投影到一组更小的投影数据库上,分别在每个投影数据库上增长子序列。这一过程对数据和待检验的频繁模式集都进行了分割,并且每一次检验限制在与其相符合的更小投影数据库中。
  • PrefixSpan 是 FreeSpan 的改进算法,即通过前缀投影挖掘序列模式。其基本思想:投影时不考虑所有可能出现的频繁子序列,只检查前缀序列,然后把相应的后缀投影成投影数据库。每个投影数据库中,只检查局部频繁模式,在整个过程中不需要生成候选序列。

AprioriAll GSP 这两种算法都属于 Apriori 类算法,都要产生大量的候选序列,需要有足够的存贮空间。同时还需要反复扫描数据库,需要占用很多运行时间。该类算法的执行效率比较低,特别是在支持度比较低的情况下,其执行效率将会大大下降。和 AprioriAll 相比,GSP 的执行效率比较高,总体来说要比 AprioriAll 高 2~20 倍。

FreeSpan PrefixSpan 这两种算法都属于模式增长算法,它们的查找更加集中和有效。由于该类算法不生成大量的候选序列以及不需要反复扫描原数据库,和 Apriori 类算法相比该类算法要快且更有效,特别是在支持度比较低的情况下更明显。此外,在时空的执行效率上,PrefixSpan 比 FreeSpan 更优。

  • Post author: fpcheng
  • Post link: https://blog.51cto.com/fpcheng/829527
  • Copyright Notice: All articles in this blog are licensed under BY-NC-SA unless stating additionally.
0%