[CS246] Finding Similar Items (3) - Minhashing

 

 

Jaccard Similarity

자카드 유사도는 두 집합의 유사도를 구하는 방법 중 하나이다.

두 집합 $A,\ B$의 자카드 유사도를 구하면 다음과 같다.

\[ J(A,\ B) = \cfrac{|A \cap B|}{ |A \cup B| } = \cfrac{|A \cap B|}{|A| + |B| - |A \cap B|} \]

Jaccard similarity = 3/8

 

※ 자카드 거리(Jaccard distance)는 $d_J(A,\ B) = 1 - J(A,\ B)$ 이다.

※ IoU(Intersection over Union) 과 식이 유사하지만 보통 IoU는 region, bounding box 에서 사용되는 용어이다.

 

자카드 유사도는 앞서 설명한 characteristic matrix의 column similarity를 계산하는데 사용된다. (컬럼이 곧 집합을 의미한다고 설명함)

Example Matrix

두 컬럼 $C_1,\ C_2$의 합집합과 교집합은 각각 $\{ a,b,c \}$와 $\{ a \}$이므로 자카드 유사도는 $1/3$ 이다.

Minhashing

Minhashing

similarity를 빠르게 추정(estimate)하는 방법이다. 행렬의 row의 순서를 바꾸어(permute) 해싱한다.

minhash value는 1이다.

 

Signature

몇 번의 random permutation을 통해 얻은 값(또는 matrix)이다.

일반적으로 characteristic matrix보다 훨씬 크기가 작다.

 

Example: Minhashing (Conceptual, Not actually implemented this way)

matrix의 컬럼개수(=집합개수)가 4이므로 signature matrix의 컬럼도 4개이다. (편의상 C1~C4라 하자) signature matrix의 row의 값은, 각 컬럼(집합)이 처음으로 1이 나타나는 row index가 된다. 이때 처음이라는 것은 row의 순서가 있다는 것을 의미한다. C1은 row=3에서, C2와 C3는 row=1에서, C4는 row=2에서 처음으로 1이 나타나므로 signature는 [3,1,1,2]가 된다. 보라색 row로 얻은 signature를 보라색으로 나타냈다.

row순서를 random하게 permute하여 녹색 row를 얻었다. row의 순서가 바뀜에 유의. C1과 C2는 row=2에서, C3는 row=1에서, C4는 row=3에서 처음으로 1이 나타나므로 signature matrix는 [2,2,1,3]이다.

row의 순서를 바꾸어 붉은 row를 얻었다. C1은 row=1에서, C2는 row=5에서, C3는 row=3에서, C4는 row=2에서 처음 1이 나타나므로 signature는 [1,5,3,2] 이다.

(row 순서에 대한 그림)

이렇게 얻은 signature matrix는 원래의 characteristic matrix보다 compressed data를 표현한다.

 

Subtle Point

minhash value가 원래 행렬의 row이거나 permuted order여야 하는가? 그것은 중요하지 않다!

일관성을 가져야 할 부분은 첫번째 1이 같은 row에 있는 경우에만 두 column(set)이 동일한 값을 갖기만 하면 된다.

 

Minhashing and Jaccard Similarity

두 컬럼 $C_1,\ C_2$와 해시함수 $h$에 대하여, $h(C_1)=h(C_2)$일 확률과 $J(C_1, C_2)$는 같다.

즉 $\Pr(h(C_1) = h(C_2)) = J(C_1, C_2)$

proof

두 컬럼은 크게 3가지 타입이 있다. 둘다 1인 경우, 어느 한쪽만 1인 경우, 모두 0인 경우가 있고 각각 $A,B,C$라 하자. 

자카드 유사도를 구할 때 타입 $A,B$만 고려하면 된다. 타입 $A$인 row의 개수와 타입 $B$인 row의 개수를 각각 $a,b$라 하면 $J(C_1, C_2)=a/(a+b)$ 이다.

그리고 타입 $A$인 경우에만 $h(C_1)=h(C_2)$이므로 위 성질이 성립한다.

 

