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

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

确定项集的发生时间, 定义了 bvTimeMap.
[7]
定义 19. bvTimeMap . 考虑包含 w 个事务的 TDS, bvTimeMap 是一个长度为 w 的数组. bvTimeMap[i]=a 表示
ID 为 (i+1) 的事务数据中项集的发生时间为 a.
例 19: 考虑表 1 所示 TDS, 由定义 19 不难得到与其相关的 bvTimeMap, 具体如图 2 所示.

时间戳 6 7 7 8 12 12 13 13 14 15 17 18 19 20 20
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
图 2 表 1 对应 bvTimeMap

3.3 改进的聚簇频繁模式挖掘算法

3.3.1 算法描述
基于优化策略与数据结构部分的内容对 Naive 算法进行改造, 可以得到改进后的聚簇频繁模式挖掘算法
ICFPM. 具体如算法 3 所示.

算法 3. ICFPM 算法.

输入: TDS: 包含 w 个事务的时间有序事务数据集, minSup, Eps, minPts, maxNR;
输出: 所有聚簇频繁模式.
1. 得到 TDS 中所有 1 项集对应的 ICFPM-list 并且计算 minCF, bvTimeMap;
2. new-Candidate k = ∅ , k=1; //new-Candidate k 用于以 ICFPM-list 结构存储长度为 k 的聚簇频繁模式候选项集;
3. 将 TDS 中所有 1 项集放入 itemsets;
4. foreach x ∈ itemsets do //对 itemsets 中每个 1 项集 x;
x
x
5. TS =map(bvTimeMap, ICFPM-list(x)); //根据 bvTimeMap 将 ICFPM-list(x) 映射为 TS ;
x
/
x
6. Sup =|TS | |TDS|;
x
7. if Sup ≥minSup then
x
x
x
x
x
8. P =C ∪Noi =DBSCAN(TS , Eps, minPts); //对 TS 进行划分;
x
x
x
/
9. NR =|Noi | |TS |;
10. if NR ≤maxNR then 通过 C 计算得到 L 并且输出 x 及对应 L ;
x
x
x
x
x
x
11. if |C |≥minCF then 将 ICFPM-list 加入 new-Candidate k 中; //定理 1
12. end if
13. end foreach
14. new-Candidates=new-Candidate k ;
15. while |new-Candidates|>1 do //|new-Candidates|表示包含候选项集总数;
16. new-Candidate k+1 =new-Generate(new-Candidates, minSup, Eps, minPts, maxNR, minCF, bvTimeMap, |TDS|);
17. new-Candidates=new-Candidate k+1 ;
18. end
ICFPM 算法首先基于 TDS 得到所有 1 项集的 ICFPM-list, 并计算得到 minCF 和 bvTimeMap. 初始化 new-
Candidate k 为空, k=1, new-Candidate k 与 ICFPM-list 结构相同, 用来存储所有长度为 1 的聚簇频繁模式候选项集对
应的 ICFPM-list, 并将 TDS 中包含的所有 1 项集放入到 itemsets 中 (第 1–3 行). 遍历 TDS 中的每个 1 项集 x, 将其
x
x
x
ICFPM-list(x) 通过 bvTimeMap 映射得到 TS , 并计算得到 Sup (第 5、6 行). 接下来, 如果 Sup ≥minSup, 那么根据
x
x
x
x
定义 15, x 是一个频繁项集, 对 TS 根据 Eps 和 minPts 使用 DBSCAN 进行划分并得到 P , 并计算 NR . 如果 NR ≤
x
x
x
x
maxNR, 那么 x 是一个聚簇频繁模式, 通过 C 得到 L 并输出 x 和 L (第 7–10 行). 接下来, 如果 |C |≥minCF, 根据