Min-Hashing이란?

MinHash 알고리즘 설명

안녕하세요.

이번 시간에는 데이터 마이닝 분야에서 문서 등 자료형 간의 유사도를

빠른 시간 내에 쉽게 근사하여 비교할 수 있는

Min-Hashing 알고리즘에 대해서 이해해보도록 하겠습니다.

 

일반적으로 N개의 연속된 단어 집합인 N-gram을 토큰으로 사용하지만,

여기서는 쉬운 이해를 위하여 단어 단위를 토큰으로 가정해보겠습니다.

 

아래처럼 3개의 문서에서 각각 4개의 단어씩을 포함하고 있는 상황이라고 해보겠습니다.

아래처럼 문서 내 토큰(단어)의 포함 여부를 나타내는 TF 행렬을 생각해볼 수 있습니다.

이제, 이 예시를 기반으로 MinHash 알고리즘을 설명해보겠습니다.

 

 

유사도 예시 : Jaccard Similarity

문서 간의 유사도는 어떻게 측정할까요?

여러가지 방법이 있겠지만, 토큰이 얼마나 겹쳐서 등장하는지를 체크하는

자카드 유사도가 대표적으로 사용되는 유사도 중 하나입니다.

 

자카드 유사도의 계산 방법은 매우 간단합니다. 두 문서 A, B의 토큰들에 대해서

교집합 원소 개수 / 합집합 원소 개수로 측정하게 됩니다.

$ Similarity = \frac{n(A \cap B)}{n(A \cup B)}$

위의 예시에서 문서 간 유사도를 측정해보도록 하겠습니다.

A와 B 사이에서는 겹치는 토큰이 가장 많아 자카드 유사도가 높았지만,

B와 C 사이에서는 단 1개의 토큰만 겹치면서 자카드 유사도가 낮게 측정되었습니다.

 

자카드 유사도를 모든 문서에 대해서 정의대로 측정하는 것이 직접적인 방법이겠지만,

실제로 N-gram을 사용하게 되면, 토큰의 개수가 엄청나게 많아지게 됨으로써,

일일이 비교하는 것이 시간이 많이 소요되게 됩니다.

 

따라서, 실제 모든 토큰 간 등장 여부 비교를 전부 수행하는 것이 아닌

유사도를 근사하여 측정하는 방법이 필요하게 되고, 여기서 고안된 방법이 MinHash입니다.

 

 

MinHash 알고리즘 1단계 : 해시 함수 적용

Min-Hashing을 이용한 근사 유사도를 구하기 위해서는, 알고리즘 이름에서 짐작할 수 있듯이,

해시 함수를 적용해야합니다.

 

해시 함수의 종류는 모든 원소들이 1개씩 값에 정확히 permutation mapping될 수 있다면,

크게 제약은 없는 편 입니다.

각 토큰에 0~6까지 x라는 임의 번호를 부여한 뒤,

f1, f2라는 두 개의 간단한 예시 해시 함수를 적용한 결과는 위와 같습니다.

반응형

MinHash 알고리즘 2단계 : Hash된 최소 인덱스 값 구하기

이제 해시된 결과를 바탕으로 각 문서마다의 최소 인덱스를 구해주면 됩니다.

여기서 최소 인덱스는, 1로 등장한 토큰들 중 최소의 해시 값을 말합니다.

예를 들어, f1 해시 함수에서는 A 문서는 가장 아래의 0, 1, 2 인덱스 토큰에서는 0의 빈도였다가,

3 인덱스를 가지는 car 토큰에서 빈도 1이 등장하므로, A의 MinHash 값은 3이 됩니다.

 

B 문서는 0번 인덱스인 bus 토큰이 바로 등장하므로 0의 MinHash 값을 가지며,

C 문서는 1번 인덱스인 airplane 토큰이 MinHash 값을 결정짓습니다.

 

마찬가지로, f2 해시 함수의 Min-Hashing 결과도 위와 같이 계산됨을 이해해볼 수 있습니다.

 

 

MinHash 알고리즘 3단계 : 해시 결과로 유사도 측정

이제 여러 개의 서로 다른 해시 함수에 같은 과정을 적용하여

아래와 같은 결과를 얻었다고 가정해보겠습니다.

총 5개의 해시 함수에 적용한 결과,

A와 B는 3개의 함수에서 Min-Hashing 결과가 같았고, 이는 유사도가 3/5임을 의미합니다.

 

마찬가지로 다른 문서 사이에서도 Min-Hashing 결과가 동일한 해시 함수의 개수를 센 뒤,

적용했던 해시 함수의 전체 개수로 나누어 유사도를 측정해볼 수 있습니다.

 

해시 함수의 개수가 많아지면, 실제로 측정된 유사도는 자카드 유사도와 거의 동일해지는데,

이를 이용하여 자카드 유사도의 근사를 수행해볼 수 있습니다.

 

너무 많은 개수의 해시 함수를 사용하게되면 수행 시간의 이점은 작아지겠지만,

토큰의 개수보다 훨씬 적은 개수로도 문서 간 유사도 측정이 쉬워져 많이 사용되는 방법입니다.

 

다음 시간에는 Min-Hashing 알고리즘을 기반으로 유사한 데이터 그룹들을 찾아낼 수 있는

LSH 방법론에 대해서 살펴보도록 하겠습니다. 감사합니다.