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

作者：杨鸿茜; 武优西^*; 耿萌; 刘靖宇; 李艳

来源：计算机工程, 2023, 1-10.

• 序列模式挖掘
• 项集挖掘
• 间隙约束
• 一次性条件
• 弱间隙约束

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

• 单位
  河北工业大学; 经济管理学院