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}一定会满足条件。步骤：

找到频繁项集
根据频繁项集生成关联规则

示例（略）

另外一个计算示例：

L3 = {abc, abd, acd, ace, bcd}
构造L4：
1. abcd = {abc, abd}
2. acde = {acd, ace}
移除 acde，因为 ade 并没出现在 L3中。
留下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可以并行执行，而且这个算法最终只会扫描数据库一次。

步骤：

实际是扫描数据库两次。

第一次扫描交易数据库，构造一个FP-Tree。
然后在FP-Tree中做Trimming，去查找对应子树（排序得到精简的FP-Tree）。
第二次扫描交易数据库，根据精简的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