Association Rule Learning是一种用来发掘目前的数据库里的变量之间潜在的关系的例子，这里最有名的例子当属“啤酒与纸尿布”的故事了，实际就是 做了A，然后又会去做B 。

一个直接的应用就是购物篮分析，或者更流行的，推荐系统( recommendation system )。这些都是能很快想到的应用。可能用到的场所比如沃尔玛（也是之前的啤酒尿布的故事来源）、豆瓣儿（我猜，我猜，我猜猜猜）、Amazon、Taobao或者NetFlix之类的。

提到关联规则几乎第一个跳出来的要讲的就是Apriori系列的算法，此算法是前IBM Lab的Rakesh Agrawal大牛在94的VLDB的一篇叫《Fast Algorithms for Mining Association Rules》的paper里提出来的，该算法在2006年的ICDM里被评选为Top 10 algorithms in data mining. 这个paper也有超过8k的引用，可谓是非常非常的seminal了。

这儿有个八卦，2006年的时候微软偷偷挖走了Rakesh，IBM一看急了，你这个把我们数据组核心专家挖走了以后日子还怎么过啊！而且IBM之前也是给了有超过70万美金的股票期权等来试图以这种方式留人，结果二月份时候Rakesh先是把期权给卖了，然后才加入了M$。IBM就直接一纸诉状给他告上了法庭。结果不了了之，搞技术的挖墙角的事儿见多了。

回到正题，Apriori要解决的是：找出出现的次数大于一个指定的threshold的项集(itemSet)。直接暴力解决的复杂性是不言而喻的，单一个n元素的集合的不同的子集的个数就有{2^n}个，就别说再搭配了。而Apriori的算法的核心思想就是化大为小，从item很小开始做起，慢慢变大。

“老鼠的爸爸也是老鼠”原理：非频繁项集的超集也是非频繁的
if an itemset is not frequent, any of its superset is never frequent

很容易理解吧，因为超集的support（支撑度def: Freq/Obs）肯定小于等于子集嘛。理解了这么多基本就可以猜出算法啦：

第三行的函数Apriori-gen函数分两步走：

1.  
   1. 连接步: R_{k+1}，连接所有的满足前{k-1}个元素相同的P_k和R_k生成一个k+1元的itemset
      e.g.:P_k={ a_1, a_2, …a_{k-1}, a_k},  R_k={ a_1, a_2, …a_{k-1}, a_k’ }
            ---> R_{ k+1 }={ a_1, .. a_{k-1}, a_k, a_k’ }
   2. 剪枝步: 如果R_{k+1}中有任一k元子集R’不是频繁集，那么直接剪去该枝，如前所言，必须要是所有的自己都是频繁的，那么超集本身才可能是频繁的。

与此同时，Apriori的缺点也是一堆啦，频繁的扫描数据库，必然带来算法效率的低下，下篇给一个算法Demo和潜在的改进。