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

李忠根 等: GPU 加速的高维向量聚类算法 1051

BLOCK-DBSCAN h-DBSCAN KNN-DBSCAN Cal-DBSCAN cuML-DBSCAN KG-DBSCAN
INF 1.00 1.00 1.00
10 4 0.98 0.98 0.98
运行时间 (s) 10 3 2 1 F1 分数 0.96 准确率 0.96 召回率 0.96
10
0.94
0.94
0.94
10
0.90
0.90
10 0 0.92 0.92 0.92
0.90
50 60 70 80 90 50 60 70 80 90 50 60 70 80 90 50 60 70 80 90
minPts minPts minPts minPts
(a) DEEP1M 数据集
INF 1.00 1.00 1.00
10 4 0.98 0.98 0.98
运行时间 (s) 10 3 2 1 F1 分数 0.96 准确率 0.96 召回率 0.96
10
0.94
0.94
0.94
10
0.90
0.90
0.90
10 0 0.92 0.92 0.92
50 60 70 80 90 50 60 70 80 90 50 60 70 80 90 50 60 70 80 90
minPts minPts minPts minPts
(b) SIFT1M 数据集
INF 1.00 1.00 1.00
10 4 0.98 0.98
运行时间 (s) 10 3 2 1 F1 分数 0.96 准确率 0.96 召回率 0.96
10
0.94
0.94
0.92
10
0.90
10 0 0.92 0.88 0.92
0.90
10 20 30 40 50 10 20 30 40 50 10 20 30 40 50 10 20 30 40 50
minPts minPts minPts minPts
(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
50 60 70 80 90 50 60 70 80 90 50 60 70 80 90 50 60 70 80 90
minPts minPts minPts minPts
(d) GIST 数据集
图 7 查询参数 minPts 变化时的算法对比

4.4.3 聚类质量评估
本节使用默认参数对 4 个数据集上各算法的轮廓系数进行了对比, 以评估各算法的聚类质量. 由于 BLOCK-
DBSCAN 计算超时, 因此未对该算法进行评估. 结果如表 2 所示.

表 2 轮廓系数对比

算法 DEEP1M SIFT1M MSong GIST
h-DBSCAN 0.071 6 0.103 5 0.073 4 0.224 5
KNN-DBSCAN 0.192 4 0.150 8 0.247 2 0.332 0
Cal-DBSCAN 0.180 3 0.151 6 0.231 9 0.327 0
cuML-DBSCAN 0.179 9 0.151 0 0.244 6 0.323 4
KG-DBSCAN 0.169 2 0.150 5 0.261 1 0.332 8

KG-DBSCAN 与 4 个基线算法得到了较为接近的轮廓系数 (SC), 且各算法的轮廓系数均大于 0, 说明各算法
均取得了较高的聚类质量. h-DBSCAN 具有较低的轮廓系数值, 这是由于该算法产生了较多的单点簇, 导致了与
其他算法指标的偏差. 虽然 KG-DBSCAN 被设计为近似算法, 其聚类质量仍可与 cuML-DBSCAN 和 Cal-DBSCAN
两个精确算法相媲美, 这得益于 KG-DBSCAN 设计了高精度的 K 近邻图构建以及基于核心近邻图的聚类簇合并