這篇文主要會簡介 Jaccard similarity 及 Minhash 的原理、證明及實作的技巧。

為了降低資料的維度，且仍能保留相似度(similarity)，我們希望能找到一個hash函數h符合以下兩種特徵:

1. 能將高維度的資料C，映射為較低維度的特徵h(C) (signature)
2. 維持 Sim(C1,C2) ≒ Sim(h(C1),h(C2))

C1 = 10110101
C2 = 10000001
h(C1) = 1011
h(C2) = 1101
Sim(C1,C2) = $\frac{4}{8}$
Sim(h(C1),h(C2)) = $\frac{2}{4}$

Jaccard similarity

在這邊首先要介紹一種相似度的一種度量方法 Jaccard similarity。這是一個常用於計算集合相似度的方法:

Jac(C1,C2) = $\frac{|C1∩C2|}{|C1∪C2|}$
C1 = {a,b,c}
C2 = {a,d}
Jac(C1,C2) = $\frac{1}{4}$

Minhash 原理

若以 Jaccard similarity 來計算相似度，Minhash 符合了上述的兩個條件，可以幫助我們降維且保留相似度。Minhash 的演算法如下:

1. 首先找出不同文件的 similarity matrix:

   element	C1	C2	類別
   a	1	1	X
   b	1	0	Y
   c	1	0	Y
   d	0	1	Y
   e	0	0	Z

   row 代表的是 element，column 代表的是集合(文件)。
   若值為1代表集合內包含該元素，0則是不包含。
   C1 = {a,b,c} , C2 = {a,d}

2. 隨機調換順序

   element	C1	C2	類別
   e	0	0	Z
   b	1	0	Y
   a	1	1	X
   c	1	0	Y
   d	0	1	Y

3. 以每個集合裡第一個 element 為特徵(signature)。
   h(C1)=b , h(C2)=a

4. 重複2、3步驟K次，則得到特徵為 K-bits 的向量。
   h(C1)=badd….ab , h(C2)=abdc….db 若元素有M個(M-dimension)，選取K<M，即可達到降維。

Minhash 證明

Minhash 的演算法看起來非常簡單，但卻能維持相似度
並有P(Minhash(C1) = Minhash(C2)) = Jac(C1,C2)的結論，
以下簡單的證明一下這個結論。

首先我們對 row 的組合分成3種類別:

1. X: 均為1，在兩個集合中皆包含此元素，如a。
2. Y: 其中一個為1，只有一個集合包含此元素，如b。
3. Z: 均為0，兩個集合都不包含此元素，如e。

由於 Minhash 是採每個集合裡第一個元素，所以 Minhash 的結果不會有Z類，我們可以將Z類排除。 因此 Minhash(C1) = Minhash(C2) 的情形就只會發生在:
當排序為X類較所有Y類前面時。若今天有Y類排在X類前面，如上述調換順序後的情形，則 Minhash 值勢必不會相等。 由於採取隨機排序，所以X類排在Y類前面的機率則為$\frac{|X|}{|X|+|Y|}$ (第一個抽籤抽到X的機率)，當選取次數K夠大時，會相當接近理想機率值。我們得到結論: P(Minhash(C1) = Minhash(C2)) = $\frac{|X|}{|X|+|Y|}$

再來看Jac(C1,C2)，根據 Jaccard similarity 的定義，得到:
Jac(C1,C2) = $\frac{|C1∩C2|}{|C1∪C2|} = \frac{|X|}{|X|+|Y|}$

非常神奇的，我們得到了P(Minhash(C1) = Minhash(C2)) = Jac(C1,C2)的結論。所以 Minhash 在保留相似度的前提下，達到了降維的效果。

Minhash 實作技巧

• 隨機排序: 由於隨機排序本身十分花費時間，所以我們採取 row hashing，隨機選取K個 hash function，對每個 row 進行 hash，並確保不會發生 collision，則可達到隨機排序的效果。
  • 若元素有M個，隨機選取a、b<M，c為大於X的質數，可產生隨機的 hash function: $h(x) = (ax+b)%c$
• 第一個元素: 經過 row hashing 後的值越小，排在越前面。所以要找出第一個元素，只需將每個值為1的 row 丟入 hash function 中，紀錄最小的 hash 值，即為第一個元素。