MinHash簡介,MinHash原理,Jaccard index,MinHash,
MinHash簡介
傳統的hash算法只負責將原始內容儘量均勻隨機地映射為一個簽名值，原理上相當於偽隨機數產生算法。傳統hash算法產生的兩個簽名，如果相等，說明原始內容在一定機率下是相等的；如果不相等，除了說明原始內容不相等外，不再提供任何信息，因為即使原始內容只相差一個位元組，所產生的簽名也很可能差別極大。從這個意義上來說，要設計一個hash算法，對相似的內容產生的簽名也相近，是更為艱難的任務，因為它的簽名值除了提供原始內容是否相等的信息外，還能額外提供不相等的原始內容的差異程度的信息。
MinHash也是LSH的一種，可以用來快速估算兩個集合的相似度。MinHash由Andrei Broder提出，最初用於在搜尋引擎中檢測重複網頁。它也可以套用於大規模聚類問題。
MinHash原理
Jaccard index
Jaccard index是用來計算相似性，也就是距離的一種度量標準。假如有集合A、B，那么
J(A,B)=（A intersection B）/ （A union B)
也就是說，集合A,B的Jaccard係數等於A,B中共同擁有的元素數與A,B總共擁有的元素數的比例。很顯然，Jaccard係數值區間為[0,1]。
MinHash
先定義幾個符號術語：
h(x): 把x映射成一個整數的哈希函式。
hmin(S)：集合S中的元素經過h(x)哈希後，具有最小哈希值的元素。
那么對集合A、B，hmin(A) = hmin(B)成立的條件是A ∪ B 中具有最小哈希值的元素也在 A ∩ B中。這裡
有一個假設，h(x)是一個良好的哈希函式，它具有很好的均勻性，能夠把不同元素映射成不同的整數。
所以有，Pr[hmin(A) = hmin(B)] = J(A,B)，即集合A和B的相似度為集合A、B經過hash後最小哈希值相
等的機率。
有了上面的結論，我們便可以根據MinHash來計算兩個集合的相似度了。一般有兩種方法：
第一種：使用多個hash函式
為了計算集合A、B具有最小哈希值的機率，我們可以選擇一定數量的hash函式，比如K個。然後用這K個hash函式分別對集合A、B求哈希值，對
每個集合都得到K個最小值。比如Min(A)k={a1,a2,...,ak}，Min(B)k={b1,b2,...,bk}。
那么，集合A、B的相似度為|Min(A)k ∩ Min(B)k| / |Min(A)k ∪ Min(B)k|，即Min(A)k和Min(B)k中相同元素個數與總的元素個數的比例。
第二種：使用單個hash函式
第一種方法有一個很明顯的缺陷，那就是計算複雜度高。使用單個hash函式是怎么解決這個問題的呢？請看：
前面我們定義過 hmin(S)為集合S中具有最小哈希值的一個元素，那么我們也可以定義hmink(S)為集合S中具有最小哈希值的K個元素。這樣一來，
我們就只需要對每個集合求一次哈希，然後取最小的K個元素。計算兩個集合A、B的相似度，就是集合A中最小的K個元素與集合B中最小的K個元素
的交集個數與並集個數的比例。
