> For the complete documentation index, see [llms.txt](https://riverallzero.gitbook.io/summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://riverallzero.gitbook.io/summary/data-mining/find-similar-documents.md).

# Find Similar Documents

<figure><img src="/files/FOpeGuy9eWgjfYXIKqT0" alt=""><figcaption></figcaption></figure>

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

![](/files/UMqdFCnyhmcRenxnz6ts)

* 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

![](/files/yPu5m6Ql1JVtiVDh69MX)

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