자카드 유사도

통계 소프트웨어 마지막 수정: 2026-08-30 04:51:22

1. 개요[편집]

자카드 유사도 Jaccard similarity
제안	Paul Jaccard (1901) — 알프스 식생 비교
정의	$J(A,B)=\lvert A\cap B\rvert/\lvert A\cup B\rvert$
거리	$1-J$ 는 거리 공리를 전부 만족한다
추정	MinHash — 무편향, 분산 $J(1-J)/k$
별칭	타니모토 계수(화학정보학) · IoU(컴퓨터 비전)

두 집합이 얼마나 닮았는지 재는 데 백 년 넘게 살아남은 공식. 분자에는 겹친 것, 분모에는 전부.

자카드 유사도(Jaccard similarity, 자카드 지수)는 두 유한집합 $A,B$ 의 교집합 크기를 합집합 크기로 나눈 값

J(A,B) = \frac{\lvert A\cap B\rvert}{\lvert A\cup B\rvert} = \frac{\lvert A\cap B\rvert}{\lvert A\rvert + \lvert B\rvert - \lvert A\cap B\rvert} \;\in\; [0,1]

으로 정의되는 집합 유사도 척도다. 스위스의 식물학자 폴 자카르가 1901년 알프스 지역 식물상의 지역 간 유사성을 비교하려고 “공동체 계수”(coefficient de communauté)라는 이름으로 도입했다.¹ $A=B$ 면 1, 서로소면 0이며, 관례적으로 $J(\emptyset,\emptyset)=1$ 로 둔다.

이진 벡터로 보면 성질이 더 선명해진다. 두 벡터의 좌표를 넷으로 분류해 $M_{11}$ (둘 다 1), $M_{10}$ , $M_{01}$ , $M_{00}$ (둘 다 0)이라 하면

J = \frac{M_{11}}{M_{11}+M_{10}+M_{01}}

이다. 분모에 $M_{00}$ 이 없다. 즉 “둘 다 없는 것”을 유사성의 증거로 세지 않는다. 이것이 단순 일치 계수와 갈리는 지점이자, 자카드가 희소한 원-핫·집합 데이터에 잘 맞는 이유다. 문서 하나에 안 나오는 단어가 사전의 99.99%인데 그 일치를 다 세면 모든 문서가 서로 닮은 것이 되기 때문이다.

2. 거리 공리를 만족한다[편집]

$d_J(A,B)=1-J(A,B)$ 를 자카드 거리라 하며, 이것이 실제로 거리 공리를 전부 만족한다는 사실이 이 척도의 가장 단단한 자산이다. 비음성·대칭성·동일성은 자명하고 문제는 삼각부등식인데, 대칭차집합 $A\triangle B$ 를 쓰면

d_J(A,B) = \frac{\lvert A\triangle B\rvert}{\lvert A\cup B\rvert}

로 쓸 수 있다는 데서 출발한다. $\lvert A\triangle B\rvert$ 자체는 (측도이므로) 거리이고, 여기에 기준점 $a$ 에 대한 슈타인하우스 변환

d'(x,y) = \frac{2\,d(x,y)}{d(x,a)+d(y,a)+d(x,y)}

을 $a=\emptyset$ 로 적용하면 분모가 $\lvert A\rvert+\lvert B\rvert+\lvert A\triangle B\rvert = 2\lvert A\cup B\rvert$ 가 되어 정확히 $d_J$ 가 나온다. 슈타인하우스 변환이 거리를 거리로 보낸다는 것이 알려져 있으므로 증명이 끝난다.²

이게 왜 중요한가. 삼각부등식이 있으면 가지치기가 가능해진다. 계층적 군집화에서 병합 순서의 일관성이 보장되고, 거리 기반 색인(VP-트리, BK-트리)에서 부분트리를 통째로 건너뛸 수 있으며, 근사 알고리즘의 오차 분석이 성립한다. 뒤에 나오는 다이스 계수는 이 성질이 없어서 그런 도구를 못 쓴다.

여담으로, 유사도를 자카드로 재는 순간 $\ell_2$ 세계의 도구는 거의 못 쓴다. 마할라노비스 거리 같은 공분산 기반 척도나 커널 PCA 같은 내적 기반 기법은 애초에 벡터공간을 전제하는데, 집합에는 덧셈이 없다. 대신 자카드에는 아래의 무편향 추정량이라는, 벡터 척도가 못 가진 무기가 있다.

