Min-Hashing

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

---

왜 필요한가?

문서함에 수많은 문서가 있고, 각 문서에는 많은 단어들이 적혀있다고 가정합시다. 이 문서함에서 우리가 가지고 있는 하나의 문서와 가장 유사도가 높은 문서를 찾아봅시다.

이때 가장 먼저 떠오르는 방법은 각 문서와 하나씩 유사도를 계산하는 방법일 것입니다. 이 포스트에서 유사도 계산할 때 자카드 유사도를 사용합니다. 자카드 유사도의 계산 식은 아래와 같습니다.

source: https://en.wikipedia.org/wiki/Jaccard_index

문서함에 있는 문서의 개수를 d, 문서에 적힌 평균 단어 개수를 n이라고 하면, 자카드 유사도 계산의 시간 복잡도가 O(N)이므로 총 O(nd)의 시간 복잡도만큼 걸립니다. 문서의 수가 기하급수적으로 커지면 시간 복잡도 또한 기하급수적으로 커질 것입니다.

따라서 빠르게 문서 간의 유사도를 계산하기 위해 2가지를 고려할 수 있습니다.

• 모든 문서를 비교하는 것이 아니라, 일부의 문서만 비교
• 유사도 계산을 더욱 빠르게

Min-Hashing은 자카드 유사도 계산을 더 빠르게 할 수 있는 알고리즘입니다.

Min-Hashing

Min-Hashing 알고리즘의 중요 포인트는 계산 결과가 100% 정확하지 않다는 것입니다.

알고리즘에서 큰 집합을 작은 벡터(signature)로 변환해 벡터들 간의 유사도를 계산합니다. 계산의 양을 줄여 속도를 높일 수 있다는 장점을 지니고 있습니다.

확률의 시선으로 본 자카드 유사도

임의의 두 집합 1, 2를 각각 아래와 같이 정의하겠습니다.

• 1 = {'A', 'B', 'D', 'E'}
• 2 = {'B', 'C', 'E', 'F'}
• \((1 ∪ 2)^c\) = {'G', 'H', 'I'}

그리고 집합의 영역을 다음과 같이 표기하겠습니다.

• a: (집합 1) ∩ (집합 2)
• b: (집합 1) - (집합 2)
• c: (집합 2) - (집합 1)

위와 같이 정의, 표기할 때 자카드 유사도를 확률의 관점으로 다음과 같이 생각해 볼 수 있습니다.

영역 a, b, c에 포함된 원소 중에서 a 영역의 원소를 뽑을 확률을 자카드 유사도와 동일하게 볼 수 있다.

이 관점으로 자카드 유사도의 계산 과정을 살펴봅시다.

먼저, 위의 집합 1, 2를 아래와 같이 bit vector로 표기할 수 있습니다.

	A	B	C	D	E	F	G	H	I
집합 1	1	1	0	1	1	0	0	0	0
집합 2	0	1	1	0	1	1	0	0	0

그리고 원소를 뽑을 순서를 랜덤 하게 정해봅시다. 랜덤 하게 선택한 순서까지 작성하면 아래의 표와 같습니다.

순서	1	9	2	8	3	7	4	6	5
원소	A	B	C	D	E	F	G	H	I
집합 1	1	1	0	1	1	0	0	0	0
집합 2	0	1	1	0	1	1	0	0	0

이제 정해진 순서대로 원소를 뽑는데, 뽑힌 원소가 a, b, c 영역 중에 한 곳에 속할 때까지 반복해서 뽑습니다. 이번 순서에서는 첫 순서가 되자마자 원소 'A'가 b 영역에 속하므로 뽑는 과정이 끝납니다.

이러한 과정을 k번 반복해서 (a 영역에서 뽑은 원소 수) / k로 계산하면 자카드 유사도와 유사한 값을 얻을 수 있습니다.

만약 k = 4일 때, 순서를 다음과 같이 랜덤 하게 결정했다고 합시다.

순서 4	1	3	5	7	9	2	4	6	8
순서 3	5	1	2	3	7	8	9	6	4
순서 2	9	5	3	2	1	7	4	8	6
순서 1	1	9	2	8	3	7	4	6	5
원소	A	B	C	D	E	F	G	H	I
집합 1	1	1	0	1	1	0	0	0	0
집합 2	0	1	1	0	1	1	0	0	0

