728x90 반응형 cs2641 [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. 이전 1 다음 728x90 반응형
