我国社会经济发展综合评价指数研究.ppt

1、-CARMA Continuous Association Rule Mining Algorithm,报告人：徐启元 指导教师:谢邦昌 日期：2007年11月30日,目录,关联规则基本概念 CARMA算法简介 CARMA模块的基本概念 案例分析及Clementine操作步骤 购物篮分析-Tabular类型数据 网络日志分析-Transactional类型数据 值得注意的问题 CARMA算法原理（参考）,关联规则算法简介,关联分析的目的是寻找数据项间的相关性常用技术： 关联规则：即寻找在同一个事件中出现的不同项目的相关性 例如：找出顾客经常同 时购买哪些商品。网民 浏览的网页之间有没有 什么关

2、联性。,CARMA算法简介,CARMA是一种比较新的关联规则算法，它是1999年由Berkeley大学的Christian Hidber教授提出来的。,1,2,3,4,能够处理在线连续交易流数据,仅需一次，最多两次对数据的扫描就可以构造出结果集,允许在算法执行过程中按需要重新设置支持度,占用内存少,CARMA,CARMA模块中的基本概念,Antecedent,CARMA算法原理,如果v是k-项集(k=2)，则先按前述方式处理包含的所有1-项集，且： 如果第一次出现，判断该k-项集是否可以进入V，且令Count(v)1, firstTrans i,且 如果不是第一次出现，则项集各子集的Count

3、(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项子集是否也在内）。

4、项集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个时刻

5、， v的具有最大firstTrans的真子集w(|w|=|v|-1)，其支持度一定大于v的，即：,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) 依据二：用户以

6、往定义的最小支持度的情况 总之有：主要取决于以往的一系列最小支持度,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,

7、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。,CA

8、RMA算法原理,策略二： 序列为变化量 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的项集 如果某个项集被剔除了，则其所有超集也应被剔除 在频繁项集的基础上产生关联规则(同其他算