问题定义
给定一个a set of sequences。其中每一个sequence 是 a list of elements 并且 每一个 element 是 a set of items。
| Sequence_id | Sequence |
|---|---|
| 10 | <a(abc)(ac)d(cf)> |
| 20 | <(ad)c(bc)(ae)> |
| 30 | <(ef)(ab)(df)cb> |
| 40 | <eg(af)cbc> |
子序列:
α=<a1 ,a2 ,..., an > , β=α=<b1 ,b2 ,..., bm>, 当且仅当:1≤j1＜j2<...< jn ≤ m 使得 α1 ⊆ bj1,α2 ⊆ bj2,...,αn ⊆ bjn时称α是β的子序列. 表示为α ⊆ β.
前缀:
投影:
后缀:
算法步骤
1：计算1-sequence pattern。其实就是扫一遍sequence database。统计每个item的支持度然后挑出来大于等于阈值的即可。可以找到的是<a>:4 , <b>:4 , <c>:4 , <d>:3 , <e>:3 和 <f>:3。 那么在这一步我们就获得了1-sequence pattern了，一共有6个。
2: 考虑将之后的其他的sequence pattern解划分为分别以上述的6个为前缀。
<a(abc)d(bc)e> 写成 <(a)(abc)(d)(bc)(e)> 。子串型匹配前缀。第一个(a)就有了。所以投影就是 <(a)(abc)(d)(bc)(e)>，而后缀是<(abc)(d)(bc)(e)>。
<(ef)(ab)(df)cb> 写成 <(ef)(ab)(df)(c)(b)> 。 子串型匹配前缀。 直到匹配到第两个element(ab)才有前缀<a>。
所以投影就是 <(ab)(df)cb>。而后缀是<(b)(df)cb>
而修改后的后缀为<(_b)(df)cb>。
3: 递归求解,第一次找出1-sequence pattern。并且根据这个为前缀来划分sequence pattern。其实就是做投影，取修改后的后缀。在新的sequence database上面找 2-sequence pattern的。
spark实现
package com.roobo.ai.library.machinelearning.mining
import org.apache.spark.{SparkConf, SparkContext}
import org.apache.spark.mllib.fpm.PrefixSpan
object PrefixSpanTest {
def main(args: Array[String]): Unit = {
val conf = new SparkConf().setAppName("prefixSpan").setMaster("local[4]")
val sc = new SparkContext(conf)
val sequences = sc.parallelize(Seq(
Array(Array("a"), Array("a", "b", "c"), Array("a", "c"), Array("d"), Array("c", "f")),
Array(Array("a", "d"), Array("c"), Array("b", "c"), Array("a", "e")),
Array(Array("e", "f"), Array("a", "b"), Array("d", "f"), Array("c"), Array("b")),
Array(Array("e"), Array("g"), Array("a", "f"), Array("c"), Array("b"), Array("c"))
), 2).cache()
val prefixSpan = new PrefixSpan()
.setMinSupport(0.5)
.setMaxPatternLength(5)
val model = prefixSpan.run(sequences)
model.freqSequences.collect().foreach { freqSequence =>
println(
s"${freqSequence.sequence.map(_.mkString("[", ", ", "]")).mkString("[", ", ", "]")}," +
s" ${freqSequence.freq}")
}
}
}
