检索结果-内蒙古大学图书馆

软件学报 2021年第11期32卷 3331-3350页

作者：武优西刘茜闫文杰郭磊吴信东河北工业大学人工智能与数据科学学院天津300401 省部共建电工装备可靠性与智能化国家重点实验室(河北工业大学) 天津300401 河北省大数据计算重点实验室天津300401 河北工业大学电气学院天津300401 教育部大数据知识工程重点实验室(合肥工业大学) 合肥230009 明略科学院明略科技集团北京100084

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法,与同类挖掘方法相比,该方法更容易发现有价值的频繁模式,其核心问题是计算给定模式在序列中的支持度或出现数,进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模... 详细信息

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法,与同类挖掘方法相比,该方法更容易发现有价值的频繁模式,其核心问题是计算给定模式在序列中的支持度或出现数,进而判定该模式的频繁性.而计算模式支持度问题实质是无重叠条件模式匹配.当前研究采用迭代搜索无重叠出现,然后剪枝无用结点的方式计算模式的支持度,其计算时间复杂度为O(m×m×n×W),其中,m,n和W分别为模式长度、序列长度及最大间隙.为了进一步提高无重叠条件模式匹配计算速度,从而有效地降低无重叠条件序列模式挖掘时间,提出了一种高效的算法,该算法将模式匹配问题转换为一棵网树,然后从网树的最小树根结点出发,采用回溯策略迭代搜索最左孩子方式计算无重叠最小出现,在网树上剪枝该出现后,无需进一步查找并剪枝无效结点即可实现问题的求解.理论证明了该算法的完备性,并将该算法的时间复杂度降低为O(m×n×W).在此基础上,继续指明该问题还存在另外3种相似的求解策略,分别是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最右双亲方式.实验结果验证了该算法的性能,特别是在序列模式挖掘中,应用该方法的挖掘算法可以降低挖掘时间.

关键词：模式匹配序列模式挖掘无重叠条件网树回溯策略

来源：评论

学校读者我要写书评

暂无评论

无重叠条件模式匹配的在线求解算法

引用

计算机工程与科学 2019年第12期41卷 2239-2246页

作者：武优西王博高雪冬河北工业大学人工智能与数据科学学院

无重叠条件模式匹配是众多间隙约束的模式匹配算法中的一种,尽管当前证明了无重叠条件模式匹配是一个多项式时间复杂度问题,并提出了有效的求解算法,但是当前求解算法采用离线计算方式,具有空间复杂度较高的缺点。为了解决该问题,设计... 详细信息

无重叠条件模式匹配是众多间隙约束的模式匹配算法中的一种,尽管当前证明了无重叠条件模式匹配是一个多项式时间复杂度问题,并提出了有效的求解算法,但是当前求解算法采用离线计算方式,具有空间复杂度较高的缺点。为了解决该问题,设计了一种在线求解算法,该算法一边读入序列串,一边在流网树中寻找符合约束条件的树根-树叶路径,以快速剪枝无用节点,从而加快了匹配速度。与离线算法的空间复杂度相比,在线算法的空间复杂度为O(m×maxlen×W),这里m,maxlen和W分别表示模式串长度、模式最大长度约束和最大间隙约束。实验结果不仅验证了算法的完备性,与现有算法相比,在内存占用上均有较大性能的提升。

关键词：模式匹配间隙约束无重叠条件在线算法网树

来源：评论

学校读者我要写书评

暂无评论

无重叠条件下的Top-k序列挖掘

引用

小型微型计算机系统 2019年第10期40卷 2170-2174页

作者：武优西王振坤史巧硕刘靖宇河北工业大学人工智能与数据科学学院天津300401 河北省大数据计算重点实验室天津300401

无重叠条件序列模式挖掘是一种带间隙约束的序列模式挖掘方法,能够有效地克服当前此类挖掘中的问题.但是当前的方法仅仅用于挖掘频繁模式,为了高效地挖掘最为频繁的k种无重叠序列模式,本文提出了"Gfp-tree(Gain-frequence-patternt... 详细信息

无重叠条件序列模式挖掘是一种带间隙约束的序列模式挖掘方法,能够有效地克服当前此类挖掘中的问题.但是当前的方法仅仅用于挖掘频繁模式,为了高效地挖掘最为频繁的k种无重叠序列模式,本文提出了"Gfp-tree(Gain-frequence-patterntree)"这一数据结构,构建了无重叠条件下完备的Top-k模式挖掘算法.该算法基于Apriori性质,不预先设定支持度阈值,而是在挖掘过程中生成并动态调整,直到挖掘过程结束.有效减少了候选模式的生成数量,节约了运行时间.实验表明,该算法具有较高的效率.

