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

대량 데이터에 대한 유사도 측정의 대안, MinHash & LSH
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

Read more

OLS 기반 인과추론 시 오차항 관련 체크 필요 가정

OLS 기반 인과추론 시 오차항 관련 체크 필요 가정

배경 * 아래 글을 DANBI에서 보다가 더 알아보게 되었습니다. OLS를 떠받치는 몇 개의 기둥이 있는데 그중 실용적으로 가장 중요한 것이 일치성(consistency)다. 쉽게 말해서 OLS를 통해 도출된 추정량이 있을 때 샘플사이즈가 커지면서 이 값이 참 값으로 접근한다는 것이다. 일치성이 충족되면 우리는 적당하게 큰 표본에 대해서 추정치가 좋은 속성을 지니고 있다고

인공지능이 문제가 아니라 결국 사람이 문제가 될 것입니다.

인공지능이 문제가 아니라 결국 사람이 문제가 될 것입니다.

사람들이 AI가 필요하다고 생각하는 시점 저 판사를 얼른 AI로 교체해야 한다. 유튜브에서 뉴스를 보다 보면 정말 많이 보이는 덧글입니다. 이러한 내용의 덧글이 달릴 때마다, 정말 많은 사람들이 공감을 표하곤 합니다. 왜 이렇게 사람들은 이러한 주장에 공감을 표하는 것일까? AI는 시킨대로 하기 때문에 공정하다는 인식 여러 이유가 있겠지만, 사람들은 아마 AI가

BG/NBD 모델은 고객 생애가치를 추정하는데 사용되는 확률 모델입니다.

BG/NBD 모델은 고객 생애가치를 추정하는데 사용되는 확률 모델입니다.

1. BG/NBD 모델이란? * BG/NBD(Beta-Geometric/Negative Binomial Distribution) 모델은 **고객의 생애 가치(Customer Lifetime Value, CLV)**를 추정하는 데 사용되는 확률적 모델입니다. * 특히 고객이 반복 구매를 할지, 아니면 더 이상 활동하지 않을지를 추정하는 데 유용합니다. 이 모델은 고객의 구매 행태를 두 가지 중요한 개념으로 나눕니다: * 고객은 활성(active)

다중공선성은 잘못된 인과추론 결과를 만들어낼 수 있습니다.

다중공선성은 잘못된 인과추론 결과를 만들어낼 수 있습니다.

다중공선성(Multi Collinearity) * **Multi-Collinearity(다중공선성)**는 독립 변수들 간의 강한 상관관계가 존재할 때 발생합니다. 즉, 한 독립 변수가 다른 독립 변수에 의해 설명될 수 있을 정도로 상관관계가 높은 상황을 의미합니다. * 이 문제는 주로 회귀 분석에서 나타나며, 변수들 간의 관계를 해석하는 데 있어 큰 장애물이 될 수 있습니다. * 일반적인 회귀식을 $Y=