순서 1부터 4까지 a 영역의 원소를 뽑은 횟수는 각각 0, 1, 1, 0 이므로 계산 식에 따라 2/4 = 0.5로 자카드 유사도를 유추할 수 있습니다. 실제 자카드 유사도를 계산하면, 2/6 = 0.33입니다. 정확히 값이 같지 않지만 얼추 유사하게 자카드 유사도를 계산했음을 볼 수 있습니다.

k 값을 키운다면 더 많은 시행을 하기에 더 근사한 값을 얻을 수 있지만, 그만큼 연산 속도가 느려지므로 k 값의 변화가 정확도와 속도 사이의 trade-off 관계에 영향을 미칩니다. 따라서 k 값은 상황에 따라 적절히 설정해야 하는 값입니다.

Min-Hashing 적용하기

위의 과정에서 min-hashing을 적용한다는 것은 각 집합에 대해 signature를 생성해서 유사도를 계산한다는 것입니다. 각 집합의 signature를 다음과 같이 만들 수 있습니다.

1. k 만큼의 크기를 가지는 vector 준비

먼저 signature를 생성, 기록하기 위해 k 만큼의 크기를 가지는 signature를 준비합니다. 여기서는 k = 4일 때를 가정하겠습니다.

	순서 1	순서 2	순서 3	순서 4
집합 1의 signature
집합 2의 signature

2. 영역에 속할 때의 순서를 기록

랜덤 하게 고른 순서대로 원소를 뽑을 때, a, b, c 영역 중 해당 영역에 속한 원소를 뽑게 되면 그때의 순서를 signature에 기록합니다. 예를 들어, 순서 1에서 원소들을 뽑아봅시다. 1번 순서에서 원소 'A'는 집합 1에 속하고, b 영역에 속합니다. 2번 순서에서 원소 'C'는 집합 2에 속하고, c 영역에 속합니다. 따라서 signature에 아래와 같이 기록합니다.

	순서 1	순서 2	순서 3	순서 4
집합 1의 signature	1
집합 2의 signature	2

위의 방식대로 순서 4까지 시행했을 때 signature는 다음과 같이 기록됩니다.

	순서 1	순서 2	순서 3	순서 4
집합 1의 signature	1	1	1	1
집합 2의 signature	2	1	1	2

순서 2, 3일 때에 signature 값이 같으므로 자카드 유사도를 2/4 = 0.5로 계산할 수 있습니다.

랜덤 한 순서 선정 과정 제거

임의로 순서를 정하는 과정도 사실 시간이 오래 걸리는 작업입니다. 그렇기에 더 빠르게 하기 위해 랜덤 하게 순서를 고르는 과정 대신 각 순서마다 다른 해시 함수를 사용합니다. 예를 들어 해시 함수를 다음과 같이 정의해서 적용할 수 있습니다.

• 순서 1에 적용할 해시 함수(해시 1): x mod 13
• 순서 2에 적용할 해시 함수(해시 2): (2x + 10) mod 13
• 순서 3에 적용할 해시 함수(해시 3): (5x + 8) mod 13
• 순서 4에 적용할 해시 함수(해시 4): (7x + 3) mod 10

'A'부터 'I'까지의 원소들을 0부터 순서대로 숫자를 부여한다고 했을 때, 각 원소마다 해시 함수를 적용하면 다음과 같이 볼 수 있습니다.

해시 4	3	10	4	11	5	12	6	0	7
해시 3	8	0	5	10	2	6	12	3	9
해시 2	10	12	1	3	5	7	9	11	0
해시 1	0	1	2	3	4	5	6	7	8
원소	A	B	C	D	E	F	G	H	I
집합 1	1	1	0	1	1	0	0	0	0
집합 2	0	1	1	0	1	1	0	0	0

이제 각 순서에 해당하는 해시 함숫값들 중 가장 작은 값부터 원소를 뽑습니다. 이후의 signature 작성 방식은 전과 동일하게 영역에 속할 때의 해시 값을 작성하면 됩니다. 따라서 signature는 다음과 같이 작성됩니다. 아래의 signature를 바탕으로 자카드 유사도를 계산하면 1/4 = 0.25로 계산됩니다.

	해시 1	해시 2	해시 3	해시 4
집합 1의 signature	0	3	0	3
집합 2의 signature	1	1	0	4