> For the complete documentation index, see [llms.txt](https://lang-yu.gitbook.io/mi-ai/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lang-yu.gitbook.io/mi-ai/ke-cheng-xi-lie/00.index/11.association.md).
# 11.关联规则
## 1. 基本概念
从交易数据库中找到频繁挖掘模式，做市场分析。两个指标：
* 支持度
* 置信度
### 1.1. 支持度/置信度
示例
| 交易编号 | 购买项 |
| ---- | ----- |
| 1000 | A,B,C |
| 2000 | A,C |
| 3000 | A,D |
| 4000 | B,E,F |
关联规则以交易为单位，每一个交易通常是一张发票，比如`1000`购买了三个项目，所以根据上述数据库：
* **Support** = Support({A,C}) = 50%
* **Confidence** = Support({A,C}) / Support({A}) = 66.6%，买A有三次，有两次是买了C的。
有时候又将关联规则称为**购物篮分析**，关联规则描述：
> Shirt -> Tie, Support = 13.5%, Confidence = 70%
如果一个用户买了Shirt，70%的情况都购买了Tie，而这种情况在所有交易中13.5%的情况会发生。上述交易数据库中，如果最小支持度和置信度设置为50%，则有：
* 关联规则 A -> C，\[50%, 66.6%]
* 关联规则 C -> A，\[50%, 100%]
> 大于阈值即可。
## 2. 关联规则
### 2.1. 算法
#### 2.1.1. Apriori算法
如果所有的项组合都测试一次，其数据量十分巨大，产品组合呈指数增长，所以无法**暴力分析**，如何在最快速度计算结果。
Apriori Principle：**任何频繁项集的子集也一定会被频繁购买**，参考下表：
| Frequent Itemset | Support |
| ---------------- | ------- |
| {A} | 75% |
| {B} | 50% |
| {C} | 50% |
| {A,C} | 50% |
> 最小支持度50%，最小置信度50%。
上述表格中，如果`{A,C}`满足条件，那么`{C}`一定会满足条件。步骤：
1. 找到频繁项集
2. 根据频繁项集生成关联规则
**示例（略）**
**另外一个**计算示例：
1. L3 = {abc, abd, acd, ace, bcd}
2. 构造L4：
1. abcd = {abc, abd}
2. acde = {acd, ace}
3. 移除 acde，因为 ade 并没出现在 L3中。
4. 留下L4 = {abcd}
频繁被购买的 k-1 的频繁项目集去产生候选的 k 的频繁项目集，最终会导致扫描数据库多次。所以**它的缺点**如：
* 产生的候选集太多，$$10^4$$的 1 项集会生成$$10^7$$个 2 项集，浪费记忆。
* 需要多次扫描数据库：产生长度为n长度的项目集，需要扫描`n + 1`次，浪费时间。
#### 2.1.2. FP-Growth
可以并行处理频繁项目集的产生：
FP-Growth的产生方式是从产品维度出发，参考上图两种算法的对比，上图中，`L1, L3, L4, L5`可以并行执行，而且这个算法最终只会扫描数据库一次。
**步骤**：
> 实际是扫描数据库两次。
1. 第一次扫描交易数据库，构造一个FP-Tree。
2. 然后在FP-Tree中做Trimming，去查找对应子树（排序得到精简的FP-Tree）。
3. 第二次扫描交易数据库，根据精简的FP-Tree执行计算（参考下图）。
上图是最后购买的FP-Tree的信息，每个节点有出现次数，接下来就可以计算频繁项目集了。
### 2.3. 评估指标
* Subjective Measures
* Objective Measures
第一个基本规则：最小支持度/最小置信度
$$Lift\_{A,B} = Corr\_{A,B} = \frac{P(A \cap B)}{P(A)P(B)}$$
只看置信度和支持度是不够的，所以需要考察上边公式，计算**提升度**。
* Lift > 1：正相关（此时支持度和信赖度才会有更好的效果）
* Lift < 1：负相关
计算后如下：
如图所示，根据提升度，$$X, Y$$正相关，$$X, Z$$负相关，所以$$X, Z$$是误导的关联规则，即`< 1`的负相关，都可以不考虑**支持度，置信度**。
### 2.4. 关联规则生成
如何生成关联规则？
* **Exhaustive Approach**（暴力法产生所有规则）
* 尝试任意组合。
* 因为产生的规则太多，且花的时间很多，所以几乎所有的软件或套件都只产生结果是单一项的规则。
* **Improved Approach 1**（改进策略1）
* 从项多的开始产生，避免一些不必要的尝试
$$confidence({A,B,C} -> D) = \frac{support(A,B,C,D)}{support(A,B,C)} < \min conf$$ $$confidence({A,B} -> {C,D}) = \frac{support(A,B,C,D)}{support(A,B)} \le \le \frac{support(A,B,C,D)}{support(A,B,C)} < \min conf.$$
* **Improved Approach 2**（改进策略2）
* 从项少的开始尝试，避免一些不必要的尝试
* 证明同1
### 2.5. 关联规则延伸
* Virtual Items：虚拟商品
* Association Mining：关联规则挖掘
* Dissociation Rules：反向关联规则
**Dependency Network**（依赖式网络）。
## 3. 序列模式
### 3.1. 概念和评估指标
顾客购买商品的顺序：
引入**交易时间**，包含交易ID，顾客ID；在结果中，顾客的交易时间不一定要连续，只要先购买然后购买就够了。
* 先根据ID排序（Customer Id）
* 再根据交易时间排序（Transaction Time）
### 3.2. Apriori All算法
**步骤**
1. Sort Phase，按ID和交易时间排序
2. Litemset Phase，找到大于`min_sup_count=2`的项
3. Transformation Phase
4. Sequence Phase（截图为另外一个例子，描述详细转换流程）
5. Maximal Phase（**上图中最后一步**）
### 3.3. PrefixSpan算法实例