关键词：无重叠条件频繁模式 Top-k 序列挖掘

来源：评论

学校读者我要写书评

暂无评论

无重叠条件下的Top-k序列模式挖掘

无重叠条件下的Top-k序列模式挖掘

引用

作者：杨丹河北工业大学

学位级别：硕士

在一些模式挖掘问题研究中,经常会挖掘出大量用户不感兴趣的模式,这些模式在实际生活中难以应用。由于越频繁的模式,越容易是用户关心的模式,为此提出了Top-k模式挖掘。尽管该模式挖掘可以帮助用户找到最频繁的k种模式,但是在满足Aprior... 详细信息

在一些模式挖掘问题研究中,经常会挖掘出大量用户不感兴趣的模式,这些模式在实际生活中难以应用。由于越频繁的模式,越容易是用户关心的模式,为此提出了Top-k模式挖掘。尽管该模式挖掘可以帮助用户找到最频繁的k种模式,但是在满足Apriori性质的挖掘中,Top-k挖掘只能挖掘到短模式。然而短模式所包含的信息量不如长模式的多。为此本文针对无重叠序列模式挖掘问题,研究挖掘各个模式长度下前k个支持度最高的模式,即无重叠条件下的Top-k序列模式挖掘。本文的主要研究内容和相关工作如下:(1)分析了传统Top-k序列模式挖掘存在的缺点,对周期间隙约束的Top-k序列模式挖掘算法MAPBOK和改进的Top-k序列模式挖掘算法NOSEP-k进行了描述和分析。针对已有Top-k算法存在的不足,本文提出了无重叠条件下的Top-k序列模式挖掘算法NOSTOPK(Non-overlapping Sequence Pattern Mining for Top-k)。(2)本文算法NOSTOPK采用网树结构计算模式支持度,无需设置最小支持度阈值,有效解决了最小支持度阈值ρ在频繁模式挖掘中难以设置的问题;每次都选择支持度最高的前k个模式向下挖掘,探寻其对应的k*|?|个模式中支持度最高的前k个,不但减少了模式候选集的数量,而且对模式进行了有效压缩。(3)传统的Top-k模式挖掘算法是为了得到所有频繁模式中最频繁的前k个模式,而本文挖掘算法可以得到各个长度下支持度最高的前k个模式,满足用户对模式的特殊需求。大量的实验结果验证了我们提出的NOSTOPK算法的可行性和有效性。

关键词：序列模式挖掘间隙约束 Top-k 无重叠条件网树

来源：评论

学校读者我要写书评

暂无评论

无重叠条件下的Top-k序列模式挖掘

无重叠条件下的Top-k序列模式挖掘

引用

作者：王振坤河北工业大学

学位级别：硕士

在序列模式挖掘研究中,带间隙约束的序列模式挖掘因其高效性和有效避免盲目挖掘冗余模式而成为当下的研究热点。无重叠条件序列模式挖掘是一种带间隙约束的序列模式挖掘方法,能够有效地克服当前此类挖掘中的问题。无重叠条件是指在一次... 详细信息

在序列模式挖掘研究中,带间隙约束的序列模式挖掘因其高效性和有效避免盲目挖掘冗余模式而成为当下的研究热点。无重叠条件序列模式挖掘是一种带间隙约束的序列模式挖掘方法,能够有效地克服当前此类挖掘中的问题。无重叠条件是指在一次挖掘过程中,序列中相同位置的字符不能在模式的相同位置处重复使用。但是当前的方法仅仅用于挖掘频繁模式,且最小支持度阈值不好设定。为了高效地挖掘最为频繁的k种无重叠序列模式,本文在无需预先设定支持度阈值情况下,挖掘无重叠条件下Top-k序列模式。本论文的主要研究内容与相关工作如下:(1)首先,分析了Top-k序列模式挖掘产生的原因与背景;介绍了三种挖掘条件并进行了比较。对带间隙约束的Top-k序列模式挖掘算法NOSEPK和Top-k序列模式挖掘算法ENUMK进行了描述和分析,指出他们所存在的不足,因而提出本文算法TOPMINING。(2)本文算法TOPMINING采用网树结构计算模式支持度,无需设置最小支持度阈值,有效解决了最小支持度阈值ρ在频繁模式挖掘中难以设置的问题;采用高效的模式增长策略和精心构建的数据结构——模式增长树,快速且完备地找出所有模式中支持度最高的前k个模式。(3)而后,针对短模式过多的信息量不足问题。提出了算法TOPBYLEN。通过给出候选因子e,通过支持度较高的前k*e个模式进行增长,减少了模式候选集的数量,而且对模式进行了有效压缩。(4)本文针对无重叠条件的Top-k模式挖掘问题,分别研究了传统Top-k模式挖掘和特定长度的Top-k模式挖掘,并给出了相关算法。最后通过对比实验,验证了两算法的可行性与有效性。

关键词：序列模式挖掘间隙约束 Top-k 无重叠条件网树

来源：评论

学校读者我要写书评

暂无评论

无重叠条件的闭合序列模式挖掘

无重叠条件的闭合序列模式挖掘

引用

作者：王宁宁河北工业大学

学位级别：硕士

闭合序列模式挖掘已经成为序列模式挖掘重要研究方向之一并且在诸多领域具有广泛应用。许多研究表明闭合模式集是频繁模式集的无损压缩表示,同时保留了频繁模式集中所有有用的信息,并且隐含了其他频繁模式的信息。无重叠条件是指一个模... 详细信息

闭合序列模式挖掘已经成为序列模式挖掘重要研究方向之一并且在诸多领域具有广泛应用。许多研究表明闭合模式集是频繁模式集的无损压缩表示,同时保留了频繁模式集中所有有用的信息,并且隐含了其他频繁模式的信息。无重叠条件是指一个模式在序列中的任意两个出现的相同位置不使用序列位置相同的字符。无重叠条件的序列模式挖掘大大减少了冗余模式的产生,并能够有效地挖掘出满足条件的模式。无重叠条件的闭合模式挖掘结合了二者的优势,得到了越来越多研究者们广泛的关注和研究。相对于其他类型的序列模式,无重叠条件的闭合模式更加简洁有效且结果完整。因此,本文对无重叠条件的闭合模式挖掘问题进行深入研究。本文主要的研究内容和相关工作如下:(1)给出无重叠条件的闭合序列模式挖掘的相关概念和定义,并对相关算法Clo GSgrow的挖掘过程进行简要分析,举例说明了该算法丢失有效解的原因,证明该算法不具有完备性。(2)介绍了网树的相关概念和性质,模式P的所有出现都能转化为网树的根结点到叶子结点的路径,进而采用网树结构计算模式支持度。提出基于位置检索策略的PSC算法来进行闭合模式的判定,并在该算法的基础上提出了基于广度优先的无重叠条件的闭合模式挖掘算法NOCSP-BEST。(3)选取DNA序列和蛋白质序列,通过大量实验分析比较NOCSP-BEST、NOCSP-DF与Clo GSgrow算法的挖掘结果和挖掘时间,证明NOCSP-BEST算法具有高效性和完备性。

关键词：序列模式挖掘闭合模式无重叠条件网树位置检索

来源：评论

学校读者我要写书评

暂无评论

无重叠条件下的间隙约束序列模式挖掘

无重叠条件下的间隙约束序列模式挖掘

引用

作者：仝瑶河北工业大学

学位级别：硕士

序列模式挖掘(Sequence Pattern Mining)是数据挖掘的重要组成部分,主要任务是发现序列数据库中频繁出现的子序列,并且在诸多领域具有广泛的应用。传统的序列模式挖掘具有盲目性,导致挖掘结果冗余并且效率低下,因此衍生出多种类型的条... 详细信息

