728x90 반응형 locality-sensitive hashing2 [CS246] Finding Similar Items (4) - Locality Sensitive Hashing (LSH) Recap: Shingling and Minhashing$k$-shinglesdocument를 set으로 매핑. 아래 표는 $k=3$인 경우의 예시다.Jaccard Similarity두 집합의 유사도를 구하는 방법 중 하나.$J(S, T) = \text{sim}(S, T) = \cfrac{|S \cap T|}{S \cup T}$$\text{sim}(S_1, S_3) = \cfrac{2}{3}$ Minhashrow의 random permutation을 하나 고르고, 처음으로 1이 나오는 row index를 minhash value로 한다.$h(S_1)=0,\ h(S_2)=2,\ h(S_3)=1$$\Pr(\text{minhash is same}) = \text{Jaccard Similarity}$Locali.. 2023. 9. 21. [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 반응형
