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

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

注微调前与目标数据点相近的数据, 从而避免遍历所有数据点.
为此, 本文提出了一种基于乘积量化的候选数据点定位方法, 通过快速缩小搜索范围来提升效率. 直观来说,
确定哪些数据点可能成为某一数据点的“新邻居”, 可以通过聚类进行优化. 比如首先将数据点进行聚类, 然后检查
每个数据点所属簇内的数据点. 由于微调后的嵌入变化通常较小, 因此数据点的新邻居很可能集中在其所在簇内
的邻近区域.
然而, 直接对数据进行聚类会引入误差, 主要原因是大多数数据点并不位于聚类中心, 这可能导致一些不在同
一簇中但与其距离较小的点被忽略, 进而影响最终的 K 近邻图质量. 为了解决这一问题, 另一种思路是为每个数
据点维护一个候选邻居集合, 包含距离其较近的数据点. 这个思路可以看作是为每个数据点维护一个更大的近邻
列表. 但当近邻列表的大小增加时, 计算和存储开销也会显著增大.
为了有效解决这一问题, 本文提出了一种基于乘积量化 [19,20] 的方法, 用于限定每个数据点的候选邻居集合, 从
而避免无谓的全局搜索. 如图 3 所示, 乘积量化通过将每个数据点的向量分割为多个子向量, 并计算这些子向量与
预先计算的聚类中心的距离来实现数据的聚类和划分. 具体来说, 假设 D 维向量被分为 M 个子向量, 每个子向量
D
的维度为 . 每个划分后的子向量会被聚类到 c 个聚类中心中, 并通过与其距离最近的聚类中心的下标进行编码.
M
由此, 每个数据点都会被转换为一个长度为 M 的 PQ 编码, 表示每个子向量对应的聚类中心编号. 以图 3 中的例子
来说, 原始的向量被划分为 M=4 个子向量, 在图中表示为不同的颜色, 每个子向量独立地由其最近的聚类中心表
示, 因此原始的向量被子向量分别对应的聚类中心编码为 4 个整数下标.
此外, PQ 中各个子向量的聚类中心之间的距离会在预处理阶段被计算并存储. 由此, 对于两条使用 PQ 编码
过的数据, 其近似距离可以通过查聚类中心之间的距离表, 以 O(M) 的复杂度计算. 与精确计算的 O(D) 复杂度相
D
比, 这种方法能够加速 倍.
M
● 快速判断是否需要计算实际距离. 为了提高计算效率, 在为目标点判断采样数据时基于建立的乘积量化结
果进行过滤, 从而用较低的代价避免与距离较远的数据点计算距离. 作为辅助, 在预处理阶段, 本文为每条数据计
算并存储其每个子向量与其前 λ 近的 PQ 聚类中心编号, 其中, λ 是一个超参数 (例如, 取 λ=0.5c 表示取前 50% 近
的聚类中心, λ 的大小与微调程度相关, 微调程度越大, λ 也取较大). 然后, 在 K 近邻图的调整阶段, 本文通过算法
1 判断是否需要进一步计算采样点与目标点的实际距离.

算法 1. 判断采样数据是否需要计算与目标点的实际距离.
输入: 目标点及其 PQ 编码, 采样数据及其 PQ 编码, 检查阈值 θ;
输出: 是否需要计算实际距离.
1. 检查采样数据的 PQ 编码是否每一个都是离目标点 PQ 编码前 λ 近的
λ 近 then
2. If 均为前
3. Return True
4. else
5. dist ← 使用目标点与采样点的 PQ 编码计算近似距离
dist ← 目标点到当前第 K 近邻的距离
′
6.
′
7. If dist −dist > θ then
8. Return False
9. else
dist −dist ′
10. Return 随机数 (0,1) >
θ
11. end
12. end