14.11-相似度检索

要点

  • 相似度检索的本质：在向量空间里找离查询向量最近的 k 个向量
  • 三种距离度量：余弦相似度、欧氏距离、点积——语义检索几乎都用余弦相似度
  • 精确搜索（暴力遍历）在大规模数据上不可行，需要近似最近邻（ANN）索引
  • 四种主流索引：IVF（倒排文件）、HNSW（图索引）、PQ（乘积量化）、LSH（局部敏感哈希）
  • 索引选型没有银弹——按数据规模、内存、延迟要求选择
  • 检索质量用 Recall@K 衡量——不是 top1 越准越好，要关心 top10 里有多少正确答案

1. 距离度量

余弦相似度（Cosine Similarity）

衡量两个向量的方向相似程度，不考虑长度。

cos(θ) = (A · B) / (|A| × |B|)

范围：[-1, 1]
- 1：方向完全相同
- 0：正交，无关
- -1：方向完全相反

function cosineSimilarity(a: number[], b: number[]): number {
  let dot = 0
  let normA = 0
  let normB = 0
 
  for (let i = 0; i < a.length; i++) {
    dot += a[i] * b[i]
    normA += a[i] * a[i]
    normB += b[i] * b[i]
  }
 
  return dot / (Math.sqrt(normA) * Math.sqrt(normB))
}

文本检索场景几乎都用余弦相似度。因为文本经过 embedding 后通常会被归一化（长度为 1），此时余弦相似度等价于点积。

欧氏距离（Euclidean Distance）

衡量两个点在空间中的直线距离。

d(A, B) = √(Σ(Ai - Bi)²)

function euclideanDistance(a: number[], b: number[]): number {
  let sum = 0
  for (let i = 0; i < a.length; i++) {
    sum += (a[i] - b[i]) ** 2
  }
  return Math.sqrt(sum)
}

适合向量没有归一化、绝对位置有意义的场景。文本检索场景用得少。

点积（Inner Product / Dot Product）

A · B = Σ(Ai × Bi)

function dotProduct(a: number[], b: number[]): number {
  let sum = 0
  for (let i = 0; i < a.length; i++) {
    sum += a[i] * b[i]
  }
  return sum
}

如果向量已归一化（长度为 1），点积等于余弦相似度。很多向量数据库在归一化向量场景下用点积代替余弦——计算更快。

距离度量的选择

场景推荐
文本语义检索余弦相似度（或归一化后点积）
图像检索余弦相似度
推荐系统点积（用户/物品向量不一定归一化）
地理位置欧氏距离

2. 精确搜索 vs 近似搜索

暴力搜索（Flat / Brute Force）

遍历所有向量，计算距离，取 topK。

function bruteForceSearch(
  queryVector: number[],
  vectors: number[][],
  topK: number,
  metric: 'cosine' | 'euclidean' | 'dot' = 'cosine'
): Array<{ index: number; score: number }> {
  const distances = vectors.map((v, i) => ({
    index: i,
    score: metric === 'cosine' ? cosineSimilarity(queryVector, v) : euclideanDistance(queryVector, v),
  }))
 
  distances.sort((a, b) => b.score - a.score)  // cosine 越大越近
  return distances.slice(0, topK)
}

时间复杂度：O(N × D)，N 是向量数，D 是维度。

  • 10 万条 768 维向量：~7600 万次浮点运算，几十毫秒
  • 100 万条：几百毫秒到几秒
  • 1 亿条：不可行

近似最近邻（ANN）

核心思想：牺牲一点精度，换取几个数量级的速度提升。

ANN 索引不保证找到「真正最近的」k 个向量，而是找到「大概率很近的」k 个。通常用 Recall@K 衡量质量：

Recall@K = 真正 topK 中被找到的数量 / K

比如 Recall@10 = 0.9 意味着平均 10 个结果里有 9 个是真正最近的。

3. IVF 索引（倒排文件）

核心思路

把所有向量聚类成 nlist 个簇。查询时只搜索最近的几个簇，跳过远的簇。

训练阶段：
1. 随机选 nlist 个向量作为聚类中心
2. 每个向量分配到最近的聚类中心
3. 重复直到收敛（类似 K-Means）

查询阶段：
1. 计算查询向量和所有聚类中心的距离
2. 选最近的 nprobe 个簇
3. 只在这 nprobe 个簇里暴力搜索

聚类中心: [C1, C2, C3, C4, ...]

查询向量 Q → 最近的聚类中心: C2, C5
→ 只搜索 C2 和 C5 的向量
→ 跳过 C1, C3, C4, ... 的向量

参数

  • nlist：聚类数。经验值：sqrt(N) 到 4 * sqrt(N)，N 是向量总数
  • nprobe：查询时搜索的簇数。越大越精确但越慢

优缺点

  • 优点：内存占用和原始向量差不多（存原始向量 + 聚类中心）
  • 缺点：需要训练（先有数据才能建索引）；边界区域的向量容易被跳过

PQ 结合（IVF_PQ）

IVF 可以和乘积量化（Product Quantization）结合，进一步压缩内存。

PQ 把向量切成若干段，每段独立量化。比如 768 维切成 96 段，每段 8 维，用 8 bit 表示——存储从 32×768 = 24576 bit 降到 8×96 = 768 bit，压缩 32 倍。

原始向量: [0.12, -0.34, 0.88, ..., 0.05]  (768 维, 32 bit float)

PQ 量化:
  段 1: [0.12, -0.34, 0.88, ...] (8 维) → code 42
  段 2: [0.56, -0.11, 0.23, ...] (8 维) → code 15
  ...
  段 96: [...] → code 88

