数据挖掘第三章关联规则挖掘

在数据挖掘的知识模式中，关联规则模式是比较重要的一种。关联规则的概念由Agrawal、Imielinski、Swami 提出，是数据中一种简单但很实用的规则。关联规则模式属于描述型模式，发现关联规则的算法属于无监督学习的方法。

第三章 关联规则挖掘

• 什么是关联规则挖掘？
  • 购物篮分析
  • 目的：在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构
  • 频繁模式: 数据库中频繁出现的项集
  • 关联规则挖掘：给定事务的集合 T, 关联规则发现是指找出支持度大于等于 min_sup并且置信度大于等于min_conf的所有规则, min_sup和min_conf是对应的支持度和置信度阈值。
  • 应用：
    • 购物篮分析、交叉销售、产品目录设计生物信息学、医疗诊断、网页挖掘、科学数据分析等。
  • 举例：
    • 规则形式：“X ® Y[support, confidence]”.
    • “尿布” ® “啤酒” [0.5%, 60%]
    • “CS” ^ “DM” ® “A” [1%, 75%]
    • “面包” ® “牛奶” [2.5%, 70%]
• 定义: 频繁项集（Frequent Itemset）
  • 项集（Itemset）
    • 包含0个或多个项的集合: 例子: {Milk, Bread, Diaper}
    • k-项集: 如果一个项集包含k个项
  • 支持度计数（Support count ）(σ)
    • 包含特定项集的事务个数
    • 例如： σ({Milk, Bread,Diaper}) = 2
  • 支持度（Support）
    • 包含项集的事务数与总事务数的比值
    • 例如：support({Milk, Bread, Diaper}) = 2/5
  • 频繁项集（Frequent Itemset）
    • 满足最小支持度阈值（ min_sup ）的所有项集
• 定义: 关联规则（Association Rule）
  • 关联规则
    • 关联规则是形如 X  Y的蕴含表达式, 其中 X 和 Y 是不相交的项集
    • 例子: {Milk, Diaper}  {Beer}
  • 关联规则的强度
    • 支持度 support (X ® Y): 确定项集的频繁程度
    • support(X ® Y) = P(X Y)
    • - 置信度 Confidence (X ® Y): 确定Y在包含X的事务中出现的频繁程度
    • confidence (X ® Y) = P(Y|X) = support(X Y)/support(X)
  • Note: P(X Y) 表示事务包含集合A和B中每个项的概率
  • 几个重要的概念
    • 项集
    • 支持度计数
    • 支持度
    • 频繁项集
    • 置信度
    • 关联规则
