论文研究-基于节点集Top-k频繁模式挖掘算法.pdf

所需积分/C币:20 2019-09-08 04:39:48 556KB .PDF
收藏 收藏
举报

频繁模式挖掘的模式数量通常过于巨大,在实际应用中只有少量的频繁模式被使用。Top-k频繁模式挖掘通过排列模式频数限制频繁模式的数量,有效提高了算法效率。提出了TPN(Top-k-Patterns based on Nodesets)算法,该算法使用了节点集的概念,将数据压缩于Poc-tree,通过Top-k-rank表重新计算最小支持度限制生成候选模式的数量。实验通过与ATFP,Top-k-FP-growth算法比较,证明该算法有较好的效率。
孙俊,张曦煌:基于节点集Top-k频繁模式挖掘算法 2017,53(6 103 例设事务数据库如表1所示,支持度∂为2,根据定低的那个点决症的。因此,在 Poc-tree中同一条路径中 义2得,1-频繁模八为{A,B,C,D,E},按照降序排列可支持度低的离根节点更远。例如,节点A是节点E的 得,F1={B,A,C,D,E},nul.根节点,将TD=1的祖先节点,那么2-频繁模式AE的节点集是E节点集 事务数据{ABF}根据算法剔除F1以外模式,并按賬F1的子集。由图1得AE=(1,5(1,5并且可得AE支持 顺序排列得{BAE},调用 insert(()函数,rot中不存在度为1+1=2。 名为B的孩子节点,因此需要创建一个rot的孩子节 定义8(k-频繁模式节集)设Ⅰ=il2…i是k-频繁模 点B, B Count=1,rot. Children-list= root. children-式,其中;是in+1的祖先节点,l1=i…ik节点集为 l+{B},此时,AE不为空,算法继续递归调用1,l2=i2i…k节点集为 Nodesets,,那么有 Inserto(AE,B,B中不存在名为A的孩子节点,因此,需 Nodesets= nodesets∩ Nodesets,2。图1AE={(1,5 要创建一个B的孩子节点A, A Count=1。 (1,6)},CE-1,5},因此,ACE-AE∩CE-{(1,5》,并 B. Children-list=B Children -list+Aj 且 SUP=1。 递归继续直到将所有项全部插入到Poc-uree树中 当所有事务全部插入树中对树进行前序遍历,为每个4TPN算法 节点添加一个唯一标示自已的序列号。结果如图1所示。4.1算法描述 root TPN算法提供了一个 top-k-rank表,由rank, support, patterns三列组成如表2所示,算法生成的k-频繁模式都 B:7 需要将k-频繁模式插入top-k-rank表,进行更新"。更新 原则为:保留k个最大支持度的所有模式,并按支持度 降序排列。下面简要地介绍算法的实现步骤 ):1.8 (1)扫描事务数据库,生成1-频繁模式L1,将L1插 C:2,10 入到top-k-rank表中,剔除超过rn=k的模式得到F1, C:2,4E:1,6|D:1,7 构建P oC-tree (2)根据前序遍历树节点扫描Poc-tree找到2-频繁 E:1,5 模式L2,更新Top- k-rank表,并且剔除L2中支持度小于 图1DB对应的Poc+tre Outrank=k的模式,得到F2 32节点集 (3)再次扫描 Poc-tree找到F2中的 Nodesets 设给定·个Poc-tree,其屮的每个节点信息N-info (4)根据定义8生成k-频繁模式,再次更新top- k-rank 可表示为( Node count,orde,例如,图1中前序为2的C表,得到Fk 节点可表示为(2,2)。 (5)如果Fk+1为空则算法结束,输出tp- k-rank表 定义6(节点集)炀繁模式i的节点集, Nodesets是否则,算法重复步槃(4) 由Poc-tree中i节点的所有 N-info组成。图1中,所有1 更新Iop-k-rank表如算法2所示 频繁模式的 Nodesets如下 算法2更新 Top-k-rank 输入 Top-k-rank表,F A:4,3)(2,9 输出Top- k-rank,F C:(2,2)(2,4)(2,10} R indicate row in Top-k-rank; 1 For each patters∈F,do D{(1,7(1,8 2 If patters. Sup<Ri Sup then E:{(1,5,(1,6) F←F-{atis}; 设频繁模式的 Nodesets为: 4 Elseif patters. Sup =RxSup then 5 R←RU{mes} 那么频繁模式的支持度为:a1+a2+…+an,如,频 6 EIs 繁模式C的 Nodesets为(2,2).(2,4),(2,0),那么可得 7 Create R +I in table Top-k-rank; 其支持度为2+2+2=6 R+1←R+U{aes}; 定义7(2-频繁模式的节点集)设和2是2个1-频 R order by R. Sup dESC 繁模式,存在i是i2的祖先节点,2对应的节点集是 Delete 的 Nodesets的子集。其理论依据是,同一条到根节点 的路径上的任意点组成的模式,其支持度是由支持度最 12 Endfor 1042017,53(6) Computer Engineering and4 pplications计算机工程与应用 13 Return Top-k-rank, F 35上ndif 例如表1所示给定数据库事务集,k=4,首先通过 36Ii2i2… i. Nodeset≠then 算法2找到F1={B,A,C,D,E},由算法1构建Poc-tree C=c+1 树如图1所示,前序遍历整棵树并通过算法2修剪后得 38F←FU{2… 到F2={BA,AC,BC,AE,BD,BE},连接得到ABC 9 Enlil AC∩BC-(2,4),ABE-AE∩BE-(1,6),通过算法2 40调用算法2 修剪得:F3={ABC},由于F4=C算法终止。F=F1 41 Endfor F2∪F3,最终结果如表2所示,F={B,A,C,D,F,BA 42 Endwhile AC,BC,AE,BD,BE,ABC}为最终挖掘出来的Topk 43 Return Top-k-rank 所有频繁模式 42复杂度分析 算法3TPN算法实现。 设事务数为n,记录平均长度为1,poc-tree的节点 输入事务数据库DB和k 个数为x,节点的深度为d,4为L1的长度,F为 输出top-k-rank表 生成的C频繁模式的个数 1F←Q 分步复杂度分析如下 2 F 初始化阶段时间复杂度为O1);扫描数据库DB生 3F2←C, Top-h-rank←; 成l并排序得到F时间复杂度为Oml+nlbl;构建 4扫描数据库B,找到1-频繁模式!1,调用算法2,得Poe-re时间复杂度为Oml2+x);遍历树节点找到2-频 到F1; 5调用Poc-tree算法构建Poc-tee 繁模式时间复杂度为O∑l); Top-k-rank表更新算法 6根据树的前序扫描Poc-tree,do 时间复杂度为O(F(k+1)b(k+1);生成c+1频繁模式 7N←当前访问的节点前序号 时间复杂度为OF;综上所述该算法的时间复杂度 ←N对应的模式 T(n) 9 For each M节点的祖先节点N,do T(n)=01)+O(+mlbl)+Ol2+x)+ x←N2对应的模式 Ifi∈F2 C>2)+OF、+1b(+1)+ i i.Supe-iriy Sup+N Node count Else (OF(2)+O(Fkk+1b(k+1) x2ySp← N. Nodecount F2←F2U{i 5实验对比 Endif 实验分別采用 mushroom、T104D100K两种不同 Endfor 的数据集进行实验,其中 mushroom为稠密数据集, 18 or each i;inf。do Tl0I4D100K为稀疏数据集。实验计算机为 Intel i5-3470 19调用算法2 CPU,主频为3.2GHz,操作系统为64位 Windows7,8GB 20 ii. nodesets←; 内存,在版本为Luna的 eclipse平台上,Java编写。表3 21 Endfor 给出了两种不同数据集的各参数指标。 22根据树的前序扫描Poc-tre,do 23Nd←当前访向节点前序号 表3各数据集 24i←Na对应的模式 Datasets size/KB Items Trans mushroom 558 25 For each N节点的祖先节点N2,do 8124 TIO4D100K 8 100000 261←N2对应的模式 27 If i, i∈F2then 图2所示为在 mushroom数据集上,三种算法分别在 28 iri Nodeset tii, Nodeset U Nd. -inf o 不同k值上的运行时间,黑色线是基于 Apriori的AhP 9 Endif 算法,如图所示运行时间随着k值增大而快速増长,这是 30 Endfor 由于AIFP算法需要多次扫描数据库,1O操作耗费大量 3! While F≠ 时间。蓝色线表示基于 FP-Growth的Top-算法,数据高 32 For each i;…iy∈F 度压缩于P-uree避免多次扫描数据增加的1O开销,运行 33I彐 ∈Fthe 时间全面低于ATFP,且运行时间随着k增加平稳上升 34tt2…iy- odeset=t… i Nodeset ni… i. nodeset 红色线表示TPN算法,运行时间在三种算法中最低。 孙俊,张曦煌:基于节点集Top-k频繁模式挖掘算法 2017,53(6 105 1200 TPN 据集上的效率。 10000 EATFP -Top-k-FP-Gruwth 28000 参考文献 6000 [1] Agrawal R, Srikant R Fast algorithm for mining associa 4000 品品品a tion ruleslci/ proceedings of the 20th International Con- 2000 ference on Very Large Data Base. San Francisco Morgan Kaufmann,1994:287-299 [2 Park J S, Chen M S, Yu P s An effective hash based algo 图2 mushroom运行时间 rithm for mining association rules[C]/SIGMOD Conference 1995:175-186 图3所示为在数据集T104D100K上三种算法的实31 Toivonen H Sampling large databases for association rules[C 际运行效果图,从图中依然可以看到,∧TFP算法效率最 Proc Very Large Data Bases Conf,1996: 134-145 差,因为其多次扫描数据库造成的资源消耗依然没有解[4]7akⅰMJ, Gouda k Fast vertical mining using diffsets[O]y 决,TPN和Top-k-FP- Growth运行时间差不多。 Proc of the 9th ACM SIGKDD Int Conf on Knowledge Discovery and Dala Mining, 2003 N000 - TPN [5] Han Pei J, Yin Y Mining frequent patterns without candi ATFp 6000 date generation[J].ACM SIGMOD Record, 2000, 29(2) Top-k-FP-Growth E4000 [6]杨蓓数据流topκ频繁模式挖掘算法研究[D]北京:北京 交通大学 2000F [7 Yu H, Iwahashi E, Yamana HTF 2 P-growth: an efficient algorithm for mining frequent patterns without any thresh olds[C]/Proc of Icdm, 2004 图3T104D100K运行时间 18 Deng Z H Fast mining Top-Rank-k frequent patterns by using node-lists[J]. Expert Systems with Applications, 2014 两组实验对比,各算法运行时间随着k值的增大而 41(4):1763-1768 增长。k值的增大,导致Poc-tce和top-k-rank表增大,在[」 Huynh-IhiLεQ,LeI,vB, et al. an efficient and effec 挖掘过程中这些是直接导致运行时间长短的重要因素。 tive algorithm for mining top-rank-k frequent patterns[J] 综合各算法在两种不同数据集上的表现可知,在 Expert Systems with Applications, 2015, 42: 156-164 稠密数据集上TN算法表现出优于ATFP和Top-k-FP[10 Deng Zhihong, Wang Zhonghui, Jiang Jiajian. A new algo ( Growth算法性能,表示所提出算法的可行性与优越性。 rithm for fast mining frequent itemsets using N-lists[J 根据稀硫数据集上各算法的表现,ATF依然表现为最糟 Science China: Information Sciences, 2012. 55(9): 200 糕,TPN算法和Top-k-FP- Growth有着差多的运行时间, 那是由于数据集的稀疏导致生成的 Poc-tree6和 FP-tree1l.富江,杜静陈彬,等一种基于混合搜索的高效TopK 较大,根据前序遍历寻找所有2频繁模式的时侯消耗较 最频繁模式挖捆算法[]国防科技大学学报,2009,31(2) 大的时间,在稀疏数据集上失去其优越性。囚此,所提 出的TFN算法在密集数据能够有效地提高算法效率。 [12 Vu L, Alaghband G A fast algorithm combining FP-tree and TID-list for frequent pattern mining[CyiProccedings of IEeE Conference on Information and Knowledge 6总结与展望 Engineering, 2011: 472-477 本文提岀了基于节点集的Top-k频繁模式挖掘算 [13 Deng 7H, Lv S I Fast mining frequent itemsets using 法,逦过在实验部分与当前主流Top-k挖掘算法的两组 Nodesets[J].Expert Systems with Applications, 2014 实验对比,TPN算法大大提高了挖掘效率,尤其在稠密数 41(10):4505-4512 据集上,其算法性能大大超过了主流算法,该算法在频[141 Quang TM, Oyanagi S, Yamazaki K Mining the k-most 繁模式挖掘具有良好的应用前景。但是该算法在稀疏 interesting frequent patterns sequentiallylCy/Lecture Notes 数据集上表现平平,效率依然较低,接下来需要找到有 in Computer Science, 2006, 4224: 620-628 效的剪枝策略在生成多项频繁模式过程中,减少侯选模[15] Nguyen G,LeT.√oB,eta! EIFDD: an efficient approach 式的生成,以及找到一种生成策略不需要历Poc-tree for erasable itemset mining of very dense datasets[JI 即可找到所有的2-频繁模式,进一步提高算法在稀疏数 Applied Intelligence, 2015, 43: 85-94

...展开详情
试读 5P 论文研究-基于节点集Top-k频繁模式挖掘算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744270 你的留言是对我莫大的支持
    2019-09-08
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于节点集Top-k频繁模式挖掘算法.pdf 20积分/C币 立即下载
    1/5
    论文研究-基于节点集Top-k频繁模式挖掘算法.pdf第1页
    论文研究-基于节点集Top-k频繁模式挖掘算法.pdf第2页

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

    20积分/C币 立即下载 >