最小哈希

在電腦科學領域，**最小雜湊**（或**最小雜湊式獨立排列**局部性敏感雜湊）方法是一種快速判斷兩個集合是否相似的技術。這種方法是由 Andrei Broder （1997）, 發明的，最初在 AltaVista 搜尋引擎中用於在搜尋結果中檢測並消除重複 Web 頁面。

它同樣也應用於大規模聚類問題，比如通過文件間包含的詞語相似性進行聚類。

## 雅可比相似度與最小雜湊值

雅可比相似度係數通常用來表示兩個集合的相似度，定義 _U_ 是一個集合，_A_ 和 _B_ 是 _U_ 的子集。雅可比相似度定義如下：

　
: $J(A,B)={{|A\cap B|} \over {|A\cup B|}}.$

它是一個 0 到 1 之間的數值上，當其為 0 時表示兩個集合不相交，當其為 1 時表示兩個集合相等，其他的情況則在 0 和 1 之間。它廣泛地用於兩集合間相似性的判斷：當雅可比係數趨向於 1 時，兩個集合更相似；反之，當雅可比係數趨向於 0 時，兩個集合更不相似。

定義 _h_ 是一個將 _U_ 中的元素對映到一些不相交整數的雜湊函數，_perm_ 是集合 _U_ 中元素的排列排列，對於任意集合 _S_，定義 _h_min(_S_) 為 S 集合中具有最小 h (x) 函數值的元素 x，對應 _h_ ∘ _perm_（集合 _S_ 的元素 _x_ 是 _h_(_perm_(_x_)) 的最小值）。將 _h_min 應用於 集合 _A_ 和 _B_，假定沒有發生雜湊碰撞。有 _h_min(_A_) = _h_min(_B_)，若且唯若最小雜湊值的聯集 _A_ ∪ _B_ 依賴於交集 _A_ ∩ _B_ 時。
因此，

　
: Pr[_h_min(_A_) = _h_min(_B_)] = _J_(_A_,_B_).

也就是說，_h_min(_A_) = _h_min(_B_) 是真的機率等於 _J_(_A_,_B_) 另一方面來說，如果 _r_ 是一個當 _h_min(_A_) = _h_min(_B_) 時值為 1，其它情況下值為 0 的隨機變數，那麼 _r_ 可認為是 _J_(_A_,_B_) 的不偏估計。儘管 _r_ 的變異數很高時，不能很好的估計雅可比相似度，因為 $r$ 總是 0 或 1。最小雜湊思想通過以相同方式構造的幾個變數，將其平均在一起來減少這種變異數

## 演算法

### 多雜湊函數的變種

最簡單的最小雜湊方法是使用 _k_ 個不同的雜湊函數，其中 _k_ 是固定的整數參數，使用這 _k_ 個函數所對應的 _k_ 個 _h_min(_S_) 值來描述每個集合 _S_。
使用這種最簡單的版本來判斷 _J_(_A_,_B_)，假定 y 是使得 _h_min(_A_) = _h_min(_B_) 的雜湊函數個數，使用 _y_/_k_ 作為估計。則此估計是 _k_ 個不同的 0-1 隨機變數的平均值，其中每個隨機變數當 _h_min(_A_) = _h_min(_B_) 值為 1，反之為 0，並且是 _J_(_A_,_B_) 的不偏估計。因此，該平均值同樣也是一個不偏估計，而且通過 0-1 隨機變數之和的標準 Chernoff 上界可得知，其期望誤差是 O(1/√_k_)。所以，針對任意給定的常數 ε > 0，存在另一常數 _k_ = O(1/ε2)，其估計的期望誤差不超過 ε。例如，使用 400 個雜湊函數值來估計 _J_(_A_,_B_)，其期望誤差將小於或等於.05。

### 單一雜湊函數的變種

計算多個雜湊函數的代價是相當昂貴的，因此有關最小雜湊方法的另一種實現方法是僅使用單一的雜湊函數來避免這個問題。對於每個集合，使用這個單一的雜湊函數選出其中的多個值，而不是每個雜湊函數選擇一個值。假定 _h_ 是一個雜湊函數，_k_ 是一個固定整數。如果 _S_ 是 _h_ 域上 _k_ 或更多元素的集合，則定義 _h_(_k_)(_S_) 為 _S_ 中具有最小 _h_ 值的 _k_ 個元素所組成的子集。該子集 _h_(_k_)(_S_) 可用作集合 _S_ 的一個_簽章_，任意兩個集合間的相似度可通過比較它們的簽章來計算。

