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

关联规则挖掘(Association Rule Mining)

      • 关联规则挖掘(Association Rule Mining)详解
        • 1. 项集 (Itemset) 与 交易数据
        • 2. 支持计数 (Support Count, σ) 与支持度 (Support, s)
        • 3. 频繁项集 (Frequent Itemset)
        • 4. 关联规则 (Association Rule)
        • 5. 置信度 (Confidence, c)
        • 6. Apriori 算法与计算案例
          • 案例2:数据集
          • 步骤 1:生成频繁项集
            • 计算 1-项集的支持计数
            • 计算 2-项集的支持计数
          • 计算 3-项集的支持计数
          • 步骤 2:生成关联规则
          • 规则生成示例
          • 最终关联规则
        • 7. FP-Growth 算法与计算案例

关联规则挖掘(Association Rule Mining)详解

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

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

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

交易 项目
交易 1 牛奶, 尿布, 啤酒
交易 2 牛奶, 面包, 尿布
交易 3 牛奶, 尿布, 啤酒, 面包
交易 4 面包, 啤酒
交易 5 尿布, 啤酒

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

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

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

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

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

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

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

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 = σ ( X ∪ Y ) σ ( X ) c= \frac{\sigma(X \cup Y)}{\sigma(X)} c=σ(X)σ(XY)

其中 σ ( X ∪ Y ) σ(X∪Y) σ(XY)表示同时包含 X 和 Y 的交易数。
σ ( X ) σ(X) σ(X) 表示包含 X 的交易数。

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

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

因此,置信度为:

c = σ ( { 牛奶 , 尿布 , 啤酒 } ) σ ( { 牛奶 , 尿布 } ) = 2 3 ≈ 0.67 c = \frac{\sigma(\{牛奶, 尿布, 啤酒\})}{\sigma(\{牛奶, 尿布\})} = \frac{2}{3} \approx 0.67 c=σ({牛奶,尿布})σ({牛奶,尿布,啤酒})=320.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:数据集
交易 ID 项目集
1 A, C, D
2 B, C, E
3 A, B, C, E
4 B, E
步骤 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

交易 ID 项目集
1 A, C, D
2 B, C, E
3 A, B, C, E
4 B, E
  • 第一步:统计频率并构建项集的支持度降序。
item 频率
A 2
B 3
C 3
D 1
E 3
  • 第二步:根据降序将交易重新排序,构建 FP-树。例如:

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

item 排序后的item
A, C, D CA
B, C, E CBE (C在B前面,因为上一行先出现的C)
A, B, C, E CBEA
B, E BE

在这里插入图片描述

figure from usyd

  • 挖掘频繁项集:从 FP-树的底部开始构建条件 FP-树,最终得到频繁项集 {尿布, 啤酒}, {尿布, 牛奶}, 等
item condition pattern base
A C:1, EBC:1
E B:1, BC:2
B C:2, {}
C {}

最后根据条件状态得到所有频繁项集
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}

上一篇:【优选算法篇】化繁为简,见素抱朴:从乱象中重构秩序的艺术


下一篇:机器学习系列----KNN分类