还剩5页未读,继续阅读
文本内容:
课程设计报告2013--2014年度第二学期名称数据仓库与挖掘论文院系经济管理系班级信管1101学生姓名聂麟鹏学号201106040110指导教师___日期2014年6月温磊老师在数据仓库与挖掘的课程中,为我们详细的讲述了关联规则的挖掘,并且介绍了两个算法,一种是Apriori算法,另一种是FP—Tree算法,并且做了一系列的习题,经过了温磊老师的讲解后,我们通过算法对关联规则有了更深一步的了解,为了加深我们的印象,老师让我们在课下收集关于关联规则的其他算法,下面我将对几种其他的书中没有介绍过的算法进行详细的讲述
1、数据集划分算法S__asere设计了一个基于划分的算法这个算法先把数据库从逻辑上分成几个互不相交的块,每次单独考虑一个分块并对它生成所有的频集,然后把产生的频__并,用来生成所有可能的频集,最后计算这些项集的支持度这里分块的大小选择要使得每个分块可以被放入主存,每个阶段只需被扫描一次而算法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的该算法是可以高度并行的,可以把每一分块分别分配给某一个处理器生成频集产生频集的每一个循环结束后,处理器之间进行通信来产生全局的候选k-项集通常这里的通信过程是算法执行时间的主要瓶颈;而另一方面,每个__的处理器生成频集的时间也是一个瓶颈
2、采样算法采样算法包括由Park等人提出的可调精度的挖掘算法、Toivonen提出的Sampling算法等Sampling算法是从数据库D中随机抽取一个可以调入内存的数据库子集D’,然后求出数据库子集D’中可能在数据库D中成立的所有规则,再用数据库D中剩余部分(D-D’)来验证结果的正确性它适用于挖掘准确性不太高而挖掘效率较高的环境采样算法很大程度上减少了扫描数据库的时间开销,但它最大的缺点就是可能产生数据扭曲导致结果不精确如果频繁项集包含了数据库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等人提出的D__和FDM算法等CD算法运行在空闲的处理器上进行并行冗余计算以减小通信量,速度几乎可以达到线性加速比的速度但它的缺点是通信量和候选频繁项集都比较大DD算法通过吧候选集划分到各个处理器来克服CD算法的缺陷,然而DD算法由于数据__方案效率较低导致通信负载较大、处理器件的交互模式易倒是处理器处于空闲状态、每一笔交易记录都根据多个哈希树进行处理导致冗余计算等缺点CaD算法师徒通过划分数据库和候选集的办法来减少处理器之间的数据依赖性,使每个处理器可以__地进行计算但它在划分候选集时要对整个的事务数据库进行划分并分配到每一个处理器节点中,从而消耗了大量的时间用于通信PDM算法类似于CD算法,所有处理器含有相同的杂凑表和候选集并行候选集生成的过程是通过每个处理器生成一个候选子项集,然后交换所有处理器上的子项集,然后交换所有处理器上的子项集生成全局候选集来实现但是PDM算法对非大项集的项目和事务的物理剪枝要涉及大量磁盘的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-项目集,频繁l-项目集简称频繁项目.挖掘出所有频繁项目集是关联规则挖掘的核心问题,占据整个计算量的大部分给定事务数据库D,事务数据集dl及d2(d2cD).针对实际应用需求,关联规则的更新问题可以分为如下两种情况(l)最小支持度s发生变化后如何生成D中的频繁项目集;
(2)事务数据库D发生变化后如何生成最新事务数据库D+dl-d2中的频繁项目集.最小支持度S发生变化后关联规则增量式更新算法FIUA1设旧的最小支持度为s,Ll为D中频繁项目的__,L为D中频繁项目集的__.同样地,对于新的最小支持度s,Ll为D中频繁项目的__,L为D中频繁项目集的__.当最小支持度发生改变时,可分为两种情况(l)ss;
(2)ss输入支持度为s时D中的所有频繁项目集L和FP-tree,新的支持度s’.输出支持度为s’时D中的所有频繁项目集L’和FP-tree.if(Ln1≠Ø)then{调用AdjUstFP-treeFP-tree,Ln1)得到FP-tree;调用FP-growth(FP-tree,null,0,Ln1,L’1);}//求Ln’调用FP-growth(FP-tree’,null,1,L1,Ln1);//求LO’L’=LULn’ULO’事务数据库发生变化后关联规则的更新算法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,设t1=t∩L1,t2=t∩Ln1,显然,t1∩t2=Ø.由FP-tree的构造原理可知,t1中的各项目必将同时出现在FP-tree的某唯一条路径p上,因此如果能将t2中的各项目添加到FP-tree的路径p上,那么t中的频繁项目将映射到FPtree的某唯一条路径上.由于Ln1中各项目在D中的支持度均小于L1中任意项目的支持度,因此直接调用AdjustFP-tree(FP-tree,Ln1)即可实现此功能,设调整后的模式树为P-tree,项目头表为Htable[1q],其中q=IL1I+ILn1I.由此可见,求项目集在D中的支持数可以转换成求P-tree中包含此项目集的路径数,从而得到求ρ∈Cnk在D中的支持数算法,算法描述如下Pro__durecomputercount(P-tree,ρ)//ρ={α1,α2,⋯,αp}按其支持数降序排列搜索项目头表Htable[1g]的项目名称域item-name,假设Htable[q1].item-name=αp;根据Htable[q1].head找到P-tree中节点名称为αp的节点nd1,nd2,⋯,ndh;根据nd1,nd2,⋯,ndh及其前缀节点的父节点指针域找到包含αp的所有路径P1,P2,⋯,Ph;for(i=1;i≦h;i++)do如果路径Pi包含ρ,那么ρ的支持数增加ndi.count输入事务数据库D及其所有频繁项目集L;事务数据集d;最小支持度S;输出事务数据库DUd中的所有频繁项目集LDd.扫描d求D中的强频繁项目集LD’并求出d中的强频繁1-项目集Ld1’及Ln1;调用AdjustFP-tree(FP-tree,Ln1)得到模式树P-tree;Cd2=Apriori-gen(Lfd1);for(k=2;Cd≠Ø;k++)do{扫描d求Cdk中各项目集在d中的支持数并删除d中的非频繁项目集得到Cdk;Cnk=Cdk-Lk;if(Cn≠Ø)then{foreachρ={α1,α2,⋯,αt}∈Cnk调用computercount(P-tree,ρ);}Ldk’={c∈Cdk|c.SupDd≧S};Cd(k+1)=Apriori-gen(Ldk‘);Lnk={c∈Cnk|c.SupDd≧S};}//Lnk为新频繁k-项目集LDd=∪Lnk∪LD‘并行算法PFP-growth算法
1、全局频繁项产生首先将事务数据集分配给各个可利用的处理机每个处理机读取和分析大致相同数量的数据设处理机的个数为p,结果所有数据被均匀划分为p等份每个处理机对分配到的事务进行读取和分析,___部频繁项(localfrequentitem)设全局频繁阈值为ξ,则局部频繁阈值设为ξlocal=ξ/p这个过程如表1所示表1事务数据分配TIDTransactionPro__ssors1ABCDEPro__ssor02FBDEG3BDAEG4ABFGDPro__ssor15BFDGK6ABFGD7ARMKOPro__ssor28AFGAD9ABFMO……………………当局部频繁项产生后,各处理机将局部频繁项表示为一字符串例如对pro__ssor0,它将频繁项表示为“A:2|B:3|C:1|D:3|E:3|F:1|”按照图1所示的数据传输策略,一些处理机将自己的字符串传给另外一些处理机当一个处理机收到从另外处理机发过来的频繁项字符串后,将收到的字符串和自身的字符串合并为一个字符串作为自己的字符串,并按图1所示策略继续传给另外的处理机对pro__ssor0,它收到pro__ssor1发给它的字符串“A:2|B:3|D:3|F:3|G:3|K:1|”并将这个收到的字符串与自己的串“A:2|B:3|C:1|D:3|E:3|F:1|”进行合并合并后的新字符串为“A:4|B:6|C:1|D:6|E:3|F:4|G:3|K:1|”直到最后pro__ssor0获得最后字符串,这个字符串就代表了所有局部频繁项及其支持度的汇总整个传输不超过log2q个步骤,接着pro__ssor0通过删除非频繁的项并按支持度排序获得全局的频繁项(globalfrequentitem)pro__ssor0同样以字符串的形式表示全局频繁项,并将这个字符串广播给所有的处理机
2、局部频繁项集挖掘在收到全局频繁项字符串后,每个处理机对所分配的事务数据开始挖掘局部频繁项集挖掘过程类似于FP-growthFP-growth*只产生FP-tree一次,并递归__生__头表由于原FP-growth需要在每次创建FP-tree前需对局部频繁项排序,形成局部降序,然后按局部降序构造,所以它不能保证所有挖掘出的频繁项集中的频繁项以相同的顺序排列FP-growth*区别于FP-growth的一个特点即是所有的频繁项集中的频繁项按严格相同的顺序排列而这个顺序即是全局降序,即FP-growth*所有频繁子树的构造都是按全局降序构造的而FP-growth是建立在FP-growth*的基础上,这个全局降序定义为并行算法第一阶段产生的全局频繁项的降序由于所有的频繁项按相同的顺序排列,所有的频繁项集就能构造出一棵树,叫“频繁结果树”这个性质用来压缩挖掘出的频繁项集结果算法频繁结果树生算法PFP-growth输入频繁树Tfptree;HeadertableHhead_tableMinimumsupportthresholdξ输出结果树Tresulttree方法调用PFP_growthTfp_treeHhead_tablenullTresulttree;PFP-growthTree_fptreeheaderTableHhead_tableItemSetIpostfixTree*Tresult-tree{intsize=Theadtable→GetSize;ForintI=size–1;i≧0;i--{HeaderTableItemHcur-head-item=Hhead-table→GetAti;IfHcur-head-item→supξcontinue;ItemsetIcur-itemset=Hcur-head-item→supTresult-tree;HeaderTablehnewheadtable=CreateHeadTableTfp-treeHhead-tablei;PFP_growthTfp-treeHnew-head-tableIcur-itemset;}}PFP-growth算法的一个明显特征是作为参数的后缀项集Ipostfix引入Ipostfix的目的是为在当前迭代过程中产生的频繁项集结果
3、全局频繁项集产生在这个阶段,算法将对频繁结果树进行合并通过合并接收到的字符串和自己的字符串产生一个新的字符串这种合并过程进行到最后,然后pro__ssor0得到最终频繁结果树字符串然后pro__ssor0将这个字符串转换为通常的频繁项集形式,作为最后结果输出,算法到此结束以上算法参考了一些百度百科和百度文库的资料,还有上述的几个例子我查阅了校网中的一些学位论文,经历了这次学习,我对关联规则以及相关算法有了更深一步的了解,希望在温磊老师的指导和学习下,能够好好的完成数据仓库与挖掘这门课程,并且日后在工作中将它用于实践中去。