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

主讲张荣梅2014.10数据挖掘导论

关联规则主讲张荣梅数据挖掘导论

关联规则数据挖掘算法所处位置数据挖掘算法所处位置数据挖掘算法功能根据所挖掘知识的类型不同：为了反映事物之间依赖或关联的为了反映同类事物共同性质的为了反映事物各方面特征的为了反映不同事物之间属性差别的根据历史的和当前的数据推测未来数据揭示事物偏离常规的异常现象数据挖掘算法功能根据所挖掘知识的类型不同：数据挖掘技术关联（Association）分类（Classification）预测（Prediction）聚类（Clustering）Web挖掘技术

数据挖掘技术关联（Association）3挖掘频繁模式和关联规则3.1基本概念3.2Apriori算法3.3其他算法概述

3挖掘频繁模式和关联规则3.1关联的基本概念若两个或多个变量的取值之间存在某种规律性，就称为关联。关联规则是寻找同一事件中出现的不同项的相关性，比如在一次购买活动中所购买不同商品的相关性。关联分析即利用关联规则进行数据挖掘。购物篮模型典型案例---啤酒与尿布3.1关联的基本概念若两个或多个变量的取值之间存在某种规啤酒与尿布在商业应用中常用关联分析最典型的例子就是一家连锁店(沃尔玛)通过数据挖掘发现了小孩尿布与啤酒之间有着内在的联系，即“啤酒与尿布”的故事。在美国，一些年轻(25—35岁）的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30—40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布与啤酒放在一起，明显增加了销售额。啤酒与尿布在商业应用中常用关联分析最典型的例子就是一家连锁店CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer“啤酒与尿布”的关联规则CustomerCustomerCustomer“啤酒与尿布更多举例e.g：

在购买铁锤的顾客当中，有70％的人同时购买了铁钉。更多举例e.g：关联的基本概念关联自然界中某种事物发生时其他事物也会发生，则这种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）。关联的类型分为简单关联、时序关联、因果关联。关联规则关联是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性。关联的基本概念关联关联的基本概念关联规则的数学定义设I={i1,i2,...,im}是一个以m个不同项的集合，任务相关的数据D是数据库事务（交易）的集合，其中每个事务T是针对I的项的集合，即每一笔交易包含若干个属于I的项。关联规则可表示为：X=>Y，其中X,YI且XY=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,YI且XY=

关联规则可以理解为一个命题，即如果一个交易支持项集X，则它也以一定的可能性支持项集Y，这一可能性称之为规则的可信度，记为conf(R)或C(R)关联规则的形式规则形式举例Body®Head[support,confidence]buys(x,“diapers”)®buys(x,“beers”)[2%,60%]major(x,“CS”)^takes(x,“DB”)®grade(x,“A”)[5%,75%]规则形式举例关联规则挖掘应用实例

通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。

通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。

例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？这种信息可以引导销售，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。关联规则挖掘应用实例通过发现顾客放入其购物篮中不关联规则挖掘实例购物篮分析哪些商品频繁地被顾客同时购买？关联规则挖掘实例购物篮分析哪些商品频繁地被顾客同时购买？3.2Apriori关联规则挖掘算法关联规则挖掘是从事务数据库、关系数据库和其它信息存储中的大量数据项集之间发现有趣的、频繁出现的模式、关联和相关性。3.2Apriori关联规则挖掘算法关联规则挖掘是从事务关联规则挖掘步骤一般分为2个步骤：依据支持度找出所有的频繁项集。

（频度）依据置信度产生关联规则。（强度）可以根据兴趣度，找出有兴趣的关联规则。先验算法关联规则挖掘步骤一般分为2个步骤：先验算法基本概念项项集频繁项集事务关联规则置信度支持度由此我们引出之后需要的几个概念：兴趣度基本概念项项集频繁项集事务关联规则置信度支持度由此我们引出之购物篮模型中的有关概念项—商品事务---交易，购物篮项集---每个购物篮由多个项组成的集合。包含k个项的项集称为k项集。{milk，bread}是一个2项集。支持度----项集的频率，是指包含项集的事务数。如果A是一个项集，A的支持度是指包含A的购物篮的数目。频繁项集----一个在多个购物篮中出现的项集。假定最小支持度阈值为s。如果A的支持度不小于s，则称A是频繁项集。置信度---可信度。规则A→B的可信度等于集合A∪B的支持度与A的支持度的比值兴趣度---关联规则A→B的兴趣度定义为其可信度与包含B的购物篮的比率之差。如果为负值或接近于0，则表示关联规则不十分有趣。购物篮模型中的有关概念项—商品关联挖掘实例--最简单的关联规则挖掘单维、单层、布尔关联规则挖掘Minsupport=50%Minconfidence=50%ForruleA

Csupport=support({A

C})=50%confidence=support({A

C})/support({A})=66.7%ForCA(50%,100%)这就是

Apriori算法Apriori性质：Anysubsetofafrequentitemsetmustbefrequent（1）找出频繁项集（2）在频繁项集中找出满足置信度的项集关联挖掘实例--最简单的关联规则挖掘单维、单层、布尔关联规则

Apriori算法

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。按照所处理的值类型不同进行关联规则分类：布尔关联规则，如事务向量（001101100）对每种商品可以用一个布尔量来表示该种商品是否被购买，则每个购物篮可以用一个布尔向量来表示量化关联规则，如Age{X,”30--39”}

∩income{X,”40k—48k”}=〉buys{X,”computer”}Apriori算法Apriori算法是一种最有Apriori算法的步骤-----使用候选产生发现频繁项集。（1）由候选项集(candidateitemset)产生频繁项集(frequentitemset)；（2）由频繁项集(frequentitemset)产生强关联规则(strongassociationrule)。Apriori算法的步骤-----使用候选产生发现频繁项集Apriori使用一种称作逐层搜索的迭代方法，“K项集”用于探索“K+1项集”。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁“1项集”的集合。该集合记作L1。然后，L1用于找频繁“2项集”的集合L2，而L2用于找L3，如此下去，直到不能再找到频繁“K项集”。找每个LK需要一次数据库全扫描。为了提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。Apriori算法Apriori使用一种称作逐层搜索的迭代方法，“K项集”用核心：连接步和剪枝步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算法主要为了提高数据访问效率，提升发现频繁项集的速度使用候选产生发现频繁项集Apriori性质：频繁项集的所有非空子集也必须是频繁的。Apriori算法目的意义Apriori算法主要为了提高数步骤1：发现频繁项集频繁项集发现过程：（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）~（5）直到不能发现更大频集

步骤1：发现频繁项集频繁项集发现过程：步骤2：产生关联规则根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果则输出规则“S→L－S”。注：L－S表示在项集L中除去S子集的项集。步骤2：产生关联规则根据前面提到的置信度的定义，关联规则的产举例举例由频繁项集产生关联规则频繁项集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规则可以输出。由频繁项集产生关联规则频繁项集l={B,C,E}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(L

k-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;

Apriori算法伪代码算法：Apriori，使用逐层迭代连接步和剪枝步第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)then6)deletec;//修剪，去掉无用的候选项7)elseaddctoCk;8)}9)returnCk;连接步和剪枝步第1步：连接(join)连接步和剪枝步第2步:剪枝(prune)procedurehas_infrequent_subset(c:candidatekitemset;Lk-1:frequent(k-1)itemset);//使用先验知识1)foreach(k-1)subsetsofc2)ifs∉Lk-1

