Data

대량 데이터에 대한 유사도 측정의 대안, MinHash & LSH

Bongho, Lee

2024년 5월 29일 — 3 min read

Photo by Priscilla Du Preez 🇨🇦 / Unsplash

MinHash & LSH are

MinHash는 두 집합간의 유사도를 측정하는 기술로 각 집합을 기존 데이터보다 적은 형태의 Signature로 변환하여 연산비용을 줄여준다
LSH는 Locality Sensitivity Hashing의 약자로, 해싱(Hashing()을 이용, 높은 확률도 유사한 아이템을 같은 버킷(Bucket)에 분류하는데 이용된다.

Motivation

대량 데이터셋에서 유사도를 비교하는 것은 연산비용이 크게 들 수 있다. 특히 비정형 데이터의 경우 고차원 데이터이기 때문에 모든 쌍을 비교하는 거의 불가능에 가까울 정도로 비현실적이다. MinHash와 LSH는 연산비용 최적화에 중점을 두어 유사도 측정을 수행한다.

Pros & Cons

Pros

계산효율성 → 빠른 검색을 가능하게 도와준다
확장성 → 데이터의 차원 또는 크기를 늘릴 수 있다.
간단성 → 구현이 비교적 직관적이어서 다양한 곳에 적용 가능하다.

Cons

결국 추정값이다. → 정확하지 않을 수 있다.
튜닝이 필요하다. → 최적의 성능을 위해서는 버킷 크기라던가, 파라미터에 대한 튜닝이 요구된다.
메모리 소모가 클 수 있다. → 해시 테이블을 상시 운용해야 하는 부분은 높은 메모리 소모량으로 직결된다.

Alternative

KNN: 가장 간단하면서 일반적인 방식이지만, 대규모 데이터에는 비효율적이다.
Vector Search Engine: Faiss,Annoy
Tree 기반 모델: KD-Tree, Ball Tree등 사용 가능

Sample Code


import hashlib
import random
import numpy as np
from collections import defaultdict

class MinHash:
    def __init__(self, num_hashes):
        self.num_hashes = num_hashes
        self.max_hash = (1 << 32) - 1
        self.hash_funcs = [self._make_hash_func(i) for i in range(num_hashes)]

    def _make_hash_func(self, seed):
        def hash_func(x):
            return hashlib.md5((str(seed) + x).encode('utf8')).hexdigest()
        return hash_func

    def _min_hash(self, s):
        return [min([int(h(x), 16) for x in s]) for h in self.hash_funcs]

    def compute_signature(self, doc):
        return self._min_hash(doc)

class LSH:
    def __init__(self, num_hashes, bands):
        self.num_hashes = num_hashes
        self.bands = bands
        self.rows = num_hashes // bands
        self.buckets = defaultdict(list)

    def _hash_band(self, band):
        return hashlib.md5(str(band).encode('utf8')).hexdigest()

    def add(self, doc_id, signature):
        for i in range(self.bands):
            band = signature[i * self.rows:(i + 1) * self.rows]
            bucket = self._hash_band(tuple(band))
            self.buckets[bucket].append(doc_id)

    def query(self, signature):
        results = set()
        for i in range(self.bands):
            band = signature[i * self.rows:(i + 1) * self.rows]
            bucket = self._hash_band(tuple(band))
            results.update(self.buckets[bucket])
        return results

# 문서 예시
documents = {
    "doc1": {"apple", "banana", "cherry"},
    "doc2": {"banana", "cherry", "durian"},
    "doc3": {"apple", "cherry", "elderberry"},
    "doc4": {"fig", "grape", "honeydew"}
}

# MinHash 서명 생성
num_hashes = 100
minhash = MinHash(num_hashes)
signatures = {doc_id: minhash.compute_signature(doc) for doc_id, doc in documents.items()}

# LSH를 사용한 문서 유사성 검색
bands = 20
lsh = LSH(num_hashes, bands)
for doc_id, sig in signatures.items():
    lsh.add(doc_id, sig)

# 특정 문서와 유사한 문서 찾기
query_doc_id = "doc1"
query_signature = signatures[query_doc_id]
similar_docs = lsh.query(query_signature)

print(f"'{query_doc_id}'와 유사한 문서들: {similar_docs}")

References

[책] 생각하는 기계 - ‘황의 분노’와 OIALO, 한 엔지니어의 눈으로 본 리더의 두 얼굴

처음 “생각하는 기계“라는 제목을 보았을 때, 젠슨황을 일컫는 말인 줄알았다. 보통은 유명할지라도 자서전을 읽는 것 자체를 그리 좋아하지는 않는 편이다. 그런데 누군가 이 책에 대해 평하길 “AI의 역사를 지근거리에서 볼 수 있다”라고 한 것을 보았다. 그래서 읽게 되었다. AI의 거대한 흐름을 기술의 관점으로는 지속해서 보고 있지만 구체적으로 왜

[책]Reshuffle: Who wins when AI restacks the knowledge economy

원래는 Amazon에 가서 Personal Knowledge Managment에 관한 책을 사려고 했다. Sketch Your Mind라는 책이었는데, 그 때 이 책 “Reshuffle”을 발견하였다. AI가 어떻게 Knowledge Economy를 흔들 것가? 라는 부제를 훑어보면서 저자가 쓴 다른 책을 보게 되었는데 거기에 내가 좋아했던 책을쓴 저자라는 것을 알게 되었다. 그래서 크게 고민하지 않고 구매를 하고

[책]올라운드투자, 누군가의 투자일기

“올라운드 투자”라는 제목을 보았을 때는, “올라운드 플레이어”가 생각이 났다. “올라운드”라는 표현을 오랜만에 들어본 까닭이었다. 그럼에도 불구하고 이 책을 고른 것은 저자가 그간 보여준 컨텐츠에 대한 신뢰가 있던 까닭이었다. 컨텐츠를 다양하게 보는 편이지만 깊이가 아주 있지는 않았다. 여기서 깊이라 함은 기존 전문적인 정량적 분석의 내용의 수준을 말하는 것이다.

내가 놓치고 있던 미래, 먼저 온 미래를 읽고

장강명 작가의 책은, 유학시절 읽고 처음이었다. 유학시절 "한국이 싫어서"라는 책은 동기부여가 상당히 되는 책이었다. 한국을 떠나 새로운 정채성을 학생으로서 Build up 해나가고 있던 상황에서 이 책은 제목부터 꽤 솔깃하였다. 물론 결말이 기억날 정도로 인상깊은 책은 아니었지만 말이다. 그렇게 시간이 흘러 장강명 작가의 책은 더 이상 읽지 않던