【机器学习】29. 关联规则挖掘（Association Rule Mining）

关联规则挖掘（Association Rule Mining）详解

关联规则挖掘是一种无监督学习方法，旨在从数据中发现项目之间的相关性。关联规则常用于市场篮分析等场景，用来寻找交易中的商品关联，例如“如果顾客买了A，可能还会买B”。下面，我们通过具体的计算案例来阐释关联规则挖掘的各项基本概念。

1. 项集 (Itemset) 与 交易数据

项集 是一组项目的集合，例如 {牛奶, 面包, 尿布}。在关联规则挖掘中，交易数据通常表示顾客购买的商品清单。我们用以下交易数据来作为示例：

每个交易包含一个或多个项目的组合。关联规则挖掘的目的是找出这些项目组合之间的相关性。

2. 支持计数 (Support Count, σ) 与支持度 (Support, s)

支持计数 是项集在所有交易中出现的次数，用于衡量该项集的普遍性。例如：

• 项集 {牛奶, 尿布} 出现在交易 1、2 和 3 中，因此： σ({牛奶,尿布})=3

支持度 是项集在所有交易中出现的频率，即支持计数除以总交易数，用于衡量项集的流行度。计算公式为：

$$s=\frac{\sigma (\text{项集})}{\text{总交易数}}$$

例如，项集 {牛奶, 尿布} 的支持度为：

s ( 牛奶 , 尿布 ) = σ ( { 牛奶 , 尿布 } ) 5 = 3 5 = 0.6 s({牛奶,尿布})= \frac{\sigma(\{牛奶, 尿布\})}{5} = \frac{3}{5} = 0.6 s(牛奶,尿布)=5σ({牛奶,尿布})​=53​=0.6

这个支持度表示在60%的交易中，顾客同时购买了牛奶和尿布。

3. 频繁项集 (Frequent Itemset)

频繁项集 是支持度达到某一预设阈值的项集。设定一个最低支持度阈值（min_support）可以过滤掉出现次数较少的项集。假设我们设定 min_support = 0.4（即项集至少需要出现在 40% 的交易中）。基于这个阈值，我们可以得到：

• {牛奶, 尿布} 的支持度为 0.6，满足 min_support，因此它是一个频繁项集。
• {面包, 啤酒} 的支持度为 0.4（2/5），也满足 min_support，因此也是一个频繁项集。

4. 关联规则 (Association Rule)

关联规则 是一种形式为 X→YX的蕴含关系，表示若顾客购买了项集 X，则很可能购买项集 Y。例如，规则 {牛奶, 尿布} → {啤酒} 表示“如果顾客买了牛奶和尿布，那么他们可能还会买啤酒”。

5. 置信度 (Confidence, c)

置信度 用于衡量在包含 X 的交易中，多少比例同时也包含 Y。置信度的计算公式为：

$$c=\frac{\sigma (X\cup Y)}{\sigma (X)}$$

其中 $$\sigma (X\cup Y)$$表示同时包含 X 和 Y 的交易数。
$$\sigma (X)$$ 表示包含 X 的交易数。

以规则 {牛奶, 尿布} → {啤酒} 为例：

• 项集 {牛奶, 尿布, 啤酒} 出现在交易 1 和交易 3 中，所以 $$\sigma (牛奶,尿布,啤酒)=2$$
• 项集 {牛奶, 尿布} 出现在交易 1、2 和 3 中，所以 $$\sigma (牛奶,尿布)=3$$

因此，置信度为：

c = σ ( { 牛奶 , 尿布 , 啤酒 } ) σ ( { 牛奶 , 尿布 } ) = 2 3 ≈ 0.67 c = \frac{\sigma(\{牛奶, 尿布, 啤酒\})}{\sigma(\{牛奶, 尿布\})} = \frac{2}{3} \approx 0.67 c=σ({牛奶,尿布})σ({牛奶,尿布,啤酒})​=32​≈0.67

这个置信度表示，在购买牛奶和尿布的交易中，约 67% 的顾客也购买了啤酒。

6. Apriori 算法与计算案例

Apriori 算法用于高效地生成频繁项集和关联规则。它基于以下原则：

• Apriori 原则：如果一个项集是频繁的，则它的所有子集也必须是频繁的；反之，如果一个项集是不频繁的，那么它的所有超集也不可能是频繁的。这一原则用于减少不必要的项集计算。

Apriori 计算步骤：

1. 生成频繁项集：从 1-项集开始逐步生成频繁项集。
2. 生成规则：对每个频繁项集生成高置信度的关联规则。

案例： 假设我们设定 min_support = 2，并使用前面的交易数据。

• 第一步：1-项集：
  • 计算每个单项的支持计数：例如，{牛奶} = 3, {尿布} = 4，{啤酒} = 4，{面包} = 3。
  • 滤除支持度小于 min_support 的项集。
• 第二步：2-项集：
  • 对保留的 1-项集进行组合生成 2-项集，并计算支持计数。例如，{牛奶, 尿布} = 3, {牛奶, 啤酒} = 2，{面包, 啤酒} = 2 等。
  • 滤除支持度小于 min_support 的项集。

案例2：数据集

步骤 1：生成频繁项集

计算 1-项集的支持计数

计算每个单项的支持计数，要求其支持计数大于或等于 min_support = 2。

