위키득계정 ↗
기술

미니해시

미니해시기술
영문명
MinHash
추정 대상
집합의 자카드 유사도
보관 정보
여러 최소값으로 이루어진 서명
대표 활용
유사 문서와 중복 후보 탐색
미니해시는 집합의 자카드 유사도를 작은 서명으로 추정하는 확률적 방법이다. 같은 무작위 순서에서 각 집합의 최소 원소를 고르고, 여러 번 만든 서명에서 값이 일치하는 비율을 이용한다.

집합의 겹침을 수로 나타내기

자카드 유사도는 교집합 크기를 합집합 크기로 나눈 값이다. 예를 들어 A가 {가, 나, 다}, B가 {나, 다, 라}라면 공통 원소는 두 개이고 전체 서로 다른 원소는 네 개이므로 값은 1/2이다. 미니해시는 큰 집합의 원소 전체를 비교하는 대신 이 비율을 추정한다.

최소값이 같아지는 경우

합집합의 원소를 무작위로 줄 세운다고 생각하자. 그 순서에서 가장 먼저 나오는 원소가 교집합에 속하면 두 집합이 고른 첫 원소가 같아진다. 각 원소가 첫 자리에 올 가능성이 같은 이상적인 순서에서는 이 사건의 확률이 자카드 유사도와 같다.

여러 번 골라 서명 만들기

하나의 순서만 쓰면 결과는 일치하거나 불일치하는 두 경우뿐이다. 서로 독립적인 여러 순서에서 최소값을 골라 서명을 만들고 대응하는 칸의 일치 비율을 계산하면 더 안정적으로 추정할 수 있다. 서명을 늘리면 보관 공간과 비교 작업도 함께 늘어난다.

문서를 집합으로 바꿀 때

문서를 연속된 단어 묶음의 집합으로 나타내면 표현이 비슷한 문서를 찾는 데 적용할 수 있다. 그러나 어떤 단위로 묶고 무엇을 정규화하는지에 따라 결과가 달라진다. 미니해시의 높은 유사도는 선택한 특징의 겹침을 뜻하며 문장의 의미나 사실관계가 같다는 보증은 아니다.

관련 문서

자카드 유사도 / 집합 / 해시 함수 / 확률 / 블룸 필터 / 하이퍼로그로그