新版数据挖掘第6章--挖掘频繁模式、关联和相关性：基本概念和方法

第6章-挖掘频繁模式、关联和相关性：基本概念和方法基本概念购物篮分析：一个诱发例子频繁项集、闭项集和关联规则频繁项集挖掘方法哪些模式是有趣的：模式评估方法购物篮分析：―尿布与啤酒”•采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。购物篮分析如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示（0001001100，这种方法丢失了什么信息？）关联规则的两个兴趣度度量–支持度–置信度%]60%,2[sup),(),(confidenceportsoftwareXbuyscomputerXbuys频繁项集、闭项集和关联规则频繁项集、闭项集基本概念–k－项集：包含k个项的集合•{牛奶，面包，黄油}是个3－项集–项集的频率是指包含项集的事务数–如果项集的频率大于（最小支持度×D中的事务总数），则称该项集为频繁项集–项集X在数据集D中是闭的，即不存在真超项集Y’使得Y与X在D中具有相同的支持度计数，则项集X是数据集D中的闭项集频繁项集、闭项集和关联规则关联规则：基本概念给定：–项的集合：I={i1,i2,...,in}–任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得–每个事务由事务标识符TID标识；–A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：–其中并且，规则在事务集D中成立，并且具有支持度s和置信度cITTA],[csBAIBIA,BABA项的集合I={A,B,C,D,E,F}每个事务T由事务标识符TID标识，它是项的集合比如：TID(2000)={A,B,C}任务相关数据D是数据库事务的集合关联规则基本概念——示例TID购买的item2000A,B,C1000A,C4000A,D5000B,E,F规则度量：支持度和置信度TID购买的item2000A,B,C1000A,C4000A,D5000B,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeer对所有满足最小支持度和置信度的关联规则–支持度s是指事务集D中包含的百分比–置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度为50%，最小置信度为50%，则有如下关联规则–AC(50%,66.6%)–CA(50%,100%)BA)()(supBAPBAport)(/)()|()(APBAPABPBAconfidence关联规则挖掘过程大型数据库中的关联规则挖掘包含两个过程：–找出所有频繁项集※大部分的计算都集中在这一步–由频繁项集产生强关联规则※即满足最小支持度和最小置信度的规则关联规则有多种分类：根据规则中所处理的值类型布尔关联规则量化关联规则（规则描述的是量化的项或属性间的关联性）根据规则中涉及的数据维单维关联规则（仅涉及buys这个维）多维关联规则关联规则挖掘分类(1)),()48...42,()39...30,(computerXbuyskkXincomeXage),(),(softwareXbuyscomputerXbuyssoftwaremanagementfinancialcomputer__关联规则挖掘分类(2)根据规则集所涉及的抽象层单层关联规则多层关联规则（在不同的抽象层发现关联规则）根据关联挖掘的各种扩充挖掘最大的频繁模式（该模式的任何真超模式都是非频繁的）挖掘频繁闭项集（一个项集c是频繁闭项集，如果不存在其真超集c’，使得每个包含c的事务也包含c’）（最大的频繁模式和频繁闭项集可以用来减少挖掘中产生的频繁项集）)_,()39...30,(computerlaptopXbuysXage),()39...30,(computerXbuysXage由事务数据库挖掘单维布尔关联规则•最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。TransactionIDItemsBought2000A,B,C1000A,C4000A,D5000B,E,FFrequentItemsetSupport{A}75%{B}50%{C}50%{A,C}50%最小支持度50%最小置信度50%对规则AC，其支持度=50%置信度%6.66)(sup/)(sup)(/)()|()(AportCAportAPCAPACPCAconfidence)()(supCAPCAport11基本概念频繁项集挖掘方法Apriori算法：通过限制候选产生发现频繁项集由频繁项集产生关联规则提高Apriori算法的效率挖掘频繁项集的模式增长方法使用垂直数据格式挖掘频繁项集挖掘闭模式和极大模式哪些模式是有趣的：模式评估方法第6章-挖掘频繁模式、关联和相关性：基本概念和方法Apriori算法：通过限制候选产生发现频繁项集Apriori算法是挖掘布尔关联规则频繁项集的算法Apriori算法利用的是Apriori性质：频繁项集的所有非空子集也必须是频繁的。–模式不可能比A更频繁的出现–Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。–Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率BAApriori算法：通过限制候选产生发现频繁项集Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将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删除。21ll])1[]1[(])2[]2[(...])2[]2[(])1[]1[(21212121klklklklllllApriori算法——示例最小支持计数：2DatabaseTDB1stscanC1L1L2C2C22ndscanC3L33rdscanTidItems10A,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}216Itemsetsup{A}2{B}3{C}3{D}1{E}3使用Apiori性质由L2产生C31．连接：–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}}由频繁项集产生关联规则同时满足最小支持度和最小置信度的才是强关联规则，从频繁项集产生的规则都满足支持度要求，而其置信度则可由一下公式计算：每个关联规则可由如下过程产生：–对于每个频繁项集l，产生l的所有非空子集；–对于每个非空子集s，如果则输出规则“”)(_sup)(_sup)|()(AcountportBAcountportABPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls提高Apriori算法的效率低效率的Apriori可能需要产生大量的候选项集.可能需要重复扫描整个数据库，通过模式匹配检验一个很大的候选集合。104个频繁1项集发掘一个频繁模式,｛a1,…a100｝多达107个候选2项集1030个候选项集提高基于Apriori挖掘效率的算法•基于散列的技术•事物归约技术•划分计术•抽样技术•动态项集计数计术•频繁模式增长但是它们仍然需要产生大量的候选集或者反复的浏览数据库挖掘频繁项集的模式增长方法频繁增长模式适应了分治策略，如下所示.：将代表频繁项集的数据库压缩到一颗频繁模式树（FP-tree），该树仍保留项集的关联信息。把这种压缩后的数据库分解成一组条件数据库,每个数据库关联一个频繁项或“模式段”并且分别挖掘每个条件数据库。示例TIDListofitem_IDsT100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3第一步123规定最小支持度计数，例子中最小支持度计数是2.数据库的第一次扫描和Apriori算法一样，它导出频繁项的集合并得到它们的支持度计数。频繁项的集合按支持度计数的递减排序。。结果集或表记为L。第一步的结果项支持度计数(frequencies)I27I16I36I42I52第二步:频繁模式树I1:1I36支持度计数I2I1I4I57622项ID节点链I3:1I4:1I3:1I1:1I2:1I5:1I3:1I4: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}I5:1第三步:频繁模式树挖掘•由长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基。•构造它的（条件）FP树,并递归地在该树上进行挖掘。•模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。频繁模式树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}对项I5挖掘项条件模式基条件FP树{