1、费高雷通信与信息工程 学院2015年春季第 6章 挖掘频繁模式、关联和相关性：基本概念和方法2第 6章：挖掘频繁模式、关联和相关性：基本概念和方法n 基本概念n 频繁项集挖掘方法n 那些模式是有趣的：模式评估方法n 小结3什么是频繁模式分析 ?n 频繁模式 : 频繁出现在数据集中的模式（如项集、子序列或子结构）n 首先被 Agrawal, Imielinski and Swami在 1993年的 SIGMOD会议上提出，称为 频繁项集 和 关联规则挖掘n 驱动 :发现数据中的内在规律n 超市数据中的什么产品会一起购买？ 啤酒和尿布n 在买了一台 PC之后下一步会购买 ?n 哪种 DNA对这种药
2、物敏感 ?n 我们如何自动对 Web 文档进行分类 ?n 更加广泛的用处n 购物篮分析、交叉销售、直销n 点击流分析、 DNA序列分析等等什么是频繁模式分析 ?5频繁模式挖掘为什么重要 ?n 频繁模式 : 数据集内在和重要的属性n 许多重要数据挖掘任务的基础n 关联 , 相关 , 和因果分析n 序列模式 ,空间模式（比如子图）n 时空模式分析 , 多媒体 , 时间序列和流数据n 分类 : discriminative, frequent pattern analysisn 聚类分析 : 基于频繁模式的聚类n 数据仓库 : iceberg cube and cube-gradient n 语义数
3、据压缩 : fasciclesn 更广泛应用6关联规则基本模型n 设 I=i1, , im为 所有项目的集合 ； D为 事务数据库 ，事务 T是 一个 项目子集（ TI）。每一个事务具有唯一的事务标识 TIDn 项集： 由项目构成的集合，为了方便表述用用 A表示n 事务 T包含项集 A，当且仅当 ATn 如果项集 A中包含 k个项目，则称其为 k项集n 支持度： 项集 A在事务数据库 D中出现的次数占 D中总事务的百分比n 频繁项集（或大项集） ：项集的支持度超过用户给定的 最小支持度阈值I=a, b, c, d, e, f若 A=a, c，则 A的支撑度为 50%项 属性一个事物 数据对象7
4、关联规则基本模型n 关联规则是形如 XY的逻辑蕴含式，其中 XI， YI，且XY=n 如果事务数据库 D中有 s% 的事务包含 XY，则称关联规则XY的 支持度为 s%n 实际上，支持度是一个概率值，是一个相对计数n support (XY)=P (X Y)n 项集的 支持度计数 (频率 ) support_countn 包含项集的事务数n 若项集 X的 支持度 记为 support (X)，规则的 信任度 为 support (XY) support (X)n 是一个条件概率 P (Y | X)n confidence (XY)=P (Y | X)=support _count(XY) su
5、pport_count (X)8频繁模式和关联规则n itemset X=x1, , xkn 找出满足最小支持度和置信度的所规则 X Y n 支持度 s：事务包含 XY的 概率 n 置信度 c：事务含 X也包含 Y的 条件概率顾客购买尿布顾客购买二者顾客购买啤酒Transaction-id Items bought10 A, B, D20 A, C, D30 A, D, E40 B, E, F50 B, C, D, E, F令 supmin = 50%, confmin = 50%频繁模式： A:3, B:3, D:4, E:3, AD:3关联规则 :A D (60%, 100%)D A (60%, 75%)9挖掘关联规则 一个例子规则 A C：支持度 = support(AC) = 50%置信度 = support(AC)/support(A) = 66.6%最小支持度 50%最小置信度 50%Transaction-id Items bought10 A, B, C20 A, C30 A, D40 B, E, FFrequent pattern SupportA 75%B 50%C 50%A, C 50%挖掘关联规则 (实际例子 )
