智能推荐2---关联分析概要

主讲张荣梅2014.10数据挖掘导论关联规则数据挖掘算法所处位置数据挖掘算法功能根据所挖掘知识的类型不同：为了反映事物之间依赖或关联的为了反映同类事物共同性质的为了反映事物各方面特征的为了反映不同事物之间属性差别的根据历史的和当前的数据推测未来数据揭示事物偏离常规的异常现象数据挖掘技术关联（Association）分类（Classification）预测（Prediction）聚类（Clustering）Web挖掘技术3挖掘频繁模式和关联规则3.1基本概念3.2Apriori算法3.3其他算法概述3.1关联的基本概念若两个或多个变量的取值之间存在某种规律性，就称为关联。关联规则是寻找同一事件中出现的不同项的相关性，比如在一次购买活动中所购买不同商品的相关性。关联分析即利用关联规则进行数据挖掘。购物篮模型典型案例---啤酒与尿布啤酒与尿布在商业应用中常用关联分析最典型的例子就是一家连锁店(沃尔玛)通过数据挖掘发现了小孩尿布与啤酒之间有着内在的联系，即“啤酒与尿布”的故事。在美国，一些年轻(25—35岁）的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30—40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布与啤酒放在一起，明显增加了销售额。CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer“啤酒与尿布”的关联规则更多举例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中事务包含XUY的百分比，即概率P(XUY):support(X=Y)=support(XUY)=P(XUY)规则的可信度c定义为D中包含X的事务同时也包含Y的百分比，即条件概率P(Y|X)。confidence(X=Y)=support(XUY)/support(X)=P(Y|X)关联规则的形式R:X=Y其中，X及Y是两个不相交的集合，即X,YI且XY=关联规则可以理解为一个命题，即如果一个交易支持项集X，则它也以一定的可能性支持项集Y，这一可能性称之为规则的可信度，记为conf(R)或C(R)规则形式举例Bodyead[support,confidence]buys(x,“diapers”)buys(x,“beers”)[2%,60%]major(x,“CS”)^takes(x,“DB”)grade(x,“A”)[5%,75%]关联规则挖掘应用实例通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？这种信息可以引导销售，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。关联规则挖掘实例购物篮分析哪些商品频繁地被顾客同时购买？3.2Apriori关联规则挖掘算法关联规则挖掘是从事务数据库、关系数据库和其它信息存储中的大量数据项集之间发现有趣的、频繁出现的模式、关联和相关性。关联规则挖掘步骤一般分为2个步骤：依据支持度找出所有的频繁项集。（频度）依据置信度产生关联规则。（强度）可以根据兴趣度，找出有兴趣的关联规则。先验算法基本概念项项集频繁项集事务关联规则置信度支持度由此我们引出之后需要的几个概念：兴趣度购物篮模型中的有关概念项—商品事务---交易，购物篮项集---每个购物篮由多个项组成的集合。包含k个项的项集称为k项集。{milk，bread}是一个2项集。支持度----项集的频率，是指包含项集的事务数。如果A是一个项集，A的支持度是指包含A的购物篮的数目。频繁项集----一个在多个购物篮中出现的项集。假定最小支持度阈值为s。如果A的支持度不小于s，则称A是频繁项集。置信度---可信度。规则A→B的可信度等于集合A∪B的支持度与A的支持度的比值兴趣度---关联规则A→B的兴趣度定义为其可信度与包含B的购物篮的比率之差。如果为负值或接近于0，则表示关联规则不十分有趣。关联挖掘实例--最简单的关联规则挖掘TransactionIDItemsBought2000A,B,C1000A,C4000A,D5000B,E,FFrequentItemsetSupport{A}75%{B}50%{C}50%{A,C}50%单维、单层、布尔关联规则挖掘Minsupport=50%Minconfidence=50%ForruleACsupport=support({AC})=50%confidence=support({AC})/support({A})=66.7%ForCA(50%,100%)这就是Apriori算法Apriori性质：Anysubsetofafrequentitemsetmustbefrequent（1）找出频繁项集（2）在频繁项集中找出满足置信度的项集Apriori算法Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。按照所处理的值类型不同进行关联规则分类：布尔关联规则，如事务向量（001101100）对每种商品可以用一个布尔量来表示该种商品是否被购买，则每个购物篮可以用一个布尔向量来表示量化关联规则，如Age{X,”30--39”}∩income{X,”40k—48k”}=〉buys{X,”computer”}Apriori算法的步骤-----使用候选产生发现频繁项集。（1）由候选项集(candidateitemset)产生频繁项集(frequentitemset)；（2）由频繁项集(frequentitemset)产生强关联规则(strongassociationrule)。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-1∞Lk-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→L－S”。注：L－S表示在项集L中除去S子集的项集。举例由频繁项集产生关联规则频繁项集l={B,C,E}L的非空子集有：{B,C}{B,E}{C.E}{B}{C}{E},得出关联规则如下：B∧C=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）L1=find_frequent_1_itemsets(D);（2）for(k=2;Lk-1≠Φ;k++){（3）Ck=apriori_gen(Lk-1);（4）foreachtransactiont∈D{//scanDforcounts（5）Ct=subset(Ck,t);//getthesubsetsoftthatarecandidates（6）foreachcandidatec∈Ct（7）c.count++;（8）}（9）Lk={c∈Ck|c.count≥min_sup}（10）}（11）returnL=∪kLk;连接步和剪枝步•第1步：连接(join)•Procedureapriori_gen(Lk-1:frequent(k-1)itemset)•1)foreachitemsetl1∈Lk-1•2)foreachitemsetl2∈Lk-1•3)if((l1[1]=l2[1])∧…∧(l1[k-2]=l2[k-2])∧•(l1[k-1]＜l2[k-1])then{•4)c=l1⋈l2；//连接，产生候选集•5)ifhas_infrequent_subset(c，Lk-1)then•6)deletec;//修剪，去掉无用的候选项•7)elseaddctoCk;•8)}•9)returnCk;连接步和剪枝步•第2步:剪枝(prune)•procedurehas_infrequent_subset(c:candidatekitemset;Lk-1:frequent(k-1)itemset);•//使用先验知识1)foreach(k-1)subsetsofc•2)ifs∉Lk-1then•3)returntrue;•4)returnfalse;Apriori算法的基本流程使用逐层搜索的迭代方法，通过对数据库的多次扫描发现所有的频繁项集。在每一趟扫描中只考虑具有同一长度k(即为项集中所含项目的个数)的所有项集。算法的第一次扫描仅仅计算每个项目的具体支持度，以确定长度为1的频繁项集。在后继的每一次扫描中，首先使用在前一次获得的频繁项集Lk-1和Apriori-gen函数产生的候选项集q，接着扫描数据库，计算Ck中候选项的支持度，最后确定候选项集中哪些真正成为频繁项集。重复上述过程直到再也发现不了新的频繁项集为止。TIDItems100134200235300123540025DatabaseDitemsetsup.{1}2{2}3{3}3{4