关联分析算法:FP-Growth

4,246 阅读6分钟

关联分析是从大量数据中发现项集之间相关联系,分析出如“由于某些事件的发生而导致另外一些事件的发生”之类的规则。

关联分析的一个典型例子是购物车分析。该过程通过发现用户加入购物车中的不同商品之间的联系,分析用户的购买习惯,了解哪些商品频繁地被用户同时购买。这种关联关系的发现可以帮助商家制定营销策略,例如商品的促销和摆放组合等。

FP-Growth算法是韩嘉炜等人提出的关联分析算法。该个算法构建通过两次数据扫描,将原始数据中的item压缩到一个FP-tree(Frequent Pattern Tree,频繁模式树)上,接着通过FP-tree找出每个item的条件模式基,最终得到所有的频繁项集。

  • 优点:简单易上手,部署起来也很方便。
  • 缺点:需要有较多的数据,且效果一般。

1、FP-Growth

1.1 原始数据准备

定义“TID”为订单ID,“Items bought”为一次订单内购买的商品,准备原始数据如下表所示。

TID Items bought
100 {f, a, c, d, g, i, m, p}
200 {a, b, c, f, l, m, o}
300 {b, f, h, j, o}
400 {b, c, k, s, p}
500 {a, f, c, e, l, p, m, n}

1.2 建立项头表

在构建FP-Tree之前,首先要建立一张项头表。扫描原始数据,并对每个商品进行计数。在这里可以设置阈值,比如保留最少要出现三次的商品。筛选后剩下a,b,c,f,m,p这六个商品,将这些商品按数量降序排列,生成项头表。

Item Count
f 4
c 4
a 3
b 3
m 3
p 3

1.3 筛选排序原始数据

接下来开始第二次扫描原属数据,对于每条数据,剔除非项头表上的商品,并按照支持度降序排列。比如订单100,购买商品为{f, a, c, d, g, i, m, p},剔除数据后为{f, a, c, m, p},排序后为{f, c, a, m, p}。其他的原始数据以此类推进行处理,得到排序后的数据集。

TID Items bought (Ordered) frequent items
100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
200 {a, b, c, f, l, m, o} {f, c, a, b, m}
300 {b, f, h, j, o} {f, b}
400 {b, c, k, s, p} {c, b, p}
500 {a, f, c, e, l, p, m, n} {f, c, a, m, p}

1.4 构建FP-Tree

有了项头表和筛选排序后的原始数据集,接下来就可以构建FP-Tree了。建立FP-Tree需要我们一条条的读取筛选排序后的原始数据,并按照顺序依次插入到树中。如果有公共的祖先节点,则在对应的祖先节点加1。同时,新节点出现时,需要将其链接到项表头对应的节点链表。直到所有数据都插入树中,则构建完成。

接下来还是用上面的数据举个例子。首先插入TID 100,此时FP-Tree没有其他节点,因此{f, c, a, m, p}是一个独立的路径,所有节点计数为1, 项头表通过节点链表链接上对应的新增节点。

avatar

接着插入TID 200,{f, c, a, b, m},其中f、c、a三个节点公用,计数变为2,到b节点产生新的分支,m为b的子节点,两个节点计数为1。当然,对应的b、m两个节点的链表也要更新。

avatar

依次处理剩下的三条数据,构建完成FP-Tree

avatar

1.5 挖掘频繁项集

准备好了FP-Tree,接下来就可以开始挖掘频繁项集。遍历项头表依次挖掘,找到每项的条件模式基。条件模式基是以要挖掘的节点作为叶子节点所对应的子树。得到这个子树,将子树中每个节点的的计数设置为叶子节点的计数,并删除计数低于约定值的节点。从这个条件模式基,我们就可以递归挖掘得到频繁项集了。

假设需要的最小节点计数为2,开始挖掘p节点,如下图所示

avatar

删除图中节点计数小于2的红色{c:1}、{b:1}、{p:1}节点,得到{p:2}节点的条件模式基为{f:2, c:2, a:2, m:2}。通过它,可以递归得到频繁二项集{f:2, p:2}、{c:2, p:2}、{a:2, p:2}、{m:2, p:2},频繁三项集{f:2, c:2, p:2}、{f:2, a:2, p:2}等等,最后得到最大的频繁项集为频繁五项集,为{f:2, c:2, a:2, m:2, p:2}。

如果最小节点计数为1,则可在挖掘完上面的子树后,根据项表头对应的节点链表找到红色的节点{p:1},继续挖掘频繁项集。

至此,p节点挖掘完毕,可以继续挖掘其他节点。挖掘完所有节点,也就得到了所有的频繁项集。至于最后f节点,由于它的条件模式基为空,因此可以不用去挖掘。

2、PFP-Growth

通过上面的介绍,可以注意到在挖掘频繁项集时,FP-Tree可能会非常大,递归得到的频繁项集也可能有指数多个。但同时也发现,每个项头表的商品对应的挖掘子树,都是互相独立的,也就是说可以并行化挖掘频繁集。因此,可以单个商品构建一棵FP-Tree,也可以几个商品以小组的形式构建一棵FP-Tree。

回忆一下单机挖掘频繁项集的步骤,可以总结出可并行化执行的节点如下:

  • 建立项头表
  • 构建FP-Tree
  • 挖掘频繁项集

因此,可以总结出并行挖掘频繁集的步骤如下所示:

  • 第一步,分割原始数据,根据分割的每片数据,并行化计数,生成项头表。

抄个算法放在这里:

avatar

  • 第二步,将项头表的商品分组,对每一组进行单独的频繁项集挖掘。

再抄个算法放在这里:

avatar

  • 第三步,将第二步的结果进行聚合总结。

最后抄一个算法放在这里:

avatar

3、其他

再讲几个可以对算法结果进行干预的点吧。除了上面介绍算法时两个可以对数据进行筛选的节点,还可以在算法前对原始数据进行处理,或者算法结束后对生成的频繁项集进行处理。

1、首先可以根据订单里商品出现的次数、订单时间、日均销量等信息设定权重值。并根据加权后的数据进行项头表和FP-Tree的构建。

2、其次对于生成的频繁结果集,可以通过计算置信度和提升度对最终结果进行筛选。

  • 其中置信度计算规则,conf(X->Y) = P(Y|X) = P(X,Y)/P(X)。置信度越高,关联性越强。
  • 提升度计算规则,lift(X->Y)=P(X,Y)/(P(X)P(Y)) = conf(X->Y)/P(Y)。关联规则提升度大于1,为有效;小于等于1,为无效。特别的,当提升度等于1时,表示两件事相互独立,即一件事的发生,对于另一件事的出现无影响。

最后,贴两篇参考文章。