Page 87 - 《软件学报》2026年第3期

1050 软件学报 2026 年第 37 卷第 3 期

ε 的增加而增加, 造成了算法总运行时间的增加. 值得指出的是, 图 6 虽然将 KG-DBSCAN 算法的
量随查询半径
K 近邻图构建时间包含在内, 但在实际执行时无须重新构建 K 近邻图, 因为 minPts 的数值未发生改变. K 近邻图
在查询半径 ε 变化时可复用的特性将显著降低 KG-DBSCAN 算法的计算开销. 另外, 对于 KG-DBSCAN 算法, 由
于簇扩展和簇合并过程开销较小, 因此查询半径 ε 的增加对其影响较小, 故而总运行时间增加趋势不明显.

BLOCK-DBSCAN h-DBSCAN KNN-DBSCAN Cal-DBSCAN cuML-DBSCAN KG-DBSCAN
INF 1.00 1.00 1.00
10 4 3 0.98 0.98 0.98
运行时间 (s) 10 2 1 F1 分数 0.96 准确率 0.96 召回率 0.96
10
0.94
0.94
0.94
10
10 0 0.92 0.92 0.92
0.5 0.6 0.7 0.8 0.9 0.5 0.6 0.7 0.8 0.9 0.5 0.6 0.7 0.8 0.9 0.5 0.6 0.7 0.8 0.9
查询半径 ε 查询半径 ε 查询半径 ε 查询半径 ε
(a) DEEP1M 数据集
INF 1.00 1.00 1.00
10 4
运行时间 (s) 10 3 2 1 F1 分数 0.99 准确率 0.98 召回率 0.99
10
10
10 0 0.98 0.96 0.98
200 210 220 230 240 200 210 220 230 240 200 210 220 230 240 200 210 220 230 240
查询半径 ε 查询半径 ε 查询半径 ε 查询半径 ε
(b) SIFT1M 数据集
INF 1.00 1.00 1.00
10 4 0.98
运行时间 (s) 10 3 2 1 F1 分数 0.96 准确率 0.96 召回率 0.98
0.96
10
0.94
0.94
0.92
10
0.90
0.90
10 0 0.92 0.88 0.92
10 15 20 25 30 10 15 20 25 30 10 15 20 25 30 10 15 20 25 30
查询半径 ε 查询半径 ε 查询半径 ε 查询半径 ε
(c) MSong 数据集
INF 1.00 1.00 1.00
10 4 0.95 0.95 0.95
运行时间 (s) 10 3 2 1 F1 分数 0.90 准确率 0.90 召回率 0.90
10
0.85
0.85
0.85
0.80
0.80
0.80
10
10 0 0.75 0.75 0.75
1.0 1.1 1.2 1.3 1.4 1.0 1.1 1.2 1.3 1.4 1.0 1.1 1.2 1.3 1.4 1.0 1.1 1.2 1.3 1.4
查询半径 ε 查询半径 ε 查询半径 ε 查询半径 ε
(d) GIST 数据集
图 6 查询半径 ε 变化时的算法对比

minPts 变化
4.4.2 查询参数
进一步地, 本节将查询半径 ε 固定为表 1 中各数据集对应的默认值, 改变查询参数 minPts, 评估各算法在运行
时间和聚类精度两方面的表现, 实验结果如图 7 所示. 结果表明, 本文所提出的 KG-DBSCAN 算法的计算效率在
minPts 变化时依然远超其余基线算法. 具体地, 相较于 h-DBSCAN、KNN-DBSCAN、Cal-DBSCAN 和 cuML-DBSCAN
算法分别快 530.4–1 617.2 倍、15.4–27.0 倍、93.0–942.6 倍和 5.7–29.3 倍. 由于本文实验过程中将 K 近邻图的参
数 k 设置为 minPts 的 2 倍, 因此基于 K 近邻图的算法 (KG-DBSCAN 与 KNN-DBSCAN) 的运行时间会随查询参
数 minPts 的增加而增加, h-DBSCAN 查询的近邻数量依赖于 minPts 的取值, 故其运行时间亦随着查询参数的增加
而增加. 其余算法的运行时间不受 minPts 的影响. 即使如此, KG-DBSCAN 算法相比于其他算法仍具有绝对优势.
此外, KG-DBSCAN 的精度, 即 F1 分数、准确率和召回率与基线算法中的近似算法精度相似, 在部分数据集上超
过了基线近似算法的精度.