《数据挖掘第6章挖掘频繁模式关联和相关性》由会员分享，可在线阅读，更多相关《数据挖掘第6章挖掘频繁模式关联和相关性（45页珍藏版）》请在金锄头文库上搜索。
1、数据挖掘与商务智能范勤勤范勤勤物流研究中心物流研究中心第二章挖掘频繁模式、关联和相关性1基本概念2频繁项集挖掘方法3模式评估方法目录 第一章1基本概念454购物篮分析：“尿布与啤酒”采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。45购物篮分析关联规则表示如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来
2、表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？）5关联规则的两个兴趣度度量支持度置信度45频繁项集、闭项集和关联规则频繁项集、闭项集基本概念k项集：包含k个项的集合。例如：牛奶，面包，黄油是个3项集项集的频率是指包含项集的事务数如果项集的频率大于最小支持度D中的事务总数，则称该项集为频繁项集项集X在数据集D中是闭的，即不存在真超项集Y，使得Y与X在D中具有相同的支持度计数，则项集X是数据集D中的闭项集645频繁项集、闭项集和关联规则7关联规
3、则：基本概念给定：项的集合：I=i1,i2,.,in任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度c45关联规则基本概念示例8项的集合I=A,B,C,D,E,F任务相关数据D是数据库事务的集合每个事务T由事务标识符TID标识，它是项的集合比如：TID(2000)=A,B,CTID购买的item2000A,B,C1000A,C4000A,D5000B,E,F45规则度量：支持度和置信度对所有满足最小支持度和置信度的关联规则支持度s是
4、指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比9假设最小支持度为50%，最小置信度为50%，则有如下关联规则A C(50%,66.6%)；CA(50%,100%)TID购买的item2000A,B,C1000A,C4000A,D5000B,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeer45关联规则挖掘过程大型数据库中的关联规则挖掘包含两个过程找出所有频繁项集大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则104511关联规则挖掘分类根据规则中所处理的值类型布尔关联规则量化关
5、联规则（规则描述的是量化的项或属性间的关联性）根据规则中涉及的数据维单维关联规则（仅涉及buys这个维）多维关联规则4512关联规则挖掘分类根据关联挖掘的各种扩充挖掘最大的频繁模式挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c，使得每个包含c的事务也包含c）最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集根据规则集所涉及的抽象层单层关联规则多层关联规则（在不同的抽象层发现关联规则）45由事务数据库挖掘单维布尔关联规则13最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘置信度最小支持度50%最小置信度50%对规则AC，其支持度=50%2频繁项集挖掘方法45Aprio
6、ri算法：通过限制候选产生发现频繁项集Apriori算法是挖掘布尔关联规则频繁项集的算法15Apriori算法利用的是Apriori性质频繁项集的所有非空子集也必须是频繁的如果 beer, diaper, nuts 是频繁的, beer, diaper也是非频繁项集的超集一定是非频繁的45Apriori算法：通过限制候选产生发现频繁项集Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到
7、频繁k-项集，找每个Lk需要一次数据库扫描。1645Apriori算法步骤Apriori算法由连接和剪枝两个步骤组成。连接：为了找Lk，通过Lk-1与自己连接产生候选k-项集的集合，该候选k项集记为Ck。Lk-1中的两个元素l1和l2可以执行连接操作的条件是剪枝Ck是Lk的超集（LkCk），即它的成员可能不是频繁的，但是所有频繁的k-项集都在Ck中。因此可以通过扫描数据库，通过计算每个k-项集的支持度来得到Lk为了减少计算量，可以使用Apriori性质，即如果一个k-项集的(k-1)-子集不在Lk-1中，则该候选不可能是频繁的，可以直接从Ck删除174518Apriori算法示例Databas
8、e TDB1st scanC1L1L2C2C22nd scanC3L33rd scanTidItems10A, C, D20B, C, E30A, B, C, E40B, EItemsetsupA2B3C3E3ItemsetA, BA, CA, EB, CB, EC, EItemsetsupA, B1A, C2A, E1B, C2B, E3C, E2ItemsetsupA, C2B, C2B, E3C, E2ItemsetB, C, EItemsetsupB, C, E2ItemsetsupA2B3C3D1E3最小支持度计数为245使用Apiori性质由L2产生C3连接L2=A,C,B,C,B
9、,EC,EL2*L2使用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的元素，因此保留这个选项。这样，剪枝后得到C3=B,C,E1945由频繁项集产生关联规则20同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：每个关联规则可由
10、如下过程产生对于每个频繁项集L，产生L的所有非空子集对于每个非空子集s，如果则输出规则“”45提高Apriori算法的效率21低效率的Apriori可能需要产生大量的候选项集可能需要重复扫描整个数据库，通过模式匹配检验一个很大的候选集合102个频繁1项集发掘一个频繁模式,a1,a100多达103个候选2项集1030个候选项集4522提高基于Apriori挖掘效率的算法基于散列的技术事物归约技术划分计术抽样技术动态项集计数计术频繁模式增长但是它们仍然需要产生大量的候选集或者反复的浏览数据库45挖掘频繁项集的模式增长方法频繁增长模式适应了分治策略，如下所示将代表频繁项集的数据库压缩到一颗频繁模式树
11、（FP-tree），该树仍保留项集的关联信息。把这种压缩后的数据库分解成一组条件数据库,每个数据库关联一个频繁项或“模式段”并且分别挖掘每个条件数据库。2345挖掘频繁项集的模式增长方法示例24TIDListofitem_IDsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I345挖掘频繁项集的模式增长方法第一步规定最小支持度计数，例子中最小支持度计数是2数据库的第一次扫描和Apriori算法一样，它导出频繁项的集合并得到它们的支持度计数频繁项的集合按支
12、持度计数的递减排序。结果集或表记为L2545挖掘频繁项集的模式增长方法第一步的结果26项支持度计数(frequencies)I27I16I36I42I5245挖掘频繁项集的模式增长方法第二步:频繁模式树生成27I1: 1I36支持度计数I2I1I4I57622 项ID节点链I3: 1I4: 1I3: 1I1: 1I2: 1I5:1I3: 1I4:1I5:1NullNullNullNullNull2 3 42252263742T100I2，I1，I5T200I2，I4T300I2，I3T400I2，I1，I4T500I1，I3T600I2，I3T700I1，I3T800I2,I1,I3,I5T9
13、00I2，I1，I345挖掘频繁项集的模式增长方法第三步:频繁模式树挖掘由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基构造它的（条件）FP树,并递归地在该树上进行挖掘模式增长通过后缀模式与条件FP树产生的频繁模式连接实现2845挖掘频繁项集的模式增长方法频繁模式树29I1: 1NullNullNullNullNullI36支持度计数I2I1I4I57622项ID节点链I3: 1I4: 1I3: 1I1: 1I2: 1I5:1I3: 1I4:1I5:12 3 42252263742T100I2，I1，I5T200I2，I4T300I2，I3T400I2，I1，I4T500I1，I3
14、T600I2，I3T700I1，I3T800I2,I1,I3,I5T900I2，I1，I345挖掘频繁项集的模式增长方法对项I5挖掘30项条件模式基条件FP树 I2,I1:1,I2,I1,I3:1 I2,I5:2,I1,I5:2,I2,I1,I5:2I5产生的频繁模式T100I2，I1，I5T200I2，I4T300I2，I3T400I2，I1，I4T500I1，I3T600I2，I3T700I1，I3T800I2,I1,I3,I5T900I2，I1，I345挖掘频繁项集的模式增长方法频繁模式树31I1: 1NullNullNullNullNullI36支持度计数I2I1I4I57622项ID
15、节点链I3: 1I4: 1I3: 1I1: 1I2: 1I5:1I3: 1I4:1I5:12 3 42252263742T100I2，I1，I5T200I2，I4T300I2，I3T400I2，I1，I4T500I1，I3T600I2，I3T700I1，I3T800I2,I1,I3,I5T900I2，I1，I345挖掘频繁项集的模式增长方法对项I4挖掘32产生的频繁模式产生的频繁模式条件模式基条件FP树I4 I2,I1:1,I2,I1,I3:1 I2,I1:1,I2:1 I5I2,I5:2,I1,I5:2,I2,I1,I5:2I2,I4:2T100I2，I1，I5T200I2，I4T300I2
16、，I3T400I2，I1，I4T500I1，I3T600I2，I3T700I1，I3T800I2,I1,I3,I5T900I2，I1，I345挖掘频繁项集的模式增长方法频繁模式树33I1: 1NullNullNullNullNullI36支持度计数I2I1I4I57622项ID节点链I3: 1I4: 1I3: 1I1: 1I2: 1I5:1I3: 1I4:1I5:12 3 4225226374245挖掘频繁项集的模式增长方法对I3挖掘34产生的频繁模式产生的频繁模式项条件模式基条件FP树I4I3 I2,I1:1,I2,I1,I3:1 I2,I1:1,I2:1 I2,I1:2,I2:2,I1:2
17、 ,I2,I5:2,I1,I5:2,I2,I1,I5:2I2,I4:2I2,I3:4,I1,I3:4,I2,I1,I3:2I5T100I2，I1，I5T200I2，I4T300I2，I3T400I2，I1，I4T500I1，I3T600I2，I3T700I1，I3T800I2,I1,I3,I5T900I2，I1，I345挖掘频繁项集的模式增长方法频繁模式树35I1: 1NullNullNullNullNullI36支持度计数I2I1I4I57622项ID节点链I3: 1I4: 1I3: 1I1: 1I2: 1I5:1I3: 1I4:1I5:12 3 42252263742T100I2，I1，I
18、5T200I2，I4T300I2，I3T400I2，I1，I4T500I1，I3T600I2，I3T700I1，I3T800I2,I1,I3,I5T900I2，I1，I345挖掘频繁项集的模式增长方法与条件节点I1相关联的条件FP树36I2I144项ID支持度计数节点链NullI1:2I2:4I1:2T100I2，I1，I5T200I2，I4T300I2，I3T400I2，I1，I4T500I1，I3T600I2，I3T700I1，I3T800I2,I1,I3,I5T900I2，I1，I345挖掘频繁项集的模式增长方法挖掘结果37项条件模式基条件FP树I4I3I1I2,I1:1,I2,I1,I
19、3:1I2,I1:1,I2:1I2,I1:2,I2:2,I1:2I2:4,I2,I5:2,I1,I5:2,I2,I1,I5:2I2,I4:2I2,I3:4,I1,I3:4,I2,I1,I3:2I2,I1:4I545挖掘频繁项集的模式增长方法局限性当数据库很大时,构造基于主存的FP树有时是不现实的将数据库划分成投影数据库的集合，然后在每个投影数据库上构造FP树并在每个投影数据库中挖掘优势将发现的长频繁模式问题转换成较小的条件数据库中递归地搜索一些较短的模式，然后连接后缀对于挖掘长的频繁模式和短的频繁模式它都是有效的和可伸缩的，并且大约比Apriori算法快一个数量级3845使用垂直数据格式挖掘频
20、繁项集最小支持度计数为239Database TDBL1L2TID-集集TID-集集10A, C, D20B, C, E30A, B, C, E40B, E项集项集TID-集集A10,30B20,30,40C10,20,30D10E20,30,40项集项集TID-集集A,C10,30B,C20,30B,E20,30C,E20,30项集项集TID-集集B, C, E20,30L345挖掘闭模式和极大模式挖掘方法挖掘频繁项集的完全集，再删除这样的频繁集直接搜索闭频繁项集，但要求一旦识别闭项集就尽快对搜索空间剪枝，剪枝策略如下：项合并子项集剪枝项跳过403模式评估方法45强规则不一定是有趣的示例假设
21、我们对涉及购买计算机游戏和录像的allelectronices的事务感兴趣，在10000个事务中，6000个顾客事务包含计算机游戏，7500个事务包含录像，4000个事务同时包含，规定minsup=30%，mincov=60%，并且服从规则：buys(X,”computergames”)=buys(X,”videos”)可知这是强关联规则，其sup=40%，cov=66%,分别满足minsup和mincov，然而购买录像的概率为75%，比66%还高。结论规则A=B的置信度有一定的欺骗性，这并不能度量A和B之间的实际强度。4245由关联分析到相关分析当项集A的出现独立于项集B的出现时，P(AB)=P(A)P(B)，即corrA,B1，表明A与B无关， corrA,B 1表明A与B正相关，corrA,B1表明A与B负相关将相关性指标用于前面的例子，可以得出录像带和游戏将的相关性为：P(game,video)/(P(game)P(video)=0.4/(0.750.6)=0.89结论：录像带和游戏之间存在负相关43我们需要一种度量事件间的相关性或者是依赖性的指标45模式评估度量比较评估度量的模式度 2全置信度最大置信度Kulczynski余弦44谢谢关注欢迎指导
