先验算法

apriori是一种基于交易数据库进行频繁项集挖掘和关联规则学习的算法。算法识别数据库中经常出现的频繁项，并将它们扩展为更大的频繁项集。由算法决定的频繁项目集可以用来确定关联规则，这些规则突出了数据库中的一般趋势:这在市场篮分析等领域中有应用。

apriori算法其核心是基于两阶段频集思想的递推算法。在这里，所有支持度大于最小支持度的项集称为频繁项集，简称频集。该算法的基本思想是：首先找出所有的频集，这些项集出现的频繁性至少和预定义的最小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小支持度和最小可信度。然后使用第1步找到的频集产生期望的规则，产生只包含集合的项的所有规则。一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。为了生成所有频集，使用了递归的方法。

[描述来源：Wikipedia；URL：https://en.wikipedia.org/wiki/Apriori_algorithm

百度百科；URL：https://baike.baidu.com/item/APRIORI/2000746?fr=aladdin]

关联规则最初提出的动机是针对购物篮分析(Market Basket Analysis)问题提出的。假设分店经理想更多的了解顾客的购物习惯。特别是，想知道哪些商品顾客可能会在一次购物时同时购买？为回答该问题，可以对商店的顾客事物零售数量进行购物篮分析。该过程通过发现顾客放入“购物篮”中的不同商品之间的关联，分析顾客的购物习惯。这种关联的发现可以帮助零售商了解哪些商品频繁的被顾客同时购买，从而帮助他们开发更好的营销策略。

关联规则算法最著名的应用是 "尿布与啤酒"。在美国的沃尔玛连锁超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：跟尿布一起购买最多的商品竟是啤酒！

关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(Frequent Itemsets)，第二阶段再由这些高频项目组中产生关联规则(Association Rules)。

就沃尔玛的案例而言，使用关联规则挖掘技术，对交易资料库中的纪录进行资料挖掘，首先必须要设定最小支持度（交易中同时出现啤酒和尿布的概率阈值）与最小信赖度（交易中已包含啤酒的情况下出现尿布的概率阈值）两个门槛值。符合此该超市需求的关联规则将必须同时满足以上两个条件。若经过挖掘过程所找到的关联规则「尿布，啤酒」，满足下列条件，将可接受「尿布，啤酒」的关联规则。

[描述来源：百度百科；URL：https://baike.baidu.com/item/%E5%85%B3%E8%81%94%E8%A7%84%E5%88%99/6319603?fr=aladdin]

发展历史

R. Agrawal 和 R. Srikant于1994年提出了Apriori算法。之后Apriori算法被多次改进。包括使用哈希映射、分区、采样和使用垂直数据格式等方法，来降低算法的复杂度。但这些仍然属于Apriori算法类，因为他们都有一个共同特征，即产生候选频繁项集。2000年，针对Apriori算法的固有缺陷，J. Han等提出了不产生候选挖掘频繁项集的方法：FP-growth (frequent pattern growth).实验表明，FP-growth对不同长度的规则都有很好的适应性，同时在效率上较之Apriori算法有巨大的提高。

主要事件

发展分析

瓶颈

Apriori算法有一些难以克服的缺点：

• 对数据库的扫描次数过多；
• 产生大量的中间项集；
• 采用唯一支持度；
• 算法的适应面窄

未来发展方向

如何通过减少数据库扫描次数、缩减候选项集等方法降低算法复杂度，是值得研究的问题。

Contributor: Han Hao