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

2354 软件学报 2025 年第 36 卷第 5 期

2
(2 (n–1) –n–u)×(m+m+r +s)), 其中, u 表示使用了 2 种优化策略后对比 Naive 算法减少的需要做聚簇频繁模式判断的
项集数量. 算法可以根据参数的设置, 减少搜索空间, 进而减少时间复杂度.
(2) 空间复杂度
由于 ICFPM 算法在 Naive 算法基础上, 使用了 ICFPM-list 结构, 由于使用位向量表示事务 ID 集合, 所以, 所
有 1 项集对应 ICFPM-list 共占用空间为 O(m/8), 对比 R 结构减少了 8 倍空间消耗; bvTimeMap 占用空间为 O(m);
x
x
itemsets 占用空间为 O(n). 对项集 x ∈ itemsets, TS 占用的空间为 O(r); P 占用的空间为 O(r), L 只需要存储发生位
x
置区间, 占用的空间为 O(d). 综上, 对每个 1 项集做聚簇频繁模式判断的空间复杂度为 O(r+r+d). 之后, 调用 new-
Generate 求 (k+1) 项集. 在 new-Generate 算法生成 (k+1) 项集过程中, 算法只需在内存中保留 new-Candidates 和
new-Candidate k+1 . 在最坏情况下, 生成的所有 (k+1) 项集都可以作为聚簇频繁模式候选项集, 假设 new-Candidates
包含 g 个 k 项集, new-Candidates 占用空间为 O(g×m/8); itemsets 占用空间为 O(g); new-Candidate k+ 中包含
1
2
(g×(g–1))/2 个 (k+1) 项集, 其占用空间为 O(g ×m/8). 对比 Naive-Generate 算法中的 Candidates 和 Candidate k+1
分别减少了 8 倍. 对每个 (k+1) 项集进行聚簇频繁模式判断与 1 项集过程类似, 空间复杂度都为 O(r+r+d).
在最坏情况下, 所有 1 项集及生成的 (k+1) 项集都满足频繁, Naive 算法最终会生成 2 (n–1) 个项集. 然而, ICFPM
算法在 Naive 算法基础上使用了 2 种优化策略, 减少了搜索空间和不必要的判断操作. 同时使用 ICFPM-list 结构
减少了项集对应事务 ID 集合占用空间, 但增加了 bvTimeMap 的占用空间. 最终, 可得 ICFPM 算法总的空间复杂
度为 O(m/8+m+n+(2 (n–1) –u)×(r+r+d)+(n–1–v)×(g×m/8+g+g ×m/8)). 其中, v 表示 new-Generate 算法减少的迭代次数.
2
算法可以根据参数的设置, 减少搜索空间, 进而减少空间复杂度.

4 实验评测

本节实验目的有 2 个: (1) 验证 ICFPM 算法中优化方法的有效性; (2) 对 ICFPM 算法在参数 minSup、Eps、
minPts、maxNR 不同取值下的性能变化 (时间和空间) 情况进行评测. 由于目前并没有针对时间有序事务数据集上
聚簇频繁模式挖掘的研究, 所以我们把 Naive 算法、使用 ICFPM-list 结构改造后的 Naive 算法 (记为 Naive-
NoPrune 算法)、使用 ICFPM-list 结构和优化策略 1 改造后的 Naive 算法 (记为 Naive-T1 算法)、使用 ICFPM-list
结构和优化策略 2 改造后的 Naive 算法 (记为 Naive-T2 算法), 作为 ICFPM 算法的实验对比算法.

4.1 实验环境及数据集
本文实验中的算法都使用 Python 实现, 在 Windows 11 22H2 环境下运行. 计算机配置为 Intel(R) Core(TM) i7-
10700 CPU@2.90 GHz. 实验使用 2 个真实数据集: MBA 和 Value-Inc. 其中 MBA 时间范围为 2010/01/12–
2011/12/10, 包含 4 186 个不同的商品和 21 663 笔交易. Value-Inc 时间范围为 2018/02/12–2019/02/20, 包含 3 407 个
不同的商品和 25 898 笔交易. 数据集可从 Market Basket Analysis (kaggle.com) 和 Sales Analysis for “Value Inc.”
Case Study Python | Kaggle 获得.

4.2 ICFPM 算法性能评价

4.2.1 ICFPM 算法运行时间分析
首先分析 minSup 的取值改变对算法运行时间的影响, 其他参数取值如下: Eps=5, minPts=10, maxNR=0.1, 算
法在 minSup 变化时运行时间比较如图 3 所示.
由图 3 可以看到, 随着 minSup 增加, 所有算法运行时间都逐渐减少. 这是因为 minSup 越大, 算法找到的频繁
项集越少, 时间复杂度和搜索空间越小, 从而减少了算法运行时间, 与时间复杂度分析结果相同. 同时, 可以在 2 个
数据集上观察到在相同 minSup 取值下, ICFPM 算法相对于其他 4 种算法消耗时间总是最少, 这是因为 ICFPM 算
法使用 2 种剪枝策略可以有效减少搜索空间和时间复杂度, 并且相对于 Naive-T1 算法和 Naive-T2 算法, ICFPM
算法同时减少了候选项集数量和不必要的判断. 还可以观察到, 使用 ICFPM-list 的 Naive-NoPrune 算法要好于
Naive 算法, 这是因为使用位向量表示事务 ID 集合可以更快地做交集, 与时间复杂度分析结果相同. 当 minSup 取
0.003 时, Naive 算法要比 ICFPM 多消耗约 100 倍时间.