第6章：挖掘大型数据库中的关联规则-数据挖掘：概念与技术-教学课件1

2020/7/29DataMining:ConceptsandTechniques1第6章：挖掘大型数据库中的关联规则6.1关联规则挖掘关联规则挖掘寻找给定数据集中项之间的有趣联系。2020/7/29DataMining:ConceptsandTechniques46.1.2基本概念:频繁模式和关联规则Itemset（项集）X={x1,…,xk}找出满足最小支持度和置信度的所规则XY：支持度,s,事务包含XY的概率置信度,c,事务含X也包含Y的条件概率.设min_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,F2020/7/29DataMining:ConceptsandTechniques5挖掘关联规则—一个例子规则AC:支持度=support({A}{C})=50%置信度=support({A}{C})/support({A})=66.6%最小支持度50%最小置信度50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%2020/7/29DataMining:ConceptsandTechniques66.1.3关联规则挖掘：一个路径图2020/7/29DataMining:ConceptsandTechniques72020/7/29DataMining:ConceptsandTechniques82020/7/29DataMining:ConceptsandTechniques92020/7/29DataMining:ConceptsandTechniques106.2单维关联规则挖掘算法最简单形式的关联规则挖潜方法：关联规则是单维、单层、布尔关联规则。2020/7/29DataMining:ConceptsandTechniques116.2.1Apriori:一种候选产生-测试方法Apriori性质：频繁项集的任何子集必须是频繁的。如果{beer,diaper,nuts}是频繁的,{beer,diaper}也是。每个包含{beer,diaper,nuts}的事务也包含{beer,diaper}。Apriori剪枝原则:如果一个项集不是频繁的,将不产生/测试它的超集－反单调性。方法:由长度为k的频繁项集产生长度为(k+1)的候选项集,并且根据DB测试这些候选。性能研究表明了它的有效性和可伸缩性。Agrawal&Srikant1994,Mannila,etal.19942020/7/29DataMining:ConceptsandTechniques12Apriori算法：通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集Lk的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。2020/7/29DataMining:ConceptsandTechniques131.Apriori算法—一个例子数据库TDB第1次扫描C1L1L2C2C2第2次扫描C3L3第3次扫描TidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2最小支持度=22020/7/29DataMining:ConceptsandTechniques142.Apriori算法算法伪代码:Ck:长度为k的候选项集Lk:长度为k的频繁项集L1={频繁项};for(k=1;Lk!=;k++)dobeginCk+1=由Lk产生的候选;foreach数据库中的事务tdo增加包含在t中的所有候选Ck+1的计数Lk+1=Ck+1中满足min_support的候选endreturnkLk;2020/7/29DataMining:ConceptsandTechniques153.Apriori的重要细节如何产生候选?步骤1:Lk的自连接步骤2:剪枝入何对候选的支持度计数?候选产生的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3abcd：由abc和abdacde：由acd和ace剪枝:acde被删除,因为ade不在L3C4={abcd}L4的每个频繁项的子集都应在L3中。2020/7/29DataMining:ConceptsandTechniques164.如何产生候选?假定Lk-1中的项集已排序步骤1:Lk-1自连接insertintoCkselectp.item1,p.item2,…,p.itemk-1,q.itemk-1fromLk-1p,Lk-1qwherep.item1=q.item1,…,p.itemk-2=q.itemk-2,p.itemk-1q.itemk-1在p和q中，前K-2项相同，且p的第k-1项少于q的第k-1项值。Step2:剪枝forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk2020/7/29DataMining:ConceptsandTechniques175.完整的Apriori算法(1)L1={频繁1项集};(2)for(k=2;Lk-1;k++)dobegin(3)Ck=apriori_gen(Lk-1);//新的潜在频繁项集(4)foralltransactionstDdobegin(5)Ct=subset(Ck,t);//t中包含的潜在频繁项集(6)forallcandidatescCtdo(7)c.count++;(8)end;(9)Lk={cCk|c.countminsup}(10)end;2020/7/29DataMining:ConceptsandTechniques18D：2020/7/29DataMining:ConceptsandTechniques192020/7/29DataMining:ConceptsandTechniques206.2.2由频繁项集产生关联规则2020/7/29DataMining:ConceptsandTechniques212020/7/29DataMining:ConceptsandTechniques22关联规则的可视化:PaneGraph2020/7/29DataMining:ConceptsandTechniques23关联规则的可视化:RuleGraph2020/7/29DataMining:ConceptsandTechniques246.2.3提高Apriori算法的有效性频繁模式挖掘的挑战挑战事务数据库的多遍扫描数量巨大的候选候选支持度计数繁重的工作量改进Apriori:基本思想减少事务数据库的扫描遍数压缩候选数量便于候选计数2020/7/29DataMining:ConceptsandTechniques251.基于Hash的技术一种基于Hash的技术可以用于压缩候选k－项集Ck（k＞1）。2020/7/29DataMining:ConceptsandTechniques26由C1中的候选1－项集产生1－项集L1时，可以对每个事务产生所有的2－项集。Hash函数：h(Ii,Ij)=(i*10+j)mod7若支持度=3，则0、1、3和4桶中的项集不可能是频繁的。频繁项：{I2,I3}:4、{I1,I2}:4、{I1,I3}:42020/7/29DataMining:ConceptsandTechniques272.事务压缩不包含任何k－项集的事务不可能包含任何k+1－项集。这样，这种事务在其后的考虑时，可以加上标记或删除。因为为产生j－项集（j＞k），扫描数据库时不再需要它们。2020/7/29DataMining:ConceptsandTechniques283.划分:只扫描数据库两次项集在DB中是频繁的,它必须至少在DB的一个划分中是频繁的扫描1:划分数据库,并找出局部频繁模式。扫描2:求出全局频繁模式。2020/7/29DataMining:ConceptsandTechniques294.选样计算频繁模式选取给定数据库D的随机样本S，然后，在S而不是D中找频繁项集。牺牲一些精度换取了有效性。2020/7/29DataMining:ConceptsandTechniques305.动态项集计数将数据库划分为标记开始点的块。不像Aprior仅在每次完整的数据库扫描之前确定新的候选，在这种变形中，可以在任何开始点添加新的候选项集。如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。2020/7/29DataMining:ConceptsandTechniques31频繁模式挖掘的瓶颈多遍数据库扫描是昂贵的。挖掘长模式需要很多遍扫描,并产生大量候选。挖掘频繁模式i1i2…i100扫描次数:100候选个数:(1001)+(1002)+…+(110000)=2100-1=1.27*1030!瓶颈:候选产生-测试。能够避免候选产生吗?6.2.4不产生候选挖掘频繁项集2020/7/29DataMining:ConceptsandTechniques32挖掘频繁模式而不产生候选使用局部频繁的项,由短模式增长产生长模式“abc”是频繁模式得到包含“abc”的所有事务:DB|abc“d”是DB|abc中的局部频繁项abcd是频繁模式2020/7/29DataMining:ConceptsandTechniques33由事务数据库构造FP－树（Frequent－Patterntree）{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1HeaderTableItemfrequencyheadf4c4a3b3m3p3min_support=3TIDItemsbought(ordered)frequentitems100{f,a,c,d,g,i,m,p}{f,c,a,m,p}200{a,b,c,f,l,m,o}{f,c,a,b,m}300{b,f,h,j,o,w}{f,b}400{b,c,k,s,p}{c,b,p}500{a,f,c,e,l,p,m,n}{f,c,a,m,p}1.扫描DB一次,找出频繁1-itemset(单个项的模式)2.按频率的降序将频繁项排序,得到f-list3.再次扫描DB,构造FP－树F-list=f-c-a-b-m-p2020/7/29DataMining:ConceptsandTechniques34FP－树结构的优点完全性保留频繁模式挖掘的完整信息。不截断任何事务的长模式。压缩性压缩无关信息—非频繁的项被删除。项按频率的降序排列:越是频繁出现,越可能被共享。绝对不比原来的数据库大(不计结点链和计数字段)。对于Connect-4DB,压缩率超过100。2020/7/29DataMining:ConceptsandTechniques35基本思想(分而治之)用FP-tree地归增长频繁集方法对每个项，生成它的条