Minhashing

해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.

앞선 포스팅에서는 문서를 shingle 집합의 형태로 변환하였고,

집합 간 유사도를 구하는 측도인 Jaccard Similarity 에 대해 다뤘습니다.

shingle 집합으로 변환한 문서들에 대해

하나 하나 유사도를 구하는 것이 정확한 방법이지만, 이 방법은 너무나도 많은 연산을 필요로 합니다.

문서가 백만개 인 경우, 조 단위의 비교작업이 이뤄저야 하고,

하나의 문서 비교작업도, 9-shingle 인 경우 $27^9$ 의 비교연산이 필요합니다.

실질적으로 계산이 불가능합니다.

처리할 데이터의 규모를 줄이는 것이 필요하였고,

그래서 고안된 것이 Minhashing 입니다.

이번 포스팅에서는 Minhashing 이 어떻게 동작하는지 와

Minhash의 결과물인 Signature 가 왜 자카드 유사도를 대체할 수 있는지 증명하겠습니다.

Minhashing

Minhash 함수 $h(C)$ 란 칼럼 $C$ 가 1을 가진 첫번째 순열의 수 입니다.

이 해시 함수가 각 칼럼별로 만들어낸 결과값을 Signature 라고 합니다.

순열이 어떻게 구성되느냐에 따라 다른 해시 함수가 되는 것이고,

여러가지 순열들로 수행한 해시 함수의 결과들을 모아

Signature Matrix 를 구성합니다.

예시를 통해 살펴보겠습니다.

그림 출처

$h(C)$ 는 첫번째 순열의 수 이지만, 이 예시에서는 이해하기 쉽도록 문자를 사용하였습니다.

(위 행렬과 같이, 실제 행렬에서도 entry는 0과 1로 표현을 합니다.

‘a’,’b’ 와 같이 실제 데이터를 entry 로 사용하지 않는 이유는,

행렬이 sparse 하기 때문입니다. 0과 1로 entry 를 나타내 공간을 절약합니다. )

여기서 각 집합은 다음과 같이 element 를 갖습니다.

$S_1 = { a,d },S_2 = { c },S_3 = { b,d,e},S_4 = { a,c,d },$

여기서 $a,b,c,d,e$ 의 순열을 순서를 섞어 봅시다.

여러 순열 중 $b,e,a,d,c$ 순서의 순열을 선택하였고, 다음 그림과 같습니다.

이 $b,e,a,d,c$ 순열에서 minhash 함수가 어떻게 작동하는지 봅시다.

S1의 경우 3번째 행에서 1을 갖게 됩니다.

앞선 정의 처럼 ‘1을 가진 첫번째 순열’ 은 a 가 됩니다.

그러므로 $b,e,a,d,c$ 순열에서 $h(S_1) = a$ 가 됩니다.

이런식으로 $h(S_2) = c$ , $h(S_3) = b$ , $h(S_4) = a$ 를 얻을 수 있습니다.

Signature matrix

$b,e,a,d,c$ 는 만들 수 있는 여러 순열 중 하나이고,

이와같은 순열을 여러개 만들어서 minhashing 을 수행합니다.

$a,c,d,b,e$ , $e,a,d,c,b$ 와 같은 순열들을 사용하여 signature 를 생성하고

그 결과들을 행으로 쌓은 것을 signature matrix 라 합니다.

이 signature matrix 는 기존 행렬보다 행이 더 작게 구성합니다.

이렇게 만들어진 signature matrix는

더 작은 차원으로도 기존 행렬의 특성을 나타냅니다.(represent)

실제 작업에서는 이 element 대신 숫자를 사용할 뿐입니다.

직관적으로 보았을 때,

이렇게 만들어진 signature matrix 가 기존 행렬의 모든 특성을 다 반영하지 못하는 것으로 보입니다.

첫번째 1이되는 순열만 사용하므로, 그 이후 정보는 하나의 signature 에 반영을 할 수 없습니다.

