向量计算-第04章-近似最近邻搜索算法

清华大学出版社《向量计算》配套课件·课堂讲义第4章近似最近邻搜索（ANN）算法换个角度学AI，打通任督二脉刘鹏著·清华大学出版社用极小的精度损失，换取成百上千倍的速度提升《向量计算》配套课件第4章近似最近邻搜索（ANN）算法第4章近似最近邻搜索（ANN）算法2/42教学目标1理解ANN「牺牲精度换速度」的核心思想2掌握KD-Tree与LSH的原理、参数与适用边界3深入理解HNSW分层结构、搜索过程与三参数调优4掌握SQ/PQ量化原理，能按场景选择索引与压缩策略5能用Faiss/Milvus构建并评估HNSW与IVF+PQ索引重点与难点1重点：HNSW的分层结构与m、efConstruction、ef参数2重点：PQ子向量分解、码本编码与压缩比3难点：维度灾难导致KD-Tree性能退化的机理4难点：距离表预计算与非对称距离计算（ADC）《向量计算》配套课件第4章近似最近邻搜索（ANN）算法第4章近似最近邻搜索（ANN）算法3/42本章内容导航4.1暴力搜索（KNN）的局限性4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）4.3核心算法详解：HNSW4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）4.5本章小结《向量计算》配套课件·第4章近似最近邻搜索（ANN）算法4.1暴力搜索（KNN）的局限性基本原理·时间与空间代价·适用场景·精度vs速度·ANN核心思想《向量计算》配套课件4.1暴力搜索（KNN）的局限性第4章近似最近邻搜索（ANN）算法5/42KNN基本原理与工作流程●原理：与库中所有向量逐一算距离，取最近K个–流程：接收query→全量算距→选Top-K→返回●单次距离计算O(d)，N次累计O(N×d)（表4-1）–找Top-K需排序O(N×logK)，大头仍是距离计算●总体O(N×d)：查询耗时随库规模线性增长《向量计算》配套课件4.1暴力搜索（KNN）的局限性第4章近似最近邻搜索（ANN）算法6/42代码示例：KNN暴力搜索importnumpyasnpfromsklearn.metrics.pairwiseimporteuclidean_distances#假设我们有1000个128维的向量database=np.random.randn(1000,128)#数据库向量query=np.random.randn(1,128)#查询向量#方法1：使用sklearn计算欧氏距离distances=euclidean_distances(query,database)[0]#方法2：手动实现defknn_search(query,database,k=10):#计算距离矩阵distances=np.sqrt(np.sum((database-query)**2,axis=1))#找到距离最小的k个索引top_k_indices=np.argpartition(distances,k)[:k]#对这k个结果排序top_k_indices=top_k_indices[np.argsort(distances[top_k_indices])]top_k_distances=distances[top_k_indices]returntop_k_indices,top_k_distances注：摘自4.1.1节：sklearn距离or手动实现，argpartition取Top-K《向量计算》配套课件4.1暴力搜索（KNN）的局限性第4章近似最近邻搜索（ANN）算法7/42暴力搜索的时空账单：规模是座大山1亿×128维：128亿次FLOP÷10亿次/秒≈128秒≈2.1分钟计入内存延迟、I/O、排序后实际可达5～10分钟存储：1亿×128×4B=51.2GB，另加距离值400MB●10万向量约0.2秒，10亿约2000秒（表4-2）●毫秒级响应的互联网时代，暴力搜索不可接受《向量计算》配套课件4.1暴力搜索（KNN）的局限性第4章近似最近邻搜索（ANN）算法8/42暴力搜索并非一无是处：适用场景●小规模数据：小于10万、查询频率不高●离线批量处理：数据分析、离线推荐●作为基准：评估ANN算法准确性与正确性–图中不同颜色代表不同类别的决策边界图4-1KNN在二维数据上的分类示例《向量计算》配套课件4.1暴力搜索（KNN）的局限性第4章近似最近邻搜索（ANN）算法9/42问题的本质：我们真需要100%准确吗？●暴力搜索优势：100%准确，必找到真最近邻–电商推荐：0.95与0.96的相似度用户能感知吗？–图像搜索：第100名与第101名差距真有那么大？●没人愿为5%精度提升，等待10倍的时间——答案是否定的●结论：用少量准确性换巨大速度提升，即ANN的由来《向量计算》配套课件4.1暴力搜索（KNN）的局限性第4章近似最近邻搜索（ANN）算法10/42暴力搜索vsANN算法对比对比维度暴力搜索ANN算法时间复杂度O(N×d)O(logN×d)~O(N^a×d),0<a<1准确性100%90%～99%查询延迟秒级到分钟级毫秒级内存需求O(N)O(N)-O(N×k)适用场景小数据、离线分析大数据、实时应用索引构建时间O(1)O(N×logN)《向量计算》配套课件4.1暴力搜索（KNN）的局限性第4章近似最近邻搜索（ANN）算法11/42ANN核心思想：只搜「可能」的邻居●图书馆找书：逐本翻阅vs先定位书架再查找●关键手段：构建索引（Index）加速相似度搜索–索引构建有成本，查询时大幅减少候选向量–图示：不同搜索策略的效率差异一目了然图4-2不同搜索策略的示意图《向量计算》配套课件·第4章近似最近邻搜索（ANN）算法4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）两类经典ANN：思路值得先学，再自然引出HNSW《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法13/42KD-Tree：递归切分k维空间●KD-Tree：递归划分k维空间、加速最近邻的树●①选一个维度切分（通常取方差最大的维度）–②切分点取中位数–③小于切分点的归左，大于的归右–④对左右两部分递归重复上述过程●直接基于数据构建，无需训练，得到一棵平衡树《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法14/42KD-Tree的结构：切分线与树的对应●左图：数据点分布与切分线；右图：对应树结构●根节点沿X轴切分：蓝色竖线X=5–左子树沿Y轴切分：红色横线Y=4–右子树沿Y轴切分：红色横线Y=2●叶子节点包含具体的数据点图4-3数据分布及对应的KD-Tree结构《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法15/42KD-Tree的构建与搜索过程●每个节点包含数据点及其坐标●搜索：从根判断进左/右子树，递归下行到叶子●回溯时检查另一子树中是否有更近的点–重复直至收敛，找到最近邻●低维查询O(logN)，理论基础扎实图4-4KD-Tree的构建过程《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法16/42KD-Tree的致命伤：维度灾难●CurseofDimensionality：维度增加，性能急剧下降–高维空间中数据点变得非常稀疏–切分效果变差：大部分点都落在边界附近–需搜索的子树数量激增，复杂度退化为O(N)●100维以上向量（如文本向量）基本不可用●适用：低维（<20）、静态、不超100万条数据《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法17/42KD-Tree在不同维度下的性能表现维度数据量查询时间相对暴力搜索的加速比2维10万0.0001秒1000倍10维10万0.01秒10倍20维10万0.1秒1倍（相当）50维10万0.5秒0.2倍（更慢！）100维10万1秒0.1倍（更慢！）《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法18/42LSH：让相似向量落进同一个桶●传统哈希（MD5）：相似输入映射到完全不同的值●LSH恰恰相反：相似输入高概率哈希到同一个桶–图中v1、v3被映射到bucket1，v2到bucket2●查询向量经哈希函数定位桶，只搜同桶向量–搜索范围大幅缩小图4-5LSH的工作原理《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法19/42LSH家族：一种度量配一种哈希●LSH不是单一算法，而是一类算法●Jaccard相似度→MinHash：集合最小哈希签名●欧氏距离→RandomProjection：随机超平面定侧–向量在超平面哪侧记1/0，编码串作桶key–多表收集候选后精算距离，取Top-K●余弦相似度→SimHash：投影正负生成hash位《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法20/42多哈希表策略与LSH关键参数●多表（table1/2/3）降低碰撞概率、提高召回率–相似向量同桶概率↑，但牺牲一些精确率●L（表数）↑：召回率↑，查询时间与内存↑●K（超平面数）↑：精确率↑但召回率↓，可能漏掉相似向量–桶数量↑：精确率↑召回率↓（表4-5）图4-6多哈希表的LSH策略《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法21/42LSH的理论保证与优劣势●保证：q的最近邻以一定概率在(1+c)倍半径内被找到●优势：理论坚实、适合高维、可并行、增量更新友好–新向量只需重算hash值插入对应桶●劣势：参数敏感、多表内存消耗大–精确率与召回率难两全，查询质量不稳定图4-7LSH的理论保证《向量计算》配套课件4.2基于树的方法（KD-Tree）与基于哈希的方法（LSH）第4章近似最近邻搜索（ANN）算法22/42不同搜索方法的对比方法适用维度查询时间索引构建准确性主要优势主要劣势暴力搜索任意慢（O(N)）快（O(1)）100%简单、准确太慢KD-Tree低维（<20）快（O(logN)）中等（O(NlogN)）高理论基础好维度灾难LSH高维中等快（O(N)）中等适合高维参数敏感HNSW高维快（O(logN)）慢（O(NlogN)）高性能最优构建慢《向量计算》配套课件·第4章近似最近邻搜索（ANN）算法4.3核心算法详解：HNSW暴力太慢、KD-Tree高维失效、LSH参数敏感——需要高维有效、快、准、免调参的算法：HNSW，被Milvus、Pinecone、Chroma等广泛采用《向量计算》配套课件4.3核心算法详解：HNSW第4章近似最近邻搜索（ANN）算法24/42从小世界图（SW）到可导航小世界（NSW）●小世界图：任意两点平均距离短＋有很多捷径边–例：社交网络六度分隔、互联网、大脑神经元–核心特征：短路径、高聚集●难题：贪心搜索只见局部，易陷局部最优「死胡同」●NSW：故意保留足够多长程边，保证可导航性●NSW大规模数据仍需遍历大量节点→HNSW引入分层《向量计算》配套课件4.3核心算法详解：HNSW第4章近似最近邻搜索（ANN）算法25/42HNSW的分层结构：高速公路+本地道路●顶层似高速公路快速跳跃，底层似本地道路精细搜索●第0层G_0含所有节点，第i层是第i-1层子集–顶层（绿）稀疏、中间层渐多、底层（蓝紫）最密●层级随机分配、服从几何分布，上层节点指数级减少–m：每层平均连接数；L：最大层数图4-8HNSW的分层结构《向量计算》配套课件4.3核心算法详解：HNSW第4章近似最近邻搜索（ANN）算法26/42HNSW的搜索过程：两个阶段●阶段1（顶层向下）：从入口点出发（ef=1）–当前层找最近邻居，若更近则移动，直到没有–逐层下降，重复贪心搜索，快速接近目标区域●阶段2（底层精细搜索）：在第0层继续扩展–每步走向更近邻居直至收敛，返回最优节点●类似城市导航：高速接近目标区，再按详细地图找《向量计算》配套课件4.3核心算法详解：HNSW第4章近似最近邻搜索（ANN）算法27/42HNSW搜索过程：逐层缩小范围●从顶层向下搜索，逐层缩小搜索范围●最后在底层（第0层）找到精确结果●构建时同理：新节点随机分层，逐层选m个邻居–建立双向连接，超过Mmax时裁剪邻居图4-9HNSW搜索过程示意图《向量计算》配套课件4.3核心算法详解：HNSW第4章近似最近邻搜索（ANN）算法28/42HNSW参数对性能的影响参数推荐范围增加该参数查询时间准确性构建时间内存m（每层连接数）16～32↗↘（减少）↗（提高）↗（增加）↗（增加）efConstruction（构建宽度）200～500↗↘（减少）↗（提高）↗（增加）↗（增加）ef（查询宽度）50～200↗↗（增加）↗（提高）无影响无影响《向量计算》配套课件4.3核心算法详解：HNSW第4章近似最近邻搜索（ANN）算法29/42实战：用Faiss构建HNSW索引importfaissnp.random.seed(42)data=np.random.randn(100000,128).astype('float32')#10万个128维向量query=np.random.randn(1,128).astype('float32')#查询向量#定义HNSW索引dim=128M=16index=faiss.IndexHNSWFlat(dim,M)#设置构建参数index.hnsw.efConstruction=200#构建时的搜索宽度index.hnsw.efSearch=100#搜索时的搜索宽度index.add(data)k=10#返回前10个最相似的向量distances,indices=index.search(query,k)#计算召回率recall=len(set(indices[0])&set(true_indices[0]))/k注：调优策略：先调高efConstruction与ef建好索引；高精度ef=200~500，速度优先ef=50~100；小数据m=16，大数据m=32《向量计算》配套课件4.3核心算法详解：HNSW第4章近似最近邻搜索（ANN）算法30/42HNSW的优势与劣势（综合对比表4-8）●优：O(logN)查询，Top-10召回率通常95%以上●优：100维以上仍有效；主要参数少；支持增量更新●劣：构建需O(NlogN)，时间长–劣：需存多层图，内存消耗较大–劣：数据超1亿时构建时间可能过长●表4-8：查询速度与准确性均最优→当前最主流《向量计算》配套课件·第4章近似最近邻搜索（ANN）算法4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）HNSW之外的另一半拼图：在亿级数据与内存受限场景压缩向量《向量计算》配套课件4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）第4章近似最近邻搜索（ANN）算法32/42为什么需要量化：再算一笔账1亿×512维×4B=204.8GB→uint8：1亿×512×1B=51.2GB（省75%）量化（Quantization）：连续浮点值→有限离散值更极端的压缩：uint4压缩比1:8，二值化1:32（表4-9）●收益：省内存、整数运算快、减少磁盘/网络I/O–收益：SIMD指令集对整数运算有专门优化《向量计算》配套课件4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）第4章近似最近邻搜索（ANN）算法33/42量化如何工作：码本生成器●原始向量被分解成多个子向量●每个子向量映射到最近的码本向量●生成紧凑编码（Code）加速检索图4-10码本生成器的工作流程《向量计算》配套课件4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）第4章近似最近邻搜索（ANN）算法34/42标量量化（SQ）：逐维独立压缩q=round((x−x_min)/(x_max−x_min)×255)；x̂=q/255×(x_max−x_min)+x_min均匀（线性）量化：[x_min,x_max]等分为256个子区间非均匀（Lloyd-Max）：密集区分更细，MSE更小但复杂度高float32→float16/bfloat16：免计算缩放因子的「免训练」量化●SQ特点：实现简单、任意维度、支持增量更新–局限：忽略维度间相关性，float32→uint8最多4倍压缩《向量计算》配套课件4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）第4章近似最近邻搜索（ANN）算法35/42乘积量化（PQ）：分而治之的极致压缩●128维向量切成8个16维子向量●每个子向量独立K-means建码本：256个中心点●编码=最近中心索引，8位=1字节/子向量●128维浮点向量压缩为8字节，压缩比可达64倍–四步：分解v=[v1..vM]→建码本→编码argmin‖vi−cj‖²→组合●距离查询：预计算查询与各中心的距离表，查表相加《向量计算》配套课件4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）第4章近似最近邻搜索（ANN）算法36/42PQ工作流程与优劣●向量分解为子向量，逐个子量化成紧凑编码●优：距离表使批量距离计算极快；内存友好–优：10亿级向量也能高效工作●劣：需训练多个K-means，时间长–劣：量化损失精度；不适合增量更新●ADC非对称距离：查询保留原向量，库向量用编码图4-12PQ的工作流程《向量计算》配套课件4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）第4章近似最近邻搜索（ANN）算法37/42标量量化vs乘积量化对比维度标量量化（SQ）乘积量化（PQ）压缩比最高4倍可达64倍训练时间快慢（需要K-means）查询速度快快（使用距离表）量化误差较大较小（考虑向量结构）内存占用较低很低增量更新容易困难适用场景一般需求超大规模数据、内存受限《向量计算》配套课件4.4向量量化技术：乘积量化（PQ）与标量量化（SQ）第4章近似最近邻搜索（ANN）算法38/42量化实战：Faiss的PQ与IVF+PQimportfaissdata=np.random.randn(1000000,128).astype('float32')#100万个128维向量query=np.random.randn(1,128).astype('float32')#方法1：纯PQ量化d=128#向量维度M=16#子向量数量nbits=8#每个子向量的编码位数index_pq=faiss.IndexPQ(d,M,nbits)index_pq.train(data)index_pq.add(data)k=10distances_pq,indices_pq=index_pq.search(query,k)#方法2：IVF+PQnlist=100#倒排列表数量quantizer=faiss.IndexFlatL2(d)#量化器index_ivfpq=faiss.IndexIVFPQ(quantizer,d,nlist,M,nbits)index_ivfpq.train(data)index_ivfpq.add(data)index_ivfpq.nprobe=10#搜索的倒排列表数量distances_ivfpq,indices_ivfpq=index_ivfpq.search(query,k)