6

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

 2 years ago
source link: https://www.cnblogs.com/ERKE/p/16755980.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

转载请注明出处

我们从最最最简单的场景开始，假设在一个二维平面上，现有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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK