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

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

• Mining of Massive Datasets" by Jure Leskovec, Anand Rajaraman, and Jeffrey Ullman
• Introduction to Information Retrieval" by Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze
• A Survey of Locality-Sensitive Hashing Schemes" by Alexandr Andoni and Piotr Indyk
• Efficient Similarity Search and Classification via Rank Aggregation" by Moses Charikar
• Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality" by Piotr Indyk and Rajeev Motwani
• MinHash Python Implementation
• LSH Tutorial and Examples