关联规则挖掘

时间：2024-04-07 18:20:18

关联规则挖掘

已知一组交易数据，找到根据交易中其他项目的出现来预测项目发生的规则。
关联规则挖掘
关联关系可为：
{Diaper} -> {Bear}
{Milk, Bread} -> {Eggs,Coke}
{Beer, Bread} -> {Milk}
PS: 以上表示意味着同时出现，而不是因果关系

定义：频繁项目集

  • 项目集Itemset
    • 一个或者多个项目的集合
      例如： {Milk, Bread, Diaper}
    • k-Itenset
      一个含有k个项目的项目集
  • 支持数Support count(δ)
    • 项目集出现的频度
    • 例如：δ({Milk, Bread, Diaper})=2
  • 支持度Support
    • 包含项目集的事务的分数
    • 例如 s({Milk, Bread, Diaper})=25
  • 频繁项目集
    • 一个支持度大等于最小支持度的项目集
  • 关联规则
    • 一种形式的含义表达 X->Y, 此处X和Y均为项目集
    • 例如：{Milk, Diaper}->{Beer}
  • 规则评估指标(Rule Evaluation Metrics)
  • 支持度Support(s)
    • 包含项目集的事务的分数
  • 置信度Confidence(c)
    • 衡量Y中的项目在包含X的交易中的频率
    • 例如：
      c=δ(Milk,Diaper,Beer)δ(Milk,Diaper)=23=0.67

关联规则挖掘的任务

  1. 给定一组交易T, 关联规则挖掘的目标是找到所有规则它们符合以下定义：
    • 支持度support > 最小支持度 minsup
    • 置信度confidence > 最小置信度minconf
      1. 暴力方法：
    • 例举所有可能的关联规则
    • 计算每一个规则的支持度和置信度
    • 剪去支持度和置信度小于最小支持度及最小置信度的规则

挖掘关联规则

利用之前给出的图片例子，我们可以得出以下规则：
{Milk, Diaper} -> {Beer} (s=0.4,c=0.67)
{Milk, Beer} -> {Diaper} (s=0.4,c=1.0)
{Diaper, Beer} -> {Milk} (s=0.4,c=0.67)
{Beer} -> {Milk，Diaper} (s=0.4,c=0.67)
{Diaper} -> {Beer} (s=0.4,c=0.5)
{Milk} -> {Diaper, Beer} (s=0.4,c=0.5)

观察：

  • 所有以上列出的规则都是相同项目集的二维划分
  • 来自相同项目集的规则具有唯一的支持度但不同的置信度
  • 因此，我们可以解分离支持度和置信度的要求

两步方法
1. 生成频繁项目集
- 生成所有支持度大等于最小支持度的所有项目集
2. 产生规则
- 从每一个频繁项目集中生成高置信度的规则，每一个规则都是一个项目集的二维划分
生成频繁项目集计算量巨大

生成频繁项目集

关联规则挖掘

  • 暴力方法：
  • 栈中的每一个项目集都是候选频繁项目集
  • 通过扫描数据库技术每一个候选的支持度
  • 给定d个唯一的项目：
  • 项目集的总数=2d
  • 可能的关联规则总数
    R=∑k−1d−1[(dk)×∑j−1d−k(dk)]=3d−2d+1+1

    如果d=6，那么就会生成602个规则

生成频繁项目集策略

  1. 减少候选项的个数(M)
    • 完整的检索：M=2d
    • 使用剪枝技术去减少M
  2. 减少事务transaction的数量(N)
    • 随着项目集大小的增加，减小N的大小
    • 使用DHP(direct hashing and pruning)和vertical-based mining algorithms
  3. 减少比较的数量(NM)
    • 使用有效的数据结构去存储候选项和事务
    • 不需要匹配每个候选人与每个交易

生成频繁项目集(减少候选项的个数)的方法

  • Apriori principle
  • PF-Tree
    关于具体生成频繁项目集的方法在其他几篇博客当中会有详细介绍。

相关文章