Find Similar Documents

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

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

Last updated 2 months ago

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)$

$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$ 을 작게 설정하면 된다.

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)$

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

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

특정 밴드에서 $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$ 을 작게 설정하면 된다.