推荐算法: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

相关文章

SpringBoot UserAgentUtils获取用户浏览器的用法

《SpringBootUserAgentUtils获取用户浏览器的用法》UserAgentUtils是于处理用户代理(User-Agent)字符串的工具类,一般用于解析和处理浏览器、操作系统以及设备... 目录介绍效果图依赖封装客户端工具封装IP工具实体类获取设备信息入库介绍UserAgentUtils

Mysql用户授权(GRANT)语法及示例解读

《Mysql用户授权(GRANT)语法及示例解读》:本文主要介绍Mysql用户授权(GRANT)语法及示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql用户授权(GRANT)语法授予用户权限语法GRANT语句中的<权限类型>的使用WITH GRANT

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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