lsh
LSH的含义
LSH 是 局部敏感哈希 的缩写，英文全称为 Locality-Sensitive Hashing。
它是一种用于高维数据近似最近邻搜索的高效算法技术。其核心思想是：将原始数据空间中相似（距离近）的数据点，以较高的概率映射到相同的哈希桶中；而不相似（距离远）的数据点，则大概率被映射到不同的哈希桶中。 这与传统密码学哈希函数（如MD5、SHA）的目标截然相反。
核心思想与工作原理
LSH不是某一个特定的哈希函数，而是一族满足“局部敏感”性质的哈希函数的框架。其工作原理可以概括为：
- 哈希函数族选择： 根据具体的距离度量标准（如欧氏距离、余弦相似度、杰卡德相似度等），选择或设计一个合适的LSH函数族。这个函数族中的每个函数都能将数据点映射到一个哈希值（或哈希桶编号）。
- 放大差异： 单个LSH函数的区分能力可能有限。通常采用两种技术来增强效果：
- 放大（Amplification）： 使用多个独立的LSH函数，只有当一个数据点通过了所有（或足够多）的哈希函数检查，才被认为候选匹配。
- 多表（Multiple Tables）： 独立构建多个哈希表，每个表使用一组不同的LSH函数。查询时，综合所有哈希表的结果，以提高召回率。
- 索引与查询：
- 索引阶段： 将所有数据点通过LSH函数映射到相应的哈希桶中，构建哈希表。
- 查询阶段： 对于一个新的查询点，用同样的LSH函数计算其哈希值，然后只与落入相同哈希桶内的数据点进行精确距离计算和比较。这避免了与整个数据集进行暴力计算，极大提升了搜索效率。
关键特性
- 近似性： LSH是一种近似算法，它可能无法找到绝对的最近邻，但能以很高的概率找到近似最近邻。它需要在精度（准确率）和召回率之间进行权衡。
- 效率： 通过将搜索范围限制在少数几个哈希桶内，大大减少了需要计算的距离比较次数，尤其适用于海量高维数据。
- 与距离度量绑定： 不同的距离度量需要设计不同的LSH函数族。例如：
- 汉明距离： 常用比特采样（Bit Sampling）。
- 欧氏距离： 常用
p-stable分布（如随机投影法）。 - 余弦相似度： 可通过随机超平面法（Sign Random Projection）转化为汉明距离处理。
- 杰卡德相似度： 常用最小哈希（MinHash）。
应用场景
LSH技术广泛应用于需要快速进行相似性搜索的领域：
- 图像与视频检索： 根据特征向量查找相似图片或视频片段。
- 文档去重与相似性检测： 如网页查重、论文抄袭检测。
- 推荐系统： 快速查找相似用户或物品。
- 生物信息学： 基因序列比对。
- 音频指纹识别： 如Shazam等音乐识别软件。
- 数据库： 高维数据的近似查询。
简单示例：最小哈希（MinHash）
以用于集合相似度（杰卡德相似度）的MinHash为例：
- 假设有两个集合A和B。
- 我们设计一个哈希函数，它对全集中的所有元素进行随机排列。
- 对一个集合，MinHash值定义为：在随机排列后，集合中第一个出现的元素的哈希值。
- 数学上可以证明：两个集合的MinHash值相等的概率，等于这两个集合的杰卡德相似度。
- 因此，通过使用多个独立的随机排列（即多个MinHash函数），我们可以通过统计MinHash值相等的次数来估计集合的相似度，而无需直接计算庞大的交集和并集。
总结： LSH是一种通过“哈希”将相似数据聚拢的索引技术，它用一定的精度损失换取搜索速度的数量级提升，是处理大规模高维相似性搜索问题的利器。