特別地，假定 _A_ and _B_ 為任意兩個集合，_X_ = _h_(_k_)(_h_(_k_)(_A_) ∪ _h_(_k_)(_B_)) = _h_(_k_)(_A_ ∪ _B_) 是 _A_ ∪ _B_ 的 _k_ 個元素的集合，如果 _h_ 是隨機變數並且 _k_ 個元素的任意子集等可能地被選擇。也就是說，_X_ 是 _A_ ∪ _B_ 的簡單隨機樣本。_Y_ = _X_ ∩ _h_(_k_)(_A_) ∩ _h_(_k_)(_B_) 是集合 _X_ 中屬於 _A_ ∩ _B_ 交集的元素。因此，|_Y_|/_k_ 是 _J_(_A_,_B_) 的不偏估計。單一雜湊函數的估計與多個雜湊函數產生的估計的不同在於 _X_ 總是有 _k_ 個元素，而多個雜湊函數由於兩個不同的雜湊函數可能會產生相同的最小值，因此可能會產生更少的樣本元素。然而，當 _k_ 相對集合大小來說很小時，該區別可忽略不計。

通過不重複取樣的標準 Chernoff 上界，該估計的期望誤差為 O(1/√_k_)，其效能與多個雜湊函數方法相匹配。

### 耗時分析

|_Y_|/_k_ 估計通過給定集合的兩個簽章能夠在 O(_k_) 能夠計算出來，因此，當 ε and _k_ 為常數時，從簽章中計算相似度估計的時間也為常數，這樣當眾多兩兩相似度需要計算時，該方法在執行時間上與每個集合中元素的完全比較相比，能夠有實質性的最佳化。

## 最小雜湊式獨立排列

為了實現上述的最小雜湊方法，雜湊函數 _h_ 需要定義 _n_ 元素上的一個隨機排列，這裡的 _n_ 是指待比較的所有集合併集中不相交元素的總數。
但是由於存在 _n_!個不同的排列，僅僅指定一個真正隨機的排列就需要 Ω(_n_ log _n_) 位，即使 _n_ 一般時，這個數值也很大。基於這樣的事實，與全域雜湊相類似的理論，有大量的研究工作尋找「最小雜湊式獨立的」一簇排列，意指標對域的任意子集，任何元素都與其最小值是等可能的。已經證明，最小雜湊式獨立的排列簇至少必須包含: $lcm(1,2,...,n)\geq e^{n-o(n)}$ 個不同的排列，因此它需要 Ω(_n_) 位來指定一個排列，這個數值仍然很大。

由於實踐上不可行，引入了最小雜湊式獨立的兩個變型概念：嚴格最小雜湊式獨立排列簇和近似最小雜湊式獨立排列簇。
嚴格的最小雜湊式獨立是指最小雜湊式獨立屬性被限制在集合基數至多為 _k_ 的一些集合中。
近似最小雜湊式獨立最多有一個固定的機率 ε 變化為完全獨立。

## 應用

最小雜湊的最初應用包括在 Web 文件中聚類並消除近似重複，這通過在那些文件中出現的詞語集合來描述。 相似的技術也應用於其他類型資料的聚類和近似重複消除，如圖片：在圖片資料中，一張圖片可以通過分割用很多更小的子圖片集合或更多複雜圖片特徵的描述集合來表示。

Schleimer，Wilkerson & Aiken (2003) 使用最小雜湊技術作為數字文件剽竊檢測方法的一部分，他們的方法將文件表示成給定長度的子串集合，將文件劃分成更大固定長度的窗口，然後使用子串的最小雜湊值作為每個窗口的描述值。如果文字的拷貝部分比兩倍窗口尺寸還要長，則該描述值將肯定匹配儲存在資料庫中眾多描述值中的一個，這樣那個窗口就可以用來檢查有多少內容是拷貝的。

在資料探勘領域，Cohen 等人 (2001) 使用最小雜湊技術作為關聯規則學習的工具。給定一個資料庫，其中每一項都有多個屬性（可看作是每行為一個資料庫項， 每列為一個屬性的 0-1 矩陣），他們將最小雜湊的近似度方法應用於 Jaccard 係數，用來辨別頻繁共同出現的屬性候選對，然後僅計算這些候選對的確切係數值，以確定哪些專案共同出現的頻度低於一個給定的嚴格閾值。

## 相關主題

最小雜湊方法可看作是局部性敏感雜湊的一個實例。局部性敏感雜湊是使用雜湊將大集合的資料物件對映到更小的雜湊值的技術集合，通過這樣的方法當兩個物件距離相近時，它們的雜湊值也可以相同。在最小雜湊方法實例中，一個集合的簽章可看作是它的雜湊值。其它局部性敏感雜湊技術還有針對集合間的海明距離，以及向量間的餘弦距離等。另外，局部性敏感雜湊還在最近鄰搜尋演算法有著重要的應用。

 

## 參考文獻