《数据挖掘期中论》

QQ11华妊#力*孑课程设计报告（2013--2014年度第二学期）名称：数据仓库与挖掘论文院系：经济管理系 班级：信管1101 学生姓名：聂麟鹏 学号：201106040110指导教师：王立军 日期：2014年6月温磊老师在数据仓库与挖掘的课程中，为我们详细的讲述了关联规则的挖掘，并且介绍了两个算法，一种是Apriori算法，另一种是FP^ree算法，并且做了一系列的习题，经过了温磊老师的讲解后，我们通过算法对关联规则有了更深一步的了解，为了加深我们的印象，老师让我们在课下收集关于关联规则的其他算法，下而我将对几种其他的书中没有介绍过的算法进行详细的讲述。1、数据集划分算法Savasere设计了一个基于划分的算法。这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频集。产生频集的每一个循环结朿后，处理器之间进行通信来产生全局的候选项集。通常这里的通信过程是算法执行时间的主要瓶颈：而另一方而，每个独立的处理器生成频集的时间也是一个瓶颈。2、采样算法采样算法包括由Park等人提出的可调精度的挖掘算法、Toivonen提岀的Sampling算法等。Sampling算法是从数据库D中随机抽取一个可以调入内存的数据库子集D',然后求出数据库子集D中可能在数据库D中成立的所有规则，再用数据库D中剩余部分（D・Dr）来验证结果的正确性。它适用于挖掘准确性不太高而挖掘效率较髙的环境。采样算法很大程度上减少了扫描数据库的时间开销，但它最大的缺点就是可能产生数据扭曲导致结果不精确。如果频繁项集包含了数据库D中的所有频繁项集，则只需要扫描一次D。否则，为了减少这个问题带来的影响，可以使用更小的支持度阈值在随机样本上做第二次扫描数据库再次产生频繁项集，找出在第一次扫描中遗漏的频繁项集。通过对数据库多次扫描来减少频繁项集的遗漏。对于数据扭曲现象，有人讨论了反扭曲算法来挖掘关联规则，可以使得扫描数据集的次数少于2次。3、增量式更新算法增量式更新算法是利用已挖掘的关联规则在变化了的数据库或参数上发现新的关联规则、删除过时的关联规则来维护数据集更新的问题。目前大多数的增量式更新算法都是以Apriori算法为核心进行的改进与演化，包括D.W.Cheung等人提出的FUP和FUP2算法，冯玉才等人提出的IUA和PIUA算法，高峰等人提出的IUAR算法等等。FUP算法是Apriori算法的改进，也是解决增量更新问题的一种经典算法。FUP算法主要是针对在最小支持度和最小置信度不变的情况下，数据库DB被添加、删除或修改时，如何生成更新后的数据库的关联规则。它利用已挖掘得到的频繁项集信息来避免重复计算频繁项集支持数的时间开销来提高算法效率。FUP2算法同时考虑到增加数据库和修改、删除数据库的情况，比较适用于大量的增加数据库和少量的删除数据库的情况。IUA、PIUA算法都是主要考虑在最小支持度和最小巻信度发生变化而数据库DB不变时，如何生成DB中的关联规则。IUAR算法主要考虑在最小支持度和最小置信度和数据库DB同时发生变化时，如何生成更新后的关联规则。4、并行挖掘算法并行算法是利用同时执行的诸过程的集合相互作用和协调完成对给泄问题的求解。包括Agrawal等人提出的CD、DD、CaD算法，Park等人提出的PDM算法，Cheung等人提出的DMA和FDH算法等。CD算法运行在空闲的处理器上进行并行冗余计算以减小通信量，速度几乎可以达到线性加速比的速度。但它的缺点是通信量和候选频繁项集都比较大。DD算法通过吧候选集划分到各个处理器来克服CD算法的缺陷，然而DD算法由于数据移动方案效率较低导致通信负载较大、处理器件的交互模式易倒是处理器处于空闲状态、每一笔交易记录都根据多个哈希树进行处理导致冗余计算等缺点。CaD算法师徒通过划分数据库和候选集的办法来减少处理器之间的数据依赖性，使每个处理器可以独立地进行讣算。但它在划分候选集时要对整个的事务数据库进行划分并分配到每一个处理器节点中，从而消耗了大量的时间用于通信。PDH算法类似于CD算法，所有处理器含有相同的杂凑表和候选集。并行候选集生成的过程是通过每个处理器生成一个候选子项集，然后交换所有处理器上的子项集，然后交换所有处理器上的子项集生成全局候选集来实现。但是PDH算法对非大项集的项目和事务的物理剪枝要涉及大量磁盘的I/O操作。简单的介绍了四种算法后，下而我引用例子对增量式更新算法和并行挖掘算法进行详细的介绍。例1：设I=（il,i2,•“，im}是m个不同项目的集合.给世事务数据库D,对于项目集X^I在D中的支持数是指D中包含X的事务数，记为X.countD.X在D中的支持度是指D中包含X事务的百分比，记为X.supD.如果X的支持度不小于用户给过的最小支持度阈值s,则称X为频繁项目集，如果X包含I个项目，那么又称X为频繁I•项目集，频繁1・项目集简称频繁项目.挖掘岀所有频繁项目集是关联规则挖掘的核心问题，占据整个计算量的大部分。给左事务数据库D,事务数据集dl及d2（d2cD）.针对实际应用需求，关联规则的更新问题可以分为如下两种情况：（1）最小支持度s发生变化后如何生成D中的频繁项目集：（2）事务数据库D发生变化后如何生成最新事务数据库D+dl-d2中的频繁项目集.最小支持度S发生变化后关联规则增童式更新算法FIUA1：设旧的最小支持度为s,L1为D中频繁项目的集合，L为D中频繁项目集的集合.同样地，对于新的最小支持度s',L-1为D中频繁项目的集合，「为D中频繁项目集的集合.当最小支持度发生改变时,可分为两种情况：（1）s>s'： （2）s<s'输入：支持度为s时D中的所有频繁项目集L和FP-tree,新的支持度s'.

