浅谈实值向量的近邻检索方案

顾亚文

（金肯职业技术学院人工智能与信息工程学院，江苏 南京 211156）

0 引言

半导体与互联网技术的飞速发展使数据信息规模呈爆发性增长，并进一步推动了人工智能技术的进步。如何有效地从这些飞速增长的数据中挖掘有效的信息是一个非常重要的挑战，而作为数据挖掘方案的前置技术——近邻检索问题（即如何从海量数据中找出与查询数据最相近的一些数据）一直受到学术界与工业界的关注。

由于精确寻找最近向量的计算代价过高，因此现有研究聚焦于近似近邻检索问题，其严格定义如下：给定一个欧式空间E中的点集，包括个点，对进行一定的预处理，从而能够快速返回与给定查询点最接近的点，使（，）≤（1+）（，）。其中，为与最接近的点，、∈；为给定的距离度量函数；为某个预设常量。

在实际应用中，通常需要找到最接近的若干个点（例如个），而非单个点；即关注近似近邻检索问题。在超过50年的发展过程中，三类方案（树形索引、哈希散列以及近邻图）被证明适合于该问题，其总体思路如图1 所示。该文对三类方案中的主流方案进行介绍。

图1 三类主流方案总体思路

1 树形方案

在近邻检索方案中，为了保证较高的检索效率，三类方案都需要在实际检索前对数据集进行较长时间的索引构建工作；因此，描述1 个近邻检索方案须关注2 个问题：1） 如何构建索引。2） 如何进行检索。为方便起见，该文相关字母解释如下：为向量的维度；为待检索向量集合；为中维点的个数；为需要返回的结果个数。具体来说，树形方案可按索引划分方式进一步划分为以下3 种类型。

1.1 基于平衡树的树形索引

树形方案可追溯到标量（即=1）下的经典数据结构。通过二分法可以在对数复杂度上找到有序数组中的某个值，即在1 个平衡二叉树中对数次查询即可找到叶子节点。受平衡树思想的启发，kd 树最早为维向量构造索引，可以将其视为平衡二叉树的高维拓展。在构造索引时，选择向量的某一个维度进行划分，然后随着深度增加不断变化选择的维度，直至划分的2 个子区域都不存在新的点。在检索时，先根据每个维度的切分点坐标来判断深入方向，直至找到叶节点；再递归地回退，检查现有找到的最近点与查询节点为半径所形成的超球体是否可能与父节点的另一子节点所形成的区域相交，如果相交，则移动到对应子区域重复执行上述操作，否则，向父节点继续回退；当回退至根节点时，即找到了最近邻点。

当较低而较高时，超球体相交的可能性较低；但维度上升时，出现相交的概率快速上升，从而使kd 树近乎于普通的线性扫描。为应对上述问题，Arya 等人提出使用优先检索策略，其索引构建过程与kd 树相同；而在检索时，维护1 个优先队列，先将根节点放入优先队列，再重复以下步骤：1） 从队列中找到高优先级节点对应的子树，然后尝试在该子树中找到更好的最近子节点，并比较每个遇到的节点，从而尽可能更新优先队列。2） 当优先队列为空时，将找到的节点视为最近子节点。通过限制优先队列的长度，可在尽可能保证精度的同时，避免检索效率降至线性扫描。Silpa-Anan 等人进一步指出优先搜索在返回较多结果时精度会大幅降低，并指出其原因是树中的节点在优先队列中相互关联，从而带来误差。为了避免该问题，他们提出利用多个搜索树来共同查询，每个搜索树都为原始树的一个随机旋转；他们还指出主成分分析降维后的树可有效避免在某些不重要的维度上出现相交的情况。

1.2 基于聚类的树形索引

受聚类方案的启发，Nister 等人指出可以使用k 均值聚类并按照聚类中心对中的点进行划分；而对每个小类又可继续进行聚类划分，直至每类中的点数量少于某个固定值。此时，中的点根据聚类中心自然地形成1 颗树，检索时通过与聚类中心进行距离度量来避免进入无用的子树。后续工作结合该思路与优先队列的思想进一步编写了开源库FLANN，并成为OpenCV 中的重要组成工具。

1.3 结合支撑点技术的树形索引

在度量空间的近邻检索问题中，由于缺少一般意义的坐标，因此常常使用支撑点技术来加快最近邻检索。具体来说，先选出若干个支撑点，计算支撑点与中的点以及支撑点之间的距离；在检索时，通过基本的三角不等式或托勒密不等式就可以快速确定大量中的点不可能成为最近邻点，从而达到快速过滤的效果。

