`

推荐系统:关联规则(2)

阅读更多

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 个问题:

  1. 需要多次扫描数据库,时间成本很高;
  2. 运算过程中需要产生大量的候选集,空间成本也非常高。

针对 Apriori 算法所做的改进也基本上是围绕着解决这两个问题进行的,如在扫描DB前首先进行以便事务合并和压缩,数据分区或抽样等。

Weka 里有 Apriori 算法的 Java 实现,非常值得一看。

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics