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

来源 :华东交通大学 | 被引量 : 0次 | 上传用户:jiaosai
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着大数据时代的到来,出现了大量的序列数据,而当前研究的热点与难点是从其中挖掘出用户感兴趣以及有价值的信息。然而,目前大多数的研究都为非负间隙的序列模式匹配,对每个字符的出现顺序有着严格的要求,限制了模式匹配的灵活性,降低了模式匹配的实用价值。关键词抽取是文本挖掘的重点问题,关键词是对一个文档中信息的概括与浓缩,但是目前的关键词抽取研究对抽取模式进行了严格的限制,不能够灵活的获取词语间的语义关系,导致不能对文档进行有效自主的关键词提取。因此,本文提出了一般间隙的序列模式挖掘算法并在关键抽取中进行应用研究,一般间隙的模式匹配研究不仅在理论上具有研究的价值,而且在生物信息学,文本挖掘等领域具有广泛的应用价值。本文是基于一般间隙与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算法进行序列模式挖掘,能够更好的获得候选关键词,并统计模式候选关键词的特征值,利用有监督的机器学习在特征集合中训练,构造分类模型,抽取关键词。通过大量的实验证明了该方法能有效的提高关键词抽取的质量。
其他文献
随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟,研制出了各种具有感知能力、计算能力和通信能力的微型传感器,由许多微型传感器构成的无线传感器网络(WSN)引起
随着我国经济的不断发展,人民物质生活与精神生活水平的不断提高,国家在基础建设方面的投入越来越多,从而使建筑市场逐渐扩大。如何使建筑工程项目在保证质量的前提下,运用科学的
随着社会的进步和科学技术的不断提高,交通运输网络体系变的越来越庞大、复杂,那么如何在规模庞大、结构复杂的交通运输网络中寻求一条高效、时实、可靠的最短路径却成为人们眼
医学图像配准是指针对两幅医学图像,通过对其寻找某种空间变换,使得两幅图像的特征点、面或像素值达到空间上的一致。医学图像配准在临床上有非常重要的研究意义,是非常有价值的
形式概念分析(Formal ConceptAnalysis,FCA),也称概念格理论,是Wille R于1982年提出的一种有效的知识表示与知识发现工具,目前已被成功的应用到很多领域,如知识工程、机器学习、信息
在云计算、大数据环境下,负载均衡问题逐渐成为研究的焦点之一。负载均衡是实现集群最优调度的主要目标之一,计算节点的负载不均衡,就会导致云平台上任务执行效率低、严重浪
随着遥感应用逐渐趋向于定量化和精确化,高光谱解混作为高光谱遥感影像处理的关键技术之一,日益引起国内外学者的广泛关注。高光谱解混是指利用高光谱图像将混合像元分解为几种基本类型的地物光谱向量(端元),并求得这些基本地物所占比例(丰度)的技术。高光谱解混性能的提高,不仅有利于高光谱应用的发展,如地物的分类和识别、图像的解译和可视化、图像的增强和压缩等,也对地质勘探、农业监测和军事侦查等具有重要意义。本文
随着互联网技术和经济的飞速发展以及Saas概念的提出,传统的服务行业也发生了巨大的变化。面对互联网中急剧增长的服务资源提供商和服务需求客户,我们提出了面向双边资源整合(B
随着多媒体技术和万维网的快速发展,从海量图像数据中检索出来人们需要的图像信息成为一个急需解决的问题。不同于传统的基于文本的图像检索方式,基于内容的图像检索成为大规模
多核处理器已经成为目前主流的处理器,相应的多线程并发编程也成为了目前主流的编程。多线程并发程序在充分利用多核处理器带来的高运行效率的同时,相比于串行程序也带来了更多线程交错的不确定性。线程的交错执行让程序员对并发程序的理解更加困难,使并发程序存在着比串行程序更多的错误和缺陷。因此,并发程序的正确性成为了研究热点,而对并发程序正确性的验证,也成为了当下程序验证领域的热门话题。并发程序正确性的验证工作
学位