一、Apriori 算法概述
Apriori算法是一种挖掘最具影响力的布尔关联规则频繁项集的算法，由Rakesh Agrawal和RamakrishnanSkrikant提出。 它使用一种称为分层搜索的迭代方法，其中k-项集用于搜索[k1]-项集。 首先，找到频繁的1-项集的集合。 将该集合记为L1。 L1用于查找频繁的二元集合的集合L2，L2用于查找L2。 这样一直持续到找不到k项集合为止。 每次找Lk都需要进行数据库扫描。 为了提高分层生成频繁项集的效率，使用一个称为Apriori属性的重要属性来压缩搜索空间。 其执行定理一是频繁项集合的所有非空子集都必须频繁，二是非频繁项集合的所有父集合都是非频繁的。
二、问题的引入
购物车分析：诱发性范例
Question :哪一组商品在一次购物中可能同时购买？
相关分析
解决方案：
1 )总是同时购买的商品放在附近，可以进一步刺激这些商品一起销售。
2 )为了刺激主体商品的捆绑销售，计划哪些附属商品可以降价销售。
三、关联分析的基本概念
1、支持度
关联规则A-B的支持度support=p(ab )是指事件a和事件b同时发生的概率。
2、可靠性
可靠性confidence=p(b|a )=p (ab )/p (a ) )是指在事件a发生的基础上事件b发生的概率。 例如，在规则Computer=antivirus_software，其中support=2%，confidence=60%中，所有商品交易中2%的顾客同时购买电脑和杀毒软件
3、k项集
在事件a中包含k个要素的情况下，将该事件a称为k项集，将事件a满足最小支持度阈值的事件称为频繁出现k项集。
4、从频繁项集中生成强关联规则
1 ) k维数据项集LK是频繁出现项集的必要条件是其所有K-1维子集也是频繁出现项集，表示为LK-1
2 )如果k维数据项集LK的任意K-1维子集Lk-1不是频繁的项集，则k维数据项集LK本身也不是最大数据项集。
3 ) Lk是k维频繁出现项集合，如果所有K-1维频繁出现项集合LK-1中包含Lk的K-1维子集合的数目小于k，则Lk不是k维最频繁出现项集合。
4 )同时满足最小支持度阈值和最小可靠度阈值的规则称为强规则。
例如，用简单的例子说明。 表1是顾客购买记录的数据库d，包含6个事务。 项集I={网球拍、网球、运动鞋、羽毛球}。 考虑关联规则：网球拍网球，事务1、2、3、4、6包括网球拍，事务1、2、6包括网球拍和网球、支持度、可靠性。 给定最小支持度、最小可靠度，相关规则网球拍的网球很有趣。 网球拍的购买和网球拍的购买之间被认为有很强的关联。
四、Apriori算法的基本思想：
Apriori算法的过程分为两个步骤。
第一步，通过迭代获取事务数据库中的所有频繁项集，即支持度等于或大于用户设置的阈值的项集
步骤2使用频繁的项集构建满足用户最小信任度的规则。
具体做法是：
首先找到频繁的1-项集，记为L1； 接着，使用L1生成候选集合C2，确定C2中的项并挖掘L2，即频繁地挖掘2-项集合； 一直这样循环下去，直到找不到更频繁的k-项集。 每次挖一楼的Lk都需要扫描整个数据库。 算法利用了一个性质：
Apriori 性质:任何频繁项集的所有非空子集也必须频繁。 也就是说，生成k-itemset候选时，如果该候选的子集不在[ k-1 ]-items et (确定为frequent ) )中，则不拿走该候选，也不判断支持度，直接删除该候选具体来说：
1 )连接步骤
为了找到Lk (所有频繁出现k项集的集合)，通过将Lk-1 (所有频繁出现k-1项集的集合)连接到自身生成k项集候选的集合。 候选集合记为Ck。 以l1和l2为Lk-1的成员。 li[j]表示li的第j项。 假设Apriori算法按词典顺序对事务或项集中的项进行排序。 也就是说，对于[k-1]项目集li，li[1]li[2]……….li[k-1]。 将Lk-1连接到自身，(l1(1)=l2(1) ) (l1 )=L2 ) )……(l1 ) K-2 ) ) K-2 ) ) L1 )连接K-1 l1和L2的结果是
2 )剪枝步骤
CK是LK的一个超集。 也就是说，CK的成员可能不频繁。 扫描所有事务(交易)，为每个候选CK确定计数，确定是否小于最小支持度计数，否则，认为候选频繁。 为了压缩Ck，可以利用Apriori的性质：利用任何频繁项集的
所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。五、实例说明
实例一：下面以图例的方式说明该算法的运行过程： 假设有一个数据库D，其中有4个事务记录，分别表示为：
这里预定最小支持度minSupport=2,下面用图例说明算法运行的过程：
1、扫描D，对每个候选项进行支持度计数得到表C1:
2、比较候选项支持度计数与最小支持度minSupport，产生1维最大项目集L1：
3、由L1产生候选项集C2：
4、扫描D，对每个候选项集进行支持度计数:
5、比较候选项支持度计数与最小支持度minSupport，产生2维最大项目集L2：
6、由L2产生候选项集C3：
7、比较候选项支持度计数与最小支持度minSupport，产生3维最大项目集L3：
算法终止。
实例二：下图从整体同样的能说明此过程：
此例的分析如下：
1 . 连接： C3=L2 L2 = {{A,C},{B,C},{B,E}{C,E}} {{A,C},{B,C},{B,E}{C,E}} = {{A,B,C},{A,C,E},{B,C,E}} 2．使用Apriori性质剪枝： 频繁项集的所有子集必须是频繁的，对候选项 C 3 ，我们可以删除其子集为非频繁的选项： {A,B,C} 的 2 项子集是 {A,B},{A,C},{B,C} ，其中 {A,B} 不是 L2 的元素，所以删除这个选项； {A,C,E} 的 2 项子集是 {A,C},{A,E},{C,E} ，其中 {A,E} 不是 L2 的元素，所以删除这个选项； {B,C,E} 的 2 项子集是 {B,C},{B,E},{C,E} ，它的所有 2 －项子集都是 L2 的元素，因此保留这个选项。 3． 这样，剪枝后得到 C3={{B,C,E}}
PS
从算法的运行过程，我们可以看出该Apriori算法的优点：简单、易理解、数据要求低，然而我们也可以看到Apriori算法的缺点：
(1)在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;
(2)每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。
六、改进Apriori算法的方法
方法1：基于hash表的项集计数
将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。
方法2：事务压缩（压缩进一步迭代的事务数）
不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除
方法3：划分
挖掘频繁项集只需要两次数据扫描
D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。
第一次扫描：将数据划分为多个部分并找到局部频繁项集
第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集。
方法4：选样（在给定数据的一个子集挖掘）
基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式
通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式
可以通过一次全局扫描来验证从样本中发现的模式
可以通过第二此全局扫描来找到遗漏的模式
方法5：动态项集计数
在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。
PS：Apriori算法的优化思路
1、在逐层搜索循环过程的第k步中，根据k-1步生成的k-1维频繁项目集来产生k维候选项目集，由于在产生k-1维频繁项目集时，我们可以实现对该集中出现元素的个数进行计数处理，因此对某元素而言，若它的计数个数不到k-1的话，可以事先删除该元素，从而排除由该元素将引起的大规格所有组合。
这是因为对某一个元素要成为K维项目集的一元素的话，该元素在k-1阶频繁项目集中的计数次数必须达到K-1个，否则不可能生成K维项目集(性质3)。
2、根据以上思路得到了这个候选项目集后，可以对数据库D的每一个事务进行扫描，若该事务中至少含有候选项目集Ck中的一员则保留该项事务，否则把该事物记录与数据库末端没有作删除标记的事务记录对换，并对移到数据库末端的事务记录作删除标一记，整个数据库扫描完毕后为新的事务数据库D’ 中。
因此随着K 的增大，D’中事务记录量大大地减少，对于下一次事务扫描可以大大节约I/0 开销。由于顾客一般可能一次只购买几件商品，因此这种虚拟删除的方法可以实现大量的交易记录在以后的挖掘中被剔除出来，在所剩余的不多的记录中再作更高维的数据挖掘是可以大大地节约时间的。
实例过程如下图：
当然还有很多相应的优化算法，比如针对Apriori算法的性能瓶颈问题-需要产生大量候选项集和需要重复地扫描数据库，2000年Jiawei Han等人提出了基于FP树生成频繁项集的FP-growth算法。该算法只进行2次数据库扫描且它不使用侯选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。研究表明它比Apriori算法大约快一个数量级。