Find Similar Documents

web, 뉴스 기사 등의 매우 큰 스케일에서 문자 그대로(textually) 유사한 문서를 찾는 것이다. 의미가 비슷한(similar meaning, topic) 것을 찾는 것이 아니라 문자 수준(character-level)으로 유사한 것을 찾는다.

1. K-Shingling

• document를 길이가 k인 문자열 집합으로 hasing하는 작업이다.

• 예를 들어 "abcdabd"에 대해 인 2-shingling 집합은 {ab, bc, cd, da, ab, bd} 이다.

2. Min Hashing

• similarity를 보존하면서 크기가 큰 집합($C$)을 signature($M$)로 매핑($h$: hashing)하는 작업이다.

• $sim(C_1, C_2)$가 높으면 $h(C_1) = h(C_2)$이고, $sim(C_1, C_2)$가 낮으면 $h(C_1) \neq h(C_2)$ 즉, 유사한 집합끼리는 signature의 유사도 역시 보존되어야한다.

• $Jaccard \ similarity = sim(C_1, C_2)=\frac{|C_1 \cap C_2|}{|C_1 \cup C_2|} = \frac{|M_i = M_j|}{T}$

• $Jaccard \ distance = d(C_1, C_2) = 1 - sim(C_1, C_2)$

3. Locality Sensitive Hashing

• $Jaccard \ similarity$가 $s$(similarity threshold: 0 < s < 1) 이상인 document를 찾는것이다.

• signature matrix($M$)를 bands($b$)의 row($r$)로 나눈다.

• 각 row에서 M의 column들이 각각 bucket에 해시되며, 같은 bucket에 위치한 문서들이 candidate pair가 된다. 이는 해당 문서들이 유사할 가능성이 높다는 것을 의미한다.

• 특정 밴드에서 $C_1$과 $C_2$가 동일할 확률 = $(s)^r$

• $C_1$과 $C_2$가 $b$개의 밴드 중 어느 하나도 유사하지 않을 확률 = False Negative = $[1-(s)^r]^b$

• $C_1$과 $C_2$가 $b$개의 밴드 중 최소 1개 유사할 확률 = False Positive = $1-[1-(s)^r]^b$

• 정리해보면 우리는 $s$의 유사도를 가질때, 문서쌍 중 $1-[1-(s)^r]^b\times100$%는 candidate pair가 된다 즉, 유사하다는 것을 말한다.

• 만약 실제 유사한 쌍을 놓치고싶지 않다면 $b$를 크게, $r$을 작게 설정해 false negative를 줄이고 false positive를 증가시키면 된다. 반대로 유사하지 않은 쌍을 보고싶지 않다면 $b$를 작게 $r$을 작게 설정하면 된다.