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
