局部敏感哈希：物以類聚

演算法背後的故事：藝術家的調色板

想像妳是一位擁有 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 教會我們：有時候，細節並不重要。透過模糊身份的界限，我們獲得了在複雜世界中尋找關聯的能力。她提醒我們，在數位時代，「相似」往往比「相等」更有價值。