关联分析与频繁模式挖掘

第十一讲关联规则邓志鸿北京大学信息科学技术学院2016年6月内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估关联规则1993年SIGMOD大会上Agrawal等人首次提出关联规则挖掘(associationrulemining)目的：发现数据中内在的规律性人们通常会同时购买什么样的商品？—Beeranddiapers?购买微机后，接下来用户通常会有什么购物行为？哪种DNA对某个新药敏感？应用Basketdataanalysis,cross-marketing,catalogdesign,salecampaignanalysis,Weblog(clickstream)analysis,andDNAsequenceanalysis.核心任务频繁模式(Frequentpattern)在数据集（库）中频繁出现的模式（项集(asetofitems)、子序列(subsequences)、子结构(substructures)等）。内容简介基本概念频繁模式挖掘基本方法基本内容频繁模式挖掘关联规则生成模式评估基本概念AssociationRuleAnalysis给定事务集合，根据某些项的出现来预测其它项的出现Market-BaskettransactionsTIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeExampleofAssociationRules{Diaper}{Beer},{Milk,Bread}{Eggs,Coke},{Beer,Bread}{Milk},隐含着内在关联，而非偶然现象基本概念项(Item)最小的处理单位例如：Bread,Milk事务(Transaction)由事务号和项集组成例如：1,{Bread,Milk}事务数据库由多个事务组成项集(Itemset)一个或多个项(item)的集例如：{Milk,Bread,Diaper}k-项集(k-itemset)包含k个项的集合TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke基本概念包含关系令T为一事务，P为一项集。称T包含P，如果P是T的子集记TP或PT支持度计数(Supportcount)事务数据库中包含某个项集的事务的个数例如：({Milk,Bread,Diaper})=2支持度(Support)事务数据库中包含某个项集的事务占事务总数的比例。例如：s({Milk,Bread,Diaper})=2/5频繁项集(FrequentItemset)令P为任何一个项集，称P为频繁项集，如果P的支持度不小于指定的最小阈值(minsupthreshold)TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke基本概念Example:Beer}{}Diaper,Milk{4.052|T|)BeerDiaper,,Milk(s67.032)Diaper,Milk()BeerDiaper,Milk,(c关联规则(AssociationRule)表达形式：XY(s,c)其中，X和Y都是项集，s是规则的支持度，c是置信度例子：{Milk,Diaper}{Beer}(0.4,0.67)规则评估度量指标支持度－Support(s)同时包含X和Y的事务占事务总数的比例置信度－Confidence(c)在所有包含X的事务中包含Y的事务所占比例TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估关联规则分析－内容给定一个事务数据库TD，关联规则挖掘的目标是要找到所有支持度和置信度都不小于指定阈值的规则。支持度≥minsupthreshold置信度≥minconfthreshold穷举法(Brute-forceapproach)列出所有可能的规则对每条规则计算其支持度和置信度通过阈值minsup和minconf过滤无效规则可计算性？计算复杂性分析给定d个不同项：项集数目等于2d所有可能的关联规则总数等于：1231111dddkkdjjkdkdR如果d=6则R=602关联规则－分析ExampleofRules:{Milk,Diaper}{Beer}(s=0.4,c=0.67){Milk,Beer}{Diaper}(s=0.4,c=1.0){Diaper,Beer}{Milk}(s=0.4,c=0.67){Beer}{Milk,Diaper}(s=0.4,c=0.67){Diaper}{Milk,Beer}(s=0.4,c=0.5){Milk}{Diaper,Beer}(s=0.4,c=0.5)TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,Coke思考•所有规则都对应于把同一项集分成两个部分{Milk,Diaper,Beer}•源自同一项集的规则有相同的支持度，但是置信度不同•因此，我们可以分别处理对支持度和置信度的要求•XYs=s(XY)/|DB|,c=s(XY)/s(X)关联规则分析分两步执行：1.挖掘频繁项集－生成所有支持度minsup的项集2.构造规则－用每个频繁项集生成高置信度的规则－对频繁模式的每次分割（一分为二）就形成一条规则，再判断该规则是否满足最小置信度阈值条件。但是，挖掘频繁模式仍然是一个“计算昂贵”的工作。{Milk,Diaper,Beer}s=0.4{Milk}s=0.8{Milk}{Diaper,Beer}s=0.4,c=0.4/0.8=0.5关联规则分析的核心内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估频繁模式挖掘－重要性发现数据集中的有价值的重要性质是其它数据挖掘任务的基础关联分析：AssociationrulesanalysisMiningFrequentItemset因果分析：causalityanalysis序列、结构模式：Sequential,structural(e.g.,sub-graph)patterns时空、多媒体、时间序列、流数据模式分析分类聚类数据仓库语义数据压缩推荐系统等其他应用生成频繁项集nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE给定d个项，有2d个可能的候选项集生成频繁项集穷举法(Brute-forceapproach)网格中每个项集都是候选的频繁项集通过扫描一次数据库，可以得到每个候选项集的支持度比较每一条事务和每个候选项集计算复杂度－O(NMw)N为事务数目，M=2d为候选项集，w为一次比较的计算代价TIDItems1Bread,Milk2Bread,Diaper,Beer,Eggs3Milk,Diaper,Beer,Coke4Bread,Milk,Diaper,Beer5Bread,Milk,Diaper,CokeNTransactionsListofCandidatesMw内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估频繁项集挖掘算法Apriori算法第一个算法用了Apriori性质所有挖掘算法的基础基于事务列表的算法Eclat算法基于节点列表的算法PPV算法、Prepost算法Apriori算法候选－生成类型Apriori性质反单调性基本思想由长度为k的频繁模式生成长度为(k+1)的候选模式计算长度为(k+1)的候选模式的支持度，从而获得长度为(k+1)的频繁模式Aprioir算法Apriori性质:如果一个项集是频繁的，那么它的所有子集都是频繁的。也称为反单调性Apriori性质成立的原因如下：任何一个项集的支持度不可能超过其子集的支持度)()()(:,YsXsYXYX发现不频繁nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDEApriori性质－演示nullABACADAEBCBDBECDCEDEABCDEABCABDABEACDACEADEBCDBCEBDECDEABCDABCEABDEACDEBCDEABCDE裁减所有超集Apriori算法－示例1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,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}2Supmin=2Apriori算法－（伪码）描述Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withsupportmin_supportendreturnkLk;Apriori算法－重要细节如何生成候选项集？Step1:自连接(self-joining)LkStep2:裁减(pruning)如何计算候选项集的支持度？例子L3={abc,abd,acd,ace,bcd}Self-joining:L3*L3由abc和abd生成abcd由acd和ace生成acdePruning:因为ade不在L3中，所以不用处理acde（它不可能是频繁项集）C4={abcd}Apriori算法－生成候选项集SupposetheitemsinLk-1arelistedinanorderStep1:self-joiningLk-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Step2:pruni