关联规则挖掘及相关算法的介绍课件

目录关联规则挖掘介绍Apriori算法介绍FP-growth算法介绍强规则、关联与相关分析目录关联规则挖掘介绍1什么是关联规则挖掘？关联规则挖掘：从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。应用：购物篮分析、分类设计、捆绑销售和亏本销售分析、Web日志（点击流）分析，和DNA序列分析。什么是关联规则挖掘？关联规则挖掘：2“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例3购物篮分析——一个诱发的例子购物篮分析——一个诱发的例子4购物篮分析——一个诱发的例子策略一：把经常同时购买的商品摆放在一起，以便进一步刺激这些商品同时销售。(如计算机和杀毒软件)策略二：把经常同时购买的商品摆放在商店的两端，使顾客多看更多的商品，用来带动其他商品的出售。购物篮分析——一个诱发的例子策略一：把经常同时购买的商品摆放5购物篮分析——一个诱发的例子如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示（0001001100）；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示。关联规则的两个兴趣度度量支持度（support）置信度（confidence）购物篮分析——一个诱发的例子如果问题的全域是商店中所有商品的6关联规则：基本概念给定：项的集合：I={i1,i2,...,in}任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度c关联规则：基本概念给定：7规则度量：支持度和置信度CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer对所有满足最小支持度（min-sup)和置信度(min-con)的关联规则支持度s是指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度为50%，最小置信度为50%，则有如下关联规则AC(50%,66.6%)CA(50%,100%)规则度量：支持度和置信度CustomerCustomerCu8由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。最小支持度50%最小置信度50%对规则A

C，其支持度

=50%置信度由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维9大型数据库关联规则挖掘过程基本概念k－项集：包含k个项的集合{牛奶，面包，黄油}是个3－项集项集的频率是指包含项集的事务数如果项集的频率大于（最小支持度×D中的事务总数），则称该项集为频繁项集大型数据库中的关联规则挖掘包含两个过程：找出所有频繁项集大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则大型数据库关联规则挖掘过程基本概念10目录关联规则挖掘介绍Apriori算法介绍FP-growth算法介绍强规则、关联与相关分析目录关联规则挖掘介绍11Apriori算法Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-1项集用于探察k项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。Apriori性质：频繁项集的所有非空子集也必须是频繁的。（

模式不可能比A更频繁的出现）Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。频繁模式：是指频繁地出现在数据集中的模式（如项集、子序列或子结构）。频繁项集：频繁地同时出现在交易数据集中的数据集合。Apriori算法Apriori算法利用频繁项集性质的先验知12Apriori算法步骤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算法步骤Apriori算法由连接和剪枝两个步骤13Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{A}2{B}3{C}3{D}1{E}3Itemsetsup{A}2{B}3{C}3{E}3Itemset{A,B}{A,C}{A,E}{B,C}{B,E}{C,E}Itemsetsup{A,B}1{A,C}2{A,E}1{B,C}2{B,E}3{C,E}2Itemsetsup{A,C}2{B,C}2{B,E}3{C,E}2Itemset{B,C,E}Itemsetsup{B,C,E}2Apriori算法——示例DatabaseTDB1sts14使用Apiori性质由L2产生C31．连接：C3=L2L2={{A,C},{B,C},{B,E}{C,E}}{{A,C},{B,C},{B,E}{C,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}}使用Apiori性质由L2产生C31．连接：15由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由以下公式计算：每个关联规则可由如下过程产生：对于每个频繁项集l，产生l的所有非空子集；对于l的每个非空子集s，如果 则输出规则“ ”由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强16例题：交易记录事务数据库有9个事务。用Apriori算法寻找D中的频繁项集。

例题：交易记录事务数据库有9个事务。用Apriori算法寻找17关联规则挖掘及相关算法的介绍课件18关联规则挖掘及相关算法的介绍课件19例题：交易记录事务数据库有9个事务。用Apriori算法寻找D中的频繁项集。

