자카드 지수(Jaccard index)

철수와 영희의 장바구니를 비교해 봅시다. 노란 원이 철수의 장바구니 A, 파란 원이 영희의 장바구니 B입니다. 물건을 끌어 원 안팎으로 옮겨 보세요. 철수는 개, 영희는 개를 담았고, 둘 다 담은 것은 개, 둘 중 하나라도 담은 것은 개입니다.

자카드 지수는 교집합의 크기를 합집합의 크기로 나눈 값, 지금 $J =$ 입니다. 공통점이 없으면 0, 같은 집합이면 1입니다. 교집합만 세지 않고 합집합으로 나누는 까닭은 규모를 맞추기 위해서입니다. 백 가지를 담은 두 장바구니가 세 가지를 공유하는 것과 네 가지를 담은 두 장바구니가 세 가지를 공유하는 것은 전혀 다른 일입니다. 합집합의 크기는 포함배제 원리⁠(inclusion–exclusion principle)⁠로 $|A|+|B|-|A\cap B|$이고, 집합의 크기⁠(cardinality)⁠만 알면 계산됩니다. 둘 다 담지 않은 물건(회색)은 셈에 들어가지 않는다는 점도 중요합니다. 수만 가지 상품 가운데 둘 다 사지 않은 물건이 많다고 두 사람이 닮았다고 할 수는 없으니까요.

1에서 뺀 $d_J = 1 - J =$ 삼각부등식(A와 C 사이의 거리는 A–B 거리와 B–C 거리의 합을 넘지 않는다)까지 지키는 진짜 거리 함수⁠(metric)⁠입니다. 분자 $|A\triangle B|$(한쪽에만 있는 것의 개수)는 두 집합을 0과 1의 줄로 적었을 때의 해밍 거리⁠(Hamming distance)⁠이고, 자카드 거리는 그것을 합집합의 크기로 나눈 것입니다. 삼각부등식은 아래의 무작위 순서 요령으로 한 줄에 증명됩니다. 반면 비슷해 보이는 쇠렌센–다이스 계수⁠(Sørensen–Dice coefficient)⁠는 1에서 빼도 삼각부등식을 어깁니다.

문서를 집합으로. 두 문장이 얼마나 겹치는지 재려면 문장을 조각(슁글⁠, shingle⁠)들의 집합으로 바꿉니다. 첫 문장은 '고양이가 매트 위에 앉아 있었다', 비교할 문장은 , 조각은 입니다. 조각 수는 개와 개, 공통 조각은 이고, 자카드 지수는 입니다. 단어 단위로 보면 어순을 바꾼 문장이 원래 문장과 같은 집합이 되지만, 글자 두세 개씩 겹쳐 자른 조각은 순서도 조금 기억합니다. 표절 검사나 웹 문서의 중복 찾기는 이렇게 합니다. 문자 하나하나의 고침을 세는 편집 거리⁠(edit distance)⁠보다 거칠지만, 긴 문서에서도 빠릅니다.

문서가 수십억 개면 모든 쌍의 교집합을 셀 수 없습니다. 1990년대 후반 당시의 대표적 검색 엔진 알타비스타에서 컴퓨터 과학자 안드레이 브로더가 쓴 MinHash는 전체 원소⁠(element)⁠를 무작위 순서로 섞은 뒤 각 집합에서 가장 앞에 오는 원소를 봅니다. 두 집합의 '맨 앞 원소'가 같을 확률⁠(probability)⁠은 정확히 J입니다. 합집합의 원소 가운데 가장 앞에 온 것이 교집합에 속할 확률이기 때문입니다. 장바구니에 이 요령을 200번 써 보면 같았던 비율이 , 큰 수의 법칙⁠(law of large numbers)⁠대로 J 근처에 옵니다. 같은 식으로 $d_J$는 '맨 앞 원소가 다를 확률'이고, A와 B의 맨 앞이 다르면 A와 C, C와 B 가운데 적어도 한 쌍은 다르므로 삼각부등식이 성립합니다.

이어지는 곳. 이름은 스위스의 식물학자 폴 자카드에게서 왔습니다. 그가 알프스와 쥐라 산지의 여러 지역에 사는 식물 종의 목록을 비교하며 1900년대 초(흔히 1901년과 1912년 논문으로 꼽습니다) 두 지역에 공통으로 사는 종의 비율을 재려고 쓴 '공동체 계수⁠(coefficient of community)⁠'가 바로 이 값입니다. 집합을 0과 1의 벡터⁠(vector)⁠로 보면 교집합의 크기는 내적⁠(dot product)⁠이 되고, 같은 내적을 다른 방식으로 나누면 코사인 유사도⁠(cosine similarity)⁠가 됩니다. 컴퓨터 비전에서는 예측한 상자와 정답 상자가 겹친 넓이⁠(area)⁠ ÷ 합친 넓이를 IoU라 부르며 같은 값을 씁니다. 비슷한 사용자나 문서를 찾아 추천하는 최근접 이웃⁠(nearest neighbor)⁠ 방법도 흔히 자카드 거리로 이웃을 고릅니다.