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

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

法. 第 3.2 节针对 Naive 算法存在的冗余运算, 设计了 2 种优化策略和一种新的数据结构进行优化. 第 3.3 节介绍
了优化 Naive 算法后得到的新聚簇频繁模式挖掘算法.

3.1 Naive 算法

3.1.1 算法描述
由定义 16 可知, 聚簇频繁模式的挖掘可基于如下 2 个阶段来完成. 首先, 得到时间有序事务数据集中所有的
频繁项集; 接着基于邻域半径阈值 (Eps), 密度阈值 (minPts) 以及最大噪点比阈值 (maxNR) 过滤这些频繁项集, 保
[1]
证最终得到项集的聚簇特性. 在这 2 个阶段本文分别使用了 Apriori-TID 算法和 DBSCAN 算法 [41] , 其中 Apriori-
TID 是经典的频繁模式挖掘方法, DBSCAN 算法是一种经典的密度聚类算法, 能够保证最终结果的正确性和完整
性. 这样的方法被称为 Naive 算法. 具体描述如算法 1.

算法 1. Naive 算法.
输入: TDS: 包含 w 个事务的时间有序事务数据集, minSup, Eps, minPts, maxNR;
输出: 所有聚簇频繁模式.

1. 基于 TDS 得到哈希表 R, R 的结构为 (x, tid(x)). 其中, 键 x 是 1 项集, tid(x) 表示 x 在 TDS 中的发生事务 ID 集合,
R(x) 表示 tid(x);
∅ , k=1; //Candidate k 以 R 的结构形式存储所有频繁 k 项集;
2. Candidate k =
3. 将 TDS 中包含的所有 1 项集放入 itemsets 中;
4. foreach x ∈ itemsets do
x
5. TS =map(TDS, R(x));
x
x
/
6. Sup =|TS | |TDS|;
x
7. if Sup ≥minSup then
8. 将 (x, R(x)) 加入 Candidate k ;
9. P =C ∪Noi =DBSCAN(TS , Eps, minPts); //对 TS 进行划分;
x
x
x
x
x
x
x
x
/
10. NR =|Noi | |TS |;
x
11. if NR ≤maxNR then 通过 C 计算得到 L 并且输出 x 及对应 L ;
x
x
x
12. end if
13. end foreach
14. Candidates=Candidate k;
15. while |Candidates|>1 do //|Candidates|表示包含频繁项集总数;
16. Candidate k+1 =Naive-Generate(Candidates, minSup, Eps, minPts, maxNR, TDS);
17. Candidates=Candidate k+1 ;
18. end
如算法 1 所示, Naive 算法首先基于 TDS 得到每个 1 项集的发生事务 ID 集合, 接着以哈希表 R 的形式进行存
放. 这里 R 的结构形式为 (x,tid(x)), 其中, 项集 x 是键, tid(x) 为 x 发生事务 ID 集合, 可表示为 R(x). 初始化
Candidate k 为空, 其中, Candidate k 用来存储所有频繁 k 项集, 结构与 R 相同. 之后, 将 TDS 中包含的所有 1 项集放
x
入 itemsets 中 (第 1–3 行). 对 itemsets 中每个 1 项集 x 对应的 R (x), 通过 TDS 映射得到 TS , 并计算得到 Sup (第 x 5、
x
6 行). 如果 Sup ≥minSup, 根据定义 15, x 是一个频繁项集, 将 (x,R(x)) 加入 Candidate k 中 (第 8 行) (第 1 阶段). 对
x
x
TS 根据 Eps 和 minPts 使用 DBSCAN 进行划分并得到 P , 计算 NR . 如果 NR ≤maxNR 那么 x 是一个聚簇频繁模
x
x
式, 通过 C 得到 L 并输出 x 和 L (第 9–11 行) (第 2 阶段). 最后, 将 Candidate k 复制到 Candidates 中 (第 14 行). 算
x
x
x
法通过 while 循环重复调用 Naive-Generate 生成更大项集, 每次调用 Naive-Generate 时, 它都会组合 k 项集 (k≥1)
来生成 (k+1) 项集. Naive-Generate 调用结束后会将满足频繁条件的项集存储到 Candidates 中, while 结束条件是