Page 444 - 《软件学报》2025年第5期
P. 444
2344 软件学报 2025 年第 36 卷第 5 期
1 相关工作
本文关注的问题属于时间有序事务数据中模式挖掘这一类别, 所以这部分只对该领域的研究情况进行调研.
总体来看, 当前这个领域的研究分为周期模式相关和规范模式相关 2 类.
1.1 周期模式相关
Tanbeer 等人 [27] 提出了在事务数据集中挖掘周期性频繁模式的问题, 并设计了一种基于 PF-tree 结构的模式增
长挖掘算法. Kiran 等人 [28] 基于模式增长的算法 PP-growth 挖掘周期模式, 同时考虑了周期性模式的不同周期和最
小循环重复次数. Venkatesh 等人 [29] 提出了周期相关模式, 引入了“周期-全置信度”的测量方法确定模式的周期相
关性, 并设计了 EPCP-growth 的模式增长算法. Rage 等人 [30] 设计了 PS-tree 结构记录项集时间发生信息, 并基于此
结构设计了 PS-growth 算法挖掘周期性频繁模式. Fournier-Viger 等人 [7] 提出了局部周期模式, 可以发现在一些非
预定义的时间区间内具有周期性行为的项集, 在该论文中作者使用 2 个新度量方法来评估时间间隔内模式的周期
性和频率, 分别是最大溢出周期 (度量允许检测具有可变长度的时间区间), 最小持续时间 (度量确保这些发生时间
区间具有最小持续时间). Krzywicki 等人 [31] 设计了一种新的算法 AllPat, 可以在不需要指定目标周期的情况下, 识
别局部周期性模式. Kiran 等人 [32] 设计了 3P-growth 算法以及 2 个数据结构 3P-tree 和 3P-list 挖掘部分周期模式.
Upadhya 等人 [33] 设计了 3P-BitVectorMiner 算法挖掘部分周期模式, 并设计了 2 个变种算法 RFPP-BitVectorMiner
和 R3P-BitVectorMiner 挖掘稀有完全周期模式和稀有部分周期模式. Chen 等人 [40] 提出了周期聚簇模式, 设计了周
期聚簇模式算法, 可以在事件序列上挖掘到发生位置聚簇状并且任意 2 个相邻簇的间隔满足周期特点的事件.
1.2 规范模式相关
Tanbeer 等人 [34] 提出了在事务数据集上挖掘规范模式, 设计了称为 RP-tree 的树结构, 并基于 RP-tree 设计了
模式增长算法, 挖掘具有用户定义的最大规范性的规范模式集合. Rashid 等人 [35] 设计了称为 RF-tree 的树结构, 引
入了一种基于同一模式在数据库中发生的间隔方差的新的规范性度量, 并基于 RF-tree 设计了模式增长算法挖掘
规范频繁模式. Amphawan 等人 [36] 设计了 TKRIMPE 算法挖掘 top-k 规范频繁模式, 利用数据库分区和支持度估计
技术来挖掘 top-k 规范频繁模式. 该 TKRIMPE 采用最佳优先搜索策略, 且仅需要进行 1 次数据库扫描. Kumar 等
人 [37] 设计了 MaRFI 算法, 使用一对事务标识而非项目标识来挖掘最大规范频繁模式, MaRFI 满足向下闭包性质.
Amphawan 等人 [38] 设计了 TFRC-Mine 算法挖掘 top-k 闭规范频繁模式, 利用紧凑的位向量表示来剪枝不感兴趣的
候选集. Rehman 等人 [39] 设计了 TKIFRPM 算法挖掘 top-k 规范频繁模式, 通过维护 ISI-tables 来存储增量数据的统
计信息, 采用了深度优先的搜索模式和渐进式剪枝策略, 减少了不必要的候选集生成和支持度计算.
总体来看, 目前与本文类似的研究只有 Fournier-Viger 等人 [7] 提出的局部周期模式和 Chen 等人 [40] 提出的周
期聚簇模式. 对于局部周期模式来说, 它所描述的是某段时间内周期出现, 且有最短持续时间条件约束的模式, 但
聚簇频繁模式要找的是在某段时间内或某个时间点大量出现且发生时间呈簇状的模式, 模式并不需要限制持续发
生时间; 对于周期聚簇模式来说, 它只描述 1 项集, 并不考虑多项集的发生情况. 另外对于聚簇发生位置不具有周
期特点的项, 便会舍弃. 比较而言, 聚簇频繁模式关注所有满足聚簇频繁条件的项集, 而且不具有周期特点的项集
也有可能满足聚簇频繁的条件. 所以综上所述, 现有相关研究都不适用于挖掘聚簇频繁模式, 本文试图为该问题的
解决提供一种有效的处理方法.
2 基本概念和问题说明
2.1 基本概念
设 S I = {I 1 ,I 2 ,...,I m } 是 m 个项的集合, I i 是其中第 i (1≤i≤m) 个成员, S I 中的所有成员按全序≻(字典序) 排列.
任给项集 P⊂S I , P 中的所有成员按≻排列, 令|P|表示 P 中项的个数, 如果|P|=l, 则称 P 为 l 项集 (或模式), P 的长度
为 l.
定义 1. 时间有序事务数据集. 包含 w 个成员的时间有序事务数据集 TDS = {T 1 ,T 2 ,...,T w } , 令|TDS|为 TDS 的