FP-Growth 频繁模式增长算法

Question

FP-Growth（频繁模式增长）算法是韩家炜老师在 2000 年提出的关联分析算法，它采取如下分治策略：将提供频繁项集的数据库压缩到一棵频繁模式树（FP-Tree），但仍保留项集关联信息；该算法和 Apriori 算法最大的不同有两点：第一，不产生候选集，第二，只需要两次遍历数据库，大大提高了效率。

演示—构造 FP-树

1、事务数据库建立

原始事务数据库如下：

Tid	items
1	I1,I2,I5
2	I2,I4
3	I2,I3
4	I1,I2,I4
5	I1,I3
6	I2,I3
7	I1,I3
8	I1,I2,I3,I5
9	I1,I2,I3

扫描事务数据库得到频繁 1-项目集 F。

I1:6 I2:7 I3:6  I4:2  I5:2

定义 minsup=20% ，即最小支持度为 2 ，重新排列 F。

I2:7  I1:6  I3:6  I4:2  I5:2

重新调整事务数据库。

Tid	items
1	I2, I1,I5
2	I2,I4
3	I2,I3
4	I2, I1,I4
5	I1,I3
6	I2,I3
7	I1,I3
8	I2, I1,I3,I5
9	I2, I1,I3

（2）创建根结点和频繁项目表

（3）加入第一个事务（I2,I1,I5）

（4）加入第二个事务(I2,I4)

（5）加入第三个事务(I2,I3)

以此类推加入第 5、6、7、8、9 个事务。

（6）加入第九个事务(I2,I1,I3)

演示—FP-树挖掘

FP-树建好后，就可以进行频繁项集的挖掘，挖掘算法称为 FpGrowth（Frequent Pattern Growth）算法，挖掘从表头 header 的最后一个项开始，以此类推。本文以 I5、I3 为例进行挖掘。

（1）挖掘 I5：

对于 I5，得到条件模式基： &lt;(I2,I1:1)&gt;、<i2,i1,i3:1>

构造条件 FP-tree：

