在平时我们逛超市或是商场时都会有意无意发现物品的摆放似乎存在着某些关联关系的（商品摆放原理），经典的案例就是在数据挖掘常被提及的“尿布与啤酒”现象。注意是“尿布”在前哦。
这种现象的存在其实就是我们机器学习里所提到的关联分析（association analysis），即从大规模数据中寻找物品间的隐含的关系。本文将介绍在关联分析中较为经典的Apriori算法。
Apriori算法
Apriori：先验的; <拉>由原因推及结果的; 演绎的; 推测的;
1. 关联分析
关联分析是一种在大规模数据集中寻找物品间是否存在某种关系的任务，在这过程中主要通过构建频繁项集（frequent item sets）和关联规则（association rules）来完成。
频繁项集：常出现在一起的物品集合
关联规则：物品间可能存在某种强联
问题来了，我们是要如何通过这些频繁项集发现物品间的关联性呢？
| 交易号 | 商品 |
|---|---|
| 0 | 豆奶，草莓 |
| 1 | 草莓，尿布，啤酒，辣椒酱 |
| 2 | 豆奶，黄瓜，尿布，饼干 |
| 3 | 豆奶，尿布，啤酒，饼干 |
| 4 | 黄瓜，啤酒，尿布 |
可以通过支持度（support）和可信度（置信度confidence）来定义。一个项集的支持度指的是数据集中包含该项集记录所占的比例，上例中{豆奶}的支持度是2/5,{啤酒，尿布}的支持度是3/5；可信度是针对于像{尿布}->{啤酒}这样的关联规则来定义的，定义为：支持度({尿布，啤酒})/支持度（尿布）
于是问题又来了，当在计算一个频繁项集的支持度时，通常需要遍历所有的商品列表求得，对于列表数目较少的情况该方法无疑是没问题的，但当列表数目成千上万时，计算量过大，这种方法势必是不可取的。
Apriori来了！
2. Apriori算法
Apriori原理是说如果某个项集是频繁的，那么它的所有子集势必也是频繁的。也可以这样来理解，如果一个项集是非频繁项集，那么它所对应的超集就全都是非频繁项集。
这样在确定了一个项集是非频繁项集了之后，它所对应的超集的支持度我们就可以不去计算了，这在很大程度上避免了项集数目的指数增长，可以更加合理的计算频繁项集。
Apriori算法来发现频繁项集
Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先生成所有单个物品的项集列表，遍历之后去掉不满足最小支持度要求的项集；接下来对剩下的集合进行组合生成包含两个元素的项集，去掉不满足最小支持度的项集；重复该过程直到去掉所有不满足最小支持度的项集。
从频繁项集中挖掘关联规则
频繁项集可以使用Apriori算法寻找，当然下来就是要找出关联规则了。我们知道，假设有一个频繁项集，它们之间就有可能有一条关联规则，即可以表示为："...—>..."，但反过来并不一定成立（其中箭头左边对应的集合为前件，箭头右边对应的集合为后件）。
寻找关联规则的思想是：从一个频繁项集开始，创建一个规则列表，首先将规则的右边限定为一个元素，对这些规则进行测试，接下来合并剩下的规则来创建一个新的规则列表，规则的右边限定为两个元素，就这样一步一步实现。
Apriori算法缺点
每次增加频繁项集的大小，Apriori算法都会重新扫描整个数据集。当数据集很大时，这会显著降低频繁项集发现的速度。
其他算法
FP-growth算法，和Apriori算法相比，该算法只需要对数据库进行两次遍历，能够显著加快发现频繁项集的速度。（本文不对此算法进行介绍，请读者自行查阅）。
