Finding Similar Items

hashing은 insert, delete, lookup 하는데 모두 O(1) 시간 걸린다.

 

Locality-Sensitive Hashing(LSH)

: similar 한 아이템쌍을 찾기 위해 O(n^2)의 시간을 쓰지 않고도 할 수 있는 방법

• hash function을 이용하여 bucket에 아이템을 넣는다
• Upside(장점): buckte에 들어온 것들만 비교하면 되므로 비교 횟수가 적음
• Downside(단점): false negative 발생

 

어휘가 비슷한 문서들을 찾는다고 가정해 보자.

(LSH는 비슷한 내용이 아니라 비슷한 어휘를 찾기 위함)

ex) Mirror site(비슷하게 쓰인 사이트), Plagiarism(표절)

 

 

찾는 순서

1. Shingling: 문서에 쓰인 어휘들을 K길이의 문자들의 집합으로 변환

2. Minhashing: 큰 집합을  시그니처로 변환.

3. Locality-sensityve hashing: 비슷한 시그니처의 쌍들을 찾기

 

 

 

Shingles

k-shingle: 문서에 나타나는 k 길이의 연속된 문자열

ex) k=2, doc=abcab

-> {ab, bc, ca}

 

어휘적으로 비슷한 문들은 많은 공통의 shingle들을 가진다.

k의 길이가 너무 짧으면 대부분이 비슷한 문서로 판명된다.

그러므로 보통 k는 8~10 정도로 사용한다.

 

저장공간을 절약하기 위해 각 shingle들을  hash 함수를 통해 4byte로 보관한다.

-> tokens이라 부른다.

 

 

 

Minhashing

Jaccard Similarity

 

교집합인 원소가 3개고

합집합인 원소가 8개라면 

Jaccard Similarity는 3/8이 된다.

 

 

집합들을 Boolean Matrices로 표현하기

 

Rows=전체 집합의 원소들

Columns= 집합들

예) 집합에 원소 e가 있다면 1로 아니면 0으로 표현

 

Column similarity란 Jaccard Similarity이다.

실제로 matrix를 구축하는 건 아니고 존재한다고 가정만 하는 것.

예)

두 집합이 모두 가지지 않는 원소는 합집합에 포함하지 않는다.

 

 

Minhashing

minhashing function을 정의하자

h(C)=row들의 원소들을 랜덤으로 뽑아서 처음으로 나오는 1이 몇 번째인지

 

모든 column에 적용해서 각 column에 대한 signature matrix를 만들자

columns=sets

rows=minhash function의 결괏값

원소들을 순서대로 뽑았을 경우

1번 집합에 처음으로 1이 나오는 원소의 번호는 3

2번 집합에 처음으로 1이 나오는 원소의 번호는 1

 

원소들을 뒤에서부터 뽑았을 경우

1번 집합에 처음으로 1이 나오는 원소의 번호는 2

2번 집합에 처음으로 1이 나오는 원소의 번호는 2

원소들을 랜덤하게 뽑았을 경우

1번 집합에 처음으로 1이 나오는 원소의 번호는 1

2번 집합에 처음으로 1이 나오는 원소의 번호는 5

 

두 집합의 signature값이 동일한 확률은 Jaccard similarity값과 동일하다.

그리고 시그니처가 길어지면 오류가 줄어든다

 

 

 

Minhashing 구현

• 행이 10개가 있다면 랜덤으로 고르기 어려울 것이다.
  -> 행들을 랜덤으로 접근하기 위한 좋은 근사치는 100개의 해쉬함수를 선택하는 것
• M=slot matrix, r=행번호, c는 열번호, i는 해쉬함수 번호, h는 해쉬함수일 때,
  M(i, c)를 h(r)로 근사 시켜서 signature matrix를 구한다.
•  slot matrix의 크기는 (해쉬함수 개수) * (칼럼 개수)
• h(r)은 min(M(i, c), h(r))로 구한다.

* 구하는 방법

1. 해쉬함수가 2개, 행의 개수가 2개이므로 2*2짜리 매트릭스 만들고,

일단 Sig1과 Sig2를 무한대로 초기화

 

2. Row=1일 때 1을 가지는 행은 c1 하나

h(1)=1, g(1)=3

Sig1을 1,3으로 업데이트

 

3. Row=2일 때 1을 가지는 행은 c2 하나