序列模式挖掘(Sequence Pattern Mining)是数据挖掘的重要组成部分,主要任务是发现序列数据库中频繁出现的子序列,并且在诸多领域具有广泛的应用。传统的序列模式挖掘具有盲目性,导致挖掘结果冗余并且效率低下,因此衍生出多种类型的条件和约束有针对性地进行挖掘。间隙约束的序列模式挖掘问题具有广泛的应用价值,是目前的研究热点。根据出现的不同约束要求,间隙约束的序列模式挖掘可以分为无特殊条件、一次性条件和无重叠条件。无重叠条件是指一个模式在序列中的任何两个出现中不能在相同位置处使用同一个字符,即不会像无特殊条件产生大量的冗余模式,也不会像一次性条件忽略了感兴趣的模式。本文研究表明,无重叠条件下的序列模式挖掘具有更充分的研究价值和应用价值。本文的主要研究内容和相关工作如下:1.给出了无重叠条件下的序列模式挖掘问题的严格定义,分析现有的无重叠模式匹配算法INSgrow不能完备求解的原因,并且理论证明无重叠条件下的模式匹配可以求出完备解。2.提出了模式匹配算法NETGAP,该算法采用网树结构,可以完备地求解出现,并在此基础上提出了三种挖掘算法,分别是广度优先挖掘算法NetMining-B,深度优先挖掘算法NetMining-D和采用了能够减少候选集的模式增长策略的NOSEP算法;3.在DNA序列和时间序列上比较无特殊条件、一次性条件和无重叠条件的挖掘结果,证明无重叠条件更能挖掘出用户感兴趣的频繁模式。并通过大量的对比实验证明NOSEP算法的完备性和高效性。

关键词：序列模式挖掘间隙约束无重叠条件网树 Apriori性质

来源：评论

学校读者我要写书评

暂无评论

无重叠条件的负序列模式挖掘

无重叠条件的负序列模式挖掘

引用

作者：邢欢河北工业大学

学位级别：硕士

重复的序列模式挖掘是一种重要的数据挖掘方式,它能够有效地检测和识别出模式在序列中的重复出现。无重叠条件的序列模式挖掘是重复的序列模式挖掘的一种变形,它通过使用无重叠条件和间隙约束,可以避免挖掘过多无意义的模式,从而使挖掘... 详细信息

重复的序列模式挖掘是一种重要的数据挖掘方式,它能够有效地检测和识别出模式在序列中的重复出现。无重叠条件的序列模式挖掘是重复的序列模式挖掘的一种变形,它通过使用无重叠条件和间隙约束,可以避免挖掘过多无意义的模式,从而使挖掘结果更具针对性。然而,当前无重叠条件的序列模式挖掘只考虑了序列中发生的事件,忽略了未发生的事件,因此导致一些发生频率较高的负序列模式被忽略。为了解决这个问题,本文研究了无重叠条件的负序列模式(Nonoverlapping Negative Sequential Pattern,简称NNSP)挖掘问题,并提出了对应的挖掘算法NNSP-Miner,该算法可以同时挖掘正序列模式和负序列模式。NNSP-Miner算法包含三个核心步骤,分别是候选模式的支持度计算、生成和剪枝。本文主要的研究工作如下: 1.在计算候选模式的支持度时,为了提升计算效率,本文首先提出了采用倒排索引结构的PScan算法。然后为了进一步提升支持度的计算效率,本文又提出了基于索引表结构的ITGAP算法。与同类算法NETGAP和DFOM相比,本文提出的算法在计算支持度的过程中均有效避免了频繁地创建和销毁结点。 2.在生成候选模式时,为了使生成结果中包含所有潜在的频繁模式,本文首先提出了枚举策略。但是由于该策略的生成空间较大,从而会降低算法的性能。因此,本文又提出了一种新的模式连接策略,它能够同时生成正负两种候选模式,并且能够大大降低候选模式的数量,从而极大地提高挖掘的效率。 3.为了进一步提升挖掘的性能,本文提出了一种基于哈希表的剪枝策略,该策略可以有效地避免计算冗余的负候选模式的支持度。 4.结合ITGAP算法、模式连接策略和剪枝策略,本文提出了一种高效的挖掘算法NNSP-Miner。经过大量的实验,发现该算法在DNA、病毒和蛋白质等数据集上都表现出良好的效果。此外,通过在股票数据集上进行实验,验证了该算法可以有效地过滤波动较大的噪音模式,从而使得挖掘结果更加满足用户的需求。综上,本文深入研究了无重叠条件下的负序列模式挖掘,并且提出了一种高效的挖掘算法NNSP-Miner。此外,本文在大量数据集上进行了充分的实验,实验结果表明NNSP-Miner不仅具有出色的挖掘性能和挖掘能力,而且在实际生活中也有较高的应用价值。

关键词：负序列模式挖掘索引表无重叠条件倒排索引间隙约束

来源：评论

学校读者我要写书评

暂无评论

无重叠条件下最大序列模式挖掘

无重叠条件下最大序列模式挖掘

引用

作者：张帅河北工业大学

学位级别：硕士

