一、简介
Apriori算法是第一个关联规则挖掘算法，也是最经典的算法。它利用逐层搜索的迭代方法找出数据库中项集的关系，以形成规则，其过程由连接（类矩阵运算）与剪枝（去掉那些没必要的中间结果）组成。该算法中项集的概念即为项的集合。包含K个项的集合为k项集。项集出现的频率是包含项集的事务数，称为项集的频率。如果某项集满足最小支持度，则称它为频繁项集。
还记得啤酒与尿布的故事吗？这是超市数据挖掘史上经常被拿出来说的事迹。用的便是关联分析。
全球零售业巨头沃尔玛在对消费者购物行为分析时发现，男性顾客在购买婴儿尿片时，常常会顺便搭配几瓶啤酒来犒劳自己，于是尝试推出了将啤酒和尿布摆在一起的促销手段。没想到这个举措居然使尿布和啤酒的销量都大幅增加了。
二、涉及到的概念
在了解关联分析的过程前，我们需要了解3个名词。支持度与置信度。
支持度（Support） 支持度可以理解为物品当前流行程度。计算方式是：支持度 = （包含物品A的记录数量） / （总的记录数量）
用上面的超市记录举例，一共有五个交易，牛奶出现在三个交易中，故而{牛奶}的支持度为3/5。{鸡蛋}的支持度是4/5。牛奶和鸡蛋同时出现的次数是2，故而{牛奶，鸡蛋}的支持度为2/5。
置信度（Confidence） 置信度是指如果购买物品A，有较大可能购买物品B。计算方式是这样：置信度( A -> B) = （包含物品A和B的记录数量） / （包含 A 的记录数量）
举例：我们已经知道，(牛奶，鸡蛋)一起购买的次数是两次，鸡蛋的购买次数是4次。那么Confidence(牛奶->鸡蛋)的计算方式是Confidence(牛奶->鸡蛋)=2 / 4。
提升度（Lift） 提升度指当销售一个物品时，另一个物品销售率会增加多少。计算方式是：提升度( A -> B) = 置信度( A -> B) / (支持度 A)
举例：上面我们计算了牛奶和鸡蛋的置信度Confidence(牛奶->鸡蛋)=2 / 4。牛奶的支持度Support(牛奶)=3 / 5，那么我们就能计算牛奶和鸡蛋的支持度Lift(牛奶->鸡蛋)=0.83
当提升度(A->B)的值大于1的时候，说明物品A卖得越多，B也会卖得越多。而提升度等于1则意味着产品A和B之间没有关联。最后，提升度小于1那么意味着购买A反而会减少B的销量。
其中支持度和Apriori相关，而置信度和提升度是寻找物品关联规则的时候会用到。
三、算法过程
Apriori的作用是根据物品间的支持度找出物品中的频繁项集。通过上面我们知道，支持度越高，说明物品越受欢迎。那么支持度怎么决定呢？这个是我们主观决定的，我们会给Apriori提供一个最小支持度参数，然后Apriori会返回比这个最小支持度高的那些频繁项集。
说到这里，有人可能会发现，既然都知道了支持度的计算公式，那直接遍历所有组合计算它们的支持度不就可以了吗？
是的，没错。确实可以通过遍历所有组合就能找出所有频繁项集。但问题是遍历所有组合花的时间太多，效率太低，假设有N个物品，那么一共需要计算2^N-1次。每增加一个物品，数量级是成指数增长。而Apriori就是一种找出频繁项集的高效算法。它的核心就是下面这句话：
某个项集是频繁的，那么它的所有子集也是频繁的。
这句话看起来是没什么用，但是反过来就很有用了。
如果一个项集是 非频繁项集，那么它的所有超集也是非频繁项集。
如图所示，我们发现{A,B}这个项集是非频繁的，那么{A,B}这个项集的超集，{A,B,C},{A,B,D}等等也都是非频繁的，这些就都可以忽略不去计算。运用Apriori算法的思想，我们就能去掉很多非频繁的项集，大大简化计算量。
那么具体的，Apriori算法是如何做到挖掘K项频繁集的呢？Apriori算法采用了迭代的方法，先搜索出候选1项集及对应的支持度，剪枝去掉低于支持度阙值的1项集，得到频繁1项集。
然后对剩下的频繁1项集进行连接，得到频繁2项集，筛选去掉低于支持度阙值的候选2项集，得到真正的频繁2项集。
以此类推，迭代下去，直到无法找到频繁k+1项集为止，对应的频繁k项集的集合即为算法的输出结果。
下面时是使用Aprioris算法获取频繁项集的一个简单的例子：
补充一个中文的例子：
如上过程，得出最大的是3项的频繁项集，无法再找出4项超过0.3的频繁项集了。接着根据源数据求出筛选的频繁项集的置信度。由于这个两个图是网上找的，没有源数据，按源数据和置信度的公式计算即可。
第一条数据的意思是客户在点了菜品a和b的概率是50%，点了菜品a，再点了b的概率是71.4286%
四、优缺点
1、优点
（1）简单、易理解、经典、运用了独特的挖掘算法，同时也是数据挖掘中最活跃的研究方法之一。很多算法都是基于apriori算法而产生的，包括FP-Tree、GSP、 CBA等。
2、缺点
（1）在每一步产生侯选项目集时循环产生的组合过多,没有排除 不应该参与组合的元素;
（2）每次计算项集的支持度时,都对数据库中的全部记录进行了一遍扫描比较,需要很大的I/O 负载。
