Locality Sensitive Hashing

이 포스트는 국민대학교 소프트웨어학부 '빅데이터최신기술' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

이 포스트의 흐름은 전에 작성한 Min-Hashing 포스트에서 이어집니다. 따라서 이 포스트를 보기 전에, 아래의 포스트를 읽어보는 것을 추천합니다.

Min-Hashing

왜 필요한가?

Min-Hashing 포스트에서는 자카드 유사도 계산을 더 빠르지만 덜 정확하게 계산해서 문서 간 유사도 계산 속도를 향상하려 했습니다. 이번에는 탐색 대상의 수를 줄여서 가장 유사한 문서를 찾는 시간을 줄이는 것이 목적입니다. 이를 위해 사용되는 방법이 locality sensitive hashing입니다. 이 또한 정확한 결과보다는 빠르게 유사한 결과를 얻기 위한 목적으로 사용합니다. 이 과정에서는 min-hashing에서 만든 signature를 사용합니다.

Locality Sensitive Hashing

Locality Sensitive Hashing은 탐색 대상 문서들의 signature들 중 서로 유사한 signature끼리 먼저 그룹을 지어놓고, 질의 문서의 signature와 유사도가 높을 것으로 예상하는 몇 개의 그룹을 대상으로 탐색을 진행하는 방법입니다.

그룹을 만드는 과정

유사한 Signature 끼리 그룹을 짓는 방법은 아래와 같습니다.

1. signature를 r 길이의 여러 벡터들로 쪼갠다. 쪼개진 벡터들을 지금부터 band라고 부르자.
2. band들을 해시 함수의 input으로 넣는다.
3. 해시 함수의 출력 값이 같으면 같은 그룹에 포함시킨다.

예를 들어 sum(band의 원소들) mod 10이라는 해시 함수가 있다고 하고, 탐색 대상 문서들(A, B, C, D, E)로 min-hashing을 통해 만든 signature들이 아래와 같다고 합시다.

A의 signature	43	92	11	31	48	19	45	41	56
B의 signature	17	32	46	36	58	18	84	31	71
C의 signature	81	72	31	36	38	57	81	1	56
D의 signature	16	89	7	65	70	27	71	9	43
E의 signature	21	1	60	35	65	87	91	5	17

Band의 길이를 3(r = 3)으로 설정하고 그룹을 지어봅시다. 먼저 처음 얻을 수 있는 band는 아래와 같습니다. 얻어진 band는 'band 1'이라고 이름을 붙입시다.

A의 band 1	43	92	11
B의 band 1	17	32	46
C의 band 1	81	72	31
D의 band 1	16	89	7
E의 band 1	21	1	60

각 band의 해시 값을 계산해 보면 각각 6, 5, 4, 2, 2 이므로 다음과 같이 그룹을 만들 수 있습니다.

	band 1
그룹 1	A
그룹 2	B
그룹 3	C
그룹 4	D, E

다음에 얻어지는 band는 아래와 같고, 이 band들은 'band 2'라고 이름을 붙입시다.

A의 band 2	31	48	19
B의 band 2	36	58	18
C의 band 2	36	38	57
D의 band 2	65	70	27
E의 band 2	35	65	87

같은 해시 함수를 통해 얻은 해시 값들을 가지고 그룹을 만들면 아래와 같이 나옵니다.

	band 1	band 2
그룹 1	A	A
그룹 2	B	B, D
그룹 3	C	C
그룹 4	D, E	E

마지막 band까지 확인하면 최종적으로 다음과 같이 그룹이 만들어집니다.

	band 1	band 2	band 3
그룹 1	A	A	A
그룹 2	B	B, D	B
그룹 3	C	C	C
그룹 4	D, E	E	D, E

유사도 계산 대상 선택

질의 문서 Z의 signature가 다음과 같다고 합시다.

Z의 signature

81

34

31

54

87

10

69

1

56

Z의 signature를 가지고 질의를 할 때도 똑같이, signature를 여러 band로 나눠서 각 band를 해시 함수에 거쳐서 그룹에 해당하는 문서를 탐색 대상으로 선택합니다.

첫 번째로 얻어지는 band는 '81, 34, 31' 이므로 이 band에서는 '그룹 1'을 선택합니다. 다음 band는 '54, 87, 10' 이므로 '그룹 3'을 선택합니다. 마지막 band는 '69, 1, 56' 이므로 '그룹 2'를 선택합니다. 선택한 그룹에는 각각 'A', 'C', 'B'가 있었으므로 유사도 탐색 대상은 문서 A, B, C가 됩니다.

만약 모든 문서를 대상으로 유사도를 계산한다면 A, B, C, D, E 문서 모두가 대상에 속하지만 locality sensitive hashing을 통해 대상을 A, B, C로 줄였습니다.

Locality Sensitive Hashing의 성능

위에서도 얘기했듯이, 이 방법은 정확한 결과보다는 빠르게 계산해서 실제 값과 유사한 값을 얻을 수 있는 방법입니다. 그렇기에 이 방법이 어느 정도의 성능을 보장하는지 확인해야 합니다. 따라서 이를 확률로 계산을 해서 알아보려 합니다. 이를 위해 문제를 다음과 같이 적겠습니다.

질의 문서 Z와의 유사도가 0.445인 문서 C가 탐색 대상에 속할 확률을 구하시오. (3점)

Z와 C의 자카드 유사도가 0.445라는 얘기는 Z와 C의 signature에서 같은 위치의 value가 동일할 확률이 0.445라는 이야기와 같습니다. 자카드 유사도를 t라고 할 때, 같은 band의 value가 모두 동일할 확률은 \(t^r\)입니다. 위의 예시에 따르면 r = 3이므로 \(t^r = 0.445^3 = 0.08812125\) 입니다.

그럼 band가 동일하지 않을 확률은 1 - 0.08812125 = 0.911878875라는 것을 알 수 있습니다. Band의 개수를 b라고 할 때, 모든 band가 동일하지 않을 확률은 \(0.911878875^b\)입니다. 위의 예시에서 b의 값은 3이므로 \(0.911979975^3 \cong 0.7582483\) 입니다. 그럼, 적어도 하나의 band가 같을 확률은 1 - 0.7582483 = 0.2417517입니다.

따라서 질의 문서 Z와의 자카드 유사도가 0.445인 문서 C가 탐색 대상에 속할 확률은 0.2417517입니다.

결과를 보면 확률 값이 낮아서 좋지 않게 보일 수도 있습니다. 그러나 여기서 알아야 할 점은, band의 개수(b)와 band의 크기(r)는 구현하는 사람이 정하는 값이라는 것입니다. 위의 결과를 변수를 사용해 일반화하면 아래와 같이 작성됩니다.

 

\(1 - (1 - t^r)^b\) (t: 자카드 유사도, r: band 크기, b: band 수)

 

r과 b의 값을 바꿔보면서 0부터 1까지의 범위에 포함되는 t에 대한 확률을 계산하면 아래와 같은 그래프가 나옵니다.

blue: r=1,b=100    orange: r=2, b=64    green: r=4, b=32    red: r=8, b=16    purple: r=16, 8    brown: r=32, b=4    pink: r=64, b=2    gray: r=100, b=1

따라서 상황에 맞는 r값과 b값의 선정이 중요합니다.

 

추가적으로 몇 가지 더 알아보겠습니다.

• 추가적인 메모리 사용량 = O(bn) (b: band 개수, n: 기존에 존재하는 문서의 수)
• 전처리 시간 = O(bn)
• 평균 탐색 문서 = O(bn / m) (m: 해시 값 범위)
• 질의 시간 = O(k * bn / m) (k: signature 크기)