▲

GN⁺: Jaccard 유사도와 MinHash를 이용한 유사 중복 탐지

 (blog.nelhage.com)
1P by neo 2달전 | favorite | 댓글 1개

유사 문서 찾기: Jaccard 유사도와 MinHash

  • 문제 정의
    • 대규모 문서 컬렉션에서 유사한 문서를 식별하는 방법에 대해 논의함
    • 예를 들어, 웹 크롤링을 통해 동일한 페이지를 여러 번 가져왔을 때 메타데이터의 약간의 차이 또는 작은 편집 후의 여러 버전을 가질 수 있음
    • 이 글에서는 Jaccard 유사도와 MinHash를 사용한 근사 중복 제거 방법을 탐구함

유사도

  • 유사도 정의
    • 두 문서 간의 유사도를 정의하고, 유사도 값이 특정 임계값 이상인 쌍을 찾는 방법
    • 유사도 함수 S:U×U→[0,1]을 정의하고, S(A,B)≥S_crit인 경우 두 문서를 근사 중복으로 간주함

Jaccard 유사도

  • Jaccard 유사도
    • 두 유한 집합의 유사도를 그들의 교집합과 합집합의 비율로 나타내는 함수
    • J(A,B)=∣A∩B∣/∣A∪B∣
    • 두 집합이 유사할수록 대부분 동일한 요소를 가짐

Jaccard 유사도 확장

  • 확장 방법
    • 문서를 특징 집합으로 변환하고, 높은 Jaccard 유사도를 가진 집합을 검색함
    • 작은 코퍼스에서는 직접 적용 가능하지만, 큰 코퍼스에서는 비효율적임

Jaccard 유사도 근사

  • MinHash 서명
    • Jaccard 유사도를 근사하기 위해 샘플링을 사용
    • 각 문서에 대해 고정 크기의 서명을 사전 계산하여 효율적으로 유사도를 추정함

더 많은 해시 함수 사용

  • 다중 해시 함수
    • 여러 해시 함수를 사용하여 각 문서를 k-요소 벡터로 요약
    • 두 서명 간의 일치하는 해시 수를 세어 Jaccard 유사도를 근사함

모든 문서 비교

  • 문서 그룹화
    • 문서를 그룹화하여 유사한 문서만 비교
    • MinHash 값을 그룹화 키로 사용하여 효율적으로 근사 중복을 찾음

더 유연한 중복 탐지

  • 다중 키 사용
    • 여러 키를 사용하여 문서를 여러 버킷에 배치하고, 각 버킷 내에서 비교
    • 더 낮은 유사도 값에서도 중복을 탐지할 수 있음

결론

  • 결론
    • MinHash와 같은 알고리즘을 통해 효율적으로 유사 문서를 찾을 수 있음
    • 이 글이 더 많은 엔지니어들에게 이러한 알고리즘을 소개하고 이해를 돕기를 바람

부록: 문서를 집합으로 표현

  • n-그램

    • 문서를 n-그램으로 표현하여 비교
    • n 값에 따라 비교의 정밀도가 달라짐

  • 단어 분할

    • 문서를 단어 또는 토큰으로 분할하여 특징으로 사용
    • 더 정교한 토크나이저를 사용할 수도 있음

GN⁺의 의견

  • 유사 문서 탐지의 중요성

    • 대규모 데이터셋에서 중복을 제거하는 것은 데이터 품질을 높이고 저장 공간을 절약하는 데 중요함
    • 특히 웹 크롤링이나 데이터 수집 과정에서 필수적임

  • MinHash의 장점

    • MinHash는 효율적이고 확장 가능한 방식으로 유사 문서를 탐지할 수 있음
    • 기존의 해시 기반 중복 제거 방법보다 더 유연함

  • 다른 유사한 기술

    • HyperLogLog와 같은 다른 스케치 알고리즘도 유사한 문제를 해결하는 데 사용될 수 있음
    • 두 알고리즘을 결합하여 더 강력한 솔루션을 만들 수 있음

  • 실제 적용 시 고려사항

    • 해시 함수 선택의 중요성: 해시 함수의 선택이 결과의 정확도에 큰 영향을 미침
    • 성능과 정확도 간의 균형: 더 많은 해시 함수를 사용할수록 정확도가 높아지지만, 성능 비용이 증가함

  • 추천 기술

    • Spark의 MinHashLSH 구현과 같은 도구를 사용하여 쉽게 적용 가능
    • 대규모 데이터셋에서의 효율적인 중복 제거를 위해 이러한 기술을 적극 활용할 것을 권장함
▲
neo 2달전  [-]
Hacker News 의견

  • Jaccard 유사도와 F1 점수는 퍼지 집합에서도 동일하게 사용할 수 있음

    • 퍼지 집합에서는 적절한 T-Norm/T-Conorm 쌍을 선택해야 함
    • 이 방법은 의료 이미지 분할 검증에 유용함
    • 대부분의 사람들은 0.5로 임계값을 설정해 이진 집합을 사용함
    • 이는 검증 연산자의 정밀도를 크게 감소시킴

  • Python으로 프랑스 정부 데이터베이스의 중복 제거를 구현한 경험이 있음

    • 현재는 datasketch를 추천함
    • rensa라는 새로운 도구도 있음
    • rensa는 Rust로 작성된 더 빠른 버전임

  • Google 초기에 중복 제거를 위해 개발된 기술임

    • Jeffrey Ullman의 "Mining Massive Datasets"에서 자세히 설명됨
    • 이 기술은 AltaVista에서 처음 개발됨

  • Minhash 시스템을 구현한 경험이 있음

    • 큰 행렬의 부분 행렬의 (유사) 역행렬을 찾는 문제를 해결함
    • Minhashing을 사용해 유사한 행렬을 찾음
    • 다중 해상도 해시를 사용해 검색 선택성을 조정함

  • Minhash와 그 변형을 이해하기 어려워 시각화 도구를 개발 중임

    • Jaccard 유사도 계산을 포함할 예정임

  • 코드 예제를 통해 기술을 이해하는 것이 더 쉬움

    • Google의 Douglas Eck로부터 이 기술을 배움
    • 노래 클러스터링에 사용됨

  • NVIDIA 팀이 GPU 가속 퍼지 중복 제거 알고리즘을 출시함

    • GitHub 저장소와 문서 제공
    • Python 예제도 포함됨

  • 해싱 또는 작은 신경망과 벡터 검색 엔진을 결합한 중복 제거 전략이 일반적임

    • Google의 RETSim 모델과 USearch 엔진 프로젝트가 있음

  • 저자에게 오타를 지적함

    • S(A,B) 대신 S(A,C)여야 함

  • Postgres에서 유사한 뉴스 항목을 하나로 줄이는 문제를 해결 중임

    • 600,000개의 피드 항목이 있음
    • 내용과 요약이 매우 유사함
답변달기