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

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

加, 固定的迭代次数不足以使得各数据点获得较高质量的邻居, 进而使得 F1 分数略有下降. 为此, 本文选择
k = 2×minPts 作为聚类算法的输入参数.
4.6.2 K-means 树分区
为了验证本文第 3.2 节提出的层间并行策略的有效性, 本节首先在两个代表性数据集上对基于层间并行的
K-means 树分区和不采用层间并行策略的 K-means 树分区进行对比. 在 DEEP1M 数据集上, 分区时间分别为 0.64 s
和 0.98 s, 层间并行策略将分区效率提升了 47%; 在 SIFT1M 数据集上, 分区时间分别为 0.79 s 和 1.52 s, 层间并行
策略将分区效率提升了 92%. 由此可见, 层间并行策略进一步提升了分区效率, 这是因为该策略通过合理分配
GPU 线程块, 并行计算各层所有数据点, 提高了 GPU 资源利用率, 进而提升了分区效率.
此外, 为了验证 K-means 树分区的有效性, 本节将 K-means 树分区与随机分区和 KD 树分区进行对比, 采用
以上 3 种方式得到的分区进行聚类. 在达到相近精度的前提下, 随机分区、KD 树分区和 K-means 树分区所得分
区结果在 DEEP1M 数据集上的并行聚类时间分别为 0.50 s、0.49 s 和 0.34 s, 在 SIFT1M 数据集上为 0.21 s、0.21 s
和 0.17 s, 可见采用 K-means 树分区后的并行聚类相较于随机分区和 KD 树分区后聚类的效率分别高 35.3% 和 33.8%.
这是由于 K-means 树分区不受到维度灾难的影响, 将距离相近的节点分至同一区域, 减小了合并聚类簇的代价, 进
而提高了并行聚类的效率.
4.6.3 并行聚类
本节在不同参数设置下, 在两个代表性数据集上对第 3.3 节提出的 KG-DBSCAN 的并行聚类模块进行评估.
由于 cuML-DBSCAN 的近邻计算与聚类是耦合的, 无法单独测量聚类时间, 而 h-DBSCAN 的聚类是串行计算, 因
此只与 KNN-DBSCAN 和 Cal-DBSCAN 的聚类模块进行对比, 结果如表 3 所示. 结果表明, KG-DBSCAN 的聚类
模块效率显著优于基线算法的聚类模块, 平均超过 KNN-DBSCAN 算法 8.1 倍、Cal-DBSCAN 算法 10.1 倍. 这是
由于本文在第 3.3 节中提出的基于广度优先搜索的分区局部并行 DBSCAN 算法对 GPU 并行遍历数据点进行了
优化, 利用共享内存的高速访存速度以及多线程并行访问的特性加速局部 DBSCAN 的效率. 此外, 所提出的基于
核心近邻图的簇合并利用 GPU 的并行能力高效构建了核心近邻图, 基于并查集进行了高效的簇合并. 以上技术共
同促进了聚类的计算. Cal-DBSCAN 算法在 ε 固定、 minPts 变化时聚类时间变化幅度较小, 这是由于该算法聚类
策略比较简单, 仅涉及广度优先搜索扩展聚类簇, 当 minPts 变化时其计算代价所受影响较小.

表 3 并行聚类时间对比 (s)

数据集 参数 [ ε, minPts] KNN-DBSCAN Cal-DBSCAN KG-DBSCAN
[0.5, 50] 1.39 0.48 0.10
[0.5, 70] 1.73 0.47 0.15
DEEP1M
[0.7, 50] 1.99 4.77 0.31
[0.7, 70] 2.00 4.74 0.34
[200, 50] 1.63 1.85 0.17
[200, 70] 1.75 1.86 0.24
SIFT1M
[220, 50] 1.76 4.01 0.29
[220, 70] 1.99 4.04 0.36

5 总结与展望

大规模高维向量聚类旨在揭示数据分布的内在规律, 为异常检测等数据分析任务提供基础支撑. 针对现有的
基于密度的聚类方法在高维场景下效率低下的问题, 本文提出了一种 GPU 加速的高维向量聚类算法. 首先, 本文
采用 K 近邻图作为 DBSCAN 算法的索引, 设计了一种 GPU 加速的 K 近邻图索引构建算法, 利用偏好采样技术进
一步提高 K 近邻图的构建精度并提高构建速度, 显著减小了索引构建开销. 其次, 本文提出 Tensor 核心增强的层
间并行 K-means 树分区算法, 并设计了层间并行策略高效利用 GPU 资源. 此外, 本文提出基于广度优先搜索和核
心近邻图的并行聚类算法, 设计了并行广度优先策略扩展局部簇, 并构造核心近邻图, 基于核心近邻图实现了有效