关联模式挖掘

Posted on

挖掘频繁模式、关联和相关性：基本概念和方法

概念

  • 频繁模式：频繁地出现在数据集中的模式（项集，序列，子结构）
  • 频繁项集：频繁出现在交易数据集中的商品
  • 频繁序列模式：交易序列频繁地出现购物历史中

购物篮分析

  • 商品是否被购买代表一个bool向量
  • 购物篮可用一个bool向量代替
  • 关联规则举例
    $computer\to software[support = 2% ; confidence = 60% ]$
    support支持度：computer和software被同时购买的占全体事务的比例
    confidence置信度：在购买computer的顾客同时购买software的频率
    如果一条关联规则满足最小置信度和最小支持度阈值，那么认为这条规则是有趣的

频繁项集，闭项集和关联规则

  • 事务TID：每个事务的标识
  • 规则$A\to B$，在事务集中成立，具有支持度$s$，置信度$c$
    $s=P(AB),c=P(B|A)$
  • 满足最小置信度和支持度的规则被认为是强的
  • 挖掘关联规则可以归结为挖掘频繁项集
    1. 找出全体频繁项集
    2. 从频繁项集中产生强规则
  • 反单调性：
    • 在数据集的某一个项集，增加一项不会使得它的支持度变高
    • 频繁项集的非空子集也是频繁项集
    • 非频繁项集的超集不会是频繁项集
  • 如果X是闭项集，如果不存在Y，$X \subset Y$,Y与X具有相同的支持度
    • （X添加一个元素都会使得其支持度降低）
  • 如果X是极大项集，如果X是频繁项集，且不存在Y，$X \subset Y$,Y是频繁的
    • （X添加一个元素甚至会导致支持度小于阈值）
  • 闭频繁项集包含频繁项集的所有信息

频繁项集挖掘方法

Apriori算法：通过限制候选产生发现频繁项集

  1. 数据预处理
    1. 找到全体频繁1项集
    2. 按照支持度降序给每个事务重新排序
  2. 递归连接
    1. 假设生成全体频繁k项集$L_k$，对于每一个可连接的$l_i,l_j\in L_k$,
      • 称频繁k项集a,b可连接，如果它们前k-1项相同但是最后一项不同
    2. 将$L_i \cup L_j$ 加入$L_{k+1}$
  3. 剪枝
    • 扫描刚刚生成的$L_{k+1}$,剪去那些非频繁的项集

由频繁项集产生关联规则

  • 对于某一个频繁项集$L$，其自动满足关联规则的支持度规则，因此划分称两个部分$L=A\cup B$
  • 如果$A\to B$满足置信度规则，那么这个关联规则就是强规则

提高Apriori算法的效率

  • 基于散列的技术：
    • 一个其hash桶的计数小于阈值的k-itemset 不可能是频繁的
  • 事务压缩
    • 不包含任何频繁k项集的事务不可能包含任何频k+1项集
    • 因此这些事务在其后的考虑中，可以加上标记或删除
  • 划分
    • 原理：项集在DB中是频繁的, 它必须至少在DB的一个划分中是频繁的
    • 扫描 1: 划分数据库, 并找出局部频繁模式 local frequent itemset
    • 扫描 2: 求出全局频繁模式
  • 抽样

挖掘频繁模式的增长算法

  • FP-growth算法

    1. 建立FP树

      • 创建根节点null

      • 找到频繁1项集

      • 全体事务按照支持度递减顺序处理

      • 事务按照次序建字典树，同时标记权重

        • 考虑为一个事务增加分枝时，沿共

        • 向上同前缀每个结点计数加1，再创建结点和连接

        • 创建项头表，每项通过结点链指向树上的位置

          image-20240528171902886

    2. 挖掘频繁模式

      • 从项头表的后面向前考虑
      • 对于当前项在树上的每一个位置，开始爬树，生成条件模式基
      • 把新的条件模式基看成新的事务集，建立条件FP树

    image-20240528172315980

    1. 特点：
      • FP增长算法对长和短的模式都是有效且可伸缩的
      • 效率比Apriori算法快了一个数量级
      • 对内存要求较大， 算法实现相对复杂

哪些模式是有趣的：模式评估方法

强规则不一定是有趣的

尽管关联规则有可能满足最小置信度和最小支持度，但是置信度小于没有关联规则的概率时，关联规则就具有误导性了；

从关联分析到相关分析

强规则不一定是有趣的，甚至是“误导”的。

原因：置信度的缺点在于该度量忽略了规则后件中项集的支持度。

  • 提升度（兴趣因子）
    • $lift(A,B)=\frac{P(AB)}{P(A)P(B)}=\frac{P(B|A)}{P(B)}$
    • 描述A出现对B出现的提升程度
  • $\chi^2$分析
    • $\chi^2 = \sum_{i}\sum_{j}\frac{(\sigma_{ij}^2-e_{ij})}{e_{ij}}$
    • $\chi^2$大于1，说明负相关

模式评估度量比较

  • 下面每种越接近1，A,B联系越紧密
    • 全置信度
      • $all_{conf}(A,B)=min{P(A|B),P(B|A)}$
    • 最大置信度
      • $all_{conf}(A,B)=max{P(A|B),P(B|A)}$
    • Kule度量
      • $Kule(A,B)=\frac{P(A|B)+P(B|A)}{2}$
    • 余弦度量
      • $cosine(A,B)=\sqrt{P(A|B)\times P(B|A)}$
  • 对于指示有趣的模式联系，哪个最好？
    • 不平衡比$IR=\frac{|sup(A)-sup(B)|}{sup(A)+sup(B)-sup(AB)}$
    • $IR$越接近0，四种度量越平衡