当前位置: 首页 > news >正文

【AI知识点】近似最近邻搜索(ANN, Approximate Nearest Neighbor Search)

近似最近邻搜索(ANN, Approximate Nearest Neighbor Search) 是一种用于高维数据检索的技术,目标是在给定查询的情况下,快速找到距离查询点最近的数据点,尽管结果可能并不完全精确。这种方法特别适用于高维数据(如图像、文本嵌入、用户行为特征等)的快速相似性搜索。

1. 最近邻搜索(NNS)

最近邻搜索(Nearest Neighbor Search, NNS) 是指在一个数据集中,给定一个查询点,找到与该点最接近的一个或多个点。对于低维数据,如二维或三维空间,可以通过简单的几何方法(如欧几里得距离)快速完成这种搜索。然而,当数据的维度非常高时(如深度学习中的嵌入向量通常有数百或上千维),标准的最近邻搜索方法变得非常耗时和计算复杂,因为搜索空间呈指数级增长。这种现象被称为维度灾难(curse of dimensionality)

在这种高维数据场景中,近似最近邻搜索 提供了一种权衡方案,即通过舍弃一些精度,来显著提高搜索速度。


2. 为什么选择近似最近邻搜索(ANN)

在许多应用中,找到近似的最近邻已经足够,例如推荐系统、图像检索、文本相似性搜索等。这些场景更注重响应速度,而不一定要求找到完全最接近的点。通过允许近似的结果,ANN 方法在精度和速度之间取得平衡,适合大规模高维数据场景。

例子:

  • 图像检索:给定一张图像,用户希望找到与之相似的图像。尽管用户并不要求找到精确的最相似图像,但要求结果在几毫秒内返回,近似相似的图像检索结果已经可以满足用户需求。

  • 文本相似性搜索:对于一段输入文本,ANN可以快速找到语义上相似的其他文本,即使找到的文本并不是与输入完全相同。


3. 近似最近邻搜索的工作原理

ANN 的主要目标是通过优化算法结构,减少高维数据中查找最近邻的时间复杂度。典型的算法有以下几类:

a. 分区树方法

这些方法通过将数据集划分为不同的子区域,减少搜索空间。例如:

  • KD树(k-dimensional tree):将空间递归地划分为一系列超平面。KD树适合低维度数据,但在高维数据上效率较低。

  • 球树(Ball tree):用球体代替超平面来划分空间,适合处理高维数据。

尽管这些方法能加速查询,它们在维度非常高的情况下仍然不够高效,因此更多高维情况下使用的ANN方法会采用其他策略。

b. 局部敏感哈希(LSH, Locality Sensitive Hashing)

LSH 是一种非常流行的ANN方法,通过将相似的数据点散列到相同的桶(bucket)中,从而减少需要检查的点的数量。

工作原理:

  1. 哈希函数设计:LSH的核心是设计一组哈希函数,使得相似的数据点有较高概率被映射到相同的桶中,而不相似的点被映射到不同的桶。
  2. 哈希映射:将数据点通过这些哈希函数映射到多个桶中。
  3. 快速搜索:对于给定的查询点,只需要检查与查询点映射到同一桶的数据点,从而大幅减少比较的次数。

LSH特别适用于欧几里得距离和余弦相似度度量的高维数据。

c. 矢量量化(Vector Quantization, VQ)

矢量量化方法将数据集划分为有限数量的码字(centroids),然后仅在这些码字中进行最近邻搜索。常用的技术有产品量化(Product Quantization, PQ),它通过将高维空间分割成低维子空间并对每个子空间量化,从而大大减少搜索空间。

d. 图嵌入法(Graph-based Methods)

图嵌入法使用基于图的结构来加速ANN。通过构建数据点之间的邻居图,查询点可以通过遍历图找到接近的数据点。这类方法通常会用到近邻图(k-nearest neighbor graph, k-NN graph)小世界图,通过邻居节点的连接进行高效搜索。

常见的图嵌入法有:

  • HNSW(Hierarchical Navigable Small World):是一种基于小世界网络的高效算法,在现实中被广泛应用,如Facebook的FAISS库中。

4. 近似最近邻搜索的实际应用

a. 推荐系统

推荐系统中,经常需要快速找到与用户过去行为或喜好相似的其他产品、电影、音乐等。ANN算法能帮助系统在大规模用户数据中快速找到相似的用户或物品,从而提供个性化推荐。

b. 图像搜索

在图像搜索系统中,用户上传图片后,系统需要找到数据库中与之相似的图片。通过ANN,系统可以在海量图片数据中快速找到类似的图像,即使这些图像只是近似相似而不是完全相同。

c. 文本相似性搜索

在NLP任务中,ANN可以用于快速找到与输入文本相似的其他文本。例如,在一个FAQ系统中,用户输入问题时,系统通过ANN找到与该问题语义最接近的其他问题,从而提供匹配的答案。

