挖掘关联规则

1、1挖掘关联规则挖掘关联规则n关联规则挖掘关联规则挖掘n事务数据库中关联规则挖掘算法事务数据库中关联规则挖掘算法n基于限制的关联挖掘基于限制的关联挖掘2关联规则关联规则n关联规则反映一个事物与其他事物之间的关联规则反映一个事物与其他事物之间的相互依相互依存性和关联性存性和关联性。如果两个或者多个事物之间存在。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通一定的关联关系，那么，其中一个事物就能够通过其他事物过其他事物预测预测到。到。 n典型的关联规则发现问题是对超市中的货篮数据典型的关联规则发现问题是对超市中的货篮数据进行分析。通过发现顾客放入货篮中的不同商品进行分析。通过

2、发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。之间的关系来分析顾客的购买习惯。 3什么是关联规则挖掘什么是关联规则挖掘n关联规则挖掘关联规则挖掘(1993)n在事务、关系数据库中的项集和对象中发现在事务、关系数据库中的项集和对象中发现频繁模式频繁模式、关联规则关联规则、相关性或者因果结构相关性或者因果结构n频繁模式频繁模式: 数据库中频繁出现的数据库中频繁出现的项集项集 n目的目的: 发现数据中的规律发现数据中的规律n超市数据中的什么产品会一起购买？超市数据中的什么产品会一起购买？ 啤酒和尿布啤酒和尿布n在买了一台在买了一台PC之后下一步会购买之后下一步会购买?n我们如何自动对我

3、们如何自动对Web文档进行分类文档进行分类?n交叉销售、直销等交叉销售、直销等4关联规则基本模型关联规则基本模型 nAprioriApriori是关联规则模型中的经典算法。是关联规则模型中的经典算法。n给定一组事务给定一组事务n产生所有的关联规则产生所有的关联规则n满足最小支持度和最小可信度满足最小支持度和最小可信度5关联规则基本模型关联规则基本模型n设设I=i1, im为所有项目的集合，为所有项目的集合，D为事务数据库，事务为事务数据库，事务T是是一个项目子集（一个项目子集（T I）。每一个事务具有唯一的事务标识）。每一个事务具有唯一的事务标识TID。n设设A是一个由项目构成的集合，称为是一

4、个由项目构成的集合，称为项集项集。事务。事务T包含项集包含项集A，当且仅当当且仅当A T。n如果项集如果项集A中包含中包含k个项目，则称其为个项目，则称其为k项集项集。n项集项集A在事务数据库在事务数据库D中出现的次数占中出现的次数占D中总事务的百分比叫中总事务的百分比叫做项集的做项集的支持度支持度。n如果项集的支持度超过用户给定的如果项集的支持度超过用户给定的最小支持度最小支持度(阈值阈值)，就称，就称该项集是该项集是频繁项集频繁项集。 交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F6关联规则基本模型关联规则基本模型n关联规则是形如关联规则是形如XY的逻辑

5、蕴含式，其中的逻辑蕴含式，其中X I，Y I，且且X Y=。n如果事务数据库如果事务数据库D中有中有s%的事务包含的事务包含X Y，则称关联，则称关联规则规则XY的的支持度为支持度为s%nsupport (XY)=P (X Y)n项集的项集的支持度计数支持度计数support_countn包含项集的事务数包含项集的事务数n若项集若项集X的的支持度支持度记为记为support (X)，规则的，规则的置信度置信度为为support (X Y)support (X)。n是一个条件概率是一个条件概率P (Y | X)。confidence (XY)=P (Y | X)n=support _count(

6、X Y)support_count (X)7频繁模式和关联规则频繁模式和关联规则nItemset X=x1, , xkn找出满足最小支持度和置信度找出满足最小支持度和置信度的所有规则的所有规则 XY n支持度支持度, s, 事务包含事务包含 X Y 的的概率概率 n置信度置信度, c, 事务含事务含 X 也包含也包含 Y 的的条件概率条件概率.顾客购买顾客购买尿布尿布顾客购顾客购买二者买二者顾客购买顾客购买啤酒啤酒Transaction-idItems bought10A, B, D20A, C, D30A, D, E40B, E, F50B, C, D, E, F令令supmin = 50%

7、, confmin = 50%A:3, B:3, D:4, E:3, F:3,AD:3关联规则关联规则Association rules:A D (60%, 100%)D A (60%, 75%)8挖掘关联规则挖掘关联规则一个例子一个例子规则规则 A C支持度支持度 = support(A C) = 50%置信度置信度 = support(A C)/support(A) = 66.6%最小支持度最小支持度 50%最小置信度最小置信度 50%Transaction-idItems bought10A, B, C20A, C30A, D40B, E, FFrequent patternSuppor

