Apriori Algorithm 是关联规则领域里最具影响力的基础算法。它是由 Rakesh Agrawal 在 1994 年提出的，详细的介绍在这里《Fast Algorithms for Mining Association Rules》。十几年过去了，不少学者围绕着 Apriori 进行了诸多改良。但与 1994 年相比，目前基于互联网的应用，数据量大了几十倍甚至是几百倍，因此，基于 Apriori 的算法逐渐暴露出其运算成本过高的问题。但不管怎样，对于大师及其做出的贡献，我们也只有高山仰止的份儿。
Apriori 是一种广度优先算法，通过多次扫描数据库来获取支持度大于最小支持度的频繁项集。它的理论基础是频繁项集的两个单调性原则：频繁项集的任一子集一定是频繁的；非频繁项集的任一超集一定是非频繁的。晦涩的理论我这里就不多写了，有兴趣的可以去看论文。我把里面的例子给翻译一下，图文并茂，简明易懂。
某数据库 DB 里有 4 条事务记录，取最小支持度（min support）为 0.5，则计算频繁项集的过程如下：
| TID |
Items |
| 100 |
A, C, D |
| 200 |
B, C, E |
| 300 |
A, B, C, E |
| 400 |
B, E |
|
扫描DB |
| Itemset |
Support |
| {A} |
2 (0.5) |
| {B} |
3 (0.75) |
| {C} |
3 (0.75) |
| {D} |
1 (0.25) |
| {E} |
3 (0.75) |
|
取满足
最小支持度
项集 |
| Itemset |
Support |
| {A} |
2 |
| {B} |
3 |
| {C} |
3 |
| {E} |
3 |
|
| Itemset |
| {A, B} |
| {A, C} |
| {A, E} |
| {B, C} |
| {B, E} |
| {C, E} |
|
扫描DB |
| Itemset |
Support |
| {A, B} |
1 (0.25) |
| {A, C} |
2 (0.5) |
| {A, E} |
1 (0.25) |
| {B, C} |
2 (0.5) |
| {B, E} |
3 (0.75) |
| {C, E} |
2 (0.5) |
|
取满足
最小支持度
项集 |
| Itemset |
Support |
| {A, C} |
2 |
| {B, C} |
2 |
| {B, E} |
3 |
| {C, E} |
2 |
|
| Itemset |
| {A, B, C} |
| {A, B, E} |
| {A, C, E} |
| {B, C, E} |
|
扫描DB |
| Itemset |
Support |
| {A, B, C} |
1 (0.25) |
| {A, B, E} |
1 (0.25) |
| {A, C, E} |
1 (0.35) |
| {B, C, E} |
2 (0.5) |
|
取满足
最小支持度
项集 |
| Itemset |
Support |
| {B, C, E} |
2 (0.5) |
|
如上可以看出，在海量数据的情况下，Apriori 算法的运算过程有 2 个问题：
- 需要多次扫描数据库，时间成本很高；
- 运算过程中需要产生大量的候选集，空间成本也非常高。
针对 Apriori 算法所做的改进也基本上是围绕着解决这两个问题进行的，如在扫描DB前首先进行以便事务合并和压缩，数据分区或抽样等。
Weka 里有 Apriori 算法的 Java 实现，非常值得一看。
貌似 wikipedia 已经解封了，呵呵！
预报：关联规则(3)，关于 FP-Growth 算法。
说到推荐系统，就不能不说关联规则。基于关联规则的推荐，是入门级的推荐技术实现，也是目前应用最广泛的一种推荐形式。
就拿刚上线的“蚂蚁”来说吧，打开《引爆流行》的页面，稍微滚动两下鼠标，你就可以看到这个了——“喜欢此宝贝的会员还喜欢”。豆瓣上也有类似的形式，还看《引爆流行》，豆瓣的是——“喜欢引爆流行的人也喜欢”。是不是很像？但别被形式迷惑了，这两个用的是完全不同的技术实现。豆瓣的之前我说过了，他是
Item-Based
方法；蚂蚁的这个应该就是关联规则方法了。当然我是猜的，不过也不是乱猜。有兴趣的可以刷刷上面那两个《引爆流行》的页面，看一下两个推荐区域的内容会有什么不同。
关联规则起源于数据挖掘领域，人们用它来发现大量数据中项集之间（有趣/有用）的关联。它本身是数据挖掘领域中一个重要的研究课题，近些年来更是由于被业界广泛应用而倍受重视。Rakesh
Agrawal 是关联规则领域的大牛，他于 1993 年发表的一篇
paper，《Mining
Association Rules between Sets of Items in Large Databases》，是被引用最多的一篇大作。不过让
google fans 们失望的是，他目前就职于 microsoft 的搜索实验室！^_^
关联规则的最典型例子就是购物篮分析。在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。原来，美国的妇女们经常会嘱咐她们的丈夫下班以后要为孩子买尿布。而丈夫在买完尿布之后又要顺手买回自己爱喝的啤酒，因此啤酒和尿布在一起购买的机会还是很多的。这个故事听起来是不是很酷？没错，这就是技术的力量！
但是，和任何其他经典的故事一样——这事儿听起来带劲儿，做起来很难！真正做过关联规则挖掘的人，一定都有这样的体会：想从浩瀚的记录集里，挖掘一条带劲儿的关联规则出来，简直太难了。（什么，你问有多难？请参照朱广沪~~~）
对于挖掘得到的关联规则，都会制定一些指标来衡量它们的有效程度，最经典的包括，支持度和置信度。简单来讲，
-
支持度是指，商品A、商品B在全部销售订单中所占的比例。
-
置信度是指，购买商品A并且同时购买了商品B的订单，在所有包含商品A的订单中所占的比例。
当然，这里的商品和订单是个泛化的概念，具体指代是的什么，就得具体问题具体分析了。
