局部敏感哈希：物以类聚

算法背后的故事：艺术家的调色板

想象你是一位拥有 100 万幅画作的艺术家。有人带了一张新素描来问你：“你的画作中，哪一幅与这张最相似？”

如果用传统的哈希表，你会给素描算一个哈希值。但如果素描多画了一笔，哈希值就会翻天覆地。你将一无所获。

1998 年，Indyk 和 Motwani 故意设计了一种“坏掉”的哈希函数。他们不追求最大化差异，反而追求最大化碰撞。他们设想将画作投影到一堵低维的墙上。如果两幅画从 10 个不同的角度看都很相似，那它们极有可能是同一幅画。

这就是 局部敏感哈希 (LSH)。它是一门将“足够接近”的项聚类在一起的艺术，而无需进行不可能完成的全量比对 ($O(N^2)$)。

为什么需要它？

LSH 是相似性搜索的核心引擎。

• 推荐系统： “找到与 Luke 电影口味相似的用户。”
• 版权检测： “这段视频是否是某部版权电影的微调或剪辑版本？”
• 查重系统： “这篇论文是否与已有文章有 90% 的相似度？”
• 图片搜索： 寻找“视觉上相似”的照片。

算法是如何“思考”的

这个算法是一个富有创造力的分类者。

1. 向量化： 它将数据（文本、图片）转化为一串数字（向量）。
2. 投影 (影子)： 它将这些向量投影到随机的超平面上。想象成从特定的角度给数据拍一张“快照”。
3. 指纹： 它将投影的结果记录为一个简短的签名。
4. 分桶： 拥有相同签名的项被丢进同一个“桶”里。
5. 搜索： 当你想找相似项时，你只需要看同一个桶里的东西。你直接无视了剩下数以亿计的其他数据。

工程决策：精度与召回率的权衡

• 速度： 搜索一个只有 1000 項的桶，比搜索一个 10 亿項的数据库快得多。
• 准确性： 你可能会漏掉一些相似项（召回率问题），或者找回一些不那么像的东西（精度问题）。
• 优化： 工程师通常使用多组 LSH。如果两项在任何一组中匹配，就认为它们是候选相似项。这就是 Google 和 Amazon 常用到的 MinHash + LSH 组合。

实现参考 (Python 素描版)

import numpy as np

class SimpleLSH:
    def __init__(self, input_dim, num_projections=10):
        # 创建随机超平面 (即我们觀察的角度)
        self.projections = np.random.randn(num_projections, input_dim)
        self.buckets = {}

    def _get_hash(self, vector):
        # 投影向量并获取二进制签名 (在平面上方或下方)
        sig = (np.dot(self.projections, vector) > 0).astype(int)
        return "".join(sig.astype(str))

    def add(self, label, vector):
        h = self._get_hash(vector)
        if h not in self.buckets:
            self.buckets[h] = []
        self.buckets[h].append(label)

    def query(self, vector):
        h = self._get_hash(vector)
        return self.buckets.get(h, [])

# 使用示例
lsh = SimpleLSH(input_dim=128, num_projections=8)
vec_luke = np.random.randn(128)
vec_similar = vec_luke + 0.1 * np.random.randn(128) # 微小差异

lsh.add("Luke", vec_luke)
print(f"搜索结果: {lsh.query(vec_similar)}") # 极大概率返回 ['Luke']

小结

LSH 教会我们：有时候，细节并不重要。通过模糊身份的界限，我们获得了在复杂世界中寻找关联的能力。它提醒我们，在数字时代，“相似”往往比“相等”更有价值。