数据挖掘挖掘频繁模式关联和相关性

数据挖掘挖掘频繁模式关联和相关性演示文稿现在是1页\一共有45页\编辑于星期六第二章挖掘频繁模式、关联和相关性1基本概念2频繁项集挖掘方法3模式评估方法目录第一章现在是2页\一共有45页\编辑于星期六基本概念现在是3页\一共有45页\编辑于星期六购物篮分析：“尿布与啤酒”采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。4现在是4页\一共有45页\编辑于星期六购物篮分析关联规则表示如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？）关联规则的两个兴趣度度量支持度置信度5现在是5页\一共有45页\编辑于星期六频繁项集、闭项集和关联规则频繁项集、闭项集基本概念k－项集：包含k个项的集合。例如：{牛奶，面包，黄油}是个3－项集项集的频率是指包含项集的事务数如果项集的频率大于最小支持度×D中的事务总数，则称该项集为频繁项集项集X在数据集D中是闭的，即不存在真超项集Y，使得Y与X在D中具有相同的支持度计数，则项集X是数据集D中的闭项集6现在是6页\一共有45页\编辑于星期六频繁项集、闭项集和关联规则关联规则：基本概念给定：项的集合：I={i1,i2,...,in}任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度c7现在是7页\一共有45页\编辑于星期六关联规则基本概念——示例项的集合I={A,B,C,D,E,F}任务相关数据D是数据库事务的集合每个事务T由事务标识符TID标识，它是项的集合比如：TID(2000)={A,B,C}TID购买的item2000A,B,C1000A,C4000A,D5000B,E,F8现在是8页\一共有45页\编辑于星期六规则度量：支持度和置信度对所有满足最小支持度和置信度的关联规则支持度s是指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度为50%，最小置信度为50%，则有如下关联规则A

C(50%,66.6%)；CA(50%,100%)TID购买的item2000A,B,C1000A,C4000A,D5000B,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeer9现在是9页\一共有45页\编辑于星期六关联规则挖掘过程大型数据库中的关联规则挖掘包含两个过程找出所有频繁项集大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则10现在是10页\一共有45页\编辑于星期六关联规则挖掘分类根据规则中所处理的值类型布尔关联规则量化关联规则（规则描述的是量化的项或属性间的关联性）根据规则中涉及的数据维单维关联规则（仅涉及buys这个维）多维关联规则11现在是11页\一共有45页\编辑于星期六关联规则挖掘分类根据关联挖掘的各种扩充挖掘最大的频繁模式挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c’，使得每个包含c的事务也包含c’）最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集根据规则集所涉及的抽象层单层关联规则多层关联规则（在不同的抽象层发现关联规则）12现在是12页\一共有45页\编辑于星期六由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘置信度最小支持度50%最小置信度50%对规则AC，其支持度=50%13现在是13页\一共有45页\编辑于星期六频繁项集挖掘方法现在是14页\一共有45页\编辑于星期六Apriori算法：通过限制候选产生发现频繁项集Apriori算法是挖掘布尔关联规则频繁项集的算法Apriori算法利用的是Apriori性质频繁项集的所有非空子集也必须是频繁的如果{beer,diaper,nuts}是频繁的,{beer,diaper}也是非频繁项集的超集一定是非频繁的15现在是15页\一共有45页\编辑于星期六Apriori算法：通过限制候选产生发现频繁项集Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-项集用于探察(k+1)-项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。16现在是16页\一共有45页\编辑于星期六Apriori算法步骤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删除

17现在是17页\一共有45页\编辑于星期六Apriori算法——示例DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,C,D20B,C,E30A,B,C,E40B,EItemsetsup{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}2Itemsetsup{A}2{B}3{C}3{D}1{E}3最小支持度计数为218现在是18页\一共有45页\编辑于星期六使用Apiori性质由L2产生C3连接L2={{A,C},{B,C},{B,E}{C,E}}L2

*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,E}}19现在是19页\一共有45页\编辑于星期六由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：每个关联规则可由如下过程产生对于每个频繁项集L，产生L的所有非空子集对于每个非空子集s，如果 则输出规则“ ”20现在是20页\一共有45页\编辑于星期六提高Apriori算法的效率低效率的Apriori可能需要产生大量的候选项集

可能需要重复扫描整个数据库，通过模式匹配检验一个很大的候选集合102

个频繁1项集发掘一个频繁模式,｛a1,…a100｝多达103

个候选2项集1030

