检索结果-南通市图书馆

一般间隙与one-off条件的序列模式匹配

在线全文

学校读者我要写书评

暂无评论

软件学报 2018年第2期29卷 363-382页

作者：刘慧婷刘志中黄厚柱吴信东计算智能与信号处理教育部重点实验室(安徽大学) 安徽合肥230039 安徽大学计算机科学与技术学院安徽合肥230601 合肥工业大学计算机科学与信息工程学院安徽合肥230009 School of Computing and Informatics University of Louisiana at LafayetteLafayette 70503USA

带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-... 详细信息

带有间隙约束的模式匹配问题是序列模式挖掘的关键问题之一.目前,大多数的研究都为非负间隙,对字符串中每个字符的出现顺序有着严格的要求.为了增加匹配的灵活性,并且考虑到在序列模式挖掘中采用one-off条件更加合理,研究一般间隙与one-off条件下的模式匹配问题.该问题为NP-Hard问题.为了有效地求解该问题,提出了MSAING(maximum sequential pattern matching with one-off and general gaps condition)算法:首先,利用Reverse策略使模式与序列达到最佳的匹配状态;然后,使用线性表的结构使匹配过程中消耗的时间和空间大幅度地降低,同时,利用回溯机制提高匹配的成功率;最后,根据inside_Checking机制判断模式串是否会产生内部重复现象,以进一步提高算法的执行效率.理论证明了MSAING算法的完备性,实验结果验证了MSAING算法匹配结果的准确性以及在时间和空间方面的高效性.

关键词：一般间隙 one-off条件模式匹配线性表

满足one-off条件及间隔约束的频繁模式挖掘研究

在线全文

学校读者我要写书评

暂无评论

满足One-off条件及间隔约束的频繁模式挖掘研究

作者：黄咏明合肥工业大学

学位级别：硕士

随着信息技术的高速发展和互联网的迅速普及,使得数据挖掘的使用越来越广泛。频繁模式挖掘就是数据挖掘领域中的一个重要分支,它主要是从序列文本中发现出现频繁的模式,它在文本检索、网络安全和各种数据流挖掘等领域都有着巨大的实际... 详细信息

随着信息技术的高速发展和互联网的迅速普及,使得数据挖掘的使用越来越广泛。频繁模式挖掘就是数据挖掘领域中的一个重要分支,它主要是从序列文本中发现出现频繁的模式,它在文本检索、网络安全和各种数据流挖掘等领域都有着巨大的实际应用。本文研究的“满足one-off条件及间隔约束的频繁模式挖掘”,是“带通配符的频繁模式挖掘”问题的一种,是基于传统的模式挖掘问题上的提高,它允许挖掘出的频繁模式中含有通配符。引入通配符虽然使问题变得复杂,但是模式形式更加灵活,这使得带通配符的频繁模式挖掘不仅具有理论研究价值,而且有着更加广泛的应用价值:它可以从生物序列中发现对生物学家有用的信息,也可以处理网络日志、入侵数据、购物数据等事务数据集中发现更灵活的模式。本文的主要工作如下:(1)oneoffMining算法满足one-off条件和Apriori性质,可以减少挖掘过程生成的候选项集,实验证明该算法相比单序列挖掘算法MPP有更好的时间性能,并且在多序列数据集上也有良好的效果。(2)本文将oneoffMining算法应用于生物序列模式挖掘,事务数据挖掘,以及文本挖掘等相关领域,展示其具有很强的实际应用价值。(3)最后给出一个课题网站系统设计,结合了该课题的一些研究的算法演示,包括本文的算法演示,为今后研究更加深入的研究提供一个平台。

关键词：数据挖掘频繁模式通配符间隔约束 one-off条件

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

带通配符的多序列模式挖掘

南京大学学报（自然科学版） 2013年第2期49卷 226-234页

作者：马晓文胡学钢谢飞郭丹合肥工业大学计算机与信息学院合肥230009 合肥师范学院计算机科学与技术系合肥230601

带有通配符的多序列模式挖掘在文本检索、网络安全、生物科学等领域中具有很重要的作用.通过挖掘多序列模式,能够透彻的了解序列之间的联系,在各个领域中具有重要的现实意义.在已有的工作中,随着多序列集长度的增大,挖掘的规模呈现指数... 详细信息