算法使用L3

L3产生候选4-项集的集合C4。C4={{I1，I2，I3，I5}}，因为它的子集{I2,I3，I5}不是频繁的，这个项集被剪去，这样C4=Ø

，因此算法终止，找出了所有的频繁项集。例题：交易记录事务数据库有9个事务。用Apriori算法寻找20提高Apriori算法的有效性(1)Apriori算法主要的挑战要对数据进行多次扫描；会产生大量的候选项集；对候选项集的支持度计算非常繁琐；解决思路减少对数据的扫描次数；缩小产生的候选项集；改进对候选项集的支持度计算方法方法1：基于hash表的项集计数将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。提高Apriori算法的有效性(1)Apriori算法主要的21提高Apriori算法的有效性(2)方法2：事务压缩（压缩进一步迭代的事务数）不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。方法3：划分挖掘频繁项集只需要两次数据扫描D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。第一次扫描：将数据划分为多个部分并找到局部频繁项集第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集提高Apriori算法的有效性(2)方法2：事务压缩（压缩进22提高Apriori算法的有效性(3)方法4：选样（在给定数据的一个子集挖掘）基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式可以通过一次全局扫描来验证从样本中发现的模式可以通过第二此全局扫描来找到遗漏的模式方法5：动态项集计数在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。提高Apriori算法的有效性(3)方法4：选样（在给定数据23目录关联规则挖掘介绍Apriori算法介绍FP-growth算法介绍强规则、关联与相关分析目录关联规则挖掘介绍24FP-Growth算法AProiri算法需要产生大量候选项集,而且需要多次扫描数据库,然后通过模式匹配检查一个很大的候选集合,在挖掘长模式时,算法性能退化很快。Han提出了一种频繁模式

增长算法(FP-Growth)，不产生候选集而直接产生全部频繁项集。FP-Growth算法采用了分而治之策略:首先，将提供频繁项集的数据库压缩成一棵频繁模式树(FP)，

该树仍保留项集关联信息,然后，将这种压缩后的数据库划分成一组条件数据库，每个数据库关联一个频繁项，并分别挖掘每个条件数据库。FP-Growth算法AProiri算法需要产生大量候选项集25使用FP-Growth算法挖掘频繁模式

数据库中有9个事务,即|D|=9,如表所示，事务中的项按字典次次序存放。

表中有9个交易的数据库事务项ID列表事务项ID列表T100I1,I2,I5T600I2,I3T200I2,I4T700I1,I3T300I2,I3T800I1,I2,I3,I5T400I1,I2,I4T900I1,I2,I3T500I1,I3使用FP-Growth算法挖掘频繁模式

