论文部分内容阅读
随着大数据时代的到来,出现了大量的序列数据,而当前研究的热点与难点是从其中挖掘出用户感兴趣以及有价值的信息。然而,目前大多数的研究都为非负间隙的序列模式匹配,对每个字符的出现顺序有着严格的要求,限制了模式匹配的灵活性,降低了模式匹配的实用价值。关键词抽取是文本挖掘的重点问题,关键词是对一个文档中信息的概括与浓缩,但是目前的关键词抽取研究对抽取模式进行了严格的限制,不能够灵活的获取词语间的语义关系,导致不能对文档进行有效自主的关键词提取。因此,本文提出了一般间隙的序列模式挖掘算法并在关键抽取中进行应用研究,一般间隙的模式匹配研究不仅在理论上具有研究的价值,而且在生物信息学,文本挖掘等领域具有广泛的应用价值。本文是基于一般间隙与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算法进行序列模式挖掘,能够更好的获得候选关键词,并统计模式候选关键词的特征值,利用有监督的机器学习在特征集合中训练,构造分类模型,抽取关键词。通过大量的实验证明了该方法能有效的提高关键词抽取的质量。