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

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

2
2
为 O(r +r+r +s). 算法利用了上述过程探索了项集的搜索空间. 在最坏情况下, 所有 1 项集及生成的 (k+1) 项集都
2
2
2
满足频繁, 最终会生成 2 (n–1) 个项集, 总的时间复杂度为 O(m×w+n×((r+r +s)+(2 (n–1) –n)×(r +r+r +s)). 其中, n 为 TDS
包含不同 1 项集总数. 算法可以根据参数的设置, 减少搜索空间, 进而减少时间复杂度.
(2) 空间复杂度
x
算法首先基于 TDS 得到 R, 占用空间为 O(m); itemsets 占用空间为 O(n). 对项集 x ∈ itemsets, TS 占用的空间
x
x
为 O(r), 如果项集满足频繁, 则可继续向下判断, P 占用的空间为 O(r); L 只需要存储 C 的发生区间, 其占用的空
x
x
间为 O(d). 其中, d 为 C 包含簇总数. 综上, 对每个 1 项集做聚簇频繁模式判断的空间复杂度为 O(r+r+d). 之后, 调
用 Naive-Generate 算法求 (k+1) 项集. 在 Naive-Generate 算法生成 (k+1) 项集过程中, 算法只需在内存中保留
Candidates 和 Candidate k+1 . 在最坏情况下, 生成的所有 (k+1) 项集都可以作为聚簇频繁模式候选项集, 假设
Candidates 包含 g 个 k 项集, Candidates 占用空间为 O(g×r); itemsets 占用空间为 O(g); Candidate k+ 中包含
1
2
(g×(g–1))/2 个 (k+1) 项集, 其占用空间为 O(g ×r). 对每个 (k+1) 项集进行聚簇频繁模式判断与 1 项集过程类似, 空
间复杂度都为 O(r+r+d). 在最坏情况下, 所有 1 项集及生成的 (k+1) 项集都满足频繁, 最终会生成 2 (n–1) 个项集, 总
的时间复杂度为 O(m+n+2 (n–1) ×(r+r+d)+(n–1)×(g×r+g+g ×r)). 其中, (n–1)×(g×r+g+g ×r) 的 (n–1) 表示 Naive-
2
2
Generate 算法迭代次数. 算法可以根据参数的设置, 减少搜索空间, 进而减少空间复杂度.

3.2 算法优化

3.2.1 优化策略
Naive 算法的第 2 阶段需要无差别地对每一个频繁项集对应的时间集合使用 DBSCAN 算法, 这极大地影响
了算法的时间效率, 有必要对该操作进行优化. 使用向下闭包性是频繁模式进行优化的首选策略, 但聚簇频繁模式
并不具有向下闭包的特点 (即一个项集如果不是聚簇频繁项集, 则其超集必不是聚簇频繁项集), 我们可以通过如
下实例来说明这点: 考虑表 1 所示 TDS, 给定 minSup=0.3, maxNR=0.3, Eps=2(天), minPts=3(天). 对 1 项集{b}求得
Sup {b} =0.6>minSup, 之后, 对 TS {b} 进行划分得到 C {b} ={c 1 }={[12,13,13,14,14]}, Noi {b} =[7,8,18,20]. 计算得
{b}
NR =0.44>maxNR, 所以, {b}不是聚簇频繁项集. 同理对 2 项集{b,f}进行判断, 可得该项集是聚簇频繁模式, 所以
向下闭包性并不成立. 聚簇频繁模式不具有向下闭包的特点使我们无法严格从该角度出发对 Naive 算法进行优化.
通过该算法执行过程进行研究, 我们得到了如下结论.
x
x'
x'
x'
引理 1. 任给项集 x', x, 考虑对 TS 和 x TS 划分后得到的 C 和 x C , 如果 x' ⊂x , 则有|C |≤|C |成立.
x
x
x'
x'
x'
x
证明: 由于 x' ⊂x, 根据 Apriori 性质, 可得 T ⊂T . 根据定义 4, 可推得 TS ⊂TS , 且∀t ∈ TS , 都有 ∈ t TS . 根据
x
x'
x'
定义 14 可知簇的形成是基于 Eps 和 minPts, 且 C 和 x C 中的簇分别由 TS 和 x TS 中的时间戳构成, 所以, ∀c2 ∈ C ,
x'
∈ C , 使得 c2⊂c1. 因此, 可知|c2|≤|c1|, 进而可得|C |≤|C |. 证毕.
x
x'
∃c1
x
引理 2. 令 minCF=minSup×|TDS|×(1–maxNR), 任给频繁项集 x, 我们有如下结论成立: 如果|C |<minCF, 那么 x
不是聚簇频繁模式.
x
x
证明: 由于|C |<minCF, 根据 minCF=minSup×|TDS|×(1–maxNR), 可得|C |<minSup×|TDS|×(1–maxNR), 由于 x 是
x
x
x
频繁项集, 根据定义 15 可知, Sup ≥minSup, 所以可以得到|C |<Sup ×|TDS|×(1–maxNR). 对上式比较符右边括号展
开, 并重新组合比较符左右两边, 可得 Sup ×|TDS|–|C |>maxNR×Sup ×|TDS|. 根据定义 14 和定义 15, 将比较符左右
x
x
x
x
x
x
两边进行替换, 可得|Noi |>maxNR×|TS |. 根据定义 14, 将比较符左右两边化简, 可得 NR >maxNR. 由定义 16 可知,
x
当 NR >maxNR 时, x 不是聚簇频繁模式. 证毕.
引理 1 给出了项集 x'与包含 x'的项集 x 在划分发生时间后得到的聚簇内容数|C |与|C |间的关系, 引理 2 得到
x'
x
了一个与新变量 minCF 相关的非聚簇频繁模式的判断条件, 具体内容可通过如下实例说明.
考虑表 1 所示 TDS, 给定 minSup=0.3, maxNR=0.1, Eps=2(天), minPts=3(天), 计算得到 minCF=4.5. 对 1 项集
{b}
{b}求得 Sup =0.6>minSup, 之后对 TS 进行划分得到 C ={c 1 }={[12,13,13,14,14]}, 对 2 项集{b,e}求得 Sup {b,e} =
{b}
{b}
{b}
0.3≥minSup, 之后对 TS {b,e} 进行划分得到 C {b,e} ={c 1 }={[13,13,14,14]}, 可得|C {b,e} |≤|C |. 对 2 项集{b,f}求得 Sup {b,f} =
0.47≥minSup, 之后对 TS {b, f} 进行划分得到 C {b,f} ={c 1 }={[12,13,13,14,14]}, 可得|C {b,f} |≤|C | (引理 1). 对 2 项集{b,e},
{b}