带有通配符的多序列模式挖掘在文本检索、网络安全、生物科学等领域中具有很重要的作用.通过挖掘多序列模式,能够透彻的了解序列之间的联系,在各个领域中具有重要的现实意义.在已有的工作中,随着多序列集长度的增大,挖掘的规模呈现指数级增长.研究这样一个问题:给定多条序列s1,…,sn,支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于给定支持度阈值的频繁序列模式,并且要求模式中任意两个相邻元素在序列中的出现位置满足用户定义的间隔约束.设计了一个有效的算法M-oneoffMine,模式在序列中的出现满足one-off条件.在生物DNA序列上的实验结果表明,M-oneoffMine算法比相关的序列模式挖掘算法具有更好的时间性能.

关键词：多序列间隔约束通配符 one-off条件频繁模式

在线全文

学校读者我要写书评

暂无评论

带有间隔约束的多序列模式挖掘

计算机应用 2014年第9期34卷 2612-2616,2634页

作者：王华东杨杰李亚娟郑州轻工业学院现代教育技术中心郑州450002

研究这样一个问题:给定多序列、支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于支持度阈值的频繁序列模式,这里要求模式中任意两个相邻元素在序列中的出现都要满足用户自定义的间隔约束,并且模式在序列中的出现要满足one-off... 详细信息

研究这样一个问题:给定多序列、支持度阈值和间隔约束,从多序列中挖掘所有出现次数不小于支持度阈值的频繁序列模式,这里要求模式中任意两个相邻元素在序列中的出现都要满足用户自定义的间隔约束,并且模式在序列中的出现要满足one-off条件。在解决该问题上,已有算法M-oneoffMine在计算模式的支持度时,只考虑模式的每个字符在序列中的首次出现,导致计算的模式支持度远小于其真实支持度,以致许多频繁的模式没有被挖掘出来。为此,设计了一个有效的带有间隔约束的多序列模式挖掘算法——MMSP算法:首先,通过采用二维表保存模式的候选位置;然后,根据候选位置采用最左最优的思想选择匹配位置。通过生物DNA序列进行实验,多序列中元素序列数目不变而序列长度变化时,MMSP挖掘出的频繁模式总数是同类算法M-oneoffMine的3.23倍;在元素序列个数变化时,MMSP挖掘出的频繁模式个数平均是M-oneoffMine的4.11倍;这两种情况下MMSP都有更好的时间性能。在模式长度变化时,MMSP挖掘出的频繁模式个数分别平均是M-oneoffMine的2.21倍和MPP的5.24倍。同时还验证了M-oneoffMine挖掘到的模式是MMSP挖掘到的频繁的子集。实验结果表明,MMSP算法不仅可以挖掘到更多的频繁模式,而且时间花费更少,更适合于实际的应用。

关键词：多序列模式挖掘间隔约束频繁模式 one-off条件

在线全文

学校读者我要写书评

暂无评论

求解PMWOC问题的位并行算法

计算机应用研究 2015年第10期32卷 2973-2977页

作者：张浩叶明全皖南医学院计算机教研室安徽芜湖241002

带有灵活通配符和one-off条件的模式匹配问题(pattern matching with flexible wildcards and one-off condition,PMWOC)具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹... 详细信息

带有灵活通配符和one-off条件的模式匹配问题(pattern matching with flexible wildcards and one-off condition,PMWOC)具有重要的理论意义和实际应用价值。给定带灵活通配符的模式和文本,目标是在线的计算模式在文本中的出现次数和匹配位置,这里要求任何两次出现不能共享文本同一位置,即one-off条件。提出了一个基于位并行的搜索算法,采用了非确定有限自动机(nondeterministic finite automatons,NFA)对文本进行扫描。通过理论和实验证明,与其他解决相同问题的算法对比,该算法取得更好的时间性能和空间性能,而且不受模式长度变化和通配符间距变化影响。

关键词：模式匹配通配符 one-off条件

在线全文

学校读者我要写书评

暂无评论

一次性条件约束的序列模式挖掘

