做网站每年需要多少维护费,江西省工程建设信息官方网站,河北seo网站优化价格,wordpress禁止保存图片HNSW算法概述
HNSW#xff08;Hierarchical Navigable Small Word#xff09;算法算是目前推荐领域里面常用的ANN#xff08;Approximate Nearest Neighbor#xff09;算法了。其目的就是在极大量的候选集当中如何快速地找到一个query最近邻的k个元素。
要找到一个query的…HNSW算法概述
HNSWHierarchical Navigable Small Word算法算是目前推荐领域里面常用的ANNApproximate Nearest Neighbor算法了。其目的就是在极大量的候选集当中如何快速地找到一个query最近邻的k个元素。
要找到一个query的k个最近邻元素一个朴素的思想就是我去计算这个query和所有的总量N 个候选元素的距离然后选择其中的前k 个最小元素这个经典算法的算法复杂度是O(Nlog(k))显然这个算法复杂度实在是太高了无法适用于实际的使用场景。
而要解决这个问题可以有多种实现方法这里所要说的HNSW算法就是目前比较常用的一种搜索算法它算是其前作NSW算法的一个升级版本但是两者的本质都是基于一个朴素的思路就是通过图连接的方式给所有的N 个候选元素事先地定义好一个图连接关系从而可以将前述的算法复杂度当中的N 的部分给减小掉从而优化整体的检索效率。
其整体的一个图结果可以用下图进行表达 解决的问题做高效率相似性查找。推荐系统中如何找到与用户query最相近的几个item然后推荐出去【也就是推荐出与用户搜索的类似的/用户感兴趣的商品】。
解决方法有AnnoyKD-Tree LSH PQNSW HNSW等。
近似最近邻搜索算法Approximate Nearest Neighbor SearchANNS发展近邻图(Proximity Graph)– NSW -- Skip List -- HNSW 近似最近邻搜索算法Approximate Nearest Neighbor SearchANNS
1. 近邻图(Proximity Graph)
近邻图(Proximity Graph) 最朴素的图算法
思路 构建一张图 每一个顶点连接着最近的 N 个顶点。 Target 红点是待查询的向量。在搜索时 选择任意一个顶点出发。 首先遍历它的友节点 找到距离与 Target 最近的某一节点 将其设置为起始节点 再从它的友节点出发进行遍历 反复迭代 不断逼近 最后找到与 Target 距离最近的节点时搜索结束。 存在的问题
图中的K点无法被查询到。如果要查找距离Target 红点最近的topK个点 而如果点之间无连线 将影响查找效率。D点有这么多友节点吗 增加了构造复杂度。谁是谁的友节点如何确定如果初始点选择地不好比如很远将进行多步查找。 2. NSW算法原理
NSW即没有分层的可导航小世界的结构Navigable-Small-World-Graph 。
针对上面的问题解决办法
某些点无法被查询到 - 规定构图时所有节点必须有友节点。相似点不相邻的问题 - 规定构图时所有距离相近到一定程度的节点必须互为友节点。关于某些点有过多友节点 - 规定限制每个节点的友节点数量。初始点选择地很远 - 增加高速公路机制。
2.1 NSW构图算法
图中插入新节点时通过随机存在的一个节点出发查找到距离新节点最近的m个节点规定最多m个友节点m由用户设置连接新节点到这最近的m个节点。节点的友节点在新的节点插入的过程中会不断地被更新。 m3每个点在插入时找3个紧邻友点。
第1次构造图为空随机插入A初始点为A。图中只有A故无法挑选友节点。插入BB点只有A点可选所以连接BA。
第2次构造插入FF只有A和B可以选所以连接FAFB。
第3次构造插入CC点只有ABF可选连接CACBCF。
第4次构造插入E从ABCF任意一点出发计算出发点与E的距离和出发点的所有“友节点”和E的距离选出最近的一点作为新的出发点如果选出的点就是出发点本身那么看我们的m等于几如果不够数就继续找第二近的点或者第三近的点本着不找重复点的原则直到找到3个近点为止。找到了E的三个近点连接EAECEF。
第5次构造插入D与E点的插入一模一样都是在“现成”的图中查找到3个最近的节点作为“友节点”并做连接。
第6次构造插入G与E点的插入一模一样都是在“现成”的图中查找到3个最近的节点作为“友节点”并做连接。
在图构建的早期很有可能构建出“高速公路”。
第n次构造在这个图的基础上再插入6个点这6个点有3个和E很近有3个和A很近那么距离E最近的3个点中没有A距离A最近的3个点中也没有E但因为A和E是构图早期添加的点A和E有了连线我们管这种连线叫“高速公路”在查找时可以提高查找效率当进入点为E待查找距离A很近时我们可以通过AE连线从E直接到达A而不是一小步一小步分多次跳转到A。
结论一个点越早插入就越容易形成与之相关的“高速公路”连接越晚插入就越难形成与之相关的“高速公路”连接。
这个算法设计的妙处就在于扔掉德劳内三角构图法改用“无脑添加”NSW朴素插入算法降低了构图算法时间复杂度的同时还带来了数量有限的“高速公路”加速了查找。 2.2 NSW查找算法 图中的边有两个不同的目的
Short-range edges用作贪婪搜索算法所需的近似 Delaunay 图。Long-range edges用于贪婪搜索的对数缩放。负责构造图形的可导航小世界NSW属性。
优化查找
建立一个废弃列表visitedSet在一次查找任务中遍历过的点不再遍历。建立一个动态列表result把距离查找点最近的n个点存储在表中并行地对这n个点进行同时计算“友节点”和待查找点的距离在这些“友节点”中选择n个点与动态列表中的n个点进行并集操作在并集中选出n个最近的友点更新动态列表。 推荐算法HNSW算法简介-CSDN博客
检索模型-粗排HNSW_hnsw模型-CSDN博客
