推荐系统:关联规则(2)
来源:百度文库 编辑:神马文学网 时间:2024/03/29 20:10:15
推荐系统:关联规则(2)
本文可以任意转载,转载时请务必以超链接形式标明文章 原始出处 与 版权信息。http://www.guwendong.cn/post/2007/apriori_algorithm.html
Wednesday, July 11, 2007 10:50:05 AM 发布:guwendong
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 个问题:
- 需要多次扫描数据库,时间成本很高;
- 运算过程中需要产生大量的候选集,空间成本也非常高。
Weka 里有 Apriori 算法的 Java 实现,非常值得一看。
貌似 wikipedia 已经解封了,呵呵!
预报:关联规则(3),关于 FP-Growth 算法。
推荐系统:关联规则(2)
推荐系统:关联规则(1)
关联规则挖掘综述
B2C之关联推荐:聚物,聚人
【转】关联规则数据挖掘的算法相关_土拨呼
【转】关联规则数据挖掘的算法相关_土拨呼
总述频繁模式、关联规则和相关规则的挖掘
数据挖掘中关联规则中求频繁项集的aprior算法
数据挖掘中关联规则中求频繁项集的aprior算法
湖州市纪检监察系统内部督察工作规则
GTS全球外汇交易系统帐户规则说明
股票交易软件 股票交易规则 股票交易系统
亿万物流公司ERP系统编码规则
亿万物流公司ERP系统编码规则
[推荐]系统哲学引论
[推荐]系统哲学引论
Beyond Search-推荐系统
[推荐]系统哲学引论a
中国神怪系统-----郜毛德推荐
B2C之关联推荐:聚物,聚人--艾瑞网专家刘爽的博客专栏 - 艾瑞网
GTS全球外汇交易系统帐户规则说明 - Qzone日志
DSL:基于规则系统组织业务规则 (转载与 Anders小明的Blog )
人间方圆规则2
英语发音规则2