带有间隙约束的序列模式挖掘是重复序列模式问题的扩展,其具有灵活的表达性和良好的针对性,已成为数据挖掘方向中的热点课题。作为间隙约束序列模式挖掘的一种,无重叠条件下序列模式挖掘与同类方法相比,该方法更易于发现有价值的频繁序... 详细信息

带有间隙约束的序列模式挖掘是重复序列模式问题的扩展,其具有灵活的表达性和良好的针对性,已成为数据挖掘方向中的热点课题。作为间隙约束序列模式挖掘的一种,无重叠条件下序列模式挖掘与同类方法相比,该方法更易于发现有价值的频繁序列模式。当前研究是一种挖掘频繁模式完全集的方法,会挖掘出大量较短模式,这不仅降低了挖掘效率,而且增加了用户获取需求信息的难度。最大序列模式挖掘是指挖掘其超模式为非频繁模式的频繁模式,在不改变用户设定的最小支持度阈值前提下,可以有效减小模式集的规模,并且保留其表达能力,从而提供频繁模式与非频繁模式的边界信息。有鉴于此,本文针对在无重叠条件下的最大序列模式挖掘课题做出了详细的分析和介绍。本文主要研究内容和相关工作如下:1.本文对无重叠条件下的最大序列模式挖掘问题的定义及性质作出详细的分析与说明。2.本文提出了Netback算法,该算法将模式在序列中计算支持度问题转换为一颗网树,从叶子结点出发采用回溯策略迭代搜索最左双亲结点,得到无重叠出现,从而计算模式的支持度。与NETGAP算法相比,使时间复杂度从O（m*m*n*w/r/r）降到O（n*m*w/r/r）。3.本文提出Net MNP算法挖掘无重叠条件下的最大序列模式。本文利用无重叠条件下的序列模式挖掘满足Apriori性质,提出PGrowth候选模式生成算法,该算法采用模式拼接方式生成候选模式,有效对候选模式集进行剪枝。同时Net MNP算法结合模式生成算法对最大序列模式进行判定。4.本文在真实生物序列数据集上进行大量实验,通过Net MNP算法与多种挖掘算法的实验结果对比,验证了本文算法在模式匹配和模式挖掘方面的高效性。在无重叠条件下,挖掘结果集与频繁模式集对比,验证了最大序列模式集的良好压缩效果。

关键词：序列模式挖掘最大序列模式无重叠条件网树回溯策略

来源：评论

学校读者我要写书评

暂无评论

无重叠条件严格模式匹配的高效求解算法

无重叠条件严格模式匹配的高效求解算法

引用

作者：刘茜河北工业大学

学位级别：硕士

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法,与同类挖掘方法相比,该方法更容易发现有价值的频繁模式,其核心问题是计算给定模式在序列中的支持度或出现数,进而判定该模式的频繁性,而计算模式支持度问题实质是无重叠条件模... 详细信息

无重叠条件序列模式挖掘是一种间隙约束序列模式挖掘方法,与同类挖掘方法相比,该方法更容易发现有价值的频繁模式,其核心问题是计算给定模式在序列中的支持度或出现数,进而判定该模式的频繁性,而计算模式支持度问题实质是无重叠条件模式匹配。当前研究采用迭代搜索无重叠出现,然后剪枝无用结点的方式计算模式的支持度,其计算时间复杂度为O(mmnW),其中m,n和W分别为模式长度,序列长度及最大间隙。为了进一步提高无重叠条件模式匹配计算速度,从而为降低无重叠条件序列模式挖掘时间打下基础,本文提出了一种高效的无重叠条件模式匹配算法NETBack(Nonoverlapping Nettree Backtracking),该算法将模式匹配问题转化为网树形式,然后从网树的最小树根结点出发,采用回溯策略迭代搜索最左孩子方式计算无重叠最小出现,在网树上剪枝该出现后,无需进一步查找并剪枝无效结点即可实现问题的求解。本文理论证明了该算法的完备性并将该算法的时间复杂度降低为O(mnW)。在此基础上,本文继续指明,该问题还存在另外三种相似的求解策略,分别是从最左叶子出发迭代查找最左双亲方式、从最右树根出发迭代查找最右孩子方式和从最右叶子出发迭代查找最右双亲方式。实验结果证明了本文算法的性能,特别是在序列模式挖掘中,应用本文方法的挖掘算法可以降低挖掘时间。

关键词：模式匹配间隙约束无重叠条件网树回溯策略

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：