输出：支持度为s时D中的所有频繁项目集L^flFP-tree'.if（Ln1=50）then{调用AdjUstFP-1ree（FP-tree»Lnl）得到FP-tree1；调用FP-growth(FP-tree*1null,0,Lnl>Ll)：}//求Ln'调用FP・growth(FP-1ree\null,1,LI,Lnl)：//求L0‘L‘二LULnUL0‘事务数据库发生变化后关联规则的更新算法FIUA2：本节仅考虑当最小支持度不变，一个事务数据集d添加到事务数据库D中去时，如何生成事务数据库DUd中的频繁项目集.对此，我们将英分解为以下两个子问题：（1）找出D中不再生效或仍然生效的频繁项目集：（2）找出DUd中新的频繁项目集.对于前者，只需扫描d—次即可，由于D中的频繁项目集和d均较小，因此其运算量也较小，故下而的工作主要集中在第2个子问题上，即找出所有新的频繁项目集匚基本步骤：1、求d中的候选强频繁k•项目集Cdk；2、求候选新频繁k・项目集Cnk：3、求出Cnk中各项目集在D中的支持数；4、确立DUd中的所有新频繁k・项目集Lnk。一般情况下，经过1,2步的处理后，Cnk中项目集的个数是较少的，因此如何有效地利用已有的一切信息来求Cnk中各项目集在D中的支持数将是更新算法FIUA2的核心问题.对于D中的任何一条事务t,设tl=tALbt2二tCLnl,显然，tirit2=0.由FP-tree的构造原理可知，tl中的各项目必将同时出现在FP-tree的某唯一条路径pt,因此如果能将t2中的各项目添加到FP-tree的路径p上，那么t中的频繁项目将映射到FPtree的某唯一条路径上.由于Lnl中各项目在D中的支持度均小于LI中任意项目的支持度，因此直接调用AdjustFP-tree(FP-tree，Lnl)即可实现此功能，设调整后的模式树为P-tree,项目头表为Htable[1：q]，其中q二ILII+ILnlI.由此可见，求项目集在D中的支持数可以转换成求P-tree中包含此项目集的路径数，从而得到求PGCnk在D中的支持数算法，算法描述如下：Procedurecomputercount(P-1ree»p)//尸｛q,①，•“，cp｝按其支持数降序排列