d. 嵌入向量的快速检索

深度学习中的许多模型(如BERT、GPT等)将文本、图像等数据转化为高维嵌入向量。这些向量可以被用于表示数据的语义特征。在各种检索系统中,ANN算法可以高效地处理这些高维向量的相似性搜索,帮助系统快速找到最相关的数据。


5. 比喻解释

可以把ANN比作一个大图书馆的“快速查找系统”。假设图书馆里有百万本书,当你想找到与某本书内容相似的几本书时,如果你逐一阅读每本书来进行比较,会非常耗时。ANN的作用就像是图书馆里的一种快速分类系统,它把书本按照某些关键特征快速归类,然后通过这些特征的近似匹配,迅速帮你找到几本可能最接近的书。这种方法虽然不保证找到的书是100%最接近的,但可以在非常短的时间内给出足够好的结果。


6. 总结

近似最近邻搜索(ANN) 是一种为了提升高维数据相似性搜索效率的技术,它在牺牲一定精度的前提下,大大提升了搜索速度。它被广泛应用于推荐系统、图像检索、文本相似性搜索等实际场景。常见的ANN算法包括局部敏感哈希(LSH)、图嵌入法(如HNSW)、矢量量化(VQ)等,它们通过不同的方式优化搜索过程,解决了高维数据中的“维度灾难”问题。

相关文章:

【AI知识点】近似最近邻搜索(ANN, Approximate Nearest Neighbor Search)

近似最近邻搜索(ANN, Approximate Nearest Neighbor Search) 是一种用于高维数据检索的技术,目标是在给定查询的情况下,快速找到距离查询点最近的数据点,尽管结果可能并不完全精确。这种方法特别适用于高维数据&#x…...

编程工具简介

在编程工作中,选择合适的工具确实能够显著提升工作效率。以下是一些被广泛推荐的工具: 1. Visual Studio Code (VS Code):这是一款轻量级但功能强大的代码编辑器,支持多种编程语言,拥有丰富的插件生态系统&#xff0…...

汽车信息安全 -- 存到HSM中的密钥还需包裹吗?

目录 1.车规芯片的ROM_KEY 2.密钥加密与包裹 3.瑞萨RZ\T2M的密钥导入 4.小结 在车控类ECU中,我们通常把主控芯片MCU中的HSM以及HSM固件统一看做整个系统安全架构的信任根。 所以大家默认在HSM内部存储的数据等都是可信的,例如CycurHSM方案中使用HSM…...

【PostgreSQL】入门篇——SELECT、INSERT、UPDATE 和 DELETE 语句,SQL 中最常用的四种操作用法

1. SELECT 语句 描述 SELECT 语句用于从数据库中查询数据。可以选择特定的列或所有列,并可以通过条件过滤结果。 语法 SELECT column1, column2, ... FROM table_name WHERE condition;示例 假设我们有一个名为 employees 的表,结构如下&#xff1a…...

【Ubuntu】安装常用软件包-mysql

我的几个服务是部署在docker的同一个网络里,这样相互访问就可以通过docker容器的名字访问,比如容器A访问容器B,就可以http://B:8080/xxx 这样访问,不用关心ip是多少。 所以mysql前面文章给安装到主机里,感觉有点坑自己…...

幂等性及技术解决方案

文章目录 定义幂等性 为什么需要幂等性幂等性设计注意事项幂等性的范围分布式锁解决幂等性 设计 延伸阅读 定义幂等性 简单地说,我们可以多次执行幂等运算而不改变结果或者使用相同的输入参数中被调用多次,则不具有额外效果的操作,也就是多…...

正向代理 反向代理

正向代理 正向代理是一种网络服务,它作为客户端和目标服务器之间的中间人,代表客户端向目标服务器发送请求并接收响应。以下是关于正向代理的详细解释: 工作原理 客户端配置: 客户端(如浏览器)配置为使用…...

【分布式微服务云原生】如何在ActiveMQ中优雅处理提前支付的延时订单

摘要 本文将深入探讨在ActiveMQ中如何处理用户提前支付的延时订单问题。我们将介绍如何通过更新订单状态、检查延迟任务、取消延迟消息、使用死信队列、消息选择性消费、设置合理的超时时间以及及时反馈和日志记录等策略,来确保系统的一致性和及时响应用户操作。文…...

Easy Excel从入门到精通!!!

目录 1.文件导入 1.1基本方式读取excel文件内容 1.2注解模型映射器读取excel 1.3多行表头读取 1.4文件上传读取 2.文件导出 2.1基本方式导出 2.2模型映射导出 2.3设置行高、列宽等内容 2.4合并单元格 2.5导出设置超链接、批注、公式 2.6模板填充对象导出 2.7模板填…...

