1、第四章关联规则4.1关联规则的基本概念4.2关联规则的挖掘过程4.3关联规则的Apriori算法4.4关联规则的FP-Growth算法习题4.1 关联规则的基本概念第四章 关联规则关联规则概念最早是由Agrawal等人在1993年首先提出的，最初的动机是针对购物篮分析问题提出的，其目的是为了发现交易数据库中不同商品之间的联系规则。Agrawal等人于1993年提出了关联规则挖掘算法AIS，但是性能较差。1994年，他们建立了项目集格空间理论，并提出了著名的Apriori算法，至今Apriori仍然作为关联规则挖掘的经典算法被广泛讨论，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。4.
2、1 关联规则的基本概念第四章 关联规则More应用市场：市场货篮分析、交叉销售（Crossing Sale）、部分分类（Partial Classification）、金融服务（Financial Service），以及通信、互联网、电子商务 4.1 关联规则的基本概念第四章 关联规则4.1.1 基本概念1）项（Item）、项集（Itemset）、k-项集与事务 项：是指数据库中不可分割的最小单位。项集：是指多个项的集合，其中，空集是指不包含任何项的项集。k-项集：是指由k个项构成的项集组合。事务：是指用户定义的一个数据库操作序列，这些操作序列是一个不可分割的工作单位。2）频繁项集（Frequ
3、ent Itemset）频繁项集：是指在所有训练元组中同时出现的次数，超过人工定义的阈值的项集。在关联规则的挖掘过程中，一般只保留候选项集中满足支持度条件的项集，不满足条件的舍弃。4.1 关联规则的基本概念第四章 关联规则4.1.1 基本概念3）极大频繁项集（Frequent Large Itemset）极大频繁项集：不存在包含当前频繁项集的频繁超集，则当前频繁项集就是极大频繁项集。4）支持度（Support）支持度：是指项集在所有训练元组中同时出现的次数，因此，支持度可以表述为Support(X-Y)=|X U Y|/|N|。其中，X，YN，XY=，|X U Y|表示集合X与Y在一个事务中同
4、时出现的次数，|N|表示数据记录的总个数。5）置信度（Confidence）置信度可以表述为：Confidence(X-Y)=|X U Y|/|X|=Support(X-Y)/Support（X），其中，X，YN，XY=，|X U Y|表示集合X与Y在一个事务中同时出现的次数，|X|表示X出现的总次数。4.1 关联规则的基本概念第四章 关联规则4.1.2 关联规则定义关联规则（Association rule）：指从事务数据库、关系数据库和其他信息存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。关联分析（Association analysis）：用于发现隐藏在大型数据集中
5、的令人感兴趣的联系。所发现的联系可以用关联规则或者频繁项集的形式表示。关联规则挖掘就是从大量的数据中挖掘出描述数据项之间相互联系的有价值的有关知识。4.1 关联规则的基本概念第四章 关联规则4.1.2 关联规则定义一般地，关联规则挖掘问题可以划分成两个子问题：1）发现频繁项目集通过用户给定的Minsupport，寻找所有频繁项目集，即满足Support不小于Minsupport的项目集。事实上，这些频繁项目集可能具有包含关系。一般地，我们只关心那些不被其它频繁项目集所包含的所谓频繁大项集的集合。这些频繁大项集是形成关联规则基础。2）生成关联规则通过用户给定的Minconfidence，在每个最
6、大频繁项目项目集中，寻找Confidence不小于Minconfidence的关联规则。这两个子问题主要在4.3节中进行介绍。4.1 关联规则的基本概念第四章 关联规则4.1.3 关联规则分类1）基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。2）基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。3）基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。第四章关联规则4.2关联规则的挖掘过程4.1关联规则的基本概念4.3关联规则的Apriori算法4.4关联规则的FP-Growth算法习题大数据应用人才培养系列教材4.2关联规则的挖掘过程第四章 关联规则4.2.
7、1 频繁项集产生格结构（Lattice Structure）常常被用来枚举所有可能的项集。图1 项集的格4.2关联规则的挖掘过程第四章 关联规则4.2.2 频繁项集的产生及其经典算法查找频繁项目集经典的查找策略基于精简集的查找策略基于最大频繁项集的查找策略按照挖掘的策略不同经典的挖掘完全频繁项集方法基于广度优先搜索策略的关联规则算法基于深度优先搜索策略的算法Apriori算法、DHP算法FP-Growth算法、ECLAT算法COFI算法与经典查找不同方法基于精简集的方法基于最大频繁项目集的方法A-close算法MAFIA算法、GenMax算法DepthProject算法格结构（Lattice
8、Structure）常常被用来枚举所有可能的项集。4.2关联规则的挖掘过程第四章 关联规则4.2.3 强关联规则生成关联规则是指通过用户给定的最小可信度，在每个最大频繁项集中，寻找可信度不小于Minconfidence的关联规则。得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、.k个元素作为后件，该项目集中的其他元素作为前件，计算该规则的置信度进行筛选即可。这样的穷举效率显然很低。假如对于一个频繁项目集f，可以生成下面这样的关联规则：（f-）-4.2关联规则的挖掘过程第四章 关联规则4.2.4 关联规则评价标
9、准在某些特定情况下，仅凭支持度和置信度来衡量一条规则，是完全不够的，对于数据的筛选力度也不足。因此，需要介绍更多的判断强关联规则的评价标准，来满足实际需求。支持度和置信度并不能过成功滤掉那些我们不感兴趣的规则，因此我们需要一些新的评价标准，下面介绍六中评价标准：相关性系数，卡方指数，全置信度、最大置信度、Kulc、cosine距离。4.2关联规则的挖掘过程第四章 关联规则4.2.4 关联规则评价标准1）相关性系数lift引入正相关和负相关的机制，对于不是正相关的商品规则，可以用相关性系数lift过滤掉。对于规则A-B或者B-A，lift(A,B)=P(AB)/(P(A)*P(B)，如果lift
10、(A,B)1表示A、B呈正相关，lift(A,B)B),confidence(B-A)4）最大置信度max_confidence最大置信度则与全置信度相反，求的不是最小的支持度而是最大的支持度，max_confidence(A,B)=maxconfidence(A-B),confidence(B-A)，不过感觉最大置信度不太实用。4.2关联规则的挖掘过程第四章 关联规则4.2.4 关联规则评价标准5）KulcKulc系数本质上是对两个置信度做一个平均处理，公式为：kulc(A,B)=(confidence(A-B)+confidence(B-A)/2。6）cosine距离cosine(A,B)
11、=P(AB)/sqrt(P(A)*P(B)=sqrt(P(A|B)*P(B|A)=sqrt(confidence(A-B)*confidence(B-A)第四章关联规则4.3关联规则的Apriori算法4.1关联规则的基本概念4.2关联规则的挖掘过程4.4关联规则的FP-Growth算法习题大数据应用人才培养系列教材4.3关联规则的Apriori算法第四章 关联规则频繁项集的产生及其经典算法之一Apriori算法 Apriori算法1概念Apriori算法基于频繁项集性质的先验知识，使用由下至上逐层搜索的迭代方法，即从频繁1项集开始，采用频繁k项集搜索频繁k+1项集，直到不能找到包含更多项的频
12、繁项集为止。Apriori算法由以下步骤组成，其中的核心步骤是连接步和剪枝步：4.3关联规则的Apriori算法第四章 关联规则频繁项集的产生及其经典算法之一Apriori算法 Apriori算法2核心思想Apriori算法的核心思想主要体现在两个方面，即其两个关键步骤：1)连接步为了找到频繁k项集Lk，首先将Lk-1与自身连接，产生候选k项集Ck，Lk-1的元素是可连接的。4.3关联规则的Apriori算法第四章 关联规则频繁项集的产生及其经典算法之一Apriori算法 Apriori算法2核心思想Apriori算法的核心思想主要体现在两个方面，即其两个关键步骤：2)剪枝步候选k项集Ck是L
13、k的超集，因此，Ck成员即可为频繁项集也可不是频繁的，但所有的频繁项集都包括在Ck中。扫描数据库，确定Ck中每一个候选的计数，从而确定Lk（计数值不小于最小支持度计数的所有候选是频繁的，从而属于Lk）。然而，Ck可能很大，这样所涉及的计算量就很大。为压缩Ck，使用Apriori性质：任何非频繁的(k-1)项集都不可能是频繁k项集的子集。因此，如果一个候选k项集的(k-1)项集不在Lk中，则该候选项也不可能是频繁的，从而可以由Ck中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。4.2关联规则的挖掘过程4.2关联规则的挖掘过程频繁项集的产生及其经典算法之一Apriori算法 Aprior
14、i算法3步骤生成频繁1项集L1连接步剪枝步生成频繁k项集Lk重复步骤（2）（4），直到不能产生新的频繁项集的集合为止，算法中止。性能瓶颈Apriori算法是一个多趟搜索算法可能产生庞大的候选项集4.3关联规则的Apriori算法第四章 关联规则4.3关联规则的Apriori算法第四章 关联规则频繁项集的产生及其经典算法之一Apriori算法 Apriori算法4算法描述算法4-1 Apriori发现频繁项目集(1)L1=large 1-itemsets;(2)FOR(k=2;Lk-1;k+)DO BEGIN(3)Ck=apriori-gen(Lk-1);/Ck 是k个元素的候选集(4)FOR
15、all transactions tD DO BEGIN(5)Ct=subset(Ck,t);/Ct是所有t包含的候选集元素(6)FOR all candidates c Ct DO(7)c.count+;(8)END(9)Lk=c Ck|c.countminsup_count(10)END(11)Answer=kLk;4.3关联规则的Apriori算法第四章 关联规则频繁项集的产生及其经典算法之一Apriori算法 Apriori算法5改进鉴于Apriori算法需要多次扫描数据库，在实际应用中，运行效率往往不能令人感到满意，尤其是当数据库较大时更为棘手。为了提高Apriori算法的性能和运行
16、效率，许多专家对Apriori算法的改进展开了研究，形成了许多改进和扩展Apriori的方法。4.3关联规则的Apriori算法第四章 关联规则频繁项集的产生及其经典算法之一Apriori算法 Apriori算法5改进改进算法的途径包括以下几个方面：通过减少扫描数据库的次数改进I/O的性能；改进产生频繁项集的计算性能；寻找有效的并行关联规则算法；引入抽样技术改进生成频繁项集的I/O和计算性能；扩展应用领域。比如展开定量关联规则、泛化关联规则及周期性的关联规则的研究。4.3关联规则的Apriori算法第四章 关联规则频繁项集的产生及其经典算法之一Apriori算法 Apriori算法5改进鉴于A
17、priori算法需要多次扫描数据库，在实际应用中，运行效率往往不能令人感到满意，尤其是当数据库较大时更为棘手。为了提高Apriori算法的性能和运行效率，许多专家对Apriori算法的改进展开了研究，形成了许多改进和扩展Apriori的方法。第四章关联规则4.4关联规则的FP-Growth算法4.1关联规则的基本概念4.2关联规则的挖掘过程4.3关联规则的Apriori算法习题大数据应用人才培养系列教材4.2关联规则的挖掘过程频繁项集的产生及其经典算法之二FP-Growth算法FP-Growth算法1概念频繁模式树增长算法（Frequent Pattern Tree Growth）采用分而治之
18、的基本思想，将数据库中的频繁项集压缩到一棵频繁模式树中，同时保持项集之间的关联关系。然后将这棵压缩后的频繁模式树分成一些条件子树，每个条件子树对应一个频繁项，从而获得频繁项集，最后进行关联规则挖掘。4.4关联规则的FP-Growth算法第四章 关联规则4.2关联规则的挖掘过程频繁项集的产生及其经典算法之二FP-Growth算法FP-Growth算法2构建FP树FP-growth算法将数据集的特点以一种树结构的方式存储，称为FpTree。FpTree是一种用于编码数据集的有效方式，树结构定义如下：public class FpNode String idName;/id号 List childr
19、en;/子结点 FpNode parent;/父结点 FpNode next;/下一个id号相同的结点 long count;/出现次数4.4关联规则的FP-Growth算法第四章 关联规则4.2关联规则的挖掘过程频繁项集的产生及其经典算法之二FP-Growth算法FP-Growth算法2构建FP树树的每一个结点FpNode代表一个项，项的内容包括id号idName、子结点children、父结点parent、下一个id号相同的结点next以及该项的出现次数count。4.4关联规则的FP-Growth算法第四章 关联规则4.2关联规则的挖掘过程频繁项集的产生及其经典算法之二FP-Growth
20、算法FP-Growth算法3从FP树中挖掘频繁项集（1）从header table的最下面的item开始，构造每个item的条件模式基（Conditional Pattern Base，CPB）。（2）构造条件FP-tree（Conditional FP-tree）累加每个CPB上的item的频繁度（计数），过滤低于阈值的item，构建FP-tree。（3）FP-Growh：递归的挖掘每个条件FP-tree，累加后缀频繁项集，直到找到FP-tree为空或者FP-tree只有一条路径（只有一条路径情况下，所有路径上item的组合都是频繁项集）。可以证明（严谨的算法和证明在此不进行叙述），频繁项集
21、即不重复也不遗漏。4.4关联规则的FP-Growth算法第四章 关联规则4.2关联规则的挖掘过程 FP-Growth算法4步骤FP-Growth算法由以下步骤组成：扫描事务数据库D，生成频繁1项集L1将频繁1项集L1按照支持度递减顺序排序，得到排序后的项集L1构造FP树通过后缀模式与条件FP树产生的频繁模式连接实现模式增长1234图2 FP树的构造4.4关联规则的FP-Growth算法第四章 关联规则频繁项集的产生及其经典算法之二FP-Growth算法4.2关联规则的挖掘过程频繁项集的产生及其经典算法之二FP-Growth算法FP-Growth算法5对比FpGrowth算法的平均效率远高于Ap
22、riori算法，但它并不能保证高效率，它的效率依赖于数据集。当数据集中的频繁项集的没有公共项时，所有的项集都挂在根结点上，不能实现压缩存储，而且Fptree还需要其他的开销，需要存储空间更大，使用FpGrowth算法前，首先需要对数据分析，在决策是否采用FpGrowth算法。4.4关联规则的FP-Growth算法第四章 关联规则4.2关联规则的挖掘过程4.2.2 频繁项集的产生及其经典算法给定一个事务数据库，如表2所示，采用Apriori算法生成该事务数据库的关联规则。设置信度为2/3。采用Apriori算法求出强关联规则？TID项目列表T1I1,I2,I5T2I2,I4T3I2,I3T4I1
23、,I2,I4T5I3,I4T6I1,I3T7I1,I2,I3,I5T8I2,I3,I4T9I2,I3,I5T10I3,I54.4关联规则的FP-Growth算法第四章 关联规则第四章关联规则4.4关联规则的FP-Growth算法4.1关联规则的基本概念4.2关联规则的挖掘过程4.3关联规则的Apriori算法习题大数据应用人才培养系列教材1说明关联规则挖掘的目的和作用。2简要说明在频繁模式发现技术中，产生候选项集和不产生候选项集两种技术各自的特点和优缺点。3练习使用SQL Server 2005的关联规则挖掘模型。4如课本中表4-1所示，设定最小支持度s=10%和s=40%，置信度c=70%，试分别计算该示例数据库中的频繁项集和规则。习题：5给定一个事务数据库，如表2所示，采用Apriori算法生成该事务数据库的关联规则（设置信度为2/3）。分别采用Apriori算法和FP-Growth算法，求出强关联规则？习题：TID项目列表T1I1,I2,I5T2I2,I4T3I2,I3T4I1,I2,I4T5I3,I4T6I1,I3T7I1,I2,I3,I5T8I2,I3,I4T9I2,I3,I5T10I3,I5感谢聆听