一次性条件约束的序列模式挖掘

作者：赵培河北工业大学

学位级别：硕士

实际应用领域中存在大量的序列数据,这些序列数据中隐藏着丰富的有价值的知识。如何在序列数据库中挖掘频繁出现的序列模式,是序列模式挖掘的重要任务。随着信息技术的高速发展和互联网的迅速普及,序列模式挖掘已成为数据挖掘领域中一... 详细信息

实际应用领域中存在大量的序列数据,这些序列数据中隐藏着丰富的有价值的知识。如何在序列数据库中挖掘频繁出现的序列模式,是序列模式挖掘的重要任务。随着信息技术的高速发展和互联网的迅速普及,序列模式挖掘已成为数据挖掘领域中一项非常重要的研究任务。本文研究的一次性条件约束的序列模式挖掘,是带通配符的频繁模式挖掘问题的一种,是基于传统的模式挖掘问题上的提高,它允许挖掘出的频繁模式中含有通配符并满足一次性条件。引入一次性条件具有重要的理论价值,同时在实际应用中,找到模式P的所有出现有时也是不必要的。因此本文主要针对一次性条件约束的序列模式挖掘算法进行研究,以进一步提高频繁模式的挖掘效率。本文的研究内容和相关工作如下:1.本文研究的一次性条件约束的序列模式挖掘是基于模式匹配技术的,应用网树结构设计了三种算法来计算候选模式的支持度,即Cal-SGSP(Calculating Support with Strategy of Greedy-Search Parent)、Cal-SRMP(Calculating Support with Strategy of Right Most Parent)和Cal-SBO(Calculating Support with Selecting Better Occurrence).Cal-SGSP算法在寻找模式在目标序列的一个出现时,采用贪婪搜索双亲策略,每一步都寻找当前结点的一个近似最优双亲;Cal-SRMP算法则采用最右双亲策略,每一步寻找当前结点的最右双亲结点作为当前该模式的一个出现位置;Cal-SBO算法则择优使用两种策略,寻找相同叶子结点的两个出现并选择出现相关数最小的作为候选模式的一个出现,最后返回候选模式的支持数。2.给出了基于网树结构的一次性条件约束的序列模式挖掘算法的框架。通过调用以上三种应用网树结构的模式匹配方法计算候选模式在给定的序列上的支持数,最后以此来判定该模式是否是频繁模式,形成了三种一次性条件约束的序列模式挖掘算法,即SGSP-Mining,SRMP-Mining和SBO-Mining算法。同时为了避免待检测的候选模式过多,算法采用Apriori性质进行剪枝,以减少对候选模式支持数的计算。3.选取有代表性的数据集和对比算法,设计了大量的对比实验,从算法的挖掘结果和挖掘效率两方面对实验结果进行了分析,验证了本文提出的三种算法的有效性。

关键词：序列模式挖掘频繁模式 one-off条件模式匹配网树

基于通配符和长度约束的近似模式匹配问题研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于通配符和长度约束的近似模式匹配问题研究

作者：黄国林合肥工业大学

学位级别：硕士

近年来，随着生物信息计算、网络入侵检测、文本检索等领域数据量的激增，如何从中快速地提取用户感兴趣的信息成为了一项重要的研究课题，而模式匹配与挖掘是其中的重要组成部分，引起了国内外研究学者的广泛关注。为了增加用户模式... 详细信息

