# Jaccard 유사도와 MinHash를 이용한 유사 중복 탐지

> Clean Markdown view of GeekNews topic #15703. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=15703](https://news.hada.io/topic?id=15703)
- GeekNews Markdown: [https://news.hada.io/topic/15703.md](https://news.hada.io/topic/15703.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2024-07-06T09:45:57+09:00
- Updated: 2024-07-06T09:45:57+09:00
- Original source: [blog.nelhage.com](https://blog.nelhage.com/post/fuzzy-dedup/)
- Points: 1
- Comments: 1

## Topic Body

##### 유사 문서 찾기: 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 구현과 같은 도구를 사용하여 쉽게 적용 가능
  - 대규모 데이터셋에서의 효율적인 중복 제거를 위해 이러한 기술을 적극 활용할 것을 권장함

## Comments



### Comment 27002

- Author: neo
- Created: 2024-07-06T09:45:57+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=40872438) 
- 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개의 피드 항목이 있음
  - 내용과 요약이 매우 유사함