在机器学习的无监督问题中，常使用关联分析法来发现存在于大量数据集中的关联性或相关性。关联分析是从大量数据中发现项集之间的关联和相关联系，从而描述一个事物中某些属性同时出现的规律和模式。
关联分析的一个典型例子是超市购物分析，通过分析顾客购物车中的不同商品之间的联系、哪些商品会被频繁地同时购买，即“哪些商品经常被同时购买？”，来制定超市商品的营销策略等。经典的关联分析方法有Apriori算法和FP-growth算法。
目录
1、关联分析
2. Apriori算法
2.1 Apriori原理
2.2 使用Apriori算法来发现频繁集
2.3 Python代码实现
3. FP-growth
3.1 构建FP树
3.2 挖掘频繁项集
3.3 Python代码实现
1、关联分析
关联分析是指从大规模数据集中训练物品间的隐含关系，也称为关联规则学习。关联分析的目标包括发现以下两点：① 频繁项集 ② 关联规则
① 频繁项集：经常一起出现的物品集合
② 关联规则：暗示两种物品之间可能存在很强的关系
举一个例子：
| 交易号码 | 商品 |
| 1 | 豆奶，面包 |
| 2 | 面包，尿布，啤酒，甜菜 |
| 3 | 豆奶，尿布，啤酒，橙汁 |
| 4 | 面包，豆奶，尿布，啤酒 |
| 5 | 面包，豆奶，尿布，橙汁 |
- 频繁项集 (frequent item sets)：经常出现在一起的商品集合。
- 关联规则 (rule)：先决条件->结果。如上例中的{啤酒，尿布}，可以推断如果这名顾客买了尿布，那么也可能购买啤酒。
- 支持度 (support)：定义数据集中包含该项集的记录所占的比例。如上例中{豆奶}的支持度为，{豆奶，尿布}的支持度为。
- 可信度或置信度 (confidence)：针对关联规则定义的，X发生时Y也发生的概率，即条件概率。比如，规则{尿布}->{啤酒}的可信度为。意思是，{尿布，啤酒}的支持度为，{尿布}的支持度为，那么顾客买了尿布后可能会一起买啤酒的可信度为。
2. Apriori算法
Apriori算法是一个很经典的数据挖掘算法，很多算法都是基于Apriori产生的，如FP-Tree、GSP、CBA等。
2.1 Apriori原理
可以通过枚举法列出所有的可能子集，但当数据集很大时，枚举法并不是个高效的方法。如图1所示，对于一个有4个项（假设超市卖4种商品），那么共有15个项集。
为了提高寻找频繁项集的效率，那些不可能满足support阈值的项集会被减裁掉。
Apriori原理：如果一个项集是频繁的，那么它的子项集一定也是频繁的；如果一个项集不是频繁的，那么它的父项集也一定不是频繁的。
如图1中，项集{2,3}是非频繁的，那么可以得到其它非频繁的项集，如图2所示。
2.2 使用Apriori算法来发现频繁集
关联分析的目标包括两项：① 发现频繁项集 ② 发现关联规则。
首先需要找到频繁项集，然后根据频繁项集的支持度计算关联规则的可信度，以获得关联规则。
输入：最小支持度，数据集
返回：频繁项集列表
Apriori算法流程：
- 生成所有k=1个元素的项集列表
- 扫描数据集，查看哪些项集满足最小支持度要求，裁剪不满足最小支持度的项集。
- 对留下的项集进行组成，生成包含k+1个元素的项集
- 重复2~3
- 返回所有频繁项集的列表
2.3 Python代码实现
Github：Apriori算法的Python实现（包含中文注释）
3. FP-growth
FP-growth对Apriori算法进行了优化，提升了其效率。FP-growth全称为基于频繁模式树（Frequent Pattern Tree）。
在FP-growth算法执行过程中，只需遍历数据集2次，就能发现频繁模式，过程分为：①构建FP树；② 从FP树种挖掘频繁项集。
3.1 FP树FP-growth算法将数据存储在一种称为FP树的紧凑数据结构中，FP树通过链接（link）来连接相似元素。FP树存储项集的出现频率，每个项集以路径的方式存储在树中。相似项之间的link称为节点链接（node link），用于快速发现相似项的位置。
给定一个事务数据样例：
| 事务ID | 事务中的元素项 |
|---|---|
| 001 | r, z, h, j, p |
| 002 | z, y, x, w, v, u, t, s |
| 003 | z |
| 004 | r, x, n, o, s |
| 005 | y, r, x, z, q, t, p |
| 006 | y, z, x, e, q, s, t, m |
上表能够产生如图3所示的FP树。可以发现，对于项集{r,z}只出现了1次，而元素项z出现了5次。集合{t, s, y, x, z}出现了2次，集合{t, r, y, x, z}出现了1次，z本身单独出现1次。就像这样，FP树的解读方式是读取某个节点开始到根节点的路径。
路径上的元素构成一个频繁项集，开始节点的值表示这个项集的支持度。如项集{z}的支持度为5，项集{s,t,x,y,z}的支持度为2。
类似于Apriori算法，我们取一个最小支持度的阈值，如果出现次数小于阈值，那么该元素将被裁剪。 图3中将最小支持度设置为3，因此p、q、h等没有在FP树种出现。
FP-growth算法的工作流程为：
- 首先构建FP树，利用它来挖掘频繁项集。
- 在构建FP树时，对数据集扫描2遍。
- 第一遍对所有元素项的出现次数进行计数。
- 第二遍只考虑那些频繁元素。
3.2 构建FP树
| 事务ID | items |
|---|---|
| 1 | l1 l2 l5 |
| 2 | l2 l4 |
| 3 | l2 l3 |
| 4 | l1 l2 l4 |
| 5 | l1 l3 |
| 6 | l2 l3 |
| 7 | l1 l3 |
| 8 | l1 l2 l3 l5 |
| 9 | l1 l2 l3 |
1. 扫描数据集，对每个item进行计数
| l1 | l2 | l3 | l4 | l5 |
|---|---|---|---|---|
| 6 | 7 | 6 | 2 | 2 |
2. 设置最小支持度（即item最少出现的次数），设为2
3. 按降序重新排列item集（小于阈值的将被剪裁）
| l2 | l1 | l3 | l4 | l5 |
|---|---|---|---|---|
| 7 | 6 | 6 | 2 | 2 |
4. 根据item出现的次数重新调整事务列表
5. 依次根据事务ID构建FP树，累计出现频次
加入第一条事务：{l2, l1, l5}
加入第二条事务：{l2,l4}
依次加入其余事务，得到FP树：
3.3 挖掘频繁项集
条件模式基：是以所查找元素项为结尾的路径集合。每一条路径其实都是一条前缀路径。
在FP树的挖掘频率项集过程中，对于每一个元素项，需获取其对应的条件模式基。
例子1：挖掘 l5 的频繁项集（单路径树）
step1：根据上图，得到l5的条件模式基为 { (l2, l1), (l2, l1, l3) }。
step2：构造条件FP树（如下图右所示），这个FP树是单路径的。
step3：设定支持度大于2，和模式后缀 l5 取并集得到满足条件的所有模式：{ (l2, l5) : 2, (l1, l5) : 2, (l1, l2, l5) : 2 }
例子2：挖掘 l3 的频繁项集（多路径树）
step1：根据3.2中的图，得到l3的条件模式基为 { (l2, l1) : 2, (l2) : 2, (l1) : 2 }
step2：构造条件FP树（如下图右所示），这个FP树是多路径的。
step3：将 l3 与条件FP树的每一项（l1, l2）取并集，得到一组模式为 { (l2, l3) : 4, (l1, l3) : 4}
step4：step3中的模式不是后缀为 l3 的所有模式，递归调用FP-growth。对于 {l2, l3}，它的条件模式基为空；对于 {l1, l3}，它的条件模式基为 {l2: 2}，生成如下图下所示的条件FP树，这是一个单路径的条件FP树，与条件后缀 {l1, l3}取并得到模式 {l2, l1, l3 : 2}。
step5：设定支持度大于2，和模式后缀 l3 取并集得到满足条件的所有模式：{ (l2, l3) : 4, (l1, l3) : 4, (l1, l2, l3) : 2}
3.4 Python代码实现
Github：FP-growth的Python实现（包含中文注释）
参考资料：
《机器学习实战》
Apriori算法实现
使用Apriori算法和FP-growth算法进行关联分析
FP-growth算法理解和实现
