第5章关联规则.pptVIP

第5章 关联分析 关联分析的预备知识 频繁项集的产生 Apriori方法 FP-Growth方法 非二元属性的关联规则挖掘 规则产生 关联规则的评估 序列模式 关联分析的基本概念 给定一组事务，寻找预测 “某些项将会随其他项的出现而出现” 的规则 挖掘关联规则 相关概念的定义 项集 一个或多个项的集合 例子： {Diaper, Beer} k-项集 包含k个项的项集 支持度计数 (support count) 给定项集的出现次数 例如： ?({Diaper, Beer} ) = 2 相关概念的定义（续） 举例： 关联规则挖掘任务 给定一个事务集合T，关联规则挖掘的目标是寻找所有满足下面条件的规则 支持度 ≥ minsup（支持度阈值） 置信度 ≥ minconf（置信度阈值） 挖掘关联规则 两步方法: 频繁项集的产生 产生 支持度?minsup 的所有项集 规则的产生 由每个频繁项集产生 置信度?minconf 的规则 关联分析 关联分析的预备知识 频繁项集的产生 Apriori方法 FP-Growth方法 非二元属性的关联规则挖掘 规则产生 关联规则的评估 序列模式 频繁项集的产生 频繁项集的产生 Brute-force（蛮力）方法: 在项集格中的每个项集都是一个候选频繁项集 扫描事务数据库计算每个候选频繁项集的支持度 将每个事务与每个候选频繁项集匹配 比较次数 ~ O(NMw) = 代价极高，因为M = 2k-1 !!! 关联分析 关联分析的预备知识 频繁项集的产生 Apriori方法 FP-Growth方法 规则产生 非二元属性的关联规则挖掘 关联规则的评估 序列模式 Apriori方法的优化策略 减少候选频繁项集的个数 (M) 完全有哪些信誉好的足球投注网站: M=2d 使用剪枝计数减少M 减少比较的次数 (NM) 使用高效的数据结构保存候选频繁项集或事务 不需要匹配每个候选和每个事务 减少候选频繁项集的个数 先验原理（Apriori principle）: 如果一个项集是频繁的，那么它的所有子集都是频繁的 先验原理成立的原因: 一个项集的支持度不会超过其任何子集的支持度 该性质称作支持度的反单调性质 先验原理的图示 Apriori算法 算法流程: 设定k=1 扫描事务数据库一次，生成频繁的1-项集 如果存在两个或以上频繁k-项集，重复下面过程： [候选产生] 由长度为k的频繁项集生成长度为k+1的候选项集 [候选前剪枝] 对每个候选项集，若其具有非频繁的长度为k的子集，则删除该候选项集 [支持度计算] 扫描事务数据库一次，统计每个余下的候选项集的支持度 [候选后剪枝] 删除非频繁的候选项集，仅保留频繁的(k+1)-项集 设定k = k+1 Apriori算法的核心步骤 候选产生 设A={a1,a2,…,ak}和B={b1,b2,…,bk}是一对频繁k-项集，当且仅当ai=bi (i=1,2,k-1)并且ak≠bk时，合并A和B，得到{a1,a2,…,ak,bk} 例如：合并{Bread,Milk}和{Bread,Diaper}得到{Bread,Milk,Diaper}，但{Milk,Bread}和{Bread,Diaper}不能合并 候选前剪枝 设A={a1,a2,…,ak,ak+1}是一个候选(k+1)-项集，检查每个A’是否在第k层频繁项集中出现，其中A’由A去掉ai (i=1,…,k-1) 得到 ? 若某个A’没有出现，则A是非频繁的 Apriori算法的例子 考虑下面的事务数据库 最小支持度计数阈值=2 Apriori算法的例子… 减少比较次数 候选项集的支持度计算: 扫描事务数据库，决定每个候选项集的支持度 为了减少比较次数，将候选项集保存在散列（hash）结构中 将每个事务与保存在散列结构的候选项集作匹配 生成候选的散列树（续） 事务与候选散列树匹配 关联分析 关联分析的预备知识 频繁项集的产生 Apriori方法 FP-Growth方法 规则产生 非二元属性的关联规则挖掘 关联规则的评估 序列模式 FP增长算法 FP算法使用一种称作FP树的紧凑数据结构组织数据，并直接从该结构中提取频繁项集。 FP树是一种输入数据的压缩表示，它通过逐个读入事务，并把每个事务映射到FP树中的一条路径来构造。 FP树的构建 FP增长过程 首先查找以“Ham”为后缀的频繁项集，然后依次是“Beer”、“Diaper”、“Cola”。 “Ham”的条件模式基{(Cola: 1)，(Cola Diaper Beer: 1)} “Ham”的条件FP-树只有1个分支Cola: 2 得到频繁项集{Cola Ham：2} FP增长过程 “Beer”的条件模式基{(Cola D