局部敏感哈希（LSH）介绍

标准哈希表擅长均匀分布项目以避免冲突，但在机器学习 (machine learning)中，我们有时希望相反：我们希望相似的项目发生冲突，或落入同一个哈希桶中。这是局部敏感哈希（LSH）背后的主要思想，它是一种有力技术，用于处理高维空间 (high-dimensional space)中高效查找最近邻居的问题。

难题：高维空间 (high-dimensional space)中的最近邻居

在许多机器学习 (machine learning)任务中，比如推荐系统（查找相似用户/项目）、分类（k-NN算法）、聚类和近似重复项检测，找到给定查询点的最近邻居是一项基本操作。

"朴素的方法涉及计算查询点与数据集中每个点的距离。虽然对于小型数据集或低维度数据可行，但随着数据集大小（$n$）或维度数量（$d$）的增长，这种暴力方法在计算上变得难以承受。其复杂度通常为 $O(n \cdot d)$，对于处理数百万个数据点或数千个特征的实际场景来说，这通常太慢了。这种困难常被称为“维度灾难”。"

LSH方法：用于相似性的哈希

LSH 提供一种比线性扫描快得多地查找近似最近邻居的方法。它不保证找到精确的最近邻居，而是以高概率找到确实接近查询点的点。

其核心原理依赖于具有“局部敏感”特性的特殊哈希函数：

• 相似点： 在原始特征空间中相互接近的点，被哈希到同一桶的概率很高。
• 不相似点： 相互之间距离较远的点，被哈希到不同桶的概率很高。

这与加密哈希函数有根本区别，加密哈希函数旨在确保输入中即使是微小的改变也会导致输出哈希值截然不同。LSH 函数旨在保留邻近结构，尽管是概率性的。

LSH 系列

LSH 不是单一算法，而是一系列哈希技术。特定LSH系列的选择取决于用于衡量相似度的距离度量标准：

• Jaccard 距离： 通常用于比较集合（例如，文档中的词集，用户交互过的项目集）。MinHash 是适用于此度量的一种流行LSH系列。
• 余弦距离： 通常用于衡量向量 (vector)之间的方向相似性，与它们的大小无关（例如，文本文档嵌入 (embedding)、用户偏好向量）。基于随机投影的方法（如SimHash）适用于此。
• 欧几里得距离（$L_2$）： 测量空间中点之间的直线距离。可以使用基于p-稳定分布的LSH系列（将数据投影到随机线上并分区）。
• 汉明距离： 测量对应符号不同位置的数量（例如，比较二进制代码或哈希值）。简单的方案，如随机选择比特，即可奏效。

LSH 如何工作：多重哈希表

仅使用一个LSH哈希函数查找邻居并不十分可靠。为了提高找到真实邻居的概率，并平衡查找邻居和最小化比较之间的关系，LSH通常采用多个哈希表。

以下是该过程的简化概览：

1. 选择LSH系列： 根据您选择的距离度量（例如，Jaccard距离用MinHash，余弦距离用随机投影）选择合适的LSH系列。
2. 构建哈希表： 创建 $L$ 个哈希表。对于每个表 $i$（从 $1$ 到 $L$），创建一个复合哈希函数 $g_i(p) = (h_{i,1}(p), h_{i,2}(p), ..., h_{i,k}(p))$。这个函数 $g_i$ 连接从所选LSH系列中随机选择的 $k$ 个哈希函数（$h_{i,j}$）的结果。映射到相同序列 $(h_{i,1}(p), ..., h_{i,k}(p))$ 的点会落入表 $i$ 内的同一个桶中。
3. 预处理： 对于数据集中的每个点 $p$，计算其在 $L$ 个哈希表中的哈希值 $g_i(p)$，并将该点（或其标识符）存储在每个表中的相应桶内。
4. 查询： 当一个查询点 $q$ 到达时：
   • 计算其在 $L$ 个哈希表中的哈希值 $g_i(q)$。
   • 从所有 $L$ 个表中检索存储在桶 $g_1(q), g_2(q), ..., g_L(q)$ 中的所有点。这构成了候选邻居集。
5. 精炼： 由于LSH是概率性的，候选集可能包含并非真正接近的点（假阳性）并可能遗漏一些真实邻居（假阴性）。计算查询点 $q$ 与上一步检索到的所有候选点之间的精确距离。
6. 结果： 从候选集中返回与 $q$ 具有最小精确距离的点作为近似最近邻居。

此图描绘了LSH的两个阶段：将数据集预处理到多个哈希表中，以及通过哈希查询点并从匹配桶中检索候选点以进行精炼的查询过程。

性能与权衡

LSH 的有效性取决于参数 (parameter) $k$（每个表的哈希函数数量）和 $L$（哈希表的数量）：

• 增加 $k$ 会使复合哈希 $g_i$ 更具选择性。这会减少不相似点最终落入同一桶中的可能性（减少假阳性），但也会增加遗漏真实邻居的可能性（增加假阴性）。
• 增加 $L$ 会提高真实邻居对至少在一个表中发生冲突的概率，从而减少假阴性。然而，这也会增加检索到的候选点数量以及整体查询时间和内存使用量。

调整 $k$ 和 $L$ 允许您在准确性（召回率）和查询速度之间进行权衡。目的是检索一个相对较小的候选集，其中包含大部分真实的最近邻居，从而使最终的精炼步骤比与整个数据集进行比较快得多。

优点：

• 速度： 相比暴力搜索，查找近似最近邻居的查询时间显著更快，特别是在高维空间 (high-dimensional space)中。通常可以实现亚线性查询时间。
• 可扩展性： 相比精确方法，对大型数据集的适应性更强。

缺点：

• 近似性： 不保证找到精确的最近邻居。提供概率性保证。
• 参数调整： 性能受LSH系列选择以及参数 $k$ 和 $L$ 的影响。需要根据数据集和应用需求仔细选择和调整。
• 内存： 可能需要大量内存来存储多个哈希表，尤其是当 $L$ 较大时。

机器学习 (machine learning)中的应用

LSH 在涉及大规模相似性搜索的场景中特别有价值：

• 近似重复项检测： 查找相似的文档、图像或网页。
• 推荐系统： 识别品味相似的用户或用户喜欢的相似项目。
• 聚类： 可用作预处理步骤，快速查找基于密度的聚类算法的候选邻居。
• 生物信息学： 查找相似的DNA或蛋白质序列。
• 计算机视觉： 基于特征描述符查找相似图像。

通过理解LSH的原理，您就获得了一个有力工具，可以高效处理机器学习流程中常见的大型和高维数据集上的相似性搜索任务，这补充了前面讨论的标准哈希表的精确匹配能力。