【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居

时间:2022-10-05 18:06:45

转载请注明出处

我们从最最最简单的场景开始,假设在一个二维平面上,现有N个点,如下图所示
【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居
现在给你一个点,求K个最近的点(欧式距离),如下图所示
【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居

肉眼很容易可以看出,以query点为中心画个圆,慢慢往外扩展,直到包含K个点,然后这K个点就是最近的点。
看起来很容易,但这得给算法实现个眼睛啊!

二、暴力解法

这里需要遍历所有的N个点跟query点分别求个距离,然后找出K个最相近的点。
咱们专注于这个算法本身,假设距离计算的复杂度为1,那么暴力解法的复杂度为:N + NlogK

假设N很大,在没有考虑距离计算的复杂度前提下,其实这复杂度已经很高了。那如果是单机,估计实现不了在线实时计算了,有没有办法解决呢?

三、分布式解法

把点随机分布到不同机器上,然后求解的时候每台机器都算个top K出来,再合并。如下图所示:
【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居

其实这样整体复杂度并没有变化,只是利用机器资源换取时间,理论上只要机器够多,耗时还是能降低很多的。

如果没有很多机器资源,可以考虑下更优的解法。

四、分布式解法优化——IVF

既然都已经把N个点划分成A(3)个区域了,划分方法能否考虑下距离?比如最简单的按距离划分,如图所示:
【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居
这时我们在检索的时候,只需要在最近的B(>A=3)个区域暴力检索就行了。
如果A=3,B=1,那么复杂度就是: (N+NlogK)/3,这个复杂度是有很大的降低的,但是会有一个缺点,精度有所降低。如果上图所示,划分后的结果,会导致一个点出错~

实际构建区域步骤

  1. 对所有点集合抽样一份小的集合。
  2. 利用聚类算法(一般是Kmean)得出A个聚类中心点。
  3. 把所有点都按距离分配到每个聚类中心,得到A个点集合。

实际检索步骤

  1. 在A个聚类中心点中,暴力找出B个最近的聚类中心点
  2. 只在B个聚类中心点所属点集中,暴力检索最近的top K个点

实际复杂度

(N + NlogK)B/A + A
A为聚类中心个数,B为检索查询的聚类中心数

虽然这种方法已经大大降低了复杂度,但还有更有的方式吗?

五、图论算法——NSW

其实就是把N个点按一定规则连边,构成一个有向图,如下图所示:
【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居

蓝色点为点集,黑色边为有向边,具体如何构造这个有向边后边再说,先说下检索流程

检索流程

如下图所示:
【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居

  1. 给出一个query点,如上图 红色点

  2. 初始化一个点集访问记录存储

  3. 初始化两个优先队列,一个存储结果候选集,只存K个元素,一个存储遍历候选集

  4. 随机找一个点,当作进场开始点(如上图右下角红点,entry point)

  5. entry point 加入遍历候选集,如果它并不是标记为删除的,把它放入结果候选集;

  6. 从遍历候选集中取出距离query点最近的点,遍历与它所有关联的点,检查是否已经访问过

    • 如果它已经访问过,直接跳过
    • 如果没有访问过加入遍历候选集,如果关联点并不是标记为删除的,把它放入结果候选集。
  7. 重复第6步骤,直到遍历候选集中距离query最近的点,都比结果候选集距离query最远的点距离query大,并且结果候选集已经足够K个点就结束。

新增构建步骤

  1. 给出一个待新增的点 A
  2. 在图中检索出top k个点,k = ef_construction
  3. 从点A 连接其中M_个点,这M_个点从 top k里面选择,后面简称M_个点里面当前遍历的点为点B
  4. 遍历每条新增连边,检查是否有相应的反向连边,也就是从点B到点A的连边
    • 如果有就跳过
    • 如果没有就给反向边连上
      • 如果点B的连边没有超过M_, 直接连上就行
      • 如果点B的连边超过了M_, 需要重新选择M_个点,保证点B只有外出M_条边

简单的说,其实就是找出top k近邻,然后连边。重点问题在于,如果 K > M_,怎么选择更加合适的邻居呢?

最简单的方式:按距离排序,选择跟新增点最近的那些。这样有可能形成孤岛,导致整个图并不是连通图,有没有更好的方式呢?

优质邻居选择方式

如下图所示:
【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居

  1. 给出一个query点(黄色),top K结果候选集(红色)

  2. 初始化一个结果候选集的优先队列,一个优质邻居列表

  3. 从结果候选集取出一个点,判断该点与query的距离,是不是比该点与优质邻居的距离都大

    • 如果是,加入优质邻居列表
    • 如果不是,丢弃

其实就是把连边的点尽量分散。

更新点构建步骤

  1. 初始化两个set 集合A、B
  2. 集合A存更新点的所有邻居,集合B存更新点的 所有邻居 & 所有邻居的邻居
  3. 给集合A里面的所有点,从集合B里面重新选择合适的邻居
  4. 重新跑一遍新增点的流程,见上面的新增

六、图论算法优化——HNSW

其实它就是 Skip list + NSW,我们先回顾下跳表的结构吧。

跳表

【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居
这是一种很常见的数据结构,这里就不详细描述了。

真正的HNSW结构

【近似最近邻搜索】在茫茫点集中,怎么找到你的邻居
如上图所示,其实HNSW 就是 Skip List + NSW。
跳表也是分层的,但是真正的跳表每一层是一条有序列表。
然而在HNSW中,也是跟跳表一样分层,这里每一层就是一个NSW有向图。

加上跳表思想后,nsw的操作只有一个不同的点。检索进场点是上一层的得到的最近的点,当然最上面一层还是随机点进场。

这种算法复杂度理论上是logN的,当然也只是理论上哈,而且又一定的精度损失~

实际场景

实际场景上

  • 如果内存够大能撑住NSW所需的内存,可以考虑直接上HNSW
  • 如果内存不够,可以考虑IVF + HNSW 或者 直接随机分布 + HNSW