推荐算法:HNSW【推荐出与用户搜索的类似的/用户感兴趣的商品】

2023-12-11 23:04

本文主要是介绍推荐算法:HNSW【推荐出与用户搜索的类似的/用户感兴趣的商品】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

HNSW算法概述

HNSW(Hierarchical Navigable Small Word)算法算是目前推荐领域里面常用的ANN(Approximate Nearest Neighbor)算法了。其目的就是在极大量的候选集当中如何快速地找到一个query最近邻的k个元素

要找到一个query的k个最近邻元素,一个朴素的思想就是我去计算这个query和所有的总量N 个候选元素的距离,然后选择其中的前k 个最小元素,这个经典算法的算法复杂度是O(Nlog(k)),显然这个算法复杂度实在是太高了,无法适用于实际的使用场景。

而要解决这个问题,可以有多种实现方法,这里所要说的HNSW算法就是目前比较常用的一种搜索算法,它算是其前作NSW算法的一个升级版本,但是两者的本质都是基于一个朴素的思路,就是通过图连接的方式给所有的N 个候选元素事先地定义好一个图连接关系,从而可以将前述的算法复杂度当中的N 的部分给减小掉,从而优化整体的检索效率

其整体的一个图结果可以用下图进行表达:

解决的问题做高效率相似性查找。推荐系统中,如何找到与用户query最相近的几个item,然后推荐出去【也就是推荐出与用户搜索的类似的/用户感兴趣的商品】

解决方法有:Annoy,KD-Tree, LSH, PQ,NSW, HNSW等。

近似最近邻搜索算法(Approximate Nearest Neighbor Search,ANNS)发展:近邻图(Proximity Graph)–> NSW --> Skip List --> HNSW

近似最近邻搜索算法(Approximate Nearest Neighbor Search,ANNS)

1. 近邻图(Proximity Graph)

近邻图(Proximity Graph): 最朴素的图算法

思路: 构建一张图, 每一个顶点连接着最近的 N 个顶点。 Target (红点)是待查询的向量。在搜索时, 选择任意一个顶点出发。 首先遍历它的友节点, 找到距离与 Target 最近的某一节点, 将其设置为起始节点, 再从它的友节点出发进行遍历, 反复迭代, 不断逼近, 最后找到与 Target 距离最近的节点时搜索结束。

存在的问题:

  1. 图中的K点无法被查询到。
  2. 如果要查找距离Target (红点)最近的topK个点, 而如果点之间无连线, 将影响查找效率。
  3. D点有这么多友节点吗? 增加了构造复杂度。谁是谁的友节点如何确定?
  4. 如果初始点选择地不好(比如很远),将进行多步查找。

2. NSW算法原理

NSW,即没有分层的可导航小世界的结构(Navigable-Small-World-Graph )。

针对上面的问题,解决办法:

  1. 某些点无法被查询到 -> 规定构图时所有节点必须有友节点。
  2. 相似点不相邻的问题 -> 规定构图时所有距离相近到一定程度的节点必须互为友节点。
  3. 关于某些点有过多友节点 -> 规定限制每个节点的友节点数量。
  4. 初始点选择地很远 -> 增加高速公路机制。

2.1 NSW构图算法

图中插入新节点时,通过随机存在的一个节点出发查找到距离新节点最近的m个节点(规定最多m个友节点,m由用户设置),连接新节点到这最近的m个节点。节点的友节点在新的节点插入的过程中会不断地被更新。

待更新...............

推荐算法:HNSW算法简介-CSDN博客

检索模型-粗排HNSW_hnsw模型-CSDN博客

这篇关于推荐算法:HNSW【推荐出与用户搜索的类似的/用户感兴趣的商品】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/482396

相关文章

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Redis中如何实现商品秒杀

《Redis中如何实现商品秒杀》:本文主要介绍Redis中如何实现商品秒杀问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录技术栈功能实现步骤步骤一:准备商品库存数据步骤二:实现商品秒杀步骤三:优化Redis性能技术讲解Redis的List类型Redis的Set

查看Oracle数据库中UNDO表空间的使用情况(最新推荐)

《查看Oracle数据库中UNDO表空间的使用情况(最新推荐)》Oracle数据库中查看UNDO表空间使用情况的4种方法:DBA_TABLESPACES和DBA_DATA_FILES提供基本信息,V$... 目录1. 通过 DBjavascriptA_TABLESPACES 和 DBA_DATA_FILES

最新Spring Security实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)

《最新SpringSecurity实战教程之表单登录定制到处理逻辑的深度改造(最新推荐)》本章节介绍了如何通过SpringSecurity实现从配置自定义登录页面、表单登录处理逻辑的配置,并简单模拟... 目录前言改造准备开始登录页改造自定义用户名密码登陆成功失败跳转问题自定义登出前后端分离适配方案结语前言

OpenManus本地部署实战亲测有效完全免费(最新推荐)

《OpenManus本地部署实战亲测有效完全免费(最新推荐)》文章介绍了如何在本地部署OpenManus大语言模型,包括环境搭建、LLM编程接口配置和测试步骤,本文给大家讲解的非常详细,感兴趣的朋友一... 目录1.概况2.环境搭建2.1安装miniconda或者anaconda2.2 LLM编程接口配置2

mysql删除无用用户的方法实现

《mysql删除无用用户的方法实现》本文主要介绍了mysql删除无用用户的方法实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 1、删除不用的账户(1) 查看当前已存在账户mysql> select user,host,pa

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Python使用DeepSeek进行联网搜索功能详解

《Python使用DeepSeek进行联网搜索功能详解》Python作为一种非常流行的编程语言,结合DeepSeek这一高性能的深度学习工具包,可以方便地处理各种深度学习任务,本文将介绍一下如何使用P... 目录一、环境准备与依赖安装二、DeepSeek简介三、联网搜索与数据集准备四、实践示例:图像分类1.