大規模數據的相似度計算方法 Min Hashing 和 LSH

在數據挖掘任務中都涉及了海量數據的相似度計算，例如檢索文檔的相似度，用戶之間的相似度等。這些數據通常維度很高，用 one-hot 編碼的文檔數據維度等於字典的大小，在數據量大，數據維度高的情況下，計算對象兩兩之間的相似度需要耗費大量的時間。本文介紹兩種近似算法 Min Hashing (最小哈希) 和 Locality Sensitive Hashing (LSH，局部敏感哈希)，近似算法可以在犧牲部分精度下大大提升運行效率。

1.Min Hashing

假設給定兩個文檔 D1 和 D2，其特徵向量採用 one-hot 編碼，即如果一個位置為 1 則說明文檔擁有對應的單詞。

文檔向量

我們可以用 Jaccard 係數計算兩個向量的相似度，公式如下，A 和 B 是兩個集合：

Jaccard 係數

Jaccard 係數是 A、B 交集的元素數量除以 A、B 併集的元素數量，因此上面的文檔 D1、D2 相似度為 2/5。用 x 表示 A、B 共有的元素數量，y 表示 A、B 單獨擁有的元素數量，則 Jaccard 係數可以改寫為下面的公式：

Jaccard 係數

Min Hashing 是一種近似計算 Jaccard 係數的方法，主要的步驟如下：

對向量D1、D2 的維度進行 m 次隨機排列找到重新排列後 D1、D2 第一個非 0 行的索引，用函數 h(D1)、h(D2) 表示執行 m 次隨機排列後，可以得到 D1、D2 的新特徵向量，如下：

Min Hashing 後的特徵向量

這一過程如下圖所示，下圖中 m=3：

Min Hashing 過程示例

得到新的特徵向量 Sig(D1) 和 Sig(D2) 後可以計算每一個位置上相同 (即第一個非 0 行索引相同) 的概率 P=1/3，這個概率就是 Jaccard 係數的近似值。這主要是根據下面的原理：

Min Hashing 原理

這個原理可以證明，重新排列後兩個向量 D1、D2 後，在每一個維度存在三種可能：

D1、D2 在這一個維度都是 1，對應了 Jaccard 公式中的 xD1、D2 只有一個向量在這一個維度是 1，對應了 Jaccard 公式中的 yD1、D2 在這一維度都是 0Min Hashing 得到的新向量 Sig(D1) 是 D1 第一個不為 0 的行索引。則 Sig(D1) 和 Sig(D2) 第一個非 0 行索引相同的概率為 x/(x+y) 即 Jaccard 係數公式。

如果採用全排列 (即考慮所有的排列情況) 則 Min Hashing 可以得到準確的 Jaccard 值，但是在實際使用時為了提升效率，通常採用 m 次排列，可以將原向量轉為長度為 m 的新向量。

2.LSH

Min Hashing 可以將原始的特徵向量轉為更低維度的 Sig 向量，減少計算兩個對象之間相似度的時間。但是如果對象的數量 N 很大，計算所有對象之間相似度需要執行的次數為 O(N^2)，仍然需要耗費大量時間。

LSH 算法 (Locality Sensitive Hashing，局部敏感哈希) 的核心思想是先把數據粗略地進行分桶，使相似度高的數據儘可能出現在同一個桶內。分到同一個桶的數據互相視為 candidate 數據，後續計算相似度時只計算數據和其 candidate 數據的相似度 (即出現在同一個桶內的)。

LSH 先將 Min Hashing 得到的 Sig 向量劃分為 b 段 (Bands)，每段的長度為 r。下面是將 Sig 向量分段的例子，其中每一列是一整個 Sig 向量，向量被劃分為 4 個 Band (b=4)，每個 Band 長度為 3 (r=3)。

Sig 向量分段

然後利用哈希函數將每一個 Band 中的向量 (r 維向量) 分配到不同的桶裡面，哈希函數的取值 (桶數量) 應該儘可能地多，使兩個向量只在完全相同時才會有大概率被分到同一個桶裡面。分桶的示意圖如下：

LSH 算法分桶的過程

在上面的分桶過程中，每一個 Band 都使用同一個哈希函數，但是採用不同的桶。Band 1 的桶在頂部，Band 4 的桶在底部。在 Band 1 中，第 1 個數據和第 9 個數據分到了同一個桶裡 (紅色)，因此數據 1 和數據 9 互為 candidate 數據，即兩個數據只要有一個 Band 被分到同一個桶，就是 candidate。

因為 LSH 分桶是近似的算法，因此會存在一些誤差。我們希望可以減少 LSH 的 False Positive (相似度低的數據分到同一個桶) 和 False Negative (相似度高的數據沒有分到同一個桶)。為了減少誤差，首先需要計算出兩個數據被分到同一個桶的概率。

假設有兩個數據，他們真實的 Jaccard 係數為 s，LSH 算法把他們的 Sig 向量劃分為 b 段，每段長度為 r。在介紹 Min Hashing 算法時，我們知道 Sig 向量保存的是重排列後第一個非 0 行的索引，因此兩個數據的 Sig 向量在某一維度上取值相同的概率為 Jaccard 係數，即 s。則我們可以計算出這兩個數據至少在一個 Band 裡被分到同一個桶裡面的概率：

分桶概率計算

上面公式的最後一行即為兩個數據至少在一個 Band 裡被分到同一個桶裡的概率 P，給定 b 和 r，可以畫出概率 P 隨 Jaccard 係數 s 變化的圖像，稱為 S-curve，如下圖所示。

S-curve

可以看到當 Jaccard 係數變得足夠大的時候，兩個數據被分到同一個桶的概率會大大增加 (接近 1)。因此一般使用的時候要事先設置好一個 Jaccard 係數的閾值 s，然後調整 b 和 r，使得相似度大於閾值 s 時，兩個數據被分到同一個桶的概率最大。

3.參考文獻

Mining of Massive Datasets