• 如何进行关联规则挖掘？
  • 挖掘关联规则一般步骤
  • 频繁项集产生（Frequent Itemset Generation）
    • 其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集。
  • 规则的产生（Rule Generation）
    • 其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）。
  • Brute-force 方法（蛮力方法）
    • 格结构（lattice structure）
    • 频繁项集产生（Frequent Itemset Generation）
      • Brute-force 方法:
      • 把格结构中每个项集作为候选项集
      • 将每个候选项集和每个事务进行比较，确定每个候选项集的支持度计数。
      • 时间复杂度 高，开销非常大。
    • 蛮力方法
      • 蛮力方法把所有的k-项集都看作可能的候选，然后使用候选剪枝除去不必要的候选
      • 第k层产生的候选项集的数目为
      • 虽然候选产生是相当简单的，但是候选剪枝的开销极大，因为必须考察的项集数量太大。
      • 设每一个候选项集所需的计算量为O（k），这种方法的总复杂度为
    • 降低产生频繁项集计算复杂度的方法
      • 减少候选项集的数量
        • 先验(apriori)原理
      • 减少比较的次数
        • 替代将每个候选项集与每个事务相匹配，可以使用更高级的数据结构，或存储候选项集或压缩数据集，来减少比较次数
  • Apriori算法
    • 性质一：如果一个项集是频繁的，则它的所有子集一定也是频繁的
    • 性质二：相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的
    • 这种基于支持度度量修剪指数搜索空间的策略称为基于支持度的剪枝（support-based pruning）
    • 这种剪枝策略依赖于支持度度量的一个关键性质，即一个项集的支持度决不会超过它的子集的支持度。这个性质也称为支持度度量的反单调性（anti-monotone）
    • Apriori: 一种候选产生-测试方法
      • 频繁项集的任何子集必须是频繁的
        • 如果 {beer, diaper, nuts} 是频繁的, {beer, diaper}也是
        • 每个包含 {beer, diaper, nuts}的事务也包含 {beer, diaper}
      • Apriori 剪枝原则:
        • 如果一个项集不是频繁的, 将不产生/测试它的超集!
      • 方法:
        • 由长度为k的频繁项集产生长度为 (k+1) 的候选项集（连接，剪枝）, 并且根据 DB测试这些候选。
    • 频繁项集到规则产生
      • 怎样有效的从频繁项集中产生关联规则?
      • 关联规则的提取：将一个项集 Y划分成两个非空的子集 X 和Y-X，使得X  Y –X满足置信度阈值。
      • 如果 {A,B,C,D} 是频繁项集, 候选项集为:
        • ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABCAB CD, AC  BD, AD  BC, BC AD, BD AC, CD AB,
      • 一般，计算关联规则的置信度并不需要再次扫描事务数据集。规则{A,B,C} {D}的置信度为support(ABCD)/ support (ABC)。
    • 计算复杂性
      • 支持度阈值
        • 降低支持度阈值通常将导致更多的项集是频繁的。计算复杂度增加
        • 随着支持度阈值的降低，频繁项集的最大长度将增加，导致算法需要扫描数据集的次数也将增多
      • 项数
        • 随着项数的增加，需要更多的空间来存储项的支持度计数。如果频繁项集的数目也随着数据项数增加而增长，则由于算法产生的候选项集更多，计算量和I/O开销将增加
      • 事务数
        • 由于Apriori算法反复扫描数据集，因此它的运行时间随着事务数增加而增加
    • 频繁模式挖掘的挑战
      • 挑战
        • 事务数据库的多遍扫描
        • 数量巨大的候选
        • 候选支持度计数繁重的工作量
      • 改进 Apriori: 基本思想
        • 减少事务数据库的扫描遍数
        • 压缩候选数量
        • 便于候选计数
    • 提高Apriori算法的方法
      • Hash-based itemset counting（散列项集计数）
        • 基于Hash(散列)的技术
        • 基本思想：压缩候选k项集
        • 散列项集到对应的桶中，一个其hash桶的计数小于阈值的k-itemset 不可能是频繁的
        • J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining association rules. In SIGMOD’95
      • Transaction reduction（事务压缩）
        • 基本思想：删除不可能对寻找频繁项集有用的事务（对象）
        • 不包含任何频繁k项集的事务不可能包含任何频k+1项集。因此这些事务在其后的考虑中，可以加上标记或删除。
      • Partitioning（划分）
        • 基本思想：分而治之
        • 原理：项集在DB中是频繁的, 它必须至少在DB的一个划分中是频繁的
        • 扫描 1: 划分数据库, 并找出局部频繁模式 local frequent itemset
        • 扫描 2: 求出全局频繁模式
        • A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association in large databases. In VLDB’95
      • Sampling（采样）
        • 基本思想：选取原数据库的一个样本, 使用Apriori 算法在样本中挖掘频繁模式
        • 扫描一次数据库, 验证在样本中发现的频繁模式.
        • 再次扫描数据库, 找出遗漏的频繁模式（可选）
        • 牺牲一些精度换取有效性。
        • see: H. Toivonen. Sampling large databases for association rules. In VLDB’96
  • FP增长算法 （Frequent-Pattern Growth）
    • 该算法不同于Apriori算法的“产生-测试”范型。而是使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。
    • 基本思想：
      • 首先：将代表频繁项集的数据库压缩到FP树上
      • 其次：将FP树划分为一组条件数据库（每个数据数据库关联一个频繁项或“模式段 ”），挖掘每个条件数据库获取频繁项集
    • 首先，我们该如何构造FP树呢？
      • 支持度排序：扫描一次数据集，确定每个项的支持度计数。丢弃非频繁项，而将频繁项按照支持度的递减排序。L = {a:8, b:7, c:6, d:5, e:3}
      • 构建FP树：第二次扫描数据集，读入第一个事务{a, b}之后，创建标记为a和b的结点。然后形成null->a->b路径。该路径上的所有结点的频度计数为1。
      • 读入第二个事务{b,c,d}之后，为项b,c和d创建新的结点集。然后，连接结点null->b->c->d，形成一条代表该事务的路径。该路径上的每个结点的频度计数也等于1.
      • 注意：尽管前两个事务具有一个共同项b，但是它们的路径不相交，因为这两个事务没有共同的前缀.
    • FP树特点
      • 通常，FP树的大小比未压缩的数据小，因为购物篮数据的事务常常共享一些共同项。如果共同项较少，FP树对存储空间的压缩效果将不明显。
      • FP树的大小也依赖于项如何排序。一般按照支持度计数递减序可以导致较小的FP树。但也有一些例外。
      • FP树还包含一个连接具有相同项的结点的指针列表。这些指针有助于方便快捷地访问树中的项。
    • 其次，如何在FP树进行频繁模式挖掘呢？
      • (1) 构建条件模式基（子数据库）
        • 条件模式基：一个“子数据库”，由FP树中与该后缀模式一起出现的前缀路径集组成。
      • (2) 构建条件FP树
        • 将条件模式基看作为事务数据库，构造条件FP树
      • (3) 挖掘频繁项集
        • 对每一（条件）树，两种情况：
        • 1)如果（条件）FP树为单个路径，则产生该路径下所有模式的组合。
        • 2) 如果（条件）FP树为多路径，则针对树的头表中的每一个项， 产生对应模式获取频繁模式。
    • FP增长算法
      • 优点：
        • FP增长算法对长和短的模式都是有效且可伸缩的
        • 效率比Apriori算法快了一个数量级
      • 缺点： 对内存要求较大， 算法实现相对复杂