then3)returntrue;4)returnfalse;连接步和剪枝步第2步:剪枝(prune)Apriori算法的基本流程使用逐层搜索的迭代方法，通过对数据库的多次扫描发现所有的频繁项集。在每一趟扫描中只考虑具有同一长度k(即为项集中所含项目的个数)的所有项集。算法的第一次扫描仅仅计算每个项目的具体支持度，以确定长度为1的频繁项集。在后继的每一次扫描中，首先使用在前一次获得的频繁项集Lk-1和Apriori-gen函数产生的候选项集q，接着扫描数据库，计算Ck中候选项的支持度，最后确定候选项集中哪些真正成为频繁项集。重复上述过程直到再也发现不了新的频繁项集为止。Apriori算法的基本流程使用逐层搜索的迭代方法，通过对数DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanDApriori算法实例设定最小支持度阈值为2

DatabaseDScanDC1L1L2C2C2Scan练习题下表是某商店的事务数据库D，数据库中有9个事务。试用Apriori算法找出其关联规则。TID商品ID列表T100I1，I2，I5T200I2.I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3设定最小支持度阈值为2

练习题TID商品ID列表T100I1，I2，I5T200I2扫描D，对每个候选项计数，生成C1：项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2扫描D，对每个候选项计数，生成C1：项集支持度计数｛I1｝6比较候选项支持度计数与最小支持度计数，生成L1：

项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2比较候选项支持度计数与最小支持度计数，生成L1：项集支持度由L1产生候选集C2：

项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝由L1产生候选集C2：项集｛I1，I2｝｛I1，I3｝｛I再次扫描D，对每个候选项计数，产生L2：

项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2再次扫描D，对每个候选项计数，产生L2：项集支持度计数｛I对L2进行连接&剪枝，产生C3，即最终结果。

由频繁项集产生关联规则:L1={I1,I2,I5}的非空子集有：{I1,I2}{I1,I5}{I2,I5}{I1}{I2}{I5},结果关联规则如下：I1∧I2==>I5confidence=2/4=50%如果最小置信度阈值为70%，则2I1∧I5==>I2confidence=2/2=100%3,6条规则可以输出。I2∧I5==>I1confidence=2/2=100%请写出第2个频繁项集的关联规则I1=>I2∧I5confidence=2/6=33%I2==>I1∧I5confidence=2/7=29%I5==>I1∧I2confidence=2/2=100%项集｛I1，I2，I3｝｛I1，I2，I5｝支持度计数22对L2进行连接&剪枝，产生C3，即最终结果。由频繁项集产生可能产生大量的候选集可能需要重复扫描数据库Apriori算法局限性可能产生大量的候选集Apriori算法局限性Apriori算法的局限性可能需要产生大量候选项集。例如，如果有104个频繁1项集，可能产生107个候选2项集。可能需要重复扫描数据库，通过模式匹配检查一个很大的候选集合。由于依赖于候选项集产生频繁项集的理论（Apriori类算法）所开发的算法具有先天的弱点，使得在基于Apriori算法开发的应用没有实质性突破。