8、tA75%B50%C50%A, C50%9第第5讲：挖掘关联规则讲：挖掘关联规则n关联规则挖掘关联规则挖掘n事务数据库中关联规则挖掘算法事务数据库中关联规则挖掘算法n基于限制的关联挖掘基于限制的关联挖掘10Apriori算法的步骤算法的步骤nApriori算法将发现关联规则的过程分为两个步骤：算法将发现关联规则的过程分为两个步骤：n通过通过迭代迭代、检索检索出事务数据库中的所有频繁项集，即支出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；持度不低于用户设定的阈值的项集；n利用频繁项集构造出满足用户最小信任度的规则。利用频繁项集构造出满足用户最小信任度的规则。n挖掘或识别出挖掘

9、或识别出所有频繁项集所有频繁项集是该算法的是该算法的核心核心，占整，占整个计算量的大部分。个计算量的大部分。 11频繁项集频繁项集n为了避免计算所有项集的支持度（实际上频为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），繁项集只占很少一部分），Apriori算法引算法引入入潜在频繁项集潜在频繁项集的概念。的概念。n若若潜在频繁潜在频繁k项集项集的集合记为的集合记为Ck ，频繁，频繁k项集项集的集合记为的集合记为Lk ，m个项构成的个项构成的k项集的集合项集的集合为为 ，则三者之间满足关系，则三者之间满足关系Lk Ck 。kmCkmC12关联规则的性质关联规则的性质 n性质性质1：频

10、繁项集的子集必为频繁项集。：频繁项集的子集必为频繁项集。 n性质性质2：非频繁项集的超集一定是非频繁的：非频繁项集的超集一定是非频繁的。 nApriori算法运用性质算法运用性质1，通过已知的频繁项集，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项构成长度更大的项集，并将其称为潜在频繁项集。集。n潜在频繁潜在频繁k项集项集的集合的集合Ck 是指由有可能成为频繁是指由有可能成为频繁k项项集的项集组成的集合。集的项集组成的集合。n以后只需计算潜在频繁项集的支持度，而不必以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，计算所有不同项集的支持度，因此在一定程度因此在一定程

11、度上减少了计算量。上减少了计算量。 13Apriori: 一种候选产生一种候选产生-测试方法测试方法n频繁项集的任何子集必须是频繁的频繁项集的任何子集必须是频繁的n如果如果 beer, diaper, nuts 是频繁的是频繁的, beer, diaper也是也是n每个包含每个包含 beer, diaper, nuts的事务的事务 也包含也包含 beer, diaper nApriori 剪枝原则剪枝原则: （性质（性质2）n如果一个项集不是如果一个项集不是频繁的频繁的, 将不产生将不产生/测试它的超集测试它的超集!n方法方法: n由长度为由长度为k的的频繁频繁项集项集产生长度为产生长度为 (

12、k+1) 的候选项集的候选项集n并且根据并且根据 D测试这些候选（测试这些候选（.）14Apriori 算法算法 一个例子一个例子数据库数据库 TDB第第1次扫描次扫描C1L1L2C2C2第第2次扫描次扫描C3L3第第3次扫描次扫描TidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3D1E3ItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2I

13、temsetB, C, EItemsetsupB, C, E215Apriori算法算法n(1) L1=频繁频繁1项集项集; n(2) for(k=2;Lk-1;k+) do begin n(3) Ck=apriori_gen(Lk-1); /新的潜在频繁项集新的潜在频繁项集 n(4) for all transactions t D do begin n(5) Ct=subset(Ck,t); /找出找出t中包含的潜在的频繁项中包含的潜在的频繁项 n(6) for all candidates c Ct do n(7) c.count+; n(8) end; n(9) Lk=c Ck|c.c

14、ount minsup n(10) end; n(11) Answer= kkL16Apriori的重要细节的重要细节n如何产生候选如何产生候选?n步骤步骤 1: Lk的自连接的自连接 n步骤步骤 2: 剪枝剪枝n候选产生的例子候选产生的例子nL3=abc, abd, acd, ace, bcdn自连接自连接: L3*L3nAbcd：由由 abc 和和 abdnAcde：由由 acd 和和 acen剪枝剪枝:nacde 被删除被删除, 因为因为 ade 不在不在 L3nC4=abcd17如何产生候选如何产生候选?n假定假定 Lk-1 中的项集已排序中的项集已排序(按字典序排序按字典序排序)n步

15、骤步骤 1: Lk-1自连接自连接 insert into Ckselect p.item1, p.item2, , p.itemk-1, q.itemk-1from Lk-1 p, Lk-1 qwhere p.item1=q.item1, , p.itemk-2=q.itemk-2, p.itemk-1 q.itemk-1nStep 2: 剪枝剪枝forall itemsets c in Ck doforall (k-1)-subsets s of c doif (s is not in Lk-1) then delete c from Ck18例子例子-支持计数支持计数=219例子例子20

