基于局部敏感哈希的近似最近邻搜索算法
字数 2249 2025-12-23 00:43:56

基于局部敏感哈希的近似最近邻搜索算法

题目描述

局部敏感哈希（Locality-Sensitive Hashing, LSH）是一种用于高维空间近似最近邻搜索的随机算法。它的核心思想是：将空间中相邻的点以较大概率映射到同一个哈希桶中，不相邻的点映射到不同桶中。通过构建多个哈希表，可以在亚线性时间内完成近似最近邻查询，适用于大规模高维数据（如图像特征、文本向量）的快速检索。

解题过程

1. 问题定义

设我们有一个高维数据集 \(X \subseteq \mathbb{R}^d\)，距离度量通常为欧氏距离或余弦相似度。给定查询点 \(q\)，最近邻搜索需要找到：

\[x^* = \arg\min_{x \in X} \|x - q\| \]

当 \(d\) 很大时，精确搜索的计算成本过高。LSH 的目标是快速找到一个近似最近邻 \(x'\)，满足：

\[\|x' - q\| \le (1 + \epsilon) \|x^* - q\| \]

其中 \(\epsilon > 0\) 是允许的近似误差。

2. LSH 的核心思想

LSH 并不直接比较所有点，而是通过哈希函数将数据点“分桶”，使得：

  • 相似的点（距离小）有高概率被哈希到同一个桶；
  • 不相似的点（距离大）有低概率被哈希到同一个桶。

这样只需在查询点所在的桶内搜索，从而大幅减少比较次数。

3. 构造 LSH 函数族

以欧氏距离为例，常用 p-stable LSH（基于稳定分布）。

步骤 1：随机投影

随机生成一个 \(d\) 维向量 \(a\)，其每个分量独立采样自标准正态分布 \(N(0,1)\)。

步骤 2：量化分桶

定义哈希函数：

\[h_{a,b}(x) = \left\lfloor \frac{a \cdot x + b}{w} \right\rfloor \]

其中：

  • \(a\) 是随机投影向量；
  • \(b\) 是从区间 \([0, w]\) 均匀采样的偏移量；
  • \(w\) 是桶宽（超参数）。

解释：

  • 点积 \(a \cdot x\) 将高维点投影到一维直线；
  • 加 \(b\) 并除以 \(w\) 后取整，相当于将直线划分为宽度为 \(w\) 的区间（桶）；
  • 若两个点 \(x, y\) 的投影值相近，则它们有很大概率落入同一个桶。

4. 放大概率差距

单个哈希函数对“相似”与“不相似”的区分能力有限。为了加大概率差距，采用两种技术：

4.1 构建复合哈希函数（AND 结构）

定义 \(g(x) = (h_1(x), h_2(x), \dots, h_k(x))\)，其中每个 \(h_i\) 独立采样。

  • 两个点 \(x, y\) 只有在 所有 \(k\) 个哈希函数上都碰撞（即 \(g(x) = g(y)\)），才被认为在同一桶。
  • 这降低了碰撞概率，尤其能减少不相似点的误碰撞。

4.2 构建多个哈希表（OR 结构）

构建 \(L\) 个独立的复合哈希函数 \(g_1, g_2, \dots, g_L\)，对应 \(L\) 个哈希表。

  • 查询时，检查查询点 \(q\) 在 每个哈希表 中对应的桶，合并所有候选点。
  • 增加 \(L\) 可提高召回率（找到真实最近邻的概率）。

5. 完整 LSH 索引构建流程

  1. 选择参数：
    • 哈希函数数量 \(k\)；
    • 哈希表数量 \(L\)；
    • 桶宽 \(w\)。
  2. 对每个 \(\ell = 1, \dots, L\)：
    • 随机生成 \(k\) 个独立哈希函数 \(h_{\ell,1}, \dots, h_{\ell,k}\)；
    • 定义复合哈希函数 \(g_\ell = (h_{\ell,1}, \dots, h_{\ell,k})\)；
    • 用 \(g_\ell\) 对数据集 \(X\) 中所有点哈希，将点放入对应桶（哈希表 \(T_\ell\) 中）。
  3. 存储所有哈希表 \(\{T_1, \dots, T_L\}\) 作为索引。

6. 查询流程

给定查询点 \(q\)：

  1. 对每个哈希表 \(T_\ell\)：
    • 计算 \(g_\ell(q)\)；
    • 取出 \(T_\ell\) 中对应桶内的所有点，加入候选集 \(C\)。
  2. 在候选集 \(C\) 中计算 \(q\) 与每个点的实际距离，返回最近点。

7. 参数选择与理论保证

  • 若两点距离为 \(r\)，则单个哈希函数的碰撞概率为 \(p(r)\)（可推导出与 \(r/w\) 相关）。
  • 通过 AND-OR 结构，最终“相似点被检索到”的概率约为 \(1 - (1 - p_1^k)^L\)（其中 \(p_1\) 是相似点的碰撞概率）。
  • 调整 \(k\) 和 \(L\) 可在召回率与计算量间权衡：
    • 增大 \(k\)：每个桶内点更少，但可能漏掉真实近邻；
    • 增大 \(L\)：搜索更多桶，召回率提高，但内存和查询时间增加。

总结

LSH 通过随机投影+量化分桶实现快速候选集筛选，再通过多表多哈希函数平衡准确率与效率。该方法尤其适合高维、海量数据的近似最近邻搜索，广泛应用于推荐系统、图像检索、相似文本检测等场景。

基于局部敏感哈希的近似最近邻搜索算法 题目描述 局部敏感哈希（Locality-Sensitive Hashing, LSH）是一种用于 高维空间近似最近邻搜索 的随机算法。它的核心思想是：将空间中相邻的点以较大概率映射到同一个哈希桶中，不相邻的点映射到不同桶中。通过构建多个哈希表，可以在亚线性时间内完成近似最近邻查询，适用于大规模高维数据（如图像特征、文本向量）的快速检索。 解题过程 1. 问题定义 设我们有一个高维数据集 \( X \subseteq \mathbb{R}^d \)，距离度量通常为欧氏距离或余弦相似度。给定查询点 \( q \)，最近邻搜索需要找到： \[ x^* = \arg\min_ {x \in X} \|x - q\| \] 当 \( d \) 很大时，精确搜索的计算成本过高。LSH 的目标是快速找到一个近似最近邻 \( x' \)，满足： \[ \|x' - q\| \le (1 + \epsilon) \|x^* - q\| \] 其中 \( \epsilon > 0 \) 是允许的近似误差。 2. LSH 的核心思想 LSH 并不直接比较所有点，而是通过 哈希函数 将数据点“分桶”，使得： 相似的点（距离小）有 高概率 被哈希到同一个桶； 不相似的点（距离大）有 低概率 被哈希到同一个桶。 这样只需在查询点所在的桶内搜索，从而大幅减少比较次数。 3. 构造 LSH 函数族 以欧氏距离为例，常用 p-stable LSH （基于稳定分布）。 步骤 1：随机投影 随机生成一个 \( d \) 维向量 \( a \)，其每个分量独立采样自标准正态分布 \( N(0,1) \)。 步骤 2：量化分桶 定义哈希函数： \[ h_ {a,b}(x) = \left\lfloor \frac{a \cdot x + b}{w} \right\rfloor \] 其中： \( a \) 是随机投影向量； \( b \) 是从区间 \([ 0, w ]\) 均匀采样的偏移量； \( w \) 是桶宽（超参数）。 解释 ： 点积 \( a \cdot x \) 将高维点投影到一维直线； 加 \( b \) 并除以 \( w \) 后取整，相当于将直线划分为宽度为 \( w \) 的区间（桶）； 若两个点 \( x, y \) 的投影值相近，则它们有很大概率落入同一个桶。 4. 放大概率差距 单个哈希函数对“相似”与“不相似”的区分能力有限。为了加大概率差距，采用两种技术： 4.1 构建复合哈希函数（AND 结构） 定义 \( g(x) = (h_ 1(x), h_ 2(x), \dots, h_ k(x)) \)，其中每个 \( h_ i \) 独立采样。 两个点 \( x, y \) 只有在 所有 \( k \) 个哈希函数上都碰撞（即 \( g(x) = g(y) \)），才被认为在同一桶。 这降低了碰撞概率，尤其能减少不相似点的误碰撞。 4.2 构建多个哈希表（OR 结构） 构建 \( L \) 个独立的复合哈希函数 \( g_ 1, g_ 2, \dots, g_ L \)，对应 \( L \) 个哈希表。 查询时，检查查询点 \( q \) 在 每个哈希表 中对应的桶，合并所有候选点。 增加 \( L \) 可提高召回率（找到真实最近邻的概率）。 5. 完整 LSH 索引构建流程 选择参数： 哈希函数数量 \( k \)； 哈希表数量 \( L \)； 桶宽 \( w \)。 对每个 \( \ell = 1, \dots, L \)： 随机生成 \( k \) 个独立哈希函数 \( h_ {\ell,1}, \dots, h_ {\ell,k} \)； 定义复合哈希函数 \( g_ \ell = (h_ {\ell,1}, \dots, h_ {\ell,k}) \)； 用 \( g_ \ell \) 对数据集 \( X \) 中所有点哈希，将点放入对应桶（哈希表 \( T_ \ell \) 中）。 存储所有哈希表 \( \{T_ 1, \dots, T_ L\} \) 作为索引。 6. 查询流程 给定查询点 \( q \)： 对每个哈希表 \( T_ \ell \)： 计算 \( g_ \ell(q) \)； 取出 \( T_ \ell \) 中对应桶内的所有点，加入候选集 \( C \)。 在候选集 \( C \) 中计算 \( q \) 与每个点的实际距离，返回最近点。 7. 参数选择与理论保证 若两点距离为 \( r \)，则单个哈希函数的碰撞概率为 \( p(r) \)（可推导出与 \( r/w \) 相关）。 通过 AND-OR 结构，最终“相似点被检索到”的概率约为 \( 1 - (1 - p_ 1^k)^L \)（其中 \( p_ 1 \) 是相似点的碰撞概率）。 调整 \( k \) 和 \( L \) 可在召回率与计算量间权衡： 增大 \( k \)：每个桶内点更少，但可能漏掉真实近邻； 增大 \( L \)：搜索更多桶，召回率提高，但内存和查询时间增加。 总结 LSH 通过 随机投影+量化分桶 实现快速候选集筛选，再通过 多表多哈希函数 平衡准确率与效率。该方法尤其适合 高维、海量 数据的近似最近邻搜索，广泛应用于推荐系统、图像检索、相似文本检测等场景。