数据挖掘2015最新精品课程完整课件(第3讲)---关联规则挖掘的基本概念与算法

关联规则挖掘基本概念与算法从推荐系统(recommendersystem)说起频繁项集关联规则关联规则挖掘的兴起1993年，Agrawal提出了关联规则(AssociationRule)问题，旨在发现顾客购货篮内商品间令人感兴趣的关系。“啤酒和尿布”沃尔玛利用NCR数据挖掘工具意外的发现：跟尿布一起购买最多的商品竟是啤酒！今天，关联规则已广泛应用于金融、营销以及生物信息学等领域。主要内容关联规则的基本概念Apriori算法其它基于Apriori的关联规则挖掘算法关联规则挖掘的动机发现数据内在的关系哪些商品往往被一起购买－－啤酒尿布买了PC机之后，还会购买哪些商品哪些DNA对新药较为敏感什么是关联规则关联规则是寻找给定的数据集中项目之间令人感兴趣的关系购物栏数据库TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke例子{Diaper}{Beer},{Milk,Bread}{Eggs,Coke},{Beer,Bread}{Milk},蕴含并不是因果关系频繁项集•项集•一个或多个项目的集合。例如:{Milk,Bread,Diaper}•包含k个项目的项集称为k-项集•绝对支持度()•某一项集出现的次数比如({Milk,Bread,Diaper})=2•相对支持度•包含某一项集的事务在全体事务中的比例。比如.s({Milk,Bread,Diaper})=2/5•频繁项集•支持度不小于给定最小支持度阈值(minsup)的项集TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke关联规则关联规则形如XY的蕴涵式,其中X和Y是项集，且XY=。比如:{Milk,Diaper}{Beer}规则评价参数支持度(s)同时包含X和Y的事务占全部事务的百分比可信度(c)包含项集X的事务中也包含Y的百分比Example:Beer}Diaper,Milk{4.052|T|)BeerDiaper,,Milk(s67.032)Diaper,Milk()BeerDiaper,Milk,(cTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke关联规则挖掘的一般流程找出满足最小支持度阈值的所有频繁项集。由频繁项集产生满足最小可信度阈值的强关联规则。这两步中，第二步较容易。关联规则挖掘的总体性能由第一步决定。频繁项集的生成--1nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE给定d个项目,可以生成2d候选项集频繁项集的生成--2频繁项集格中每个项集都作为候选频繁项集扫描数据库，计算每个候选集的支持度复杂度~O(NMw)=ExpensivesinceM=2d!!!TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeNTransactionsListofCandidatesMw计算复杂度假设存在d个不同的项目:项集总数=2d规则总数:1231111dddkkdjjkdkdRd=6,R=602频繁项集的生成策略减少候选项集的个数(M)利用各种剪枝方法减少M减少事务的个数(N)随着项集维度的增加，不断减少N的数目减少比较的次数(NM)使用新颖的数据结构存储事务/项集无需在每个事务中匹配每个项集主要内容关联规则的基本概念Apriori算法其它基于Apriori的关联规则挖掘算法Apriori性质--1AgrawalR,SrikantR.Fastalgorithmsforminingassociationrules.(VLDB’94).Apriori性质:频繁项集的所有非空子集都必须也是频繁的。Apriori性质成立的原因:项集的支持度不超过其子集的支持度，即支持度的反单调性。Apriori性质--2FoundtobeInfrequentnullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEnullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEPrunedsupersetsApriori算法--1扫描数据库，找出1-频繁项集连接k-频繁项集生成(k+1)-候选项集在数据库中验证候选集是否频繁当没有候选集或频繁项集生成时结束Apriori算法--2Pseudo-code:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturnkLk;规则生成--1给定频繁项集L,找出所有非空的fL使得fL–f满足最小可信度阈值如{A,B,C,D}为频繁项集,候选规则有:ABCD,ABDC,ACDB,BCDA,ABCD,BACD,CABD,DABCABCD,ACBD,ADBC,BCAD,BDAC,CDAB,若|L|=k,则存在2k–2个候选关联规则规则生成--2可信度一般不满足反单调性c(ABCD)可以比c(ABD)大，也可以比c(ABD)小定理.若规则XY-X不满足最小可信度阈值，则规则X’Y-X’，X’X，也不满足最小可信度阈值。比如,L={A,B,C,D}:c(ABCD)c(ABCD)c(ABCD)规则生成--3：Apriori算法使用一种逐层方法来产生关联规则，其中每层对应规则后件中的项数。算法首先提取规则后件只含一个项的所有高置信度规则，然后使用这些规则来产生新的候选规则。例如使用{abc}→{b}和{abd}→{c}来产生候选规则{ad}→{bc}。规则生成--4合并结论中具有共同前缀的规则，生成候选规则连接(CD=AB,BD=AC)生成候选规则D=ABC若AD=BC的可信度未超过最小可信度阈值则删去D=ABCBD=ACCD=ABD=ABC规则生成--5ABCD={}BCD=AACD=BABD=CABC=DBC=ADBD=ACCD=ABAD=BCAC=BDAB=CDD=ABCC=ABDB=ACDA=BCDLatticeofrulesABCD={}BCD=AACD=BABD=CABC=DBC=ADBD=ACCD=ABAD=BCAC=BDAB=CDD=ABCC=ABDB=ACDA=BCDPrunedRulesLowConfidenceRule支持度—可信度框架的问题强关联规则有可能不是令人感兴趣的CoffeeCoffeeTea15520Tea755809010100TeaCoffeeConfidence=P(Coffee|Tea)=0.75butP(Coffee)=0.9Althoughconfidenceishigh,ruleismisleadingP(Coffee|Tea)=0.9375小结Apriori算法是挖掘频繁项集中最具有影响力的算法。算法有两步骤：一是发现所有的频繁项集；二是生成强关联规则。发现频繁项集是关联规则挖掘中的关键步骤。在Apriori算法中利用“频繁项集的子集是频繁项集，非频繁项集的超集是非频繁项集”这一个性质有效的对频繁项集进行修剪。小结算法核心思想：给定一个数据库，第一次扫描数据库，搜索出所有支持度大于等于最小支持度的项集组成频繁1-项集即为L1，由L1连接得到候选1-项集C1；第二次扫描数据库，搜索出C1中所有支持度大于等于最小支持度的项集组成频繁2-项集即为L2，由L2连接得到候选2-项集C2；同理第k次扫描数据库，搜索出Ck-1中所有支持度大于等于最小支持度的项集组成频繁k-项集即为Lk，由Lk连接得到候选k-项集Ck，直到没有新的候选集产生为止。小结Apriori算法需扫描数据库的次数等于最大频繁项集的项数。Apriori算法有两个致命的性能瓶颈：1.产生的候选集过大(尤其是2-项集)，算法必须耗费大量的时间处理候选项集2.多次扫描数据库，需要很大的1/0负载，在时间、空间上都需要付出很大的代价。频繁模式挖掘的挑战挑战多次扫描事务数据库巨大数量的候选项集繁重的计算候选项集的支持度工作改进Apriori:大体的思路减少事务数据库的扫描次数缩减候选项集的数量使候选项集的支持度计算更加方便主要内容关联规则的基本概念Apriori算法其它基于Apriori的关联规则挖掘算法AprioriTid算法核心AgrawalR,SrikantR.Fastalgorithmsforminingassociationrules.(VLDB’94).AprioriTid算法是在Apriori算法的基础上演化而来的。该算法第一趟扫描数据库时采用Apriori算法，当再次扫描时不再是扫描整个数据库，而只是扫描上次生成的候选项集，扫描的同时还会计算出频繁项集的支持度，以减少扫描数据库的时间来提高算法的效率。AprioriTidAprioriTid算法由Apriori算法改进优点：只和数据库做一次交互，无须频繁访问数据库将Apirori中的Ck扩展，内容由{c}变为{TID，c}，TID用于唯一标识事务，引入Bk，使得Bk对于事务的项目组织集合，而不是被动的等待Ck来匹配2020/2/2633AprioriTid算法举例：minsupp=2数据库：tTID项目1001342002353001235400252020/2/2634AprioriTid算法示例TID项目集100{1}{3}{4}200{2}{3}{5}300{1}{2}{3}{5}400{2}{5}项集支持度{1}2{2}3{3}3{5}32020/2/2635ApioriTid算法示例TID项目集100{{13}}200{{23}{25}{35}}300{{12}{13}{15}{23}{25}{35}}400{{25}}项集支持度{13}2{23}2{25}3{35}22020/2/2636ApioriTid算法示例TID项目集100空200{{235}}300{{235}}400空2020/2/2637ApioriTid算法上面图中分别为Bk和Lk，而Ck和Apriori算法产生的一样，因此没有写出来可以看到Bk由Bk-1得到，无须由数据库取数据缺点：内存要求很大，事务过多的时候资源难以满足例子--1TIDItems1Bread,Milk2Bread,Dia