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

目录关联规则挖掘介绍Apriori算法介绍FP-growth算法介绍强规则、关联与相关分析什么是关联规则挖掘？关联规则挖掘：从事务数据库，关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。应用：购物篮分析、分类设计、捆绑销售和亏本销售分析、Web日志（点击流）分析，和DNA序列分析。“尿布与啤酒”——典型关联分析案例采用关联模型比较典型的案例是“尿布与啤酒”的故事。在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30%～40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起，明显增加了销售额。同样的，我们还可以根据关联规则在商品销售方面做各种促销活动。购物篮分析——一个诱发的例子购物篮分析——一个诱发的例子策略一：把经常同时购买的商品摆放在一起，以便进一步刺激这些商品同时销售。(如计算机和杀毒软件)策略二：把经常同时购买的商品摆放在商店的两端，使顾客多看更多的商品，用来带动其他商品的出售。购物篮分析——一个诱发的例子如果问题的全域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是否被顾客购买，则每个购物篮都可以用一个布尔向量表示（0001001100）；而通过分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以用关联规则表示。关联规则的两个兴趣度度量支持度（support）置信度（confidence）关联规则：基本概念给定：项的集合：I={i1,i2,...,in}任务相关数据D是数据库事务的集合，每个事务T则是项的集合，使得每个事务由事务标识符TID标识；A,B为两个项集，事务T包含A当且仅当则关联规则是如下蕴涵式：其中并且，规则在事务集D中成立，并且具有支持度s和置信度cITTA],[csBAIBIA,BABA规则度量：支持度和置信度TID购买的item2000A,B,C1000A,C4000A,D5000B,E,FCustomerbuysdiaperCustomerbuysbothCustomerbuysbeer对所有满足最小支持度（min-sup)和置信度(min-con)的关联规则支持度s是指事务集D中包含的百分比置信度c是指D中包含A的事务同时也包含B的百分比假设最小支持度为50%，最小置信度为50%，则有如下关联规则AC(50%,66.6%)CA(50%,100%)BA)()(supBAPBAport)(/)()|()(APBAPABPBAconfidence由事务数据库挖掘单维布尔关联规则最简单的关联规则挖掘，即单维、单层、布尔关联规则的挖掘。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大型数据库关联规则挖掘过程基本概念k－项集：包含k个项的集合{牛奶，面包，黄油}是个3－项集项集的频率是指包含项集的事务数如果项集的频率大于（最小支持度×D中的事务总数），则称该项集为频繁项集大型数据库中的关联规则挖掘包含两个过程：找出所有频繁项集大部分的计算都集中在这一步由频繁项集产生强关联规则即满足最小支持度和最小置信度的规则目录关联规则挖掘介绍Apriori算法介绍FP-growth算法介绍强规则、关联与相关分析Apriori算法Apriori算法利用频繁项集性质的先验知识（priorknowledge），通过逐层搜索的迭代方法，即将k-1项集用于探察k项集，来穷尽数据集中的所有频繁项集。先找到频繁1-项集集合L1,然后用L1找到频繁2-项集集合L2，接着用L2找L3，直到找不到频繁k-项集，找每个Lk需要一次数据库扫描。Apriori性质：频繁项集的所有非空子集也必须是频繁的。（模式不可能比A更频繁的出现）Apriori算法是反单调的，即一个集合如果不能通过测试，则该集合的所有超集也不能通过相同的测试。频繁模式：是指频繁地出现在数据集中的模式（如项集、子序列或子结构）。频繁项集：频繁地同时出现在交易数据集中的数据集合。BA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删除。])1[]1[(])2[]2[(...])2[]2[(])1[]1[(21212121klklklklllll21llApriori算法——示例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}2使用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的所有非空子集；对于l的每个非空子集s，如果则输出规则“”)(_sup)(_sup)|()(AcountportBAcountportBAPBAconfidenceconfscountportlcountportmin_)(_sup)(_sup)(sls例题：交易记录事务数据库有9个事务。用Apriori算法寻找D中的频繁项集。例题：交易记录事务数据库有9个事务。用Apriori算法寻找D中的频繁项集。算法使用L3L3产生候选4-项集的集合C4。C4={{I1，I2，I3，I5}}，因为它的子集{I2,I3，I5}不是频繁的，这个项集被剪去，这样C4=Ø，因此算法终止，找出了所有的频繁项集。提高Apriori算法的有效性(1)Apriori算法主要的挑战要对数据进行多次扫描；会产生大量的候选项集；对候选项集的支持度计算非常繁琐；解决思路减少对数据的扫描次数；缩小产生的候选项集；改进对候选项集的支持度计算方法方法1：基于hash表的项集计数将每个项集通过相应的hash函数映射到hash表中的不同的桶中，这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。提高Apriori算法的有效性(2)方法2：事务压缩（压缩进一步迭代的事务数）不包含任何k-项集的事务不可能包含任何(k+1)-项集，这种事务在下一步的计算中可以加上标记或删除。方法3：划分挖掘频繁项集只需要两次数据扫描D中的任何频繁项集必须作为局部频繁项集至少出现在一个部分中。第一次扫描：将数据划分为多个部分并找到局部频繁项集第二次扫描：评估每个候选项集的实际支持度，以确定全局频繁项集提高Apriori算法的有效性(3)方法4：选样（在给定数据的一个子集挖掘）基本思想：选择原始数据的一个样本，在这个样本上用Apriori算法挖掘频繁模式通过牺牲精确度来减少算法开销，为了提高效率，样本大小应该以可以放在内存中为宜，可以适当降低最小支持度来减少遗漏的频繁模式可以通过一次全局扫描来验证从样本中发现的模式可以通过第二此全局扫描来找到遗漏的模式方法5：动态项集计数在扫描的不同点添加候选项集，这样，如果一个候选项集已经满足最少支持度，则在可以直接将它添加到频繁项集，而不必在这次扫描的以后对比中继续计算。目录关联规则挖掘介绍Apriori算法介绍FP-growth算法介绍强规则、关联与相关分析FP-Growth算法AProiri算法需要产生大量候选项集,而且需要多次扫描数据库,然后通过模式匹配检查一个很大的候选集合,在挖掘长模式时,算法性能退化很快。Han提出了一种频繁模式增长算法(FP-Growth)，不产生候选集而直接产生全部频繁项集。FP-Growth算法采用了分而治之策略:首先，将提供频繁项集的数据库压缩成一棵频繁模式树(FP)，该树仍保留项集关联信息,然后，将这种压缩后的数据库划分成一组条件数据库，每个数据库关联一个频繁项，并分别挖掘每个条件数据库。使用FP-Growth算法挖掘频繁模式数据库中有9个事务,即|D|=9,如表所示，事务中的项按字典次次序存放。表中有9个交易的数据库事务项ID列表事务项ID列表T100I1,I2,I5T600I2,I3T200I2,I4T700I1,I3T300I2,I3T800I1,I2,I3,I5T400I1,I2,I4T900I1,I2,I3T500I1,I3FP树构造FP-树构造如下:1）创建树的根节点,用”null”标记。2）第二次扫描数据库,每个事务中的项按L中的次序处理(处理后的数据库见表1-2),并对每个事务创建一个分枝,若节点或分枝已经存在,则共享节点或分枝,同时将共享前缀上的每个结点的计数加1，为前缀之后的项创建结点和链接。若不存在，则以根结点为父结点将该事务中的项按L中的次序依次插入。扫描所有的事务之后得到的树如图所示。第一步、构造FP-tree扫描事务数据库得到频繁1-项目集F定义minsup=20%，即最小支持度为2重新排列FI1I2I3I4I567622I2I1I3I4I576622重新调整事务数据库TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3创建根结点和频繁项目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull加入第一个事务(I2,I1,I5)Item-nameNode-headI2I1I3NullI4NullI5NullI2:1I1:1I5:1加入第二个事务(I2,I4)Item-nameNode-h