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

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

400
400 1 000 400
Memory (MB) 300 600 Number of patterns Memory (MB) 300 300 Number of patterns
800

200
200
200
100 400 100 100
200
0 0 0 0
0.003 0 0.003 5 0.004 0 0.004 5 0.005 0 0.003 0 0.003 5 0.004 0 0.004 5 0.005 0
minSup minSup
(a) Value-Inc (b) MBA
Naive Naive-NoPrune Naive-T2 Naive-T1 ICFPM Patterns
图 7 算法在 minSup 变化时空间开销比较

由图 7 可以看到, 在 2 个数据集上随着 minSup 增加, 所有算法空间开销和模式数量都逐渐减少. 这是因为
minSup 越大, 算法找到的频繁模式越少, 空间复杂度和搜索空间越小, 从而减少了算法空间开销和模式数量, 与空
间复杂度分析结果相同. 同时, 可以在 2 个数据集上观察到在相同 minSup 取值下, ICFPM 算法相对于其他 4 种算
法空间开销总是最少, 这是因为 ICFPM 算法通过 2 种剪枝略可以最大限度地减少搜索空间, 减少了不必要的计算
和空间复杂度, 进而减少空间开销. 并且 Naive-NoPrune 算法要好于 Naive 算法, 这是因为使用位向量存储事务
ID 集合相比列表存储可以显著减少空间消耗, 与空间复杂度分析结果相同. 当 minSup 取 0.003 时, Naive 算法要
比 ICFPM 多消耗约 400 MB 空间.
分析 Eps 的取值改变对算法空间开销的影响, 其他参数取值如下: minSup=0.003, minPts=10, maxNR=0.1, 算法
在 Eps 变化时空间开销比较如图 8 所示.

400 8 000 400 2 000
Memory (MB) 300 6 000 Number of patterns Memory (MB) 300 1 500 Number of patterns

1 000
4 000
200
200
100 2 000 100 500
0 0 0 0
3 5 7 9 11 3 5 7 9 11
Eps Eps
(a) Value-Inc (b) MBA
Naive Naive-NoPrune Naive-T2 Naive-T1 ICFPM Patterns
图 8 算法在 Eps 变化时空间开销比较

由图 8 可以看到, 在 2 个数据集上随着 Eps 增加, ICFPM 算法、Naive-T1 算法和 Naive-T2 算法空间开销和
模式数量逐渐增加. 这是因为 Eps 越大, 更多时间戳可以聚为一簇, 产生更多候选项集, 增加了搜索空间和空间复
杂度, 从而增加了算法空间开销和模式数量, 这与空间复杂度分析结果相同. 而 Naive 算法和 Naive-NoPrune 算法
的空间开销不随着 Eps 增加而改变, 这是因为只通过频繁阈值剪枝, Eps 改变并没有改变算法搜索空间, 所以算法
空间开销和空间复杂度也不会随着 Eps 增加而变化. 同时, 可以在 2 个数据集上观察到在相同 Eps 取值下,
ICFPM 算法相对于其他 4 种算法空间开销总是最少, 并且 Naive-NoPrune 算法要好于 Naive 算法, 这与空间复杂
度分析结果相同. 当 Eps 取 11 时, Naive 算法要比 ICFPM 多消耗约 400 MB 空间.