简易CPU设计入门:取指令(三),ip_buf与rd_en的非阻塞赋值

在开篇,还是请大家首先准备好本项目所用的源代码。如果已经下载了,那就不用重复下载了。如果还没有下载,那么,请大家点击下方链接,来了解下载本项目的CPU源代码的方法。 下载本项目代码 准备好了项目源代码以后&…...

【算法】---归并排序(递归非递归实现)

参考 左程云算法 算法导论 前言 本篇介绍 归并排序分治法 前置知识 了解递归, 了解数组。 引入 归并排序 归并排序最早是由公认的现代计算机之父John von Neumann发明的, 这是一种典型的分治思想应用。 我们先介绍分治思想 分治思想 分治思想的…...

UniVue大版本更新:UniVue2.0.0-preview

大版本发布说明 距离上次更新好像已经过去很久了,最近太忙了没时间维护新版本,也是自己在使用的过程中发现了很多问题也有了更多的灵感,由于和之前的版本区别太大,决定重新开一个大版本。这个UniVue2之后的版本追求是性能&#xf…...

RabbbitMQ篇(环境搭建 - 下载 安装)(持续更新迭代)

目录 一、Windows 1. 下载安装程序 2. 安装配置erlang 3. 安装rabbitMQ 4. 验证 二、Linux 1. 下载rpm包 1.1. 下载Erlang的rpm包 1.2. 下载socat的rpm包 1.3. 下载RabbitMQ的rpm包 2. 安装 2.1. 安装Erlang 2.2. 安装socat 2.3. 安装RabbitMQ 3. 启动RabbitMQ服…...

C++基础补充(02)C++其他控制语句break continue goto等

文章目录 1. break2. continue 语句3. goto 语句goto的存在 4. 跳出多重循环4.1 goto 直接跳转4.2 C11及其后版本的 return 语句4.3 使用标志变量 在C中,控制语句用于管理程序的执行流程。常见有 break、continue 和 goto。 1. break break语句主要用于在循环或者s…...

决策树中联合概率分布公式解释说明

学习决策树时书本中有一公式 7-3 是: P ( X x i , Y y j ) p i j ( i 1 , 2 , … , m , j 1 , 2 , … , n ) P(X x_i, Y y_j) p_{ij} \quad (i 1, 2, \dots, m, \ j 1, 2, \dots, n) P(Xxi​,Yyj​)pij​(i1,2,…,m, j1,2,…,n) 这个公式表示的是随机变…...

计算机毕业设计 农场投入品运营管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍:✌从事软件开发10年之余,专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ 🍅文末获取源码联系🍅 👇🏻 精…...

php email功能实现:详细步骤与配置技巧?

php email发送功能详细教程?如何使用php email服务? 无论是用户注册、密码重置,还是订单确认,电子邮件都是与用户沟通的重要手段。AokSend将详细介绍如何实现php email功能,并提供一些配置技巧,帮助你更好…...

MapBox Android版开发 6 关于Logo

MapBox Android版开发 6 关于Logo Logo的显示查看源码及思路(Logo)第一步第二步 隐藏Logo示例查看源码及思路(Info)第一步第二步 隐藏Logo和Info示例 看到有网友留言问如何移除Logo,今天看了下V9源码,发现M…...

2024年房市

