| # | Contents | Link |
| 1 | Min-Hash 기본 개념 |
http://knol.google.com/k/simple-simhashing# http://www.stanford.edu/class/cs276b/handouts/minhash.pdf |
| 2 | Locality sensitive hashing(LSH) 이론 | http://www.cs.uc.edu/~annexste/Courses/cs728-2008/Lecture18.ppt http://people.csail.mit.edu/indyk/mmds.pdf |
| 3 | Google News 분류에 사용되는 LSH | http://www2007.org/papers/paper570.pdf |
?
if and only if
.
be the member of 
that produces the minimum hash value.
and 
share the minimum hash is equivalent to the probability that 
is in both 
and 
.
has an equal chance of having the minimum hash value, this becomes
위 설명의 이해를 돕기위한 예를 제시해보면 아래와같다.
5개의 요소들을 갖는 두개의 집합 A, B가 있다고 가정하자.
A = { a, b, c, d, e }
B = { b, d, f, g, h }
Then,
A ∪ B = { a, b, c, d, e, f, g, h } , and
A ∩ B = { b, d }
So, the Jaccard coefficient is 2/8.
여기까진 뭐 다아는 내용이고, 이제 hashing 을 이용한 확률적 해석을 해보겠다.
우선, 서로 다른 hash function을 Hi( x )로 표현하며, hash 값은 unique하며,
A ∪ B 에속한 각각의 요소들을 hashing 했을때 다른 값들과 비교해 최소가 되게해주는 hash function이 각각 요소들에대해 존재한다고 가정한다.
예를들어 a 요소를 최소값으로 hashing하는 hash function을 H1(x),
b 요소를 최소값으로 hashing하는 hash function을 H2(x),
c 요소를 최소값으로 hashing하는 hash function을 H3(x),
d 요소를 최소값으로 hashing하는 hash function을 H4(x),
e 요소를 최소값으로 hashing하는 hash function을 H5(x),
f 요소를 최소값으로 hashing하는 hash function을 H6(x),
g 요소를 최소값으로 hashing하는 hash function을 H7(x),
h 요소를 최소값으로 hashing하는 hash function을 H8(x)
라고 한다면, 각각의 요소들이 최소 해쉬값을 갖을 확률은 1/8 이된다.
여기서 A ∩ B 에 속하는 b, d 요소를 최소값으로 hashing하는 함수 H2(x), H4(x)만이
min(H(A)) = min(H(B)) 가 성립하게 되므로,
min(H(A)) = min(H(B)) 가 성립할 확률은 2/8 이된다.
Therefore, the probability that
여기서 좀더 깊이 들어가, Minwise Independent Permutation 에 대한 이해와 LSH 에서 minhash들을 계산하고, 일정한 수의 minhash값들로 grouping하여 각각의 group들을 이용하여 clustering하는 방법에 대해 이해해 보길바란다.
LSH.pdf