1、钱钱 峰峰通信与信息工程学院通信与信息工程学院2018年年第第6 6章章 挖掘频繁模式、关联和相关挖掘频繁模式、关联和相关性：基本概念和方法性：基本概念和方法2第第6 6章：挖掘频繁模式、关联和相关性：章：挖掘频繁模式、关联和相关性：基本概念和方法基本概念和方法n 基本概念基本概念n 频繁项集挖掘方法频繁项集挖掘方法n 那些模式是有趣的：模式评估方法那些模式是有趣的：模式评估方法n 小结小结3什么是频繁模式分析什么是频繁模式分析?n频繁模式频繁模式:频繁出现在数据集中的模式（如项集、子序列或子结构）频繁出现在数据集中的模式（如项集、子序列或子结构）n首先被首先被Agrawal,Imielins
2、ki and Swami在在1993年的年的SIGMOD会议上提出，称会议上提出，称为为频繁项集频繁项集和和关联规则挖掘关联规则挖掘n驱动驱动:发现数据中的内在规律发现数据中的内在规律n超市数据中的什么产品会一起购买？超市数据中的什么产品会一起购买？啤酒和尿布啤酒和尿布n在买了一台在买了一台PC之后下一步会购买之后下一步会购买?n哪种哪种DNA对这种药物敏感对这种药物敏感?n我们如何自动对我们如何自动对Web文档进行分类文档进行分类?n更加广泛的用处更加广泛的用处n购物篮分析、交叉销售、直销购物篮分析、交叉销售、直销n点击流分析、点击流分析、DNA序列分析等等序列分析等等什么是频繁模式分析什么
3、是频繁模式分析?5频繁模式挖掘为什么重要频繁模式挖掘为什么重要?n频繁模式频繁模式:数据集内在和重要的属性数据集内在和重要的属性n许多重要数据挖掘任务的基础许多重要数据挖掘任务的基础n关联关联,相关相关,和因果分析和因果分析n序列模式序列模式,空间模式（比如子图）空间模式（比如子图）n时空模式分析时空模式分析,多媒体多媒体,时间序列和流数据时间序列和流数据n分类分类:discriminative,frequent pattern analysisn聚类分析聚类分析:基于频繁模式的聚类基于频繁模式的聚类n数据仓库数据仓库:iceberg cube and cube-gradient n语义数据压
4、缩语义数据压缩:fasciclesn更广泛应用更广泛应用6关联规则基本模型关联规则基本模型n设设I=i1,im为为所有项目的集合所有项目的集合；D为为事务数据库事务数据库，事务，事务T是是一个一个项目子项目子集（集（T I）。每一个事务具有唯一的事务标识）。每一个事务具有唯一的事务标识TIDn项集：项集：由项目构成的集合，为了方便表述用用由项目构成的集合，为了方便表述用用A表示表示n事务事务T包含项集包含项集A，当且仅当，当且仅当A Tn如果项集如果项集A中包含中包含k个项目，则称其为个项目，则称其为k项集项集n支持度：支持度：项集项集A在事务数据库在事务数据库D中出现的次数占中出现的次数占D
5、中总事务的百分比中总事务的百分比n频繁项集（或大项集）频繁项集（或大项集）：项集的支持度超过用户给定的：项集的支持度超过用户给定的最小支持度阈值最小支持度阈值I=a,b,c,d,e,f若若A=a,c，则，则A的支撑度为的支撑度为50%项项属性属性一个事物一个事物数据对象数据对象7关联规则基本模型关联规则基本模型n关联规则是形如关联规则是形如XY的逻辑蕴含式，其中的逻辑蕴含式，其中X I，Y I，且，且X Y=n如果事务数据库如果事务数据库D中有中有s%的事务包含的事务包含X Y，则称关联规则，则称关联规则XY的的支持度为支持度为s%n实际上，支持度是一个概率值，是一个相对计数实际上，支持度是一
6、个概率值，是一个相对计数nsupport(XY)=P(X Y)n项集的项集的支持度计数支持度计数(频率频率)support_countn包含项集的事务数包含项集的事务数n若项集若项集X的的支持度支持度记为记为support(X)，规则的，规则的信任度信任度为为support(X Y)support(X)n是一个条件概率是一个条件概率P(Y|X)nconfidence(XY)=P(Y|X)=support _count(X Y)support_count(X)8频繁模式和关联规则频繁模式和关联规则nitemset X=x1,xkn找出满足最小支持度和置信度找出满足最小支持度和置信度的所规则的所规
7、则 X Y 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%,confmin=50%频繁模式：频繁模式：A:3,B:3,D:4,E:3,AD:3关联规则关联规则:A D (60%,100%)D A (60%,75%)9挖掘关联规则挖掘关联规则一个例子一个例子规则规则 A C：支持度支持度=sup
8、port(A C)=50%置信度置信度=support(A C)/support(A)=66.6%最小支持度最小支持度 50%最小置信度最小置信度 50%Transaction-idItems bought10A,B,C20A,C30A,D40B,E,FFrequent patternSupportA75%B50%C50%A,C50%挖掘关联规则挖掘关联规则(实际例子实际例子)11闭频繁项集和极大频繁项集闭频繁项集和极大频繁项集n一个长模式包含子模式的数目：一个长模式包含子模式的数目：e.g.,a1,a100 contains(1001)+(1002)+(110000)=2100 1=1.27
9、*1030 sub-patterns!n解解:引入闭频繁项集和极大频繁项集引入闭频繁项集和极大频繁项集n闭项集：闭项集：不存在具有相同支持度的真超项集不存在具有相同支持度的真超项集n闭频繁项集：闭频繁项集：如果如果X是频繁的，且不存在真超项集（是频繁的，且不存在真超项集（super-pattern）Y（X Y），使），使 X、Y有相同的支持度计数有相同的支持度计数 n(proposed by Pasquier,et al.ICDT99)n极大频繁项集：极大频繁项集：如果如果X是频繁的，并且不存在真超项集是频繁的，并且不存在真超项集Y使得使得X Y，并，并且且Y是频繁的是频繁的n(propose
10、d by Bayardo SIGMOD98)极大频繁项集极大频繁项集BorderInfrequent ItemsetsMaximal Itemsets极大频繁项集的真超项集不频繁极大频繁项集的真超项集不频繁闭频繁项集闭频繁项集n最大频繁项集存在的问题：最大频繁项集存在的问题：最大频繁项集的子集是频繁的，但无法推最大频繁项集的子集是频繁的，但无法推断出其具体的支持度断出其具体的支持度n闭频繁项集的集合包含频繁项集的闭频繁项集的集合包含频繁项集的完整信息完整信息（包括支持度）（包括支持度）n例子：例子：数据库包含两个事物，且令最小支持度为数据库包含两个事物，且令最小支持度为1n,n闭频繁项集闭频繁
11、项集na1,a100:1 a1,a50:2n最大频繁项集最大频繁项集na1,a100:1n所有频繁模式所有频繁模式na1:2,a1,a2:2,a1,a51:1,a1,a2,a100:1nA big number:2100-1?Why?闭频繁项集和极大频繁项集闭频繁项集和极大频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE12412312342453451212424412323243445122244423424Minimum support=2#Closed=9#M
12、aximal=4Closed and maximalClosed but not maximalTIDItems1ABC2ABCD3BCE4ACDE5DE闭频繁项集和极大频繁项集闭频繁项集和极大频繁项集16第第6 6章：挖掘频繁模式、关联和相关性：章：挖掘频繁模式、关联和相关性：基本概念和方法基本概念和方法n 基本概念基本概念n 频繁项集挖掘方法频繁项集挖掘方法n 那些模式是有趣的：模式评估方法那些模式是有趣的：模式评估方法n 小结小结17频繁项集挖掘方法频繁项集挖掘方法nApriori算法算法:通过限制候选产生发现频繁项集通过限制候选产生发现频繁项集n提高提高Apriori算法的效率算法的效
13、率n挖掘频繁项集的模式增长方法挖掘频繁项集的模式增长方法n是用垂直数据格式挖掘频繁项集是用垂直数据格式挖掘频繁项集n挖掘闭模式和极大模式挖掘闭模式和极大模式18Apriori算法的步骤nApriori算法命名源于算法使用了频繁项集性质的先算法命名源于算法使用了频繁项集性质的先验（验（Prior）知识）知识nApriori算法将发现关联规则的过程分为两个步骤：算法将发现关联规则的过程分为两个步骤：n通过迭代，检索出事务数据库中的所有频繁项集，即支通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集持度不低于用户设定的阈值的项集n利用频繁项集构造出满足用户最小信任度的规则
14、利用频繁项集构造出满足用户最小信任度的规则n挖掘或识别出所有频繁项集是该算法的核心，占整挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分个计算量的大部分19频繁项集频繁项集n为了避免计算所有项集的支持度（实际上频繁项为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），集只占很少一部分），Apriori算法引入潜在频繁算法引入潜在频繁项集的概念。项集的概念。n若若潜在频繁潜在频繁k项集项集的集合记为的集合记为Ck，频繁，频繁k项集的集项集的集合记为合记为Lk则两者之间满足关系则两者之间满足关系Lk Ckn构成潜在频繁项集所遵循的原则是构成潜在频繁项集所遵循的原则是“频繁项集
15、的频繁项集的子集必为频繁项集子集必为频繁项集”。20关联规则的性质关联规则的性质 n性质性质1：频繁项集的子集必为频繁项集：频繁项集的子集必为频繁项集 n性质性质2：非频繁项集的超集一定是非频繁的：非频繁项集的超集一定是非频繁的 nApriori算法运用性质算法运用性质1，通过已知的频繁项集构成长度更大，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集的项集，并将其称为潜在频繁项集n潜在频繁潜在频繁k项集项集的集合的集合Ck 是指由有可能成为频繁是指由有可能成为频繁k项集的项项集的项集组成的集合集组成的集合n以后只需计算潜在频繁项集的支持度，而不必计算所有不同以后只需计算潜在频繁项
16、集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量项集的支持度，因此在一定程度上减少了计算量21Apriori:一种候选产生一种候选产生-测试方法测试方法n频繁项集的任何子集必须是频繁的频繁项集的任何子集必须是频繁的n如果如果 啤酒啤酒,尿布尿布,坚果坚果 是频繁的是频繁的,啤酒啤酒,尿布尿布也是也是n每个包含每个包含 啤酒啤酒,尿布尿布,坚果坚果的事务的事务 也包含也包含 啤酒啤酒,尿布尿布 nApriori 剪枝原则剪枝原则:n如果一个项集不是如果一个项集不是频繁的频繁的,将不产生将不产生/测试它的超集测试它的超集!n方法方法:n由长度为由长度为k的的频繁频繁项集产生
17、长度为项集产生长度为(k+1)的候选项集的候选项集,并且并且n根据根据 DB测试这些候选测试这些候选n性能研究表明了它的有效性和可伸缩性性能研究表明了它的有效性和可伸缩性22Apriori 算法算法 一个例子一个例子数据库数据库 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,E2Itemsets
18、upA,C2B,C2B,E3C,E2ItemsetB,C,EItemsetsupB,C,E223Apriori算法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.co
19、unt minsup n(10)end;n(11)Answer=kkL24Apriori的重要细节的重要细节n如何产生候选如何产生候选?n步骤步骤 1:Lk的自连接的自连接 n步骤步骤 2:剪枝剪枝n候选产生的例子候选产生的例子nL3=abc,abd,acd,ace,bcdn自连接自连接:L3*L3nabcd：由由 abc 和和 abdnacde：由由 acd 和和 acen剪枝剪枝:nacde 被删除被删除,因为因为 ade 不在不在 L3nC4=abcd25如何产生候选如何产生候选?n假定假定 Lk-1 中的项集已排序中的项集已排序(按字典序排序按字典序排序)n步骤步骤 1:Lk-1自连接
20、自连接（参考书本（参考书本p253）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:剪枝26教材教材161页页 例例6.3（支持计数（支持计数=2）27例子例子28由频繁项集产生关联规则由频繁项集产生关联规则n根据公式产生关联规则n对于每个频繁项集l，产生所有的非空子集频繁n对于l的每个非空子集s，如果则输出规则”s(l-s)”29频繁模式挖掘的挑战频繁模式挖
21、掘的挑战n挑战挑战n事务数据库的多遍扫描事务数据库的多遍扫描n数量巨大的候选数量巨大的候选n候选支持度计数繁重的工作量候选支持度计数繁重的工作量n改进改进 Apriori:基本思想基本思想n减少事务数据库的扫描遍数减少事务数据库的扫描遍数n压缩候选数量压缩候选数量n便于候选计数便于候选计数30频繁项集挖掘方法频繁项集挖掘方法nApriori算法算法:通过限制候选产生发现频繁项集通过限制候选产生发现频繁项集n提高提高Apriori算法的效率算法的效率n挖掘频繁项集的模式增长方法挖掘频繁项集的模式增长方法n是用垂直数据格式挖掘频繁项集是用垂直数据格式挖掘频繁项集n挖掘闭模式和极大模式挖掘闭模式和极
22、大模式31提高Apriori算法的方法nHash-based itemset counting（散列项集计数）（散列项集计数）nTransaction reduction（事务压缩）（事务压缩）nPartitioning（划分）（划分）nSampling（采样）（采样）思路：降低扫描次数、提高每次扫描的效率思路：降低扫描次数、提高每次扫描的效率32划分划分:只扫描数据库两次只扫描数据库两次n项集在项集在DB中是频繁的中是频繁的,它必须至少在它必须至少在DB的一个划分中频繁的一个划分中频繁n扫描扫描 1:划分数据库划分数据库,并找出局部频繁模式并找出局部频繁模式 local frequent i
23、temsetn扫描扫描 2:求出全局频繁模式求出全局频繁模式nA.Savasere,E.Omiecinski,and S.Navathe.An efficient algorithm for mining association in large databases.In VLDB9533抽样抽样-频繁模式频繁模式n选取原数据库的一个样本选取原数据库的一个样本,使用使用Apriori 算法在样本算法在样本中挖掘频繁模式中挖掘频繁模式n扫描一次数据库扫描一次数据库,验证在样本中发现的频繁模式验证在样本中发现的频繁模式.n再次扫描数据库再次扫描数据库,找出遗漏的频繁模式找出遗漏的频繁模式n牺牲一些
24、精度换取有效性。牺牲一些精度换取有效性。nH.Toivonen.Sampling large databases for association rules.In VLDB9634基于散列的技术基于散列的技术n散列项集到对应的桶中，一个其散列项集到对应的桶中，一个其hash桶的计数小于阈值的桶的计数小于阈值的k-itemset 不可能是频繁的不可能是频繁的nJ.Park,M.Chen,and P.Yu.An effective hash-based algorithm for mining association rules.In SIGMOD9535动态集计数动态集计数:减少扫描次数减少扫描
25、次数ABCDABCABDACD BCDABACBCADBDCDABCDItemset latticen一旦确定一旦确定 A 和和 D 是频繁的，立即开是频繁的，立即开始始 AD 的计数的计数n一旦确定一旦确定 BCD 的两个长度为的两个长度为2的子的子集是频繁的，立即开始集是频繁的，立即开始BCD 的计数的计数事务事务1-itemsets2-itemsetsApriori1-itemsets2-items3-itemsDICS.Brin R.Motwani,J.Ullman,and S.Tsur.Dynamic itemset counting and implication rules fo
26、r market basket data.In SIGMOD9736频繁项集挖掘方法频繁项集挖掘方法nAprioriApriori算法算法:通过限制候选产生发现频繁项集通过限制候选产生发现频繁项集n提高提高AprioriApriori算法的效率算法的效率n挖掘频繁项集的模式增长方法挖掘频繁项集的模式增长方法n是用垂直数据格式挖掘频繁项集是用垂直数据格式挖掘频繁项集n挖掘闭模式和极大模式挖掘闭模式和极大模式37n主要步骤主要步骤:n利用频繁利用频繁k-1项集产生项集产生候选的候选的频繁频繁k项集项集Ck n扫描数据库确定扫描数据库确定Ck 中的每一项是否为频繁中的每一项是否为频繁k项集项集nE.
27、g.,TIDItems bought 100f,a,c,d,g,i,m,p200a,b,c,f,l,m,o300 b,f,h,j,o400 b,c,k,s,p500 a,f,c,e,l,p,m,nAprioriApriori iteration C1f,a,c,d,g,i,m,p,l,o,h,j,k,s,b,e,nL1f,a,c,m,b,pC2 fa,fc,fm,fp,ac,am,bpL2 fa,fc,fm,38频繁模式挖掘的瓶颈频繁模式挖掘的瓶颈n多遍数据库扫描是多遍数据库扫描是 昂贵的昂贵的n挖掘长模式需要很多遍扫描挖掘长模式需要很多遍扫描,并产生大量候选并产生大量候选n挖掘频繁模式挖掘频
28、繁模式 i1i2i100n扫描次数扫描次数:100n候选个数候选个数:(1001)+(1002)+(110000)=2100-1=1.27*1030!n瓶颈瓶颈:候选产生候选产生-测试测试n能够避免候选产生吗能够避免候选产生吗?39挖掘频繁模式而不产生候选挖掘频繁模式而不产生候选n使用局部频繁的项使用局部频繁的项,由由短模式短模式增长产生增长产生长模式长模式n“abc”是频繁模式是频繁模式n得到包含得到包含“abc”的所有事务的所有事务:DB|abcn“d”是是 DB|abc 中的局部频繁项中的局部频繁项 abcd 是频繁模式是频繁模式挖掘频繁模式增长方法（挖掘频繁模式增长方法（FP-grow
29、thFP-growth）：根据事物数据库构造）：根据事物数据库构造频繁模式树（频繁模式树（FP-treeFP-tree），在频繁模式树上挖掘，），在频繁模式树上挖掘，实质是把事实质是把事物数据库压缩成物数据库压缩成FP-treeFP-tree进行挖掘进行挖掘40由事务数据库构造由事务数据库构造FP-树树f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem frequency head f4c4a3b3m3p3min_support=3TIDItems bought (ordered)frequent items100 f,a,c,d,g,i,m,p
30、 f,c,a,m,p200 a,b,c,f,l,m,o f,c,a,b,m300 b,f,h,j,o,w f,b400 b,c,k,s,p c,b,p500 a,f,c,e,l,p,m,n f,c,a,m,p1.扫描扫描 DB 一次一次,找出频繁找出频繁 1项集项集（单个项的模式）（单个项的模式）2.按频率的降序将频繁项排按频率的降序将频繁项排序序,得到得到 f-list3.再次扫描再次扫描 DB,构造构造 FP-树树f-list=f-c-a-b-m-p41Item frequency f4c4a3b3m3p3TIDItems bought 100f,a,c,d,g,i,m,p200a,b,c
31、,f,l,m,o300 b,f,h,j,o400 b,c,k,s,p500 a,f,c,e,l,p,m,nStep 1:扫描数据库构造频繁扫描数据库构造频繁1项集项集LLf-list=f-c-a-b-m-p42TIDItems bought (ordered)frequent items100f,a,c,d,g,i,m,p f,c,a,m,p200a,b,c,f,l,m,o f,c,a,b,m300 b,f,h,j,o f,b400 b,c,k,s,p c,b,p500 a,f,c,e,l,p,m,n f,c,a,m,pStep 2:第二遍扫描数据库，对频繁项进行排序第二遍扫描数据库，对频繁项
32、进行排序43f:1c:1a:1m:1p:1f,c,a,m,pf:2c:2a:2b:1m:1p:1m:1f,c,a,b,mNOTE:每一条事每一条事物对应到物对应到FP树中的树中的一条路径一条路径Step 2:构造构造FP树树44f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Step 2:构造构造FP树树f:3c:2a:2b:1m:1p:1m:1f,bb:1c,b,pc:1b:1p:1f:3c:2a:2b:1m:1p:1m:1b:1f,c,a,m,p Node-Link45f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1Header TableItem he
33、ad fcabmpStep 2:最终的最终的FP树树46频繁模式挖掘步骤频繁模式挖掘步骤n可以按照可以按照f-list 将频繁模式划分成子集将频繁模式划分成子集nf-list=f-c-a-b-m-pn包含包含 p的模式的模式n包含包含 m 但不包含但不包含 p的模式的模式nn包含包含 c 但不包含但不包含 a,b,m,pn模式模式 fn完全性和非冗余性完全性和非冗余性47构造条件模式基构造条件模式基n由长度为由长度为1的频繁模式开始的频繁模式开始n收集频繁项收集频繁项 的所有的所有前缀路径，前缀路径，形成形成条件模式基条件模式基 条件模式基条件模式基itemcond.pattern basec
34、f:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p348从条件模式基到条件从条件模式基到条件FP-树树 n对于每个条件模式基对于每个条件模式基n累计累计条件模式基条件模式基中每个项的计数中每个项的计数n构造模式基中构造模式基中频繁项的频繁项的FP-树（条件树（条件FP-树）树）m-条件模式基条件模式基:fca:2,fcab:1f:3c:3a:3 m-条件条件FP-树树m的所有频繁模式的所有频繁模式m,fm,cm,am
35、,fcm,fam,cam,fcamf:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表头表Item frequency head f4c4a3b3m3p349EmptyEmptyf(f:3)|c(f:3)c(f:3,c:3)|a(fc:3)aEmpty(fca:1),(f:1),(c:1)b(f:3,c:3,a:3)|m(fca:2),(fcab:1)m(c:3)|p(fcam:2),(cb:1)p条件条件FP-tree条件模式基条件模式基项项从条件模式基到条件从条件模式基到条件FP-树树 递归递归:挖掘每个条件挖掘每个条件 FP-树树f:3c:3a:3“m”的条件的条件FP
36、-树树(fca:3)add“a”add“c”add“f”“am”的条件的条件FP-树树(fc:3)“cm”的条件的条件FP-树树(fa:3)“fm”的条件的条件FP-树树(ca:3)“acm”的条件的条件FP-树树(f:3)“afm”的条件的条件FP-树树(c:3)add“c”add“f”51特殊情况特殊情况:FP-树中的单个前缀路径树中的单个前缀路径n假定假定(条件条件)FP-树树 T 具有单个共享的前缀路径具有单个共享的前缀路径Pn挖掘可以分解成两步挖掘可以分解成两步n将单个前缀路径归约成将单个前缀路径归约成 一个结点一个结点n连接两部分的挖掘结果连接两部分的挖掘结果a2:n2a3:n3a
37、1:n1b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C2:k2C3:k3r1+a2:n2a3:n3a1:n1r1=52使用使用FP-树挖掘频繁模式树挖掘频繁模式n基本思想基本思想:频繁模式增长频繁模式增长n通过模式和数据库划分递归地增长频繁模式通过模式和数据库划分递归地增长频繁模式n方法方法 n对于每个频繁项对于每个频繁项,构造它的条件模式基构造它的条件模式基n然后构造它的条件然后构造它的条件 FP-树树n在新构造的条件在新构造的条件FP-树上重复这一过程树上重复这一过程n直到结果条件直到结果条件 FP-树为空树为空,或者它只包含一条路径或者它只包含一条路径单个路径将产生其子路
38、径的所有组合单个路径将产生其子路径的所有组合,每个子路径是每个子路径是一个频繁模式一个频繁模式53FP-树结构的优点树结构的优点n完全性完全性 n保留频繁模式挖掘的完整信息保留频繁模式挖掘的完整信息n不截断任何事务的长模式不截断任何事务的长模式n压缩性压缩性n压缩无关信息压缩无关信息非频繁的项被删除非频繁的项被删除n项按频率的降序排列项按频率的降序排列:越是频繁出现越是频繁出现,越可能被共享越可能被共享n绝对不比原来的数据库大绝对不比原来的数据库大(不计结点链和计数字段不计结点链和计数字段)54FP-增长增长 vs.Apriori:随支持度增长的可伸缩性随支持度增长的可伸缩性010203040
39、506070809010000.511.522.53Support threshold(%)Run time(sec.)D1 FP-grow th runtimeD1 Apriori runtimeData set T25I20D10K55FP-增长增长 vs.树树-投影投影:随支持度增长的可伸缩性随支持度增长的可伸缩性02040608010012014000.511.52Support threshold(%)Runtime(sec.)D2 FP-growthD2 TreeProjectionData set T25I20D100K56为什么为什么FP-增长是赢家增长是赢家?n分治分治:n根
40、据已经得到的频繁模式划分任务和数据库根据已经得到的频繁模式划分任务和数据库n导致较小的数据库的聚焦的搜索导致较小的数据库的聚焦的搜索n其它因素其它因素n没有候选产生没有候选产生,没有候选测试没有候选测试n压缩数据库压缩数据库 :FP-:FP-树结构树结构n不重复地扫描整个数据库不重复地扫描整个数据库 n基本操作基本操作局部频繁项计数和建立子局部频繁项计数和建立子FP-FP-树树,没没有模式搜索和匹配有模式搜索和匹配57有关的其他方法有关的其他方法n挖掘频繁闭项集合和最大模式nCLOSET(DMKD00)n挖掘序列模式 nFreeSpan(KDD00),PrefixSpan(ICDE01)n频繁
41、模式的基于限制的挖掘nConvertible constraints(KDD00,ICDE01)n计算具有复杂度量的冰山数据方nH-tree and H-cubing algorithm(SIGMOD01)58频繁项集挖掘方法频繁项集挖掘方法nAprioriApriori算法算法:通过限制候选产生发现频繁项集通过限制候选产生发现频繁项集n提高提高AprioriApriori算法的效率算法的效率n挖掘频繁项集的模式增长方法挖掘频繁项集的模式增长方法n是用垂直数据格式挖掘频繁项集是用垂直数据格式挖掘频繁项集n挖掘闭模式和极大模式挖掘闭模式和极大模式使用垂直数据格式挖掘频繁项集使用垂直数据格式挖掘频
42、繁项集n使用使用tid-list,包含包含item的事务的标识的集合的事务的标识的集合nM.Zaki et al.New algorithms for fast discovery of association rules.In KDD97n扫描一次数据集将扫描一次数据集将水平格式水平格式数据转化为垂直格式数据转化为垂直格式n通过频繁通过频繁k项集的项集的tid-list的交集，计算对应的交集，计算对应(k+1)项集的项集的tid-list60频繁项集挖掘方法频繁项集挖掘方法nApriori算法算法:通过限制候选产生发现频繁项集通过限制候选产生发现频繁项集n提高提高Apriori算法的效率算法
43、的效率n挖掘频繁项集的模式增长方法挖掘频繁项集的模式增长方法n是用垂直数据格式挖掘频繁项集是用垂直数据格式挖掘频繁项集n挖掘闭模式和极大模式挖掘闭模式和极大模式极大模式极大模式n频繁模式频繁模式 a1,a100 包含包含(1001)+(1002)+(110000)=2100-1=1.27*1030 频繁子模式频繁子模式!n最大模式最大模式:频繁模式频繁模式,其真超模式都不是频繁的其真超模式都不是频繁的nBCDE,ACD 是最大模式是最大模式nBCD 不是最大模式不是最大模式TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,Fmin_sup=2挖掘极大模式挖掘极大模式n扫
44、描扫描1:找出频繁项找出频繁项nA,B,C,D,En扫描扫描2:找出以下项集的支持度找出以下项集的支持度 nAB,AC,AD,AE,ABCDEnBC,BD,BE,BCDEnCD,CE,DE,CDEn由于由于 BCDE 是最大模式是最大模式,不必在此后的扫描时检查不必在此后的扫描时检查 BCD,BDE,CDEnR.Bayato.Efficiently mining long patterns from databases.In SIGMOD98TidItems10A,B,C,D,E20B,C,D,E,30A,C,D,F潜在的最大模式潜在的最大模式 关联规则的可视化关联规则的可视化64关联规则的可
45、视化关联规则的可视化65频繁项集挖掘方法频繁项集挖掘方法nApriori算法算法:通过限制候选产生发现频繁项集通过限制候选产生发现频繁项集n提高提高Apriori算法的效率算法的效率n挖掘频繁项集的模式增长方法挖掘频繁项集的模式增长方法n是用垂直数据格式挖掘频繁项集是用垂直数据格式挖掘频繁项集n挖掘闭模式和极大模式挖掘闭模式和极大模式n模式评估的方法模式评估的方法兴趣度度量兴趣度度量n游戏游戏视频视频 40%,66.7%（结论具有误导性）（结论具有误导性）n事实上，视频光盘的购买会降低购买游戏光盘的可能性事实上，视频光盘的购买会降低购买游戏光盘的可能性n买视频所占百分比为买视频所占百分比为75
46、%,比比 66.7%还高还高游戏游戏非游戏非游戏Sum(row)视频视频200017503750非视频非视频10002501250Sum(col)300020005000寻找支持度寻找支持度信任度框架的替代，评价关联规则信任度框架的替代，评价关联规则提升度提升度n提升度（定义）提升度（定义）:游戏游戏非游戏非游戏Sum(row)视频视频200017503750非视频非视频10002501250Sum(col)30002000500089.05000/3750*5000/30005000/2000)V,G(lift)()()(BPAPBAPliftA与与B之间的相关性：大于之间的相关性：大于1正
47、相关，小于正相关，小于1负相关负相关1000/5000(G,V)1.333000/5000*1250/5000lift模式评估比较（几种度量）模式评估比较（几种度量）n全置信度：全置信度：n最大置信度：最大置信度：nKulczynski（Kulc）度量：）度量：n余弦度量：余弦度量：_(,)min(|),(|)allconf A BP A B P B A_(,)max(|),(|)max conf A BP A B P B A1(,)=(|)(|)2Kulc A BP A BP B Acos(,)=(|)(|)ine A BP A BP B A69零零不变度量不变度量n零事物：不包含任何考察项
48、的事物零事物：不包含任何考察项的事物n零不变度量：不受零事物影响的度量零不变度量：不受零事物影响的度量MilkNo MilkSum(row)Coffeem,cm,ccNo Coffeem,cm,ccSum(col.)mm各种度量的比较各种度量的比较nD1，D2中中m，c正相关；正相关；D3中负相关；中负相关；D4中性中性nD5，D6中牛奶与咖啡的关系中牛奶与咖啡的关系9.09%,0.99%mcm90.9%,99%mccnIR（Imbalance Ratio，不平衡比），不平衡比）:评估规则蕴含式中两个评估规则蕴含式中两个项集项集A 和和 B 的不平衡程度的不平衡程度nKulc与与IR一起可以清
49、晰的对一起可以清晰的对D4D6进行描述进行描述nD4 is balanced&neutralnD5 is imbalanced&neutralnD6 is very imbalanced&neutral各种度量的比较各种度量的比较72本章总结本章总结nBasic concepts:association rules,support-confident framework,closed and max-patternsnScalable frequent pattern mining methodsnApriori(Candidate generation&test)nProjection-based(FPgrowth,CLOSET+,.)nVertical format approach(ECLAT,CHARM,.)Which patterns are interesting?Pattern evaluation methods73作业作业n课后习题：课后习题：6.6、6.8、6.14