量化后: [42, 15, ..., 88]  (96 bytes vs 3072 bytes)

精度损失比 IVF_FLAT 大，但内存占用极低——适合超大规模场景。

4. HNSW 索引（分层导航小世界）

核心思路

构建多层图结构。上层稀疏，用于快速跳跃；下层密集，用于精确定位。

Layer 2 (最稀疏):  A -------- D
                   |          |
Layer 1 (中等):    A --- B --- D --- F
                   |  |  |  |  |  |
Layer 0 (最密集):  A-B-C-D-E-F-G-H-I-J

查询时从最上层开始，贪心搜索——找到当前层最近的节点，往下走到下一层，继续贪心搜索，直到最底层。

// HNSW 查询伪代码
function hnswSearch(query: number[], entryPoint: Node, layers: Layer[]): Node[] {
  let current = entryPoint
 
  // 从最上层往下，快速定位大致区域
  for (let layer = layers.length - 1; layer > 0; layer--) {
    current = greedySearch(query, current, layers[layer])
  }
 
  // 在最底层精细搜索
  return beamSearch(query, current, layers[0], topK)
}

参数

  • M：每个节点的最大连接数。通常 12-64
  • efConstruction：构建索引时的搜索宽度。越大索引质量越好，但构建越慢
  • ef：查询时的搜索宽度。越大越精确但越慢

优缺点

  • 优点：查询速度极快（通常 O(log N)），不需要训练
  • 缺点：内存占用高（每个节点存 M 个邻居指针），构建慢

实际表现

对于百万级向量：

索引类型查询延迟内存占用Recall@10
Flat~500ms3GB（768维）1.0（精确）
IVF_FLAT (nlist=1024, nprobe=16)~5ms3.1GB0.92
HNSW (M=16, ef=128)~2ms4.5GB0.95
IVF_PQ (nlist=1024, m=96)~3ms0.5GB0.85

HNSW 在查询速度和精度上通常最优，但内存占用最高。

5. 向量归一化

归一化把每个向量缩放到单位长度。

function normalize(vector: number[]): number[] {
  let norm = 0
  for (const v of vector) {
    norm += v * v
  }
  norm = Math.sqrt(norm)
 
  return vector.map((v) => v / norm)
}

归一化后：

  • 余弦相似度 = 点积
  • 欧氏距离² = 2 × (1 - 余弦相似度)

很多向量数据库（包括 Qdrant、Milvus）在内部会自动归一化。如果 embedding 模型输出的向量已经归一化，不需要重复处理。

6. 检索质量的衡量

Recall@K

Recall@K = |{真正 topK} ∩ {检索到的 topK}| / K

比如真正最近的 10 个向量是 A, B, C, D, E, F, G, H, I, J，索引返回了 A, B, C, D, E, F, G, H, K, L，则 Recall@10 = 8/10 = 0.8。

影响 Recall 的因素

  1. 索引类型和参数：nprobe / ef 越大，Recall 越高
  2. 数据分布：向量分布均匀时 ANN 效果好，分布偏斜时可能退化
  3. 维度：维度越高，「近邻」的概念越模糊（维度灾难）

实际测试

async function evaluateRecall(
  testQueries: Array<{ query: number[]; groundTruth: string[] }>,
  searchFn: (q: number[]) => Promise<string[]>,
  k: number
): Promise<number> {
  let totalRecall = 0
 
  for (const { query, groundTruth } of testQueries) {
    const results = await searchFn(query)
    const correctCount = results.filter((r) => groundTruth.includes(r)).length
    totalRecall += correctCount / k
  }
 
  return totalRecall / testQueries.length
}

生产环境的 Recall@10 通常要求 >= 0.9。如果低于 0.85，需要调参或换索引。

7. 检索优化

预过滤 + 后过滤

向量数据库的过滤查询有两种执行策略：

预过滤（Pre-filtering）：
1. 先用标量条件过滤出候选集
2. 在候选集上做向量检索
→ 精确，但候选集太小时向量检索效果差

后过滤（Post-filtering）：
1. 先做向量检索，返回 topK × 2 的结果
2. 用标量条件过滤掉不符合的
→ 快，但可能过滤后结果不足 topK

大多数向量数据库（Qdrant、Milvus）用的是预过滤或混合策略。

批量化

查询多个向量时，批量化可以减少网络往返：

// ❌ 逐条查询
for (const query of queries) {
  const results = await vectorDB.search(query)
}
 
// ✅ 批量查询
const results = await vectorDB.searchBatch(queries)

缓存

热门查询的检索结果可以缓存：

async function searchWithCache(queryVector: number[]): Promise<SearchResult[]> {
  const cacheKey = `search:${hashVector(queryVector)}`
  const cached = await redis.get(cacheKey)
  if (cached) return JSON.parse(cached)
 
  const results = await vectorDB.search(queryVector)
  await redis.set(cacheKey, JSON.stringify(results), 'EX', 300)  // 5 分钟
  return results
}

总结

回顾这一节的要点：

  • 三种距离度量：余弦相似度（文本首选）、欧氏距离、点积
  • 暴力搜索在大规模数据上不可行，需要 ANN 索引
  • IVF（倒排文件）：聚类后搜索局部，内存占用适中
  • HNSW（图索引）：查询快、精度高，但内存占用高
  • IVF_PQ：结合量化压缩，适合超大规模
  • 向量归一化后余弦相似度等于点积
  • Recall@K 衡量检索质量，生产环境通常要求 >= 0.9
  • 过滤策略分预过滤和后过滤，各有取舍

下一篇讲混合检索——怎么把向量检索和关键词检索结合起来。