词汇/表达差异-10-LSH（局部敏感哈希）

LSH（局部敏感哈希）技术概述 LSH是一种高效的高维数据近邻检索方法，通过特殊设计的哈希函数使相似数据大概率映射到相同哈希桶。其核心原理是利用AND/OR构造实现概率放大，通过调整波段(b)和行数(r)平衡查全率与查准率。相比传统两两比较方法，LSH可将复杂度从O(N×D)降至近O(N)。该技术特别适合文本去重、推荐系统等场景，但存在参数调优复杂、不保证100%召回等局限。主流实现包括datas

natide

1351人浏览 · 2025-12-25 20:39:48

natide · 2025-12-25 20:39:48 发布

1.基本原理

LSH（Locality Sensitive Hashing，局部敏感哈希）是一种面向高维数据的近邻检索技术，核心思想是通过 “哈希函数将相似的数据映射到相同哈希桶的概率远高于不相似数据” 的特性，在大规模数据中快速找到相似对象，避免了传统 “两两比较” 的高复杂度。
基本思路：

签名生成：为每个数据对象生成签名向量
分桶与哈希：将签名向量分桶，计算每个桶的哈希值并将对象映射到桶中；
候选查询：根据目标对象的签名向量，找到所有可能的候选对象，再计算真实相似度。

1.1 核心问题：高维数据的相似检索困境

对于高维数据（如文本的MinHash签名、图像的特征向量、用户的行为特征），要找到与目标数据相似的对象，传统方法是两两计算相似度，时间复杂度为 $\times D)$ （ $N$ 为数据量， $D$ 为数据维度）。当 $N$ 达到百万/千万级时，这种方法在工程上完全不可行。

LSH的核心解决思路是：构造“局部敏感”的哈希函数，让相似的数据大概率映射到同一个哈希桶，仅对同一桶内的数据计算相似度，从而将检索复杂度从 $\times D)$ 降低到接近 $O (N)$ （线性复杂度）。

1.2 局部敏感的定义（核心数学特征）

一个哈希函数族 $H\mathcal{H}$ 被称为对相似度度量 $sim(⋅,⋅)sim(\cdot, \cdot)$ 局部敏感，当且仅当对于任意两个数据 $x, y $：

若 $x$ 与 $y$ 相似（ $\geq t$ ， $t$ 为相似度阈值），则 $h (x) = h (y)$ 的概率为 $p_1$ （高概率）；
若 $x$ 与 $y$ 不相似（ $s im (x, y) < t$ ），则 $h (x) = h (y)$ 的概率为 $p_2$ （低概率）；
满足 $p_1 > p_2$ 。

简单来说：相似的数据，哈希值相同的概率高；不相似的数据，哈希值相同的概率低——这是LSH与普通哈希（追求均匀分布、低碰撞）的本质区别。

1.3 常见的LSH类型（按相似度度量划分）

不同的相似度度量对应不同的LSH哈希函数族，工程中最常用的有三类：

相似度度量	对应的LSH类型	核心应用场景
Jaccard相似度	MinHash LSH	文本集合相似检索、文档去重
余弦相似度	Random Projection LSH（随机投影LSH）	高维向量相似检索（如图像特征、词嵌入）
欧氏距离	Euclidean LSH（如p-stable LSH）	数值向量的近邻检索（如推荐系统的用户特征）

其中，MinHash LSH是文本处理中最常用的类型，也是我们后续实现和示例的重点。

2.算法步骤

LSH的核心是一个巧妙的概率设计，它基于一个直观的观察：如果两个数据整体相似度高，那么它们在数据的某一部分（波段）完全相同概率就很高。

🔧 实现机制：Amplification via AND/OR Construction

为了增强区分能力，LSH 使用两种组合方式：

构造	效果	用途
AND（串联）	降低假阳性 → 提高 precision	要求多个哈希值同时相等才视为候选
OR（并联）	降低假阴性 → 提高 recall	只要任一哈希组相等就算候选

