1、2003-11-1高等教育出版社1第六章：关联规则n6.1 引言n6.2 关联规则基本模型n6.3 多级关联规则与多维关联规则n6.4 关联规则价值衡量与发展n本章小结2003-11-1高等教育出版社2第六章：关联规则n6.1 引言n6.2 关联规则基本模型n6.3 多级关联规则与多维关联规则n6.4 关联规则价值衡量与发展n本章小结2003-11-1高等教育出版社3关联规则简介n关联规则反映一个事物与其他事物之间的相互依存性和关联性。如果两个或者多个事物之间存在一定的关联关系，那么，其中一个事物就能够通过其他事物预测到。n典型的关联规则发现问题是对超市中的货篮数据（Market Basket
2、）进行分析。通过发现顾客放入货篮中的不同商品之间的关系来分析顾客的购买习惯。2003-11-1高等教育出版社4第六章：关联规则n6.1 引言n6.2 关联规则基本模型n6.3 多级关联规则与多维关联规则n6.4 关联规则价值衡量与发展n本章小结2003-11-1高等教育出版社5关联规则基本模型 nIBM公司Almaden研究中心的R.Agrawal首先提出关联规则模型，并给出求解算法AIS。随后又出现了SETM和Apriori等算法。其中，Apriori是关联规则模型中的经典算法。2003-11-1高等教育出版社6关联规则基本模型（续）n设I=i1,i2,im为所有项目的集合，D为事务数据库，
3、事务T是一个项目子集（TI）。每一个事务具有唯一的事务标识TID。设A是一个由项目构成的集合，称为项集。事务T包含项集A，当且仅当AT。如果项集A中包含k个项目，则称其为k项集。项集A在事务数据库D中出现的次数占D中总事务的百分比叫做项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集是频繁项集（或大项集）。2003-11-1高等教育出版社7关联规则基本模型（续）n关联规则是形如XY的逻辑蕴含式，其中XI，YI，且XY=。如果事务数据库D中有s%的事务包含XY，则称关联规则XY的支持度为s%，实际上，支持度是一个概率值。若项集X的支持度记为support(X)，规则的信任度为
4、support(XY)support(X)。这是一个条件概率P(Y|X)。也就是：support(XY)=P(X Y)confidence(XY)=P(Y|X)2003-11-1高等教育出版社8关联规则基本模型（续）n关联规则就是支持度和信任度分别满足用户给定阈值的规则。n发现关联规则需要经历如下两个步骤：n找出所有频繁项集。n由频繁项集生成满足最小信任度阈值的规则。2003-11-1高等教育出版社9Apriori算法的步骤nApriori算法命名源于算法使用了频繁项集性质的先验（Prior）知识。nApriori算法将发现关联规则的过程分为两个步骤：n通过迭代，检索出事务数据库中的所有频繁项
5、集，即支持度不低于用户设定的阈值的项集；n利用频繁项集构造出满足用户最小信任度的规则。n挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。2003-11-1高等教育出版社10频繁项集n为了避免计算所有项集的支持度（实际上频繁项集只占很少一部分），Apriori算法引入潜在频繁项集的概念。若潜在频繁k项集的集合记为Ck，频繁k项集的集合记为Lk，m个项目构成的k项集的集合为，则三者之间满足关系Lk Ck 。构成潜在频繁项集所遵循的原则是“频繁项集的子集必为频繁项集”。kmCkmC2003-11-1高等教育出版社11关联规则的性质：n性质6.1 频繁项集的子集必为频繁项集。n性质6.2
6、 非频繁项集的超集一定是非频繁的。nApriori算法运用性质6.1，通过已知的频繁项集构成长度更大的项集，并将其称为潜在频繁项集。潜在频繁k项集的集合Ck 是指由有可能成为频繁k项集的项集组成的集合。以后只需计算潜在频繁项集的支持度，而不必计算所有不同项集的支持度，因此在一定程度上减少了计算量。2003-11-1高等教育出版社12Apriori算法n(1)L1=频繁1项集;n(2)for(k=2;Lk-1;k+)do begin n(3)Ck=apriori_gen(Lk-1);/新的潜在频繁项集 n(4)for all transactions tD do begin n(5)Ct=sub
7、set(Ck,t);/t中包含的潜在频繁项集 n(6)for all candidates cCt do n(7)c.count+;n(8)end;n(9)Lk=cCk|c.countminsup n(10)end;n(11)Answer=kkL2003-11-1高等教育出版社13LIG算法基本定义及定理n定义6.1 设T是事务数据库中的一个事务，TD，称T中基本项的个数为事务T的规模，记为T。n定义6.2 若d是一个项集，将d中元素的个数称为该项集的长度，记为d。n定理6.1 在一个已知事务数量的数据集D中，规模小于A的事务不会影响计算D(A)。n定理6.2 已知数据集D中的一个频繁k项集A
8、k（即，D(Ak)minsup），令数据集D=ddDdmk，若D(Ak)minsup，则对D中任意一个频繁m项集Am而言，一定有Ak Am。2003-11-1高等教育出版社14LIG算法基本定义及定理n定义6.3 当kpq时，sp为项集I在规模为p的事务中出现的次数；当p=q时，sp是项集I在规模不低于p的事务中出现的次数。这里 元组(sk,sk+1,sq1,sq)称为项集I的多段支持度。n定义6.4 若项I能与区间ip,iq，ir,is，iu,iv中的频繁1项集构成潜在频繁2项集，而与任何区间外的项均不构成频繁2项集，则称这些区间为项I的相关区间。()qkDp ksI2003-11-1高等教
9、育出版社15LIG算法基本定义及定理n定理6.3 若频繁k项集itemi和itemj的多段支持度分别为(ik,ik+1,iq)和(jk,jk+1,jq)，满足 1)+=t;n(7)end;n(8)L1=large 1-itemset;/满足最小支持度n(9)C2=a,b a L1 and ba.AREA;/潜在频繁2项集2003-11-1高等教育出版社17LIG算法（续）n(10)M2=C2中相异元素;/提取因子n(11)k=2,q置初值；n(12)do beginn(13)for all transactions t do beginn(14)Ct=subset(Ck,t)；/t中包含的潜在
10、频繁项集n(15)r=t;n(16)if(rq)then r=q;n(17)if(r=k)then t;/剔除长度为k的事务2003-11-1高等教育出版社18LIG算法（续）n(18)else t=Mk;/剔除事务中无价值的项n(19)for all Candidates cCt don(20)c.sr+；n(21)endn(22)LCk=limit-gen(k,Ck);/生成 Lk 和 LCkn(23)Ck+1=JOIN(LCk)；/新的潜在频繁项集的集合n(24)Mk+1=Ck+1中相异元素;/提取因子n(25)k+;q+;n(26)end while(LCk1);n(27)L=kkL2
11、003-11-1高等教育出版社19Apriori算法与LIG算法数据规模比较表 2003-11-1高等教育出版社20FP算法nProcedure FP_growth(Tree,)n(1)if Tree包含一个单一路径P thenn(2)for each 路径P中节点组合(记为)n(3)生成模式，拥有支持度为节点中的最小支持度n(4)else for each 树的头列表节点ai n(5)生成模式=ai且support=ai.supportn(6)构成，的条件模式基和的条件FP_tree Treen(7)if Tree thenn(8)call FP_growth(Tree,);2003-11-
12、1高等教育出版社21第六章：关联规则n6.1 引言n6.2 关联规则基本模型n6.3 多级关联规则与多维关联规则n6.4 关联规则价值衡量与发展n本章小结2003-11-1高等教育出版社22多级关联规则 n在很多应用中，由于多维数据空间上的数据稀少，在低层或原始抽象级别上很难发现数据项间的强关联（Strong Associations）。nHan等人对多级关联规则进行了深入研究，指出强关联在高层概念上可以描述通常意义的知识。n多级关联规则可以在不同的抽象空间上描述多层抽象知识。2003-11-1高等教育出版社23多级关联规则n在多个概念级别上生成的关联规则称为多级关联规则。n由于数据分布的分散
13、性，很难在数据最细节的层次上发现一些强关联规则。当引入概念层次后，就可以在较高的层次上进行数据挖掘。n概念分层可以由系统用户、领域专家、知识工程师人工提供，也可以根据数据分布的统计特征自动产生。n根据规则中涉及到的层次，多级关联规则可以分为同级关联规则和级间关联规则。2003-11-1高等教育出版社24多级关联规则的挖掘n多级关联规则的挖掘基本上可以沿用“支持度和信任度”的框架。挖掘多级关联规则时可采用自上而下，深度优先的方法，由较抽象的概念层开始向下，到较低的具体概念层（如原始概念层），对每个概念层的频繁项集累加计数，直到再也找不到频繁项集为止。nApriori算法及其变种算法均可以应用到每
14、一级频繁项集的发现上。n从模型上讲可以分成两类:n所有级别采用统一的最小支持度阈值;n低级别上采用较小的最小支持度阈值。2003-11-1高等教育出版社25规则的冗余性n概念分层允许在不同抽象层上发现知识，所以多级关联规则在数据挖掘中能发挥较大的作用。但由于“祖先”关系的原因，有些规则可能是冗余的。n如果同时挖掘到这两条规则且后者不能提供更新的信息，就把这个规则剔除。设规则R1是规则R2的祖先，如果通过修改R2的前件使之提升到上一级概念抽象后，能够得到规则R1，则规则R2就是冗余的，可以从规则集中把R2删去。2003-11-1高等教育出版社26多维关联规则 n在多维数据库中，将每个不同的谓词层
15、称作维。n称规则购买(X,“牛奶”)购买(X,“面包”)为单维或者维内关联规则，这些规则一般都是在交易数据库中挖掘出的。n对多维数据库而言，还有一类多维的关联规则。多维关联规则是涉及两个或多个属性或谓词的规则，例如：年龄(X,“20.30”)职业(X,“学生”)购买(X,“笔记本电脑”)2003-11-1高等教育出版社27多维关联规则的分类n如果在规则的每一维上使用不同的断言，就把包含两个或两个以上断言的关联规则称为多维关联规则。n如果规则中的断言不重复，就称这样的规则为维间关联规则（Interdimension Association rule）；n如果规则中的断言可以重复，就称之为混合维关
16、联规则（Hybrid-dimension Association Rule）。2003-11-1高等教育出版社28数量属性的处理方法 n数据库属性分为定性和定量两种。定性的属性有有限个可能取值；定量的属性不能给出确切范围的数量值。n数量属性的处理方法分为三种：n把数量值划分为若干个离散区间，用区间值描述数量属性，这样就可以把定量的问题转化为定性的问题。也就是通过数量属性静态离散化挖掘多维关联规则。n对离散数据而言，为适应数据挖掘需要，离散化进程可以是动态的，这样的关联规则称为数量相关规则。n如果在离散化时考虑数据点间的距离，就将这样的数量关联规则称为基于距离的关联规则。2003-11-1高等教
17、育出版社29用数量属性静态离散化挖掘多维关联规则 n在这种情况下，数量属性依据事先定义的概念层次进行离散化，数量值由范围取代。n数据立方体非常适合于挖掘多维关联规则，因为它包含描述多维数据结构的立方体格，有利于数据聚集和信息分组。n多维数据挖掘问题可以利用类似于Apriori的算法予以解决。在挖掘之前利用特定的概念分层对数量属性（量化属性）进行离散化。这里的离散化是静态的、预确定的。离散化的数值属性具有区间值，将每个区间看作一个类，就可以像定性属性那样处理。定性属性可以生成更高级别的概念。2003-11-1高等教育出版社30数量关联规则 n数量关联规则是多维的，往往需要对数量属性动态离散化，以
18、满足某种挖掘标准需要。n所谓2-维量化规则是指左部有两个量化属性、右部有一个分类属性的量化规则，如AQUAN1AQUAN2ACAT。2003-11-1高等教育出版社31数量关联规则（续）n可以利用关联规则聚集系统ARCS（Association Rule Clustering System）来发现数据关联规则。ARCS包括分箱、查找频繁项集、聚集和优化。ARCS的核心在于将量化属性映射到2-D栅格上，然后搜索栅格形成数据点的聚类，从而产生关联规则。n具体步骤如下：分箱、生成频繁项集、聚类。2003-11-1高等教育出版社32关联规则聚集系统ARCS 关联规则 聚类后的关联规则 分割 分箱数据的
19、数组 标准 最小信任度 最小支持度 测试数据 记录数据#of x-bins#of y-bins 关联规则 启发式优化器 分箱器 引擎 聚类 验证(聚类分析)位图转换规则 2003-11-1高等教育出版社33基于距离的关联规则 n数量关联规则先用分箱的方法将数量属性离散化，然后将结果区间聚合。由于分箱的方法未考虑数据点之间或区间之间的相对距离，因此不能体现区间数据的语义。n基于距离的关联规则挖掘紧扣区间数据的语义，同时允许数据值的临近，划分使得关联规则可以表达这种接近性。2003-11-1高等教育出版社34基于距离的关联规则n基于距离的关联规则算法分两趟扫描。n第一趟扫描使用聚类找出区间或簇；n
20、第二趟搜索频繁出现的簇组，得到基于距离的关联规则。2003-11-1高等教育出版社35第六章：关联规则n6.1 引言n6.2 关联规则基本模型n6.3 多级关联规则与多维关联规则n6.4 关联规则价值衡量与发展n本章小结2003-11-1高等教育出版社36规则价值衡量 n对关联规则的评价与价值衡量涉及两个层面：系统客观的层面和用户主观的层面。2003-11-1高等教育出版社37系统客观层面 n使用“支持度和信任度”框架可能会产生一些不正确的规则。如果把支持度和信任度设得足够低，就可能得到矛盾的规则。如果把阈值设得过高，就可能得到不符合实际的规则。因此，只凭支持度和信任度阈值未必总能找出符合实际
21、的规则。2003-11-1高等教育出版社38系统客观层面（续）n人们引入兴趣度概念，用来剔除不感兴趣的规则。一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强度之比，然而在应用中发现，只要把支持度作为产生项集的主要决定因素，就要把支持度设得足够低以保证不丢失任何有意义的规则，或者冒丢失一些重要规则的风险。前者计算效率是个问题，而后者则有可能丢失有意义的规则。n另一个度量值是“收集强度”（Collective Strength），使用“大于期望值”为条件来发现有意义的关联规则。项集的收集强度是0,区间上的一个数值，其中，0表示完备的否定相关性，表示完备的正相关性。2003-11-1
22、高等教育出版社39用户主观层面 n只有用户才能决定规则的有效性、可行性。所以，应该将用户的需求和系统更加紧密地结合起来。n可以采用基于约束（Consraint-based）的数据挖掘方法。具体约束的内容有：数据约束、限定数据挖掘的维和层次、规则约束。n如果把某些约束条件与算法紧密结合，既能提高数据挖掘效率，又能明确数据挖掘的目标。2003-11-1高等教育出版社40基于约束的关联规则 n基于约束的关联规则就是利用用户给出的各种约束关系，使挖掘出的规则更有效。这些约束包括：n知识类型约束 n数据约束 n维数或层约束 n兴趣度约束 n规则约束 n规则模板允许用户约束感兴趣的规则的语法形式，以便通过
23、规则形式化约束提高数据挖掘效率。规则模板可以来自分析者的实验、期望或对数据的直觉。2003-11-1高等教育出版社41对比度n在支持度和信任度关联规则框架中，采用最小信任度阈值来判断一个规则是否有意义。最小信任度仅体现事物之间的表面关系，并不代表必然的因果关系，往往产生的规则中有许多是冗余无用的。n在规则挖掘中加入前件和后件重要度的比较限制，称为对比度。一个项集的重要度为所有组成元素重要度之和。njjjmiiiBB11/规则后件重要度规则前件重要度2003-11-1高等教育出版社42冗余规则n定义6.5 若一个关联规则前件和后件的对比度的值大于某个指定的阈值，则称过于重要的前件推出非常次要的后
24、件，该规则是冗余规则。n定义6.6 若有两个或两个以上有相同后件的有意义关联规则，分别为：R1:Ai1,Aj1B，R2:Ai2,Aj2B，Rm,Rn，Rk :Aik,AjkB，信任度分别为：C1,C2,Cm,Cn,Ck，规定一个阈值，若规则Rm的前件属于规则Rn的前件，即RmARnA，且 CmCn ，则称规则Rn是冗余规则。2003-11-1高等教育出版社43冗余规则（续）n定义6.7 若有两个或两个以上有相同前件的有意义关联规则，分别为：R1:ABi1,Bj1，B2:ABi 2,Bj2，Rm,Rn，Rk :ABi k,Bj k，信任度分别为：C1,C2,Cm,Cn,Ck，规定一个阈值，若规则
25、Rm的后件属于规则Rn的后件，即RmBRnB，且 CmCn ，则称规则Rn是冗余规则。n定理6.4 若有两个有意义的关联规则，分别为：R1:A1B1，R2:A2 B2，信任度分别为：C1,C2，规定一个阈值，若R1A1R2A2且R2B2R1B1，同时 C1C2 ，则称规则R2是冗余规则。2003-11-1高等教育出版社44冗余规则（续）n定理6.5 如果关联规则R:AB，同时满足定义6.5和定理6.4，则其必满足定义6.6。n定理6.5剪除冗余规则的同时，得到简洁的规则。n定理6.4和定理6.5保证能够用最小前提推出尽可能有价值的信息，使规则更加简洁有效。2003-11-1高等教育出版社45关
26、联规则新进展 n在基于一维布尔型关联规则的算法研究中先后出现了AIS、SETM等数据挖掘算法。nR.Agrawal等人提出的Apriori 是经典算法。随后的关联规则发现算法大多数建立在Apriori算法基础上，或进行改造，或衍生变种。比如AprioriTid和AprioriHybrid算法。nLin等人提出解决规则挖掘算法中的数据倾斜问题，从而使算法具有较好的均衡性。Park等人提出把哈希表结构用于关联规则挖掘。2003-11-1高等教育出版社46关联规则新进展（续）n数据挖掘工作是在海量数据库上进行的，数据库的规模对规则的挖掘时间有很大影响。nAgrawal首先提出事务缩减技术，Han和P
27、ark等人也分别在减小数据规模上做了一些工作。n抽样的方法是由Toivonen提出的。nBrin等人采用动态项集计数方法求解频繁项集。nAggarwal提出用图论和格的理论求解频繁项集的方法。Prutax算法就是用格遍历的办法求解频繁项集。2003-11-1高等教育出版社47关联规则新进展（续）n关联规则模型有很多扩展，如顺序模型挖掘，在顺序时间段上进行挖掘等。n还有挖掘空间关联规则，挖掘周期性关联规则，挖掘负关联规则，挖掘交易内部关联规则等。nGuralnik提出顺序时间段问题的形式描述语言，以便描述用户感兴趣的时间段，并且构建了有效的数据结构SP树（顺序模式树）和自底向上的数据挖掘算法。n
28、最大模式挖掘是Bayardo等人提出来的。2003-11-1高等教育出版社48关联规则新进展（续）n随后人们开始探讨频率接近项集。Pei给出了一种有效的数据挖掘算法。nB.zden等人的周期性关联规则是针对具有时间属性的事务数据库，发现在规律性的时间间隔中满足最小支持度和信任度的规则。n贝尔实验室的S.Ramaswamy等人进一步发展了周期性关联规则，提出挖掘符合日历的关联规则（Calendric Association Rules）算法，用以进行市场货篮分析。nFang等人给出冰山查询数据挖掘算法。2003-11-1高等教育出版社49关联规则新进展（续）nT.Hannu等人把负边界引入规则发
29、现算法中，每次挖掘不仅保存频繁项集，而且同时保存负边界，达到下次挖掘时减少扫描次数的目的。nSrikant等人通过研究关联规则的上下文，提出规则兴趣度尺度用以剔除冗余规则。nZakia还用项集聚类技术求解最大的近似潜在频繁项集，然后用格迁移思想生成每个聚类中的频繁项集。nCAR，也叫分类关联规则，是Lin等人提出的一种新的分类方法，是分类技术与关联规则思想相结合的产物，并给出解决方案和算法。2003-11-1高等教育出版社50关联规则新进展（续）nCheung等人提出关联规则的增量算法。nThomas等人把负边界的概念引入其中，进一步发展了增量算法。如，基于Apriori框架的并行和分布式数据
30、挖掘算法。nOates等人将MSDD算法改造为分布式算法。还有其他的并行算法，如利用垂直数据库探求项集聚类等。2003-11-1高等教育出版社51第六章：关联规则n6.1 引言n6.2 关联规则基本模型n6.3 多级关联规则与多维关联规则n6.4 关联规则价值衡量与发展n本章小结2003-11-1高等教育出版社52本章小结n本章介绍了关联规则的基本模型和经典算法Apriori算法，在此基础上介绍了一种改进的关联规则发现算法LIG。这些算法是建立在候选集的基础上的。随后，介绍了一种不用候选集的算法FP算法。并介绍了多维和多级关联规则的挖掘方法。n本章的最后讨论了关联规则的评价问题，并简单地介绍了一些研究关联规则的新方向。