搜索项目头表Htable[1：g]的项目名称域item-name.假设Htable[ql].item-name=ap：根据Htable[ql].head找到P-1ree中节点名称为中的节点ndl,nd2,•“，ndh：根据ndl,nd2,…，ndh及其前缀节点的父节点指针域找到包含中的所有路径Pl,P2,Ph；for(i=1：i垒h；i++)do如果路径Pi,包含d那么肉勺支持数增加ndi.count输入：事务数据库D及貝所有频繁项目集L：事务数据集d；最小支持度S；输岀：事务数据库DUd中的所有频繁项目集LDd.扫描d求D中的强频繁项目集LD并求岀d中的强频繁项目集Ldl及Lnl：

调用AdjustFP-tree(FP-tree,Lnl)得到模式树P-tree；Cd2=Apriori・gen(Lfdl)；for(k二2；Cd老：k++)do｛扫描d求Cdk中各项目集在d中的支持数并删除d中的非频繁项目集得到Cdk：Cnk二Cdk・Lk：

if（Cn=50）then（foreachp={4,0:a}^Cnk

调用computercount（P-1ree,p）；}

Ldk,={ceCdklc.SupDd^S}:

Cd（k+1）=Apriori-gen（Ldk）':

Lnk=（cGCnklc.SupDdS}；}//Lnk为新频繁k•项目集

LDd=ULnkULD“并行算法PFP-growth算法1、全局频繁项产生首先将事务数据集分配给务个可利用的处理机。每个处理机读取和分析大致相同数量的数据。设处理机的个数为p,结果所有数据被均匀划分为P等份。每个处理机对分配到的事务进行读取和分析，统计局部频繁项(localfrequentitem)。设全局频繁阈值为g则局部频繁阈值设为§ocal二"p。这个过程如表1所示。表1事务数据分配TIDTransactionProcessorsTIDTransactionProcessors1ABCDEProcessor02FBDEG3BDAEG4ABFGDProcessor15BFDGK6ABFGD7ARMK0Processor28AFGAD9ABFM0•—••■■■■••■■•当局部频繁项产生后，冬处理机将局部频繁项表示为一字符串。例如对processor0,它将频繁项表示为A:2IB:3IC:1ID:3^:3IF:1I'：按照图1所示的数据传输策略，一些处理机将自己的字符串传给另外一些处理机。当一个处理机收到从另外处理机发过来的频繁项字符串后，将收到的字符串和自身的字符串合并为一个字符串作为自己的字符串，并按图1所示策略继续传给另外的处理机。对processor0.它收到processor1发给它的字符串上2IB:3ID:3IF:3IG:3IK:11'：并将这个收到的字符串与自己的串盘:2IB:3IC:1ID:3IE:3IF:1I'进行合并。合并后的新字符串为比4IB:6IC:1ID:6IE:3IF:4IG:3IK:1I'：直到最后processor0获得最后字符串，这个字符串就代表了所有局部频繁项及英支持度的汇总。整个传输不超过log2q个步骤，接着processor0通过删除非频繁的项并按支持度排序获得全局的频繁项(globalfrequentitem)。processor0同样以字符串的形式表示全局频繁项，并将这个字符串广播给所有的处理机。2、局部频繁项集挖掘在收到全局频繁项字符串后，每个处理机对所分配的事务数据开始挖掘局部频繁项集。挖掘过程类似于FP-growthoFP-growth*只产生FP-1ree一次，并递归地产生独立头表。由于原FP-growth需要在每次创建FP-tree前需对局部频繁项排序，形成局部降序，然后按局部降序构造，所以它不能保证所有挖掘出的频繁项集中的频繁项以相同的顺序排列oFP-growth*区别于FP-growth的一个特点即是所有的频繁项集中的频繁项按严格相同的顺序排列。而这个顺序即是全局降序，即FP-growth*所有频繁子树的构造都是按全局降序构造的。而FP-growth是建立在FP-growth*的基础上，这个全局降序立义为并行算法第一阶段产生的全局频繁项的降序。由于所有的频繁项按相同的顺序排列，所有的频繁项集就能构造出一棵树，叫频繁结果树'这个性质用来压缩挖掘岀的频繁项集结果。算法：频繁结果树生算法PFP-growth输入：频繁树,Tfptree;HeadertableH(head_table,Minimumsupportthreshold^输出:结果树T(resulttree)方法:调用PFP_growth(Tfp_tree,Hhead_table»nul1,Tresulttree);PFP-growth(Tree_fptree.headerTableHhead^table,ItemSetIpostfix,Tree*Tresult-1ree){intsize=Theadtable—GetSize();For(intI=size-1;i=0;i--){Heade