[웹정보] ch03 Finding Similar Items1

Mining of Massive Datasets

Jure Leskovec Stanford University, Anand Rajaraman Rocketship Ventures, Jeffrey D. Ullman Stanford University

 

Chapter03 Finding Similar Items

 

Shingling

문서, 이메일 등을 set으로 전환

• 2-Shingle 예시
• k = 2, doc = ab cab
• Set of 2-shingles = {ab, b_, _c, , ca}
• (?? , 중복이면 한번만 써도 되나)

• k는 보통 8, 9, 10
• 8비트로는 256가지 표현 가능한데
• charactor는 몇가지 안됨.
• 1Shingle이 1바이트이지 않아도 됨.
• 모든 char 조합 중 사실 실제 사용하는 것은 극히 적은 부분임.
• 4바이트에 8Shingle의 정보를 담아도 될 듯!
• -> Hashing!

 

Minhashing

similarity를 보존하면서, 큰 set을 작은 set(signature)으로 전환. 

 

Jaccard Similarity: 

 

Column Similarity (based on Jaccard Similarity):

 

Minhashing

• Permute the rows
• Define minhash function: ex. h(c) = 1이 나오는 첫번째 행 번호
• Signature matrix를 구함
  • 행은 minhash values
  • 열은 document

 

Minhasing & Jaccard Similartity

Minhashing을 통한 similarity와 Jaccard similarity의 기대값은 동일하다!

두 기댓값 모두 아래와 같다.

• Jaccard Similarity
• "교집합/합집합" 이기 때문 위의 식과 같다,

• Minhashing (Similarity for Signature)
• 만약 a type의 row였다면 h(C1) = h(C2)
• b, c type이었다면 h(C1) != h(C2)

기댓값이 같은거지 정확히두 값이 같은 것은 아님!!

jaccard similarity와 비슷해지려면 permute 횟수를 늘려야함!

 

Implementation of Minhasing

문제점:

• 만약 1billion row라면..?
• random permutation하는 것이 매우 어려울 것임
• sub array도 필요로해서 공간 사용이 늘어남

해결책:

100개의 해시 함수를 선택하자!

(hash function을 사용해 pemuting에 근사시켜 문제를 해결하자!)

 

Locality-sensitive hashing

지금까지 signature matrix를 만들었다면 지금부터는 비슷한 pair를 고르는 것!

(b번 했을 때 적어도 한 번은 bucket에 들어가도록)

비슷한 document면 적어도 한번은 같은 bucket에 들어가지 않겠냐!!라는 아이디어에서 나옴

같은 bucket에 들어간 적이 없으면 이 둘의 similarity는 매우 작다!!

그래서 밴드의 수 b와 행의 수 r을 조정하는 것이 중요하다!

 

Locality-Sensitive hashing의 예시

80% similar한 C1과 C2에서는 과연 어떻게 될까?

전체에서 80% 비슷하다? -> 각 band 안에서도 80%가 비슷하다고 생각해도 무방하다!

b = 20이고, r = 5라고 예시를 들어보겠다.

LSH로 similar하다고 판단할 확률 = 하나의 버켓에 들어갈 확률 =  (0.8)^5 = 0.328

반대로 not similar하다고 판단할 확률 = 20번 모두 다른 버켓에 들어갈 확률 = (1-0.328)^20 = 0.00035

이상적인 그림

특정 similarity가 넘으면 bucket을 sharing화면 좋겠다!!

위의 그림은 minhash 값만 고려한 것임. 하지만 밴드를 사용하면?

아래의 그림처럼 됨. 좀 더 이상향에 가까워짐.