728x90 반응형 shingling2 [CS246] Finding Similar Items (2) - Shingling Shinglings$k$-Shinglingsdocument를 길이가 $k$인 문자열 집합으로 표현한다.예를 들어 "abcdabd"에 대해 $k=2$인 2-shingling 집합은 {ab, bc, cd, da, ab, bd} 이다.공백과 관련하여 몇까지 옵션이 가능하다. (blank, tab, newline 등)일반적으로 $k=9,\ 9,\ 10$ 정도로 한다. textually similar한 문서들은 많은 수의 shingling이 겹칠 것이다. 단순히 한단어를 바꾸는 것으로는 $k-1$ 거리만큼만 바뀐다. 예를 들어 "The dog which chased the cat" 과 "The dog that chased the cat"을 비교해보자.두 문장의 차이점은 오직 "g_which_c"에서만 발생한다.. 2023. 9. 19. [CS246] Finding Similar Items (1) - Introduction Big Picturenaive하게 similar item을 찾는다고 하면 이중 루프를 통해 유사도를 계산하는 것을 생각할 수 있다. 해싱(hashing)을 이용하여 제곱의 시간복잡도 없이 유사한 아이템을 빠르게 찾을 수 있다.대표적인 알고리즘으로 Locality-Sensitive Hashing (LSH)에 대하여 공부할 것이다.LSH의 장점으로 매우 적은 pair만으로도 계산이 가능하다는 것이고, 단점으로 false negative가 존재할 수 있다는 것이다. ApplicationsFinding Similar Documentsweb, 뉴스 기사 등의 매우 큰 스케일에서 문자 그대로(textually) 유사한 문서를 찾는 것이다. 의미가 비슷한(similar meaning, topic) 것을 찾는 것이 아.. 2023. 9. 18. 이전 1 다음 728x90 반응형
