携手创造，一起生长！这是我参与「日新计划 8 月更文应战」的第2天，点击查看活动概况>>
简介
跟着深度学习的开展和普及，很多非结构数据被表明为高维向量，并经过近邻查找来查找，完成了多种场景的检索需求，如人脸辨认、图片查找、商品的推荐查找等。另一方面跟着互联网技术的开展及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区分子向量，核算子向量和对应段的一切簇心的间隔，得到间隔表（mk*矩阵）
- 遍历样本库中的向量，依据间隔表，核算每个样本与查询向量的间隔和回来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库是构建近邻检索服务的比较好的挑选。
总结
本文展现了当时比较常见的几种近邻查找算法，并简略分析了各算法的原理；跟着深度学习的不断开展，不同场景对近邻查找的需求越来越多，必定会有新的算法不断地涌现，每种算法有它适合的场景，在挑选不同算法时需求结合事务的需求，如数据量的大小，召回的作用，功能，资源消耗等各方面的要素，经过了解不同算法的完成，能够挑选更适合当时事务的算法。
*文/张林
