关联规则是反映一个事物与其他事物之间的相互依存性和关联性，如果两个或多个事物之间存在一定的关联关系，那么，其中一个事物就能通过其他事物预测到。关联规则是数据挖掘的一个重要技术，用于从大量数据中挖掘出有价值的数据项之间的相关关系。
关联规则挖掘的最经典案例就是沃尔玛的啤酒与尿布的故事，通过对超市购物小票进行分析，发现顾客买尿布时会顺便购买啤酒，超市就把尿布和啤酒放在一起销售增加销售额。关联分析的使用场景非常广泛，除了超市购物这一典型场景，电影分类也可进行关联分析，每部电影的分类可以看做一个购物小票（Transaction），进而可以挖掘电影种类中的关联规则。
关联规则与协同过滤都是基于大众的行为数据展开分析，两者的区别在于关联规则是基于当前一次的购买/点击，即当下的需求；协同过滤是基于用户历史的行为进行分析，建立一定时间内的偏好排序，即长期偏好。两种推荐算法的思考维度不同，很多时候，我们需要把多种推荐方法的结果综合起来做一个混合的推荐。
基本概念
-
支持度：指的是某个商品组合出现的次数与总次数之间的比例
-
置信度：指的是当你购买了商品A，会有多大的概率购买商品B（条件概念）
-
提升度：商品A的出现，对商品B的出现概率提升的程度，提升度(A→B)=置信度(A→B)/支持度(B)
Apriori算法
频繁项集：支持度大于等于最小支持度(Min Support)阈值的项集
非频繁项集：支持度小于最小支持度的项集
Apriori算法流程：
-
Step1，K=1，计算K项集的支持度；
-
Step2，筛选掉小于最小支持度的项集；
-
Step3，如果项集为空，则对应K-1项集的结果为最终结果；否则K=K+1，重复1-3步。
下表中用ID来代表商品，ID1-6分别代表牛奶、面包、尿布、可乐、啤酒、鸡蛋。
利用Apriori算法查找频繁项集(frequent itemset)的过程如下：
先计算K=1项的支持度
假设最小支持度=0.5，那么Item4和6不符合最小支持度的，不属于频繁项集
在这个基础上，我们将商品两两组合，得到k=2项的支持度
筛选掉小于最小值支持度的商品组合
将商品进行K=3项的商品组合，可以得到：
筛选掉小于最小值支持度的商品组合
得到K=3项的频繁项集{1,2,3}，也就是{牛奶、面包、尿布}的组合。
FPGrowth算法
Apriori在计算的过程中存在一些不足。一是可能产生大量的候选集，因为采用排列组合的方式，把可能的项集都组合出来了；二是每次计算都需要重新扫描数据集，计算每个项集的支持度，浪费了计算空间和时间。
为解决上述问题，在Apriori算法基础上提出了FP-Growth算法：
-
创建了一棵FP树来存储频繁项集，在创建前对不满足最小支持度的项进行删除，减少了存储空间
-
整个生成过程只需遍历数据集2次，大大减少了计算量
下表是由一些超市购物记录构成，我们来看如何利用FPGrowth算法挖掘频繁项集。
首先创建项头表，目的是为FP构建及频繁项集挖掘提供索引。项头表包括了项目、支持度，以及该项在FP树中的链表，初始的时候链表为空。
Step1：流程是先扫描一遍数据集，对于满足最小支持度的单个项（K=1项集）按照支持度从高到低进行排序，这个过程中删除了不满足最小支持度的项。
Step2：对于每一条购买记录，按照项头表的顺序进行排序，并进行过滤。
Step3：构造FP树，根节点记为NULL节点。整个流程是需要再次扫描数据集，把Step2得到的记录逐条插入到FP树中。节点如果存在就将计数count+1，如果不存在就进行创建。同时在创建的过程中，需要更新项头表的链表。
Step4：通过FP树挖掘频繁项集
- 现在已经得到了一个存储频繁项集的FP树，以及一个项头表。可以通过项头表来挖掘出每个频繁项集。
- 挖掘从项头表最后一项“啤酒”开始。
- 从FP树种找到所有“啤酒”节点，向上遍历祖先节点，得到3条路径。对于每条路径上的节点，其count都设置为“啤酒”的count
- 具体的操作会用到一个概念，叫“条件模式基”
- 因为每项最后一个都是“啤酒”，因此我们把“啤酒”去掉，得到条件模式基，此时后缀模式是（啤酒）
假设{啤酒}的条件频繁集为{S1,S2,S3}，则{啤酒}的频繁集为{S1+{啤酒},S2+{啤酒},S3+{啤酒}}，此时的条件频繁项集为{$\emptyset$,{尿布}}，所以啤酒的频繁项集为{啤酒}，{尿布，啤酒}
继续找项头表倒数第2项面包，求得“面包”的条件模式基。根据条件模式基，可以求得面包的频繁项集：{面包}，{尿布，面包}，{牛奶，面包}，{尿布，牛奶，面包}
继续找项头表倒数第3项牛奶，求得“牛奶”的条件模式基。根据条件模式基，可以求得牛奶的频繁项集：{牛奶}，{尿布，牛奶}
继续找项头表倒数第4项尿布，求得“尿布”的条件模式基。根据条件模式基，可以求得尿布的频繁项集：{尿布}
所以全部的频繁项集为：{啤酒}，{尿布，啤酒}，{面包}，{尿布，面包}，{牛奶，面包}，{尿布，牛奶，面包}，{牛奶}，{尿布，牛奶}，{尿布}.
实例：MarketBasket数据集购物篮分析、词云展示
- MarketBasket数据集：Market_Basket_Optimisation.csv（该文件由超市购物订单数据构成）。
- 采用Apriori算法进行频繁项集及关联规则挖掘，并针对MarketBasket数据集进行词云展示，探索TOP10的商品有哪些。
