1、1三三 关联规则挖掘理论关联规则挖掘理论n基本概念与解决方法 n经典的频繁项目集生成算法分析及其改进算法n对项目集格空间理论的发展n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法2关联规则挖掘是数据挖掘研究的基础n关联规则挖掘（Association Rule Mining）是数据挖掘中研究较早而且至今仍活跃的研究方法之一。n最早是由Agrawal等人提出的（1993）。最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据库（Transaction Database）中不同商品之间的联系规则。n关联规则的挖掘工作成果颇丰。例如，关联规则的
2、挖掘理论、算法设计、算法的性能以及应用推广、并行关联规则挖掘（Parallel Association Rule Mining）以及数量关联规则挖掘（Quantitive Association Rule Mining）等。n关联规则挖掘是数据挖掘的其他研究分支的基础。 3事务数据库 n设I= i1，i2，im 是一个项目集合，事务数据库D= t1，t2，tn 是由一系列具有唯一标识TID的事务组成，每个事务ti（i=1，2，n）都对应I上的一个子集。n一个事务数据库可以用来刻画：n购物记录： I是全部物品集合， D是购物清单，每个元组ti是一次购买物品的集合（它当然是I的一个子集）。n其它应
3、用问题4支持度与频繁项目集 n定义（项目集的支持度）定义（项目集的支持度）. 给定一个全局项目集I和数据库D，一个项目集I1I在D上的支持度（Support）是包含I1的事务在D中所占的百分比：support（ I1 ）=| t D | I1 t| / | D|。n定义（定义（频繁项目集）.给定全局项目集I和数据库D ，D中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于minsupport的I的非空子集，称为频繁项目集（频集：Frequent Itemsets）或者大项目集（Large Iitemsets）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最
4、大频繁项目集（最大频集： Maximum Frequent Itemsets）或最大大项目集（Maximum Large Iitemsets）。5可信度与关联规则n定义（关联规则与可信度）定义（关联规则与可信度）.给定一个全局项目集I和数据库D，一个定义在I和D上的关联规则形如I1I2，并且它的可信度或信任度或置信度（Confidence）是指包含I1和I2的事务数与包含I1的事务数之比，即Confidence（I1I2）= support（I1I2）/ support（I1），其中I1，I2I，I1I2=。n定义（强关联规则）定义（强关联规则）. D在I上满足最小支持度和最小信任度（Minc
5、onfidence）的关联规则称为强关联规则（Strong Association Rule）。6关联规则挖掘基本过程n关联规则挖掘问题可以划分成两个子问题：n1. 1. 发现频繁项目集发现频繁项目集: :通过用户给定Minsupport ，寻找所有频繁项目集或者最大频繁项目集。n2 2生成关联规则生成关联规则: :通过用户给定Minconfidence ，在频繁项目集中，寻找关联规则。n第1个子问题是近年来关联规则挖掘算法研究的重点。7第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法n基本概念与解决方法 n经典的频繁项目集生成算法分析及其改进算法n对项目集格空间理论的发展n关联规则
6、挖掘中的一些更深入的问题n数量关联规则挖掘方法8频繁项目集生成算法分析nAgrawal等人建立了用于事务数据库挖掘的项目集格空间理论（1993, Appriori 属性）。n1994年，Agrawal 等人提出了著名的Apriori 算法。（发现频繁项目集）nApriori作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的作用。nApriori算法有两个致命的性能瓶颈:n1 1多次扫描事务数据库，需要很大的多次扫描事务数据库，需要很大的I/OI/O负载负载n2 2可能产生庞大的侯选集可能产生庞大的侯选集9频繁项目集生成算法分析n一些算法虽然仍然遵循Apriori 属性，但是由于引入了相关技
7、术，在一定程度上改善了Apriori算法适应性和效率。n主要的改进方法有：n基于数据分割（Partition）的方法：基本原理是“在一个划分中的支持度小于最小支持度的k-项集不可能是全局频繁的”。n基于散列（Hash）的方法：基本原理是“在一个hash桶内支持度小于最小支持度的k-项集不可能是全局频繁的”。n基于采样（Sampling）的方法：基本原理是“通过采样技术，评估被采样的子集中，并依次来估计k-项集的全局频度”。n其他：如，动态删除没有用的事务：“不包含任何Lk的事务对未来的扫描结果不会产生影响，因而可以删除”。10基于散列的方法基于散列的方法n1995，Park等发现寻找频繁项目集
8、的主要计算是在生成2-频繁项目集上。因此，Park等利用了这个性质引入杂凑技术来改进产生2-频繁项目集的方法。11第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法n基本概念与解决方法 n经典的频繁项目集生成算法分析及其改进算法 n对项目集格空间理论的发展n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法12探索新的理论n随着数据库容量的增大，重复访问数据库（外存）将导致性能低下。因此，探索新的理论和算法来减少数据库的扫描次数和侯选集空间占用，已经成为近年来关联规则挖掘研究的热点之一。n两个典型的方法：nClose算法 nFP-tree算法 13第三章第三章 关联规则挖掘理论和算
9、法关联规则挖掘理论和算法n基本概念与解决方法 n经典的频繁项目集生成算法分析及其改进算法 n对项目集格空间理论的发展n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法14第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法n基本概念与解决方法 n经典的频繁项目集生成算法分析及其改进算法n对项目集格空间理论的发展n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法15多层次关联规则挖掘多层次关联规则挖掘n根据规则中涉及到的层次，多层次关联规则可以分为：n同层关联规则：同层关联规则：如果一个关联规则对应的项目是同一个粒度层次，那么它是同层关联规则。n层间关联规则：层间关联规则：如果
10、在不同的粒度层次上考虑问题，那么可能得到的是层间关联规则。n多层次关联规则挖掘的度量方法可以沿用 “支持度-可信度”的框架。不过，多层次关联规则挖掘有两种基本的设置支持度的策略：n统一的最小支持度：统一的最小支持度：算法实现容易，而且很容易支持层间的关联规则生成。但是弊端也是显然的：n不同层次可能考虑问题的精度不同、面向的用户群不同。不同层次可能考虑问题的精度不同、面向的用户群不同。n对于一些用户，可能觉得支持度太小，产生了过多不感兴趣的规则。对于一些用户，可能觉得支持度太小，产生了过多不感兴趣的规则。而对于另外的用户来说，又认为支持度太大，有用信息丢失过多。而对于另外的用户来说，又认为支持度
11、太大，有用信息丢失过多。n不同层次使用不同的最小支持度：不同层次使用不同的最小支持度：每个层次都有自己的最小支持度。较低层次的最小支持度相对较小，而较高层次的最小支持度相对较大。这种方法增加了挖掘的灵活性。但是，也留下了许多相关问题需要解决：n首先，不同层次间的支持度应该有所关联，只有正确地刻画这种联系首先，不同层次间的支持度应该有所关联，只有正确地刻画这种联系或找到转换方法，才能使生成的关联规则相对客观。或找到转换方法，才能使生成的关联规则相对客观。n其次，由于具有不同的支持度，层间的关联规则挖掘也是必须解决的其次，由于具有不同的支持度，层间的关联规则挖掘也是必须解决的问题。例如，有人提出层
12、间关联规则应该根据较低层次的最小支持度问题。例如，有人提出层间关联规则应该根据较低层次的最小支持度来定。来定。 16多维关联规则挖掘多维关联规则挖掘n多维关联规则可以有：n维内的关联规则：维内的关联规则：例如，“年龄（X，2030）职业（X，学生）=购买（X，笔记本电脑）”。这里我们就涉及到三个维：年龄、职业、购买。n混合维关联规则：混合维关联规则：这类规则允许同一个维重复出现。例如，“年龄（X，2030）购买（X，笔记本电脑） = 购买（X，打印机）”。由于同一个维“购买”在规则中重复出现，因此为挖掘带来难度。但是，这类规则更具有普遍性，具有更好的应用价值，因此近年来得到普遍关注。17第三章第三章 关联规则挖掘理论和算法关联规则挖掘理论和算法n基本概念与解决方法 n经典的频繁项目集生成算法分析及其改进算法 n对项目集格空间理论的发展n基于项目序列集操作的关联规则挖掘算法n关联规则挖掘中的一些更深入的问题n数量关联规则挖掘方法18数量关联规则挖掘方法n数量关联规则是指同时包含分类属性和数量属性的关联规则。对数量关联规则挖掘的研究只要基于两条技术路线： 一是通过对相对比较成熟的布尔关联规则算法的改进来解决数量关联规则问题； 二是用一种新的全新的思路和算法来解决数量关联规则挖掘问题。n目前讨论比较多的和相对成熟的方法是基于第一种技术的。
