关联规则--CARMA.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,统计分析、数据挖掘与商业智能应用研究小组,关联规则,-,CARMA,Continuous Association Rule Mining Algorithm,报告人：徐启元,指导教师,:,谢邦昌,日期：,2007,年,11,月,30,日,目录,关联规则基本概念,CARMA,算法简介,CARMA,模块的基本概念,案例分析及,Clementine,操作步骤,购物篮分析,-Tabular,类型数据,网络日志分析,-Transactional,类型数据,值得注意的问题,CARMA,算法原理（参考）,关联规则算法简介,关联分析的目的是寻找数据项间的相关性常用技术：,关联规则：即寻找在同一个事件中出现的不同项目的相关性,例如：找出顾客经常同,时购买哪些商品。网民,浏览的网页之间有没有,什么关联性。,CARMA,算法简介,CARMA,是一种比较新的关联规则算法，它是,1999,年由,Berkeley,大学的,Christian,Hidber,教授提出来的。,1,2,3,4,能够处理在线连续交易流数据,仅需一次，最多两次对数据的扫描就可以构造出结果集,允许在算法执行过程中按需要重新设置支持度,占用内存少,CARMA,On-line,CARMA,模块中的基本概念,Antecedent&Consequent,它们指的是规则的前项和后项。,Instances,对于每一条规则，它的,Instances,值指的是所有,记录中包含该规则的,antecedent,的记录的数量。,面包,牛奶,前项,Antecedent,后项,Consequent,ID,P1,P2,P3,P4,1,bread,cheese,butter,water,2,water,milk,bread,noodle,3,orange,noodle,meat,beer,4,fish,softdrink,frozenmeal,bread,总共,4,条购买数据，其中有三条都包含,bread,，那么该条规则的,instances,等于,3,CARMA,模块中的基本概念,Support,它的定义和,instances,很接,近，不同的是,support,描述,的不是数量，而是比例。,Rule Support,它在,Support,定义的基础,上更进一步，它指的是,所有记录中既包含某规,则的,antecedent,，又包含,consequent,的记录所占,的比例。,ID,P1,P2,P3,P4,1,bread,cheese,butter,water,2,water,milk,bread,noodle,3,orange,noodle,meat,beer,4,fish,softdrink,frozenmeal,bread,Support=3/4100%=75%,四条记录中只有一条既包含了前项,bread,，又包含了后向,milk,，所以,Rule Support=1/4,100%=25%,CARMA,模块中的基本概念,Confidence,Confidence,=Rule Support/Support,该指标反映的是规则预测的,准确程度。,Deployability,Deployability,=Support,Rule Support,它的作用与,confidence,类似。,ID,P1,P2,P3,P4,1,bread,cheese,butter,water,2,water,milk,bread,noodle,3,orange,noodle,meat,beer,4,fish,softdrink,frozenmeal,bread,根据规则,“,面包,=,牛奶,”,，那么购买了面包的第一、二及四行都会被预测购买了牛奶，但事实上这三个预测只有第二个是正确的，所以,confidence=1/3,100%=33.3%,CARMA,模块中的基本概念,Lift,在已知某规则的,consequent,发生,的先验概率的情况,下，某规则的,Lift,被定义为,Confidence,和该先验概率的比,率值。,ID,P1,P2,P3,P4,1,bread,cheese,butter,water,2,water,milk,bread,noodle,3,milk,noodle,meat,beer,4,fish,softdrink,frozenmeal,bread,那么对于一条记录，那么不采用任何规则进行预测，随便猜测该顾客是否该买牛奶的正确率是,50%,已知有,50%,的人购买了牛奶：）,如果采用“面包,=,牛奶”的规则进行预测的话，正确率，即,confidence=33.3%,比随便猜测的正确率还低。,那么此时的,Lift,值为多少呢,？,Lift=33.3%/50%=66.6%1,的规则才是有意义的,规则,源数据格式,CARMA,模块能够处理一下两种格式的数据,Tabular,数据格式,Transactional,数据格式,案例研究之购物篮分析,数据准备,使用数据为,clementine,自带的,Baskets1n,数据集；,该数据集样本量为,1000,，每笔交易包含了顾客的卡号、性别、年龄、收入、付款方式等一系列个人信息，以及其购买的各种食品清单；,该数据集为,Tabular,格式,的数据。,研究目的,为超市货架的摆放提供科学的依据；,为超市商品促销决策提供支持。,案例研究,购物篮分析,加入,type,模块对变量类型进行设置。,先点击,Read Values,将各个变量实例化。,购物篮分析,将,CARMA,模块加入,流中，并双,击打开进行,参数设置。,点击,点击,购物篮分析,对,Model,选项卡进行设置。修改,Rule Support,、,Rule Confidence,以及,Rule Size,的大小。,点击此处，打开,Model,选项卡编辑,对这三个选项进行编辑以控制输出的规则的数目,购物篮分析,对,Expert,选项卡进行设置，如果对,CARMA,算法比较了解的用户，可以对该选项卡进行设定以获得使,CARMA,模块具有更好的性能。,选择此项，则输出的规则中后项（,consequent,）只能由一个元素。,选择该选项可以让,CARMA,算法周期性的剔除掉当前不太重要的规则，加速建模。,设定周期的大小，周期设定的越小，则越省内存，但是,CARMA,算法执行时间常；反之，则短。,设定该选项可以加速,CARMA,算法的执行。其大致思想是：一开始先给定一个较高的,support,值，将不显著的规则排除在外，然后再一次降低,support,值。,设定,support,值降低的速度,选择该项，则,CARMA,模型会输出不包含,antecedent,的规则。,购物篮分析,执行后建,立的模型,会,显示在,Canvas,内。,共产生,16,条规则,每一行分别显示了一组规则，以及度量该规则的一组指标，如：,Lift,、,support,等。,点击该图标可以按指定规则筛选出自己想要的规则,。,生成对应规则集的节点，包括三种节点：,Select Node,、,Filtered Node,以及,Rule set,节点。,购物篮分析,置信度（,Confidence,）最高的前三个规则：,Cannedveg,&,Beer,Frozenmeal,Frozenmeal,&,Beer,Cannedveg,Cannedveg,&,Frozenmeal,Beer,Frozenmeal,Connedveg,Beer,促销,购物篮分析,CARMA,模型可以,直接放在流中对,数据进行打分预,测（,scoring,）。,在打分之前可以,双击模型打开,Settings,选项卡进,行相关的参数设,置。,设定用于预测的规则个数,为选取规则设定标准，从而可以根据该规则选出最显著的,n,条规则，,n,由上一个选项设定。,设定该项，则允许用于预测的,n,条规则可以有相同的后项，即可以允许几条规则有相同的预测结果。,勾选该项，则在应用规则进行预测之前，系统会剔除掉不符合要求的数据行，不对其进行预测。,购物篮分析,对,CARMA,模型设置好了以后就可以将,CARMA,模型加入流中对数据进行预测了，本文仅用一,条规则进行预测，结果存入表中（见下页）。,购物篮分析,预测值,预测置信度,所使用规则的编号,购物篮分析,用,CARMA,模型预测顾客的购买行为,Confectionery,Freshmeat,Dairy,Wine,购物篮分析,除了直接使用生成的,CARMA,模型进行预测,外，还有一种预测方式即使用,Rule Set,。,使用,Generate,菜单生成想要的,Rule Set,节点，并将该节点放入流中进行预测。,点击确定以后可以生成一个规则集节点，将该节点加入流中就可以进,行预测了。,案例研究之网络日志分析,数据准备,使用数据为某网站五天的访问日志；,该数据集记录数为,173665,，每行记录对应用户对服务器的一个页面请求，记录了用户,IP,地址、请求时间、请求页面,URL,、访问协议、请求状态以及端口号等信息。本文为了简化仅引入前三个变量，且页面已经过分类，访问已按事务划分；,该数据集为,Transactional,格式,的数据。,研究目的,找出用户的访问模式，为网站结构上的调整和网站经营决策提供支持。,网络日志分析,加载数据集,网络日志分析,使用,CARMA,模块来处理,Transactional,格式的网络日志数据，并从中找出关联规则。,双击打开打开,Fields,选项卡进行编辑。,勾选该项，将,CARMA,模型处理的数据格式改为,Transactional,格式,指定数据的唯一标识，标识相同的记录属于同一个事务,该栏用以指定交易数据字段，本文中这里指定的是当前请求的页面种类。,网络日志分析,双击打开,Model,选项卡进行编,辑，设定,Rules,Support,、,Rule,Confidence,以及,Rule Size,等参,数。,网络日志分析,查看,CARMA,模型生成的规则集,网络日志分析,数据中定义的第一类页面为娱乐新闻版面，第二,类是灌水版面。,访问娱乐新闻版面,访问灌水版,访问灌水版面,访问娱乐新闻版,整合,访问量,将灌水版和娱乐新闻版整合为一个“我主娱乐”新版,值得注意的问题,CARMA,模型运算速度不是最快的，但是它只需要对数据集一至两遍的扫描就可以构造规则集；,CARMA,模型及可以处理,Tabular,格式的数据，也可以处理,Transactional,格式的数据；,CARMA,模型中需要设定的,Rule Support,的大小，而不是,Support,；,CARMA,模型不能处理数值型的数据。,CARMA,算法原理,Carma,算法也包括两个部分,寻找频繁项集,在频繁项集的基础上产生关联规则,Carma,寻找频繁项集的过程又分为,Phase I,和,Phase II,Phase I,：产生频繁项集的超集，即产生潜在频繁项集,V,在,Phase I,中可以随时调整最小支持度,Phase II,：对潜在频繁项集,V,进行删减得到最终的频繁项集,CARMA,算法原理,初始,V,为空集，将事务按照序号排序,逐条读入事务数据，并计算以下三个整数存储在,V,的支持格,(Support Lattice),中：,Count(v,),：,v,被插入,V,以后在事务数据库中出现的次数,firstTrans(v,),：,v,被插入,V,时所在事务的事务序号,maxMissed(v,),：,v,被插入,V,之前已读入的事务个数,例如：项集,a,b,在,j,时刻进入,V,当,j,时刻时以上三个整数的情况,CARMA,算法原理,根据,Count(v,),、,maxMissed(v,),定义了,v,项集的支持度的上限和下限：,minSupport(v,),是项集的实际支持度,maxSupport(v,),用来判断项集,v,用来是否可以保留在,V,中,CARMA,算法原理,Phase I,中,V,产生的基本过程：初始,V,为空集,(,此时只可添加,1-,项集,),，,读入第,i,条事务数据,v,，给出当前的最小支持度,i,在计算过程中，算法自动调整最小支持度，即给每个事务以一个最小支持度，会形成一个最小支持度序列,t,个事务,(1,2,3,),如果,v,是,1-,项集,:,如果第一次出现，则令,Count(v),1,maxMissed(v,),0(,1-,项集的,maxMissed(v,),规定为,0,),firstTrans(v,),i,且将,v,加入,V(1-,项集自动进入,V),如果不是第一次出现，则,Count(v),Count(v)+1;,CARMA,算法原理,如果,v,是,k-,项集,(k=2),，则先按前述方式处理包含的所有,1-,项集，且：,如果第一次出现，判断该,k-,项集是否可以进入,V,，且,令,Count(v),1,firstTrans,i,且,如果不是第一次出现，则项集各子集的,Count(v),Count(v)+1;,“,修剪”，默认每读入,500,个事务作一次修剪,(,从效率角度考虑，其实可以读入一条修剪一次,),，即判断支持格中所有,k-,项集的,maxSupport(v,),，如果小于当前的最小支持度,i,则剔除相应项集出,V,CARMA,算法原理,在,Phase I,阶段，,k-,项集,v,进入,V,的主要原则,如果一个项集是频繁项集，则其所有子集必定也是频繁项集；反之，如一个项集的某个子集不是频繁项集，则该项集必定也不是频繁项集；,Carma,在决定,k-,项集,v,进入频繁项集,V,时，,应确保,v,的所有真子集已在当前事务之前进入,V,中，这是,v,进入,V,的条件之一（要看所有子集，若,2,项无所谓，若,3,项则需要检验其,2,项子集是否也在内）,。,项集,v,加入,V,的必要条件表述为：,i,为当前的事务序号，即,v,的所有真子集,w,都是频繁项集且已在当前事务之前进入,V,中,CARMA,算法原理,在,Phase I,阶段，,k-,项集,v,进入,V,的主要原则,判断,v,的真子集时应从包含项目较多的子集开始判断，如果包含项目较多的子集已在,V,中，则包含项目较少的子集也一定在,V,中。因此，不必检查所有子集，只需要检验那些包含项目最多的子集即可。,为提高效率不必检验所有真子集，只需要检查那些：,其中：,|w|,、,|v|,为所包含的项目数,k,CARMA,算法原理,计算,maxSupport(v,),的关键是计算,maxMissed(v,),maxMissed,计算的依据一：其最大子集的频繁程度,在第,i,个时刻,，,v,的具有最大,firstTrans,的真子集,w(|w,|=|v|-1),，其支持度一定大于,v,的，即：,此时,i,是相等的明显然,CARMA,算法原理,计算,maxSupport(v,),的关键是计算,maxMissed(v,),依据二：用户以往定义的最小支持度的情况,在,i+1,时刻，以往,最小支持度序列表示为,i,(,1,2,3,i,),Carma,中定义了关于,i,的,天花板,(ceiling of),序列,，记为,天花板的含义是：,当,j,i,时,(j=1,2,.i-1),：,当,j,i,时,(j=1,2,.i-1),：,例如：,(0.3,0.7,0.9,0.5),CARMA,算法原理,计算,maxSupport(v,),的关键是计算,maxMissed(v,),依据二：用户以往定义的最小支持度的情况,总之有：主要取决于以往的一系列最小支持度,b,(0,1,3),1,1,CARMA,算法原理,Phase I,举例,事务序列,T=(a,b,a,b,c,b,c),定义的支持度阀值序列,=(0.3,0.9,0.5),V,t1=a,b,1=0.3,Va,b,t2=a,b,c,2=0.9,Va,b,c,a,b,a,b,的,maxSupport,均大于,0.3,不能剔除出,V,a,(0,1,1),1,1,b,(0,1,1),1,1,a,(0,1,2),1,1,b,(0,1,2),1,1,c,(0,2,1),0.5,0.5,a,b,(1,2,1),0.5,1,t3=b,c,Va,b,c,a,b,b,c,1=0.5,a,(0,1,2),0.66,0.66,c,(0,2,2),0.66,0.66,a,b,(1,2,1),0.33,0.66,b,c,(1,3,1),0.33,0.66,(,maxMissed,firstTrans,count,),minSupport,maxSupport,CARMA,算法原理,用户自行给出各个 是不现实的，用户只需要给出初始的 ，,Carma,便可以自行调整，通过固定 、不断减少,maxSupport,来实现,maxSupport,与,的比较,策略一：序列为常数序列,S,，则,随着计算的进行，,i,由小变大，,maxSupport,则相对由大变小,(,可以加快收敛速度,),，,并趋于,S,。,CARMA,算法原理,策略二：,序列为变化量,Carma,算法允许作四次变化取四个值，分别记为,S1,S2,S3,S4;S1,在处理,19,事务保持期间不变；,S2,在处理,1099,事务期间保持不变；,S3,在处理,1004999,事务期间保持不变；,S4,在处理,5000,以后的事务期间保持不变化；,在每轮计算过程中，,i,由小变大，,maxSupport,则相对由大变小，并趋于,Si,。,Si,依据,S,和事务数,t,及以下关系确定：,CARMA,算法原理,Carma,的,Phase II,的基本思路,已知,Phase I,的,V,最后一个支持度阀值,n,剔除所有的,maxSupport,小于,n,的项集,如果某个项集被剔除了，则其所有超集也应被剔除,在频繁项集的基础上产生关联规则,(,同其他算法,),Carma,的明显特点：执行效率较高,对数据库扫描一次就可实现所有项集三个整数的计算。随着后续数据的读入，只是依据新读数据的内容对支持格中已有的数据做局部修改调整，而不是在基于对数据库重新扫描的基础上的对支持格的全部重算。,致 谢,感谢您的聆听！,