min hash

http://www.stanford.edu/class/cs276b/handouts/minhash.pdf

 

jaccard measure : 교집합/합집합

열 :  1 2 3 4 5 6

c1 :  0 1 1 0 1 0
c2 :  1 0 1 0 1 1

 

sim(c1,c2 ) = 2/5 = 0.4( c1과 c2가 0인것은 제외 )

 

관심사항은 c1이나 c2에 적어도 하나이상은 값이 있는 열

 

총 6개의 열이 있다고 할때 4번 열은 c1,c2가 0이기 때문에 제외하고

random하게 하나의 열을 선택했을때

3번 열이나 5번열이 선택될 확률( c1 = c2 = 1 일 확률)

4번 열을 제외했을때 남은 열의 수는 5개이고 그중에서 3,5번열을 선택할 확률은 결과적으로

2/5가 된다.

( 어차피 min hash라는게 열들을 random permutation해서 min( rank )를 선택하는 문제다

다시 말하면 min 값 말고 다른 것들은 의미 없다는 것이 된다.

그러면 결과적으로 열중에 하나를 선택하는 문제와 다를게 없다.

물론 선택을 할때 중복 선택을 배제해야 min hash에서 말하는 것과 같아지게 되지만

 

처음 예로 든 것에서

내가 1,3,5열을 차례대로 선택하게 되면( c1=c2=1인 경우는 1, 아니면 0 )

값은 0 1 1

그러면 결과적으로 c1 c2의 유사도는 2/3라고 추정할수 있다.

 

 

설명에도 나타나 있듯이 signature를 많이 선택할수록 정확률은 높아진다.

 

 

---------- 추가 -----------

http://www.stanford.edu/class/cs276b/handouts/minhash.pdf 이 pdf파일 중  위 이미지에 대해서 자세히 설명을 하면 다음과 같다.

순열 함수가 아래와 같이 3개가 있다고 가정한다.( 순열함수라는 것은 원본 데이터를 아래와 같은 순서로 읽겠다는 의미이다. 

단 읽는 순서가 변경이 되어도 원래 가지고 있던 데이터의 위치값은 변하지 않는다. 

예를 들면

a b c d 라고 있을때

첫번째 값은 a

두번째 값은 b

세번째 값은 c

네번째 값은 d 이고 이것을 역순으로 읽으면

d c b a 이다.

여기서 각 데이터의 원본 위치값으로 데이터를 치환하면 4 3 2 1 이 된다. )

perm1 = 1,2,3,4,5

perm2 = 5,4,3,2,1

perm3 = 3,4,5,1,2

데이터가 아래와 같이 있다.

C1 = 1 0 1 1 0

C2 = 0 1 0 0 1

C3 = 1 1 0 1 0

위 데이터를 설명을 좀 편하게 하기 위해서 1을 다른 심볼들로 대체한다.

0 은 그대로 0이고

1만 순차적으로 알파벳으로 대체

C1 = a 0 b c 0

C2 = 0 d 0 0 e

C3 = f g 0 h 0

첫번째 순열 함수 perm1을 위 데이터에 적용한다.

C1의 경우 첫번째 값이 a(1)이기 때문에 그것의 위치 1 { a(1)에서 괄호안의 1값은 원래 값이 1이었다는 의미이다. jaccard index를 계산할때 보통은 키워드의 존재 유무만 표시하기 때문에 0 또는 1로 표시를 한다. }

C2의 경우 첫번째 값은 0이고 두번째 값이 1이기 때문에 위치 2

C3의 경우 첫번째 값이 f(1)이기 때문에 위치 1

여기서 첫번째 두번째 세번째 이 의미지는 perm1 함수에서 정의한 index값을 기준으로 한다.

그럼 두번째 순열 함수 perm2을 위 데이터에 적용하면

perm2는 5,4,3,2,1이라는 순열이다. 따라서 데이터를 역순으로 읽으면 된다.

C1의 경우 

perm2에 의해 재 나열하면

0 c b 0 a가 된다.

0이 아닌 값은 두번째 c가 되고 c는 원래는 4번째 index에 있었다.

C2의 경우 

perm2에 의해 재 나열하면

e 0 0 d 0이 된다.

0이 아닌 값은 e이고 e는 원래 5번째 index에 있었다.

C3의 경우

perm3의 의해 재 나열하면

0 h 0 g h가 된다.

0이 아닌 값은 h가 되고 h는 원래 4번째 index에 있었다.

세번째 순열 함수 perm3으로 해보면

perm3은 34512이고

이 순열로 다시 재나열을 하면

C1 = b c 0 a 0

C2 = 0 0 e 0 d

C3 = 0 h 0 f g

가 된다.

여기서 0이 아닌 값을 찾으면

c1 = b

c2 = e

c3 = h 이고

b는 원본배열에서는 3번째

e는 원본배열에서는 5번째

h는 원본배열에서는 4번째

          S1 S2 S3 

perm1 = 1  2  1

perm2 = 4  5  4

perm3 = 3  5  4 

가 된다.

이것을 가지고 유사도를 계산하면

계산에 앞서

원본 값을 가지고 유사도를 계산하면

C1:C2 = 0.00

C1:C3 = 0.50

C2:C3 = 0.25이다.

그럼 signature로 추출된 값을 가지고 계산하면

S1:S2 = 0

S1:S3 = 0.67(2/3)

S2:S3 = 0