Page 448 - 《软件学报》2025年第5期
P. 448
2348 软件学报 2025 年第 36 卷第 5 期
|Candidates|≤1 (第 15–18 行).
算法 2 给出了 Naive-Generate 算法的执行情况.
算法 2. Naive-Generate 算法.
输入: Candidates, minSup, Eps, minPts, maxNR, minCF, TDS;
输出: 长度为 (k+1) 的聚簇频繁模式.
1. Candidate k+1 = ∅ ; //用于存储长度为 (k+1) 频繁项集;
2. 将 Candidates 中包含的所有 k 项集放入 itemsets 中;
3. foreach Px ∈ itemsets do
∈ itemsets 且 Px≠Py do
4. foreach Py
5. tid(Pxy)=Candidates(Px)∩Candidates(Py); //Candidate k (Px) 和 Candidate k (Py) 表示 Px, Py 对应事务 ID 集合;
Pxy
6. TS =map(TDS, tid(Pxy));
Pxy
Pxy
/
7. Sup =|TS | |TDS|;
Pxy
8. if Sup ≥minSup then
9. 将 (Pxy, tid(Pxy)) 加入 Candidate k+ 中;
1
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 ;
13. end if
14. end foreach
15. end foreach
16. return Candidate k+1
Naive-Generate (算法 2), 将 Candidates, minSup, Eps, minPts, maxNR, minCF, TDS 作为输入, 输出长度为 (k+1)
的聚簇频繁模式. 算法首先初始化 Candidate k+ 为空, Candidate k+ 用来存储频繁 k+1 项集, Candidate k+ 的结构与
1
1
1
算法 1 中的 R 相同. 之后, 将 Candidates 中的项集放入 itemsets 中 (第 1, 2 行). 接下来, 执行双重循环组合 2 个不
同的 k 项集以生成 (k+1) 项集 (第 3、4 行). 将 Px 和 Py 对应的 Candidates(Px) 和 Candidates(Py) 取交集后得到
Pxy
Pxy
tid(Pxy), 对 tid(Pxy) 通过 TDS 映射得到 TS , 并计算得到 Sup (第 5–7 行). 接下来, 如果 Sup ≥minSup, 根据定
Pxy
义 15, Pxy 是一个频繁项集, 将 Pxy 及 tid(Pxy) 转为哈希结构 (Pxy, tid(Pxy)) 并加入 Candidate k+ 中 1 (第 8、9 行) (第 1
阶段). 下一步, 对 TS Pxy 根据 Eps 和 minPts 使用 DBSCAN 进行划分并得到 P , 并计算 NR . 如果 NR ≤maxNR,
Pxy
Pxy
Pxy
那么 Pxy 是一个聚簇频繁模式, 通过 C Pxy 得到 L Pxy 并输出 P Pxy 和 L Pxy (第 10–12 行) (第 2 阶段). 最后算法返回
Candidate k+1 , 用来下一次调用 Naive-Generate 时生成 (k+2) 项集 (第 16 行).
3.1.2 算法复杂度分析
(1) 时间复杂度
算法首先基于包含 m 个事务的时间事务数据集 TDS 得到 R, 对应的时间复杂度为 O(m×w). 其中, w 为每个事
务平均长度. 之后, 对 TDS 中每个 1 项集做聚簇频繁模式判断. 对项集 x ∈ itemsets, 令 R(x) 长度为 r, 则映射为 TS x
x
的时间复杂度为 O(r); 求 Sup 对应的时间复杂度为 O(1); 如果项集满足频繁, 则可继续向下判断, DBSCAN 算法
在最坏情况下的时间复杂度为 O(r ); 由于计算 L 须遍历 1 遍 C , 令|C |=s, 则对应的时间复杂度为 O(s). 综上, 对
x
x
x
2
2
每个 1 项集做聚簇频繁模式判断的时间复杂度为 O(r+r +s). 之后, 调用 Naive-Generate 生成 (k+1) 项集, 直到无法
生成更多项集. 其中, k≥1. 如果 itemsets 中包含 g 个 k 项集, 那么所有 g 个 k 项集将组合为 (g×(g–1))/2 对项集以生
成 (k+1) 项集. 对每一对项集 Px 和 Py, 将其对应的 Candidates (Px) 和 Candidates (Py) 取交集得到 tid(Pxy), 对应的
时间复杂度为 O(r ). 接下来的判断过程与 1 项集类似, 可得对每个 (k+1) 项集做聚簇频繁模式判断的时间复杂度
2