近年来，随着生物信息计算、网络入侵检测、文本检索等领域数据量的激增，如何从中快速地提取用户感兴趣的信息成为了一项重要的研究课题，而模式匹配与挖掘是其中的重要组成部分，引起了国内外研究学者的广泛关注。为了增加用户模式查询的灵活性，通配符和长度约束的概念先后被引入模式匹配问题中。本文首先针对带有通配符和长度约束的近似模式匹配问题进行研究，用户可以自行定义模式字符间通配符的范围、模式的最短长度和最大长度以及允许出现的编辑误差。对该问题的研究，不仅完善了近似模式匹配中通配符的引入问题，而且在许多实际领域同样具备应用价值。随后，本文将该问题扩展至带有通配符和one-off条件的近似模式挖掘，解决了带间隔约束和误差的频繁模式挖掘问题。本文的研究工作主要包括以下三个方面：（1）根据文本字符是否满足one-off条件，针对带有通配符和长度约束的近似模式匹配问题分别提出了APM算法和APM-OF算法，并与同类算法Sail-Approx进行实验对比，结果表明APM和APM-OF算法解的平均增长率分别达到了12.37%和8.34%。同时，对影响算法性能的三个主要参数进行了实验与分析，发现当编辑误差k较大，模式P中字符（非通配符）的个数m适中，局部长度约束下限N很小或很大时解的增长率最为明显，可分别达到31.43%和18.78%。（2）将APM-OF算法扩展至带有通配符和长度约束的近似模式挖掘，提出了MAP算法。在与oneoffMining算法的实验对比中，结果显示MAP算法挖掘出的频繁模式个数约为oneoffMining算法的2.07倍。（3）构建了解决带有通配符和长度约束的近似模式匹配和挖掘问题的原型系统，并通过实例对系统进行演示说明，为模式匹配和挖掘进一步的研究提供了一个良好的平台。

关键词：通配符长度约束 one-off条件近似模式匹配近似模式挖掘

基于位并行技术的带通配符约束的模式匹配问题研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

基于位并行技术的带通配符约束的模式匹配问题研究

作者：洪小丽合肥工业大学

学位级别：硕士

模式串匹配是计算机科学中一个基本、重要的研究问题。随着信息技术的高速发展,它在Internet网络信息搜索、数据流挖掘、网络入侵检测、计算生物学等领域中的应用越来越广泛。近年来,带通配符约束的模式匹配问题作为模式匹配领域的一项... 详细信息

模式串匹配是计算机科学中一个基本、重要的研究问题。随着信息技术的高速发展,它在Internet网络信息搜索、数据流挖掘、网络入侵检测、计算生物学等领域中的应用越来越广泛。近年来,带通配符约束的模式匹配问题作为模式匹配领域的一项新颖的研究方向已经越来越引起广泛的关注。在传统的模式中加入通配符约束,虽然使问题变得更复杂,但更能满足用户对模式的灵活定义的需求。这使得带通配符约束的模式匹配问题不仅具有理论研究价值,而且有着实际应用价值:如在生物信息学中,很多蛋白质模式便含有通配符约束。当前对带通配符的模式匹配存在的很多现有的工作,但仍然有一些问题需要进一步的研究,如在模式中通配符约束的定义,匹配结果的表达,时间效率的提高。为此,本文针对以上关键问题进行研究,主要工作如下:(1)本文在已有的工作基础上,介绍同时包括全局长度约束及局部通配符约束模式匹配问题的形式化定义,证明在one-off条件下带通配符约束的模式匹配问题是一个NP-hard问题。(2)提出一种基于位并行技术的提出的BPBM算法。算法基于“最左最优”的启发式策略,返回one-off条件下的所有匹配序列。该算法的基本思想是采用了BM算法的基于后缀搜索的方法,使用两个非确定性自动机NFA对扫描文本的过程进行模拟,并利用位并行技术解决了NFA当前活动状态比较多,对于每次读入的新字符更新活动状态集慢的缺陷。理论分析及实验证明BPBM算法较解决同类或类似问题的其他算法无论在时间上或匹配结果上更具竞争力。(3)最后给出一个本课题的网站系统设计,包含本课题的一些研究的算法演示,为今后研究更加深入的研究提供一个平台。

关键词：模式匹配通配符约束全局长度约束 one-off条件位并行

一般间隙序列模式挖掘及其在关键词抽取中的应用

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

一般间隙序列模式挖掘及其在关键词抽取中的应用

作者：刘志中安徽大学

学位级别：硕士

随着大数据时代的到来,出现了大量的序列数据,而当前研究的热点与难点是从其中挖掘出用户感兴趣以及有价值的信息。然而,目前大多数的研究都为非负间隙的序列模式匹配,对每个字符的出现顺序有着严格的要求,限制了模式匹配的灵活性,降低... 详细信息

