论文部分内容阅读
序列模式挖掘作为数据挖掘的一项重要研究内容，用于从各应用领域的海量数据中发现所隐含的各种规律并从中获取有价值的知识和信息。周期间隙约束的序列模式挖掘是一种带有间隔约束的序列模式挖掘问题。它要求模式的项与项之间满足用户指定的间隔约束，且间隔大小或范围均相同，即挖掘形如p0[M,N]p1...[M,N]pj...[M,N]pm-1的频繁模式（M和N分别表示最小和最大间隙）。与一般的序列模式挖掘问题相比，周期间隙约束的频繁模式更具灵活性和有效性，因此周期间隙约束的序列模式挖掘成为了现代序列模式挖掘研究领域的一个重要研究方向。本文主要针对周期间隙约束的序列模式挖掘算法进行研究，以进一步提高频繁模式的挖掘效率。本文的主要研究内容和相关工作如下：(1)总结了周期间隙约束的序列模式特点及一般的挖掘方法，详细介绍并分析了已有的挖掘算法MPP、MGCS和AMin。针对已有算法所存在的缺陷，本文提出了采用不完全网树结构来计算模式支持度的方法并设计了相应的算法INSupport。(2)依据算法INSupport，结合栈和队列数据结构提出了两个高效的挖掘算法MAPB（Mining sequentiAl Pattern using incomplete Nettree with Breadth first search）和MAPD（Mining sequentiAl Pattern using incomplete Nettree with Depth first search）对现有算法进行改进。实验结果表明，MAPB算法和MAPD算法较现有的挖掘算法在运行时间性能上均具有大幅度地提高。其中，MAPD算法性能最佳，不仅运行速度更快，而且空间消耗也最小，能够对很长的序列迅速地完成挖掘任务。(3)详细介绍了周期间隙约束的Top-K模式挖掘问题及解决该问题的方法，提出了基于MAPB的启发式Top-K挖掘算法MAPBOK（MAPB for tOp-K）。虽然该算法不能准确地得到各模式长度下的前K种最频繁模式，但当序列较长时，实验表明其能够在极短的时间内获得较高正确率的结果集。