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