Apriori算法的局限性可能需要产生大量候选项集。例如，FP-growth算法-频繁模式增长Han等提出的一种新的算法理论，用一种压缩的数据结构(FP-tree)存储关联规则挖掘所需的全部数据信息，通过对源数据的两次扫描，将数据信息存到这种结构里，避开了产生候选项集的步骤，极大地减少了数据交换和频繁匹配的开销。这就是所谓不候选产生挖掘频繁项集的算法(FrequentPatternsGrowth,FP-growth)。采用分治策略，首先，将提供频繁项集的数据库压缩到一棵频繁模式树。然后，将压缩后的数据库划分成一组条件数据库，每个关联一个频繁项或“模式段”，并分别挖掘每个条件数据库。FP-growth算法-频繁模式增长Han等提出的一种新的算FP-growth算法-频繁模式增长(1)它构造了一种新颖的、紧凑的数据结构FP-tree。它是一种扩展的前缀树结构，存储了关于频繁模式数量的重要信息。(2)开发了基于FP-tree的模式片断成长算法，它从长度为1的频繁模式开始，只检查它的条件模式构建它的条件模式树，并且在这个树上递归地进行挖掘。模式的成长通过联合条件模式树新产生的后缀模式实现。(3)挖掘过程中采用的搜索技术是基于分区的，通过分割再解决的方法，而不是Apriori类算法的自下向上产生频繁模式的集合。FP-growth算法-频繁模式增长(1)它构造了一种新颖的2022/12/2245示例—FPGrowth算法找频繁项集TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事务数据库如下，最小支持度阈值为2第1步：构造FP-tree扫描事务数据库得到频繁1-项目集F定义min_sup=2，即最小支持度为2重新排列FI1I2I3I4I567622I2I1I3I4I5766222022/12/1745示例—FPGrowth算法找频繁项2022/12/2246重新调整事务数据库TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3I27I16I36I42I522022/12/1746重新调整事务数据库TidItems12022/12/2247创建根结点和频繁项目表Item-nameSupportCountNode-headI27NullI16NullI36NullI42NullI52NullNull2022/12/1747创建根结点和频繁项目表Item-na2022/12/2248加入第一个事务(I2,I1,I5)Item-nameSupportCountNode-headI27I16I36NullI42NullI52NullI2:1I1:1I5:12022/12/1748加入第一个事务(I2,I1,I5)I2022/12/2249加入第二个事务(I2,I4)Item-nameSupportCountNode-headI27I16I36NullI42I52NullI2:2I1:1I5:1I4:12022/12/1749加入第二个事务(I2,I4)Item2022/12/2250加入第三个事务(I2,I3)Item-nameSupportCountNode-headI27I16I36I42I52NullI2:3I1:1I5:1I4:1I3:12022/12/1750加入第三个事务(I2,I3)Item2022/12/2251加入第四个事务(I2,I1,I4)Item-nameSupportCountNode-headI27I16I36I42I52NullI2:4I1:2I5:1I4:1I3:1I4:12022/12/1751加入第四个事务(I2,I1,I4)I2022/12/2252加入第五个事务(I1,I3)Item-nameSupportCountNode-headI27I16I36I42I52NullI2:4I1:2I5:1I4:1I3:1I4:1I1:1I3:12022/12/1752加入第五个事务(I1,I3)Item2022/12/2253加入第六个事务(I2,I3)Item-nameSupportCountNode-headI27I16I36I42I52NullI2:5I1:2I5:1I4:1I3:2I4:1I1:1I3:12022/12/1753加入第六个事务(I2,I3)Item2022/12/2254加入第七个事务(I1,I3)Item-nameSupportCountNode-headI27I16I36I42I52NullI2:5I1:2I5:1I4:1I3:2I4:1I1:2I3:22022/12/1754加入第七个事务(I1,I3)Item2022/12/2255加入第八个事务(I2,I1,I3,I5)Item-nameSupportCountNode-headI27I16I36I42I52NullI2:6I1:3I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:12022/12/1755加入第八个事务(I2,I1,I3,I2022/12/2256加入第九个事务(I2,I1,I3)Item-nameSupportCountNode-headI27I16I36I42I52NullI2:7I1:4I5:1I4:1I3:2I4:1I1:2I3:2I5:1I3:22022/12/1756加入第九个事务(I2,I1,I3)I2022/12/2257第二步、FP-growth首先考虑I5，得到条件模式基：<(I2,I1:1)>、<I2,I1,I3:1>构造条件FP-tree得到I5频繁项集：{{I2,I5:2},{I1,I5:2},{I2,I1,I5:2}}Item-nameNode-headI2I1NullI2:2I1:2I3:12022/12/1757第二步、FP-growth首先考虑I2022/12/2258第二步、FP-growth接着考虑I4，得到条件模式基：<(I2,I1:1)>、<I2:1>构造条件FP-tree得到I4频繁项集：{{I2,I4:2}}Item-nameNode-headI2NullI2:2I1:12022/12/1758第二步、FP-growth接着考虑I2022/12/2259第二步、FP-growth然后考虑I3，得到条件模式基：

<(I2,I1:2)>、<I2:2>、<I1:2>构造条件FP-tree由于此树不是单分支路径，因此需要递归挖掘I3Item-nameNode-headI2I1NullI2:4I1:2I1:22022/12/1759第二步、FP-growth然后考虑I2022/12/2260第二步、FP-growth递归考虑I3，此时得到I1条件模式基<(I2:2)>,即I1,I3的条件模式基为<(I2:2)>构造条件FP-tree得到I3的频繁项目集{{I2,I3:4},{I1,I3:4},{I2,I1,I3:2}}Item-nameNode-headI2NullI2:22022/12/1760第二步、FP-growth递归考虑I2022/12/2261第二步、FP-growth最后考虑I1，得到条件模式基：<(I2:4)>构造条件FP-tree得到I1的频繁项目集：{{I2,I1:4}Item-nameNode-headI2NullI2:42022/12/1761第二步、FP-growth最后考虑I产生的频繁模式项条件模式基条件FP树产生的频繁模式I5{I2I1:1},{I2I1I3:1}<I2:2，I1:2>{I2I5:2},{I1I5:2}{I2

I1I5:2}I4{I2I1:1},{I2:1}<I2:2>{I2I4:2}I3{I2I1:2},{I2:2},{I1:2}<I2:4,I1:2><I1:2>{I2I3:4},{I1I3:4}{I2I1I3:2}I1{I2:4}<I2:4>{I2I1:4}频繁项目集及支持度为:L2={{I1I3:4},{I2I1:4},{I1I5:2},{I2I3:4},{I2I4:2},{I2I5:2}}L3={{I2

I1I5:2},{I2I1I3:2}}与Apriori算法的结果是相同的。

产生的频繁模式项条件模式基条件FP树产生的频繁模式I5{I2FP-growth算法FP-growth算法的主要思想该算法主要是为了克服类Apriori算法的产生候选项集的缺点，通过采用一种新的数据结构FP-tree来达到目的。优点：只扫描数据库二次，并且不用产生候选项集，提高了效率。

FP-growth算法FP-growth算法的主要思想FP-growth算法（1）数据库的第1次扫描与Apriori相同，导出频繁项（1项集）的集合和支持度计数。频繁项集L按支持度计数的递减排序。（2）构造FP树。首先创建树根，用NULL标记。第二次扫描数据库D。每个事务中的项按照L中的次序处理。并对每个事务创建一个分枝。一般地，当为一个事务考虑增加分枝时，沿共同前缀上的每个节点的计数加1.（3）创建一个项头表，使每项通过一个节点链指向它在树中的位置。FP-growth算法（1）数据库的第1次扫描与ApriorFP树的挖掘过程由每个长度为1的频繁模式（初试后缀模式）开始，构造它的条件模式基（由FP树中与后缀模式一起出现的前缀路径集组成），然后，构造它的（条件）FP树，并递归地对该树进行挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。FP树的挖掘过程由每个长度为1的频繁模式（初试后缀模式）开始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)。FP-增长算法伪代码算法：FP-增长。使用FP-树，通过模式2．FP-树的挖掘通过调用FP_growth(FP_tree,null)实现。该过程实现如下：procedureFP_growth(Tree,α)

(1)ifTree含单个路径Pthen

(2)foreach路径P中结点的每个组合（记作β）(3)

产生模式β∪α，其支持度support等于β中结点的最小支持度；(4)elsefor

Tree的头表中的每个ai

{(5)产生一个模式β=ai∪α，其支持度support=ai.support；(6)构造β的条件模式基，然后构造β的条件FP树Treeβ；(7)ifTreeβ≠∅then(8)调用FP_growth(Treeβ,β)；}2．FP-树的挖掘通过调用FP_growth(FP_tre练习：构建FP树交易编号所有购物项（排序后的）频繁项100f,a,c,d,g,i,m,pF：4,c:4,a:3,m:3,p:3200a,b,c,f,l,m,oF:4,c:4,a:3,b:3,m:3300b,f,h,j,oF:4,b:3400b,c,k,s,pC:4,b:3,p:3500a,f,c,e,l,p,m,nF:4,c:4,a:3,m:3,p:3其中，最小支持度阈值为3练习：构建FP树交易编号所有购物项（排序后的）频繁项100fFP-growth算法实现null{}b:1f:3c:1b:1p:1a:2b:1m:1f:2c:2a:3f:4c:3m:2p:23.f,b4.c,b,pf:1c:1m:1p:1a:11.f,c,a,m,p2.f,c,a,b,m5.f,c,a,m,pFP-growth算法树的构造

FP-growth算法实现null{}b:1f:3c:1bFP-growth算法实例生成的FP树

节点链性质对任意频繁项ai，顺着ai的节点链，从ai的头开始，可以找到包含ai的所有频繁模式。FP-growth算法实例生成的FP树节点链性质对任意频3.3关联规则挖掘的其他算法典型算法

Apriori算法（及变种AprioriTid和AprioriHybrid)）

AIS算法（R.Agrawal等提出）

SETM算法（M.Houtsma等提出）

DHP算法（J.Park等提出）

PARTITION算法（A.Savasere等提出）

Sampling算法（H.Toivonen提出）

FP-growth算法（JiaweiHan提出）3.3关联规则挖掘的其他算法典型算法AIS算法的主要思想其主要思想是一边扫描数据库，一边产生候选项集并累计支持度。具体地说，在对数据库进行第k次扫描时，候选项集是由第k-1次扫描所产生的边界集(frontierset)通过增加当前事务中的项得到，同时计算候选项集中元素的支持数，直到某次扫描所产生的边界集为空。缺点：生成的候选项集太大。AIS算法的主要思想其主要思想是一边扫描数据库，一边产生候选Apriori算法的主要思想该算法利用了频繁项集所具有的任意频繁项集的子集都是频繁项集的这一性质对数据库进行多次扫描:第一次扫描得到频繁项集的集合L1，第k趟扫描前先利用上次扫描的结果项目集Lk-1,产生候选k项集的集合Ck

，然后再通过扫描数据库确定C中每一候选k项集的支持数，最后在该次扫描结束时求出频繁k项集的集合Lk

，算法的终止条件是Ck或Lk为空。优点：所产生的候选项集比AIS算法少得多，效率较高。事实上，它被视为关联规则挖掘最经典的算法，其他很多算法都是其变种或改进。

Apriori算法的主要思想该算法利用了频繁项集所具有的任意SETM算法的主要思想该算法实际也是AIS算法的变形。SETM把候选集的产生和累计分开，在一个线性存储结构里存储了所有候选集和相应的交易的标识符（TID）。每次扫描结束后，不再读取数据库，而是对TID进行排序并累计各个候选集的支持度。其思想是扫描候选集的编码（TID）来代替扫描数据库，实质上是把数据库中与支持有关的信息单独提取出来，构成一个较小但充分的TID库。这种做法大大减少了数据库访问的时间。缺点：候选项集过大。

SETM算法的主要思想该算法实际也是AIS算法的变形。SETDHP算法的主要思想该算法利用散列表(hashtable)产生候选集，是对Apriori算法的直接改进。在遍历一次数据库得到候选k--项集的支持度，得到频繁k一项集后，DHP算法将每一个事务的可能的(k+1)--项集通过哈希规则形成散列表。散列表的每一栏包括所有通过散列规则映射到该栏中的项集的数目。根据结果的散列表，可以生成一个位向量，当散列表中对应的该栏中的数值大于或者等于最小支持时，对应的位置为1,否则为0。用该向量可以过滤掉下一次生成候选时所不必要的项集:如某候选项在向量中对应位的值为0，则舍弃。这对候选2--项集的产生尤为有效，可以在第二次就大大减小候选集的规模。DHP算法的主要思想该算法利用散列表(hashtable)DHP算法优点在某些场合，DHP算法的效率比Apriori算法明显提高。DHP算法优点PARTITION算法的主要思想该算法主要针对大型数据库，包括两部分：

(1)将目标数据库分为n个互不相交的子数据库D1，…，Dn，每个Di(i=1,2,⋯,n)的大小都要能容纳在内存中。然后把每个Di，读入内存并按一般算法发现频繁项集Li。再把所有的Li合并为数据库D的潜在频繁项集PL=UiLi;(2)计算潜在频繁项集PL在D中的支持度，得出频繁项集L。

PARTITION算法的主要思想该算法主要针对大型数据库，包Sampling算法的主要思想对数据库D进行随机抽样得到抽样事务数据库D’，先以小于指定的支持度（minsup）挖掘D’中的频繁项集L’，再在剩余的数据集D-D’中继续计算L’中各元素的支持数，最后再以minsup求出L。这在大多数情况下就可以求得所有的频繁项集，但是有时会漏掉一些。这时可以对D进行二次扫描以发现漏掉的频繁项集。优点：多数情况下只需对数据库扫描一次，最坏情况下也只需扫描两次。

Sampling算法的主要思想对数据库D进行随机抽样得到抽样本章小结本章小结作业作业3.5数据挖掘的可视化

以可视化的方式展示数据挖掘获取的相关知识。例如：－散点图和盒图(obtainedfromdescriptivedatamining)－决策树－关联规则－聚类－异常点－规则3.5数据挖掘的可视化以可视化的SASEnterpriseMiner的散点图SASEnterpriseMiner的散点图关联规则的可视化（MineSet3.0）关联规则的可视化（MineSet3.0）决策树的可视化（MineSet3.0）决策树的可视化（MineSet3.0）聚类的可视化（IntelligentMiner）聚类的可视化（IntelligentMiner）3.6数据挖掘的实施

一般而言，一个企业实施数据挖掘项目有三种方式可供选择：购买成熟的模型购买一般性数据挖掘系统软件构建数据挖掘系统

3.6数据挖掘的实施一般而言，一3.6数据挖掘的实施第一种方式实现简单，可以直接应用，但是要求模型所模拟的环境必须和企业的产品、客户以及市场条件相类似。当模型所涉及的环境条件改变的时候，这种模型不能根据环境的变化作出修改和调整。3.6数据挖掘的实施第一种方式实现简单，可以直接应用，但3.6数据挖掘的实施第二种方式可以利用数据挖掘系统根据企业自己的数据生成模型。但是，一个通用的数据挖掘系统在对特定行业商业问题的理解上可能需要做很多工作；同时，如何与与企业原有系统自动化集成也是一个需要着重考虑的问题。第三种方式可以较好地解决与原有系统集成的问题，并可以直接面向特定的商业问题的解决。但是这种方式实现较复杂，项目实施周期长，成本较高。3.6数据挖掘的实施第二种方式可以利用数据挖掘系统根据企3.6数据挖掘的实施

当然企业也可以把上述方式结合起来。例如：购买包含模型的数据挖掘软件或购买通用数据挖掘软件系统，然后进行针对本企业特点的二次开发等。3.6数据挖掘的实施当然企业也可以把上述方式数据挖掘系统的典型结构数据挖掘系统的典型结构主讲张荣梅2014.10数据挖掘导论

关联规则主讲张荣梅数据挖掘导论

关联规则数据挖掘算法所处位置数据挖掘算法所处位置数据挖掘算法功能根据所挖掘知识的类型不同：为了反映事物之间依赖或关联的为了反映同类事物共同性质的为了反映事物各方面特征的为了反映不同事物之间属性差别的根据历史的和当前的数据推测未来数据揭示事物偏离常规的异常现象数据挖掘算法功能根据所挖掘知识的类型不同：数据挖掘技术关联（Association）分类（Classification）预测（Prediction）聚类（Clustering）Web挖掘技术

数据挖掘技术关联（Association）3挖掘频繁模式和关联规则3.1基本概念3.2Apriori算法3.3其他算法概述

3挖掘频繁模式和关联规则3.1关联的基本概念若两个或多个变量的取值之间存在某种规律性，就称为关联。关联规则是寻找同一事件中出现的不同项的相关性，比如在一次购买活动中所购买不同商品的相关性。关联分析即利用关联规则进行数据挖掘。购物篮模型典型案例---啤酒与尿布3.1关联的基本概念若两个或多个变量的取值之间存在某种规啤酒与尿布在商业应用中常用关联分析最典型的例子就是一家连锁店(沃尔玛)通过数据挖掘发现了小孩尿布与啤酒之间有着内在的联系，即“啤酒与尿布”的故事。在美国，一些年轻(25—35岁）的父亲下班后经常要到超市去买婴儿尿布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有30—40%的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布与啤酒放在一起，明显增加了销售额。啤酒与尿布在商业应用中常用关联分析最典型的例子就是一家连锁店CustomerbuysdiaperCustomerbuysbothCustomerbuysbeer“啤酒与尿布”的关联规则CustomerCustomerCustomer“啤酒与尿布更多举例e.g：

在购买铁锤的顾客当中，有70％的人同时购买了铁钉。更多举例e.g：关联的基本概念关联自然界中某种事物发生时其他事物也会发生，则这种联系称之为关联。反映事件之间依赖或关联的知识称为关联型知识（又称依赖关系）。关联的类型分为简单关联、时序关联、因果关联。关联规则关联是两个或多个变量取值之间存在的一类重要的可被发现的某种规律性。关联的基本概念关联关联的基本概念关联规则的数学定义设I={i1,i2,...,im}是一个以m个不同项的集合，任务相关的数据D是数据库事务（交易）的集合，其中每个事务T是针对I的项的集合，即每一笔交易包含若干个属于I的项。关联规则可表示为：X=>Y，其中X,YI且XY=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,YI且XY=

关联规则可以理解为一个命题，即如果一个交易支持项集X，则它也以一定的可能性支持项集Y，这一可能性称之为规则的可信度，记为conf(R)或C(R)关联规则的形式规则形式举例Body®Head[support,confidence]buys(x,“diapers”)®buys(x,“beers”)[2%,60%]major(x,“CS”)^takes(x,“DB”)®grade(x,“A”)[5%,75%]规则形式举例关联规则挖掘应用实例

通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。

通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营销策略。

例如，在同一次购物中，如果顾客购买牛奶的同时，也购买面包（和什么类型的面包）的可能性有多大？这种信息可以引导销售，可以帮助零售商有选择地经销和安排货架。例如，将牛奶和面包尽可能放近一些，可以进一步刺激一次去商店同时购买这些商品。关联规则挖掘应用实例通过发现顾客放入其购物篮中不关联规则挖掘实例购物篮分析哪些商品频繁地被顾客同时购买？关联规则挖掘实例购物篮分析哪些商品频繁地被顾客同时购买？3.2Apriori关联规则挖掘算法关联规则挖掘是从事务数据库、关系数据库和其它信息存储中的大量数据项集之间发现有趣的、频繁出现的模式、关联和相关性。3.2Apriori关联规则挖掘算法关联规则挖掘是从事务关联规则挖掘步骤一般分为2个步骤：依据支持度找出所有的频繁项集。

（频度）依据置信度产生关联规则。（强度）可以根据兴趣度，找出有兴趣的关联规则。先验算法关联规则挖掘步骤一般分为2个步骤：先验算法基本概念项项集频繁项集事务关联规则置信度支持度由此我们引出之后需要的几个概念：兴趣度基本概念项项集频繁项集事务关联规则置信度支持度由此我们引出之购物篮模型中的有关概念项—商品事务---交易，购物篮项集---每个购物篮由多个项组成的集合。包含k个项的项集称为k项集。{milk，bread}是一个2项集。支持度----项集的频率，是指包含项集的事务数。如果A是一个项集，A的支持度是指包含A的购物篮的数目。频繁项集----一个在多个购物篮中出现的项集。假定最小支持度阈值为s。如果A的支持度不小于s，则称A是频繁项集。置信度---可信度。规则A→B的可信度等于集合A∪B的支持度与A的支持度的比值兴趣度---关联规则A→B的兴趣度定义为其可信度与包含B的购物篮的比率之差。如果为负值或接近于0，则表示关联规则不十分有趣。购物篮模型中的有关概念项—商品关联挖掘实例--最简单的关联规则挖掘单维、单层、布尔关联规则挖掘Minsupport=50%Minconfidence=50%ForruleA

Csupport=support({A

C})=50%confidence=support({A

C})/support({A})=66.7%ForCA(50%,100%)这就是

Apriori算法Apriori性质：Anysubsetofafrequentitemsetmustbefrequent（1）找出频繁项集（2）在频繁项集中找出满足置信度的项集关联挖掘实例--最简单的关联规则挖掘单维、单层、布尔关联规则

Apriori算法

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。按照所处理的值类型不同进行关联规则分类：布尔关联规则，如事务向量（001101100）对每种商品可以用一个布尔量来表示该种商品是否被购买，则每个购物篮可以用一个布尔向量来表示量化关联规则，如Age{X,”30--39”}

∩income{X,”40k—48k”}=〉buys{X,”computer”}Apriori算法Apriori算法是一种最有Apriori算法的步骤-----使用候选产生发现频繁项集。（1）由候选项集(candidateitemset)产生频繁项集(frequentitemset)；（2）由频繁项集(frequentitemset)产生强关联规则(strongassociationrule)。Apriori算法的步骤-----使用候选产生发现频繁项集Apriori使用一种称作逐层搜索的迭代方法，“K项集”用于探索“K+1项集”。首先，通过扫描数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁“1项集”的集合。该集合记作L1。然后，L1用于找频繁“2项集”的集合L2，而L2用于找L3，如此下去，直到不能再找到频繁“K项集”。找每个LK需要一次数据库全扫描。为了提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。Apriori算法Apriori使用一种称作逐层搜索的迭代方法，“K项集”用核心：连接步和剪枝步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算法主要为了提高数据访问效率，提升发现频繁项集的速度使用候选产生发现频繁项集Apriori性质：频繁项集的所有非空子集也必须是频繁的。Apriori算法目的意义Apriori算法主要为了提高数步骤1：发现频繁项集频繁项集发现过程：（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）~（5）直到不能发现更大频集

步骤1：发现频繁项集频繁项集发现过程：步骤2：产生关联规则根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果则输出规则“S→L－S”。注：L－S表示在项集L中除去S子集的项集。步骤2：产生关联规则根据前面提到的置信度的定义，关联规则的产举例举例由频繁项集产生关联规则频繁项集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规则可以输出。由频繁项集产生关联规则频繁项集l={B,C,E}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(L

k-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;

Apriori算法伪代码算法：Apriori，使用逐层迭代连接步和剪枝步第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)then6)deletec;//修剪，去掉无用的候选项7)elseaddctoCk;8)}9)returnCk;连接步和剪枝步第1步：连接(join)连接步和剪枝步第2步:剪枝(prune)procedurehas_infrequent_subset(c:candidatekitemset;Lk-1:frequent(k-1)itemset);//使用先验知识1)foreach(k-1)subsetsofc2)ifs∉Lk-1

then3)returntrue;4)returnfalse;连接步和剪枝步第2步:剪枝(prune)Apriori算法的基本流程使用逐层搜索的迭代方法，通过对数据库的多次扫描发现所有的频繁项集。在每一趟扫描中只考虑具有同一长度k(即为项集中所含项目的个数)的所有项集。算法的第一次扫描仅仅计算每个项目的具体支持度，以确定长度为1的频繁项集。在后继的每一次扫描中，首先使用在前一次获得的频繁项集Lk-1和Apriori-gen函数产生的候选项集q，接着扫描数据库，计算Ck中候选项的支持度，最后确定候选项集中哪些真正成为频繁项集。重复上述过程直到再也发现不了新的频繁项集为止。Apriori算法的基本流程使用逐层搜索的迭代方法，通过对数DatabaseDScanDC1L1L2C2C2ScanDC3L3ScanDApriori算法实例设定最小支持度阈值为2

