关联分析算法：FP-Growth

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

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

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

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

1、FP-Growth

1.1 原始数据准备

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

1.2 建立项头表

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

1.3 筛选 排序 原始数据

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

1.4 构建FP-Tree

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

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

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

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

1.5 挖掘频繁项集

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

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

删除图中节点计数小于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
• 挖掘频繁项集

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

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

抄个算法放在这里：

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

再抄个算法放在这里：

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

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

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时，表示两件事相互独立，即一件事的发生，对于另一件事的出现无影响。

最后，贴两篇参考文章。

• Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach
• PFP: Parallel FP-Growth for Query Recommendation