关联分析与频繁模式挖掘

《关联分析与频繁模式挖掘》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一讲　关联规则邓志鸿北京大学信息科学技术学院16九月2021内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估关联规则1993年SIGMOD大会上Agrawal等人首次提出关联规则挖掘(associationrulemining)目的：发现数据中内在的规律性人们通常会同时购买什么样的商品？—Beeranddiapers?购买微机后，接下来用户通常会有什么购物行为？哪种DNA对某个新药敏感？应用Basketdataanalysis,cross-marketing,catalogdesign,salecampaignanaly

2、sis,Weblog(clickstream)analysis,andDNAsequenceanalysis.核心任务频繁模式(Frequentpattern)在数据集（库）中频繁出现的模式（项集(asetofitems)、子序列(subsequences)、子结构(substructures)等）。内容简介基本概念频繁模式挖掘基本方法基本内容频繁模式挖掘关联规则生成模式评估基本概念AssociationRuleAnalysis给定事务集合，根据某些项的出现来预测其它项的出现Market-BaskettransactionsExampleofAss

3、ociationRules{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个项的集合基本概念包含关系令T为一事务，P为一项集。称T包含P，如果P是

4、T的子集记TP或PT支持度计数(Supportcount)事务数据库中包含某个项集的事务的个数例如：({Milk,Bread,Diaper})=2支持度(Support)事务数据库中包含某个项集的事务占事务总数的比例。例如：s({Milk,Bread,Diaper})=2/5频繁项集(FrequentItemset)令P为任何一个项集，称P为频繁项集，如果P的支持度不小于指定的最小阈值(minsupthreshold)基本概念Example:关联规则(AssociationRule)表达形式：XY(s,c)其中，X和Y都是项集，s是规则的支

5、持度，c是置信度例子：{Milk,Diaper}{Beer}(0.4,0.67)规则评估度量指标支持度－Support(s)同时包含X和Y的事务占事务总数的比例置信度－Confidence(c)在所有包含X的事务中包含Y的事务所占比例内容简介基本概念关联分析基本方法基本内容频繁模式挖掘关联规则生成模式评估关联规则分析－内容给定一个事务数据库TD，关联规则挖掘的目标是要找到所有支持度和置信度都不小于指定阈值的规则。支持度≥minsupthreshold置信度≥minconfthreshold穷举法(Brute-forceapproach)列出所有可

6、能的规则对每条规则计算其支持度和置信度通过阈值minsup和minconf过滤无效规则可计算性？计算复杂性分析给定d个不同项：项集数目等于2d所有可能的关联规则总数等于：如果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=

7、0.4,c=0.5){Milk}{Diaper,Beer}(s=0.4,c=0.5)思考所有规则都对应于把同一项集分成两个部分{Milk,Diaper,Beer}源自同一项集的规则有相同的支持度，但是置信度不同因此，我们可以分别处理对支持度和置信度的要求XYs=s(XY)/

8、DB

9、,c=s(XY)/s(X)关联规则分析分两步执行：挖掘频繁项集－生成所有支持度minsup的项集构造规则－用每个频繁项集生成高置信度的规则－对频繁模式的每次分割（一分为二）就形成一条规则，再判断该规则是否满足最小置信度阈值条件。但是，挖掘频繁模式仍然是一个“计算

10、昂贵”的工作。{Milk,Diaper,Beer}s=0.4{Milk}s=0.8{Milk}{Diaper,Beer}