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