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

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

由上述流程可见, 本算法将 DBSCAN 算法扩展聚类簇过程中开销最大的在线近邻查询转换为离线的 K 近邻
图构建, 在扩展聚类簇时仅需遍历 K 近邻图中的邻居节点. 此方法具有两个优势: (1) DBSCAN 算法中各节点触发
在线近邻查询的时间不同. 对于 GPU 而言, 只有当多个查询并发执行时才能充分利用其高并行度. DBSCAN 触发
查询的时间差异使其难以有效利用 GPU 加速. 而通过将在线过程转换为离线过程, 构建 K 近邻图时存在大量并
发的相似度比较, 此时可使用 GPU 高效并行处理, 从而能够充分发挥 GPU 的高并发特性; (2) 由于 DBSCAN 算法

的结果依赖于 ε 和 minPts 两个参数的设置, 在线近邻查询需在不同参数设置下重新进行近邻查询, 无法复用之前
的查询结果, 这导致了较高的计算开销. 通过将在线近邻查询转换为离线 K 近邻图构建, 只要近邻图邻居数量
k > minPts, 则在 ε 变化时仍可重复利用原先构建的索引, 无须重新构建 K 近邻图索引, 显著降低了近邻查询的成
k > minPts 仍成立, 则可重复利用原先构建的索引, 但 DBSCAN 精度将有所下降, 因此在
本; 当 minPts 增大时, 若
实际使用时需在精度与效率之间进行权衡, 依据实际需求选择是否重新构建索引.
3.3.2 基于核心近邻图的簇合并算法
在各分区内的局部 DBSCAN 计算完成后, 每个分区已经形成局部聚类簇. 此时, 需要将各分区的局部聚类簇
进行合并, 以输出最终的聚类结果.
为了高效地合并聚类簇, 本文提出了基于核心近邻图的簇合并算法. 该算法利用位于不同分区的核心点之间

的关系来表示不同簇之间的关系. 若位于分区 S i 中的核心点 p 与位于分区 S j 中的核心点 q 密度直达, 则根据基于
密度的簇定义, 在完整数据集上执行 DBSCAN 时, 无论由 p 还是由 q 出发, 最终 p 与 q 都将归属于同一个聚类簇.
因此在合并簇的过程中, p 与 q 所属的簇最终也应合并为同一个簇.
基于上述观察, 如图 5 所示, 首先使用 K 近邻图的近邻信息在分区间的核心点之间构建一个以核心点为节点、
分区间的核心点间密度直达关系为边的核心近邻图. 核心近邻图是 K 近邻图的一个子图, 当分区间的两个核心点
ε 邻域内的边界点应合并为同一个簇. 由此
为彼此的近邻时, 则在核心点之间建立一条边. 有边相连的核心点及其
可将局部簇合并问题转换为计算核心近邻图的连通分量问题. 为了减小内存开销并避免重复合并, 将分区内的核
心点视为核心近邻图中的一个节点, 分区内的核心点近邻不建立边, 因为分区内已在第 3.3 节的局部 DBSCAN 算
法中进行了局部簇合并. 图 5 的示例包含 4 个不同分区的核心点与边界点, 来自不同分区的核心点之间组成了一
ε 邻域内的边界点均属于同一个聚类簇. 最终利用并查集将连通分量中的所有
个连通分量, 因此图中核心点及其
节点归并至同一个簇.

核心点
边界点
同分区核心点

图 5 核心近邻图示例

核心近邻图的构建采用以节点为中心的并行模式, 每个 GPU 线程块负责一个节点的边的建立, 以提高并行效
率. 在线程块内部, 采用类似第 3.3 节的广度优先搜索中的并行方式, 所有线程分别处理当前节点的不同邻居节点,
判断两节点间是否建立边. 这种分层并行策略有利于 GPU 线程资源的充分利用, 进一步提高了计算效率.
算法 4 展示了对分区聚类结果的合并过程, 其输入为簇编号表 Cid、核心点集 C 和核心点近邻 core_neighbors.
其中, Cid 和 core_neighbors 的含义与算法 3 相同, 核心点集 C 中存放着数据集中的所有核心点. 算法首先初始化
边集 edges. 随后, 对于每一个核心点 p, 遍历其所有距离小于等于 ε 的近邻数据 q, 若 q 为核心点, 且与核心点 p 位
p q) 加入边集
于不同的分区, 则将边 ( , (第 2–6 行), 设每个线程块中线程数量为 threadNum, 由于核心点邻居数量
至多为 k, 故该过程的时间复杂度为 O(k/threadNum). 接着, 遍历 edges 中的所有边, 并合并边的两个顶点所代表的
簇 (第 7、8 行), 该过程的时间复杂度为 O(|edges|). 在所有边合并完成后, 算法形成了最终的聚类结果, 并将合并