随着大数据时代的到来,出现了大量的序列数据,而当前研究的热点与难点是从其中挖掘出用户感兴趣以及有价值的信息。然而,目前大多数的研究都为非负间隙的序列模式匹配,对每个字符的出现顺序有着严格的要求,限制了模式匹配的灵活性,降低了模式匹配的实用价值。关键词抽取是文本挖掘的重点问题,关键词是对一个文档中信息的概括与浓缩,但是目前的关键词抽取研究对抽取模式进行了严格的限制,不能够灵活的获取词语间的语义关系,导致不能对文档进行有效自主的关键词提取。因此,本文提出了一般间隙的序列模式挖掘算法并在关键抽取中进行应用研究,一般间隙的模式匹配研究不仅在理论上具有研究的价值,而且在生物信息学,文本挖掘等领域具有广泛的应用价值。本文是基于一般间隙与one-off条件的序列模式匹配,序列模式挖掘及其在文本领域中关键词抽取的应用进行研究。内容主要关于三个方面:(1)同时具有一般间隙与one-off条件约束的序列模式匹配的算法设计及分析;(2)在序列模式匹配的基础上,进行一般间隙与one-off条件下的序列模式挖掘问题研究;(3)将一般间隙与one-off条件下的序列模式挖掘算法应用到文本信息挖掘中,通过挖掘出词语间的语义关系,进行关键词的抽取。本文主要的工作与创新点如下:(1)在序列模式匹配研究中,提出了一般间隙与one-off条件的序列模式匹配问题 SPMGOO(Sequential Pattern Matching with General gaps—and one-off condition),在具有间隙约束的模式中允许子模式串之间的间隙为负值,同时加入了 one-off条件,允许序列串中任意位置的字符最多使用一次的精确的严格模式匹配。之后,通过理论证明了 SPMGOO问题为NP-Hard问题。并首次使用线性表解决SPMGOO问题,并且在模式匹配的过程中首次提出对模式串的结构以及序列串中各字符频度进行分析,判断是否需要转置操作,使模式与序列达到最佳匹配状态。(2)在序列模式匹配研究中,提出了基于一般间隙与one-off条件的最大数目的序列模式匹配算法 MSAING(Maximum Sequential pattern mAtching wIth one-off and General gaps condition)。MSAING 算法首先采用 Reverse 策略判断是否需要转置操作;然后,利用线性表的结构进行模式匹配,具体分为定位阶段、Forward阶段、Backward阶段,使MSAING算法在模式匹配过程中消耗的时间和内存大大的减少,同时在Backward阶段使用回溯机制,使匹配的成功率大幅度提高;最后,提出了 inside—Checking机制判断模式串是否会产生内部重复现象,以及如果产生内部重复会在模式串的哪个位置产生,从而有效的提高了MSAING算法的运行效率。并首先从理论上证明了 MSAING算法比目前已有算法具有更好的完备性,对于不含重复的模式能够取得完备解。其次,本文在真实的生物数据集以及文本上,与DCNP等多种相关的改进算法进行了对比实验,通过实验结果验证了 MSAING算法具有较高的准确性,和较低的时空复杂度,并对实验结果及其意义进行了分析。(3)在序列模式挖掘研究中,提出了一般间隙与one-off条件的序列模式挖掘算法 SPING(Sequential Pattern mIning with one-off and General gaps condition)。SPING算法在一般间隙的条件下不仅能够获取不连续的序列模式,同时也可以挖掘出前后颠倒的频繁模式,提高了模式挖掘的灵活性。该算法获取模式更加完备的解,从而挖掘出更加真实的信息,并通过在生物序列及其对比实验验证了该算法的有效性。(4)在关键词抽取研究中,提出了关键词抽取算法KEING(KeyphraseExtraction using sequentIal patterns with one-off and General gaps condition)。一般间隙能够更有效的获取词语,词组之间的语义关系,因此利用SPING算法进行序列模式挖掘,能够更好的获得候选关键词,并统计模式候选关键词的特征值,利用有监督的机器学习在特征集合中训练,构造分类模型,抽取关键词。通过大量的实验证明了该方法能有效的提高关键词抽取的质量。

关键词：一般间隙 one-off条件序列模式匹配序列模式挖掘关键词抽取