h(2)=2, g(2)=0

Sig2을 2,0으로 업데이트

 

4. Row=3일 때 1을 가지는 행은 c1, c2 둘 다

h(3)=3, g(3)=2

Sig1, Sig2를 업데이트해야 하는데 

가장 작은 수로 업데이트 해야 하므로 

Sig1 만 3을 2로 업데이트

 

5. Row=4일 때 1을 가지는 행은 c1 하나

h(4)=4, g(4)=4

가장 작은 수로 업데이트 해야 하므로 

업데이트하지 않는다.

 

6. Row=5일 때 1을 가지는 행은 c2 하나

h(5)=0, g(5)=1

가장 작은 수로 업데이트해야 하므로

Sig2의 2를 0으로 업데이트

 

 

* 성능 향상 - (1)

 minhashing의 비용은 rows의 개수에 영향을 받는다.

그러므로, 1000개의 rows만 해쉬 한다면 비용을 아낄 수 있다.

이렇게 했을 때 장점: 시간을 많이 아낄 수 있다.

단점: 모든 1000개의 row에서 column들이 0을 가진다면 minhash값을 가질 수 없다.

 

(2)

row들을 k개의 band로 나눈다.

위에서 아래로 내려가며 각각의 band에 대한 minhash값을 계산한다.

그러므로 원하는 개수의 minhash값을 얻으려면 row당 (1/k) 번만 계산하면 된다.

* k를 너무 크게 만들지 말아라

-> 크게 만들면 아무 값도 못 얻을 수 있다.

 

 

Locality-Sensitive Hashing

목표: 비슷한 객체를 같은 buckket에 담기
그러나 일반 해쉬함수는 같은 객체만 같은 bucket에 담을 수 있다.

어떻게 비슷한 객체를 담을 수 있을까?

similarity threshold 변수 t에 의해 비슷하다는 걸 정의하자.

 

방법: 시그니처의 행을 band로 나눈다.

-> band로 나누는 이유
: band(부분)으로 나누게 되면 band에서는 같은게 나오지 않을까라는 기대값이 생기게 된다.

1. 시그니처들을 r개의 행을 가진 b개의 band로 나눈다

 

2. 각 band의 coloumn들을 K개의 bucket으로 hash한다.

• K는 가능한 크게 설정
  -> 비슷한애들 잘 분류하기 위해
• band마다 다른 bucket 사용
• 적어도 하나이상 같은 bucket에 담긴 쌍을 candidate column pairs로 정의

예) 100,000 column를 가지고=signature가 100,000개

signature는 100개의 숫자(row)를 가진다.

따라서 4*100*100,000byte=40Mb.

80% 비슷한 쌍을 찾고싶다.

20개의 band를 만들자

-> 그러면 각 band당 5개의 row를 가지게 된다.

 

이 때, C1과 C2의 band 1개가 동일할 확률은 (0.8)^5=0.328

C1과 C2의 모든 band가 동일하지 않을 확률은 (1-0.328)^20=0.00035

(band 20개를 다 확인했는데도 같은 bucket에 안담길 확률)

 

40% 비슷한 쌍으로 바꿔보자.

C1과 C2의 band 1개가  동일할 확률은 (0.4)^5=0.01

C1과 C2의 모든 band가 동일하지 않을 확률은 (1-0.01)^20

C1과 C2의 band들 중 적어도 하나이상 동일할 확률은 1-(0.99)^20 < 0.2

-> 전체 band로 봤을 때 약 18% 확률로 40% 유사도인 애들도 같은 bucket에 들어갈 수 있다.

 

이걸로 알 수 있는 사실

: 한 시그니처가 일치할 확률을 S, band개수가 b, row 개수가 r일 때 

S^r  : band 한개에서 모든 시그니처가 일치할 확률
(1-s^r)^b : 모든 밴드에서 모든 시그니처가 일치하지 않을 확률
1-(1-s^r)^b : 모든 밴드에서 모든 시그니처가 일치할 확률

-> 이 계산식으로 t를 몇으로 잡아야 할지 구할 수 있다.

-> t~(1/b)^(1/r)로 구하면 된다.

예) 

b=20, r=5

 

LSH의 유의점

• 후보쌍들이 실제로 비슷한 집합인지 체크해봐야함
  (시그니처도 완벽하게 일치하다는 보장이 없어서)