• 基于约束的关联规则挖掘
  • 自动地找出数据库中的所有模式? — 不现实!
    • 模式可能太多, 并不聚焦!
  • 数据挖掘应当是一个 交互的 过程
    • 用户使用数据挖掘查询语言 (或图形用户界面) 指导需要挖掘什么
  • 基于约束的挖掘
    • 用户灵活性: 提供挖掘的 约束
    • 系统优化: 考察限制, 寻找有效的挖掘—基于约束的挖掘
  • 有关的其他方法
    • 挖掘频繁闭项集合和最大模式
      • CLOSET (DMKD’00)
    • 挖掘序列模式
      • FreeSpan (KDD’00), PrefixSpan (ICDE’01)
    • 频繁模式的基于限制的挖掘
      • Convertible constraints (KDD’00, ICDE’01)
• 关联模式的评估
  • 关联分析算法往往产生大量的规则，而其中很大一部分可能是不感兴趣的。 因此，建立一组广泛接受的评价关联模式质量的标准是非常重要的。
  • 第一组标准可以通过统计论据建立。涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的，因为它们可能反映数据中的伪联系。（这些令人感兴趣的模式可以使用客观兴趣度度量来排除）。
  • 第二组标准可以通过主观论据建立。一个模式被主观认为是无趣的，除非它能够揭示料想不到的信息或提供导致有益的行动的有用信息。
  • 例如：{黄油} {面包}可能不是有趣的，尽管有很高的支持度和置信度，但是它表示的关系显而易见。另一方面，规则{尿布} {啤酒}是有趣的，因为这种联系十分出乎意料，并且可能为零售商提供新的交叉销售机会。
  • 注意：将主观知识加入到模式的评价中是一项困难的任务，因为需要来自领域专家的大量先验信息。下面是一些将主观信息加入到模式发现任务中的方法。
  • 现有的关联规则的挖掘算法依赖于支持度和置信度来除去没有意义的模式。 然而。。。
  • 例子：假定希望分析爱喝咖啡和爱喝茶的人之间的关系。收集一组人关于饮料偏爱的信息，并汇总到下表6-8。