关联规则挖掘

频繁集是指market-basket模型中，相同商品集出现在不同basket中的概率较大的那一些集合，这里的概率threshold被叫做support，用mapreduce的方法或者思想可以很容易计算得到。而关联规则是频繁集挖掘里面不太重要的一个的事情，即求p(xj|x1,x2,...xi)，一个条件概率。只要统计出 (x1,...,xi) 以及 (x1,...,xi,xj)即可。因此大部分注意力应该集中在如何计算长度为k的频繁项中。

频繁项挖掘的应用，可以主要参考market-basket, market就是item的集合，而basket是item的一些子集合，因此我们认为这就是一个bi-partite graph的挖掘。举个例子，整个market是用户，则basket就是每一局的用户匹配/组队关系。挖掘频繁项就是挖掘经常一起组队的用户群体，这也被称为固定队。或者，更深一步，我们可以用特征来表示用户，比如说等级，地区，社群id等，就可以研究命题：什么样的用户/特征会经常一起组队；或者在NLP中，也可以用来挖掘topic，比如整个market就是所有的phrase，而每一个paragraph，或者文章就是basket，那经常一起出现的phrase可能就是抄袭。

频繁项挖掘最大的挑战一般是内存，因为我们最起码需要O(n)的内存量来记录每个item的count，然后需要O(n^2)来记录item pair的count，以此类推，关系集合越大，需要的内存量越大，且时间复杂度越高。考虑到关系的稀疏性，我们一般不用array的方式，而是用tuple的方式来表示数据，即(x1,...,xi, count)的方式，然后做mapreduce。但是这个还是需要统计全量的key和count。因此一个优化点就是通过filter掉一些低频的数据，来达到减少内存消耗的目的。这里是基于两个原理：

1. 低频的k集合，其关联的k+1集合只会更加低频。比如如果item i是个低频item，则i相关的pair只会低频（类比全概率公式，i的概率是 (i,j)概率的marginal sum）。

2. 集合k+1，则所有的k集合都是频繁的。

因此，我们在第k个pass的时候，就可以过滤掉所有低于threshold的k集合，然后再生成k+1的集合。

算法具体步骤如下

参考：

[1] https://blog.csdn.net/qq_41357569/article/details/118614358

[2] Mining of Massive Dataset, lecture 20.