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

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

在上述方法中, BLOCK-DBSCAN 使用单个线程进行 DBSCAN 计算, 为了加速计算, 本文使用 OpenMP 并行
计算向量距离, 线程数为 10. h-DBSCAN 在索引构建及查询时支持多线程计算, 线程数设为 10. KNN-DBSCAN 使
用 MPI 进行并行计算, 本文将 MPI 线程设为 10, 并部署 10 个 MPI 任务进行 DBSCAN 的计算. 本文所有实验均
在配备了 Ubuntu 24.04 系统、Intel(R) Core(TM) i9-10900K CPU @ 3.70 GHz、125 GB 内存和 NVIDIA GeForce
RTX 3090 GPU 的服务器上进行.
● 评估指标. 为了全面评估算法效率与精度, 本文测量以下指标: (1) 运行时间: 包含索引构建、DBSCAN 聚类
计算等全流程的端到端运行时间; (2) 准确率 (precision): 正确聚类的样本数占非噪声点数量的比例; (3) 召回率
(recall): 正确聚类的样本数占实际聚类样本数的比例; (4) F1 值: 该指标计算依赖准确率和召回率, 计算公式为
2×precision×recall
. 与相关工作类似 [21] , 本文采用 Scikit-learn 库中的精确 DBSCAN 算法的输出结果作为聚类参
precision+recall
考结果, 计算不同算法聚类准确率与召回率. 以上指标为外部指标, 为了进一步评估聚类结果, 本文同时计算聚类
内部指标: 轮廓系数 (silhouette coefficient, SC) [53,54] . 内部指标不依赖于已有标签, 而是根据簇内与簇间的度量来评
估聚类本身的质量.
4.3 参数设置
本文涉及的参数包括 K 近邻图索引的度数 k、K-means 树的节点度数及分区数 k′和 P 以及 DBSCAN 的参数

ε 和 minPts. 在实验中, k 的取值经第 4.6.1 节的评估设置为 minPts 的 2 倍, 使得算法在较低计算开销下取得较高
聚类精度. 此外, 考虑到 GPU 的共享内存容量限制, k′和 P 固定为 16 和 256, 使得算法在 GPU 内存限制下最大化
分区大小. DEEP1M、SIFT1M 和 GIST 数据集的 minPts 取值为{50, 60, 70, 80, 90}, MSong 数据集由于在 minPts
大于 50 时仅有一个簇, 故其 minPts 取值为{10, 20, 30, 40, 50}. ε 根据数据集内部距离取适当的值. 各数据集默认
参数取值如表 1 所示.
4.4 聚类性能实验结果与分析
本文在第 4.4.1 和 4.4.2 节分别改变 ε 和 minPts 两个参数, 在 4 个数据集上对算法的运行时间和精度进行评估
和对比; 在第 4.4.3 节利用内部指标对各算法的聚类质量进行评估.
ε 变化
4.4.1 查询半径
本节将所提出的 KG-DBSCAN 算法与第 4.2 节中列出的 5 个基线算法在 4 个数据集上进行对比, 各数据集
ε, 对第 4.2 节中的指标进行评估. 实验结果如图 6 所示. BLOCK-DBSCAN 在 4 个
minPts 保持不变, 变化查询半径
数据集的运行时间均超过 5 h, 故将其时间报告为 INF. KG-DBSCAN 的运行时间显著小于其余 5 个基线算法, 其
中, 超过 h-DBSCAN 算法 240.0–2 822.5 倍, 超过 KNN-DBSCAN 算法 16.2–28.2 倍, 超过 Cal-DBSCAN 算法
101.8–966.8 倍, 超过 cuML-DBSCAN 算法 6.2–47.7 倍. 由此可见, 即使相比于基于 GPU 的基线算法, 本文所提出
的 KG-DBSCAN 也表现出更快的聚类速度. 这是由于 KG-DBSCAN 将 DBSCAN 中开销最高的近邻查询转换为

K 近邻图的构建, 并设计了高效的 K 近邻图构建算法以充分利用 GPU 的高并发特性. K 近邻图更适合高维场景
下的快速构建与近邻查询. 此外, 对于 K 近邻图构建后的分区和聚类, KG-DBSCAN 同样进行了算法优化, 以保证
聚类效率. 与之相比, Cal-DBSCAN 和 cuML-DBSCAN 需遍历数据集中的所有数据为数据点计算近邻, 其中存在
大量冗余计算, G-DBSCAN [41] 存在同样的问题. 在聚类精度方面, Cal-DBSCAN 和 cuML-DBSCAN 均为精确
DBSCAN 算法, 故其 F1 分数、准确率和召回率始终为 1. 在 DEEP1M、SIFT1M 和 GIST 数据集上, KG-DBSCAN
的 F1 分数、准确率和召回率始终在 0.98 以上. 在 MSong 数据集上, KG-DBSCAN 的精度有所下降, 这是由于
MSong 中的近邻数据点距离十分接近, KG-DBSCAN 未能准确识别部分核心点. 此外, h-DBSCAN 在 GIST 数据集
上精度较低, 这是由于在聚类时产生了较多的只有一个核心点的簇, 该核心点在 ε 邻域内的点由于竞争均被其余
核心点标记为其各自的 ε 近邻, 进而被划分至其余核心点所在的簇内.
ε 增加时, 除 Cal-DBSCAN ε
当查询半径 算法外, 其余各算法的运行时间均呈增加的趋势. 这是由于查询半径
增加时, 邻域内数据点的数量增加, 因此距离计算操作增加. 此外, 簇扩展以及簇合并的过程中需遍历的数据点数