共计 3161 个字符，预计需要花费 8 分钟才能阅读完成。
简介
随着深度学习的倒退和遍及，很多非构造数据被示意为高维向量，并通过近邻搜寻来查找，实现了多种场景的检索需要，如人脸识别、图片搜寻、商品的举荐搜寻等。另一方面随着互联网技术的倒退及 5G 技术的遍及，产生的数据呈爆发式增长，如何在海量数据中精准高效的实现搜寻成为一个钻研热点，各路前辈专家提出了不同的算法，明天咱们就简略聊下以后比拟常见的近邻搜索算法。
次要算法
Kd-Tree
K-dimension tree，二叉树构造，对数据点在 k 维空间（如二维 (x，y)，三维(x，y，z)，k 维(x，y，z..)）中划分。
构建过程
确定 split 域的值(轮询 or 最大方差) 确定 Node-data 的域值（中位数 or 平均值）确定左子空间和右子空间 递归结构左右子空间
查问过程
进行二叉搜寻，找到叶子结点 回溯搜寻门路，进入其余候选节点的子空间查问间隔更近的点 反复步骤 2，直到搜寻门路为空
性能
现实状况下的复杂度是 O(K log(N)) 最坏的状况下（当查问点的邻域与宰割超平面两侧的空间都产生交加时，回溯的次数大大增加）的复杂度为维度比拟大时，间接利用 K - d 树疾速检索（维数超过 20）的性能急剧下降，简直靠近线性扫描。
改良算法
Best-Bin-First：通过设置优先级队列（将“查问门路”上的结点进行排序，如按各自宰割超平面与查问点的间隔排序）和运行超时限定（限定搜寻过的叶子节点树）来获取近似的最近邻，无效地缩小回溯的次数。采纳了 BBF 查问机制后 Kd 树便能够无效的扩大到高维数据集上。
Randomized Kd tree：通过构建多个不同方向上的 Kd tree，在各个 Kd tree 上并行搜寻局部数量的节点来晋升搜寻性能（次要解决 BBF 算法随着 Max-search nodes 增长，收益减小的问题）
Hierarchical k-means trees
相似 k -means tree，通过聚类的办法来建设一个二叉树来使得每个点查找时间复杂度是 O(log n)。
构建过程：
随机抉择两个点，执行 k 为 2 的聚类，用垂直于这两个聚类核心的超平面将数据集划分 在划分的子空间内进行递归迭代持续划分，直到每个子空间最多只剩下 K 个数据节点 最终造成一个二叉树构造。叶子节点记录原始数据节点，两头节点记录宰割超平面的信息
搜寻过程
- 从根节点开始比拟，找到叶子节点，同时将门路上的节点记录到优先级队列中
- 执行回溯，从优先级队列中选取节点从新执行查找
- 每次查找都将门路中未遍历的节点记录到优先级队列中
- 当遍历节点的数目达到指定阈值时终止搜寻
性能
- 搜寻性能不是特地稳固，在某些数据集上体现很好，在有些数据集上则有些差
- 构建树的工夫比拟长，能够通过设置 kmeans 的迭代次数来优化
LSH
Locality-Sensitive Hashing 高维空间的两点若间隔很近，他们哈希值有很大概率是一样的；若两点之间的间隔较远，他们哈希值雷同的概率会很小.
个别会依据具体的需要来抉择满足条件的 hash 函数，(d1,d2,p1,p2)-sensitive 满足上面两个条件（D 为空间间隔度量,Pr 示意概率）：
- 若空间中两点 p 和 q 之间的间隔 D(p,q)<d1，则 Pr(h(p)=h(q))>p1
- 若空间中两点 p 和 q 之间的间隔 D(p,q)>d2，则 Pr(h(p)=h(q))<p2
离线构建索引
抉择满足(𝑅,𝑐𝑅,𝑃1,𝑃2)-sensive 的哈希函数；依据对查找后果的准确率（即相邻的数据被查找到的概率）确定哈希表的个数𝐿，每个 table 内的 hash functions 的个数（也就哈希的键长𝐾），以及跟 LSH hash function 本身无关的参数；利用下面的哈希函数组，将汇合中的所有数据映射到一个或多个哈希表中，实现索引 的建设。
在线查找
将查问向量𝑞通过哈希函数映射，失去相应哈希表中的编号 将所有哈希表中相应的编号的向量取出来，（保障查找速度，通常只取前 2𝐿）对这 2𝐿个向量进行线性查找，返回与查问向量最类似的向量。
查问耗时次要为：
计算 q 的 hash 值（table id）+ 计算 q 与 table 中点的间隔
查问成果方面因为损失了大量原始信息从而升高检索精度。
PQ
product quantization，把原来的向量空间合成为若干个低维向量空间的笛卡尔积，并对合成失去的低维向量空间别离做量化（quantization），这样每个向量就能由多个低维空间的量化 code 组合示意。
须要选取最优的量化算法，咱们熟知的 k -means 算法就是一个靠近最优化的量化算法。
量化
应用 k -means 进行量化的过程
- 将原始向量切分为 m 组，每组内应用 k -means 聚类，产出 m 组，每组多个聚类核心
- 将原始向量编码为 m 维向量，向量中每个元素代表所在组聚类核心的 id
查问过程
- 将搜寻 query 划分子向量，计算子向量和对应段的所有簇心的间隔，失去间隔表（m×k* 矩阵）
- 遍历样本库中的向量，依据间隔表，计算每个样本与查问向量的间隔和返回 k 个间隔最靠近的样本
间隔计算
SDC(symmetric distance computation)，对称的间隔计算方法，对 query 向量和样本库中的向量都进行 PQ 量化，同时会在构建阶段会计算出每组向量各个聚类核心的间隔，生成 k * k 的间隔表，在查问阶段计算 query 向量和样本库中的向量时，通过查表即可，缩小计算过程，但放大了误差。
ADC(Asymmetric distance computation)，非对称的间隔计算计划，只对样本库中的向量进行 PQ 量化，在查问阶段计算 query 向量和 m 组聚类核心的间隔，生成 m * k 的间隔表，而后查表计算与样本库中向量的间隔，因为须要每次对查问向量实时计算，减少计算开销，但误差小。
优化
IVFPQ，基于倒排的乘积量化算法，减少粗量化阶段，对样本进行聚类，划分为较小的 region，缩小候选集数据量（之前是须要遍历全量的样本，工夫复杂度为 O(N*M)）。
HNSW
在 NSW 算法之上进行改良的基于图的算法，应用分层的构造，在每层通过启发式办法来抉择某节点的街坊（保障全局连通性），使其形成一张连通的图。
建图流程
- 计算节点的最大档次 l；
- 随机抉择初始入口点 ep，L 为 ep 点所在的最大层；
- 在 L～l+ 1 层，每层执行操作：在以后层找到间隔待 插节点最近的节点 ep，并作为下一层的输出；
- l 层以下为待插元素的插入层，从 ep 开始查找间隔待插元素 最近的 ef 个节点，从中选出 M 个与待插节点连贯，并将这 M 个节点作为下一层的输出；
- 在 l -1～0 层，每层执行操作：从 M 个节点开始搜寻，找到间隔与待插节点最近的 ef 个节点，并选出 M 个与待插元素连贯
查问流程
- 从顶层到倒数第二层，循环执行操作：在以后层寻找间隔查问节点最近的一个节点放入候选集中，从候选集中选取出间隔查问节点最近的一个节作为下一层的入口点；
- 从下层失去的最近点开始搜寻最底层，获取 ef 个近邻点放入候选集中；
- 从候选集中选取出 topk。
实现
以后有比拟成熟的库实现了各种支流的近邻搜索算法，在我的项目中能够通过这些根底库来构建对应的近邻搜寻服务，其中应用比拟宽泛的是 faiss 库，由 Fackbook 开源，在反对不同算法的同时，也反对在超大规模数据集上构建 k 近邻搜寻以及反对 GPU 来减速索引构建和查问，同时社区沉闷，在思考到性能和可维护性，faiss 库是构建近邻检索服务的比拟好的抉择。
总结
本文展现了以后比拟常见的几种近邻搜索算法，并简略剖析了各算法的原理；随着深度学习的一直倒退，不同场景对近邻搜寻的需要越来越多，必定会有新的算法一直地涌现，每种算法有它适宜的场景，在抉择不同算法时须要联合业务的需要，如数据量的大小，召回的成果，性能，资源耗费等各方面的因素，通过理解不同算法的实现，能够抉择更适宜以后业务的算法。
* 文 / 张林
@得物技术公众号
