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算法实例