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

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

x
定理 1, x 是一个聚簇频繁模式候选项集, 将 ICFPM-list 加入 new-Candidate k 中 (第 11 行). 最后, 将 new-Candidate k
复制到 new-Candidates 中 (第 14 行), 算法通过 while 循环重复调用 new-Generate 生成更大项集. 每次调用时, new-
Generate 都会组合 k 项集 (k≥1) 来生成 (k+1) 项集, new-Generate 结束后会将满足频繁的项集存储到 new-Candidates
中, while 结束条件是|new-Candidates|≤1 (第 15–18 行).
算法 4 给出了 new-Generate 算法的具体执行情况, 具体如下所示.

算法 4. new-Generate 算法.

输入: new-Candidates, minSup, Eps, minPts, maxNR, minCF, bvTimeMap, |TDS|;
输出: 长度为 (k+1) 的聚簇频繁模式.

∅ ; //用于以 ICFPM-list 结构存储所有长度为 (k+1) 聚簇频繁模式候选项集;
1. new-Candidate k+1 =
2. 将 new-Candidates 中包含的所有 k 项集放入 itemsets 中;
3. foreach Px ∈ itemsets do
4. foreach Py ∈ itemsets 如果满足 y≻ x 且 Px, Py 有相同长度为 (k–1) 的前缀 P do
5. bitvec Pxy =new-Candidates(Px)∩new-Candidates(Py); //new-Candidates(Px) 和 new-Candidates(Py) 表示 Px, Py
对应的位向量;
Pxy
6. TS =map(bvTimeMap, bitvec Pxy );
Pxy
Pxy
7. if S ⊂Pxy 且|S |=|Pxy|–1, S Pxy ∈ itemsets then //定理 2
Pxy
Pxy
/
8. Sup =|TS | |TDS|;
Pxy
9. if Sup ≥minSup then
Pxy
Pxy
Pxy
Pxy
10. P =C ∪Noi =DBSCAN(TS , Eps, minPts);
Pxy Pxy / Pxy
11. NR =|Noi | |TS |;
Pxy
Pxy
12. if NR ≤maxNR then 通过 C Pxy 计算得到 L Pxy 并且输出 Pxy 及对应 L ;
Pxy
13. if |C |≥minCF then 将 Pxy, bitvec Px 以 y ICFPM-list Pxy 形式加入 new-Candidate k+1 ; //定理 1
14. end if
15. end if
16. end foreach
17. end foreach
18. return new-Candidate k+1
new-Generate 以包含一组 k 项集的 ICFPM-list (记为 new-Candidates), minSup, Eps, minPts, maxNR, minCF,
bvTimeMap, |TDS|作为输入, 输出长度为 (k+1) 的聚簇频繁模式. 算法首先初始化 new-Candidate k+ 为空, new-
1
Candidate k+ 用于存储长度为 (k+1) 的聚簇频繁模式候选项集对应的 ICFPM-list, 并将 new-Candidates 中包含的所
1
有项集放入 itemsets 中 (第 1、2 行). 接下来, 执行双重循环组合 k 项集对以生成 (k+1) 项集. 如果 2 个 k 项集 Px
和 Py 拥有相同长度为 (k–1) 的前缀 P, 且满足 y≻ x, 则将这 2 个项集组合为 (k+1) 项集 Pxy (第 2、3 行). 接下来,
将 Px 和 Py 对应的 new-Candidates(Px) 和 new-Candidates(Py) 先取交集后得到 Pxy 对应位向量 bitvec Pxy , 之后对
Pxy
bitvec Px 通过 bvTimeMap 映射得到 TS (第 5, 6 行). 根据定理 2, 检查 Pxy 的所有长度为 k 的子项集是否都是聚
y
簇频繁模式 (在 itemsets 中), 如果存在子项集不满足, 则 Pxy 及超集都不是聚簇频繁模式 (第 7 行). 否则, 与算法 3
类似, 对 Pxy 进行聚簇频繁模式判断 (第 8–12 行). 根据定理 1, 将满足条件的 Pxy 及对应 bitvec Px 先转为 ICFPM-
y
Pxy
list , 再将 ICFPM-list Pxy 存储到 new-Candidate k+ 中 1 (第 13 行). 最后, 返回 new-Candidate k+1 , 用来下一次调用 new-
Generate 时生成 (k+2) 项集 (第 18 行).

3.3.2 运行实例
考虑表 1 所示 TDS, 给定 minSup=0.3, maxNR=0.3, Eps=2 (天), minPts=3 (天). ICFPM (算法 3) 首先将 TDS 转