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

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

核心点 边界点 噪声点
ε
p 1
p 2
p 3
C 2
C 1
p 4
p 5
minPts=3
图 1 基于密度的聚类示例

定义 9 和定义 2 是等效的. 一方面, 根据定义 9, K 近邻图核心点 p 与其邻居列表中最近的 minPts 个点的距离
ε N ε (p) ⩾ minPts, 因此符合定义 2.
小于 ε, 则说明与数据 p 的距离小于 的数据点的数量必定大于等于 minPts, 即
另一方面, 根据核心点的定义 (定义 2), 与数据 p 的距离小于 ε 的数据点的数量大于等于 minPts, 则说明数据 p 的
ε, 因此满足定义 9. 所以, 定义 2 与定义 9 是等效的.
第 minPts 近的邻居与 p 的距离必定小于
根据定义 9, 核心点的判定从计算 ε 邻域内点的数量, 转换为判断与第 minPts 个近邻点的距离是否在 ε 的范
围内. 若点 p 为核心点, 对于其在 K 近邻图中的非核心点邻居 q, 若 q 满足 q ∈ N (p)∧d(p,q) ⩽ ε, 则 q 为边界点. 然
k
ε 的近邻点数量大于 N ε (p) > k 时, 其超出 k 的边界点将被识别为噪声点, 导致聚类精度
而, 当点 p 的距离小于 k, 即
降低. 为了进一步提高精度, 本文重新定义边界点 (定义 10), 以对噪声点进行后处理.
定义 10 (K 近邻图边界点). 给定非核心点 p, 若 p 在 K 近邻图的邻居 N(p) 中存在核心点 q, 且两者的距离
d(p,q) ⩽ ε, 则点 p 为 K 近邻图边界点.
定义 10 与定义 3 是等效的. 一方面, 对于非核心点 p, 根据定义 10, 其在 K 近邻图的邻居中存在核心点 q, 且

距离小于等于 ε, 则说明数据点 p 位于核心点 q 的 ε 邻域内, 即 p ∈ N ε (q), 因此满足定义 3. 另一方面, 根据定义 3,
ε
边界点 p 位于核心点 q 的 邻域内, 则 q 必定出现在点 p 在 K 近邻图的邻居中, 否则, 说明点 p 的 K 近邻均小于
p 为边界
d(p,q) < ε. 此时, 由于 minPts < k, 与点 p 的距离小于 ε 的点的数量大于 minPts, 因此点 p 为核心点, 这与
点的前提矛盾. 故定义 3 中的边界点必定满足定义 10.
根据上述讨论, 修改后的定义 9 和定义 10 对于聚类结果而言, 与定义 2 和定义 3 是等效的.

2.3 GPU 架构
GPU 通常配备数十个流式多处理器 (streaming multiprocessor, SM), 每个流式多处理器作为独立处理单元, 其
包含数百个计算核心以及独立的共享内存和寄存器结构. 在编程层面, 统一计算架构 (compute unified device
architecture, CUDA) 对 GPU 硬件架构进行抽象化建模, 充当应用程序与 GPU 之间的桥梁. CUDA 编程模型将 32 个
线程组织为线程组 (warp), 采用单指令多线程 (single instruction multiple thread, SIMT) 执行机制. 在 CUDA 架构
中, 线程块 (block) 由多个线程组构成, 各线程块分别被分配至特定流式多处理器并行执行.
现代 GPU 通常包含两类常用的计算核心: CUDA 核心与 Tensor 核心. 其中, CUDA 核心作为通用计算任务的
主要执行单元, 而 Tensor 核心则是为支持高效矩阵运算专门设计的, 其能在单个时钟周期内完成固定尺寸矩阵的
乘法运算. GPU 存储层次由全局内存 (global memory)、共享内存 (shared memory) 及寄存器 (register) 构成: 全局
内存虽具备 GPU 中最大存储容量, 但其读写带宽相对较低; 共享内存可供同一线程块内所有线程访问, 具有更高
的带宽特性; 寄存器作为存储结构中访问速度最快的类型, 其存储空间一经声明即私有于各个线程.

3 GPU 加速的高维向量聚类算法
本节介绍 GPU 加速的高维向量数据聚类算法. 该算法分为 3 个模块, 分别进行 K 近邻图索引构建、数据分
区、并行聚类计算. 算法流程如图 2 所示. 首先, 基于向量数据集进行 GPU 加速的 K 近邻图索引构建, 以利用 K
近邻图加速后续 DBSCAN 算法的近邻计算 (第 3.1 节). 同时, 为了充分利用 GPU 的并行性, 采用 K-means 树分区
算法将向量数据集进行分区, 各分区分配给 GPU 中不同的线程块并行独立计算 (第 3.2 节). 在各分区内独立进行