• {A}：出现在交易 1 和 3 中，支持计数为 2。
• {B}：出现在交易 2、3 和 4 中，支持计数为 3。
• {C}：出现在交易 1、2 和 3 中，支持计数为 3。
• {D}：出现在交易 1 中，支持计数为 1。
• {E}：出现在交易 2、3 和 4 中，支持计数为 3。

频繁 1-项集： 仅保留支持计数大于等于 2 的项集：{A}, {B}, {C}, {E}。

计算 2-项集的支持计数

接下来，生成所有包含两个元素的组合并计算它们的支持计数。

• {A, B}：出现在交易 3 中，支持计数为 1（不满足 min_support）。
• {A, C}：出现在交易 1 和 3 中，支持计数为 2。
• {A, E}：出现在交易 3 中，支持计数为 1（不满足 min_support）。
• {B, C}：出现在交易 2 和 3 中，支持计数为 2。
• {B, E}：出现在交易 2、3 和 4 中，支持计数为 3。
• {C, E}：出现在交易 2 和 3 中，支持计数为 2。

频繁 2-项集： {A, C}, {B, C}, {B, E}, {C, E}。

计算 3-项集的支持计数

生成包含三个元素的组合并计算它们的支持计数。

• {A, B, C}：出现在交易 3 中，支持计数为 1（不满足 min_support）。
• {A, B, E}：出现在交易 3 中，支持计数为 1（不满足 min_support）。
• {A, C, E}：出现在交易 3 中，支持计数为 1（不满足 min_support）。
• {B, C, E}：出现在交易 2 和 3 中，支持计数为 2。

频繁 3-项集： {B, C, E}。

步骤 2：生成关联规则

从频繁项集中生成高置信度的关联规则，假设最小置信度为 60%。

规则生成示例

• 从频繁 2-项集 {A, C} 生成规则：

  • 规则 {A} -> {C}：置信度 = 支持计数 {A, C} / 支持计数 {A} = 2 / 2 = 1.0。
  • 规则 {C} -> {A}：置信度 = 支持计数 {A, C} / 支持计数 {C} = 2 / 3 ≈ 0.67。

  规则 {A} -> {C} 和 {C} -> {A} 满足最小置信度。

• 从频繁 2-项集 {B, C} 生成规则：

  • 规则 {B} -> {C}：置信度 = 支持计数 {B, C} / 支持计数 {B} = 2 / 3 ≈ 0.67。
  • 规则 {C} -> {B}：置信度 = 支持计数 {B, C} / 支持计数 {C} = 2 / 3 ≈ 0.67。

  规则 {B} -> {C} 和 {C} -> {B} 满足最小置信度。

• 从频繁 2-项集 {B, E} 生成规则：

  • 规则 {B} -> {E}：置信度 = 支持计数 {B, E} / 支持计数 {B} = 3 / 3 = 1.0。
  • 规则 {E} -> {B}：置信度 = 支持计数 {B, E} / 支持计数 {E} = 3 / 3 = 1.0。

  规则 {B} -> {E} 和 {E} -> {B} 满足最小置信度。

• 从频繁 3-项集 {B, C, E} 生成规则：

  • 规则 {B, C} -> {E}：置信度 = 支持计数 {B, C, E} / 支持计数 {B, C} = 2 / 2 = 1.0。
  • 规则 {B, E} -> {C}：置信度 = 支持计数 {B, C, E} / 支持计数 {B, E} = 2 / 3 ≈ 0.67。
  • 规则 {C, E} -> {B}：置信度 = 支持计数 {B, C, E} / 支持计数 {C, E} = 2 / 2 = 1.0。

  规则 {B, C} -> {E}, {B, E} -> {C}, 和 {C, E} -> {B} 满足最小置信度。

最终关联规则

以下是满足 min_confidence 的关联规则：

1. {A} -> {C}，置信度 = 1.0
2. {C} -> {A}，置信度 ≈ 0.67
3. {B} -> {C}，置信度 ≈ 0.67
4. {C} -> {B}，置信度 ≈ 0.67
5. {B} -> {E}，置信度 = 1.0
6. {E} -> {B}，置信度 = 1.0
7. {B, C} -> {E}，置信度 = 1.0
8. {B, E} -> {C}，置信度 ≈ 0.67
9. {C, E} -> {B}，置信度 = 1.0

7. FP-Growth 算法与计算案例

FP-Growth 算法是一种改进的频繁项集挖掘方法，能够在无需候选项集的情况下高效地发现频繁项集。FP-Growth 基于一种称为 FP-树 的数据结构。

FP-Growth 计算步骤：

1. 构建 FP-树：
   • 第一次扫描数据库：统计每个项目的支持度，并按支持度降序排列。
   • 第二次扫描数据库：根据降序排列将每个交易中的频繁项组织到 FP-树中。
2. 挖掘频繁项集：
   • 从 FP-树的底部开始，逐步生成条件模式基，并构建条件 FP-树，直至所有项集挖掘完成。

案例： 假设我们设定 min_support = 2。

• 第一步：统计频率并构建项集的支持度降序。

• 第二步：根据降序将交易重新排序，构建 FP-树。例如：

由于D<2所以排序的时候已经删除D了

figure from usyd

• 挖掘频繁项集：从 FP-树的底部开始构建条件 FP-树，最终得到频繁项集 {尿布, 啤酒}, {尿布, 牛奶}, 等

最后根据条件状态得到所有频繁项集
A: {(C:2)} -> CA
E: BC:2, B:3, C:3 -> BCE, BE, CE
B: C:2 -> CB
所有频繁项集为{A,B,C,E,CA,CB,CE,BE,BCE}