DatabaseDScanDC1L1L2C2C2Scan练习题下表是某商店的事务数据库D，数据库中有9个事务。试用Apriori算法找出其关联规则。TID商品ID列表T100I1，I2，I5T200I2.I4T300I2，I3T400I1，I2，I4T500I1，I3T600I2，I3T700I1，I3T800I1，I2，I3，I5T900I1，I2，I3设定最小支持度阈值为2

练习题TID商品ID列表T100I1，I2，I5T200I2扫描D，对每个候选项计数，生成C1：项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2扫描D，对每个候选项计数，生成C1：项集支持度计数｛I1｝6比较候选项支持度计数与最小支持度计数，生成L1：

项集支持度计数｛I1｝6｛I2｝7｛I3｝6｛I4｝2｛I5｝2比较候选项支持度计数与最小支持度计数，生成L1：项集支持度由L1产生候选集C2：

项集｛I1，I2｝｛I1，I3｝｛I1，I4｝｛I1，I5｝｛I2，I3｝｛I2，I4｝｛I2，I5｝｛I3，I4｝｛I3，I5｝｛I4，I5｝由L1产生候选集C2：项集｛I1，I2｝｛I1，I3｝｛I再次扫描D，对每个候选项计数，产生L2：

项集支持度计数｛I1，I2｝4｛I1，I3｝4｛I1，I5｝2｛I2，I3｝4｛I2，I4｝2｛I2，I5｝2再次扫描D，对每个候选项计数，产生L2：项集支持度计数｛I对L2进行连接&剪枝，产生C3，即最终结果。

