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 实现,非常值得一看。
分享到:
相关推荐
基于apriori关联规则的商品推荐系统.pdf 基于apriori关联规则的商品推荐系统.pdf 基于apriori关联规则的商品推荐系统.pdf 基于apriori关联规则的商品推荐系统.pdf 基于apriori关联规则的商品推荐系统.pdf 基于...
针对数字图书馆资源增加致使用户难以获取感兴趣图书资源的问题,提出了一种基于标签和关联规则挖掘的图书组合推荐系统模型。该模型整合了基于内容推荐和协同过滤推荐的优点,利用标签系统对图书内容进行语义分析,...
基于关联规则数据挖掘算法的推荐系统研究与实践.pdf
以数据挖掘中的关联规则理论为基础,从应用的角度出发,设计了一套相关产品推荐系统ARecom ,实 现了电子购物中的个性化服务。针对直接决定整体算法效率的频繁大项集生成步骤,应用大量的数据,研究比较 了三种典型算法,...
分布式系统下挖掘关联规则的两种方案.pdf 分布式系统下挖掘关联规则的两种方案.pdf
提出一种基于Ap rTidRec算法的分布式关联规则挖掘算法,并通过实验验证了算法运行的有效性。给出基于局部2 全局通信模式的分布式关联规则挖掘方案,并在此方案基础之上进行了系统实现。
Java基于ssm+mysql的基于关联规则的青岛市计算机类考研院校推荐系统的实现.zipJava基于ssm+mysql的基于关联规则的青岛市计算机类考研院校推荐系统的实现.zipJava基于ssm+mysql的基于关联规则的青岛市计算机类考研...
基于关联规则的青岛市计算机类考研院校推荐系统是一款针对准备参加研究生入学考试的学生设计的智能推荐平台。该系统采用SSM框架(Spring、Spring MVC、MyBatis)开发,并集成了关联规则挖掘算法,以帮助学生找到最...
python源码集锦-基于关联规则 Apriori 算法的智能推荐
采用北京市可变信息板(variable message signs, VMS)系统近三年发布的交通诱导信息数据, 研究了交通诱导信息发布策略的空间关联规则. 首先基于系统聚类算法分析事件...
本文根据高校选课管理的情况,将关联规则挖掘技术中的FP-tree算法运用于高校选课管理的指导系统,对选课系统所积累的教学信息进行分析与挖掘,为高校选修课程的开设及学生选课提供决策支持,指导高校选课制度健康发展,...
基于数据挖掘的飞机系统故障关联规则研究.pdf
关联规则的数据挖掘在高校图书馆系统中的应用
基于关联规则的漏洞信息数据挖掘系统设计.pdf
ssm基于关联规则的青岛市计算机类考研院校推荐系统 Java;SSM;MySQL; 系统功能设计 本系统包括用户和管理员两种使用权限,其中用户功能如下: (1)用户登录:用户可以进行登录。 (2)热门院校:用户可以进行...
推荐算法到推荐系统 别忙着开始,先弄懂: 什么是推荐系统 是否需要推荐系统 推荐系统是否有效 ... 系统是一群有关联的个体组成,根据预先编排好的规则工 作。 推荐算法到推荐系统
基于关联规则的计算机类考研院校推荐系统是一个旨在帮助计算机专业的学生选择适合自己的研究生院校的在线平台。该系统利用关联规则挖掘算法,分析历年的考研数据和相关因素,通过SSM(Spring+SpringMVC+MyBatis)...
本系统是基于关联规则的青岛市计算机类考研院校推荐系统,需要符合使用者的考研院校推荐需求,也要符合管理者的管理需求。因此本系统的功能需要包括用户的功能和管理员的功能。其中用户功能包括用户登录、热门院校、...
关联规则在高校智能排课系统中的应用.
计算机类毕业设计源码