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

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

点的计算限制在分区内, 最终合并各分区聚类结果. 例如, Mr. Scan [29] 使用 MRNet 树将数据划分至各 GPU 节点,

各分区需在分区边界节点的基础上进一步扩展 ε 的范围, 称为 ε 邻域, 以保证准确识别核心点. 各 GPU 节点使用
改进后的 CUDA-DClust 进行局部 DBSCAN 的计算, 最终通过判断分区间重叠数据点的性质进行簇归并; GSCAN [42]
则使用网格划分数据, 计算簇时仅计算当前单元格及其邻近单元格点的距离; GPU Multi-grid [43] 扩展了网格的定
义, 实现了多层网格划分, 进一步限制搜索范围, 减小计算开销; Hybrid-DBSCAN [44] 同样采用基于网格的方式, 不
同的是其设计了一种 GPU-CPU 异构执行策略, 使用 GPU 计算近邻点, 而使用 CPU 进行聚类的计算; 为了提高分
区效率, CudaSCAN [45] 采用并行 KD 树划分数据集, 划分时与 Mr. Scan 采用相同的扩展 ε 邻域的策略, 合并簇时仅
需检查各分区间的重叠数据. 分区聚类计算虽限制了近邻计算范围, 但其仍需遍历分区内所有数据以计算各数据
点的近邻. 为了进一步减小近邻计算代价, 基于索引的聚类计算通过构建基于 GPU 的索引实现近邻查询的加速,
进而加速 DBSCAN 的计算. 例如, FDBSCAN 与 FDBSCAN-DenseBox [46] 使用层次包装盒树 (bounding volume
hierarchy based on tree, BVH) 作为索引结构, 每个线程分别负责一个数据点的近邻搜索; cuML-DBSACN [47] 则采用
一种更适合 GPU 并行计算的索引——随机球形覆盖 (random ball cover), 进一步提高了计算效率. 尽管上述方法
通过不同路径提升性能, 其对于高维向量的聚类仍存在效率低下的问题.

2 基础知识
本节将在第 2.1 节介绍基于密度的聚类算法的相关概念和基础知识, 在第 2.2 节介绍利用 K 近邻图作为索引
的 DBSCAN 算法的相关概念.
2.1 基于密度的聚类算法

DBSCAN 采用基于密度的思想, 将簇定义为密度相连点的最大集合, 能够发现任意形状的聚类, 并识别噪声
点. DBSCAN 算法基于以下重要概念实现聚类.
定义 1 ( ε 邻域). 给定数据点 p, 一个距离参数 ε, 数据点 p 的 ε 邻域为所有与 p 的距离小于等于 ε 的数据点组
成的集合, 即 N ε (p) = {q|d(p,q) ⩽ ε}, 其中 d 为距离函数.
定义 2 (核心点). 给定整数 minPts, 对于数据点 p, 如果 N ε (p) ⩾ minPts, 则称数据点 p 为核心点; 反之, 如果
N ε (p) < minPts, 则称 p 为非核心点.
定义 3 (边界点). 对于非核心点 q, 若存在一个核心点 p, 使得 q 位于 p 的 ε 邻域内, 即 q ∈ N ε (p), 则称数据点 q
为边界点.
定义 4 (噪声点). 对于非核心点 q, 若其不在任意一个核心点的 ε 邻域内, 则称该点为噪声点.
定义 5 (密度直达). 若 p 为核心点, q 位于 p 的 ε 邻域内, 则称 q 可由 p 密度直达.
定义 6 (密度可达). 若存在核心点序列 {p 1 , p 2 ,..., p n }, 其中, p 1 = p p n = q, 序列内任意一个点 p i +1 都可由 p i
,
密度直达, 则称 q 由 p 密度可达.
定义 7 (密度相连). 若存在数据点 o, 使得点 p 和点 q 都可由 o 密度可达, 则称 p 与 q 密度相连.
定义 8 (基于密度的聚类). 设集合 C 是所有数据点构成的集合的一个子集, 称集合 C 是一个基于密度的聚类
簇, 当且仅当 C 满足以下 3 个条件: (1) C 中包含至少一个核心点 p; (2) C 中任意两个数据点均密度相连; (3) 不存
s
在数据点 s < C, 且 与 C 内的数据点密度相连.
后文图 1 对上述定义进行展示, 该示例将 minPts 设为 3, 共形成 2 个簇 C 1 与 C 2 . 例如, 因为 p 1 位于 p 2 的 ε 邻
域内, 所以 p 1 可由 p 2 密度直达. 而由于存在核心点序列{p 3 , p 2 , p 1 }, 其中, p 2 可由 p 3 密度直达, p 1 可由 p 2 密度直
达, 所以 p 1 由 p 3 密度可达. 类似地, p 5 由 p 3 密度可达. 由于点 p 1 和点 p 5 都可由 p 3 密度可达, 因此 p 1 与 p 5 密度相连.
2.2 基于 K 近邻图的 DBSCAN 算法
为了实现基于 K 近邻图的 DBSCAN 算法, 本文在不改变结果的前提下对第 2.1 节的核心点定义进行了修改.
定义 9 (K 近邻图核心点). 给定正整数 minPts < k, 对于任意数据 p, 其在 K 近邻图中的邻居列表 N k (p) 按距离
升序排序, 若 p 与其邻居列表中第 minPts 个点 N minPts (p) 的距离 d(p,N minPts (p)) ⩽ ε, 则 p 为 K 近邻图核心点.
k k