3. MinHash — 유사도를 «세는» 대신 «맞히는»[편집]

집합이 크면 $\lvert A\cap B\rvert$ 를 직접 세는 것부터가 비싸고, 집합이 수억 개면 모든 쌍은 꿈도 못 꾼다. MinHash(브로더, 1997)는 이 문제를 통째로 바꿔 놓는다. 전체 원소 집합 위의 무작위 순열 $\pi$ 를 하나 뽑고

h_\pi(A) = \min\,\pi(A)

로 정의하면, $A\cup B$ 의 원소 중 $\pi$ 아래에서 가장 앞에 오는 것이 무엇이냐만 따지면 되고 그것이 $A\cap B$ 에 속할 확률이 곧 $J$ 이므로 $\Pr[h_\pi(A)=h_\pi(B)]=J(A,B)$ 가 정확히 성립한다. 이 항등식의 유도와 해시족으로서의 성질은 국소 민감 해싱 문서가 다루므로 여기서는 추정량으로서의 통계를 본다.

독립인 순열 $k$ 개를 쓰고

\hat J = \frac1k\sum_{t=1}^{k}\mathbf 1\big[h_{\pi_t}(A)=h_{\pi_t}(B)\big]

로 두면 $k\hat J \sim \mathrm{Binomial}(k, J)$ 이므로

\mathbb E[\hat J]=J,\qquad \mathrm{Var}[\hat J]=\frac{J(1-J)}{k}

다. 무편향이고, 표준오차가 집합 크기와 무관하게 $\sqrt{J(1-J)/k}$ 뿐이라는 것이 핵심이다. 원소가 10개짜리 집합이든 10억 개짜리 집합이든, 서명 길이 $k$ 만 같으면 정확도가 같다. 반면 대가도 명확하다 — 표준오차를 절반으로 줄이려면 $k$ 를 네 배로 늘려야 하는 몬테카를로 방법의 $1/\sqrt k$ 수렴이라, 실무에서 $k$ 는 대개 128~512에 머문다.

목표 표준오차 ( $J=0.5$ )	필요한 $k$	서명 크기(64비트)
0.05	100	800 B
0.02	625	5 KB
0.01	2500	20 KB
0.005	10000	80 KB

구현에서는 진짜 순열 대신 요령을 쓴다. 독립 해시 함수 $k$ 개를 써서 각각의 최솟값을 취하는 것이 교과서 방식이고, 해시 하나로 하위 $k$ 개를 취하는 bottom- $k$ 스케치는 해시 계산을 $k$ 배 아끼면서 비슷한 분산을 낸다. 한 번의 순열(one permutation hashing)로 해시 공간을 $k$ 개 구간으로 쪼개 각 구간의 최솟값을 쓰는 방식은 계산을 극단적으로 줄이지만 빈 구간이 생겨 «조밀화»(densification) 보정이 필요하다.

저장 공간을 더 줄이는 것이 $b$ 비트 MinHash다. 64비트 해시값 전체 대신 하위 $b$ 비트(보통 1~4)만 저장하면 서명이 한 자릿수 작아진다. 대신 서로 다른 원소가 우연히 같은 $b$ 비트를 갖는 사고가 생기므로, 관측된 일치율에서 그 우연 일치를 빼는 보정식을 반드시 써야 한다. 보정을 빼먹으면 유사도가 조직적으로 부풀려진다 — $b=1$ 이면 무작위 일치 확률만으로도 0.5가 깔린다.

4. 임계값 문제[편집]

“유사도 0.8 이상인 쌍만 찾아라”를 서명 $k$ 개로 어떻게 푸는가는 밴딩(banding) LSH의 몫이다. 서명을 $r$ 행씩 $b$ 개 밴드로 잘라 밴드 하나라도 완전히 일치하면 후보로 채택하는 방식이고, 채택 확률이 $1-(1-s^r)^b$ 인 S자 곡선을 그리며 사실상의 문턱이 $(1/b)^{1/r}$ 근방에 온다. 구성과 파라미터 선택은 국소 민감 해싱 문서에 있으니 반복하지 않는다.

여기서 짚을 것은 추정과 판정이 다른 문제라는 점이다. $\hat J$ 는 값이 궁금할 때 쓰는 것이고, 밴딩은 값이 아니라 “문턱을 넘느냐”만 궁금할 때 쓴다. 후자는 모든 쌍을 볼 필요조차 없다는 점에서 훨씬 싸다. 실무 파이프라인은 대개 둘을 이어 붙인다 — 밴딩으로 후보를 뽑고, 후보에 대해서만 $\hat J$ 나 정확한 $J$ 를 계산한다. 최근접 이웃 탐색 문서의 브로드페이즈-내로페이즈 구조 그대로다.

