HNSWlib 入门
语义搜索能让机器理解语言,并产生更好的搜索结果,这对人工智能和数据分析至关重要。一旦语言被表示为Embeddings,就可以使用精确或近似方法进行搜索。近似近邻(ANN)搜索是一种用于快速查找数据集中与给定查询点最接近的点的方法,与精确近邻搜索不同,精确近邻搜索对于高维数据来说计算成本很高。近邻搜索能提供近似于近邻的结果,从而加快检索速度。
近似近邻(ANN)搜索的算法之一是HNSW(Hierarchical Navigable Small Worlds,层次导航小世界),在HNSWlib 下实现,这将是今天讨论的重点。在本博客中,我们将
了解 HNSW 算法。
探索 HNSWlib 及其主要功能。
设置 HNSWlib,包括索引构建和搜索实现。
与 Milvus 进行比较。
了解 HNSW
Hierarchical Navigable Small Worlds(HNSW)是一种基于图的数据结构,通过构建 "小世界 "网络的多层图,可以进行高效的相似性搜索,尤其是在高维空间中。HNSW 于2016 年推出,解决了与传统搜索方法(如暴力搜索和基于树的搜索)相关的可扩展性问题。它非常适合涉及大型数据集的应用,如推荐系统、图像识别和检索增强生成(RAG)。
HNSW 为何重要
HNSW 大大提高了高维空间中最近邻搜索的性能。分层结构与小世界可导航性相结合,避免了旧方法的计算效率低下问题,使其在处理大规模复杂数据集时也能表现出色。为了更好地理解这一点,让我们来看看它现在是如何工作的。
HNSW 如何工作
分层:HNSW 将数据组织成层级结构,每一层都包含由边连接的节点。顶层较为稀疏,可以在图中进行大范围 "跳转",就像在地图上放大后只能看到城市间的主要公路一样。下层的密度增加,提供了更多细节和更多近邻之间的连接。
可导航的小世界概念:HNSW 中的每一层都建立在 "小世界 "网络概念的基础上,其中的节点(数据点)之间只有几个 "跳 "的距离。搜索算法从最高、最稀疏的层开始,向下移动到逐渐密集的层,以完善搜索。这种方法就像从全局视图向下移动到邻近层细节,逐渐缩小搜索范围。
图 1:可导航的小世界图示例
- 跳过列表式结构:HNSW 的分层结构类似于跳过列表,这是一种概率数据结构,其中较高层的节点较少,因此初始搜索速度较快。
图 2:跳表结构示例
要在给定的跳过列表中搜索 96,我们从最左侧的顶层开始,在头节点处搜索。向右移动时,我们遇到了 31,小于 96,因此我们继续向下一个节点移动。现在,我们需要向下移动一级,再次看到 31;由于它仍然小于 96,我们又向下移动了一级。再次找到 31 后,我们向右移动,到达 96,也就是我们的目标值。这样,我们就找到了 96,而无需下移到跳转列表的最低层。
搜索效率:HNSW 算法从最高层的入口节点开始,每一步都向更近的邻近节点前进。它逐层下降,利用每一层进行从粗到细的探索,直到到达可能找到最相似节点的最低层。这种分层导航减少了需要探索的节点和边的数量,使搜索既快速又准确。
插入和维护:在添加新节点时,算法会根据概率确定其入口层,并使用邻居选择启发式将其连接到附近的节点。启发式的目的是优化连接性,在平衡图密度的同时创建可提高导航性的链接。这种方法使结构保持稳健,并能适应新的数据点。
虽然我们已经对 HNSW 算法有了基本的了解,但从头开始实施可能会让人不知所措。幸运的是,社区开发了像HNSWlib这样的库来简化使用,使我们无需挠头就能使用它。下面,让我们来详细了解一下 HNSWlib。
HNSWlib 概述
HNSWlib 是实现 HNSW 的流行库,具有高效率和可扩展性,即使在数百万个点的情况下也能表现出色。它允许在图层之间快速跳转,并优化了高密度、高维数据的搜索,从而实现了亚线性时间复杂度。以下是 HNSWlib 的主要特点:
基于图形的结构:多层图表示数据点,允许快速近邻搜索。
高维效率:针对高维数据进行优化,提供快速准确的近似搜索。
亚线性搜索时间:通过跳层实现亚线性复杂性,显著提高速度。
动态更新:支持实时插入和删除节点,无需重建整个图。
内存效率内存使用效率高,适合大型数据集。
可扩展性可扩展至数百万个数据点,非常适合推荐系统等中等规模的应用。
注:HNSWlib 非常适合创建向量搜索应用的简单原型。不过,由于可扩展性的限制,对于涉及数亿甚至数十亿数据点的更复杂场景,可能有更好的选择,如专门构建的向量数据库。让我们来看看实际应用。
HNSWlib 入门:分步指南
本节将通过创建 HNSW 索引、插入数据和执行搜索来演示如何将 HNSWlib 用作向量搜索库。让我们从安装开始:
安装和导入
要开始使用 Python 中的 HNSWlib,首先使用 pip 安装:
pip install hnswlib
然后,导入必要的库:
import hnswlib
import numpy as np
准备数据
在本例中,我们将使用NumPy
生成一个包含 10,000 个元素的随机数据集,每个元素的维度大小为 256。
dim = 256 # Dimensionality of your vectors
num_elements = 10000 # Number of elements to insert
让我们创建数据:
data = np.random.rand(num_elements, dim).astype(np.float32) # Example data
现在数据已经准备就绪,让我们来建立索引。
建立索引
在建立索引时,我们需要定义向量的维度和空间类型。让我们创建一个索引:
p = hnswlib.Index(space='l2', dim=dim)
space='l2'
:该参数定义了用于衡量相似性的距离度量。将其设置为'l2'
意味着使用欧氏距离(L2 规范)。如果将其设置为'ip'
,则将使用内积,这对余弦相似性等任务很有帮助。
dim=dim
:该参数用于指定数据点的维度。它必须与计划添加到索引中的数据维度相匹配。
下面是初始化索引的方法:
p.init_index(max_elements=num_elements, ef_construction=200, M=16)
max_elements=num_elements
:Num_elements
是最大容量,因此我们将其设置为 10,000,因为我们要处理 10,000 个数据点。
ef_construction=200
:该参数控制索引创建过程中准确性与构建速度之间的权衡。数值越大,召回率(准确率)越高,但内存使用量和构建时间也会增加。常用值范围为 100 到 200。
M=16
:该参数决定了为每个数据点创建的双向链接的数量,从而影响准确性和搜索速度。典型值介于 12 和 48 之间;16 通常是兼顾适度准确性和速度的最佳值。
p.set_ef(50) # This parameter controls the speed/accuracy trade-off
ef
:ef
参数是 "探索因子 "的缩写,决定了搜索过程中检查邻域的数量。ef
值越高,搜索的邻域越多,搜索的准确率(召回率)通常会提高,但搜索速度也会变慢。相反,ef
值越低,搜索速度越快,但可能会降低准确率。
在这种情况下,将ef
设置为 50 意味着搜索算法在查找最相似数据点时最多将评估 50 个邻居。
注:ef_construction
设置索引创建过程中的邻居搜索工作,可提高准确性,但会减慢构建速度。ef
控制查询过程中的搜索工作,动态平衡每次查询的速度和召回率。
执行搜索
要使用 HNSWlib 执行近邻搜索,我们首先要创建一个随机查询向量。在本例中,向量的维度与索引数据相匹配。
query_vector = np.random.rand(dim).astype(np.float32) # Example query
labels, distances = p.knn_query(query_vector, k=5) # k is the number of nearest neighbors
query_vector
:此行生成的随机向量与索引数据的维度相同,确保了近邻搜索的兼容性。knn_query
:该方法在索引p
中搜索k
query_vector
的最近邻。它返回两个数组:labels
,其中包含近邻的索引,以及distances
,表示查询向量到每个近邻的距离。在这里,k=5
指定我们要查找五个最近的邻居。
下面是打印标签和距离后的结果:
print("Nearest neighbors' labels:", labels)
print("Distances:", distances)
> Nearest neighbors' labels: [[4498 1751 5647 4483 2471]]
> Distances: [[33.718 35.484592 35.627766 35.828312 35.91495 ]]
这就是使用 HNSWlib 的简单指南。
如前所述,HNSWlib 是一个很好的向量搜索引擎,适用于原型开发或中等规模数据集的实验。如果您有更高的可扩展性要求或需要其他企业级功能,可能需要选择专门构建的向量数据库,如开源的Milvus或其在Zilliz Cloud 上的完全托管服务。因此,在下面的章节中,我们将比较 HNSWlib 和 Milvus。
HNSWlib 与 Milvus 等专用向量数据库的比较
向量数据库将数据存储为数学表示,使机器学习模型能够通过相似性指标识别数据,从而实现上下文理解,从而为搜索、推荐和文本生成提供动力。
像 HNSWlib 这样的向量索引库可以改进向量搜索和检索,但缺乏完整数据库的管理功能。另一方面,Milvus 等向量数据库旨在大规模处理向量 Embeddings,在数据管理、索引和查询功能方面具有独立库通常缺乏的优势。以下是使用 Milvus 的其他一些优势:
高速向量相似性搜索:Milvus 在十亿规模的向量数据集上提供毫秒级的搜索性能,是图像检索、推荐系统、自然语言处理(NLP)和检索增强生成(RAG)等应用的理想选择。
可扩展性和高可用性:Milvus 专为处理海量数据而构建,可横向扩展,并包含复制和故障转移机制,以确保可靠性。
分布式架构:Milvus 采用分布式可扩展架构,将存储和计算分离到多个节点,具有灵活性和稳健性。
灵活的数据支持:Milvus 支持多种数据类型--向量、标量和结构化数据--允许在单一系统内进行无缝管理和分析。
活跃的社区 和支持:蓬勃发展的社区提供定期更新、教程和支持,确保 Milvus 始终与用户需求和该领域的进步保持一致。
人工智能集成:Milvus 集成了各种流行的人工智能框架和技术,使开发人员更容易使用自己熟悉的技术栈构建应用程序。
Milvus 还在Ziliz Cloud 上提供全面托管服务,无后顾之忧,速度比 Milvus 快 10 倍。
比较:Milvus 与 HNSWlib 的比较
特点 | Milvus | HNSWlib |
---|---|---|
可扩展性 | 轻松处理数十亿向量 | 由于使用 RAM,适合较小的数据集 |
适用于 | 原型开发、实验和企业级应用 | 专注于原型和轻量级 ANN 任务 |
索引 | 支持 10 多种索引算法,包括 HNSW、DiskANN、量化和二进制算法 | 仅使用基于图的 HNSW |
集成 | 提供 API 和云原生服务 | 作为轻量级独立库使用 |
性能 | 针对大型数据和分布式查询进行优化 | 提供高速度,但可扩展性有限 |
总的来说,Milvus 通常适用于具有复杂索引需求的大规模生产级应用,而 HNSWlib 则是原型开发和更直接使用案例的理想选择。
结论
语义搜索可能是资源密集型的,因此像HNSW这样的内部数据结构化对于加快数据检索至关重要。像HNSWlib这样的库关心的是实现,因此开发人员已经准备好了用于向量功能原型的配方。只需几行代码,我们就能建立自己的索引并执行搜索。
HNSWlib 是一个很好的入门工具。不过,如果您想构建复杂且可投入生产的人工智能应用,专门构建的向量数据库是最佳选择。例如,Milvus是一个开源向量数据库,具有高速向量搜索、可扩展性、可用性以及数据类型和编程语言的灵活性等许多企业就绪的功能。
更多阅读
Try Managed Milvus for Free
Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.
Get StartedLike the article? Spread the word