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 实现,非常值得一看。
分享到:
相关推荐
人工智能和机器学习之关联规则学习算法:R-Apriori算法:关联规则在推荐系统中的应用.docx
人工智能和机器学习之关联规则学习算法:Multi-Level Association:关联规则在推荐系统中的应用.docx
基于关联规则的推荐系统的目标是在特定情境下提高推荐的有效性。比如,当用户将A(例如尿布)添加到购物车时,推荐系统将B(例如啤酒)作为附加商品推荐给用户,这样往往能比单纯推荐B获得更好的效果。 #### 二、...
关联规则学习广泛应用于零售业、市场篮子分析、推荐系统等多个领域,例如在零售业中,通过关联规则学习可以发现哪些商品经常一起被购买,从而优化商品布局或制定更精准的推荐策略。关联规则学习主要关注三个核心指标...
关联规则学习在零售业、市场篮子分析和推荐系统等领域具有广泛的应用。通过分析顾客的购物篮,企业可以发现哪些商品经常一起被购买,从而帮助企业制定更有效的营销策略和提高销售业绩。 关联规则学习的几个基本概念...
这种技术在市场篮子分析、推荐系统、生物信息学等多个领域发挥着至关重要的作用。传统的关联规则学习主要基于事务数据,它通过分析不同商品在同一交易中的出现频率,来发现顾客购买行为的潜在模式,如“购买尿布的...
关联规则挖掘算法是数据挖掘领域的重要技术之一,它主要用于发现不同项之间存在的有趣关系,通常用于市场篮子分析、库存管理、推荐系统等多个领域。在推荐系统的背景下,关联规则挖掘算法能够揭示用户购买或选择行为...
在零售业、市场篮子分析和推荐系统等领域中,关联规则学习的应用十分广泛。关联规则通常以“如果 A 发生,则 B 很可能发生”的形式出现,其中 A 和 B 是数据集中的不同项。在零售业中,关联规则学习能够分析顾客的...
关联规则学习广泛应用于市场篮子分析、推荐系统、生物信息学等多个领域,是揭示数据中潜在规律的有力工具。 FP-Growth算法,即Frequent Pattern Growth算法,是在2000年由Jiawei Han等人提出的,旨在克服Apriori...
人工智能和机器学习之关联规则学习算法:Graph-Based Association:图关联规则在推荐系统中的应用.docx
10. 关联规则挖掘的应用:关联规则挖掘有广泛的应用,如推荐系统、市场营销、客户关系管理等。 11. 数据挖掘:数据挖掘是指从大量数据中发现有价值的知识或模式的过程。关联规则挖掘是数据挖掘的一种重要技术。 12...
5. 智能推荐:结合关联规则,我们可以构建一个简单的推荐系统。当用户购买了某个商品时,系统可以基于已发现的关联规则推荐其他可能感兴趣的商品。 6. 示例和测试:压缩包可能还包括一些示例数据和测试用例,以验证...
关联规则学习是一种在数据挖掘中发现变量间有趣关系的方法,尤其适用于市场篮子分析、推荐系统和生物信息学等领域。关联规则的核心是发现大量数据中物品间的关联或共现模式,这些模式可以揭示市场趋势、用户偏好或...
《毕业设计:关联规则与决策树组合算法在学生成绩分析中的研究》 在这个毕业设计项目中,我们探讨了如何运用关联规则和决策树这两种数据分析技术来深入理解并预测学生的学习成绩。这两种算法在数据挖掘领域有着广泛...
在这个“数据挖掘关联规则分析数据集”中,我们有两个合成的数据集,它们旨在帮助研究者和分析师探索不同项目之间的潜在关联,从而可能为业务决策、市场篮子分析或商品推荐系统提供依据。 关联规则通常由两部分组成...
关联规则挖掘是数据挖掘领域中的一个关键方法,用于发现大量数据集中的有趣关系。Apriori算法是关联规则挖掘中最经典、最广泛使用的算法之一,由Rakesh Agrawal和Ramakrishnan Srikant在1994年提出。这个算法主要...
关联规则是一种在大型数据库中发现有价值模式的统计方法,它主要应用于市场篮子分析、推荐系统和模式识别等领域。在C++中实现关联规则通常涉及数据预处理、Apriori算法或FP-Growth算法等核心步骤。下面我们将深入...
人工智能和机器学习之关联规则学习算法:QuantitativeAssociation:8.关联规则在推荐系统中的应用.docx