如果这篇文章对你有一点小小的帮助，请给个关注，点个赞喔，我会非常开心的~

0. 前言

关联分析：从大规模的数据集中，寻找不同特征或者物品之间的隐含关系。

关联分析通常由两步组成，从数据中寻找频繁项集，然后从频繁项集中挖掘关联规则。

给出以下例子：

交易号码	商品
0	豆奶、莴苣
1	莴苣、尿布、葡萄酒、甜菜
2	豆奶、尿布、葡萄酒、橙汁
3	莴苣、豆奶、尿布、葡萄酒
4	莴苣、豆奶、尿布、橙汁

• 频繁项集：经常出现在一块的物品的集合，例如｛豆奶、尿布｝
• 关联规则：暗示两种物品之间可能存在很强的关系，例如由｛尿布｝可以推断出可能含有｛葡萄酒｝
• 支持度：定义为数据集中包含该项集的记录所占的比例，例如｛豆奶、尿布｝支持度为$\frac{3}{5}$53​，用最小支持度划分频繁项集
• 置信度：针对一条关联规则$P\rightarrow H$P→H，P称为前件，H称为后件，置信度定义为$\frac{support(PH)}{support(P)}$support(P)support(PH)​，例如尿布$\rightarrow$→葡萄酒的置信度为$\frac{3}{4}$43​，用最小置信度划分关联规则

1. Apriori算法

1.1. 寻找频繁项集

例如一个数据集中，共有4种物品，则可能组成的频繁项集，如下图所示（图源：机器学习实战）：

如果某个项是频繁的，那么这个项的所有子集也是频繁的。

逆否命题：如果某个项是非频繁的，那么这个项的所有超集也是非频繁的。例如，如果$\{23\}${23}是非频繁的，那么$\{023\}\ \{123\}\ \{0123\}${023} {123} {0123}都是非频繁的，可以降低计算量。

Apriori算法寻找频繁项集的流程：

1. 生成只包含单个物品的集合$C_1$C1​
2. 去掉不满足最小支持度的项，剩余的项组成集合$L_1$L1​，将满足的项加入频繁项集
3. 从$L_1$L1​中进行组合，生成项长度为2的集合$C_2$C2​
4. 去掉不满足最小支持度的项，剩余的项组成集合$L_2$L2​，将满足的项加入频繁项集
5. 从$L_2$L2​中进行组合，生成项长度为3的集合$C_3$C3​
6. 如此循环迭代，直到只有一个项集无法进行组合，或者没有满足最小支持度的项集为止

1.2. 挖掘关联规则

对于每一个频繁项，都可挖掘出许多对关联规则，例如$\{0123\}${0123}，如下图所示（图源：机器学习实战）：

如果某条规则不满足最小可信度的要求，则该规则的子集都不满足最小可信度的要求，即包含该后件的规则，都不满足最小可信度要求。例如规则$\{012\}\rightarrow \{3\}${012}→{3}不满足最小可信度，则后件中包含$\{3\}${3}的均不满足最小可信度要求，可以降低计算量。

Apriori算法挖掘关联规则的流程：

1. 遍历频繁项集中所有频繁项
2. 对于每一个频繁项，创建一个后件只包含1个元素的规则列表
3. 去掉不满足最小可信度的规则，记录满足规则的后件
4. 从满足规则的后件中进行组合，组成后件包含2个元素的规则列表
5. 去掉不满足最小可信度的规则，记录满足规则的后件
6. 从满足规则的后件中进行组合，组成后件包含3个元素的规则列表
7. 如此迭代循环，直到前件只包含1个元素，或者没有满足最小可信度的后件为止

2. FP-growth算法

在Apriori算法中，寻找频繁项集，需要对每一个可能的频繁项扫描一遍数据集计算支持度，计算量庞大。

在FP-growth算法中，寻找频繁项集，只需要扫描两遍数据集，将数据存储在FP树的结构上，然后在FP树上挖掘频繁项集。

给出如下例子：

事务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

