挖掘大型数据库中的关联规则(武汉大学-李春葆)

2020/3/4DataMining:ConceptsandTechniques1第6章：挖掘大型数据库中的关联规则2020/3/4DataMining:ConceptsandTechniques26.1关联规则挖掘关联规则挖掘寻找给定数据集中项之间的有趣联系。事务ID购买项1A,B,C2A,C3A,D……事实表：数据集指所有记录，A、B、C等为项。找项之间的联系。元组（或记录）2020/3/4DataMining:ConceptsandTechniques3购物篮分析：2020/3/4DataMining:ConceptsandTechniques4如关联规则：购买计算机的用户同时购买金融管理软件。支持度为2％：支持度(AB)=(包含A和B的元组数)/(元组总数)置信度为60％：置信度(AB)=(包含A和B的元组值)/(包含A的元组值)。（6.1）2020/3/4DataMining:ConceptsandTechniques56.1.1什么是关联规则挖掘?关联规则挖掘:发现事务数据库,关系数据,或其它信息库中项或数据对象集合间的频繁模式,关联,相关,或因果关系结构。频繁模式:在数据库中频繁出现的模式（项集、序列等）动机:发现数据中的规律性哪些产品更经常一起购买?购买了PC后,哪些将相继购买?什么类型的DNA对新药敏感?我们能自动地对Web稳当分类吗?如果某食品商店通过购物篮分析得知“大部分顾客会在一次购物中同时购买面包和牛奶”，那么该食品商店通过降价促销面包有可能同时提高面包和牛奶的销量。2020/3/4DataMining:ConceptsandTechniques6许多基本的数据挖掘任务的基础关联、相关、因果关系。序列模式、时间或周期关联、局部周期性、空间和多媒体关联。关联分类、聚类分析等。广泛的应用购物篮数据分析、交叉销售、分类设计、销售活动分析。Web日志（点击流）分析、DNA序列分析等。2020/3/4DataMining:ConceptsandTechniques76.1.2基本概念:频繁模式和关联规则Itemset（项集）X={x1,…,xk}找出满足最小支持度和置信度的所规则XY：支持度s,事务包含XY的概率置信度c,事务含X也包含Y的条件概率.设min_support=50%,min_conf=50%:AC(50%,66.7%)CA(50%,100%)顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,F2020/3/4DataMining:ConceptsandTechniques8挖掘关联规则—一个例子规则AC:支持度=support({A}{C})=50%置信度=support({A}{C})/support({A})=66.6%最小支持度50%，计数为2最小置信度50%，计数为2Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%2020/3/4DataMining:ConceptsandTechniques96.1.3关联规则挖掘：一个路径图购买计算机的用户，购买金融管理软件；支持度为2％，置信度为60％布尔值类型2020/3/4DataMining:ConceptsandTechniques106.1.3关联规则挖掘：一个路径图（6.4）离散化的值类型2020/3/4DataMining:ConceptsandTechniques11单维关联规则2020/3/4DataMining:ConceptsandTechniques12如果规则涉及两个或多个维，则称为多维关联规则：该规则涉及age、income、buys三个维。2020/3/4DataMining:ConceptsandTechniques13（6.6）（6.7）其中age、购买商品都是维，具有概念分层。2020/3/4DataMining:ConceptsandTechniques146.2单维关联规则挖掘算法最简单形式的关联规则挖潜方法：关联规则是单维、单层、布尔关联规则。主要介绍Apriori算法，由Agrawal等人在1993／1994年提出的。其核心思想是采用逐层搜索策略产生所有频繁项集。频繁出现的项集。量化方法：大于某个支持度的项集。2020/3/4DataMining:ConceptsandTechniques156.2.1Apriori:一种候选产生-测试方法Apriori性质：频繁项集的任何子集必须是频繁的。如果{beer,diaper,nuts}是频繁的,{beer,diaper}也是。每个包含{beer,diaper,nuts}的事务也包含{beer,diaper}。定理如果一个项集Ii是频繁项集，则它的所有非空子集Ij一定也是频繁项集。该定理也称为Apriori性质。证明：∴sup_count(Ij)≥sup_count(Ii)∵sup_count(Ii)≥n×min_sup∴sup_count(Ij)≥n×min_sup证毕。最小支持度计数n为总的元数组2020/3/4DataMining:ConceptsandTechniques16Apriori剪枝原则:如果一个项集不是频繁的,将不产生/测试它的超集，称为反单调性。如{ac}不是频繁的，则{abc}、{acd}不是频繁的。方法:由长度为k的频繁项集产生长度为(k+1)的候选项集,并且根据DB测试这些候选。2020/3/4DataMining:ConceptsandTechniques17Apriori算法：通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集Lk的项集组成的集合。由Ck产生Lk。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。先验算法2020/3/4DataMining:ConceptsandTechniques181.Apriori算法—两个例子事实表第1次扫描C1L1L2C2C2第2次扫描C3L3第3次扫描TidItems10A,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}2设最小支持计数=22020/3/4DataMining:ConceptsandTechniques192020/3/4DataMining:ConceptsandTechniques20所有频繁项集：{{I1},{I2},{I3},{I4},{I5}{I1,I2},{I1,I3},{I1,I5},{I2,I3},{I2,I4},{I2,I5}{I1,I2,I3},{I1,I2,I5}}2020/3/4DataMining:ConceptsandTechniques212.Apriori算法算法伪代码:Ck:长度为k的候选项集Lk:长度为k的频繁项集L1={频繁项};for(k=1;Lk!=;k++)dobeginCk+1=由Lk产生的候选;foreach数据库中的事务tdo增加包含在t中的所有候选Ck+1的计数Lk+1=Ck+1中满足min_support的候选endreturnkLk;求每个k+1项集的计数仅选中大于等于最小支持度的k+1项集2020/3/4DataMining:ConceptsandTechniques223.Apriori的重要细节如何产生候选?步骤1:Lk的自连接步骤2:剪枝如何对候选的支持度计数?候选产生的例子L3={abc,abd,acd,ace,bcd}自连接:L3L3abcd：由abc和abdacde：由acd和ace剪枝:acde被删除,因为ade不在L3C4={abcd}L4的每个频繁项的子集都应在L3中。2020/3/4DataMining:ConceptsandTechniques234.如何产生候选?假定Lk-1中的项集已排序步骤1:Lk-1自连接Ck=Lk-1Lk-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在Lk-1（p）和Lk-1（q）中，前k-2项相同，且p的第k-1项小于q的第k-1项值。2020/3/4DataMining:ConceptsandTechniques24普通连接运算：2020/3/4DataMining:ConceptsandTechniques25Apriori算法中的连接运算R：a1a2a3ABAABBABCR：T＝RR[1]=[1]and[2]=[2]and[3][3]T：a1a2a3a4ABABABACABBCa1a2a3ABAABBABC2020/3/4DataMining:ConceptsandTechniques26步骤2:剪枝forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk从Ck中删除其k-1个项为非频繁项集的项集。2020/3/4DataMining:ConceptsandTechniques275.完整的Apriori算法(1)L1={频繁1项集};(2)for(k=2;Lk-1;k++)dobegin(3)Ck=apriori_gen(Lk-1);//新的潜在频繁项集(4)foralltransactionstDdobegin(5)Ct=subset(Ck,t);//t中包含的潜在频繁项集(6)forallcandidatescCtdo(7)c.count++;(8)end;(9)Lk={cCk|c.countminsup}(10)end;2020/3/4DataMining:ConceptsandTechniques28事务表D：2020/3/4DataMining:ConceptsandTechniques29设L3={{1,2,3},{1,2,4},{1,3,4},{1,3,5},{2,3,4}}，求C4和L4。其过程为：L3：{1,2,3}{1,2,4}{1,3,4}{1,3,5}{2,3,4}L3：{1,2,3}{1,2,4}{1,3,4}{1,3,5}{2,3,4}{1,2,3,4}{1,2,4,5}C4={{1,2,3,4},{1,2,4,5}}对于{1,2,3,4}，其3-项子集有：{1,2,3},{1,3,4},{2,3,4},{1,2,4}，均在L3中。对于{1,2,4,5}，其3-项子集有：{1,2,4},{1,2,5}，删除之。所以，L4={{1,2,3,4}}。2020/3/4DataMining:ConceptsandTechniques306.2.2由频繁项集产生关联规则求属性组合。2020/3/4DataMining:ConceptsandTechniques31以第一条规则为例，其置信度=包含I1、I2、I5的元组数（2）包含I1、I2的元组数（4）＝50％2020/3/4DataMining:ConceptsandTechni