5. 가중 자카드[편집]

원소가 있냐 없냐가 아니라 몇 번 나왔냐가 중요한 경우가 훨씬 많다. 단어 빈도, 로그 카운트, TF-IDF 가중치 같은 것들이다. 음이 아닌 벡터 $x,y$ 에 대한 가중 자카드 유사도는

J_W(x,y) = \frac{\sum_i \min(x_i,y_i)}{\sum_i \max(x_i,y_i)}

로 정의되고, 성분이 0/1이면 원래 정의로 환원된다. 이 유사도에도 MinHash에 해당하는 것이 있다 — 일관 가중 샘플링(Consistent Weighted Sampling, CWS)이다. 각 집합에 대해 독립적으로 표본 $(i^\star, y^\star)$ 를 뽑되, 두 벡터에서 같은 표본이 나올 확률이 정확히 $J_W$ 가 되도록 설계한다. “일관”이라는 말은 각 벡터를 따로 처리해도 결과가 짝지어진다는 뜻이고, 이게 없으면 분산 환경에서 못 쓴다. 이오페의 ICWS(2010)가 표본 하나를 비영원소 수에 선형인 시간에 뽑는 방법을 주면서 실용화됐다.

주의할 것은 가중 자카드가 스케일에 민감하다는 점이다. $x$ 를 두 배로 늘리면 $J_W(x,y)$ 가 변한다. 코사인 유사도가 크기를 무시하는 것과 정반대라, 문서 길이를 정규화할지 말지를 먼저 정해야 한다.

6. 실제 무대[편집]

근중복 문서 탐지. 문서를 그대로 집합으로 만들 수는 없으니 시밍글(shingle)로 자른다. 길이 $w$ 의 연속 토큰열(또는 문자열) 전부를 원소로 하는 집합을 만드는 것이고, 단어 단위면 $w=5\sim9$ , 문자 단위면 $w=8\sim10$ 이 흔하다. $w$ 가 작으면 아무 문서나 다 겹치고(“the of a” 같은 시밍글은 어디에나 있다), 크면 문장 하나만 고쳐도 유사도가 0으로 떨어진다. 시밍글을 64비트로 해시해 저장하면 원문보다 오히려 작아진다는 것이 이 표현의 실용적 이점이다.³ 요즘 LLM 학습 코퍼스 정제의 표준 도구가 이 파이프라인이라, 「MinHash 중복 제거」는 사실상 데이터 엔지니어링의 국룰이 됐다.

포함도(containment). $J$ 는 대칭이라 크기가 크게 다른 두 집합에 가혹하다. $B\subset A$ 이고 $\lvert A\rvert = 100\lvert B\rvert$ 면 완벽한 부분집합인데도 $J=0.01$ 이다. “이 짧은 문서가 저 긴 문서에 통째로 들어 있나”를 묻고 싶다면 비대칭 척도인 포함도 $\lvert A\cap B\rvert/\lvert B\rvert$ 를 써야 한다. 표절 탐지가 자카드로 잘 안 되는 흔한 이유가 이것이다.

유전체 거리. 게놈을 $k$ -mer 집합으로 보고 MinHash 스케치로 $J$ 를 추정한 뒤, 포아송 치환 모형을 가정해 돌연변이율로 환산하는 것이 Mash 거리다.

D = -\frac1k\ln\frac{2J}{1+J}

정렬을 한 번도 안 하고 게놈 수만 개의 거리 행렬을 만들 수 있다는 것이 요점이고, 스케치가 원본의 수천분의 일이라 계통수 초안을 노트북에서 뽑는다.

IoU. 컴퓨터 비전에서 검출 상자나 분할 마스크를 픽셀 집합으로 보면 IoU(Intersection over Union)가 정확히 자카드 지수다. mAP 계산의 매칭 기준(보통 IoU 0.5), 분할 모델의 mIoU 지표가 전부 이것. 미분 가능한 완화판(soft IoU, Lovász 힌지)을 손실 함수로 쓰기도 한다.

