[Data Mining] 3 - Finding Similar Items : Locality Sensitive Hashing

Finding similar items

ex.

- pages with similar words

- Customers who purchased similar products

- Images with similar features

- Recommendations and search

 

 

Problem definition

고차원 데이터 points x1, x2, .... , xn이 주어진다.

distance fuction d(x1, x2) 가 주어진다. 이는 x1과 x2 사이의 거리를 나타낸다.

 

d(xi, xj)가 s보다 작은 모든 pair of data points(xi, xj)를 찾아보자.

 

Naive solution : O(N^2)

N은 data points의 크기를 나타낸다.

LSH를 사용하면 O(N)만에 가능하다.

 

 

3 Essential steps for finding similar docs

1. Shingling : Convert documents to set representation (boolean vector)

2. Min-Hashing : Convert large sets to short signatures, white preserving similarity.

3. Locality-Sensitive Hashing (LSH) : Focus on pairs of signatures likely to be from similar documents

 

Document as high-dimensional data

1. shingling : Convert dociment to a set

A k-shingle (or k-gram) for a document : 문서에 등장하는 k자로 이루어진 문자열들의 집합.

토큰은 대상에 따라 문자나 단어 또는 다른 것이 될 수 있다.

긴 shingle을 압축하기 위해서 4바이트로 해싱한다.

k-shingles의 해시값의 집합으로 document를 나타낸다.

Idea : 해시값들이 공유될 때, 두 document는 일반적으로 shingle들을 가진 것 처럼 보일 수 있다. (?)

 

 

compressing shingles

ex.

k=2, document D_1 = abcab, D_2 = abcf

set of 2-shingles : S(D_1) = {ab, bc, ca}, S(D_2) = {ab, bc, cf}

hash the shingles : h(D_1) = {1, 5, 7}

k = 8, 9, or 10 이 보통 쓰임.

 

shingle의 장점

1. 직관적으로 비슷한 문서는 일반적으로 많은 shingle들을 갖는다.

2. 단어나 문자가 변경되었을 때 k-1 distance 만 영향을 받는다.

2-shingles에서 abcde -> abfde로 변경되었을 때, bc, cd -> bf, fd로 2개만 영향을 받는다.

 

Similarity metric for shingles

문서 D_1 은 k-shingles C_1 = S(D_1) 의 집합.

동일하게, 각 문서는 k-shingles의 공간 0/1 벡터이다.

각 유일한 shingle은 1차원이다.

벡터는 매우 드물다. (?)

 

Jaccard similarity : 전체집합 중 교집합의 비율

sim(C1, C2) = |C1 and C2| / |C1 or C2|

0 <= jaccard similarity <= 1

jaccard distance : d(C1, C2) = 1 - sim(C1, C2) = 1 - |C1 and C2| / |C1 or C2|

 

(사진 삽입, 15p)

 

 

From sets to Boolean matrices

행 : shingles의 요소

열 : 집합 (documents)

 

shingles\documents	C1	C2	C3	C4
ab	1	1	1	0
bc	1	1	0	1
cd	0	1	0	1
de	0	0	0	1
ef	1	0	0	1
fg	1	1	1	0
gh	1	0	1	0

 

sim(C1, C2) = ?

교집합 수 = 3

size of union = 6 {ab, bc, cd, ef, fg, gh}

Jaccard similarity(not distance) = 3/6

d(C1, C2) = 1 - (Jaccard similarity) = 1 - 3/6 = 3/6

 

 

Hashing columns (signatures)

key idea : 해시함수 h를 통해 document C는 다음을 만족하는 해시값 h(C)를 갖는다.

(1). h(C)는 메인 메모리에 저장하기에 적합한 크기를 갖는다.

(2). sim(C1, C2)는 'h(C1)과 h(C2)의 similarity'와 같다.

 

Goal : 다음을 만족하는 해시함수 h를 찾자.

sim(C1, C2)가 높으면 높은 확률로 h(C1) = h(C2) 이다.

sim(C1, C2)가 낮으면 높은 확률로 h(C1) != h(C2) 이다.

 

similarity가 높은 문서끼리 같은 해시값을 갖을 것이다!

해시함수는 similarity metric에 의존적이다.

모든 similarity metrics가 해시함수에 적합한 것은 아님.

 

Jaccard similarity에 적합한 해시함수가 존재함 : Min-Hashing

 

Min-Hashing

permutation phi, input matrix(Shingles X Documents 행렬) 이 주어진다.

Signature Matrix M을 출력한다.

 

(사진 삽입 22p)

 

과정

1. 최종 생성해야하는 Signature Matrix 의 값은 permutation index이다.

2. permutation을 1부터 순서대로 선택한다.

3. permutation에 해당하는 matrix의 column값이 1이면 동일한 column에 해당하는 Signature Matrix를 permutation index로 채운다.

4. permutation index가 작은 순서대로 row를 선택해서 진행한다.

 

(사진 삽입 24p)

 

특성

pr[h(C1)=h(C2)] = sim(C1, C2)

document X와 X에 속하는 shingle z가 존재한다고 하자.

pr[phi(z) = min(phi(X))] = 1/|X|

임의의 z가 min 요소에 매핑되는 것과 유사하다.(?)

 

잘 모르겠음...(26p)

 

 

Similarity for Signatures

두 signature의 similarity는 (같은 행 갯수) / (행 크기)

signature가 길수록 예상 오류(|sim(C1, C2) - sim(h(C1), h(C2))|)가 작음.

 

(사진 삽입 28p)

 

 

Locality sensitive hashing(LSH)

goal : Jaccard similarity 가 s 이상인 documents들을 찾아라.

LSH - General idea : X, Y가 후보일 수 있도록 하는 해시 함수를 사용한다.

similarity는 계산할 수 있어야 함.

 

1. similarity threshold s를 뽑는다. (0 < s < 1)

2. signature matrix M의 열 x, y의 signature 비율이 s보다 크면 (x, y)는 후보 pair이다.

M(i, x) = M(i, y) for at least frac. s values of i ( 0 < i < signature size)

문서 x, y는 같은 (Jaccard) similarity를 갖는다고 추측해볼 수 있다.

 

비슷한 문서들은 같은 해시값을 가질 가능성이 높다. = 어떤 해시 bucket 안에 들어있는 문서들은 비슷하다.

같은 해시 bucket 안에 있는 문서들은 후보 pair가 될 수 있다.