Page 443 - 《软件学报》2025年第5期

王少鹏 等: 面向时间有序事务数据的聚簇频繁模式挖掘 2343

和分类 [16,17] 等. 当前有关频繁项集挖掘的研究按照事务数据集中数据是否时间有序, 可分为面向无时间标签事务
数据和面向时间有序事务数据 2 大类. 其中面向无时间标签事务数据的频繁项集挖掘包括基本频繁项集和衍生出
的最大频繁项集 [18–20] 、频繁闭项集 [21–23] 、高效用项集 [24–26] 等相关的研究. 在面向时间有序事务数据集的频繁项
集挖掘领域, 相关研究主要关注频繁项集在数据集中发生位置的分布情况. 比如周期模式 [27–30] 挖掘定期发生在事
务数据集中的项集; 局部周期模式 [7,31] 挖掘在某几个时间区间内定期发生的项集; 部分周期模式 [32,33] 挖掘定期发生
在事务数据集中但不一定连续发生的项集; 稀有周期模式 [33] 挖掘不频繁发生但在事务数据集中定期发生的项集;
规范频繁模式 [34–39] 挖掘以固定间隔出现在事务数据集中的项集; 周期聚簇模式 [40] 在事件序列上找到发生位置聚
簇状并且任意 2 个相邻簇的间隔满足周期特点的事件. 但总体来看, 当前这一领域还没有针对发生位置呈聚簇状
态的频繁项集挖掘问题展开研究, 这使得很多与之相关的应用无法直接使用现有方法进行有效处理. 我们可以通
过如下实例来说明这个问题.
表 1 是一个时间有序的事务数据集, 描述了零售商店中 2023 年 6 月 6 日–2023 年 6 月 20 日顾客的购物篮情
况. 其中 a、b、c、d、e 和 f 分别代表不同的商品, Timestamp 表示事务数据的发生时间. 如果我们以 5 为频繁阈
值基于该数据集挖掘频繁项集, 以 2 个频繁 1 项集 a, f 为例, 它们都会被挖掘出来, 但有时候我们可能只想得到类
似 f 这种发生位置呈集中或聚簇状态的频繁项集 (比如端午节前后的粽叶和糯米, 中秋节前后的月饼, 促销期的商
品等), 以及这些项集聚簇的位置 (比如 f 的聚簇位置是 6 月 12 日–6 月 14 日和 6 月 18 日–6 月 20 日), 这样可以更
好地了解客户需求, 改进营销计划. 但据我们所知, 目前频繁项集相关的研究都无法有效解决这个问题. 直观上该
问题可以使用如下步骤来解决, 首先利用现有的频繁模式挖掘方法求出所有频繁模式, 接着找到由每个频繁模式
对应的所有发生时间组成的集合, 最后对集合进行聚类并判断, 就可以找到所有聚簇频繁模式 (Naive 算法), 但这
种方法的时间和空间复杂度很高. 因此, 在时间有序事务数据集上挖掘聚簇频繁模式的问题仍然没有得到有效解决.

表 1 时间有序事务数据集

Tid Transaction Timestamp
1 a, c 2023年6月6日
2 d 2023年6月7日
3 a, b 2023年6月7日
4 b, d 2023年6月8日
5 a, b, f 2023年6月12日
6 b, c, e, f 2023年6月13日
7 b, d, e, f 2023年6月13日
8 a, b, d, e, f 2023年6月14日
9 b, c, d, e, f 2023年6月14日
10 a, d, e 2023年6月15日
11 c, d 2023年6月17日
12 b, f 2023年6月18日
13 a, c, e, f 2023年6月19日
14 a, b, d, e, f 2023年6月20日
15 d, f 2023年6月20日

在本文中, 我们针对时间有序事务数据集中聚簇频繁模式的挖掘问题展开了研究. 主要贡献如下.
(1) 给出了聚簇频繁模式的形式化定义.
(2) 提出了聚簇频繁模式挖掘算法 ICFPM (improved cluster frequent pattern mining), 该算法基于 Naive 方法设
计了 2 种有效的优化策略. 并通过使用数据结构 ICFPM-list 来减少时空开销.
(3) 基于 2 个真实数据集的实验结果表明, ICFPM 在时间和空间成本上都要优于 Naive 算法.
本文第 1 节介绍了聚簇频繁模式的相关工作. 第 2 节给出聚簇频繁模式形式化定义和本文关注问题的具体描
述. 第 3 节介绍聚簇频繁模式的挖掘方法. 第 4 节展示实验结果并对结果进行分析. 第 5 节进行总结.