最新《数据仓库与数据挖掘》课件4关联规则挖掘理论和算法教学讲义ppt.ppt

《最新《数据仓库与数据挖掘》课件4关联规则挖掘理论和算法教学讲义ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据仓库与数据挖掘》课件4关联规则挖掘理论和算法关联规则挖掘是数据挖掘研究的基础关联规则挖掘（AssociationRuleMining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（BasketAnalysis）问题提出的，其目的是为了发现交易数据库（TransactionDatabase）中不同商品之间的联系规则。关联规则的挖掘工作成果颇丰。例如，关联规则的挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘以及数量关联规则挖掘等。关联规则挖掘是数据挖掘的其他研究分支的基础

2、。事务数据库设I={i1，i2，…，im}是一个项目集合，事务数据库D={t1，t2，…，tn}是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，…，n）都对应I上的一个子集。一个事务数据库可以用来刻画：购物记录：I是全部物品集合，D是购物清单，每个元组ti是一次购买物品的集合（它当然是I的一个子集）。其它应用问题基本概念与解决方法经典的频繁项目集生成算法分析Apriori算法的性能瓶颈问题Apriori的改进算法对项目集格空间理论的发展基于项目序列集操作的关联规则挖掘算法改善关联规则挖掘质量问题约束数据挖掘问题关联规则挖掘中的一些更深入的问题数量关联

3、规则挖掘方法第5章关联规则挖掘理论和算法内容提要项目集格空间理论定理1（Appriori属性1）.如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。证明设X是一个项目集，事务数据库T中支持X的元组数为s。对X的任一非空子集为Y，设T中支持Y的元组数为s1。根据项目集支持数的定义，很容易知道支持X的元组一定支持Y，所以s1≥s，即support（Y）≥support（X）。按假设：项目集X是频繁项目集，即support(X)≥minsupport，所以support（Y）≥support（X）≥minsupport，因此Y是频繁项目集。定理2（Apprior

4、i属性2）.如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。证明（略）经典的发现频繁项目集算法1994年，Agrawal等人提出了著名的Apriori算法。算法1Apriori（发现频繁项目集）（1）L1={large1-itemsets};//所有1-项目频集（2）FOR（k=2;Lk-1;k++）DOBEGIN（3）Ck=apriori-gen（Lk-1）;//Ck是k-候选集（4）FORalltransactionstDDOBEGIN（5）Ct=subset（Ck，t）;//Ct是所有t包含的候选集元素（6）FORallcandidatesc

5、CtDO（7）c.count++;（8）END（9）Lk={cCk

6、c.countminsup_count}（10）END（11）L=Lk;apriori-gen过程算法apriori中调用了apriori-gen（Lk-1），是为了通过（k-1）-频集产生K-侯选集。has_infrequent_subset（c，Lk-1），判断c是否加入到k-侯选集中。（1）FORallitemsetpLk-1DO（2）FORallitemsetqLk-1DO（3）IFp.item1=q.item1，…，p.itemk-2=q.itemk-2，p.itemk-1

7、itemk-1THENBEGIN（4）c=p∞q;//把q的第k-1个元素连到p后（5）IFhas_infrequent_subset（c，Lk-1）THEN（6）deletec;//删除含有非频繁项目子集的侯选元素（7）ELSEaddctoCk;（8）END（9）ReturnCk;Apriori算法例子（Minsupport=50%）DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanD关联规则的生成问题根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步骤生成关联规则：对于每一个频繁项目集l，生成其所有的非空子集；

8、对于l的每一个非空子集x，如果Confidence（x（l-x）)≥minconfidence，那么“x（l-x）”成立。算法3-4从给定的频繁项目集中生成强关联规则算法3-4的核心是genrules递归过程，它实现一个频繁项目集中所有强关联规则的生成。Rule-generate（L，minconf）（1）FOReachfrequentitemsetlkinL（2）genrules（lk，Xm）;算法-递归测试一个频集中的关联规则genrules（lk:frequentk-itemset，xm:frequentm-itemset）（1）X={（m