MinHash란?

MinHash 알고리즘을 이해한 만큼 적어보려고 합니다.

요즘, 회사에서 사용할 봇을 제작하고 있는데요, 약간의 자연어 처리 기능을 넣어보려고 했습니다. 어떻게 하면 효율적으로 처리가 가능할까 하다가 MinHash 라는 Collaborative Filtering에서 사용하는 알고리즘을 찾게 되었습니다. 활용 할 수 있을 것 같아서 일단 뜯어보기로 했습니다.

일단은 해결하고자 하는 문제를 알아야 합니다. MinHash는 두 집합의 유사도를 쉽게 구하기 위해서 만들어진 알고리즘입니다. 그 중, Jaccard Similarity를 사용합니다. 이 공식을 쉽게 옮겨보면 다음과 같습니다.

예를들어 봅시다. A, B가 다음과 같습니다.

그러면 Jaccard Similarity를 통한 유사도는 다음과 같이 계산됩니다.

만약 굉장히 큰 두 집합이 들어온다고 하면 어떻게 될까요? 단순히 생각해도 집합이 커질 수록 시간이 오래 걸릴 것 같습니다. Jaccard Similarity의 시간 복잡도(Time Complexity)는 다음과 같습니다.

union연산과 intersect 연산때문에 그렇습니다. 그렇다면 이 집합을 좀더 단순화 시켜서 연산할 수 있는 방법이 없을까하고 고안된 방식이 MinHash입니다.

동작방식은 간단합니다. 각 집합에 대한 해시를 생성합니다. 여기서 해시는 충돌이 잘나는 해시 함수를 사용합니다. 그리고 그리고 생성된 해시중에서 가장 작은 값을 대표 해시로 사용합니다. 그리고 이런식으로 여러개의 해시를 만듭니다. 그리고 그 해시간의 Jaccard Similarity를 구하면 됩니다. 해시를 구하는 함수는 \(O(1)\)이고, n개의 해시를 만드는 작업은 \(O(n)\)의 작업 시간을 필요로 합니다.

이러한 방식을 통해서 될까 의심이 되지만, 충분히 해시를 생성하면 원래 집합의 유사도 값에 근사한다고 합니다. 자세한건 참고링크를 들여다 보시면 됩니다.

어떻게 만드는지 예를 들어봅시다. (사실 이걸 다루려고 쓴 글입니다…)

위와 같은 집합이 주어졌다고 합시다. 테이블에 나타내면 다음과 같이 나타낼 수 있습니다.

여기서 \(row\)를 가지고 Signature를 생성하려고 합니다. Signature를 1개 만드려면 해시 함수가 1개, 두개를 만드려면 해시 함수도 2개, n개를 만들 때는 해시함수도 n개를 필요로 합니다.

여기선 2개로 하려고 합니다. 해시 함수도 두개 선언합니다. 대충 만들어도 됩니다.

위에서 \(x\)값은 \(row\)를 넣어줍니다. 그럼 다음과 같이 정리 할 수 있습니다.

위 테이블에서, A는 {0, 3, 4}에서 \(h_1(x)\)로는 {1, 4, 5}를 가집니다. 여기서 가장 작은 값 1을 Signature로 사용합니다. 즉 MinHash 함수는 다음과 같이 나타낼 수 있습니다.

그러면 \(h_1(x)\)와 \(h_2(x)\)에 대응하는 MinHash는 다음과 같이 나타낼 수 있습니다.

이제 이 값을 통해서 Jaccard 함수를 사용하면 그전 비용보다 더 적은 비용을 통해서 유사도를 비교할 수 있게 됩니다.

A에 대해서 B, C, D의 유사도를 Jaccard Similarity로 구하게 되면 다음과 같습니다.

MinHash를 통해서 구한 값으로 Jaccard Similarity를 구하게 되면 다음과 같습니다.

조금 다르긴 하지만 위의 값과 비슷한 느낌입니다. 만약에 A와 유사한 집합을 순서대로 뽑는다고 하면 결과에는 영향이 없습니다. 위에서도 한번 이야기 했지만, Signature의 수를 늘리면 실제 값과 상당히 유사해진다고 합니다.

수학과 친하지 않아서 많이 힘들었습니다. 그래서 개발자답게 제가 좋아하는 PHP로 짜본 소스. 좀더 한눈에 들어오네요.

<?php
function minHash(array $set):array
{
    $mod = 7; // mod 7 에 해당하는 부분
    $coeffA = [2, 3]; // 2x, 3x 에 해당하는 부분
    $coeffB = [1, 5]; // +1, +5 에 해당하는 부분

    $signatures = [];
    foreach (range(0, 1) as $index) { // hash 함수 2개
        $minHash = $mod + 1;
        foreach ($set as $element) {
            $minHash = min(
                ($coeffA[$index] * $element + $coeffB[$index]) % $mod,
                $minHash
            );
        }
        $signatures[] = $minHash;
    }
    return $signatures;
}

2023.02.14, 오타 수정 기념, 타입스크립트 코드 :-)

type Hash = (x: number) => number;

function minHash(items: number[], hash: Hash): number {
  let minHash = Infinity;
  for (const item of items) {
    minHash = Math.min(hash(item), minHash);
  }
  return minHash;
}

const rows = [
  [0, 3, 4], // row A
  [1, 2, 5], // row B
  [0, 1, 2, 3, 5], // row C
  [1, 3], // row D
];

const hashes: Hash[] = [
  (x: number) => (x + 1) % 7, // h_1(x)
  (x: number) => (x * 3 + 5) % 7, // h_2(x)
];

for (const [hashIndex, hash] of hashes.entries()) {
  const mh = rows.map((row) => minHash(row, hash));
  console.log(`m_${hashIndex + 1}(S)`, mh);
}

/*
Output:
m_1(S) [ 1, 2, 1, 2 ]
m_2(S) [ 0, 1, 0, 0 ]
 */

참고링크

• 하용호, 실시간 추천엔진을 노트북에서 돌게 만들어보자
• seongsu’s page - MinHash
• hongjun-7.blogspat.kr - Minhash for Jaccard Similarity
• Minhash.pdf