个候选项集21现在是21页\一共有45页\编辑于星期六提高基于Apriori挖掘效率的算法基于散列的技术事物归约技术划分计术抽样技术动态项集计数计术频繁模式增长但是它们仍然需要产生大量的候选集或者反复的浏览数据库22现在是22页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法频繁增长模式适应了分治策略，如下所示将代表频繁项集的数据库压缩到一颗频繁模式树（FP-tree），该树仍保留项集的关联信息。把这种压缩后的数据库分解成一组条件数据库,每个数据库关联一个频繁项或“模式段”并且分别挖掘每个条件数据库。23现在是23页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法示例TIDListofitem_IDsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I324现在是24页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法第一步规定最小支持度计数，例子中最小支持度计数是2数据库的第一次扫描和Apriori算法一样，它导出频繁项的集合并得到它们的支持度计数频繁项的集合按支持度计数的递减排序。结果集或表记为L25现在是25页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法第一步的结果项支持度计数(frequencies)I27I16I36I42I5226现在是26页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法第二步:频繁模式树生成I1:1I36支持度计数I2I1I4I57622项ID节点链I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:1Null{}Null{}Null{}Null{}Null{}2342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}27现在是27页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法第三步:频繁模式树挖掘由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基构造它的（条件）FP树,并递归地在该树上进行挖掘模式增长通过后缀模式与条件FP树产生的频繁模式连接实现28现在是28页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法频繁模式树I1:1Null{}Null{}Null{}Null{}Null{}I36支持度计数I2I1I4I57622项ID节点链I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:12342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}29现在是29页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法对项I5挖掘项条件模式基条件FP树{{I2,I1:1},{I2,I1,I3:1}}<I2:2,I1:2>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}I5产生的频繁模式T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}30现在是30页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法频繁模式树I1:1Null{}Null{}Null{}Null{}Null{}I36支持度计数I2I1I4I57622项ID节点链I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:12342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}31现在是31页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法对项I4挖掘产生的频繁模式产生的频繁模式条件模式基条件FP树I4{{I2,I1:1},{I2,I1,I3:1}}{{I2,I1:1},{I2:1}}<I2:2,I1:2><I2:2>I5{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}{I2,I4:2}T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}32现在是32页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法频繁模式树I1:1Null{}Null{}Null{}Null{}Null{}I36支持度计数I2I1I4I57622项ID节点链I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:1234225226374233现在是33页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法对I3挖掘产生的频繁模式产生的频繁模式项条件模式基条件FP树I4I3{{I2,I1:1},{I2,I1,I3:1}}{{I2,I1:1},{I2:1}}{{I2,I1:2},{I2:2},{I1:2}}<I2:2,I1:2><I2:2><I2:4,I1:2>,<I1:2>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}{I2,I4:2}{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}I5T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}34现在是34页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法频繁模式树I1:1Null{}Null{}Null{}Null{}Null{}I36支持度计数I2I1I4I57622项ID节点链I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4:1I5:12342252263742T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}35现在是35页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法与条件节点I1相关联的条件FP树I2I144项ID支持度计数节点链Null{}I1:2I2:4I1:2T100{I2，I1，I5}T200{I2，I4}T300{I2，I3}T400{I2，I1，I4}T500{I1，I3}T600{I2，I3}T700{I1，I3}T800{I2,I1,I3,I5}T900{I2，I1，I3}36现在是36页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法挖掘结果项条件模式基条件FP树I4I3I1{{I2,I1:1},{I2,I1,I3:1}}{{I2,I1:1},{I2:1}}{{I2,I1:2},{I2:2},{I1:2}}{{I2:4}}<I2:2,I1:2><I2:2><I2:4,I1:2>,<I1:2><I2:4>{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}{I2,I4:2}{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}{I2,I1:4}I537现在是37页\一共有45页\编辑于星期六挖掘频繁项集的模式增长方法局限性当数据库很大时,构造基于主存的FP树有时是不现实的将数据库划分成投影数据库的集合，然后在每个投影数据库上构造FP树并在每个投影数据库中挖掘优势将发现的长频繁模式问题转换成较小的条件数据库中递归地搜索一些较短的模式，然后连接后缀对于挖掘长的频繁模式和短的频繁模式它都是有效的和可伸缩的，并且大约比Apriori算法快一个数量级38现在是38页\一共有45页\编辑于星期六使用垂直数据格式挖掘频繁项集最小支持度计数为2DatabaseTDBL1L2TID-集TID-集10A,C,D20B,C,E30A,B,C,E40B,E项集TID-集