24年8月15日,国家统计局公布,“7月末,商品房待售面积73926万平方米”。(原文链接:https://www.stats.gov.cn/sj/zxfb/202408/t20240815_1955982.html)   7.39亿平方存量商品房,估价均价1万每平,总价约&am…...

index索引

index索引: create index 【1】on 【2】(【3】) 1为索引名,通常为id_表名_列名。2为表名。3为列名。 CREATE INDEX id_account_id ON account(id); -- 根据id创建索引 CREATE INDEX id_account_idname on account(id,name); -- 创建组合索引 索…...

理解互联网链路:从本地ISP到Tier 1 ISP运营商

1. 互联网服务提供商(ISP) 互联网服务提供商(ISP)是指提供互联网接入服务的公司或组织。它们负责将用户连接到互联网,并提供相关的服务,如电子邮件、网站托管和其他在线服务。ISP可以分为不同的层级&#…...

基于元神操作系统实现NTFS文件操作(三)

1. 背景 本文主要介绍DBR的读取和解析,并提供了基于元神操作系统的实现代码。由于解析DBR的目的是定位到NTFS磁盘分区的元文件$Root进行文件操作,所以只解析了少量的部分,其它部分可以参考相关文档进行理解。 DBR存在于磁盘分区的第一个扇区…...

深度学习与数学归纳法

最近发现,深度学习可以分为两个主要的阶段,分别是前向推理以及反向传播,分别对应着网络的推理和参数训练两个步骤。其中推理有时候也称为归纳推理。 在做参数训练的时候,本质上是在利用历史数据求网络参数的先验分布; …...

《Linux从小白到高手》理论篇(六):Linux软件安装一篇通

List item 本篇介绍Linux软件安装相关的操作命令,看完本文,有关Linux软件安装相关操作的常用命令你就掌握了99%了。 Linux软件安装 RPM RPM软件的安装、删除、更新只有root权限才能使用;查询功能任何用户都可以操作;如果普通用…...

【Spring】运行Spring Boot项目,请求响应流程分析以及404和500报错

1. 运行项目 import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; SpringBootApplication public class Application { public static void main(String[] args) { SpringApplication.run(Appl…...

②EtherCAT转Modbus485RTU网关多路同步高速采集无需编程串口服务器

EtherCAT转Modbus485RTU网关多路同步高速采集无需编程串口服务器https://item.taobao.com/item.htm?ftt&id798036415719 EtherCAT 串口网关 EtherCAT 转 RS485 (接上一章) 自由协议通信步骤 (以MS-A2-1041为例) 接收与…...

matlab-对比两张图片的HSV分量的差值并形成直方图

%对比两张图片的HSV分量的差值并形成直方图,改个路径就能用,图片分辨率要一致 close all; clear all; clc; I1imread(E:\test\resources\image\1.jpg); I2imread(E:\test\resources\image\2.jpg); HSV1 rgb2ntsc(I1); HSV2 rgb2ntsc(I2); %HSV,HSV 代…...

微服务SpringGateway解析部署使用全流程

官网地址: Spring Cloud Gateway 目录 1、SpringGateway简介 1、什么是网关 2、为什么用网关【为了转发】 2、应用: 1.启动nacos 2.创建网关项目 3.网关配置1 4.网关配置2【了解】 5.过滤器配置【了解】 1、SpringGateway简介 核心功能有三个&…...

Solidity 存储和内存管理:深入理解与高效优化

在 Solidity 中,存储和内存管理是编写高效智能合约的关键组成部分。合约执行的每一步操作都可能涉及到数据的存储和读取,而这些操作对 gas 的消耗有很大影响。因此,理解 Solidity 的存储模型以及如何优化数据的管理对于合约的安全性、性能和成…...

机器学习篇-day02-KNN算法实现鸢尾花模型和手写数字识别模型

一. KNN简介 KNN思想 K-近邻算法(K Nearest Neighbor,简称KNN)。比如:根据你的“邻居”来推断出你的类别 KNN算法思想:如果一个样本在特征空间中的k 个最相似的样本中的大多数属于某一个类别,则该样本也属…...

网站建设公司资质/外贸推广平台哪家好

本文实例讲述了MySQL使用临时表加速查询的方法。分享给大家供大家参考。具体分析如下:使用MySQL临时表,有时是可以加速查询的,下面就为您详细介绍使用MySQL临时表加速查询的方法。把表的一个子集进行排序并创建MySQL临时表,有时能…...

网站开发h5技术/免费手机网站建站系统

系统相册既支持只选择一张图片,也支持同时选择多张图片。 跳到系统相册的代码例子如下: // 创建一个内容获取动作的意图(准备跳到系统相册) Intent albumIntent new Intent(Intent.ACTION_GET_CONTENT); albumIntent.putExtra(Intent.EXTRA_ALLOW_MULTI…...

wordpress 手机 菜单/今日疫情最新消息全国31个省

由于工作中完全是linux命令开发,之前没有相关的经验,只能碰到一个学一个了。 转自http://www.9usb.net/200902/linux-cat.html linux cat命令在linux系统中算是比较常用的命令. cat主要有三大功能: 1.一次显示整个文件。 $ cat filename 2.…...

北京建设监理网站/关键词分析工具

创业者需具备的潜质——“变态”[温馨提示:变态需谨慎] 通常的情况下每个人都认为自己具有开创一翻事业的潜质,事实上真正具有这种潜质的人其实并不多。很多人只是简单的认为自己什么条件都不缺,唯一缺的就是钱。实际上即使他们有钱&#xff…...

手机网站 seo/百度指数查询官网入口

选中下拉框中的选项实现左移右移效果:1. Html部分代码左1左2左3左4左5左6左7左8左9左10右1右2右3右4右5右6右72. JavaScript脚本代码如下:function moveRight(){//获取左边select元素节点var leftSelectNode document.getElementById("left");//获取子元…...

免费oa管理系统/seo查询爱站

今天我们分享的Python程序,是一款用深度学习来为颜值评分的应用,在科技飞速发展的当今社会,我们可以通过机器学习实现自动驾驶、识别字体等,甚至连谷歌研发的Alphago都可以向人类的围棋事业发出挑战。所以,今天码趣君给…...