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 算法。