由频繁项集产生关联规则:L1={I1,I2,I5}的非空子集有：{I1,I2}{I1,I5}{I2,I5}{I1}{I2}{I5},结果关联规则如下：I1∧I2==>I5confidence=2/4=50%如果最小置信度阈值为70%，则2I1∧I5==>I2confidence=2/2=100%3,6条规则可以输出。I2∧I5==>I1confidence=2/2=100%请写出第2个频繁项集的关联规则I1=>I2∧I5confidence=2/6=33%I2==>I1∧I5confidence=2/7=29%I5==>I1∧I2confidence=2/2=100%项集｛I1，I2，I3｝｛I1，I2，I5｝支持度计数22对L2进行连接&剪枝，产生C3，即最终结果。由频繁项集产生可能产生大量的候选集可能需要重复扫描数据库Apriori算法局限性可能产生大量的候选集Apriori算法局限性Apriori算法的局限性可能需要产生大量候选项集。例如，如果有104个频繁1项集，可能产生107个候选2项集。可能需要重复扫描数据库，通过模式匹配检查一个很大的候选集合。由于依赖于候选项集产生频繁项集的理论（Apriori类算法）所开发的算法具有先天的弱点，使得在基于Apriori算法开发的应用没有实质性突破。

Apriori算法的局限性可能需要产生大量候选项集。例如，FP-growth算法-频繁模式增长Han等提出的一种新的算法理论，用一种压缩的数据结构(FP-tree)存储关联规则挖掘所需的全部数据信息，通过对源数据的两次扫描，将数据信息存到这种结构里，避开了产生候选项集的步骤，极大地减少了数据交换和频繁匹配的开销。这就是所谓不候选产生挖掘频繁项集的算法(FrequentPatternsGrowth,FP-growth)。采用分治策略，首先，将提供频繁项集的数据库压缩到一棵频繁模式树。然后，将压缩后的数据库划分成一组条件数据库，每个关联一个频繁项或“模式段”，并分别挖掘每个条件数据库。FP-growth算法-频繁模式增长Han等提出的一种新的算FP-growth算法-频繁模式增长(1)它构造了一种新颖的、紧凑的数据结构FP-tree。它是一种扩展的前缀树结构，存储了关于频繁模式数量的重要信息。(2)开发了基于FP-tree的模式片断成长算法，它从长度为1的频繁模式开始，只检查它的条件模式构建它的条件模式树，并且在这个树上递归地进行挖掘。模式的成长通过联合条件模式树新产生的后缀模式实现。(3)挖掘过程中采用的搜索技术是基于分区的，通过分割再解决的方法，而不是Apriori类算法的自下向上产生频繁模式的集合。FP-growth算法-频繁模式增长(1)它构造了一种新颖的2022/12/22135示