第3章关联规则挖掘理论和算法(new)

《第3章关联规则挖掘理论和算法(new)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基本概念与解决方法经典的频繁项目集生成算法分析Apriori算法的性能瓶颈问题Apriori的改进算法对项目集格空间理论的发展关联规则挖掘中的一些更深入的问题第三章关联规则挖掘理论和算法关联规则挖掘是数据挖掘研究的基础关联规则挖掘（AssociationRuleMining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（BasketAnalysis）问题提出的，其目的是为了发现交易数据库（TransactionDatabase）中不同商品之间的联系规则。关联规则的挖掘工作成果颇丰。例如，关联规则的

2、挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（ParallelAssociationRuleMining）以及数量关联规则挖掘（QuantitiveAssociationRuleMining）等。关联规则挖掘是数据挖掘的其他研究分支的基础。基本概念与解决方法事务数据库设I={i1，i2，…，im}是一个项目(Item)集合，事务数据库D={t1，t2，…，tn}是由一系列具有唯一标识TID(事务号)的事务组成，每个事务ti（i=1，2，…，n）都对应I上的一个子集。一个事务数据库可以用来刻画：购物记录：I是全部物品集合，D是购物清单，每个元组ti是一次购买物品的

3、集合（它当然是I的一个子集）。如I={物品1，物品2，…，物品m};事务数据库D={t1，t2，…，tn}是事务数据库中关联规则的挖掘t1物品2物品6物品9…………t2物品3物品8物品16……………………tn物品1物品12物品34…………支持度、频繁项目集、可信度、强关联规则定义（项目集的支持度）给定一个全局项目集I和数据库D，一个项目集I1I在D上的支持度（Support）是包含I1的事务在D中所占的百分比：support（I1）=

4、

5、{tD

6、I1t}

7、

8、/

9、

10、D

11、

12、定义（频繁项目集）给定全局项目集I和数据库D，D中所有满足用户指定的最小支持度（Minsupport）的

13、项目集，即大于或等于最小支持度的I的非空子集，称为频繁项目集（FrequentItemsets）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（MaximumFrequentItemsets）。定义（规则的可信度）一个定义在I和D上的形如I1I2的关联规则通过满足一定的可信度(Confidence)来给出。所谓规则的可信度是指包含I1和I2的事务与包含I1的事务之比：Confidence(I1I2)=

14、

15、Support(I1∪I2)/Support(I1)其中I1,I2I;I1∩I2=Ø定义（强关联规则）。D在I上满足最小支持度和最小可信度的关联

16、规则称为强关联规则。通常所说的关联规则一般指上面定义的强关联规则。关联规则挖掘基本过程关联规则挖掘问题就是根据用户指定的最小支持度和最小可信度来寻找强关联规则。关联规则挖掘问题可以划分成两个子问题：1.发现频繁项目集:通过用户给定最小支持度，寻找所有频繁项目集或者最大频繁项目集。2.生成关联规则:通过用户给定最小可信度，在频繁项目集中，寻找关联规则。第1个子问题是近年来关联规则挖掘算法研究的重点。项目集格空间理论Agrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993,Appriori属性）。其理论核心的原理是：频繁项目集的所有非空子集都是频繁项目集非频繁项目集的

17、所有超集都是非频繁项目集（相关定理及其证明略。）经典的频繁项目集生成算法分析Apriori算法是通过项目集元素数目不断增长来完成频繁项目集发现的。首先产生1_频繁项目集L1，然后产生2_频繁项目集L2，直到不能再扩展频繁项目集的元素数目为止。下面给出一个样本事务数据库，并对它实施Apriori算法。TIDItemset1001，3，42002，3，53001，2，3，54002，5经典的发现频繁项目集算法1994年，Agrawal等人提出了著名的Apriori算法。Apriori算法例子DatabaseDC1L1L2C2ScanDL3ScanDC3ScanDC4ScanDSca

18、nDØL4Minsupport=50%C1：1-候选集L1：1-频繁项目集C2：2-候选集L2：2-频繁项目集C3：3-候选集L3：3-频繁项目集C4：4-候选集L4：4-频繁项目集L3是最大频繁项目集Apriori算法（发现频繁项目集）（1）L1={large1-itemsets};//所有1-项目频集（2）FOR（k=2;Lk-1;k++）DOBEGIN（3）Ck=apriori-gen（Lk-1）;//Ck是k-候选集（4）FORalltransactionstDDOBEGIN（