欢迎在文章下方评论，建议用电脑看
先讲一个著名的“啤酒与尿布”的故事，它就是来自对购物单的关联分析！
“啤酒与尿布”的故事产生于20世纪90年代的美国沃尔玛超市中，沃尔玛的超市管理人员分析销售数据时发现了一个令人难于理解的现象：在某些特定的情况下，“啤酒”与“尿布”两件看上去毫无关系的商品会经常出现在同一个购物篮中，这种独特的销售现象引起了管理人员的注意，经过后续调查发现，这种现象出现在年轻的父亲身上。
关联分析有两种形式：频繁项集、关联规则。频繁项集（frequent item sets）是经常出现在一块的物品的集合，关联规则（association rules）暗示两种物品之间可能存在很强的关系。使用频繁项集和关联规则，商家可以更好地理解他们的顾客。
支持度: 关联规则A->B的支持度support=P(AB)，指的是事件A和事件B同时发生的概率。
置信度: 置信度confidence=P(B|A)=P(AB)/P(A),指的是发生事件A的基础上发生事件B的概率。比如说在规则Computer => antivirus_software , 其中 support=2%, confidence=60%中，就表示的意思是所有的商品交易中有2%的顾客同时买了电脑和杀毒软件，并且购买电脑的顾客中有60%也购买了杀毒软件。
k项集: 如果事件A中包含k个元素，那么称这个事件A为k项集，并且事件A满足最小支持度阈值的事件称为频繁k项集。
由频繁项集产生强关联规则 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同时包含网球拍和网球，支持度support= 3/6 = 0.5，置信度confident= 3/5 = 0.6。若给定最小支持度 a =0.5，最小置信度 \beta =0.6，关联规则网球拍 => 网球是有趣的，认为购买网球拍和购买网球之间存在强关联。
Apriori 算法是一种最有影响力的挖掘布尔关联规则的频繁项集的 算法，它是由Rakesh Agrawal 和RamakrishnanSkrikant 提出的。它使用一种称作逐层搜索的迭代方法，k- 项集用于探索（k+1）- 项集。首先，找出频繁 1- 项集的集合。该集合记作L1。L1 用于找频繁2- 项集的集合 L2，而L2 用于找L2，如此下去，直到不能找到 k- 项集。每找一个 Lk 需要一次数据库扫描。然而，这样遍历就太慢了，所以为提高频繁项集逐层产生的效率，一种称作Apriori 性质的重 要性质 用于压缩搜索空间。其运行定理在于一是频繁项集的所有非空子集都必须也是频繁的，二是非频繁项集的所有父集都是非频繁的。
Apriori算法过程分为两个步骤：
第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；
第二步利用频繁项集构造出满足用户最小信任度的规则。
具体做法就是：
首先找出频繁1-项集，记为L1；然后利用L1来产生候选项集C2，对C2中的项进行判定挖掘出L2，即频繁2-项集；不断如此循环下去直到无法发现更多的频繁k-项集为止。每挖掘一层Lk就需要扫描整个数据库一遍。算法利用了一个性质：
Apriori 性质：任一频繁项集的所有非空子集也必须是频繁的。意思就是说，生成一个k-itemset的候选项时，如果这个候选项有子集不在(k-1)-itemset(已经确定是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[2]=l2[2])&&……..&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])，那认为l1和l2是可连接。连接l1和l2 产生的结果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。
2） 剪枝步
CK是LK的超集，也就是说，CK的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。
不懂，用图说话！：
上图显示了4种商品所有可能的组合。对给定的集合项集{0,3}，需要遍历每条记录并检查是否同时包含0和3,扫描完后除以记录总数即可得支持度。对于包含N种物品的数据集共有2的N次方-1种项集组合，即使100种，也会有1.26×10的30次方种可能的项集组成。 为降低计算时间，可用Apriori原理：如果某个项集是频繁的，那么它的所有子集也是频繁的。逆反：如果一个项集是非频繁集，那么它的所有超集也是非频繁的。
恩，应该比较好理解了，其实这个算法也不算难的了，挺简单的！但为了写机器学习博文的宗旨——用最简单的方式去理解一切！下面再来一个更简单直观的例子吧!
下面以图例的方式说明该算法的运行过程： 假设有一个数据库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：
算法终止。
从算法的运行过程，我们可以看出该Apriori算法的优点：简单、易理解、数据要求低，然而我们也可以看到Apriori算法的缺点：
(1)在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;
(2)每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。
(3)针对Apriori算法的性能瓶颈问题-需要产生大量候选项集和需要重复地扫描数据库，2000年Jiawei Han等人提出了基于FP树生成频繁项集的FP-growth算法。该算法只进行2次数据库扫描且它不使用侯选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。研究表明它比Apriori算法大约快一个数量级。
我自己用《机器学习实战》上面的数据做过实战，实践证明，只用来查找频繁集项的话，那FP-growth算法真的不是比Apriori算法快那么一点，而是真的快很多！！
改进：怎么说呢，如果非要用Apriori的话，那就用来查找关联规则把，如果只要查找频繁集，虽然网上有一大推的改进方式，但我认识最简便的方式就是直接换模型啦，换模型之前，看下看一篇FP-growth算法（滑稽）
参考资料：
《统计学习方法》-李航
《机器学习》-周志华
《机器学习实战》-Peter Harrington
斯坦福大学公开课-机器学习
网上的各位大牛的博文
