文本挖掘技术08-关联

1关联分析技术杨建武Email:[e-mail]第八章：文本挖掘技术(2009)北京大学计算机科学技术研究所2关联分析¾关联分析：关联规则挖掘¾关联规则挖掘的典型案例：购物篮问题¾在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将所购买的商品放入到自己的购物篮中。3AExample4关联分析¾通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯™哪些物品经常被顾客购买？™同一次购买中，哪些商品经常会被一起购买？™一般用户的购买过程中是否存在一定的购买时间序列？¾具体应用：利润昀大化™商品货架设计：更加适合客户的购物路径™货存安排：实现超市的零库存管理™用户分类：提供个性化的服务5关联规则挖掘¾简单的说，关联规则挖掘就是发现大量数据中项集之间有趣的关联™在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。¾应用™购物篮分析、交叉销售、分类设计等™两种策略：•商品放近，增加销量•商品放远，增加其他商品的销量6关联规则挖掘形式化定义设I={i1,i2,…,im}是项(item)的集合。¾若干项的集合，称为项集（ItemSets）.¾记D为交易(transaction,事务)T的集合，其中，交易T是项的集合，并且T⊆I。¾对应每一个交易有唯一的标识，如交易号，记作TID。¾设X是一个I中项的集合，如果X⊆T，那么称交易T包含X。¾寻找：有趣的关联规则(强规则).7关联规则¾所有形如X⇒Y蕴涵式的称为关联规则，这里X⊂I,Y⊂I，并且X∩Y=Φ。¾关联规则是有趣的,如果它满足昀小支持度阈值与昀小置信度阈值,并称之为强规则8支持度与置信度为了描述关联规则的有用性和确定性。¾关联规则的支持度™如果交易数据库D中s的交易包含A∪B，则称规则A⇒B在事务集D上的支持度为s。Support(A⇒B)=P(A∪B)¾关联规则的置信度™如果交易数据库D中，包含A的交易中有c(%)的交易同时也包含B，称规则的置信度为c。（条件概率）Confidence(A⇒B)=P(B|A)=support({A}∪{B})/support({A})（注：这里的U是指在交易中同时出现{A}和{B}）9关联规则例子¾查找所有的规则A⇒C具有昀小支持度和可信度™支持度,s,一次交易中包含{A、C}的可能性™置信度,c,包含{A}的交易中也包含C的条件概率交易ID购买的商品10A,B,C20A,C30A,D40B,E,F买尿布的客户二者都买的客户买啤酒的客户10™ruleA⇒C:•support=support({A}∪{C})=50%•confidence=support({A}∪{C})/support({A})=66.7%™ruleC⇒A(50%,100%)Min.support50%Min.confidence50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FSupport{A}75%3{B}50%222{C}50%{A,C}50%Frequentpattern关联规则例子11挖掘关联规则方法12频繁项集¾项集(Itemset):asetofitems™例如acm={a,c,m},sup=3¾频繁项集（高频项集）™如果项集满足昀小支持度，则称之为频繁项集项集TIDItemsbought100f,a,c,d,g,I,m,p200a,b,c,f,l,m,o300b,f,h,j,o400b,c,k,s,p500a,f,c,e,l,p,m,n™如果min_sup=3,则acm是频繁项集¾如果频繁项集中包含K个项，则称为频繁K－项集13关联规则挖掘¾关联规则的挖掘步骤™发现频繁项集™由频繁项集生成满足昀小支持度和昀小置信度的关联规则¾发现频繁项集直接的方法™产生所有可能的项集,并测试它们的支持度™100个项Æ2100-1可能项集14Apriori性质Agrawal&Srikant1994,Mannila,etal.1994¾Apriori性质：一个频繁项集中任一非空子集也应是频繁项集。™如果一项交易包含{牛奶，面包，汽水}，那么它一定包含{牛奶，面包}™{牛奶，面包，汽水}是频繁的Æ{牛奶，面包}一定也是频繁的¾也就是说,任何非频繁项集的超集一定也是非频繁的™非频繁项集的超集可以不用进行测试™许多项之间的组合可以去掉（不满足频繁条件）15Apriori方法¾寻找昀大频繁集¾逐层搜索的迭代方法。¾用k-项集探求(k+1)-项集。¾具体地：™首先找出频繁1-项集，该集合记为L1;™用L1找出频繁2-项集的集合L2；™如此继续下去，直到找到昀大频繁项集¾该方法，主要有连接和剪枝两步构成。16TheAprioriAlgorithm¾Ck:Candidateitemsetofsizek¾Lk:frequentitemsetofsizek¾L1={frequentitems};¾for(k=1;Lk!=∅;k++)do™Ck+1=candidatesgeneratedfromLk;™foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedint™Lk+1=candidatesinCk+1withmin_support¾return∪kLk;17产生候选集¾L3={abc,abd,acd,ace,bcd}¾Self-joining:L3*L3™abcdÅabc*abd™acdeÅacd*ace¾Pruning:™ForeachitemsetcinCkdo•Foreach(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk™acdeisremovedbecauseadeisnotinL3¾C4={abcd}18DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,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}2TheAprioriAlgorithm—AnExample19Apriori性能瓶颈¾Apriori算法的核心:™用频繁的(k–1)-项集生成候选的频繁k-项集™用数据库扫描和模式匹配计算候选集的支持度¾Apriori的瓶颈:candidate-generation-and-test™巨大的候选集:•104个频繁1-项集要生成107个候选2-项集•要找尺寸为100的频繁模式，如{a1,a2,…,a100},你必须先产生2100≈1030个候选集™多次扫描数据库：•如果昀长的模式是n的话，则需要(n+1)次数据库扫描¾Canweavoidcandidategeneration?20¾模式增长的特征™令α为DB的一个频繁集，B为α的条件模式库，β是B中的一个项，要使α∪β是DB中的频繁集，当且仅当β是B的频繁项.¾例：“abcdef”是频繁集,当且仅当™“abcde”是频繁集,且™“f”在包含“abcde”的事务中是频繁的。™（注：支持度按个数算，而不是百分比）MiningFrequentPatternsWithoutCandidateGeneration21频繁模式增长算法¾frequent-patterngrowth（FP-增长）™基于FP-tree（频繁模式树）™将提供频繁集的数据库压缩到一棵FP-tree，但仍保留项集关联信息；™将压缩后的数据分成一组条件数据库（一种特殊类型的投影数据库），每个关联到一个频繁项集；™分别挖掘每个条件数据库22{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p3min_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}{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.扫描数据库一次，得到频繁1-项集2.把项按支持度递减排序3.再一次扫描数据库，建立FP-tree构造FP-tree次数23基于FP-tree的频繁集挖掘算法¾基本思想(分而治之)™用FP-tree递归增长频繁集¾方法™对每个项，生成它的条件模式库™用条件模式库构造对应的条件FP-tree™对每个新生成的条件FP-tree，重复这个步骤™直到结果FP-tree为空,或只含唯一的一个路径(此路径的每个子路径对应的相集都是频繁集)24¾从FP-tree的头表开始¾按照每个频繁项的连接遍历FP-tree¾列出能够到达此项的所有前缀路径，得到条件模式库条件模式库itemcond.patternbasecf: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头表Itemfrequencyheadf4c4a3b3m3p3步骤1:从FP-tree到条件模式库25FP-tree支持条件模式库构造的属性¾节点链接™任何包含ai,的可能频繁集，都可以从FP-tree头表中的ai沿着ai的节点链接得到¾前缀路径™要计算路径P中包含节点ai的频繁集，只要考察到达ai的路径前缀即可，且其支持度等于节点ai的支持度26¾对每个条件模式库™计算库中每个项的支持度™用模式库中的频繁项建立该条件FP-treem-条件模式库:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsrelatetomm,fm,cm,am,fcm,fam,cam,fcam¼¼{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p3步骤2:建立条件FP-tree27EmptyEmptyf{(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条件模式库项通过建立条件模式库得到频繁集28{}f:3c:3a:3m-条件FP-tree“am”的条件模式库:(fc:3){}f:3c:3am-条件FP-tree“cm”的条件模式库:(f:3){}f:3cm-条件FP-tree“cam”条件模式库:(f:3){}f:3cam-条件FP-tree第3步:递归挖掘条件FP-tree29¾假定一个(条件)FP-treeT有一个共享唯一前缀路径P¾挖掘可分解为如下两个步骤™用一个节点代替此前缀路径P™分别计算这两个部分的结果¼a2:n2a3:n3a1:n1{}b1:m1C1:k1C2:k2C3:k3b1:m1C1:k1C:kC:kr1+a2:n2a:na1:n1{}223333r1=特例:FP-tree中的唯一前缀路径30FP-tree结构的好处¾完备:™不会打破交易中的任何模式™包含了序列模式挖掘所需的全部信息¾紧密™去除不相关信息—不包含非频繁项™支持度降序排