高效的一次性弱间隙序列模式挖掘算法

间隙约束序列模式挖掘作为序列模式挖掘的一个重要分支，可以发现模式在序列中的重复出现。然而，当前研究主要针对单项序列进行挖掘，并且序列中每一项都被认为具有相同意义。为解决该问题，提出一次性弱间隙序列模式挖掘（OWP）算法，该算法由准备阶段、支持度计算和候选模式生成3个步骤组成。在准备阶段，建立倒排索引，并对不频繁的项进行剪枝；在支持度计算方面，利用倒排索引结构记录出现位置，避免对原始数据集的重复扫描；在候选模式生成方面，采用模式连接策略，减少冗余候选模式的生成。在项集序列和单项序列共6个真实数据集上的实验结果表明，OWP算法相比OWP-p、Ows-OWP和OWP-e算法在运行时间上分别提升了2.653、1.348、3.592倍，在内存消耗上分别减少了3.51%、0.07%、5%，说明OWP算法可以更高效地挖掘出用户感兴趣的模式。此外，OWP算法在以D1数据集为基础的6倍大小的数据集上的运行时间比D1数据集增长了3.763倍，内存消耗增长了2.310倍，运行时间和内存消耗的增加倍数均小于数据集大小的增加倍数，说明OWP算法具有良好的可扩展性。