16、由频繁项集产生关联规则由频繁项集产生关联规则n根据公式产生关联规则根据公式产生关联规则n对于每个频繁项集对于每个频繁项集l，产生所有的非空子集，产生所有的非空子集n对于对于l的每个非空子集的每个非空子集s，如果，如果则输出规则则输出规则”s (l-s)”21频繁模式挖掘的挑战频繁模式挖掘的挑战n挑战挑战n事务数据库的多遍扫描n数量巨大的候选n候选支持度计数繁重的工作量n改进改进 Apriori: 基本思想基本思想n减少事务数据库的扫描遍数n压缩候选数量n便于候选计数n提高提高Apriori算法的方法算法的方法（划分和采样）（划分和采样）22n划分划分: 只扫描数据库两次只扫描数据库两次n项集在

17、项集在D中是频繁的中是频繁的, 它必须至少在它必须至少在D的一个划分中是频繁的的一个划分中是频繁的n扫描扫描 1: 划分数据库划分数据库, 并找出局部频繁模式并找出局部频繁模式 n扫描扫描 2: 求出全局频繁模式求出全局频繁模式n采样：频繁模式采样：频繁模式n选取原数据库的一个样本选取原数据库的一个样本, 使用使用Apriori 算法在样本中挖掘算法在样本中挖掘频繁模式频繁模式n扫描一次数据库扫描一次数据库, 验证在样本中发现的频繁模式验证在样本中发现的频繁模式.n再次扫描数据库再次扫描数据库, 找出遗漏的频繁模式找出遗漏的频繁模式n牺牲一些精度换取有效性。牺牲一些精度换取有效性。23频繁模式

18、挖掘的瓶颈频繁模式挖掘的瓶颈n多遍数据库扫描是多遍数据库扫描是 昂贵的昂贵的n挖掘长模式需要很多遍扫描挖掘长模式需要很多遍扫描, 并产生大量候选并产生大量候选n挖掘频繁模式挖掘频繁模式 i1i2i100n扫描次数扫描次数: 100n候选个数候选个数: (1001) + (1002) + + (100100) = 2100-1 = 1.27*1030 !n瓶颈瓶颈: 候选产生候选产生-测试测试n能够避免候选产生吗能够避免候选产生吗?（FP-树）树）24挖掘关联规则挖掘关联规则n关联规则挖掘关联规则挖掘n事务数据库中关联规则挖掘的算法事务数据库中关联规则挖掘的算法n基于限制的关联挖掘基于限制的关联

19、挖掘25基于约束的数据挖掘基于约束的数据挖掘n自动地自动地找出数据库中的找出数据库中的所有所有模式模式? 不现实不现实(模式太多模式太多)!n基于约束的挖掘基于约束的挖掘n用户灵活性用户灵活性: 提供挖掘的提供挖掘的 约束约束 n系统优化系统优化: 考察限制考察限制, 寻找有效的挖掘寻找有效的挖掘基于约束的挖掘基于约束的挖掘n知识类型约束知识类型约束:分类分类, 关联关联, 等等n数据约束数据约束 （指定任务相关的数据集）（指定任务相关的数据集）n找出找出 Vancouver 2000年年12月份一起销售的产品对月份一起销售的产品对n兴趣度约束兴趣度约束强规则强规则 : min_support

20、 3%, min_confidence 60%n规则规则 (或模式或模式) 约束约束-指定规则形式指定规则形式n小额销售小额销售 (价格价格 $200)26规则约束规则约束- -剪枝搜索空间剪枝搜索空间n规则约束的分类规则约束的分类n反单调性反单调性Anti-monotonicn单调性单调性Monotonicn简洁性简洁性 Succinct:27规则约束规则约束n反单调性反单调性n当项集当项集 S S 违反规则约束时违反规则约束时, , 它的任何超集它的任何超集合也违反约束合也违反约束nsum(S.Pricesum(S.Price) ) v v 是是反单调的反单调的nsum(S.Pricesu

21、m(S.Price) ) v v 不是不是反单调的反单调的n单调性单调性n当项集当项集 S S 满足满足约束约束时时, , 它的任何超集合也它的任何超集合也满足约束满足约束nsum(S.Pricesum(S.Price) ) v v 是是单调的单调的nmin(S.Pricemin(S.Price) ) v v 是是单调的单调的n简洁性简洁性:不查看事务数据库不查看事务数据库, 项集项集S 是否满足约束是否满足约束C可以可以根据选取的项确定根据选取的项确定 nmin(S.Price) v 是简洁的是简洁的nsum(S.Price) v 不是简洁的不是简洁的TIDTransaction10a, b

22、, c, d, f20b, c, d, f, g, h30a, c, d, e, f40c, e, f, gTDB (min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1028Apriori 算法算法 一个例子一个例子TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database Ditemset sup.1223334153itemset sup.12233353Scan DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52items

23、et sup1 322 322 533 52L2C2C2Scan DC3L3itemset2 3 5Scan Ditemset sup2 3 5229朴素算法朴素算法: Apriori + 约束约束TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database Ditemset sup.1223334153itemset sup.12233353Scan DC1L1itemset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2Scan DC3L3itemset2 3 5Scan Ditemset sup2 3 52约束约束: SumS.price 530受约束的受约束的A