关联规则挖掘理论和算法

《关联规则挖掘理论和算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、主讲：赵宏庆数据挖掘原理与算法第三章关联规则挖掘理论和算法2ChineseAcademyofScience第三章关联规则挖掘理论和算法3.1基本概念与解决方法3.2经典的频繁项目集生成算法分析3.3Apriori算法的性能瓶颈问题3.4Apriori的改进算法3.5对项目集格空间理论的发展3.6项目集格空间和它的操作3.7基于项目序列集操作的关联规则挖掘算法3.8改善关联规则挖掘质量问题3.9约束数据挖掘问题3.10关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法3ChineseAcademyofScience关联规则挖掘是数据挖掘

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

3、iationRuleMining）等。关联规则挖掘是数据挖掘的其他研究分支的基础。4ChineseAcademyofScience3.1基本概念与解决方法事务数据库设I={i1，i2，…，im}是一个项目集合，事务数据库D={t1，t2，…，tn}是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，…，n）都对应I上的一个子集。一个事务数据库可以用来刻画：购物记录：I是全部物品集合，D是购物清单，每个元组ti是一次购买物品的集合（它当然是I的一个子集）。其它应用问题5ChineseAcademyofScience支持度与频繁项目集

4、定义（项目集的支持度）.给定一个全局项目集I和数据库D，一个项目集I1I在D上的支持度（Support）是包含I1的事务在D中所占的百分比：support（I1）=

5、

6、{tD

7、I1t}

8、

9、/

10、

11、D

12、

13、。6ChineseAcademyofScience支持度与频繁项目集定义（频繁项目集）.给定全局项目集I和数据库D，D中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于minsupport的I的非空子集，称为频繁项目集（频集：FrequentItemsets）或者大项目集（LargeIitemsets）。在频繁项目集

14、中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（最大频集：MaximumFrequentItemsets）或最大大项目集（MaximumLargeIitemsets）。7ChineseAcademyofScience可信度与关联规则定义（关联规则与可信度）.给定一个全局项目集I和数据库D，一个定义在I和D上的关联规则形如I1I2，并且它的可信度或信任度或置信度（Confidence）是指包含I1和I2的事务数与包含I1的事务数之比，即Confidence（I1I2）=support（I1∪I2）/support（I1），其中I1

15、，I2I，I1∩I2=Ф。定义（强关联规则）.D在I上满足最小支持度和最小信任度（Minconfidence）的关联规则称为强关联规则（StrongAssociationRule）。8ChineseAcademyofScience关联规则挖掘基本过程关联规则挖掘问题可以划分成两个子问题：1.发现频繁项目集:通过用户给定Minsupport，寻找所有频繁项目集或者最大频繁项目集。2.生成关联规则:通过用户给定Minconfidence，在频繁项目集中，寻找关联规则。第1个子问题是近年来关联规则挖掘算法研究的重点。9ChineseAcademyo

16、fScience第三章关联规则挖掘理论和算法3.1基本概念与解决方法3.2经典的频繁项目集生成算法分析3.3Apriori算法的性能瓶颈问题3.4Apriori的改进算法3.5对项目集格空间理论的发展3.6项目集格空间和它的操作3.7基于项目序列集操作的关联规则挖掘算法3.8改善关联规则挖掘质量问题3.9约束数据挖掘问题3.10关联规则挖掘中的一些更深入的问题3.11数量关联规则挖掘方法10ChineseAcademyofScience项目集格空间理论Agrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993,Apriori属性）。

17、定理（Apriori属性1）.如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。证明:设X是一个项目集，事务数据库T中支持X的元组数为s。