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

概念

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

购物篮分析

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

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

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

频繁项集挖掘方法

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

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

由频繁项集产生关联规则

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

提高Apriori算法的效率

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

挖掘频繁模式的增长算法

• FP-growth算法

  1. 建立FP树

     • 创建根节点null

     • 找到频繁1项集

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

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

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

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

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

         

  2. 挖掘频繁模式

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

  

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

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

强规则不一定是有趣的

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

从关联分析到相关分析

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

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

• 提升度（兴趣因子）
  • 描述A出现对B出现的提升程度
• 分析
  • 大于1，说明负相关

模式评估度量比较

• 下面每种越接近1，A,B联系越紧密
  • 全置信度
  • 最大置信度
  • Kule度量
  • 余弦度量
• 对于指示有趣的模式联系，哪个最好？
  • 不平衡比
  • 越接近0，四种度量越平衡