智能推荐2关联分析概要ppt课件.ppt

主讲 张荣梅2014.10,数据挖掘导论关联规则,数据挖掘算法所处位置,数据挖掘算法功能,根据所挖掘知识的类型不同：为了反映事物之间依赖或关联的为了反映同类事物共同性质的为了反映事物各方面特征的为了反映不同事物之间属性差别的根据历史的和当前的数据推测未来数据揭示事物偏离常规的异常现象,数据挖掘技术,关联（Association）分类（Classification）预测（Prediction）聚类（Clustering）Web挖掘技术,3 挖掘频繁模式和关联规则,3.1 基本概念3.2 Apriori算法3.3 其他算法概述,3.1 关联的基本概念,若两个或多个变量的取值之间存在某种规律性，就称为关联。关联规则是寻找同一事件中出现的不同项的相关性，比如在一次购买活动中所购买不同商品的相关性。关联分析即利用关联规则进行数据挖掘。购物篮模型 典型案例-啤酒与尿布,啤酒与尿布,在商业应用中常用关联分析最典型的例子就是一家连锁店(沃尔玛)通过数据挖掘发现了小孩尿布与啤酒之间有着内在的联系，即“啤酒与尿布”的故事。在美国，一些年轻(2535岁）的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有3040%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布与啤酒放在一起，明显增加了销售额。,Customerbuys diaper,Customerbuys both,Customerbuys beer,“啤酒与尿布”的关联规则,更多举例,e.g：在购买铁锤的顾客当中，有70的人同时购买了铁钉。,关联的基本概念,关联 自然界中某种事物发生时其他事物也会发生，则这种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）。关联的类型 分为简单关联、时序关联、因果关联。关联规则 关联是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性。,关联的基本概念,关联规则的数学定义 设I=i1,i2,.,im 是一个以m个不同项的集合，任务相关的数据D是数据库事务（交易）的集合，其中每个事务T是针对I的项的集合，即每一笔交易包含若干个属于I的项。关联规则可表示为：X=Y，其中X,Y I 且 X Y=X称为规则的前提或前项，Y称为结果或后项。规则X=Y在事务集D中成立，具有支持度s，具有置信度c.有两个度量标准：支持度(Support)和可信度(Confidence)。规则的支持度s定义为D中事务包含X U Y 的百分比，即概率P(X UY):support(X=Y)=support(X U Y)=P(X UY)规则的可信度c定义为D中包含X的事务同时也包含Y的百分比，即条件概率P(Y|X)。confidence(X=Y)=support(X U Y)/support(X)=P(Y|X),关联规则的形式 R:X=Y 其中，X及Y是两个不相交的集合，即X,YI且X Y=关联规则可以理解为一个命题，即如果一个交易支持项集X，则它也以一定的可能性支持项集Y，这一可能性称之为规则的可信度，记为conf(R)或C(R),规则形式举例Body Head support,confidencebuys(x,“diapers”)buys(x,“beers”)2%,60%major(x,“CS”)takes(x,“DB”)grade(x,“A”)5%,75%,关联规则挖掘应用实例,通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？这种信息可以引导销售，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。,关联规则挖掘实例,购物篮分析,哪些商品频繁地被顾客同时购买？,3.2 Apriori关联规则挖掘算法,关联规则挖掘是从事务数据库、关系数据库和其它信息存储中的大量数据项集之间发现有趣的、频繁出现的模式、关联和相关性。,关联规则挖掘步骤,一般分为2个步骤：依据支持度找出所有的频繁项集。（频度）依据置信度产生关联规则。（强度）可以根据兴趣度，找出有兴趣的关联规则。,先验算法,基本概念,项,项集,频繁项集,事务,关联规则,置信度,支持度,由此我们引出之后需要的几个概念：,兴趣度,购物篮模型中的有关概念,项商品事务-交易，购物篮项集-每个购物篮由多个项组成的集合。包含k个项的项集称为k项集。milk，bread是一个2项集。支持度-项集的频率，是指包含项集的事务数。如果A是一个项集，A的支持度是指包含A的购物篮的数目。频繁项集-一个在多个购物篮中出现的项集。假定最小支持度阈值为s。如果A的支持度不小于s，则称A是频繁项集。置信度-可信度。规则AB的可信度等于集合AB的支持度与A的支持度的比值兴趣度-关联规则AB的兴趣度定义为其可信度与包含B的购物篮的比率之差。如果为负值或接近于0，则表示关联规则不十分有趣。,关联挖掘实例-最简单的关联规则挖掘,单维、单层、布尔关联规则挖掘,Minsupport=50%Minconfidence=50%,For rule A Csupport=support(A C)=50%confidence=support(A C)/support(A)=66.7%For C A(50%,100%)这就是 Apriori 算法Apriori 性质：Any subset of a frequent itemset must be frequent,（1）找出频繁项集（2）在频繁项集中找出满足置信度的项集,Apriori算法,Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。,按照所处理的值类型不同进行关联规则分类：布尔关联规则，如事务向量（001101100）对每种商品可以用一个布尔量来表示该种商品是否被购买，则每个购物篮可以用一个布尔向量来表示量化关联规则，如AgeX,”30-39”incomeX,”40k48k”=buysX,”computer”,Apriori 算法的步骤,-使用候选产生发现频繁项集。（1）由候选项集(candidate itemset)产生频繁项集(frequent itemset)；（2）由频繁项集(frequent itemset)产生强关联规则(strong association rule)。,Apriori 使用一种称作逐层搜索的迭代方法，“K项集”用于探索“K+1项集”。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁“1项集”的集合。该集合记作L1。然后，L1用于找频繁“2项集”的集合L2，而L2用于找L3，如此下去，直到不能再找到频繁“K项集”。找每个LK需要一次数据库全扫描。为了提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。,Apriori算法,核心：连接步和剪枝步,Apriori性质：任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的。目的：过滤候选项集，减少工作量。用频繁项集Lk-1找频繁项集Lk（k=2),由两步组成：连接步和剪枝步。（1）连接步：为找Lk，通过将Lk-1与自身连接产生候选k项集的集合Ck。然后扫描数据库，确定Ck中每个候选项的计数，从而确定Lk。Ck=Lk-1Lk-1 自连接：按字典顺序连接(2)剪枝步:根据Apriori性质，如果k项集的（k-1)项子集不在Lk-1 中，则该候选也不可能是频繁的，从而可以从Ck中删除。,Apriori算法目的意义,Apriori算法主要为了提高数据访问效率，提升发现频繁项集的速度使用候选产生发现频繁项集Apriori性质：频繁项集的所有非空子集也必须是频繁的。,步骤1：发现频繁项集,频繁项集发现过程：（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）（5）直到不能发现更大频集,步骤2：产生关联规则,根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果则输出规则“S LS”。注：LS表示在项集L中除去S子集的项集。,举 例,由频繁项集产生关联规则,频繁项集l=B,C,EL的非空子集有：B,CB,EC.EBCE,得出关联规则如下：BC=E,confidence=2/2=100%B E=C,confidence=2/3=66.7%C E=B,confidence=2/2=100%B=C E,confidence=2/3=66.7%C=B E,confidence=2/3=66.7%E=B C,confidence=2/3=66.7%如果最小置信度阈值为70%，则只有上面的1,3规则可以输出。,Apriori算法伪代码,算法：Apriori，使用逐层迭代方法基于候选产生找出频繁项集输入：D：事务数据库 min_sup:最小支持度阈值输出：L：D中的频繁项集方法：（1）L 1=find_frequent_1_itemsets(D);（2）for(k=2;L k-1;k+)（3）C k=apriori_gen(L k-1);（4）for each transaction t D/scan D for counts（5）C t=subset(C k,t);/get the subsets of t that are candidates（6）for each candidate c C t（7）c.count+;（8）（9）L k=c Ck|c.countmin_sup（10）（11）return L=k L k;,连接步和剪枝步,第1 步：连接(join)Procedure apriori_gen(L k-1:frequent(k-1)itemset)1)for each itemset l 1L k-1 2)for each itemset l 2L k-1 3)if(l 11=l 21)(l 1k-2=l 2k-2)(l1k-1 l 2k-1)then 4)c=l1l2；/连接，产生候选集 5)if has_infrequent_subset(c，L k-1)then 6)delete c;/修剪，去掉无用的候选项 7)else add c to C k;8)9)return C k;,连接步和剪枝步,第2 步:剪枝(prune)procedure has_infrequent_subset(c:candidate k itemset;L k-1:frequent(k-1)itemset);/使用先验知识 1)for each(k-1)subset s of c2)if sL k-1 then 3)return true;4)return false;,Apriori算法的基本流程,使用逐层搜索的迭代方法，通过对数据库的多次扫描发现所有的频繁项集。在每一趟扫描中只考虑具有同一长度k(即为项集中所含项目的个数)的所有项集。算法的第一次扫描仅仅计算每个项目的具体支持度，以确定长度为1的频繁项集。在后继的每一次扫描中，首先使用在前一次获得的频繁项集Lk-1和Apriori-gen函数产生的候选项集q，接着扫描数据库，计算Ck中候选项的支持度，最后确定候选项集中哪些真正成为频繁项集。重复上述过程直到再也发现不了新的频繁项集为止。,Database D,Scan D,C1,L1,L2,C2,C2,Scan D,C3,L3,Scan D,Apriori算法实例,设定最小支持度阈值为2,练习题下表是某商店的事务数据库D，数据库中有9个事务。试用Apriori算法找出其关联规则。,设定最小支持度阈值为2,扫描D，对每个候选项计数，生成C1：,比较候选项支持度计数与最小支持度计数，生成L1：,由L1产生候选集C2：,再次扫描D，对每个候选项计数，产生L2：,对L2进行连接&剪枝，产生C3，即最终结果。,由频繁项集产生关联规则:L1=I1,I2,I5的非空子集有：I1,I2I1,I5I2,I5I1I2I5,结果关联规则如下：I1 I2=I5 confidence=2/4=50%如果最小置信度阈值为70%，则2I1 I5=I2 confidence=2/2=100%3,6条规则可以输出。I2 I5=I1 confidence=2/2=100%请写出第2个频繁项集的关联规则I1=I2 I5 confidence=2/6=33%I2=I1 I5 confidence=2/7=29%I5=I1 I2 confidence=2/2=100%,可能产生大量的候选集可能需要重复扫描数据库,Apriori算法局限性,Apriori 算法的局限性,可能需要产生大量候选项集。例如，如果有104个频繁1项集，可能产生107个候选2项集。可能需要重复扫描数据库，通过模式匹配检查一个很大的候选集合。由于依赖于候选项集产生频繁项集的理论（Apriori类算法）所开发的算法具有先天的弱点，使得在基于Apriori算法开发的应用没有实质性突破。,FP-growth算法-频繁模式增长,Han等提出的一种新的算法理论，用一种压缩的数据结构(FP-tree)存储关联规则挖掘所需的全部数据信息，通过对源数据的两次扫描，将数据信息存到这种结构里，避开了产生候选项集的步骤，极大地减少了数据交换和频繁匹配的开销。这就是所谓不候选产生挖掘频繁项集的算法(Frequent Patterns Growth,FP-growth)。采用分治策略，首先，将提供频繁项集的数据库压缩到一棵频繁模式树。然后，将压缩后的数据库划分成一组条件数据库，每个关联一个频繁项或“模式段”，并分别挖掘每个条件数据库。,FP-growth算法-频繁模式增长,(1)它构造了一种新颖的、紧凑的数据结构FP-tree。它是一种扩展的前缀树结构，存储了关于频繁模式数量的重要信息。(2)开发了基于FP-tree的模式片断成长算法，它从长度为1的频繁模式开始，只检查它的条件模式构建它的条件模式树，并且在这个树上递归地进行挖掘。模式的成长通过联合条件模式树新产生的后缀模式实现。(3)挖掘过程中采用的搜索技术是基于分区的，通过分割再解决的方法，而不是Apriori类算法的自下向上产生频繁模式的集合。,2023/1/8,45,示例FP Growth算法找频繁项集,事务数据库如下，最小支持度阈值为2,第1步：构造FP-tree扫描事务数据库得到频繁1-项目集F定义min_sup=2，即最小支持度为2重新排列F,2023/1/8,46,重新调整事务数据库,2023/1/8,47,创建根结点和频繁项目表,Null,2023/1/8,48,加入第一个事务(I2,I1,I5),Null,I2:1,I1:1,I5:1,2023/1/8,49,加入第二个事务(I2,I4),Null,I2:2,I1:1,I5:1,I4:1,2023/1/8,50,加入第三个事务(I2,I3),Null,I2:3,I1:1,I5:1,I4:1,I3:1,2023/1/8,51,加入第四个事务(I2,I1,I4),Null,I2:4,I1:2,I5:1,I4:1,I3:1,I4:1,2023/1/8,52,加入第五个事务(I1,I3),Null,I2:4,I1:2,I5:1,I4:1,I3:1,I4:1,I1:1,I3:1,2023/1/8,53,加入第六个事务(I2,I3),Null,I2:5,I1:2,I5:1,I4:1,I3:2,I4:1,I1:1,I3:1,2023/1/8,54,加入第七个事务(I1,I3),Null,I2:5,I1:2,I5:1,I4:1,I3:2,I4:1,I1:2,I3:2,2023/1/8,55,加入第八个事务(I2,I1,I3,I5),Null,I2:6,I1:3,I5:1,I4:1,I3:2,I4:1,I1:2,I3:2,I5:1,I3:1,2023/1/8,56,加入第九个事务(I2,I1,I3),Null,I2:7,I1:4,I5:1,I4:1,I3:2,I4:1,I1:2,I3:2,I5:1,I3:2,2023/1/8,57,第二步、FP-growth,首先考虑I5，得到条件模式基：、构造条件FP-tree得到I5频繁项集：I2,I5:2,I1,I5:2,I2,I1,I5:2,Null,I2:2,I1:2,I3:1,2023/1/8,58,第二步、FP-growth,接着考虑I4，得到条件模式基：、构造条件FP-tree得到I4频繁项集：I2,I4:2,Null,I2:2,I1:1,2023/1/8,59,第二步、FP-growth,然后考虑I3，得到条件模式基：、构造条件FP-tree由于此树不是单分支路径，因此需要递归挖掘I3,Null,I2:4,I1:2,I1:2,2023/1/8,60,第二步、FP-growth,递归考虑I3，此时得到I1条件模式基,即I1,I3的条件模式基为构造条件FP-tree得到I3的频繁项目集I2,I3:4,I1,I3:4,I2,I1,I3:2,Null,I2:2,2023/1/8,61,第二步、FP-growth,最后考虑I1，得到条件模式基：构造条件FP-tree得到I1的频繁项目集：I2,I1:4,Null,I2:4,产生的频繁模式,频繁项目集及支持度为:L2=I1 I3:4,I2 I1:4,I1 I5:2,I2 I3:4,I2 I4:2,I2 I5:2L3=I2 I1 I5:2,I2 I1 I3:2与Apriori算法的结果是相同的。,FP-growth算法,FP-growth算法的主要思想 该算法主要是为了克服类Apriori算法的产生候选项集的缺点，通过采用一种新的数据结构FP-tree来达到目的。优点：只扫描数据库二次，并且不用产生候选项集，提高了效率。,FP-growth算法,（1）数据库的第1次扫描与Apriori相同，导出频繁项（1项集）的集合和支持度计数。频繁项集L按支持度计数的递减排序。（2）构造FP树。首先创建树根，用NULL标记。第二次扫描数据库D。每个事务中的项按照L中的次序处理。并对每个事务创建一个分枝。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数加1.（3）创建一个项头表，使每项通过一个节点链指向它在树中的位置。,FP树的挖掘过程,由每个长度为1的频繁模式（初试后缀模式）开始，构造它的条件模式基（由FP树中与后缀模式一起出现的前缀路径集组成），然后，构造它的（条件）FP树，并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。,FP-增长算法伪代码,算法：FP-增长。使用FP-树，通过模式段增长，挖掘频繁模式。输入：事务数据库D；最小支持度阈值min_sup。输出：频繁模式的完全集。1 按以下步骤构造FP-树：(a)扫描事务数据库D 一次。收集频繁项的集合F 和它们的支持度。对F 按支持度降序排序，结果为频繁项表L。(b)创建FP树的根结点，以“null”标记它。对于D中每个事务Trans，执行：选择 Trans 中的频繁项，并按L中的次序排序。设排序后的频繁项表为p|P，其中，p 是第一个元素，而P 是剩余元素的表。调用insert_tree(p|P,T)。该过程执行情况如下:如果T有子女N 使得N.item-name=p.item-name，则N 的计数增加1；否则创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同item-name 的结点。如果P 非空，递归地调用insert_tree(P,N)。,2 FP-树的挖掘通过调用FP_growth(FP_tree,null)实现。该过程实现如下：procedure FP_growth(Tree,)(1)if Tree 含单个路径P then(2)for each 路径 P 中结点的每个组合（记作）(3)产生模式，其支持度support 等于中结点的最小支持度；(4)else for Tree 的头表中的每个ai(5)产生一个模式=ai，其支持度support=ai.support；(6)构造的条件模式基，然后构造的条件FP树Tree；(7)if Tree then(8)调用 FP_growth(Tree,)；,练习：构建FP树,其中，最小支持度阈值为3,FP-growth 算法实现,null,3.f,b,4.c,b,p,1.f,c,a,m,p,2.f,c,a,b,m,5.f,c,a,m,p,FP-growth算法树的构造,FP-growth 算法实例,生成的FP树,节点链性质对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。,3.3 关联规则挖掘的其他算法,典型算法 Apriori算法（及变种AprioriTid和AprioriHybrid)）AIS 算法（R.Agrawal等提出）SETM 算法（M.Houtsma等提出）DHP 算法（J.Park等提出）PARTITION 算法（A.Savasere等提出）Sampling 算法（H.Toivonen提出）FP-growth 算法（Jiawei Han提出）,AIS算法的主要思想,其主要思想是一边扫描数据库，一边产生候选项集并累计支持度。具体地说，在对数据库进行第k次扫描时，候选项集是由第k-1次扫描所产生的边界集(frontier set)通过增加当前事务中的项得到，同时计算候选项集中元素的支持数，直到某次扫描所产生的边界集为空。缺点：生成的候选项集太大。,Apriori算法的主要思想,该算法利用了频繁项集所具有的任意频繁项集的子集都是频繁项集的这一性质对数据库进行多次扫描:第一次扫描得到频繁项集的集合L1，第k趟扫描前先利用上次扫描的结果项目集Lk-1,产生候选k项集的集合Ck，然后再通过扫描数据库确定C中每一候选k项集的支持数，最后在该次扫描结束时求出频繁k项集的集合Lk，算法的终止条件是Ck或Lk为空。优点：所产生的候选项集比AIS算法少得多，效率较高。事实上，它被视为关联规则挖掘最经典的算法，其他很多算法都是其变种或改进。,SETM算法的主要思想,该算法实际也是AIS算法的变形。SETM把候选集的产生和累计分开，在一个线性存储结构里存储了所有候选集和相应的交易的标识符（TID）。每次扫描结束后，不再读取数据库，而是对TID进行排序并累计各个候选集的支持度。其思想是扫描候选集的编码（TID）来代替扫描数据库，实质上是把数据库中与支持有关的信息单独提取出来，构成一个较小但充分的TID库。这种做法大大减少了数据库访问的时间。缺点：候选项集过大。,DHP算法的主要思想,该算法利用散列表(hash table)产生候选集，是对Apriori算法的直接改进。在遍历一次数据库得到候选k-项集的支持度，得到频繁k一项集后，DHP算法将每一个事务的可能的(k+1)-项集通过哈希规则形成散列表。散列表的每一栏包括所有通过散列规则映射到该栏中的项集的数目。根据结果的散列表，可以生成一个位向量，当散列表中对应的该栏中的数值大于或者等于最小支持时，对应的位置为1,否则为0。用该向量可以过滤掉下一次生成候选时所不必要的项集:如某候选项在向量中对应位的值为0，则舍弃。这对候选2-项集的产生尤为有效，可以在第二次就大大减小候选集的规模。,DHP算法,优点 在某些场合，DHP算法的效率比Apriori算法明显提高。,PARTITION算法的主要思想,该算法主要针对大型数据库，包括两部分：(1)将目标数据库分为n个互不相交的子数据库D1，Dn，每个Di(i=1,2,n)的大小都要能容纳在内存中。然后把每个Di，读入内存并按一般算法发现频繁项集Li。再把所有的Li合并为数据库D的潜在频繁项集PL=Ui Li;(2)计算潜在频繁项集PL在D中的支持度，得出频繁项集L。,Sampling算法的主要思想,对数据库D进行随机抽样得到抽样事务数据库D，先以小于指定的支持度（minsup）挖掘D中的频繁项集L，再在剩余的数据集D-D中继续计算L中各元素的支持数，最后再以minsup求出L。这在大多数情况下就可以求得所有的频繁项集，但是有时会漏掉一些。这时可以对D进行二次扫描以发现漏掉的频繁项集。优点：多数情况下只需对数据库扫描一次，最坏情况下也只需扫描两次。,本章小结,作业,3.5 数据挖掘的可视化,以可视化的方式展示数据挖掘获取的相关知识。例如：散点图和盒图(obtained from descriptive data mining)决策树关联规则聚类异常点规则,SAS Enterprise Miner 的散点图,关联规则的可视化（MineSet 3.0）,决策树的可视化（MineSet 3.0）,聚类的可视化（Intelligent Miner）,3.6 数据挖掘的实施,一般而言，一个企业实施数据挖掘项目有三种方式可供选择：购买成熟的模型 购买一般性数据挖掘系统软件 构建数据挖掘系统,3.6 数据挖掘的实施,第一种方式实现简单，可以直接应用，但是要求模型所模拟的环境必须和企业的产品、客户以及市场条件相类似。当模型所涉及的环境条件改变的时候，这种模型不能根据环境的变化作出修改和调整。,3.6 数据挖掘的实施,第二种方式可以利用数据挖掘系统根据企业自己的数据生成模型。但是，一个通用的数据挖掘系统在对特定行业商业问题的理解上可能需要做很多工作；同时，如何与与企业原有系统自动化集成也是一个需要着重考虑的问题。第三种方式可以较好地解决与原有系统集成的问题，并可以直接面向特定的商业问题的解决。但是这种方式实现较复杂，项目实施周期长，成本较高。,3.6 数据挖掘的实施,当然企业也可以把上述方式结合起来。例如：购买包含模型的数据挖掘软件或购买通用数据挖掘软件系统，然后进行针对本企业特点的二次开发等。,数据挖掘系统的典型结构,