数据库中有9个事务,26FP树构造FP-树构造如下:1）创建树的根节点,用”null”标记。2）第二次扫描数据库,每个事务中的项按L中的次序处理(处理后的数据库见表1-2),并对每个事务创建一个分枝,若节点或分枝已经存在,则共享节点或分枝,同时将共享前缀上的每个结点的计数加1，为前缀之后的项创建结点和链接。若不存在，则以根结点为父结点将该事务中的项按L中的次序依次插入。扫描所有的事务之后得到的树如图所示。FP树构造FP-树构造如下:27第一步、构造FP-tree扫描事务数据库得到频繁1-项目集F定义minsup=20%，即最小支持度为2重新排列FI1I2I3I4I567622I2I1I3I4I576622第一步、构造FP-tree扫描事务数据库得到频繁1-项目集F28重新调整事务数据库TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3重新调整事务数据库TidItems1I2,I1,I52I229创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull创建根结点和频繁项目表Item-nameNode-headI30加入第一个事务(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:1加入第一个事务(I2,I1,I5)Item-nameNode31加入第二个事务(I2,I4)Item-nameNode-headI2I1I3NullI4I5NullI2:2I1:1I5:1I4:1加入第二个事务(I2,I4)Item-nameNode-he32加入第三个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:3I1:1I5:1I4:1I3:1加入第三个事务(I2,I3)Item-nameNode-he33加入第四个事务(I2,I1,I4)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1加入第四个事务(I2,I1,I4)Item-nameNode34加入第五个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:1加入第五个事务(I1,I3)Item-nameNode-he35加入第六个事务(I2,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:1加入第六个事务(I2,I3)Item-nameNode-he36加入第七个事务(I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:2加入第七个事务(I1,I3)Item-nameNode-he37加入第八个事务(I2,I1,I3,I5)Item-nameNode-headI2I1I3I4I5NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:1加入第八个事务(I2,I1,I3,I5)Item-nameN38加入第九个事务(I2,I1,I3)Item-nameNode-headI2I1I3I4I5NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:2加入第九个事务(I2,I1,I3)Item-nameNode39第二步、FP-growth首先考虑I5，得到条件模式基<(I2,I1:1)>、<I2,I1,I3:1>构造条件FP-tree得到I5频繁项集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}Item-nameNode-headI2I1NullI2:2I1:2I3:1第二步、FP-growth首先考虑I5，得到条件模式基Ite40第二步、FP-growth接着考虑I4，得到条件模式基<(I2,I1:1)>、<I2:1>构造条件FP-tree得到I4频繁项集：{{I2,I4:2}}Item-nameNode-headI2NullI2:2I1:1第二步、FP-growth接着考虑I4，得到条件模式基Ite41第二步、FP-growth然后考虑I3，得到条件模式基<(I2,I1:2)>、<I2:2>、<I1:2>构造条件FP-tree由于此树不是单一路径，因此需要递归挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:2第二步、FP-growth然后考虑I3，得到条件模式基Ite42第二步、FP-growth递归考虑I3，此时得到I1条件模式基<(I2:2)>,即I1I3的条件模式基为<(I2:2)>构造条件FP-tree得到I3的频繁项目集{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}}Item-nameNode-headI2NullI2:2第二步、FP-growth递归考虑I3，此时得到I1条件模式43第二步、FP-growth最后考虑I1，得到条件模式基<(I2:4)>构造条件FP-tree得到I1的频繁项目集{{I2,I1:4}Item-nameNode-headI2NullI2:4第二步、FP-growth最后考虑I1，得到条件模式基Ite44项条件模式基条件FP树产生的频繁模式I5{{I2,I1:1},{I2,I1,I3:1}}<I2:2,I1:2>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}I4{{I2,I1:1},{I2:1}}<I2:2>{I2,I4:2}I3{{I2,I1:2},{I2:2}{I1:2}}<I2:4,I1:2>,<I1:2>{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}I1{{I2:4}}<I2:4>{I2,I1:4}通过创建条件模式基挖掘FP树的结果项条件模式基条件FP树产生的频繁模式I5{{I2,I1:45FP-Growth算法的优点分治策略:根据当前已获得的频繁模式分解挖掘任务和DB搜索更小的数据库其它因素无需产生候选，从而测试候选项压缩的数据库:FP-tree结构无需重复扫描整个数据库基本操作:统计局部频繁项，建立子FP-tree,无需模式搜索和匹配FP-Growth算法的优点分治策略:46目录关联规则挖掘介绍Apriori算法介绍FP-growth算法介绍强规则、关联与相关分析目录关联规则挖掘介绍47关联规则的兴趣度度量客观度量两个流行的度量指标支持度置信度主观度量最终，只有用户才能确定一个规则是否有趣的，而且这种判断是主观的，因不同的用户而异；通常认为一个规则（模式）是有趣的，如果：它是出人意料的可行动的（用户可以使用该规则做某些事情）挖掘了关联规则后，哪些规则是用户感兴趣的？强关联规则是否就是有趣的？关联规则的兴趣度度量客观度量48对强关联规则的批评（1）例1：(Aggarwal&Yu,PODS9