论文研究-一种适应大型数据库的多支持度关联规则算法.pdf

所需积分/C币:9 2019-09-07 22:22:48 729KB .PDF
收藏 收藏
举报

传统的序列模式挖掘算法应用在生物序列上有其局限性,根据生物序列的特点,提出了基于相邻频繁模式段的模式挖掘算法-JPS。首先产生相邻频繁模式段,然后对这些频繁模式段进行组合,产生新的频繁模式。通过实验分析,该方法在相似性很强的序列数据库中比传统的PrefixSpan算法效率高。通过对真实的蛋白质序列家族库的处理,证明该算法能有效处理生物序列数据。
2008,44(2) Computer Engineering and Applications计算机工程与应用 序列个数大于 Minisub,那么PQ就是频繁模式 实验的硬件环境是华硕笔记本电脑: Pentium M1.6G处 证明如果P和Q共同出现的序列个数大于 Minisup,要理器,512M内存,微软 Windows XP操作系统。 么QP频繁,要么PQ频繁。因为Q最后出现的位置大于等于4.1与 PrefixSpan算法对比 P,因此PQ频繁。 PrefixSpan算法有两个主要特点:(1)不产生候选集,节约 下面,将分以下几步产生频繁模式 内存空间;(2)产生的投影数据库随着频繁模式长度的增加而 (1)依次产生的相邻频繁模式段的投影数据库,并且在递减,大大提高了挖掘效率。但是其有一个很突出的缺点,即产 每条序列中都标记该频繁模式段的偏移位置; 生大量投影数据库,在处理这些投影数据库的过程中,浪费了 (2)将P与所有频繁模式段进行组合,根据定理3,在频繁大量的资源,同时也影响了算法执行的效率。 模式段Q和P共同出现的序列中,Q在序列中最后出现的位 通过实验发现, PrefixSpan算法在处理相似序列时,效率很 置大于等于P在该序列中的偏移量,如果满足上述条件的序低,例如处理的序列完全相同。为了测试 PSrefix Span算法处理 列个数大于 Minisup,那么P*Q就是频繁模式; 相似序列的效率,使用一个人工序列数据库。该数据库由三条 (3)按照步骤(2)依次产生更长的频繁模式,直到没有新的序列组成,每条序列的长度为25,并且这三条序列完全相同 频繁模式产生为止。 如表4所示。 例2还按照例1的数据对上述过程进行举例说明。 表4一个人工序列数据库 (1)首先对频繁模式段ab进行处理,ab在序列1中的偏 ID 移量为2,在序列2中的偏移量为2。将模式段ab和其进行合 SI MADYLISGGTSYVPDDGLTAQQLFN 并,由于ab在序列1和序列2中的最大出现位置都为0,小于 S2 MADYLISGGTSY VPDDGLTAQQLFN 2,因此abab模式不频繁。将模式段ac和ab进行合并,ac在序 S3 MADYLISGGTSY VPDDGLTAQQLFN 列1中的最后出现位置为2,等于ab在序列1中的偏移位置, 设定 Minisub=1, Minilen=25。也就是说需要产生的频繁序 c在序列2中的最后出现位置为3,大于a在序列2中的偏列为: MADYLISGGTSYVPDDGLTAQQLFN。通过对上述序列数 移位置,因此,根据定理3可以得到abac频繁。 据库进行实验,得出的数据为: Prefix Span算法在处理的时间为 (2)然后计算abac在各个序列中的偏移位置,在序列1中30343ms,所产生的投影数据库总数高达13176079个。用本 4,在序列2中为5。此时,没有一个相邻频繁模式段能和文提出的算法所运行的时间为7375ms。由此可见,在处理相 abac组成频繁模式。 似性比较大的序列时,JPS优于 Prefix Span, Prefix Span算法的 (3)依次类推,直到所有频繁模式产生为止。ahac(2),效率不是很高,并且会产生大量的投影数据库。 abad(2), abacda( 2), abcd( 2), abcda(2 ), abda( 2), bacd(2 4.2蛋白质序列应用 33算法分析 从PIR(htp:/ pir. georgetown. edu/piww)上面下载到一个 在算法第一部分产生连续频繁模式段时,采用的是改进后家族的蛋白质序列数据库,其 PIRSF ID为:PRSF0130。该 的 Prefix span算法生成频繁项在生成频繁项时,只产生相邻家族由52条蛋白质序列组成 高,具体数据对比见第5章实验分析。使用该方法生成频繁项度分别为02、0.304.0.506时算法运行的时间S时,支持 的频繁项,因此相对于原始的 PrefixSpan算法,执行效率人人提 图1、图2、图3分别是在 Minilen分别为3、4、5时,支持 集有以下优点:(1)不需要产生候选集,大量节约了存储空间; Minilen=3 (2)随着投影数据库的逐渐产生,数据库的大小递减,缩小频繁 90219 项的搜索范围。原始 PrifiX Span算法有其致命的缺点:产生大量 的投影数据库。改进后的 PrefixSpan算法由于只需要产生相邻 回归 27484 的频繁项集,因此,在投影数据库数量的产生上面大大小于原 9297 57182500 始算法,使得算法执行效率大大提高 0.3 0.5 0.6 算法的第二部分将第一部分产生的相邻频繁模式段进行 支持度 组合,产生长的频繁模式。为了减少对原始数据库的扫描,设计 图1 Minlen为3时不同支持度的运行情况 了一个数据结构,用来记录第一部分产生的频繁模式段在每条 Minilen=5 序列中最后产生的位置。使用该方法可以避免对原始数据库进 31204 行反复的扫描,只需找到频繁项集的在每条序列中的偏移量, 便可产生出新的频繁模式。但是,如果相邻频繁模式段很多,并 12656 且原始序列数据库很大的情况下,存储频繁模式段在每条序列 17501250 中最后位置需要占用大量内存 0.2 0.4 0.5 0.6 支持度 4实验分析 图2 Minlen为5时不同支持度的运行情况 Prefix Span算法是非常著名的序列频繁模式挖掘算法。首 通过3幅图,可以看到,随着最小支持度的增加,算法运行 先通过对一个人工特殊序列数据库的处理,分析了 Prefix Span时间越来越少。在同一个支持度下,运行时间随着支持度的增 算法处理相似序列时的弊端并和本文提出的算法在运行时间加而减少。但在图3中,支持度为0.5和06的运行时间都支 上进行了比对然后应用本文提出的算法对一个真实的蛋白质持度为04的运行时间还大。进行了多次实验,得到了相同的 序列数据库进行了频繁集挖掘,给出了算法的运行效果。 数据。传统所认为的随着支持度的增加,运行时间必然减少的 王淼,尚学群,薛贺:基于相邻模式段组合的生物序列模式挖掘算法 2008,44(2)193 规则在此是站不住脚的,因此,支持度并不是和运行时间一定[2] Needleman S D, Wunsch C d. A general method applicable to the 成反比。 search for similarities in the amino acid sequence of two proteins[JI Minilen=7 Journal of Molecular Biology, 1970, 48: 443-453 [3 Smith T F, Waterman M S Identification of common molecular sub 6047 sequences[JJ Mol Bio, 1981, 147: 195-197 回 4 Lipman D J, Pearson W R Rapid and sensitive protein similarity 2172 10941547 1141 searches[J]. Science, 1985, 227: 1435-1441 5 Lipman D J, Pearson W R Improved tools for biological sequence 0.3 0.4 0.5 0.6 comparison[J]. Proc Narl Acad Sci, 1988: 2444-2448 支持度 [6 Altschul S F, Gish W, Miller W, et al. Basic local alignment search 图3 Minlen为7时不同攴持度的运行情况 tool[J.Journal of Molecular Biology, 1990, 215: 403-410 [7 Agrawal R, Srikant R Mining sequential patterns: generalizations 5小结 and performance improvements[C/LNCS: Proc 5th Int Conf Ex 生物序列有其自身的特点,传统的序列模式挖掘算法应用 tending Database Technology( EDBT), Avignon, 1996: 3-17. 到生物序列上有其弊端。不仅处理效率低,并且产生出大量无(8] Zaki M J Fast mining of sequential pattern in very large data 用模式,影响算法的性能。本文根据生物序列的特点,提岀基于 bases,668[R]1997-11. 相邻频繁模式段的模式挖掘算法。首先产生相邻频繁模式段,9]HanJ,PeiJ,YinY. Mining frequent patterns without candidate 然后将这些频繁模式进行组合,产生更长的频繁模式。该方法 generation[ C]/Proc 2000 ACM-SIGMOD Int'I Conf Management 并不能产生所有的频繁模式。通过实验数据对比,本算法在对 of Dta( SIGMOD00 ). Dallas: TX ACM Press, 2000: 1-12. 相似性很强的序列进行处理时,效率优于 PrefixSpan算法。通01HanJ,PiJ, Mortazavi-AslB,eta, Freespan: frequent pattern- projected sequential pattern mining[ c/proc 2000 ACM SIGKDD 过对真实的蛋白质家族序列数据库处理,证明该算法是有效可 Int'I Conf Knowledge Discovery in Databases(KDD 00),2000 行的。但是,当产生的相邻频繁模式段很多时,算法的执行效率 355-359 和运行空间都会受到影响。如何有效产生相邻频繁模式段是下1 Pei jian, Han jia-wei. Mining sequential patterns by pattern- 一步工作的内容。(收稿日期:2007年6月) growth: the Prefix Span approach [J.IEEE Transactions on Knowl- edge and Data Engineering, 2004, 6(10): 1-17 参考文献: 112 Wang Ke, Xu Ya-bo, Xu J Scalable sequential pattern mining for J Gibbs a J, Mclntyre G A.The diagram: a method for comparing biological sequences [C)/CIKM04, ashington, DC, USA, November quence[J. Eur J Biochem, 1970, 16: 1-11 13,2004 上接178页) 虑移动模型对k连通度的影响,几乎没有分析节点在不相互独 趋于0.3415(八3)的值为03415);而当n由3-∽0,式(8)趋于-立的情况下能量模型对k连通度的影响,本文通过仿真实验显 ∞,r为任意大于o的值即可。由上述分析可知,当考虑能量模示,在考虑能量模型的情况下,相关文献的数学模型变得不相 型后,由于节点个数的减少,使得网络变得比较稀疏,为了保持适应,如何对基于能量的 ad hoc网络连通度进行数学建模与 网络的连通度必需增大发射功率。但是,文献2中的r为一固分析,是目前研究的内容之一。同时,目前国内还没有 Ad hoc 定值,即p,,n在每一次实验仿真时的值是不发生变化的(不网络连通度方面的相关工作,希望本文能起到一个抛砖引玉的 考虑能量模型),当考虑能量模型后,n的值是逐步减少的,因作用。(收稿日期:2007年7月) 此为了保持网络的连通度,必须逐步增大r。所以r不仅与p, 的分布有关,也与n的减少所服从的分布相关,而如何对基于参考文献: 能量的 Ad hoc网络连通度进行数学建模与分析,目前还是 [1] Gupta P, Kumar P R Critical power for asymptotic connectivity in 个空白区域。 wireless networks[C/Fleming W H, McEneaney W M, Yin G, et al Analysis, Control, Or d Applications. Bosto Birkhauser, 1998: 547-566 0.25 [2] Santi P. The critical transmitting range for connectivity in mobile Ad Hoc networks[ IIEEE Trans on Mobile Computing, 2005. 4(3) 0.15 310-317 0.10 3 Santi P, Blough D MThe critical transmitting range for connective 0.05 ty in sparse wireless Ad hoc networks[J].IEEE Trans on Mobile 0.00 12345678910 Computing,2003,2(1):25-39 4 Dousse O, Baccelli F, Thiran P Impact of interferences on connec 图3f(x)的图像 tivity in ad-hoc networks[C]/IEEE Infocom. San Francisco, CA: 5结论与今后的工作 IEEE Computer Society Press, 2003 1724-1733 [5 Xue F, Kumar P R.The number of neighbors needed for connectiv 连通度是 Ad hoc网络的根本属性。保持网络的连通性对 ity of wireless networks[J Wireless Networks, 2004, 10(2): 169-18 于提高网络的吞吐量至关重要。本文从二个方面对这一问题进61 Hekmat r, van mieghem p degree distribution and hopcount 行了综述。由上面的分析可知,相关文献大多是在静态拓扑结 wireless Ad-hoc networks [C]/IEEE ICoN 03. Sydney, Australi- 构下考虑1连通的问题,并且假定节点之间是独立的,很少考 a: IEEE Computer Society Press, 2003: 603-609

...展开详情
试读 4P 论文研究-一种适应大型数据库的多支持度关联规则算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744270 欢迎大家使用并留下宝贵意见
    2019-09-07
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-一种适应大型数据库的多支持度关联规则算法.pdf 9积分/C币 立即下载
    1/4
    论文研究-一种适应大型数据库的多支持度关联规则算法.pdf第1页
    论文研究-一种适应大型数据库的多支持度关联规则算法.pdf第2页

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

    9积分/C币 立即下载 >