数据挖掘第六章ppt

2006年11月17日星期五DataMining:ConceptsandTechniques1数据挖掘概念与技术——第六章——JiaweiHan（加）著MichelineKamber第六章挖掘大型数据库中的关联规则„关联规则挖掘„由事务数据库挖掘单维布尔关联规则„由事务数据库挖掘多层关联规则„由事务数据库和数据仓库挖掘多维关联规则„有关联挖掘到相关分析„基于约束的关联规则„小结2006年11月17日星期五DataMining:ConceptsandTechniques3什么是关联挖掘?„关联规则挖掘:„从事务数据库,关系数据库和其他信息数据库中找出项目集和对象集中的频繁模式,关连,相关联系„应用:„购物篮数据分析,交差营销,价目表设置,聚类分类等等„例子:„规则形式:“Body→Ηead[支持度,置信度]”.„buys(x,“diapers”)→buys(x,“beers”)[0.5%,60%]„major(x,“CS”)^takes(x,“DB”)→grade(x,“A”)[1%,75%]2006年11月17日星期五DataMining:ConceptsandTechniques4关联规则:基本概念„假设:(1)事务数据库,(2)每一个事务是一个项目集列表(顾客一次购买的商品集)„找出:所有的使目前的项集与另一个项集相关联的规则„例如,98%的人们买了轮胎和汽车附件也会需要汽车的维修服务„应用„*⇒维修协议(商店应该怎样做才能提升维修协议的销售)„家电⇒*(商店应该增加其它那些产品的存储量?)„直接买卖的附加邮递2006年11月17日星期五DataMining:ConceptsandTechniques5规则度量:支持度和置信度„找出所有具有昀小支持度和置信度的规则X&Y⇒Z„支持度s,一个事务中包含X∪Y∪Z的可能性„信任度c,一个事务包含X∪Y,同时包含Z的百分比TID项ID列表2000A,B,C1000A,C4000A,D5000B,E,F设和昀小支持度为50%,昀小置信度为50%,我们有„A⇒C(50%,66.6%)„C⇒A(50%,100%)Customerbuysdiaper两者都买的顾客买啤酒的顾客2006年11月17日星期五DataMining:ConceptsandTechniques6关联规则挖掘:一个路线图„布尔关联和量化关联(根据规则中所处理的值类型)„buys(x,“SQLServer”)^buys(x,“DMBook”)→buys(x,“DBMiner”)[0.2%,60%]„age(x,“30..39”)^income(x,“42..48K”)→buys(x,“PC”)[1%,75%]„单维关连和多维关联(见以上例子)„单层和多层关联„什么牌子的啤酒和什么牌子的尿布相关联？„各种扩充„相关性和因果关系分析„关联并不一定必须意味着相关性和因果性„昀大模式和闭项集„强制的约束„E.g.,小销售(sum100)引起了大买卖(sum1,000)?2006年11月17日星期五DataMining:ConceptsandTechniques7第六章挖掘大型数据库中的关联规则„关联规则挖掘„由事务数据库挖掘单维布尔关联规则„由事务数据库挖掘多层关联规则„由事务数据库和数据仓库挖掘多维关联规则„有关联挖掘到相关分析„基于约束的关联规则„小结2006年11月17日星期五DataMining:ConceptsandTechniques8挖掘关联规则的一个例子对于规则A⇒C:支持度=支持度({A∪C})=50%置信度=支持度({A∪C})/支持度({A})=66.6%Apriori算法原理:任何一个频繁项集的子集必定是频繁项集TID项ID列表2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度{A}75%{B}50%{C}50%{A,C}50%昀小支持度50%昀小置信度50%2006年11月17日星期五DataMining:ConceptsandTechniques9挖掘频繁项集:关键步„找出频繁相集:具有昀小支持度的项目集„一个频繁项集的子集必定是频繁项集„如:如果{AB}是频繁项集,那么{A},{B}都是频繁项集.„使用从1到k的候选集交互式的产生频繁项集„由频繁项集产生关联规则2006年11月17日星期五DataMining:ConceptsandTechniques10Apriori算法„连接步:通过连接产生Ck„剪枝步:如果一个候选k-项集的(k-1)-子集不在(k-1)-的频繁项集中,则该候选集也不可能是频繁的,从而由Ck删除„Pseudo-code:Ck:大小为k的候选集Lk:大小为k的频繁项集L1={频繁项集};for(k=1;Lk!=∅;k++)dobeginCk+1=从Lk中产生的候选集;foreachtransactiont∈Ddo对于包含在t中的属于Ck+1的所有候选集的计数加一Lk+1=Ck+1中具有昀小支持度的候选集endreturn∪kLk;2006年11月17日星期五DataMining:ConceptsandTechniques11Apriori算法—例子TIDItems100134200235300123540025数据库Ditemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3扫描DC1L1itemset{12}{13}{15}{23}{25}{35}itemsetsup{12}1{13}2{15}1{23}2{25}3{35}2itemsetsup{13}2{23}2{25}3{35}2L2C2C2扫描DC3L3itemset{235}扫描Ditemsetsup{235}22006年11月17日星期五DataMining:ConceptsandTechniques12怎样产生候选集?„假设Lk-1中的项是按顺序列出的„第一步:自我连接Lk-1InsertintoCkselectp.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„第二步:剪枝步对于Ck中的所有项集cdo对于c的所有(k-1)子集sdoif(s不在Lk-1中)then从Ck中删除c2006年11月17日星期五DataMining:ConceptsandTechniques13怎样计算候选集的支持度?„为什麽计算候选集的支持度是一个问题?„候选集的总数目可能非常大„一个事务可以包含许多的候选集„方法:„候选集存储在哈希树中„包含项集和计数列表„内部结点包含了一个哈希表„子集函数:找出包含在一个事务中的所有候选集2006年11月17日星期五DataMining:ConceptsandTechniques14产生候选集的例子„L3={abc,abd,acd,ace,bcd}„自我连接:L3*L3„由abc和abd产生abcd„由acd和ace产生acde„剪枝:„删除acde因为ade不在L3„C4={abcd}2006年11月17日星期五DataMining:ConceptsandTechniques15提高Apriori的有效性的方法„散列项集计数:如果一个k-项集对应的哈希桶计数低于支持度阈值,则它不可能是频繁的„事务压缩:不包含任何k-项集的事务在以后的扫描中是无用的„划分:任何项集如果在DB中是潜在频繁的,那么它至少在DB中的一个划分中是频繁的„选样:在给定数据的一个子集上进行挖掘,低支持阈值+好的策略可以得到完整的频繁项集„动态项集计数:如果一个项集的所有子集已被确定为频繁的,则添加大作为新的候选2006年11月17日星期五DataMining:ConceptsandTechniques16Apriori算法足够的快吗?—瓶颈问题的产生„Apriori算法的核心:„使用频繁(k-1)-项集产生候选k-项集„使用数据库扫描和模式匹配为候选项集收集计数„Apriori算法中的瓶颈问题:候选集的产生„大量的候选集:„104个频繁1-项集将生成107个候选2-项集„为了发现一个大小为100的频繁模式,如,{a1,a2,…,a100},需要产生2100≈1030个候选集„数据库的多遍扫描:„需要(n+1)遍扫描,n是昀长项集的长度2006年11月17日星期五DataMining:ConceptsandTechniques17不产生候选挖掘频繁项集„把一个大型的数据库压缩到一棵频繁模式树(FP-树)„高浓缩,但对频繁项集挖掘是完整的„避免了高花销的数据库扫描„产生了一个高效的,基于FP-树的频繁模式挖掘方法„分治策略:把挖掘任务分解成小的任务„避免候选集的产生:只检测子数据库2006年11月17日星期五DataMining:ConceptsandTechniques18从事务数据库中构造一个FP-树{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1索引表项支持度计数节点链f4c4a3b3m3p3昀小支持度=0.5TIDItemsbought(排序的)频繁项集100{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}{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-项集(单项模式)2.频繁项的集合按支持度计数的递减顺序排序3.再一次扫描DB,构造FP-树2006年11月17日星期五DataMining:ConceptsandTechniques19FP-树结构的优点„完整性:„不会破坏任何交易的长模式„为频繁模式挖掘保存了完整的信息„简洁性„减少了不相关的信息—非频繁项集被删掉„频繁项集按支持度递减顺序排列:越是频繁的项集越有可能被共享„不会比原数据库大(如果不算节点链和计数)„例如:对相联的4个数据库，压缩率将超过1002006年11月17日星期五DataMining:ConceptsandTechniques20使用FP-树挖掘频繁模式„基本思想(分治策略）：„使用FP-树循环的产生频繁模式路径„方法„对于每一个项,先构造它的条件模式基,然后构造它的条件FP-树„在每一个新创建的条件FP-树上重复此过程„直到结果FP树为空,或它只包含一条路径(单路径将产生所有的它的子路径的结合,每一条子路径都是一个频繁模式)2006年11月17日星期五DataMining:ConceptsandTechniques21挖掘FP-树的主要步骤1)为FP-树中的每一个节点构造条件模式基2)为每一个条件模式基条件FP-树3)循环的挖掘条件FP-树，生成至今为止获得的频繁模式ƒ如果条件FP-树只包含单条路径，简单的列举所有的模式2006年11月17日星期五DataMining:ConceptsandTechniques22第一步:从FP-树到条件模式基„从FP-树的频繁项头表开始„跟随每一个频繁项的链遍历FP-树„聚集项的所有变换的前缀路径来形成条件模式基条件模式基item条件模式基cf:3afc:3bfca:1,f:1,c:1mfca:2,fcab:1pfcam:2,cb:1{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1项头表Itemfrequencyheadf4c4a3b3m3p32006年11月17日星期五DataMining:ConceptsandTechniques23用于条件模式基构造的FP-树的属性„节点链属性„对任意的频繁项ai,包含ai的所有可能的频繁模式可以通过追随ai的节点链获得