화학정보학. 분자를 ECFP 같은 이진 지문으로 만든 뒤 자카드를 재는 것이 타니모토 계수다. 이름만 다르고 이진 벡터에서는 같은 공식이며, “타니모토 0.85 이상이면 비슷한 활성”이라는 경험칙이 신약 스크리닝의 오래된 관행이다.

군집화. 원-핫이나 장바구니 데이터에는 유클리드 거리가 의미가 없어서 자카드 거리를 쓴다. 다만 k-평균 군집화는 평균이 정의돼야 돌아가는데 집합의 평균은 없으므로, k-medoids나 계층적 군집화로 가거나 범주형 전용인 k-modes를 쓴다. 거리를 바꿨으면 알고리즘도 바꿔야 한다는 것을 잊고 자카드 거리 행렬을 k-means에 밀어 넣는 사고가 은근히 잦다.

7. 흔한 함정[편집]

다이스와 헷갈리지 마라. 다이스-쇠렌센 계수 $D = 2\lvert A\cap B\rvert/(\lvert A\rvert+\lvert B\rvert)$ 는 자카드와 $D = 2J/(1+J)$ , $J = D/(2-D)$ 로 일대일 대응하므로 순위를 매기는 데는 완전히 동등하다. 그런데 $1-D$ 는 삼각부등식을 만족하지 않는다. 값만 볼 거면 아무거나 쓰고, 거리로 쓸 거면 자카드를 써라.
카디널리티 추정으로 우회하지 마라. $\lvert A\rvert$ , $\lvert B\rvert$ , $\lvert A\cup B\rvert$ 를 HyperLogLog 같은 스케치로 각각 추정하고 포함-배제로 $\lvert A\cap B\rvert$ 를 빼는 방법이 있다. 되긴 되는데, 교집합이 합집합에 비해 작으면 큰 수 두 개의 차이를 구하는 꼴이라 상대오차가 폭발한다. 유사도가 낮은 영역에서 특히 나쁘고, 그 영역이 보통 관심 영역이다. 자카드가 목적이면 MinHash를 써라.
해시 충돌은 유사도를 올린다. 시밍글을 32비트로 해시하면 생일 문제로 문서 하나 안에서도 충돌이 나기 시작한다. 충돌은 없던 교집합을 만들어 내므로 편향이 항상 위쪽이다. 64비트를 써라. 해시 테이블의 충돌은 성능 문제지만 여기서는 정확도 문제다.
드문 원소가 다 한다. 자카드는 원소마다 가중치가 같아서, 불용어처럼 아무 데나 있는 원소가 유사도를 떠받치고 정작 변별력 있는 희귀 원소가 묻힌다. 그래서 실무에서는 문서 빈도 상위 토큰을 미리 쳐내거나 가중 자카드로 넘어간다. 블룸 필터로 초고빈도 원소를 걸러 두는 전처리도 흔하다.
차원의 저주는 여기도 온다. 집합 표현이라고 예외가 아니다. 원소 수가 늘고 집합이 희소해질수록 대부분의 쌍이 $J\approx 0$ 으로 몰려 구분이 안 된다. 차원의 저주의 거리 집중이 자카드에서는 «전부 서로소»로 나타나는 것뿐이다.

8. 관련 문서[편집]

자카르는 이 계수로 알프스와 쥐라 산맥의 식물 분포를 비교했다. 백 년 뒤 같은 공식이 웹 문서 중복 제거와 신약 후보 스크리닝과 객체 검출 평가에 동시에 쓰이고 있다는 것을 본인이 알면 꽤 놀랄 것이다. 참고로 생태학에서는 지금도 «자카르 지수»라는 이름 그대로 종 구성 비교에 쓰인다. ↩
삼각부등식이 성립한다는 사실 자체는 꽤 늦게(1971년 Nature의 짧은 노트로) 널리 알려졌다. 그전까지는 “유사도니까 대충 거리처럼 쓰면 되겠지” 하고 썼던 셈인데, 결과적으로 맞았다. 이 바닥에서 드문 해피엔딩이다. ↩
$w$ 를 정하는 원칙적인 방법은 없고, 실무 규칙은 «임의의 문서에 그 시밍글이 우연히 나타날 확률이 충분히 낮을 것» 정도다. 코퍼스 성격을 크게 타서, 법률 문서처럼 상투구가 많은 코퍼스에서는 $w$ 를 키워야 하고 짧은 게시글 코퍼스에서는 키우면 아무것도 안 잡힌다. 결국 «일단 돌려 보고 히스토그램 보기»로 정한다. ↩