挖掘关联规则

1挖掘关联规则关联规则挖掘事务数据库中关联规则挖掘算法基于限制的关联挖掘2关联规则关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。典型的关联规则发现问题是对超市中的货篮数据进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。3什么是关联规则挖掘关联规则挖掘(1993)在事务、关系数据库中的项集和对象中发现频繁模式、关联规则、相关性或者因果结构频繁模式:数据库中频繁出现的项集目的:发现数据中的规律超市数据中的什么产品会一起购买？—啤酒和尿布在买了一台PC之后下一步会购买?我们如何自动对Web文档进行分类?交叉销售、直销等4关联规则基本模型Apriori是关联规则模型中的经典算法。给定一组事务产生所有的关联规则满足最小支持度和最小可信度5关联规则基本模型设I={i1,…,im}为所有项目的集合，D为事务数据库，事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度(阈值)，就称该项集是频繁项集。交易ID购买的商品2000A,B,C1000A,C4000A,D5000B,E,F6关联规则基本模型关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%support(XY)=P(XY)项集的支持度计数support_count包含项集的事务数若项集X的支持度记为support(X)，规则的置信度为support(XY)／support(X)。是一个条件概率P(Y|X)。confidence(XY)=P(Y|X)=support_count(XY)／support_count(X)7频繁模式和关联规则ItemsetX={x1,…,xk}找出满足最小支持度和置信度的所有规则XY支持度,s,事务包含XY的概率置信度,c,事务含X也包含Y的条件概率.顾客购买尿布顾客购买二者顾客购买啤酒Transaction-idItemsbought10A,B,D20A,C,D30A,D,E40B,E,F50B,C,D,E,F令supmin=50%,confmin=50%{A:3,B:3,D:4,E:3,F:3,AD:3}关联规则Associationrules:AD(60%,100%)DA(60%,75%)8挖掘关联规则—一个例子规则AC支持度=support({A}{C})=50%置信度=support({A}{C})/support({A})=66.6%最小支持度50%最小置信度50%Transaction-idItemsbought10A,B,C20A,C30A,D40B,E,FFrequentpatternSupport{A}75%{B}50%{C}50%{A,C}50%9第5讲：挖掘关联规则关联规则挖掘事务数据库中关联规则挖掘算法基于限制的关联挖掘10Apriori算法的步骤Apriori算法将发现关联规则的过程分为两个步骤：通过迭代、检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；利用频繁项集构造出满足用户最小信任度的规则。挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。11频繁项集为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项构成的k项集的集合为，则三者之间满足关系LkCk。kmCkmC12关联规则的性质性质1：频繁项集的子集必为频繁项集。性质2：非频繁项集的超集一定是非频繁的。Apriori算法运用性质1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。13Apriori:一种候选产生-测试方法频繁项集的任何子集必须是频繁的如果{beer,diaper,nuts}是频繁的,{beer,diaper}也是每个包含{beer,diaper,nuts}的事务也包含{beer,diaper}Apriori剪枝原则:（性质2）如果一个项集不是频繁的,将不产生/测试它的超集!方法:由长度为k的频繁项集产生长度为(k+1)的候选项集并且根据D测试这些候选（..）14Apriori算法—一个例子数据库TDB第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}215Apriori算法(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;(11)Answer=kkL16Apriori的重要细节如何产生候选?步骤1:Lk的自连接步骤2:剪枝候选产生的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3Abcd：由abc和abdAcde：由acd和ace剪枝:acde被删除,因为ade不在L3C4={abcd}17如何产生候选?假定Lk-1中的项集已排序(按字典序排序)步骤1:Lk-1自连接insertintoCkselectp.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:剪枝forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk18例子-支持计数=219例子20由频繁项集产生关联规则根据公式产生关联规则对于每个频繁项集l，产生所有的非空子集对于l的每个非空子集s，如果则输出规则”s(l-s)”21频繁模式挖掘的挑战挑战事务数据库的多遍扫描数量巨大的候选候选支持度计数繁重的工作量改进Apriori:基本思想减少事务数据库的扫描遍数压缩候选数量便于候选计数提高Apriori算法的方法（划分和采样）22划分:只扫描数据库两次项集在D中是频繁的,它必须至少在D的一个划分中是频繁的扫描1:划分数据库,并找出局部频繁模式扫描2:求出全局频繁模式采样：频繁模式选取原数据库的一个样本,使用Apriori算法在样本中挖掘频繁模式扫描一次数据库,验证在样本中发现的频繁模式.再次扫描数据库,找出遗漏的频繁模式牺牲一些精度换取有效性。23频繁模式挖掘的瓶颈多遍数据库扫描是昂贵的挖掘长模式需要很多遍扫描,并产生大量候选挖掘频繁模式i1i2…i100扫描次数:100候选个数:(1001)+(1002)+…+(100100)=2100-1=1.27*1030!瓶颈:候选产生-测试能够避免候选产生吗?（FP-树）24挖掘关联规则关联规则挖掘事务数据库中关联规则挖掘的算法基于限制的关联挖掘25基于约束的数据挖掘自动地找出数据库中的所有模式?—不现实(模式太多)!基于约束的挖掘用户灵活性:提供挖掘的约束系统优化:考察限制,寻找有效的挖掘—基于约束的挖掘知识类型约束:分类,关联,等数据约束（指定任务相关的数据集）找出Vancouver2000年12月份一起销售的产品对兴趣度约束强规则:min_support3%,min_confidence60%规则(或模式)约束-指定规则形式小额销售(价格$10)触发大额销售(sum$200)26规则约束-剪枝搜索空间规则约束的分类反单调性Anti-monotonic单调性Monotonic简洁性Succinct:27规则约束反单调性当项集S违反规则约束时,它的任何超集合也违反约束sum(S.Price)v是反单调的sum(S.Price)v不是反单调的单调性当项集S满足约束时,它的任何超集合也满足约束sum(S.Price)v是单调的min(S.Price)v是单调的简洁性:不查看事务数据库,项集S是否满足约束C可以根据选取的项确定min(S.Price)v是简洁的sum(S.Price)v不是简洁的TIDTransaction10a,b,c,d,f20b,c,d,f,g,h30a,c,d,e,f40c,e,f,gTDB(min_sup=2)ItemProfita40b0c-20d10e-30f30g20h-1028Apriori算法—一个例子TIDItems100134200235300123540025DatabaseDitemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3ScanDC1L1itemset{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}2L2C2C2ScanDC3L3itemset{235}ScanDitemsetsup{235}229朴素算法:Apriori+约束TIDItems100134200235300123540025DatabaseDitemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3ScanDC1L1itemset{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}2L2C2C2ScanDC3L3itemset{235}ScanDitemsetsup{235}2约束:Sum{S.price5}30受约束的Apriori算法:推进反单调约束TIDItems100134200235300123540025DatabaseDitemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3ScanDC1L1itemset{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}2L2C2C2ScanD