做app做网站从何学起,佛山网站上排名,网站设计的企业,广西建设厅证书查询1.Locality Sensitive Hashing (LSH) 使用 Shingling MinHashing 进行查找 左侧是字典#xff0c;右侧是 LSH。目的是把足够相似的索引放在同一个桶内。
LSH 有很多的版本#xff0c;很灵活#xff0c;这里先介绍第一个版本#xff0c;也是原始版本 Shingling one-hot …1.Locality Sensitive Hashing (LSH) 使用 Shingling MinHashing 进行查找 左侧是字典右侧是 LSH。目的是把足够相似的索引放在同一个桶内。
LSH 有很多的版本很灵活这里先介绍第一个版本也是原始版本 Shingling one-hot MinHash 从 shingled 等于 1 的那一行找找哈希值最小的四个颜色里面得到的最终签名是 2412. 根据签名划分桶对桶进行哈希 最后让两个向量在同一个桶内进行相似检索 不同的 b 值的相似度对比
在 FAISS 中的实现
import numpy as np
import faiss# 生成随机数据集10000个128维向量
np.random.seed(42)
d 128 # 向量维度
nb 10000 # 数据集大小
nq 5 # 查询数量
xb np.random.random((nb, d)).astype(float32) # 数据库向量
xq np.random.random((nq, d)).astype(float32) # 查询向量# 创建 LSH 索引
**n_bits 16 # 每个哈希签名的比特数控制分布的细粒度
nlist 100 # 哈希桶的数量**# 使用余弦相似度的 LSH 索引
index faiss.IndexLSH(d, n_bits) # d 是向量维度n_bits 是每个哈希签名的比特数# 为数据集添加索引
index.add(xb)# 执行查询
k 5 # 要找到的最近邻数量
D, I index.search(xq, k) # 查询xq中k个最近邻n_bits(哈希签名比特数) 较大的 n_bits 的值意味着哈希分布更精细每个哈希签名的长度更长从而减少哈希冲突提升检索的准确度。 nlist(桶的数量) 代码中未显示 nlist 调节但你可以通过构建带有倒排表IVF的 LSH 来设置 nlist。增加 nlist 可以减少每个桶中的向量数量提高查询速度但会增加空间分配的细粒度。
2.PQ 补充概念 code code 指数据点被量化后生成的一个索引值表示该数据点在量化器所创建的 码本(codebook) 中的位置 当数据经过量化之后他被映射到码本中的一个 质心(centroid),每个质心有一个对应的索引这个索引就是 code 例如如果有 64 个质心那么每个数据点的 code 将是 0 到 63 之间的一个整数表示该数据点最接近哪个质心。 Codebook 码本codebook 是一组质心的集合用于表示数据集中的典型向量或原型。码本中的每个质心是一个向量代表了量化后的数据点可以映射到的“典型”位置。 质心centroid 是通过聚类算法如 k-means在训练阶段学到的用来表示数据点的分布。 码本的大小由质心的数量决定。例如一个码本可能包含 64 个质心表示数据可以被量化为 64 种不同的状态。 总结 Code 是数据点量化后对应质心的索引用来表示该数据点最接近的质心。 Codebook 是质心的集合表示数据点被聚类后可以映射到的典型位置。 1.摘要
其思想是将空间分解为低维子空间的笛卡尔积并分别对每个子空间进行插值。
向量由其子空间量化索引组成的短码表示。
两个向量之间的欧氏距离可以有效地从它们的代码估计。非对称版本提高了精度因为它计算了向量和代码之间的近似距离。
实验结果表明我们的方法有效地搜索最近的邻居特别是在与倒排文件系统相结合。
2.引言
已经提出了几种多维索引方法例如流行的 KD树[5]或其他分支和界限技术以减少搜索时间。然而对于高维事实证明这种方法并不比穷举距离计算更有效其复杂度为 O ( n D ) O(nD) O(nD)。
在本文中我们利用量化来构造短码。
目标是使用向量到质心距离来估计距离例如查询向量不被量化code 仅被分配给数据库向量。这减少了量化噪声并随后提高了搜索质量。为了获得精确的距离必须限制量化误差。因此质心的总数k应该足够大。这就提出了关于如何学习码本和分配向量的若干问题。
首先学习量化器所需的样本数量是巨大的即几次 K。
其次算法本身的复杂性是禁止的。
最后地球上可用的计算机内存量不足以存储表示质心的浮点值。
3.背景 向量量化 向量量化是一个破坏的过程他会减少表示空间的基数尤其是输入数据是实数的时候 形式上量化器是将 D 维向量 x x x 映射到向量 q ( x ) ∈ C { c i , i ∈ I } , I 0... k − 1 q(x)\in C \{c_i, i\in I\}, I0...k-1 q(x)∈C{ci,i∈I},I0...k−1 的函数 q q q。 再现值 c i c_i ci 被称为质心。再现值的集合 C C C 是大小为 k k k 的码本。 映射到给定索引 i i i 的向量的集合 V i V_i Vi 被称为Voronoi单元 量化器的 k k k 个单元形成 R D R^D RD 的分区。根据定义位于相同单元 V i V_i Vi 中的所有向量由相同质心 c i c_i ci 重构。 量化器的评价指标通常通过输入向量 x x x 和其再现值 q ( x ) q(x) q(x) 之间的均方误差 MSE 来测量。 其中 d ( x , y ) ∣ ∣ x − y ∣ ∣ d(x,y)||x-y|| d(x,y)∣∣x−y∣∣ p ( x ) p(x) p(x) 是相关变量 X 的概率分布函数 为了使量化器是最佳的它必须满足两个属性称为 Lloyd 最优性条件。首先向量 x 必须量化到其最近的码本质心根据欧几里得距离 因此单元由超平面界定。 第二个 Lloyd 条件是重建值必须是位于 Voronoi 单元中的向量的期望 Lloyd 量化器对应于 k 均值聚类算法通过迭代地将训练集的向量分配给质心并从分配的向量重新估计这些质心来找到接近最优的码本。 在没有任何进一步处理熵编码的情况下存储索引值的存储器成本是 l o g 2 k log_2k log2k bit 。因此对于k使用2的幂是方便的因为量化器产生的代码存储在二进制存储器中。 乘积量化 考虑 128 维向量。一个量化器产生 64bits 的 code即包含 2 64 2^{64} 264 个质心。大的离谱内存不能接受。 乘积量化是一个处理这种问题的解决方案。 输入向量 x x x 被分成 m m m 个不同的子向量 u j u_j uj, 维度为 D ∗ D / m D^*D/m D∗D/m D D D 需要是 m m m 的倍数。 使用 m m m 个不同的量化器分别量化 子向量。 D 维向量 x 的被量化如图 乘积量化器的再现值由乘积索引集合 I I 1 × . . . × I m II_1×...×I_m II1×...×Im 的元素来标识。因此码本被定义为笛卡尔积 并且该集合的质心是 M 个子量化器的质心的级联。 从现在开始我们假设所有的子量化器都有相同的有限数量 k 的再现值。在这种情况下质心的总数由下式给出 注意在 m D的极端情况下向量 x 的分量全部被单独量化。然后乘积量化器变成标量量化器其中与每个分量相关联的量化函数可以不同。 乘积量化器的优点是从几个小的质心集合中产生一个大的质心集合与子量化器相关联的质心集合。 k 是质心数假设 k 2 64 k2^{64} k264 的情况下效果还是相当可观的
4.量化搜索 见图2。 对称和非对称距离计算的图解。利用距离 d ( q ( x ) , q ( y ) ) d(q(x), q(y)) d(q(x),q(y))左或距离 d ( x , q ( y ) ) d(x,q(y)) d(x,q(y))右来估计距离 d ( x , y ) d(x,y) d(x,y)。 距离上的均方误差平均地由量化误差限定。
最近邻搜索取决于查询向量和数据库向量之间的距离或者等效地平方距离。 使用量化 code 计算距离 让我们考虑查询向量 x 和数据库向量 y。我们提出了两种方法来计算这些向量之间的近似欧氏距离对称和非对称的。有关说明请参见图2。 Symmetric distance computation (SDC): 向量 x 和 y 都由它们各自的质心 q(x) 和 q(y) 表示距离 d(x,y) 近似为距离 d ( q ( x ) q ( y ) ) d(q(x)q(y)) d(q(x)q(y)). Asymmetric distance computation (ADC) 数据库向量 y y y 由 q ( y ) q(y) q(y) 表示但查询 x x x 未被编码。距离 d ( x y ) d(xy) d(xy) 近似为距离 d ( x , q ( y ) ) d(x,q(y)) d(x,q(y))其使用分解计算 表 II 总结了不同步骤中的复杂度涉及了 x x x 的 k k k 个最近邻邻居在 n ∣ y ∣ n|y| n∣y∣ 的数据集 Y Y Y中。可以看出SDC 和 ADC 具有相同的查询准备成本这与数据集大小 n 无关。 与 ADC 相比SDC 的唯一优点是限制了与查询相关的内存使用因为查询向量是由 code 定义的。这是大多数情况下不相关的然后应该使用非对称版本它获得了类似的复杂性较低的距离失真。我们将在本节的其余部分重点介绍 ADC。 非详尽搜索 图5.基于非对称距离计算的倒排文件IVFADC索引系统概述。上图插入载体。底部搜索。
5.总结
上面有点乱总结一下 核心思想 PQ 的关键思想是将一个高维向量分成若干低维的子向量然后对每个子向量分别进行量化。 高维向量分割假设你有一个 D D D 维的向量PQ 会将这个向量分成 m m m 个子向量。每个子向量的维度为 D / m D/m D/m 。每个子向量独立量化每个子向量分别用自己的码本(codebook)进行量化。每个码本有 k 个质心(centroid)也就是 k 种可能的量化结果存储方式每个高维向量的量化结果是 m 个子向量的量化码(code)的组合。这样。存储一个向量时不再存储整个向量。而是存储 m 个索引 工作流程 假设有一个 D 维向量 x使用 PQ 进行量化。 分割向量将 x 划分为 m 个子向量 x ( x 1 , … , x m ) x(x_1, …, x_m) x(x1,…,xm)每个子向量维度时 D / m D/m D/m对每个子向量进行独立量化 为每个子向量训练一个量化器生成对应的码本(centroid)将每个子向量 x i x_i xi 用码本中的质心替代即找到与该子向量最近的质心返回质心的索引 存储结果量化后将 x 表示为一个由 m 个量化索引组成的组合这些索引指向各自子向量的质心 查询阶段在查询时将查询向量分块分别与每个子向量的码本进行距离计算。最后将每个子向量的距离累加得到总距离。
6.faiss 中实现
import faiss# 维度
d 128# 定义PQ量化器分成m个子空间每个子空间使用k个质心
m 8 # 子空间数量
k 256 # 每个子空间使用256个质心8比特码# 创建PQ索引
index faiss.IndexPQ(d, m, k)# 训练PQ索引假设有xb作为训练数据
index.train(xb)# 添加数据
index.add(xb)# 查询
D, I index.search(xq, k) # 查询xq中的k个近邻m子空间数量 将 原始向量划分为 m 个子空间每个空间独自量化。m 需要被 d 整除m 越大单个子向量维度越小量化误差可能越大存储开销和搜索速度可能降低。较小的 m 会保留更多原始向量的结构信息但会增加存储和查询的计算复杂度。 k码表大小 每个子空间使用的质心数即每个子向量被量化为 k 种不同的值。常见的选择是 k 2568 比特编码也可以选择其他值k 越大量化的精度越高但存储需求和计算复杂度也会增加。常见的值为 256
3.HNSW
1.解决的问题
高维空间中的最近邻搜索问题在高维空间中传统的最近邻搜索算法如K-Nearest Neighbor SearchK-NNS由于“维度的诅咒”而变得低效。HNSW 通过引入层次结构来克服这个问题提供了更好的搜索性能。近似搜索中的准确性与效率平衡在近似最近邻搜索中需要在搜索的准确性召回率和搜索效率之间找到平衡。HNSW 通过层次化的结构和启发式邻居选择策略提高了搜索的效率和准确性。大规模数据集的可扩展性随着数据集规模的增长传统的ANNS算法可能会遇到性能瓶颈。HNSW 通过其层次化的设计实现了对大规模数据集的可扩展性。
2.原理
HNSW 的核心思想是构建一个多层次的图结构每个层次包含一个嵌套的邻近图proximity graph用于存储元素的子集。 Fig. 1 HNSW的图解。 搜索从顶层的元素开始显示为红色。红色箭头显示贪婪算法从入口点到查询的方向显示为绿色。
每个元素在图中的最大层数是随机选择的遵循指数衰减的概率分布。这种设计允许在保持图的连通性的同时通过不同长度尺度的链接分离来提高搜索性能。
搜索过程从最高层具有最长链接的层开始然后根据需要逐步向下层搜索直到达到底层。
这种“放大-缩小”zoom-out and zoom-in的策略有助于快速定位到目标区域并在局部区域内进行精确搜索。
HNSW还采用了一种启发式方法来选择邻近图中的邻居节点这种方法不仅考虑了候选节点与查询点的距离还考虑了候选节点之间的距离以创建多样化的连接。这有助于在高度聚集的数据中保持全局连通性并提高搜索的准确性。 图2.用于为两个孤立的集群选择图邻居的启发式图示。 在簇 1 的边界上插入一个新的元素该元素的所有最近邻居都属于簇 1因此丢失了簇之间的 Delaunay 图的边。然而试探法从簇 2 中选择元素 e2从而在插入的元素与来自簇 1 的任何其他元素相比最接近 e2 的情况下保持全局连通性。
3.总结
HNSW 会构建一个 分层的 导航小世界图 来加速搜索。 小世界网络 这是一个NSW图图中两个顶点的距离为 4 跳。 如图这允许通过少数跳跃能够快速遍历网络中的大部分节点 分层导航结构 HNSW 使用多层图结构其中每一层是一个稀疏图越往上层图越稀疏、节点数越少而下层的图更密集包含更多节点 顶层高层包含少数数据点节点之间的连通性较弱。这里的作用是快速浏览整个数据集。底层低层连接更密集的数据点允许更精确的搜索。 每一个数据点都会随机分配到不同的层中层次越高点的密度越低。搜索从最顶层开始依次向下跳转逐渐进入更加密集的底层图最终完成近似最近邻搜索。 邻居连接和随机跳跃 为了在各层图中有效进行导航HNSW 使用了“随机邻居连接”的策略。 每个点通过固定数量的边与其他点连接形成邻居节点集。这些连接不仅仅局限于靠近的点还包含一定的随机性从而确保图的连通性和避免局部最优。 随机性初始构建图时每个节点根据一定的概率与其他节点连接特别是在高层图中随机连接允许跨越较大距离的跳跃。局部连接在较低层次图中节点之间的连接更多是局部的与几何上相近的节点形成密集连接。 搜索过程 搜索过程可以分为以下几个阶段 从最高层开始从顶层的一个起始节点出发使用贪心搜索逐步寻找距离目标向量最近的邻居。逐层向下跳跃一旦在顶层找到距离目标较近的节点搜索算法会转移到下一层继续在下一层寻找更接近目标的邻居。这种逐层跳跃过程可以加速搜索因为每层的图连接性不同可以提供全局导航和局部细化。局部搜索当搜索到最底层时图的密度更高搜索会在局部邻居之间进行更精确的距离计算最终找到目标的近似最近邻。
4.代码
M 16 # 每个顶点的连接数
ef_search 8 # 搜索的深度
ef_construction 64 # 构建时的扩展因子决定了在构建图时为每个点找到最近邻的搜索深度index faiss.IndexHNSWFlat(d, M)index.hnsw.efSearch ef_search
index.hnsw.efConstruction ef_constructionindex.add(xb)D, I index.search(xq, k)M(最大连接数) 每个节点最大的连接边数。值越大搜索的结果更精确但构建和查询的成本会变大。通常 16 - 48 efConstruction(构建阶段的扩展因子) 控制图的构建质量值越大构建的图结构越精细精度越高但构建时间增加。efConstruction 通常设定为大于 M 的值。其实设置一个比较大的值最好 efSearch(查询阶段的扩展因子) 控制查询阶段的搜索广度。值越大搜索的邻居节点越多精度越高但查询速度变慢常为 50 - 200
4.IVF
1.解决的问题
IVFInverted File Index主要是为了解决大规模、高维向量数据集的最近邻搜索问题。
在高维数据集上执行精确的最近邻搜索代价极高尤其是当数据量大、维度高时计算距离的成本成指数级增长导致搜索时间和内存占用都难以接受。
2.原理 数据分簇(clustering) IVF 的核心思想是聚类。通过将数据点分成多个簇算法可以大大减少在查询时需要计算的向量数量。 使用聚类进行分簇常用 k-means。将数据集划分为多个簇每个簇用一个质心(centroid) 表示。构建倒排文件一旦聚类完成算法会为每个簇构建一个倒排列表。每个倒排索引列表中存储了归属于该簇的所有向量的 ID。这类似于搜索引擎中倒排索引的结构用于快速定位相关文档数据划分数据集中的每个向量会被分配到某个簇即它与该簇的质心距离最近。这样整个数据集被划分为多个部分每部分对应一个簇。 倒排索引 倒排索引是一种数据结构它将向量空间中的特征通常是聚类中心或代表向量映射到包含该特征的所有数据点向量的列表。这种结构通过预先对数据进行分组实现了快速的近似最近邻搜索特别适用于高维向量空间中的大规模数据检索。 例如 传统索引正向索引 条目“番茄炒蛋的做法 A” - 页码10-20页 倒排索引 “番茄” - 条目列表{“番茄炒蛋的做法 A”, …}“炒蛋” - 条目列表{“番茄炒蛋的做法 A”, …} 查询阶段 在进行搜索时IVF 只需在部分簇中执行最近邻搜索从而大大减少了距离计算的次数。搜索过程如下 查找最近的质心首先查询向量会与所有质心进行距离计算从中选出与查询向量距离最近的几个质心。这一步用于粗略定位查询向量可能所在的簇。通常选择距离最近的 nprobe 个质心而不是所有质心。在对应的簇中搜索选定最近的质心后搜索会在这些对应的簇中查找最近邻。由于这些簇包含的数据点较少算法只需在这些簇内进行精细的距离计算从而有效减少了搜索范围。返回最近邻通过在选中的簇中执行最近邻搜索最终返回最接近查询向量的几个数据点
3.代码
nlist 128 # 质心数量quantizer faiss.IndexFlatIP(d) # 可以减少内存占用并提高搜索速度
index faiss.IndexIVFFlat(quantizer, d, nlist)index.train(xb) # 需要训练index.add(xb)index.nprobe 1%%time
D, I index.search(xq, k)nlist(聚类数量) 在训练阶段创建的聚类(桶)的数量nlist 的值越大划分的簇越多簇内的向量数量就越少查询速度更快但索引构建时间和内存占用可能会增加。通常 nlist 的选择取决于数据的规模经验上建议 nlist 与数据量的平方根成比例 nprobe探测簇的数量 在查询时nprobe 控制查询向量要搜索的簇的数量。nprobe 值越大查询精度越高但计算成本也相应增加。一般而言可以通过调节 nprobe 来在搜索精度和速度之间找到平衡