모든 특성을 완벽히 반영시키기 위해서는 기존 행의 숫자만큼의 순열이 필요할 것이고, 이렇게 되면 시그니처 행렬의 크기와 기존행의 크기가 동일하게 됩니다.

이 minhashing 작업은 기존 sparse 한 행렬을 행을 기반으로 작게 압축하는 작업입니다.

기존 행렬을 무손실 압축하는 것은 아니지만, 행의 확률적 속성을 사용하여

집합(열) 간 유사도 비교를 위한 특성을 어느정도 유지하면서 압축하는 작업입니다.

minhashing 을 거친 시그니처 행렬에서,

두 시그니처의 유사도의 기대값은 그 시그니처에 해당하는 집합(열)의 자카드 유사도와 동일합니다.

즉, 그림에서

그림@@

입력 행렬의 첫번째, 세번째 열의 자카드 유사도는

시그니처 행렬 M 의 첫번재, 세번째 열의 유사도를 구해서 찾을 수 있습니다.

기대값이므로 실제 유사도 값과는 차이가 있을 수 있습니다.

그러나 해시함수의 수가 많을 수록 기대값에 수렴하므로, 오차가 줄어듭니다.

이게 왜 성립하는지에 대해 증명해보겠습니다.

Minhashing and Jaccard Similarity

앞서 말은 다시 정리하자면

행의 무작위 순열에 대한 minhash 함수가 두 집합(열) 에 대해 동일한 값을 생성 할 확률은 해당 집합의 자카드 유사도와 같습니다.

이를 증명하기에 앞서,

단순하게 집합 $S_1$,$S_2$ 만 있다고 가정하고,

행을 3개의 타입으로 분류해 봅시다.

1. 타입 X : 집합이 둘 다 1 인 행
2. 타입 Y : 집합 중 하나는 1이고 하나는 0인 행
3. 타입 Z : 집합이 둘 다 0 인 행

그림과 같이 타입을 분류할 수 있습니다.

그림@@

행렬이 sparse 하기 때문에 대부분의 행은 Z 타입 입니다.

그러나 X와 Y 의 숫자 비율은 SIM(S1,S2) 와 h(S1) = h(S2) 일 확률 둘 다로 결정됩니다. X 타입인 행이 x개 있고, Y 타입인 행이 y개 있다고 합시다.

그러면 $SIM(S_1,S_2) = \frac{x}{(x+y)}$ 가 됩니다.

(x 는 $S_1\cap S_2$ 의 크기이고 x+y 는 $S_1\cup S_2$ 의 크기입니다.)

이제 해시 h(S1) = h(S2) 를 고려해봅시다.

행이 무작위로 나열되었다고 가정해봅시다. 그리고 위에서부터 진행을 합니다. 여기서 Y 타입의 행을 만나기 전에 X 타입의 행을 만날 확률은 x/(x+y) 가 됩니다. 만약 Z 이외에 만나는 첫번째 행이 X타입의 행이면, 확실하게 h(S1) = h(S2) 이 됩니다. 반면에, Z이외에 첫번째 행이 Y타입 행이라면, 1을 가진 집합은 그것의 행을 민해시 값으로 가져옵니다. 그러나 해당 행에 0이있는 세트는 반드시 순열 목록 아래의 일부 행을 가져옵니다. 그래서 Y타입 행을 처음으로 만나는 경우 $h(S_1) \neq h(S_2)$ 가 됩니다. 결론적으로, h(S1) = h(S2) 는 x/(x+y) 이고 이는 S1, S2의 자카드 유사도 입니다.

이렇게 시그니처 행렬을 사용해서 집합 간 유사도를 파악할 수 있는 이유에 대해 살펴보았습니다.

이 minhashing 은 위의 방식 그대로 사용하기에는 어려움이 있습니다.

다음 포스팅에서는 실제 시그니처 행렬을 어떻게 구하는지에 대해 다뤄보겠습니다.