[데이터마이닝] 3. 유사항목 찾기(Finding Similar Items) -3 민해싱 실제 구현은? Minhashing

 

permutation을 하여 민해싱을 하는것은 이론적으로는 가능하지만.

시간적으로, 메모리 공간적으로 비현실적이다. 

그래서 실제로 노드를 peremutiation하지 않고 .hash fucntion을 사용한다. 

100개의 hash function을 이용한다는것은 100번 permutation한다는것임. 해당 hash value 가 바뀐 row number.

 

documnet가 set이 되고 set을 1개의 column으로 표현. 

M(i,c) i번째 hash function, c번째 문서(set)

M(i,c)는 hi(r)값들중 가장 작은 값이 된다. 

 

각 row에 대해서 100개의 hash function을 이용하여 현재 진행중인 row r의 hash 값을 구한다. 

각 column에 대하여 해당 row에서 1이 있으면 hi값을 가지고 제일 작은 값을 찾으면 된다. 현재 값은 slot에 들어있다. 현재의 hi(r)이 더 작은가? 그렇다면 update해 주라. 

 

 

Example을 봅시다. 

기존 row번호가 hash function에 의해서 어떤 row 번호로 바뀌는지 보는것. 그중 가장 작은것을 signature로 한다.

 

왜 같나요요? signature 유사도와 jaccared similarity가?

두 set이 어느정도의 같은 shingle을 가지고 있는가? 를 통해 자카르드 유사도를 알 수 있다. 

시그니처 유사도는 두 set(열) 에 대하여 특정 슁글에 대한 행이 permutation되어서 어떤 특정 열로 간다. 그중 가장 먼저 나온 셋의 행 번호를 signature값이라고 하는데 .  .. 다시 생각해 보자. 

 

input matrix에 두 셋에 대한 3가지 행 타입이 있다. 

x타입 : 두 열에서 모두 1

y타입 : 한 열에서는 1 다른 한열에서는 0

z타입 : 두 열에서 모두 0 

 

무작위로 순서과 변경된 행들이 있을때  y타입을 발견하기 전에 x타입 행을 발견할 확률은 x/(x+y) 

이는 두 행의 자카드 유사도가 된다. 

 

 

row단위로 저장된것이 아니라 column단위로 저장된것이 많은것 column이 document니까 이게 자연스러운거겠지.

sorting을 해서 matrix를 row별로 바꿔주는 작업을 해야한다. 

 

 

 

Minhashing의 cost는 row의 개수에 비례한다. 금방 1을 만났으면 그 나머지 billion - a개는 괜히 .. 했다. 

다 하지 말고 first 1000개정도만 해보자. 이런식으로 일 진행하면 좋다.~

안좋은점음 초기 1000개의 row만 가지고 했을때.. 그런데 없으면..!!! 그러면 minhash값을 구할 수 없는 것이다. 

 

값이 없는 column이 두개가 있다. 값이 없으니까. simmilar하나? ㄴㄴ 그렇다고 말할수 없다. 

 

 

주어진 rows를 k개의 band로 나눈다. 

band별로 minhash competition을 한다. 5개의 밴드