5 数据挖掘技术-大型数据库中的关联规则

1第5章挖掘大型数据库中的关联规则2自然界中某种事物发生时其他事物也会发生的这样一种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）关联分析目的是寻找给定数据记录集中数据项之间隐藏的关联关系，描述数据之间的密切度。基本概念3关联分析关联分析的结果常有两种：关联规则和序列模式。关联规则用于寻找在同一个事件中出现的不同项的相关性；序列模式与此类似，但它寻找的是事件之间时间上的相关性。4关联规则发现的主要对象是交易型数据库，一个交易一般由交易处理时间，一组顾客购买的物品，有时也有顾客标识号(如信用卡号)组成。关联规则:是描述在一个交易中物品之间同时出现的规律的知识模式，更确切的说，关联规则是通过量化的数字描述物品X的出现对物品Y的出现有多大的影响。关联规则5以零售业为例，体育用品商场通过对销售数据进行关联分析通常可以发现这些数据中常常隐含形式如下的规律——“购买篮球的顾客中有70%的人同时购买篮球运动服，所有交易中有40%的人同时购买篮球和篮球运动服”等等。这些规律即关联规则。关联规则6关联规则度量—置信度定义：规则XY在交易数据集D中的置信度是对关联规则准确度的衡量。度量关联规则的强度。即在所有出现了X的活动中出现Y的频率，即规则XY的必然性有多大。记为：confidence(XY)计算方法：包含X和Y的交易数与包含X的交易数之比：confidence(XY)=P(Y∣X)7关联规则度量—支持度定义：规则XY在交易数据集D中的支持度是对关联规则重要性的衡量，反映关联是否是普遍存在的规律，说明这条规则在所有交易中有多大的代表性。即在所有交易中X与Y同时出现的频率记为：support(XY)。计算方法：交易数据集中同时包含X和Y的交易数与所有交易数之比：support(XY)=P(X∪Y)8最小置信度阈值最小支持度阈值同时满足最小置信度阈值和最小支持度阈值的关联规则为强关联规则，是有意义有价值。关联规则度量9定义：关联规则挖掘的交易数据集记为D（一般为交易数据库），D＝｛T1，T2，…，Tk，…,Tn｝，Tk（k＝1,2,…，n）称为交易，对应每一个交易有唯一的标识，记作TID。元素im（m＝1,2,…，p）称为项。设I={i1，i2，…，im}是D中全体项组成的集合，且TkI。项的集合称为项集。设X是一个I中项的集合，如果XTk，那么称交易Tk包含项集X。包含k个项的项集称为k－项集。项集的出现频率是包含项集的事务数。若项集满足最小支持度，则称它为频繁项集。关联规则形式化定义10交易号（TID）项集合（Itemsets）T100I1，I2，I5T200I2，I4T300I2，I3T400I1，I2，I4T500I1，I3关联规则形式化定义关联规则的挖掘是一个两步的过程：找出所有频繁项集由频繁项集产生强关联规则11关联规则挖掘：一个路线图布尔vs.量化关联(基于处理数据的类型)buys(x,“SQLServer”)^buys(x,“DMBook”)buys(x,“DBMiner”)[0.2%,60%]age(x,“30..39”)^income(x,“42..48K”)buys(x,“PC”)[1%,75%]单维vs.多维关联(基于规则中涉及的数据维)单层vs.多层分析(基于规则集所涉及的抽象层)各种扩展12关联规则挖掘—一个例子对于AC：support=support({A、C})=50%confidence=support({A、C})/support({A})=66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度{A}75%{B}50%{C}50%{A,C}50%最小置信度50%最小支持度50%13Apriori算法连接:用Lk-1自连接得到Ck修剪:一个k-项集，如果他的一个k-1项集（他的子集）不是频繁的，那他本身也不可能是频繁的。伪代码:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturnkLk;14Apriori算法—例子TIDItems100134200235300123540025数据库Ditemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3扫描DC1L1itemset{12}{13}{15}{23}{25}{35}itemsetsup{12}1{13}2{15}1{23}2{25}3{35}2itemsetsup{13}2{23}2{25}3{35}2L2C2C2扫描DC3L3itemset{235}扫描Ditemsetsup{235}215如何生成候选集假定Lk-1中的项按顺序排列第一步:自连接Lk-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第二步:修剪forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk16Apriori够快了吗?—性能瓶颈Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集用数据库扫描和模式匹配计算候选集的支持度Apriori的瓶颈:候选集生成巨大的候选集:104个频繁1-项集要生成107个候选2-项集要找尺寸为100的频繁模式，如{a1,a2,…,a100},你必须先产生21001030个候选集多次扫描数据库：17挖掘频繁集不用生成候选集用Frequent-Patterntree(FP-tree)结构压缩数据库高度浓缩，同时对频繁集的挖掘又完备的将提供频繁项集的数据库压缩到一颗FP-树避免代价较高的数据库扫描18用交易数据库建立FP-tree{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p3最小支持度=50％TIDItemsbought(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-tree19FP-tree结构的好处完备:不会打破交易中的任何模式包含了序列模式挖掘所需的全部信息紧密去除不相关信息—不包含非频繁项支持度降序排列:支持度高的项在FP-tree中共享的机会也高20挖掘FP-tree的主要步骤1)为FP-tree中的每个节点生成条件模式库2)用条件模式库构造对应的条件FP-tree3)递归构造条件FP-trees同时增长其包含的频繁集如果条件FP-tree只包含一个路径，则直接生成所包含的频繁集。21步骤1:从FP-tree到条件模式库从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头表Itemfrequencyheadf4c4a3b3m3p322FP-tree支持条件模式库构造的属性节点裢接任何包含ai,的可能频繁集，都可以从FP-tree头表中的ai沿着ai的节点链接得到前缀路径要计算路径P中包含节点ai的频繁集，只要考察到达ai的路径前缀即可，且其支持度等于节点ai的支持度23步骤2:建立条件FP-tree对每个模式库计算库中每个项的支持度用模式库中的频繁项建立FP-treem-条件模式库:fca:2,fcab:1{}f:3c:3a:3m-conditionalFP-treeAllfrequentpatternsconcerningmm,fm,cm,am,fcm,fam,cam,fcam{}f:4c:1b:1p:1b:1c:3a:3b:1m:2p:2m:1头表Itemfrequencyheadf4c4a3b3m3p324通过建立条件模式库得到频繁集EmptyEmptyf{(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条件模式库项25第3步:递归挖掘条件FP-tree{}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-tree27为什么频繁集增长速度快？我们的性能研究显示FP-growth比Apriori快一个数量级。原因不生成候选集，不用候选测试。使用紧缩的数据结构避免重复数据库扫描基本操作是计数和建立FP-tree树28FP-growthvs.Apriori:相对于支持度的扩展性010203040506070809010000.511.522.53Supportthreshold(%)Runtime(sec.)D1FP-growthruntimeD1AprioriruntimeDatasetT25I20D10K29冰山查询冰山查询:在一个或多个属性上做聚合，只有当聚合的值高于指定的值时才做计算举例：selectP.custID,P.itemID,sum(P.qty)frompurchasePgroupbyP.custID,P.itemIDhavingsum(P.qty)=3用Apriori提高执行冰山查询的效率30多层关联规则项通常具有概念分层底层的项通常支持度也低在多个概念层的项之间找有趣的关联比仅在原始层数据之间更容易找。食品面包牛奶脱脂奶光明统一酸奶白黄TIDItemsT1{111,121,211,221}T2{111,211,222,323}T3{112,122,221,411}T4{111,121}T5{111,122,211,221,413}31多层关联规则:支持度不变vs.支持度递减支持度不变:在各层之间使用统一的支持度优点：一个最小支持度阈值.如果一个项集的父项集不具有最小支持度，那他本身也不可能满足最小支持度。缺点：底层项不会成为频繁集，如果支持度太高丢失底层关联规则太低生成太多的高层关联规则支持度递减:随着层次的降低支持度递减4种搜索策略：逐层独立层交叉单项过滤层交叉K－项集过滤受控的层交叉单项过滤