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

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

{f}
换为如图 1 所示 ICFPM-list, 并得到如图 2 所示 bvTimeMap, minCF=2.1. 将 1 项集{f}对应 ICFPM-list 通过
{f}
{f}
{f}
bvTimeMap 映射得到 TS =[12,13,13,14,14,18,19,20,20], 计算得到 Sup =9/15=0.6>minSup. 接下来对 TS 根据 Eps
{f}
{f}
和 minPts 使用 DBSCAN 算法进行划分, 得到 C ={c 1, c 2 }={[12,13,13,14,14],[18,19,20,20]}, Noi =[]. 计算得到
NR =0<maxNR, 所以, {f}是一个聚簇频繁模式, 计算得到 L ={l 1 ,l 2 }={[12,14],[18,20]}并输出{f}和 L . 由于
{f}
{f}
{f}
{f}
{f}
|C |>minCF, 根据定理 1, {f}是一个聚簇频繁模式候选项集, 将 ICFPM-list 存储到 new-Candidate 1 中. 同理, 对其
他项做聚簇频繁模式判断, 得到 1 项集{e}和{f}是聚簇频繁模式且都可以作为聚簇频繁模式候选项集; {b}和{d}不
是聚簇频繁模式但可以作为聚簇频繁模式候选项集. 将 new-Candidate 1 复制到 new-Candidates 中, 由于|new-
Candidates|>1, 所以, 调用 new-Generate (算法 4).
接下来进入 new-Generate 后, 首先初始化 new-Candidate 2 为空, 通过 new-Candidates 得到 itemsets={b, d, e, f}.
由于{d}和{e}有相同前缀 {∅} , 且 d≻e, 所以, 可组合为 2 项集{d,e}. 将对应 new-Candidates({d}) 和 new-
Candidates({e}) 取交集得到 bitvec {d,e} =000000111100010, 映射得到 TS {d,e} =[13,14,14,15,20]. 由于{d,e}的所有长度
为 1 的子集{d}和{e}都在 itemsets 中, 根据定理 2, {d,e}及其超集有可能是聚簇频繁模式, 可以继续向下判断. 接下
来, 计算得到 Sup {d,e} =0.3>minSup, 对 TS {d,e} 使用 DBSCAN 算法划分得到 C {d,e} ={c 1 }={[13,14,14,15]}, Noi {d,e} =
[20], NR {d,e} =0.1<maxNR. 所以, {d,e}是一个聚簇频繁模式, 计算 L {d,e} 并输出. 由于 C {d,e} ≥minCF, 根据定理 1, {d,e}
是一个聚簇频繁模式候选项集, 将{d,e}和 bitvec {d,e} 组合为 ICFPM-list {d,e} 并加入 new-Candidate 2 中. 同理, 对其他
1 项集进行组合, 对得到 2 项集并做聚簇频繁模式判断. 最后, 得到{d,e}和{b,f}是聚簇频繁模式且都可以作为聚簇
频繁模式候选项集; {b,e}和{e, f}不是聚簇频繁模式但可以作为聚簇频繁模式候选项集加入 new-Candidate 2
中. 最后, 将 new-Candidate 2 作为返回值. 根据 new-Generate 得到 new-Candidate 2 并复制到 new-Candidates, 由于
|new-Candidates|>1, 根据算法 3 (第 16 行), 继续调用 new-Generate 与上述过程相同. 最后, 得到只有{b,e,f}是聚簇
频繁模式且可以作为聚簇频繁模式候选项集, 由于|new-Candidates|=1≯1, 根据算法 3 (第 14 行), 算法结束.

3.3.3 算法复杂度分析
在第 3.1.2 节中定义了一些变量用于复杂度分析, 这些变量将在本节继续使用.
(1) 时间复杂度
ICFPM 算法首先将包含 m 个事务的时间事务数据集 TDS 转换为 ICFPM-list, 对应的时间复杂度为 O(m×w),
与 Naive 算法中得到 R 的时间复杂度相同. 之后, 对 TDS 中每个 1 项集做聚簇频繁模式判断. 对项集 x ∈ itemsets,
x
由于 x 对应的 ICFPM-list(x) 长度为 m, 所以, 映射为 TS 的时间复杂度为 O(m). 由第 3.1.2 节可知 Naive 算法使用
R 结构做映射时对应的时间复杂度为 O(r), 且 r≤m, 所以, 使用 ICFPM-list 结构做映射时的时间复杂度要多于
x
Naive 算法的 R 结构. 接下来, 求 Sup 对应的时间复杂度为 O(1). 如果项集满足频繁, 则可继续向下判断, DBSCAN
算法在最坏情况下的时间复杂度为 O(r ); 由于计算 L 须遍历 1 遍 C , 对应时间复杂度为 O(s). 综上, 对每个 1 项
2
x
x
2
集做聚簇频繁模式判断的时间复杂度为 O(m+r +s). 之后调用 new-Generate 算法生成 (k+1) 项集, 直到无法生成更
多项集. 如果 itemsets 中包含 g 个 k 项集, 那么所有 g 个 k 项集将组合为 (g×(g–1))/2 对项集以生成 (k+1) 项集. 对
每一对项集 Px 和 Py, 将其对应的 new-Candidates (Px) 和 new-Candidates (Py) 取交集得到 bitvec Pxy , 由于使用向量
2
的位与操作, 对应的时间复杂度为 O(m). 由第 3.1.2 节可知 Naive-Generate 算法做交集的时间复杂度为 O(r ), 当
2
new-Candidates(Px) 和 new-Candidates(Py) 长度较长时, 使 O(m)≤O(r ), 这时, 使用 ICFPM-list 结构要好于 R 结构.
2
接下来的判断过程与 1 项集类似, 可得对每个 (k+1) 项集做聚簇频繁模式判断的时间复杂度为 O(m+m+r +s).
在最坏情况下, 所有 1 项集及生成的 (k+1) 项集都满足频繁, Naive 算法最终会生成 2 (n–1) 个项集. 然而, ICFPM
算法在 Naive 算法基础上使用了 2 种优化策略. 首先, 在频繁条件的基础上, 使用定理 1 过滤了更多不可能是聚簇
频繁模式的项集, 减少了候选项集数量, 即 new-Candidates, 进而减少了搜索空间和时间复杂度; 其次, 定理 2 通过
参考 (n –1) 项集的判别结果, 减少了 new-Generate 算法中对项集做聚簇频繁模式判断操作, 进而减少了时间复杂
度. 综上, 2 种优化策都减少了 Naive 算法时间复杂度. 同时使用 ICFPM-list 结构减少了项集对应事务 ID 集合做
2
交集的时间复杂度, 但增加了做映射时的时间复杂度. 所以, ICFPM 算法总的时间复杂度为 O(m×w+n×(m+r +s)+