Arora 等人的工作综合使用了包括支撑点技术在内的多种想法，其索引构建过程如下：首先，将点投影到希尔伯特曲线上，即将高维值降至一维希尔伯特曲线值，由于希尔伯特曲线可能会破坏部分相邻性，因此，不完全使用维空间上的希尔伯特曲线，而分别使用部分维度生成多条希尔伯特曲线，以避免出现过度过滤的现象。其次，根据希尔伯特曲线值生成B+树的非叶节点，使用支撑点技术计算节点与支撑点间的距离，并将距离值存放在生成的B+树的叶子节点中。在检索时，首先通过B+树非叶节点过滤，此时也已隐含利用了希尔伯特曲线投影的过滤。其次，使用支撑点组成的不等式进一步过滤。最后，计算未被过滤掉的点的实际距离，以得到最终结果。可以看出，该方案充分考虑了多种已有方案的过滤手段，在提升检索效率的同时，也导致了其参数设置变得复杂，且与硬件紧密相关。

2 哈希散列

与树形索引不同，哈希类方案希望将中的点投影到键值对表中。其中，键常被称为“桶号”，而值为在该桶中的向量ID 号；在检索时，先计算检索点所对应的桶号，再对该桶号对应的所有向量的实际距离进行度量。因此，哈希类方案一方面试图寻找一种投影方式，使高维空间中相近的点投影至一维时，其桶号的值相同；另一方面，还需要考虑在确定投影方式后如何提高准确率。

2.1 静态绑定框架

单个投影函数无法保证较高的精度，因此通常随机生成个同分布的投影函数，即在索引构建时生成张表；在检索时，得到每张表中查询向量对应的桶号，度量检索向量与对应桶中靠前的点的实际距离，以获得结果。上述策略被称为静态绑定框架，其存在2 个明显缺陷：1） 需要计算很多张表才能维持较好的精度，计算过于复杂。2） 如果所有桶中没有足够多的点，那么就无法完成近似k 近邻检索，须重新生成索引表。上述问题本质上是由索引表在构建完成后完全固定、缺少灵活性所造成的。

2.2 动态绑定框架

3 近邻图方案

上述2 种方案本质上都是通过划分空间来避免检索时计算无意义的距离；然而，如果将中的点视作一个整体，那么这些点会构成一张图。近邻图类方案试图通过仅在图上计算来找到相近的点。

众所周知，图由若干点以及点上的边组成。图类方案中通常使用爬山算法来寻找近邻点。具体来说，其遵循的思路是邻居的邻居很可能是邻居；在检索时，从随机点或某个固定点出发，将距离较小的相邻点放入一个优先队列中；然后不断从优先队列中距离最小的点出发，寻找新的邻居直至收敛到个固定值。因此，检索的时间复杂度与2 个参数有关，即图中每个点的平均出度、找到想要的点需要经过的跳数。接下来主要介绍在图方案中构建索引的方法，默认其在检索时使用爬山算法或类似变体。现有的方案主要基于4 种特殊的图，即德劳内图、相对近邻图、可通航小世界网络和单调搜索网络。

3.1 德劳内图

德劳内图指如果图中任意3 点两两相连，则其形成的外接圆中无点集中的其余点。德劳内图虽适用于爬山算法，但当维度较高时，其十分接近于全连接图，因而构图效率与检索效率都较低。虽然如此，后续实用的图结构（例如K 近邻图）往往简化自德劳内图。K 近邻图指图中每个点与其最接近的个点相连。虽然这是一个检索前可完成的工作，但与前方案类似，得到精确的K 近邻图计算代价过高。Dong 等人提出一种重要的近似K 近邻图生成方案。其核心思路是将自己的邻居介绍给另一个邻居：先随机生成图中的边，然后不断借助图中所有点当前的相邻节点的相邻节点信息进行更新，以得到更准确的自身相邻节点。该方案在数学上论证了这样的迭代过程在很大程度上可以保证近邻图的精确性，其时间复杂度一般记为（）。

3.2 可通航小世界网络

3.3 相对近邻图

在相对近邻图中，如果2 点间存在边，则当且仅当该边为半径时，以两端点为圆心做圆形成的交集空间内无图中其他点。相对近邻图的平均出度为常数，且仅与数据维度有关。MALKOV 等人在可通航小世界图的基础上，进一步结合了相对近邻图的思路对索引构建的流程进行改进，即添加新节点时不完全按照最近距离连接，而是加上相对近邻图的约束，这带来更多高质量的“捷径”。

3.4 单调搜索网络

基于图的方案通常需要将所有节点读取至内存中，因此所占资源较高；但由于这一类方案在效率与精度上表现出的显著优势以及半导体技术的飞速进步，因此这一类方案更被工业界认可。此外，近年来有乘积量化类方案可用于压缩索引，以辅助快速检索。可以将图方案与这一类策略结合，以获得资源与精度的权衡。最后，将三类方案的总体优、缺点进行归纳，见表1。

表1 三类方案的总体优劣分析

4 结语

该文针对近邻检索问题，从索引构造方法与检索流程上对现有的主流或经典方案进行梳理。需要注意的是，各类方案在不同的现实维度中存在自身的优势，因此在实际应用中需要根据数据的可能分布、计算机的性能等各项参数进行细致地分析。近邻检索仍是一个不断发展的领域，希望该文能够让读者从宏观角度了解索引构造思路。