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

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

算法. K 近邻图构建通过偏好采样和 GPU 加速距离计算在提高效率的同时保证了精度, 聚类簇合并算法基于核心
近邻图将簇合并问题转换为连通分量计算, 进一步保证了聚类簇的质量.
4.5 可扩展性分析
本节在 4 个数据集上对各算法的可扩展性进行评估, 使各数据集规模分别为原规模的 20%、40%、60%、
80% 和 100%, 测量各算法的运行时间及精度. 实验结果如图 8 所示. 当数据集规模增加时, 各算法的运行时间随
之增加. 除了 DEEP1M 数据集在 20% 规模时 KG-DBSCAN 略慢于 cuML-DBSCAN 之外, 其余规模下 KG-DBSCAN
的运行时间均显著优于其他算法. 另一方面, 随着数据集规模的增加, KG-DBSCAN 的 F1 分数、准确率和召回率
虽略有下降, 但在 DEEP1M、SIFT1M 和 GIST 数据集上始终高于 0.98, 这表明本文提出的 KG-DBSCAN 算法具
有良好的可扩展性; 其在 MSong 数据集上较大的精度变化是由于 MSong 中的数据点距离十分接近, 查询参数的
微小变化将显著影响聚类结果, 最终影响精度测量指标. 此外, BLOCK-DBSCAN 算法在数据规模较小时运行时间
小于 5 h, 但其精度较低, 这是由于基于树的方法在高维空间中面临维度灾难的问题, 难以获得高精度的聚类结果.

BLOCK-DBSCAN h-DBSCAN KNN-DBSCAN Cal-DBSCAN cuML-DBSCAN KG-DBSCAN
INF 1.00 1.00 1.00
10 4 0.98
运行时间 (s) 10 3 2 1 F1 分数 0.96 准确率 0.98 召回率 0.96
10
0.92
0.94
10
10 0 0.92 0.96 0.88
20 40 60 80 100 20 40 60 80 100 20 40 60 80 100 20 40 60 80 100
数据集规模 (%) 数据集规模 (%) 数据集规模 (%) 数据集规模 (%)
(a) DEEP1M 数据集
INF 1.0 1.00 1.0
10 4 0.9 0.96 0.9
运行时间 (s) 10 3 2 1 F1 分数 0.8 准确率 0.92 召回率 0.8
10
0.7
0.88
10
10 0 0.7 0.84 0.6
20 40 60 80 100 20 40 60 80 100 20 40 60 80 100 20 40 60 80 100
数据集规模 (%) 数据集规模 (%) 数据集规模 (%) 数据集规模 (%)
(b) SIFT1M 数据集
INF 1.0 1.0 1.0
10 4 0.9 0.9
运行时间 (s) 10 3 2 1 F1 分数 0.8 准确率 0.9 召回率 0.8
0.8
10
0.7
0.7
0.7
10
10 0 0.6 0.6 0.6
20 40 60 80 100 20 40 60 80 100 20 40 60 80 100 20 40 60 80 100
数据集规模 (%) 数据集规模 (%) 数据集规模 (%) 数据集规模 (%)
(c) MSong 数据集
INF 1.00 1.00 1.00
10 4 0.96 0.96 0.96
运行时间 (s) 10 3 2 F1 分数 0.92 准确率 0.92 召回率 0.92
10
0.88
0.88
0.88
10
10 1 0 0.84 0.84 0.84
20 40 60 80 100 20 40 60 80 100 20 40 60 80 100 20 40 60 80 100
数据集规模 (%) 数据集规模 (%) 数据集规模 (%) 数据集规模 (%)
(d) GIST 数据集
图 8 数据集规模变化时的算法对比

4.6 算法模块分析
本节对算法所包含的近邻图索引构建、K-means 树分区以及并行聚类这 3 个模块分别进行实验分析, 验证其