FP树如下图所示（图源：机器学习实战）：

• FP：代表频繁模式（Frequent Pattern），一个元素项可以在一颗FP树上出现多次
• 树上每个节点：表示当前路径出现的次数，例如｛z:5｝表示元素｛z｝在数据集中出现了5次；｛y:3｝表示路径｛y, x, z｝在数据集中出现了3次
• 头指针表：给出了每个元素在数据集中出现的次数。部分元素因为不满足最小支持度的要求，所以不储存在FP树中

在FP-growth算法中，同样采用了Apriori算法的思想，如果某个项是非频繁的，那么这个项的所有超集也是非频繁的。

2.1. 构建FP树

构建FP树的过程：

1. 计算每个单个元素的频率，并根据最小支持度，滤除不满足的元素
2. 对数据集进行处理，按照元素的绝对出现频率排序，滤除不满足最小支持度的元素
3. 遍历数据集，从根节点开始递归添加路径，存在则将数值增加，不存在则创建新的节点

例如根据上述的头指针表，元素排序为｛z:5, x:4, y:3, s:3, r:3, t:3｝，所以处理后的数据为：

事务ID	事务中的元素项	过滤及排序后的元素
001	r, z, h, j, p	z, r
002	z, y, x, w, v, u, t, s	z, x, y, s, t
003	z	z
004	r, x, n, o, s	x, s, r
005	y, r, x, z, q, t, p	z, x, y, r, t
006	y, z, x, e, q, s, t, m	z, x, y, s, t

例如下图所示（图源：机器学习实战），对于第一条数据，根节点不存在子节点{z}，所以创建新的子节点{z}，递归节点{z}，因不存在子节点{r}，所以创建新的子节点{r}，对于第二条数据，根节点存在子节点{z}，所以数值增加，递归节点{z}，因不存在子节点{x}，所以创建新的子节点{x}，递归节点{x}…。

2.2. 寻找频繁项集

• 条件模式基（conditional pattern base）：这个元素所有前缀路径（prefix path）的集合
• 前缀路径（prefix path）：当前元素到根节点之间的路径（不包括当前元素和根节点）

利用FP树寻找频繁项集的过程：

1. 对于头指针表中的每一个元素，获取其条件模式基（所有前缀路径的集合）
2. 将条件模式基中每一条前缀路径作为一条数据，构建新数据集，在这个数据集上构建条件FP树
3. 取头指针表中的每一个元素，与上一轮递归的频繁项集构成新的频繁项集（上一轮的FP树头指针表单个元素一定满足最小支持度，这轮FP树头指针表单个元素也一定满足最小支持度，这轮FP树的数据是由上轮单个元素的前缀路径组成，所以这两个满足最小支持度的元素在原始数据集中一定有满足最小支持度的组合）
4. 继续对于条件FP树的头指针表中的每一个元素，获取其条件模式基，构建条件FP树
5. 如此递归过程，直到无法构建出FP树为止

举个例子：首先构建了一棵FP树，此时FP树中的单个元素均满足最小支持度（假设有{a}, {b}, {c}, {d}, {e}5个元素），遍历其中的每一个元素（假设此时遍历{a}），先将元素{a}加入总的频繁项集（能构建FP树，说明单个元素满足最小支持度），再寻找条件模式基，根据这些前缀路径递归构建一棵条件FP树（假设条件FP树中有{b}, {c}, {d}3个元素，{e}不满足最小支持度）复制上一层递归的频繁项集{a}，将当前遍历元素{b}加入复制的频繁项集中构成{a, b}，然后再将{a, b}加入总的频繁项集（因为{a}{b}均能构建FP树，且{b}的FP树是由{a}的前缀路径作为数据，所以{a,b}也一定满足最小支持度）继续递归遍历头指针表中每一个元素的条件模式基，构建条件FP树，此时复制的频繁项集为{a,b}…。

---

如果这篇文章对你有一点小小的帮助，请给个关注，点个赞喔，我会非常开心的~