Similarity for Signatures

시그니처의 유사도는 같은 row의 부분이다. 정확히 동일하지 않지만, 시그니처의 크기가 클 수록 에러의 기대값은 점점 작아질 것이다.

Example: Similarity (Stanford CS246)

편의상 input matrix와 signature matrix의 컬럼을 $C_i,\ S_i$라 하자.

$J(C_1, C_2)=1/4, \ J(S_1, S_2)=1/3$

$J(C_2, C_3)=1/5, \ J(S_2, S_3)=1/3$

$J(C_3, C_4)=1/5, \ J(S_3, S_4)=0$

반응형

Implementation of Minhashing

실제 빅데이터를 가정하여 10억개의 row가 있다고 하자. 이 경우 random permutation 자체도 버겁다. 그리고 각 permutation마다 10억개의 entry가 존재한다. 순열 순서대로 10억개의 row에 접근하면 thrashing이 발생한다.

 

※ Thrashing (쓰레싱): (OS에서) 메모리 영역에 접근할 때 page fault가 지속적으로 발생하여 CPU 효율이 급격히 떨어지는 현상. 10억개의 row에 random하게 접근하면 page fault rate가 매우 높기 때문에 빠른 속도로 처리되기 어렵다.

 

permuting row를 직접 구현하지 않고, permuting에 근사시켜 문제를 해결한다. 이때 사용되는 방법이 해시함수이다.

$n$개의 row index의 해시값 $h(r),\ (r=\{ 1, \dots, n \})$ 을 random permutation으로 사용한다.

 

slot matrix $M$를 만들어 $M(i,c):=h(r)$을 덮어쓰는 방식으로 signature matrix를 구현한다.

slot matrix의 크기는 (해시함수 개수) $\times$ (컬럼 개수) 이다.

 

Algorithm

$T$를 characteristic matrix, $M$을 slot matrix라 하자.

step 1: $M$의 모든 원소를 $\infty$로 초기화한다.

step 2: 각 해시함수 $h_i$와 컬럼 $c$에 대하여 $h_i(r)$을 구한다.

step 3: $T$의 행렬을 순회하면서 $T(r,c)=1$이면

    step 3-1: 각 해시 함수 $h_i$에 대하여 $M(i, c) \leftarrow \min\{ M(i, c), \ h_i(r) \}$

 

Example: Minhashing

Example Matrix (MMDS textbook)

characteristic matrix는 위와 같고, 2개의 해시함수 $h_1(x) = (x+1) \mod 5, \ h_2(x)=(3x+1) \mod 5$ 가 주어질 때 signature matrix $\text{SIG}$을 구해보자.

$\text{SIG}$의 크기는 (해시함수 개수) $\times$ (컬럼 개수) 이므로 $2 \times 4$ 행렬이고 무한대로 초기화한다.

모든 row 의 해시값을 미리 구한다.

row=0 M(r, c)=1인 컬럼은 $S_1,\ S_4$이다. row=0의 해시값은 (1, 1) 이다. $S_1,\ S_4$의 값을 업데이트한다.

row=1 M(r,c)=1인 컬럼은 $S_3$이다. 해시값은 각각 (2, 4) 이다. $S_3$에 대해서만 업데이트한다.

row=2 M(r,c)=1인 컬럼은 $S_2,\ S_4$이다.  row=2의 해시값은 각각 (3, 2) 이다. $S_2,\ S_4$의 값을 업데이트한다. 이때 $S_4$의 기존 값이 현재 해시값보다 작으므로 $S_4$의 값은 바뀌지 않는다.

row=3 M(r,c)=1인 컬럼은 $S_1,\ S_3,\ S_4$이다.  row=2의 해시값은 각각 (4, 0) 이다. $h_1$에서 생긴 값은 바뀌지 않지만, $S_1,\ S_3,\ S_4$의 $h_2$는 현재 해시값이 더 작으므로 업데이트된다.

row=4 M(r,c)=1인 컬럼은 $S_3$이다. 해시값은 각각 (0, 3) 이다. $S_3$만 업데이트한다.