实际中采用 “b bands of r rows” 结构（以 MinHash 为例）：

将 k 维 MinHash 签名分成 b 个 band，每个 band 含 r 行（k = b × r）
对每个 band 做一次哈希（如 tuple hash）
只要有一个 band 完全相同，就认为两项目相似

📌 这相当于：OR(bands) of AND(rows)

📈 相似度 vs 命中概率（S型曲线）

命中概率为：
$P_{\text{hit}}(s) = 1 - (1 - s^r)^b$
其中 $s$ 是 Jaccard 相似度。

通过调整 b 和 r，可控制“希望捕获的相似度阈值”：

想找高相似对（s ≥ 0.8）？→ 增大 r，减小 b
想提高召回？→ 减小 r，增大 b

假设我们用128维的MinHash签名，设定 b=16 个波段，每个波段 r=8 行（因为 b * r = 128）。

对于高度相似的数据：假设它们真实的Jaccard相似度为 s=0.8。那么，在一个特定波段（8行）上所有值都相等的概率为 s^r = 0.8^8 ≈ 0.168。这个概率看起来不高，但我们有16次独立机会（16个波段）。它们在至少一个波段上完全匹配的概率高达 1 - (1 - 0.168)^16 ≈ 0.96。这意味着，96%的高度相似对都会被我们发现并放到同一个桶里。
对于低度相似的数据：假设相似度 s=0.3。在一个波段上完全匹配的概率为 0.3^8 ≈ 0.0000656。它们在至少一个波段上碰撞的概率仅为 1 - (1 - 0.0000656)^16 ≈ 0.001。这意味着，99.9%的不相似数据对都不会被误放到同一个桶里。

通过调整 b 和 r，我们可以像操纵一个概率阀门，在查全率和查准率之间进行权衡：

增加波段 b（减少每个波段的行数 r）：碰撞条件变宽松，查全率上升，但可能引入更多不相似的假阳性对。
减少波段 b（增加每个波段的行数 r）：碰撞条件变严格，结果更精确，但可能漏掉一些相似对（假阴性）。

3.优缺点适用场景

特点	说明
✅ 核心优点	亚线性查询时间：平均 O(1) 或 O(log N) 候选，避免 O(N) 全扫内存可控：哈希表大小由 b 控制理论保证：可分析召回率与精度。流式友好：支持动态插入与 MinHash 天然集成：适合集合数据。
❌ 主要缺点	仅支持特定相似度：Jaccard（MinHash）、余弦（SimHash）、L2（随机投影）等，需匹配 LSH 变种。参数调优复杂：b/r/threshold 影响性能与效果。有漏检风险：不保证 100% 召回，是“近似”算法。不适用于稠密向量通用场景：如 BERT 嵌入更适合 FAISS、Annoy。
🛠️ 典型使用场景	实体解析：生成候选匹配对（blocking 阶段）日志聚类：将相似错误日志归类（。推荐系统：查找兴趣相似的用户（基于行为集合

4.框架选型

库名称	底层实现	核心优势	适用场景
datasketch	C++（Python绑定）	轻量、高效，支持MinHash LSH	中小规模文本数据
faiss	C++	支持多种LSH（如Random Projection LSH）、分布式检索	大规模高维向量检索
PySpark MLlib	Scala（Python绑定）	分布式LSH实现，支持海量数据	大数据集群（Spark）

6.使用

推荐使用faiss（工业级的高维向量检索库）：

# 安装：pip install faiss-cpu
import faiss
import numpy as np

# 生成示例向量（1000个128维的向量）
vectors = np.random.rand(1000, 128).astype('float32')

# 初始化LSH索引
index = faiss.IndexLSH(128, 20)  # 128维，20个哈希函数
index.add(vectors)

# 查询相似向量
query = np.random.rand(1, 128).astype('float32')
D, I = index.search(query, 5)  # 找Top5相似向量
print("相似向量的索引：", I)
print("相似距离：", D)