得到 I5 频繁项集： {{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}

I4、I1 的挖掘与 I5 类似，条件 FP-树都是单路径。

（2）挖掘 I3：

I5 的情况是比较简单的，因为 I5 对应的条件 FP-树是单路径的，I3 稍微复杂一点。I3 的条件模式基是(I2 I1:2), (I2:2), (I1:2)，生成的条件 FP-树如下图：

I3 的条件 FP-树仍然是一个多路径树，首先把模式后缀 I3 和条件 FP-树中的项头表中的每一项取并集，得到一组模式{I2 I3:4, I1 I3:4}，但是这一组模式不是后缀为 I3 的所有模式。还需要递归调用 FP-growth，模式后缀为{I1，I3}，{I1，I3}的条件模式基为{I2：2}，其生成的条件 FP-树如下图所示。

在 FP_growth 中把 I2 和模式后缀{I1，I3}取并得到模式 {I1 I2 I3:2} 。

理论上还应该计算一下模式后缀为{I2，I3}的模式集，但是{I2，I3}的条件模式基为空，递归调用结束。最终模式后缀 I3 的支持度>2 的所有模式为： { I2 I3:4, I1 I3:4, I1 I2 I3:2} 。

Spark MLlib 中的 FP-growth 算法参数：

• minSupport: 最小支持度
• numPartitions: 分布式运行情况下分区数

例子（Examples）

FPGrowth 实现了 FP-growth 算法。该算法采用的是 RDD 事务每个 RDD 都是 Array 类型，运行该事务就返回 FPGrowthModel 用该模型存储频繁项集和它们的频率。下面的示例演示如何从事务中挖掘频繁项集和关联规则。

val PATH = "file:///Users/lzz/work/SparkML/"
import org.apache.spark.rdd.RDD
import org.apache.spark.mllib.fpm.FPGrowth

val data = sc.textFile(PATH+"data/mllib/sample_fpgrowth.txt")

val transactions: RDD[Array[String]] = data.map(s => s.trim.split(' '))

val fpg = new FPGrowth().setMinSupport(0.2).setNumPartitions(10)
val model = fpg.run(transactions)

model.freqItemsets.collect().foreach { itemset =>
  println(itemset.items.mkString("[", ",", "]") + ", " + itemset.freq)
}

val minConfidence = 0.8
model.generateAssociationRules(minConfidence).collect().foreach { rule =>
  println(
    rule.antecedent.mkString("[", ",", "]")
      + " => " + rule.consequent .mkString("[", ",", "]")
      + ", " + rule.confidence)
}

[z], 5
[x], 4
[x,z], 3
[y], 3
[y,x], 3
[y,x,z], 3
[y,z], 3
[r], 3
[r,x], 2
[r,z], 2
[s], 3
[s,y], 2
[s,y,x], 2
[s,y,x,z], 2
[s,y,z], 2
[s,x], 3
[s,x,z], 2
[s,z], 2
[t], 3
[t,y], 3
[t,y,x], 3
[t,y,x,z], 3
[t,y,z], 3
[t,s], 2
[t,s,y], 2
[t,s,y,x], 2
[t,s,y,x,z], 2
[t,s,y,z], 2
[t,s,x], 2
[t,s,x,z], 2
[t,s,z], 2
[t,x], 3
[t,x,z], 3
[t,z], 3
[p], 2
[p,r], 2
[p,r,z], 2
[p,z], 2
[q], 2
[q,y], 2
[q,y,x], 2
[q,y,x,z], 2
[q,y,z], 2
[q,t], 2
[q,t,y], 2
[q,t,y,x], 2
[q,t,y,x,z], 2
[q,t,y,z], 2
[q,t,x], 2
[q,t,x,z], 2
[q,t,z], 2
[q,x], 2
[q,x,z], 2
[q,z], 2
[t,s,y] => [x], 1.0
[t,s,y] => [z], 1.0
[y,x,z] => [t], 1.0
[y] => [x], 1.0
[y] => [z], 1.0
[y] => [t], 1.0
[p] => [r], 1.0
[p] => [z], 1.0
[q,t,z] => [y], 1.0
[q,t,z] => [x], 1.0
[q,y] => [x], 1.0
[q,y] => [z], 1.0
[q,y] => [t], 1.0
[t,s,x] => [y], 1.0
[t,s,x] => [z], 1.0
[q,t,y,z] => [x], 1.0
[q,t,x,z] => [y], 1.0
[q,x] => [y], 1.0
[q,x] => [t], 1.0
[q,x] => [z], 1.0
[t,x,z] => [y], 1.0
[x,z] => [y], 1.0
[x,z] => [t], 1.0
[p,z] => [r], 1.0
[t] => [y], 1.0
[t] => [x], 1.0
[t] => [z], 1.0
[y,z] => [x], 1.0
[y,z] => [t], 1.0
[p,r] => [z], 1.0
[t,s] => [y], 1.0
[t,s] => [x], 1.0
[t,s] => [z], 1.0
[q,z] => [y], 1.0
[q,z] => [t], 1.0
[q,z] => [x], 1.0
[q,y,z] => [x], 1.0
[q,y,z] => [t], 1.0
[y,x] => [z], 1.0
[y,x] => [t], 1.0
[q,x,z] => [y], 1.0
[q,x,z] => [t], 1.0
[t,y,z] => [x], 1.0
[q,y,x] => [z], 1.0
[q,y,x] => [t], 1.0
[q,t,y,x] => [z], 1.0
[t,s,x,z] => [y], 1.0
[s,y,x] => [z], 1.0
[s,y,x] => [t], 1.0
[s,x,z] => [y], 1.0
[s,x,z] => [t], 1.0
[q,y,x,z] => [t], 1.0
[s,y] => [x], 1.0
[s,y] => [z], 1.0
[s,y] => [t], 1.0
[q,t,y] => [x], 1.0
[q,t,y] => [z], 1.0
[t,y] => [x], 1.0
[t,y] => [z], 1.0
[t,z] => [y], 1.0
[t,z] => [x], 1.0
[t,s,y,x] => [z], 1.0
[t,y,x] => [z], 1.0
[q,t] => [y], 1.0
[q,t] => [x], 1.0
[q,t] => [z], 1.0
[q] => [y], 1.0
[q] => [t], 1.0
[q] => [x], 1.0
[q] => [z], 1.0
[t,s,z] => [y], 1.0
[t,s,z] => [x], 1.0
[t,x] => [y], 1.0
[t,x] => [z], 1.0
[s,z] => [y], 1.0
[s,z] => [x], 1.0
[s,z] => [t], 1.0
[s,y,x,z] => [t], 1.0
[s] => [x], 1.0
[t,s,y,z] => [x], 1.0
[s,y,z] => [x], 1.0
[s,y,z] => [t], 1.0
[q,t,x] => [y], 1.0
[q,t,x] => [z], 1.0
[r,z] => [p], 1.0