《第10章 关联规则》由会员分享，可在线阅读，更多相关《第10章 关联规则（65页珍藏版）》请在金锄头文库上搜索。
1、数据挖掘原理与 SPSS Clementine应用宝典元昌安 主编邓松李文敬刘海涛编著电子工业出版社110.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 多维关联规则挖掘第十章 关联规则算法210.1 关联规则基本概念关联规则挖掘 (AssociationRuleMining)是帮助发现大量数据库中项集之间的关
2、联关系。310.1.1关联规则定义v 设 I=i1,i2, im,为所有项目的集合， D为事务数据库事务 T是一个项目子集 (TI)。每一个事务具有唯一的事务标识 Tid。设 A是一个由项目构成的集合，称为项集。事务 T包含项集 A，当且仅当 AT。4v 最小支持度 minsup 即用户规定的关联规则必须满足的最小支持度，它表示了一组物品集在统计意义上的需满足的最低程度。v 最小置信度 minconf 即用户规定的关联规则必须满足的最小置信度，它反应了关联规则的最低可靠度。10.1.1关联规则定义510.1.2关联规则分类1基于规则中处理的变量的类别，可以分为布尔型和数值型关联规则布尔型关联规
3、则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值型关联规则处理的是定量数据项（或属性）之间的关系，62基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则例如：IBM台式机 Sony打印机是一个细节数据上的单层关联规则；台式机 Sony打印机，（此处台式机是 IBM台式机的较高层次抽象）。10.1.2关联规则分类73基于规则中涉及到的数据维数，可以分为单维关联规则和多维关联规则例如：啤酒 尿布 (单维 )性别 =“女 ” 职业 =“秘书 ”(多维 )10.1.2关联规则分类810.2关联规则算法原理v 关联规则的挖掘就是在事务数据库 D中找出具有用户给定的最小支持度 m
4、insup和最小置信度 minconf的关联规则。v 如果项集的支持度超过用户给定的最小支持度阈值(minsup)，就称该项集是频繁项集或大项集。910.2.1关联规则挖掘算法的两个步骤v Step1根据最小支持度阈值找出数据集 D中所有频繁项目集；v Step2根据频繁项目集和最小置信度阈值产生所有关联规则。 10关联规则挖掘的基本模型算法 1 算法 2数据集 规则用 户最小支持度 最小置信度图 10-1 关联规则挖掘的基本模型1110.2.2基本关联规则算法搜索算法该类算法只适合于项集数量相对较小的数据集中的关联规则挖掘。 分层算法 (宽度优先算法 )Apriori算法是这类算法的典型代表
5、，该算法需扫描数据集的次数等于最大频繁项目集的项目数。12深度优先算法此类算法中最新最高效的是 J.Han等人提出的 FP-growth(Frequent-patternGrowth)算法。划分算法划分算法的基本思想是将整个数据集划分成可以存放在内存中进行处理的数据块，以节省访问外存的 I/0开销。 抽样算法如何计算负边界以找回部分遗漏的频繁项集是抽样算法的关键。 10.2.2基本关联规则算法1310.2.3复杂关联规则算法 多层次关联规则挖掘一般有两种途径 :一种是把单层次关联规则挖掘算法直接应用于多层次。另一种是在不同的层次应用不同的支持度阈值和置信度阈值。1410.3 分层搜索算法 -A
6、priori算法 10.3.1 频繁项集的产生v Apriori算法使用层次顺序搜索的循环方法（又称作逐层搜索的迭代方法）产生频繁项集，即用频繁 k-项集探索产生 (k+1)-项集。首先，找出长度为1的频繁项集，记为 ， 用于产生频繁 2-项集 的集合，而用于产生频繁 3-项集 的，如此循环下去，直到不能找到新的频繁 k-项集。找每个 需要扫描数据库一次。15举例 :已知事务数据库 D如表 10.1所示，最小支持度计数为 2，即 minsupport=2/9，v 利用 Apriori算法挖掘所有满足 minsup的频繁集。16 (1)第一次扫描，扫描数据库获得每个候选项的计数，从而获得频繁 1
7、-项集。如表 10-2所示。 (2)根据 L1生成 2-候选集 C2，然后扫描数据库 D，计算各项集的支持度，如表 10.3所示。从而得到频繁 2-项集，如表 10.4所示。 1718(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
8、,I5， I3,I4,I5。然后再扫描数据库 D，计算各项集的支持度计数，如表 10.5所示，从而得到频繁 3-项集 L3，如表 10.6所示。19(4)L3进行自连接得到 C4=I1,I3,I4,I5，由于 I1,I3,I4,I5的子集 I1,I3,I4,不在 L3中，因此删除 I1,I3,I4,I5后 C4=，进而 L4=，算法终止。 2010.3.2产生关联规则v 利用如下公式来计算所获关联规则的置信度。其中， support_count(AB)是包含项集 AB的交易记录数目， support_count(A)是包含项集 A的交易记录数目。21v 利用频繁项集生成规则的算法描述如下： f
9、orall频繁 k项集 ,k2dobegin H1=中规则的后件，该规则的后件中只有一个项目 ； Callap_genrules(,H1); end; Procedureap_genrules(：频繁项集 ,Hm：m个项目的后件的集合 )22v if(km+1)thenbeginHm+1=apriori_gen(Hm)forallhm+1 Hm+1dobeginconf=support()/support(-hm+1);if(confminconf)thenoutput规则 -hm+1 hm+1withconfidence=confandsupport=support();23v 例 10 2
10、以表 10.1所示数据为例，来说明关联规则的生成过程。频繁项集 l =I1,I4,I5，以下将给出根据 l所产生的关联规则。 L 的非空子集为： I1、 I4、 I5、 I1,I4、 I4,I5和 I1,I5。以下就是据此所获得的关联规则及其置信度。I1 I4I5confidence=2/2=100%I1 I5I4confidence=2/2=100%I4 I5I1confidence=2/4=50%I1I4 I5confidence=2/2=100%I4I1 I5confidence=2/7=28.5%I5I1 I4confidence=2/6=33.3%如果最小置信度阈值为 70%，那么仅
11、有第（ 1）个、第（ 2）个和第（4）个规则，由于它们的置信度大于最小置信度阈值而被保留下来作为最终的输出。 2410.3.3 Apriori算法性能分析对于存在大量频繁模式、长模式或者最小支持度闭值较小时，这类 Apriori算法将面临下面的困难 :(1)算法将花费较大的开销来处理数目特别巨大的候选项集。(2)多次扫描事务数据库，需要很大的 I/O负载。2510.3.4Apriori算法改进有以下几种算法：l数据划分（ Partition）l散列（ Hash）方法l采样 (sampling)方法2610.4并行挖掘算法10.4.1并行算法思想v 开发并行算法有两种途径 :其一是对已有的串行算
12、法进行改进，挖掘其中的并行性质并加以利用，使得串行程序并行化；其二是对问题的本质重新审视，设计全新的并行算法。v 比较经典的算法有基于 Apriori算法、 DHP算法、DIC算法的并行算法和基于集群和格遍历的并行算法。 27 v CD算法的基本思想是 :在每一个处理机上都存储全局的候选项集和频繁项集，每一步计算时利用 Apriori算法计算出候选集在本地数据上的支持数，然后做一次同步，各处理机交换本地的候选项集的支持数，使得每个处理机的候选项集都得到全局支持数，从而得到全局频繁项集 Lk。1算法 CD(Count Distribution)28 DD算法更好地利用了全局的有效存储空间，它在每
13、个处理中存储不同的候选项集，这样在处理机数量增加时，一步可以增加计算的候选项集数量。每个处理机为了计算本地候选项集的全局支持数，必须既要计算候选项目集在本地的支持数，也要计算在所有其它的处理机上的支持数2.算法 DD(Data Distribution)29 CaD算法综合了 DD和 CD算法，以弥补它们各自的不足。 与 DD算法相似， CaD算法也是在各节点间分配候选集，但它有选择地对数据库进行分割，使每个节点可以根据本地的数据来处理它的候选集，减少处理器之间对数据和各候选集的依赖，从而减少同步，减少通信量。 3算法 CaD(Candidate Distribution)3010.5增量更新
14、挖掘算法v 10.5.1增量挖掘增量式关联规则更新技术应具备下列特性 :(1)规则应可随数据的变化而变化；(2)规则更新时应可避免再次处理旧数据，而可利用在先前发现过程中所获得的结果；(3)更新维护方法应尽可能独立于具体的发现算法。3110.5.2 FUP 算法算法的基本思想 :和 Apriori算法的框架一致的。每次循环对应一定长度的项集，循环从 1-项集开始，在以后每一次循环，分别发现 k-项集，直到没有更长的项集出现为止。而且，从第二次循环开始，每一次循环的候选项集都是根据前一次循环所发现的频繁项集生成的。在每一次循环中，根据增加的数据库 db对 L中的频繁 k-项集的支持度进行更新，以过滤出淘汰者 (losers)，这一过程中只要遍历增加的数据库 db。在遍历增加的数据库 db时，根据 db中的事务产生一组候选项集 Ck，并计算它们在数据库 db中的支持度。然后根据 D对候选项集 Ck中的项目的支持度进行更新，以发现新的频繁项集。3210.6多层关联规则挖掘 10.6.1 概念层次（ Conceptual Hierarchies ）数据库中的概
