数据挖掘原理与SPSS Clementine应用宝典第10章 关联规则

1数据挖掘原理与数据挖掘原理与SPSS Clementine应用宝典应用宝典 元昌安元昌安 主编主编 邓松李文敬刘海涛编著邓松李文敬刘海涛编著 电子工业出版社电子工业出版社210.8 约束性关联规则挖掘10.9 数量关联规则挖掘10.10 负关联规则挖掘算法10.11 加权关联规则挖掘算法10.12 应用实例分析10.13 小结10.1 关联规则基本概念10.2 关联规则算法原理10.3 分层搜索经典算法-Apriori算法10.4 并行挖掘算法10.5 增量更新挖掘算法10.6 多层关联规则挖掘10.7 多维关联规则挖掘第十章 关联规则算法310.1 关联规则基本概念 关联规则挖掘(Association Rule Mining)是帮助发现大量数据库中项集之间的关联关系。410.1.1关联规则定义关联规则定义v设 I = i1, i2, im, 为所有项目的集合，D 为事务数据库事务T 是一个项目子集(TI)。每一个事务具有唯一的事务标识Tid 。设A 是一个由项目构成的集合，称为项集。事务T 包含项集A，当且仅当A T 。5v最小支持度最小支持度minsup 即用户规定的关联规则必须满即用户规定的关联规则必须满足的最小支持度，它表示了一组物品集在统计意义足的最小支持度，它表示了一组物品集在统计意义上的需满足的最低程度。上的需满足的最低程度。v最小置信度最小置信度minconf 即用户规定的关联规则必须即用户规定的关联规则必须满足的最小置信度，它反应了关联规则的最低可靠满足的最小置信度，它反应了关联规则的最低可靠度。度。10.1.1关联规则定义关联规则定义610.1.2关联规则分类1基于规则中处理的变量的类别，可以分为布尔基于规则中处理的变量的类别，可以分为布尔型和数值型关联规则型和数值型关联规则 布尔型关联规则处理的值都是离散的、种类化布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。的，它显示了这些变量之间的关系。 数值型关联规则处理的是定量数据项（或属性）数值型关联规则处理的是定量数据项（或属性）之间的关系，之间的关系，7 2基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则 例如： IBM台式机Sony打印机是一个细节数据上的单层关联规则； 台式机Sony打印机，（此处台式机是IBM台式机的较高层次抽象）。10.1.2关联规则分类8 3基于规则中涉及到的数据维数，可以分为单维关联规则和多维关联规则 例如： 啤酒尿布 (单维) 性别=“女”职业=“秘书” (多维)10.1.2关联规则分类910.2关联规则算法原理v关联规则的挖掘就是在事务数据库D中找出具有用户给定的最小支持度minsup和最小置信度minconf的关联规则。v如果项集的支持度超过用户给定的最小支持度阈值(minsup)，就称该项集是频繁项集或大项集。1010.2.1关联规则挖掘算法的两个步骤vStep1 根据最小支持度阈值找出数据集D中所有频繁项目集；vStep2根据频繁项目集和最小置信度阈值产生所有关联规则。 11关联规则挖掘的基本模型算法算法1算法算法2数据集数据集规则规则用用 户户最小支持度最小支持度最小置信度最小置信度图图10-1 关联规则挖掘的基本模型关联规则挖掘的基本模型1210.2.2基本关联规则算法搜索算法搜索算法 该类算法只适合于项集数量相对较小的数据集中的关联规则挖掘。分层算法(宽度优先算法) Apriori算法是这类算法的典型代表，该算法需扫描数据集的次数等于最大频繁项目集的项目数。13深度优先算法深度优先算法 此类算法中最新最高效的是J.Han等人提出的FP-growth(Frequent-pattern Growth)算法。划分算法 划分算法的基本思想是将整个数据集划分成可以存放在内存中进行处理的数据块，以节省访问外存的I/0开销。 抽样算法 如何计算负边界以找回部分遗漏的频繁项集是抽样算法的关键。 10.2.2基本关联规则算法1410.2.3复杂关联规则算法 多层次关联规则挖掘一般有两种途径: 一种是把单层次关联规则挖掘算法直接应用于多层次。 另一种是在不同的层次应用不同的支持度阈值和置信度阈值。1510.3 分层搜索算法-Apriori算法 1L1L2L3LkL10.3.1 频繁项集的产生频繁项集的产生vApriori算法使用层次顺序搜索的循环方法（又称作逐层搜索的迭代方法）产生频繁项集，即用频繁k-项集探索产生(k+1)-项集。首先，找出长度为1的频繁项集，记为 ， 用于产生频繁2-项集 的集合，而用于产生频繁3-项集 的，如此循环下去，直到不能找到新的频繁k-项集。找每个 需要扫描数据库一次。16举例:已知事务数据库D如表10.1所示，最小支持度计数为2，即 minsupport=2/9，v利用Apriori算法挖掘所有满足minsup的频繁集。 17 (1)第一次扫描，扫描数据库获得每个候选项的计数，从而获得频繁1-项集。如表10-2所示。 (2)根据L1生成2-候选集C2，然后扫描数据库D，计算各项集的支持度，如表10.3所示。从而得到频繁2-项集，如表10.4所示。1819 (3) L2进行自连接得到C3=I1, I4, I5， I1, I2, I4， I1, I3, I4， I1, I3, I5， I2, I3, I4， I3, I4, I5 因为 I1, I2, I4的子集 I1, I2,和 I1, I3, I4、 I1, I3, I5的子集 I1, I3,及 I2, I3, I4的子集 I2, I3不在L2中 因此，从C3中删除 I1, I2, I4、 I1, I3, I4、 I1, I3, I5、 I2, I3, I4得： C3= I1, I4, I5， I3, I4, I5。然后再扫描数据库D，计算各项集的支持度计数，如表10.5所示，从而得到频繁3-项集L3，如表10.6所示。20(4)L3进行自连接得到C4= I1, I3, I4 , I5，由于 I1, I3, I4 , I5的子集 I1, I3, I4 ,不在L3中，因此删除 I1, I3, I4 , I5后C4=，进而L4=，算法终止。2110.3.2产生关联规则v利用如下公式来计算所获关联规则的置信度。unt(A)support_coB)unt(Asupport_co)|()(BAPBAconfidence 其中，support_count(AB)是包含项集AB的交易记录数目，support_count(A)是包含项集A的交易记录数目。22v利用频繁项集生成规则的算法描述如下：for all 频繁k项集 ,k2 do begin H1= 中规则的后件，该规则的后件中只有一个项目； Call ap_genrules( ,H1);end;Procedure ap_genrules( ：频繁项集, Hm：m个项目的后件的集合)klklklkl23vif(km+1) then begin Hm+1=apriori_gen(Hm)for all hm+1 Hm+1 do begin conf=support( )/support( -hm+1); if(confminconf) then output 规则 -hm+1hm+1 with confidence=conf and support=support( );klklklkl24v例102 以表10.1所示数据为例，来说明关联规则的生成过程。频繁项集 l = I1, I4, I5，以下将给出根据l所产生的关联规则。L 的非空子集为： I1、 I4、I5、 I1, I4、 I4, I5和 I1, I5。以下就是据此所获得的关联规则及其置信度。I1I4I5 confidence=2/2=100%I1I5I4 confidence=2/2=100%I4I5I1 confidence=2/4=50%I1I4I5 confidence=2/2=100%I4I1I5 confidence=2/7=28.5%I5I1I4 confidence=2/6=33.3%如果最小置信度阈值为70%，那么仅有第（1）个、第（2）个和第（4）个规则，由于它们的置信度大于最小置信度阈值而被保留下来作为最终的输出。2510.3.3 Apriori算法性能分析 对于存在大量频繁模式、长模式或者最小支持度闭值较小时，这类Apriori算法将面临下面的困难: ( 1)算法将花费较大的开销来处理数目特别巨大的候选项集。 (2)多次扫描事务数据库，需要很大的I/O负载。2610.3.4 Apriori算法改进 有以下几种算法：l 数据划分（Partition）l 散列（Hash）方法l 采样(sampling)方法2710.4 并行挖掘算法 10.4.1并行算法思想并行算法思想v开发并行算法有两种途径:其一是对已有的串行算法进行改进，挖掘其中的并行性质并加以利用，使得串行程序并行化；其二是对问题的本质重新审视，设计全新的并行算法。v比较经典的算法有基于Apriori算法、DHP算法、DIC算法的并行算法和基于集群和格遍历的并行算法。 28 vCD算法的基本思想是:在每一个处理机上都存储全局的候选项集和频繁项集，每一步计算时利用 Apriori算法计算出候选集在本地数据上的支持数，然后做一次同步，各处理机交换本地的候选项集的支持数，使得每个处理机的候选项集都得到全局支持数，从而得到全局频繁项集Lk。1算法算法CD(Count Distribution)29 DD算法更好地利用了全局的有效存储空间，算法更好地利用了全局的有效存储空间，它在每个处理中存储不同的候选项集，这样在处它在每个处理中存储不同的候选项集，这样在处理机数量增加时，一步可以增加计算的候选项集理机数量增加时，一步可以增加计算的候选项集数量。每个处理机为了计算本地候选项集的全局数量。每个处理机为了计算本地候选项集的全局支持数，必须既要计算候选项目集在本地的支持支持数，必须既要计算候选项目集在本地的支持数，也要计算在所有其它的处理机上的支持数数，也要计算在所有其它的处理机上的支持数2.算法算法DD(Data Distribution)30 CaD算法综合了算法综合了DD和和CD算法，以弥补它们算法，以弥补它们各自的不足。各自的不足。 与与DD算法相似，算法相似，CaD算法也是在算法也是在各节点间分配候选集，但它有选择地对数据库进各节点间分配候选集，但它有选择地对数据库进行分割，使每个节点可以根据本地的数据来处理行分割，使每个节点可以根据本地的数据来处理它的候选集，减少处理器之间对数据和各候选集它的候选集，减少处理器之间对数据和各候选集的依赖，从而减少同步，减少通信量。的依赖，从而减少同步，减少通信量。 3算法算法CaD(Candidate Distribution)3110.5 增量更新挖掘算法v10.5.1增量挖掘增量挖掘 增量式关联规则更新技术应具备下列特性: (1)规则应可随数据的变化而变化； (2)规则更新时应可避免再次处理旧数据，而可利用在先前发现过程中所获得的结果； (3)更新维护方法应尽可能独立于具体的发现算法。3210.5.2 FUP 算法 算法的基本思想:和Apriori算法的框架一致的。每次循环对应一定长度的项集，循环从1-项集开始，在以后每一次循环，分别发现k-项集，直到没有更长的项集出现为止。而且，从第二次循环开始，每一次循环的候选项集都是根据前一次循环所发现的频繁项集生成的。在每一次循环中，根据增加的数据库db对L中的频繁k-项集的支持度进行更新，以过滤出淘汰者(losers)，这一过程中只要遍历增加的数据库db。在遍历增加的数据库db时，根据db中的事务产生一组候选项集Ck，并计算它们在数据库db中的支持度。然后根据D对候选项集Ck中的项目的支持度进行更新，以发现新的频繁项集。3310.6 多层关联规则挖掘 10.6.1 概念层次（概念层次（Conceptual Hierarchies ） 数据库中的概念按照各部分的顺序被组织起来，这被称为概念层次。概念层用来说明数据各部分之间的顺序。概念层次组织为树状结构，包含若干个节点。树中的结点代表属性的取值称为概念，概念层次树的根节点默认指定为“ANY”。3410.6.2 多层关联规则挖掘方法v多层关联规则的挖掘可以基于支持度-置信度框架。一般来说，可以采用自顶向下的策略，由最高概念层向下，到较低的更特定的概念层，对每个概念层计算频繁项集累加计数，直到不能再找到频繁集。对于每一概念层次（挖掘），可以使用已有的发现频繁集的任何算法来寻找频繁项集，如Apriori算法或类似算法。 35 利用递减支持阈值挖掘多层关联规则，有以下四种常用的搜索策略:l逐层独立l利用单项进行跨层次过滤l利用k-项集进行跨层次过滤l受控利用单项进行跨层次过滤。 10.6.2 多层关联规则挖掘方法3610.7约束性关联规则挖掘 在约束性关联规则挖掘中，整个挖掘是在用户所提供的各种约束条件指导下进行的，这些约束包括： (1) 知识类型的约束。 (2) 数据约束。 (3)维或层次约束。 (4)兴趣度约束。 (5)规则约束。3710.7.1数据挖掘中约束的作用 约束在数据挖掘中的使用可以在如下方面起到关键作用: (1)聚焦挖掘任务，提高挖掘效率。 (2)保证挖掘的精确性。 (3)控制系统的使用规模。 3810.7.2约束的类型 从挖掘所使用约束的类型看，可以把用于关联规则挖掘的约束分为: 1单调性约束单调性约束 (Monotone Constraint) 2反单调性约束反单调性约束(Anti-monotone Constraint) 3可转变的约束可转变的约束(Convertible Constraint) 4简洁性约束简洁性约束(Succinct Constraint)3910.7.6时态约束关联规则挖掘 时态关联规则为了能真正反映不同时间间隔内的时间数据的内在规律，通常分为三个子过程： 1.初始阶段： 2.关联规则发现阶段 3.结果关联规则的表达4010.8.2数量关联规则的分类 1根据数值属性的处理方式进行分类根据数值属性的处理方式进行分类 （1）数值属性的静态离散化 （2）数值属性的动态离散化 （3）基于特定的技术进行数值属性的离散化412.根据使用的规则模版进行分类根据使用的规则模版进行分类（1）类似于）类似于“数值属性数值属性分类属性数值属性分类属性数值属性分类分类属性属性”这样的规则这样的规则 （2）分类规则的挖掘模版 简单的挖掘模版形式类似于“数值属性分类属性数值属性分类属性”这样的规则。 （3）其它挖掘模版 例如，挖掘模版形式类似于“分类属性数值属性分类属性”这样的规则。 10.8.2数量关联规则的分类4210.8.3数量关联规则挖掘的步骤 可以将数量关联规则挖掘分为以下5个步骤：Step1 数值属性的离散化Step2离散区间整数化Step 3在离散化的数据集上生成频繁项集Step 4产生关联规则Step 5规则输出4310.8.4数值属性离散化及算法 数值属性的离散化是数量关联规则挖掘的最关键步骤，其实质就是将连续属性值划分成区间。划分的方法对数量关联规则挖掘的质量起着决定性作用。44 根据是否允许同一个维重复出现，可以又细分为维间的关联规则 （不允许维重复出现） 和混合维关联规则 （允许维在规则的左右同时出现）。 10.9多维关联规则挖掘4510.9.1多维关联规则挖掘原理v在挖掘维间关联规则和混合维关联规则时，还要考虑不同的字段种类：种类型和数值型。v对于种类型的字段，原先的算法都可以处理。46 对于数值型的字段，需要进行一定的处理之后才可以进行。处理数值型字段的方法基本上有以下几种： (1) 数值字段被分成一些预定义的层次结构。 (2) 数值字段根据数据的分布分成了一些布尔字段。 (3) 数值字段被分成一些能体现它含义的区间。 (4) 直接用数值字段中的原始数据进行分析。10.9.1多维关联规则挖掘原理47 挖掘多维关联规则的技术可以根据量化属性的处理分为三类v第一种方法，使用预定义的概念分层对量化属性离散化。这种离散化在挖掘之前进行。v第二种方法，根据数据的分布，将量化属性离散化到“箱”。这些可能在挖掘过程中进一步组合。 v第三种方法，量化属性离散化，以紧扣区间数据的语义。 10.9.1多维关联规则挖掘原理4810.9.2 MAQA算法Step 1 对于多值属性A, 取值范围为L,R。若为数量属性,则应用聚类算法确定属性的划分;若为类别属性, 则进行归纳划分。Step 2 将划分后的属性区段Lk,Rk或属性值映射成序对(A,K),进而映射为布尔属性Am, 所有这样的属性构成项集。Step 3 采用了基本的Apriori 算法从项集中寻找所有有价值的项, 构成频繁项集；有价值的项是指支持它的交易量超过给定的最小支持度的项。4910.9.2 MAQA算法Step 4在频繁集中迭代地搜索出组合后的支持度超过给定阈值的两个项, 并将其组合并入频繁集中；如果是相同属性的相邻区间, 则进一步合并。Step 5 应用频繁集产生关联规则。Step 6 确定有价值的（Interesting）关联规则作为输出。5010.9.3确定多属性划分的聚类算法v如果一个数量属性的取值数目过多时,则将这个属性划分为若干个区段。如果一个类别属性的取值过多时,则将其属性值进行归纳51 for 每个取值数N的属性 doStep 1 计算每个属性值所对应的交易数Cj;Step 2 寻找所有的局部最大点Maxi和最小点MinLi和MinRi来确定区段;Step 3 计算每个MinLi和MinRi之间的交易数Sumi;Step 4 如果满足合并条件则合并两个相邻区段,得到K个区段;10.9.3确定多属性划分的聚类算法52Step 5 S=SumimaxSumiminSumi;Step 6 Save=S(K2);Step 7 寻找所有大于c*Save的Sumi,并将结果存于Stmp;Step 8 For Stmp中每个区段j do if Sumi/(MinRi-MinLi)S(MinR-MinL) then 保存区段j于Sres结果为有价值的区段,保存在Sres中。10.9.3确定多属性划分的聚类算法5310.10负关联规则挖掘算法v在数据集中还存在着形如AB(项集A 的出现会抑制项集B 的出现) 、AB(项集A 不出现会诱导项集B 的出现) 、AB(项集A 不出现会抑制项集B 的出现) 的关联规则, 这三种形式的蕴含关系称为负关联规则。传统的形如AB 的蕴含关系称为正关联规则。负关联规则挖掘的是项目集中的否定联系。5410.10.1直接Apriori算法v直接Apriori算法的思想是将事务集看成是一个布尔矩阵，对于每一列，增加一个列。从初始的项目集的补集中挖掘正关联规则与负关联规则，假定给定一个初始项目集的矩阵，它的每一行代表一个事务，初始项目集的补集将初始项目集的每一个字节0、1互换。55 定理定理1 设，则有 其中： 为支持度函数。定理1描述的是三种不同形式的负关联规则支持度的计算方法。10.10.2“近似”负关联规则算法)sup(1)sup(AA)sup()sup()sup(BAABA)sup()sup()sup(BABBA)sup()sup()sup(1)sup(BABABA)sup(X56v定理定理2 设 ，则有BAIBIA,)(1)sup()sup()sup()(BAconfABAABAconf)sup(1)sup()sup()(ABABBAconf)(1)sup(1)sup()sup()sup(1)(BAconfABABABAconf其中：其中： 为置信度函数，如为置信度函数，如 表示的是负表示的是负关联规则关联规则 的置信度的置信度 )(Xconf)(BAconfBA 571加权关联规则发现算法加权关联规则发现算法-MINWAL(O)算法算法 MINWAL(O)算法算法类似Apriori算法，挖掘加权频繁k-项候是从候选（k-1）-项集通过连接得到，然后同样通过剪枝和检查删除这些不可能是其它加权频繁项集的子集的候选项，把加权频繁项集加入L；把可能成为加权频繁项集子集的项目集放入Ck ,以生成更高项加权频繁项集或候选频繁项集。10.11 加权关联规则挖掘算法5810.12 应用实例 目前很多高校对教学评价主要基于数值计算，把学生的评价作一总结，将结果通报给老师，作为晋升职称、评优等的依据，系里对老师做一奖惩及引导，不做深层的思考。这里我们将对教学评价数据进行关联规则挖掘，试图挖掘教学效果与教师的性别、年龄、职称、学历等的关联，找到课堂教学效果与教师整体素质的关系，从而合理调配一个班的上课老师，使学生能够较好地保持良好的学习状态，从而为教学部门提供决策支持信息，以便更好地开展教学工作，提高教学质量。59 1. 数据准备数据准备 这是我们随机抽取某高校教师教学质量评估表1000份，将教师编号、年龄、性别、职称、学历、公费进修、工作量和评定分数8项输入数据库，忽略其它信息。我们将通过数据挖掘找出性别、年龄、职称、学历、公费进修、工作量和评定分数之间的关系。表10.8给出了部分教学评价信息视图，共有1000条记录。60v在表10.8中，属性年龄、工作量、成绩都是数量属性(非离散属性)，这里，我们将其离散化。首先，对年龄进行分组:Al22，30，A231，35，A336，49，A450，60；然后对工作量进行分组:B1:0，120学时，B2:120学时以上；对成绩进行分组:C1:教学效果好85，100，C2:教学效果不是很好0，85)。将数量属性离散化后的结果如表10.9所示。 612挖掘关联规则挖掘关联规则v利用关联规则挖掘算法Apriori来挖掘关联规则了，找出性别、学历、年龄、职称、公费进修、工作量等因素对教学效果的影响，进而采取一定的措施，提高教学质量。v这里，设minsup= 5%，minconf=5%，得到满足最小支持度和最小可信度的关联规则6263v3挖掘结果分析挖掘结果分析 通过得到的关联规则，可得到如下的分析结果及改进措施。 （1）性别对教学效果的影响 规则女Cl和男C1的置信度分别为63.5%和60.4%，这两个关联规则的置信度基本相同，说明性别对教学效果没有什么影响，因此在引进教师时不应该考虑性别因素。 （2）年龄对教学效果的影响 年龄对教学效果的影响可以从下面3种情况进行分析: 64v3挖掘结果分析挖掘结果分析 随着年龄的增长，规则年龄教学效果好的置信度也增大，说明年龄大的教师的教学质量高。 规则22，30C1的置信度很低，这主要是因为目前高校引入的教师都是硕士以上，30岁以下的教师教学经验很少，应尽量少上课或不上课。 规则50，60C1的置信度很高，说明50，60这个年龄段的教师的教学质量很高，但支持度却很低，说明这部分老师承担的工作量不大。学校应采取一定措施，让老教师多承担教学工作。65v（3）职称对教学效果的影响 随着年龄的增大，职称也不断提高。反之，职称高的教师一般年龄也偏高，所以职称对教学效果的影响和年龄对教学效果的影响基本是一致的v（4）公费进修对教学效果的影响 从表10.10可知，关联规则:进修过Cl比关联规则:没进修过C1的置信度高，说明进修对提高教师的教学水平有很多作用3挖掘结果分析挖掘结果分析