论文研究-一种多关系频繁模式挖掘算法.pdf

所需积分/C币:5 2019-07-22 20:33:31 268KB .PDF
收藏 收藏
举报

传统数据挖掘算法在处理多表时,需要物理连接,存在效率不高的问题。为了解决这一问题,提出了一种多关系频繁模式挖掘算法。该算法利用元组ID传播的思想,使多表间无须物理连接,就可以直接挖掘频繁模式。实验表明,此算法具有较高的效率。
第9期 邓左祥,等;一种多关系频繁模式挖掘算法 3287 INset(C)中有某个值,设为d,m且B表中D为1的元组的属 算法:在多关系中挖掘频繁项集 性IDse(C)中也有d的话,那么就可以为2-项集{X,Y的支持 输入:一个多关系数据库D1,文持度计数阈值。 度计数加1。因为A与C表进行连接操作后,由 INset(C)知,A 输出:D1中的频繁项集。 方法 表ⅢD为1的元组可以与C表Ⅲ为d的元组连接,而B表I D2=传播元组ID(D1); 为1的元组可以与C表I为d的元组连接,从而A表中主键 L1=挖1项集(D2,支持庋计数阈值); 为1的元组可以与B表中的主键为1的元组连接,连接后的元 ifl1≠ Othen L2=挖2-项集(L1,支持度计数网值) 组必然包含2-项集{X,Y。 for(k=3;L1≠;K++) 攴持度计数不小于阈值的候选2-项集都是2-频繁项集。 I CK= apriori-gen(Ih-1 在保冇2-频繁项集时,类似于1-频繁项集,也需夏保存以下 for each c 三类 项集H1,X2∴…,X←X的(k-1)个子(k-1)-频繁项集 (a)该项集的名称,因为要区分出项所在的表的名称,所 for cach IDEX.D,., D, cXk. D ifm1,…,ID的来自相同的表的ID值都相等then 以应该保存为“表.属性(值),表.属性(值)”。 (b)该项集的持度计数。 iX.cun>=支持度计数阈值ten (c)包含该项集的所有元组ID集的值,对于任意一个产 把x加入L,存储X. count,X.ID; 生该项集一个支持度的情况,无论是单表项集,还是多表项集, 都保存为“表⑩(值),表.D(值)”。例如,假设一个出A表 return L=ULy rocedure ID为1的元组(包含项X),以及由B表D为1的元组(包含 传播元组DD(D) for each关系R1FD 项Y),它们进行连接操作后,包含2-项集{x,Y},刘于这种产 for cach关系R3cD 生2-项集{X,Y}的一个支持度的情况,把元组I集的值记为 fR2的主键在R1中作为外键then A.I(1),B.ID(1)”。 把R1的ID传播到R e)在发现了2-频繁项集后,就要找出候选3-项集。利用 Apriori算法的性质—频繁项集的所有非空子集乜必须是频 Procedure挖1-顶集(D,支持度计数值) 繁的。囚此,候选3-项集的所有子集都必须是频繁项集。根据 for each关系R∈D for each属性A∈R 这一点,产生候选3-项集。为候选3项集计数的方法与前面 fA≠主键、外键、 INset ther 的1-项集和2项集有所不同,不再通过扫措数据库来计数,而 为A上的每一个不同的项X进行计数 是通过如下方法来为候选3项集计数 ifX. count>=支持度计数國值then 为候选3-项集计数的方法是:假设有三个项X、Y、Z,产生 把X加入1-繁项集1,存储X. count、X. 了三个2-频繁项集,分别设为{x,Y}、{x,Z}、{Y,Z},包含它 return 们的所有元红ID集的值分别为{x,Y}.ID、{X,Z}.ID、{Y,Z Procedure挖2-项集(l1,支持度计数阈值) ID。分别从{X,Y}.ID、X,Z}.ID、{Y,Z}.I中各提取一个元 for each l-繁项集xcL1 组DD集,分别设为D、ID2、ID3。北较I1、ID2、ID3,如果在 for each1-频繁项集Y∈L1 合并X、Y,把{X,Y}加人候选2-项集C2,R1←X所在表, ID1、ID2、ID3中,来白同一个表的D值都相同的话,那么可以R2+y所在表 为侯选3-项集{X,y,Z的计数加1,且产生该{X,y,Z}的元组 ID集的值,就是I1、ID2、D的并集。循环地比较{X,FID 比较X.ID和Y.ID,相同的ID个数为项集{X,Y的计数 X,}.ID、Y,Z.ID中的各个元组m集,就可以知道{X,y, Z}的支持度计数。 ifR1、R2中的某一方包含另一方的 ID set then 举一个计数方法的例子,并说明理由。假设有三个表A 取项的ID对应的元组的 INset值的并集,与另一个项的ID 进行比较,相同的1D个数为项集|X,Y的计数 B,C,有个元组t1、t2、t3,t属于A,标志为ID1,t2属于B,标志 ifR1、R2中都包含某个第三方表的 INset then 为ID2,t3属于C,标志为ID3,包含项X,包含项Y,t包含Z 取X.ID和Y.ID对应的元组的IDst值的并集,对两并集进 假设有三个2-频繁项集X,H},X,z},Y,Z}。其中X,Y行比较,相同的ID个数为项集|X,Y|的计数 ID中包含(D1,DD2)(也就是说,1和t2连接在一起后,产生了 if{x,Y}, count>=支持度计数阈值then A,Y的个支持度),X,Z.D中包含(ID1,ID3),Y,∠ 把X,Ⅳ加入2-频繁项集L2,存储{X,Y|.cunl、X,Y|.ID ID中包含(ID,)。如果从X,Y}.ID、{X,∠}.ID、Y,Z return L D中各提取的一个元组集分別是(ID1,I,),(ID),1D3), Prucedure apriori_gen( Lui) (DD2,ID3),由于它们来自同一个表的I值相等,所以这种情 for each项集l1=Lh for each项集l2∈L1 况可以为{X,Y,Z}的计数加1。因为t、t2、t3是可以彼此互相 if(1[1]=2[1])∧…A(l1[k-1]<l2[k-1])then 迕接的,当A、B、C三个表进行连接后,1、t2、必然可以连接成 Ic=IDAl 个元组,这个元组就包含{X,Y,Z},产生{X,Y,Z}的一个支 if has_infrequent_subset(c, L-1 )then 持度。 删除c; 支持度计数不小于阈值的候选3-项集都是3-频繁项集 把c加入C; 需要保存的3-频繁项集的信息与前面2-频繁项集是类似的 return Ck f)4-频繁项集,以及项的个数大于4的频繁项集的挖掘方 for each( k-1)-cubeet s e c 法,与3-频繁项集类似 if s E Ly-I then return Lrue 算法的伪码如下 return false 3288 计算机应用研究 对三个表都进行裁剪.使三个表分别都保留50、100、200、 4实验 300400、500个元组),作为算法的输入,得出它们的运行 本文使用 PKDD CUP199中的包含八个表的金融数据库时间。 (httb://ip.wse.cz/pkd99/ Challenge/ chall..ht),作为实验数 结果:运行时间变化如图3所示。从图3可以看出,随着 据集,做两个实验。 每张表的元纽的个数的不断增加,运行时间不断增加,并且增 实验环境 长速度越来越快 操作系统为 Windows XP Professional;内存为52MB;CPL 20 为 Pentium43.0GIz;平台为 Borland c++ Builder6.0。 10 实验1 200 400 600 目的:比较多关系频繁模式挖掘算法和物理连接多表并采 元组个数 用传统的单表频繁模式挖掘算法的运行时间。 图3元组个数变化下的时间变化图 过程:从数据集中选择两个表( loan, account),进行裁剪,5结束语 保留200个元组;设定支持度阈值为4%,也就是支持度计数 阈值为200×4%=8。 由丁传统的数据挖掘方法在处理多关系频繁模式挖掘时, 结果:运行时间对比如表1所示。从实验结果可以看到,不得不首先通过物理连接的方法把多表集成到单表,效率低 本文提出的算法有较高的效率。 而基于IP的多关系数据挖掘算法也存在效率低、叮扩展性差 表1两种方法的运行时间比较 的问题。本文提出了一种多关系频繁模式挖掘算法,其利用了 行时间/s 元组ID传播的思想,在多关系上建立虚连接,可以直接在多关 多关系频繁模式挖掘算法 传统方法 12.412 系上挖掘频繁项集。实验表明,本文提出的算法具有较高的效 实验2 率。今后,可以继续借助元组⑩传播的思想,对多关系数据挖 目的:分别在表的个数、元组个数、支持度变化的情况下,掘的各个任务作进一步研究。 比较运行时间的变化。 参考文献 过程:保持元组个数不变(对八个表都进行裁剪,使每个[1 DZEROSKI S. LA VRAC N. Relational data mining[ m]. Berlin 表都只保留200个元组)、支持度不变(设定支持度阈值为 springer, 2001 4%,也就是支持度计数网值为200×4%=8),改变表的个数2] AGRAWAL R, SRIKANT R. Fast algorithms for mining association (分别从八个表中选择其中的两个表(loan、 ccount)、四个表 rules[ C]//Proc of International Conference on Very Large data Ba- (loan、 account、 order、 transaction)、六个表(loan、 account、 order、 [s.n.],1994:487-499 transaction、 district, disposition),以及全部八个表),作为算法的3] KAMBER M, HAN Jia-wei, CHIANG J Y. Metarule-guided mining 输入,得出它们的运行时间。 of multi-dimensional association rules using data cubes[C]// Proc of 结果:运行时间变化如图1所示。从图1可以看到,随着 International Conference on Know ledge Discovery and Data Ming. New 表的个数的不断增加,运行时间不断增加,并且增长速度越来 port Beach:s.n.],1997:207-210 越快。 [4 LAVRAC N, DZEROSKI S. Inductive logic programming: techniques and applications[ M]. New York: Fllis Horwood, 1994 [5] DE.. L. Mining association rules in multiple relations [C]// Proc of the 7th International Workshop on Inductive Logic Program 表的个数 ming. Berlin: Springer, 1997: 125-132 图1表的个数变化下的时间变化图 [6 DEHAPE. L. Frequent pattern discovery in first-order logic[D]. Bel- ginm: Katholieke University Leuven, 1998 过程:保持表的个数不变(选择loan, account两个表) [7 NIJSSEN S, KOK J. Faster association rules for multiple re lations 组个数不变(对两个表都进行裁剪,使每个表都只保留500个 [Cl//Proc of the 17 th International Conference an Artificial Intelli 元组),改变支持度(设定三个支持度阈值2%、4%6%),作为 gence.2001:891-896 算法的输入,得出它们的运行时间。 [8 YIN Xiao-xin, HAN Jia-wei, YANG Jiong, et al. Cross Mine: effi 结果:运行时间变化如图2所示。从图2可以看出,随着 cient classification across multiple database relations[ C]//Proc of In 攴持度阈值的不断增加,运行时间不断下降。 ternational Conference on Data Engineering. Boston: [sn1,2004 [9 YIN Xiao-xin, HAN Jia-wei, YU P S. Cross-relational clustering with user's guidance[ C1//Proc of the 1l th ACM SIGKDD Conference an Know ledge Discovery in Data Mining. Chicago: s n.], 2005 支持度/% 图2支持度变化下的时间变化图 [10]郭景峰,边伟峰,霍峥,等.一种基于用户指导的多关系关联规则 挖掘算法[J.计算机研究与发展,2007,44(增刊):22-26 过程:保持表的个数不变(选择loa、 account、 district三个[11 hAN Jia-wei, KAMBER M.数据挖掘;概念与技术[M].范明,孟 表)、支持庋不变(设定支持度阈值为4%),改变元组的个数 小峰,译.2版,北京:机械工业出版社,2007:164-165

...展开详情
试读 4P 论文研究-一种多关系频繁模式挖掘算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    上传资源赚积分,得勋章
    最新推荐
    论文研究-一种多关系频繁模式挖掘算法.pdf 5积分/C币 立即下载
    1/4
    论文研究-一种多关系频繁模式挖掘算法.pdf第1页
    论文研究-一种多关系频繁模式挖掘算法.pdf第2页

    试读已结束,剩余2页未读...

    5积分/C币 立即下载 >