关联规则与关联分析.ppt

第四章 关联规则与关联分析,摘要,关联规则挖掘是数据挖掘中成果颇丰而且比较活跃的研究分支。本章主要介绍了关联规则挖掘的基本概念及其分类，以单维单层布尔关联规则的挖掘理论为切入点，介绍关联规则挖掘理论模型以及算法方面的内容，并简单扼要介绍了多层关联规则挖掘、多维关联规则挖掘的相关内容，最后通过一个实例给出了关联分析的医学应用。,什么是关联规则挖掘？,关联规则挖掘： 从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。 应用： 购物篮分析、分类设计、捆绑销售等,“尿布与啤酒”典型关联分析案例,采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。,购物篮分析,如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？） 关联规则的两个兴趣度度量 支持度 置信度,关联（association）：两个或多个变量的取值之间存在某种规律性。 关联规则（association rule）：指在同一个事件中出现的不同项的相关性。 关联分析（association analysis）：用于发现隐藏在大型数据集中的令人感兴趣的联系。所发现的联系可以用关联规则或者频繁项集的形式表示。关联规则挖掘就是从大量的数据中挖掘出描述数据项之间相互联系的有价值的有关知识。 应用：购物篮分析、生物信息学、医疗诊断、Web挖掘、科学数据分析、分类设计、捆绑销售和亏本销售分析,购物篮事务的例子,第一节 关联规则基本概念和关联规则挖掘分类,关联规则的基本概念 关联规则挖掘的基本过程与分类,关联规则的基本概念,令I=i1， i2， ，id是购物篮数据中所有项的集合，而T=t1， t2， ，tn是所有事务的集合。 每个事务ti包含的项集都是I的子集。 在关联分析中，包含0个或者多个项的集合被称为项集（itemset） 如果一个项集包含k个项，则称它为k-项集。例如啤酒，尿布，牛奶是一个3-项集。 空集是指不包含任何项的项集。,事务的宽度定义为事务中出现项的个数。 如果项集X是事务tj的子集，则称事务tj包含项集X。 项集的一个重要性质就是它的支持度计数，即包含特定项集的事务个数，数学上，项集X的支持度计数（X）可以表示为： （X）=|ti|Xti，tiT|,关联规则是形如XY的蕴含表达式，其中X和Y是不相交的项集。 关联规则的强度可以用它的支持度（support）和置信度（confidence）度量。支持度确定了规则可以用于给定数据集的频繁程度，而置信度确定了Y包含X的事务中出现的频繁程度。,规则度量：支持度和置信度,Customer buys diaper,Customer buys both,Customer buys beer,对所有满足最小支持度和置信度的关联规则 支持度s是指事务集D中包含 的百分比 置信度c是指D中包含A的事务同时也包含B的百分比 假设最小支持度为50%，最小置信度为50%，则有如下关联规则 A C (50%, 66.6%) C A (50%, 100%),关联规则挖掘的基本过程与分类,关联规则挖掘的基本过程 关联规则挖掘的分类,关联规则挖掘的基本过程,给定事务的集合T，关联规则发现是指找出支持度大于等于minsup，并且置信度大于等于minconf的所有规则，其中minsup和minconf是对应的支持度和置信度的阈值。,原始关联规则挖掘方法：,计算每一个可能规则的支持度和置信度。但是这种方法由于过高的代价而让人望而却步。,关联规则挖掘任务的步骤,找出所有频繁项集：其目标是发现满足最小支持度阈值的所有项集，这些项集称作频繁项集（frequent itemset） 由频繁项集产生强关联规则：其目标是从上一步发现的频繁项集中提取所有高置信度的规则，这些规则称作强规则（strong rule）,关联规则挖掘分类 (1),关联规则有多种分类： 根据规则中所处理的值类型 布尔关联规则 量化关联规则（规则描述的是量化的项或属性间的关联性） 根据规则中涉及的数据维 单维关联规则 （仅涉及buys这个维） 多维关联规则,关联规则挖掘分类 (2),根据规则集所涉及的抽象层 单层关联规则 多层关联规则 （在不同的抽象层发现关联规则） 根据关联挖掘的各种扩充 挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的） 挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c，使得每个包含c的事务也包含c） （最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集）,由事务数据库挖掘单维布尔关联规则,最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。,最小支持度 50% 最小置信度 50%,对规则A C，支持度 =50% 置信度,Apriori算法 (1),Apriori算法是挖掘布尔关联规则频繁项集的算法 Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。 模式不可能比A更频繁的出现 Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。 Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率,Apriori算法 (2),Apriori算法利用频繁项集性质的先验知识（prior knowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。 先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。,Apriori算法步骤,Apriori算法由连接和剪枝两个步骤组成。 连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。 Lk-1中的两个元素L1和L2可以执行连接操作 的条件是 Ck是Lk的超集，即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中（为什么？）。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk 。 为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除。,Apriori算法示例,Database TDB,1st scan,C1,L1,L2,C2,C2,2nd scan,C3,L3,3rd scan,最小支持计数：2,使用Apiori性质由L2产生C3,1 连接： C3=L2 L2= A,C,B,C,B,EC,E A,C,B,C,B,EC,E = A,B,C,A,C,E,B,C,E 2使用Apriori性质剪枝：频繁项集的所有子集必须是频繁的，对候选项C3，我们可以删除其子集为非频繁的选项： A,B,C的2项子集是A,B,A,C,B,C，其中A,B不是L2的元素，所以删除这个选项； A,C,E的2项子集是A,C,A,E,C,E，其中A,E 不是L2的元素，所以删除这个选项； B,C,E的2项子集是B,C,B,E,C,E，它的所有2项子集都是L2的元素，因此保留这个选项。 3这样，剪枝后得到C3=B,C,E,由频繁项集产生关联规则,同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算： 每个关联规则可由如下过程产生： 对于每个频繁项集l，产生l的所有非空子集； 对于每个非空子集s，如果 则输出规则“ ”,多层关联规则挖掘,多层关联规则可以分为同层关联规则和层间关联规则，同层关联规则是指处于同概念层的关联规则；层间关联规则是指不同概念层的关联规则。 多层关联规则基本上可以沿用“支持度-置信度”的框架，但是在设置问题上有一些要考虑的东西,统一的最小支持度：对于不同层次，都使用一个最小支持度。这样对于用户和算法实现来讲都比较容易，但是弊端也是显然的。 递减的最小支持度：每个层次都有不同的