原创文章，转载请表明出处

今天将前段时间学的部分知识做一个总结，之前公司有一个业务为同纬度下，挖掘各个项之间有什么潜在的关系。经过一顿思考，我发现这个需求很像一个案例，那就是啤酒和纸尿裤。又经过一顿Google，百度。哦！原来完成这个需求的算法统称关联规则，我们下面就先简单的介绍一下何为关联规则。

关联规则：从大规模数据集中，寻找各个项的隐含关系被称作关联分析或者关联规则学习。

再往通俗易懂了说，就是从大规模数据中，我们去找哪些项总是同时出现，频繁出现。

那频繁的定义是什么呢？怎样才算频繁呢？度量他们的方法有很多种，这里我们来简单介绍一下支持度和置信度，下图是王者荣耀商店每个顾客买的商品公仔（图画的有点糙，哈哈）。

例图1

支持度：数据集中该项集的记录数量所占的比例，例如上图中，{貂蝉公仔}的支持度为4/10,{貂蝉公仔，吕布公仔}的支持度为2/10。

置信度：针对一条如{吕布公仔}-->{貂蝉公仔}这样的关联规则来定义的，这条规则的置信度被定义为：支持度({吕布公仔, 貂蝉公仔})/支持度({吕布公仔})。再通俗易懂的讲就是用户买吕布公仔的前提下，有多大几率买貂蝉公仔。从图中可以看出，支持度({吕布公仔, 貂蝉公仔})=2/10，支持度({吕布公仔})=2/10。所以{吕布公仔}-->{貂蝉公仔}的置信度=2/10/2/10=1。也就是说用户买了吕布公仔，肯定会买貂蝉公仔。

以上就是对关联规则本质上的一个介绍。下面我们再从实现上说一下典型的关联规则算法Aprioir。还是根据上面那张图描述一下Aprioir的逻辑步骤。

1.自己规定一个支持度阈值为：0.2，用来过滤不频繁项集。

2.扫描事物集，寻找1项频繁集并过滤，如下图：

1项频繁集

3，再次扫描事务集，寻找2项频繁集再过滤：如下图：

2项频繁集

4，以此类推，推到没有频繁项集为止。（我们这里上图的数据集也就到2项频繁集就没有了）

5，发现关联规则：以上四步把各个频繁集的支持度都已经得出，置信度上文也提及过了，这样就可以得出关联规则了。

从上述算法步骤中可以看出，Aprior算法每轮迭代都要扫描数据集，因此在数据集很大，数据种类很多的时候，算法效率很低。经过多方了解，我又找到了FP-growth算法。

FP-growth

FP-growth算法不同于Apriori算法生成频繁项集再检查是否频繁，不断扫描事物集。而是使用一种称为频繁模式树（FP-Tree，PF代表频繁模式，Frequent Pattern）菜单紧凑数据结构组织数据，并直接从该结构中提取频繁项集，不需要产生候选集。每个事务被映射到FP-tree的一条路径上，不同的事务会有相同的路径，因此重叠的越多，压缩效果越好。

FP-growth分为两大步，一是构建频繁模式树，二是从频繁模式树中挖掘各个频繁项集。下面从逻辑上说一下。由于上组数据集有点不满足现在这个需求，我们换一组数据集。现有如下数据集：

数据集

FP-growth算法需要对原始训练集扫描两遍以构建FP树。第一次扫描，过滤掉所有不满足最小支持度的项；对于满足最小支持度的项，按照全局最小支持度排序，在此基础上，为了处理方便，也可以按照项的关键字再次排序。

过滤并排序的数据集

第二次扫描，构造FP树。参与扫描的是过滤后的数据，如果某个数据项是第一次遇到，则创建该节点，并在headTable中添加一个指向该节点的指针；否则按路径找到该项对应的节点，修改节点信息。具体过程如下所示：

事物1{z,r} 事物2{z,x,y,t,s} 事物3{z} 事物4{x,s,r} 事物5{z,x,y,t,r} 事物6{z,x,y,t,s}

从上面可以看出，headTable并不是随着FPTree一起创建，而是在第一次扫描时就已经创建完毕，在创建FPTree时只需要将指针指向相应节点即可。从事务004开始，需要创建节点间的连接，使不同路径上的相同项连接成链表。

下面我们结合spark中的源码讲一下（只讲和算法相关的部分，讲个大概，细节还得自己去看）。

入口函数

上图是FP-growth的入口函数，val count = data.count()，得出事物集的总条数。

val minCount = math.ceil(minSupport * count).toLong，根据设定的最小支持度得出最小条数。

val freqItems = genFreqItems(data, minCount, partitioner)，得到1项频繁集并过滤按照次数排序（在这篇文章里叫这个顺序叫全局顺序）。这是该算法第一次扫描事物集。

val freqItemsets = genFreqItemsets(data, minCount, freqItems, partitioner)，构建树，并挖掘树，得到频繁项集。这个方法很重要，我们下面跟一下这个方法。

构建并挖掘树

val itemToRank = freqItems.zipWithIndex.toMap，将每条事物加上索引。后续处理每个项拿索引替代。

genCondTransactions(transaction, itemToRank, partitioner)，将事务集的每行按照上面提到的全集顺序排好。

(tree, transaction) => tree.add(transaction, 1L),(tree1, tree2) => tree1.merge(tree2))，每个分组内各构建一颗树。

tree.extract(minCount, x => partitioner.getPartition(x) == part)，对每颗树进行递归挖掘出频繁项集。

至此，完毕！

---

以上所述如有不妥，恳请大家指正。

(如果对您有所帮助话，那就点个赞点个关注吧，嘻嘻~~)

安利一个特别热心的编程乐园群：624108656

超级热心的群