1、1挖掘关联规则n 关联规则挖掘n 事务数据库中关联规则挖掘算法n 基于限制的关联挖掘2关联规则n 关联规则反映一个事物与其他事物之间的 相互依存性和关联性 。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物 预测 到。 n 典型的关联规则发现问题是对超市中的货篮数据进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。 3什么是关联规则挖掘n 关联规则挖掘 (1993)n 在事务、关系数据库中的项集和对象中发现 频繁模式 、关联规则 、 相关性或者因果结构n 频繁模式 : 数据库中频繁出现的 项集 n 目的 : 发现数据中的规律n 超市数据中
2、的什么产品会一起购买？ 啤酒和尿布n 在买了一台 PC之后下一步会购买 ?n 我们如何自动对 Web 文档进行分类 ?n 交叉销售、直销等4关联规则基本模型 n Apriori是关联规则模型中的经典算法。n 给定一组事务n 产生所有的关联规则n 满足最小支持度和最小可信度5关联规则基本模型n 设 I=i1, im为所有项目的集合， D为事务数据库，事务 T是一个项目子集（ TI）。每一个事务具有唯一的事务标识 TID。n 设 A是一个由项目构成的集合，称为 项集 。事务 T包含项集 A，当且仅当 AT。n 如果项集 A中包含 k个项目，则称其为 k项集 。n 项集 A在事务数据库 D中出现的次
3、数占 D中总事务的百分比叫做项集的 支持度 。n 如果项集的支持度超过用户给定的 最小支持度 (阈值 )，就称该项集是 频繁项集 。 6关联规则基本模型n 关联规则是形如 XY的逻辑蕴含式，其中 XI， YI，且 XY=。n 如果事务数据库 D中有 s% 的事务包含 XY，则称关联规则 XY的 支持度为 s%n support (XY)=P (X Y)n 项集的 支持度计数 support_countn 包含项集的事务数n 若项集 X的 支持度 记为 support (X)，规则的 置信度 为 support (XY) support (X)。n 是一个条件概率 P (Y | X)。 conf
4、idence (XY)=P (Y | X)n =support _count(XY) support_count (X)7频繁模式和关联规则n Itemset X=x1, , xkn 找出满足最小支持度和置信度的所有规则 XY n 支持度 , s, 事务包含 XY 的概率 n 置信度 , c, 事务含 X 也包含 Y 的 条件概率 .顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItems bought10 A, B, D20 A, C, D30 A, D, E40 B, E, F50 B, C, D, E, F令 supmin = 50%, confmin = 50%A:3
5、, B:3, D:4, E:3, F:3,AD:3关联规则 Association rules:A D (60%, 100%)D A (60%, 75%)8挖掘关联规则 一个例子规则 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%9第 5讲：挖掘关联规则n 关联规则挖掘n 事务数据库中关联规则挖掘算法n 基于限制的关联挖掘10Apriori算法的步骤n Apriori算法将发现关联规则的过程分为两个步骤：n 通过 迭代 、 检索 出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；n 利用频繁项集构造出满足用户最小信任度的规则。n 挖掘或识别出 所有频繁项集 是该算法的 核心 ，占整个计算量的大部分。
