[t:/]$ 지식_

minhash를 쓰는 이유

2018/03/12

곰곰히 생각해 본 추정이다.

막상 직접 날로 짜다면 minhash의 원리를 생각해볼 때, 굳이 해시든 min이든 로캘리티든 고려할 필요가 없다. 즉, 피쳐들을 깔아놓고 랜덤하게 뽑으면 된다. minhash의 원리라는 것은 이렇다. a 집합에서 눈감고 3개를 뽑고, b 집합에서 눈감고 3개를 뽑았을 때 둘의 일치율(자카드)을 보면 높을 수록 a와 b가 유사하다는 것에서 출발이다.

그렇다면 그냥 랜덤 때리면 안 되나? 왜 랜덤 안 때리고 minhash를 돌리지? 방금 전까지 랜덤으로 구현하고 있었다. 원하는 결과가 나오는 것 같았다. 근데 왜?

그냥 추정해보자면 이렇다.

만약 피쳐 공간이 100만개짜리라고 보자. 랜덤으로 100개만 뽑는다고 가정할 때 랜덤 추출기는 100만개의 피쳐 공간을 한 번에 확보하고 있어야 한다. 즉, 분산 처리가 어렵다. 이를 피봇해서 100만줄로 바꾸면 어떻게 될까. 100개의 해시 함수로 100만줄을 스캔하면서 처리할 수 있다. 메모리를 덜 쓰고 분산 처리도 할 수 있다.

이런 걸까?

아님 말고. 하핳핳핳..









[t:/] is not "technology - root". dawnsea, rss