자카드 지수

1. 개요

자카드 지수는 유한 표본 집합 간의 유사성을 측정하는 지표로, 교집합의 크기를 합집합의 크기로 나눈 값이다. 0과 1 사이의 값을 가지며, 컴퓨터 과학, 생태학, 유전체학 등 이진 데이터를 사용하는 다양한 분야에서 활용된다. 자카드 거리와 가중 자카드 지수, 확률 자카드 지수 등 변형된 형태가 존재하며, 이진 속성에 대한 자카드 지수는 단순 일치 계수와 유사하지만, 서로 다른 점이 있다. 타니모토 유사도 및 거리는 자카드 지수와 유사하게 사용되지만, 수학적으로 차이가 있을 수 있다.

2. 정의

자카드 지수는 유한 표본 집합 간의 유사성을 측정하는 방법으로, 교집합의 크기를 합집합의 크기로 나눈 값으로 정의된다.

:$J(A,\; B)\; =\; \backslash frac$

3.1. 단순 일치 계수(SMC)와의 비교

자카드 지수는 단순 일치 계수(SMC)와 매우 유사하지만, 중요한 차이점이 있다. 단순 일치 계수(SMC)는 두 집합이 모두 속성을 가지지 않는 경우(M₀₀)도 유사도에 포함하지만, 자카드 지수는 두 집합 중 적어도 하나가 속성을 가진 경우(M₁₁, M₀₁, M₁₀)만을 고려한다.

다음은 슈퍼마켓에서 두 고객의 장바구니를 비교하는 예시이다.

4. 가중 자카드 지수 및 거리

자카드 거리는 표본 집합 간의 비유사성을 측정하며, 자카드 지수와 상호 보완적이다. 자카드 거리는 자카드 지수를 1에서 빼거나, 두 집합의 합집합과 교집합의 크기 차이를 합집합의 크기로 나누어 얻는다.

:$d\_J(A,\; B)\; =\; 1\; -\; J(A,\; B)\; =\; \backslash frac$

👆

좌우로 밀어서 보기

📌 열 고정 해제

👆

좌우로 밀어서 보기

📌 열 고정 해제

.

자카드 거리의 다른 해석은 대칭 차이 $A\; \backslash mathbin\backslash triangle\; B\; =\; (A\; \backslash cup\; B)\; -\; (A\; \backslash cap\; B)$의 크기를 합집합으로 나눈 비율이다. 자카드 거리는 n개의 표본 집합의 클러스터링 및 다차원 척도법을 위한 행렬을 계산하는 데 일반적으로 사용된다.

측도를 포함한 확률 측도에 대한 자카드 거리 버전도 있다. $\backslash mu$가 가측 공간$X$에 대한 측도이면, 자카드 지수는 다음과 같이 정의된다.

:$J\_\backslash mu(A,\; B)\; =\; \backslash frac\{\backslash mu(A\; \backslash cap\; B)\}\{\backslash mu(A\; \backslash cup\; B)\},$

그리고 자카드 거리는 다음과 같다.

:$d\_\backslash mu(A,\; B)\; =\; 1\; -\; J\_\backslash mu(A,B)\; =\; \backslash frac\{\backslash mu(A\; \backslash mathbin\backslash triangle\; B)\}\{\backslash mu(A\; \backslash cup\; B)\}.$

만약 $\backslash mathbf\{x\}\; =\; (x\_1,\; x\_2,\; \backslash ldots,\; x\_n)$와 $\backslash mathbf\{y\}\; =\; (y\_1,\; y\_2,\; \backslash ldots,\; y\_n)$가 모든 실수 $x\_i,\; y\_i\; \backslash geq\; 0$을 갖는 두 벡터라면, 이들의 자카드 유사성 지수(Ruzicka 유사성이라고도 알려져 있음)는 다음과 같이 정의된다.

:$J\_\backslash mathcal\{W\}(\backslash mathbf\{x\},\; \backslash mathbf\{y\})\; =\; \backslash frac\{\backslash sum\_i\; \backslash min(x\_i,\; y\_i)\}\{\backslash sum\_i\; \backslash max(x\_i,\; y\_i)\},$

그리고 자카드 거리(Soergel 거리라고도 알려져 있음)는 다음과 같다.

:$d\_\{J\backslash mathcal\{W\}\}(\backslash mathbf\{x\},\; \backslash mathbf\{y\})\; =\; 1\; -\; J\_\backslash mathcal\{W\}(\backslash mathbf\{x\},\; \backslash mathbf\{y\}).$

더욱 일반화하여, 만약 $f$와 $g$가 측정 가능한 공간 $X$에서 측도 $\backslash mu$를 갖는 두 개의 음이 아닌 측정 가능한 함수라면, 다음과 같이 정의할 수 있다.

:$J\_\backslash mathcal\{W\}(f,\; g)\; =\; \backslash frac\{\backslash int\backslash min(f,\; g)\; d\backslash mu\}\{\backslash int\; \backslash max(f,\; g)\; d\backslash mu\},$

여기서 $\backslash max$와 $\backslash min$은 점별 연산자이다. 그러면 자카드 거리는 다음과 같다.

:$d\_\{J\backslash mathcal\{W\}\}(f,\; g)\; =\; 1\; -\; J\_\backslash mathcal\{W\}(f,\; g).$

5. 확률 자카드 지수 및 거리

자카드 거리는 표본 집합 간의 비유사성을 측정하며, 자카드 지수를 1에서 빼거나, 두 집합의 합집합과 교집합의 크기 차이를 합집합의 크기로 나누어 얻는다.
: $d\_J(A,\; B)\; =\; 1\; -\; J(A,\; B)\; =\; \backslash frac$

👆

좌우로 밀어서 보기

📌 열 고정 해제

👆

좌우로 밀어서 보기

📌 열 고정 해제

.
자카드 거리의 다른 해석은 대칭 차이 $A\; \backslash mathbin\backslash triangle\; B\; =\; (A\; \backslash cup\; B)\; -\; (A\; \backslash cap\; B)$의 크기를 합집합으로 나눈 비율이다.

측도를 포함한 확률 측도에 대한 자카드 거리 버전도 있다. $\backslash mu$가 가측 공간$X$에 대한 측도이면, 자카드 지수는 다음과 같이 정의한다.
: $J\_\backslash mu(A,\; B)\; =\; \backslash frac\{\backslash mu(A\; \backslash cap\; B)\}\{\backslash mu(A\; \backslash cup\; B)\},$
그리고 자카드 거리는 다음과 같다.
: $d\_\backslash mu(A,\; B)\; =\; 1\; -\; J\_\backslash mu(A,B)\; =\; \backslash frac\{\backslash mu(A\; \backslash mathbin\backslash triangle\; B)\}\{\backslash mu(A\; \backslash cup\; B)\}.$
$\backslash mu(A\; \backslash cup\; B)\; =\; 0$ 또는 $\backslash infty$인 경우, 이러한 공식이 정의되지 않으므로 주의해야 한다.

확률 분포와 해당 지원 집합 사이에서 연속적인 일반화는 다음과 같다.
:$J\_\backslash mathcal\{P\}(x,y)\; =\; \backslash sum\_\{x\_i\backslash neq\; 0,\; y\_i\; \backslash neq\; 0\}\; \backslash frac\{1\}\{\backslash sum\_\{j\}\; \backslash max\backslash left(\backslash frac\{x\_j\}\{x\_i\},\; \backslash frac\{y\_j\}\{y\_i\}\backslash right)\}$
이는 "확률" 자카드라고 불린다. 이는 확률 벡터에 대한 가중 자카드에 대해 다음과 같은 경계를 갖는다.
:$J\_\backslash mathcal\{W\}(x,y)\; \backslash leq\; J\_\backslash mathcal\{P\}(x,y)\; \backslash leq\; \backslash frac\{2J\_\backslash mathcal\{W\}(x,y)\}\{1+J\_\backslash mathcal\{W\}(x,y)\}$
여기서 상한은 (가중) 쇠렌센-다이스 계수이다. 해당 거리인 $1\; -\; J\_\backslash mathcal\{P\}(x,y)$는 확률 분포에 대한 메트릭이며, 음수가 아닌 벡터에 대한 의사 메트릭이다.

확률 자카드 지수는 단순체의 교차 면적으로 기하학적으로 해석될 수 있다.

단위 $k$-단순체의 모든 점은 $k+1$개의 요소에 대한 확률 분포에 해당하는데, 그 이유는 단위 $k$-단순체가 합이 1이 되는 $k+1$ 차원의 점 집합이기 때문이다. 확률 자카드 지수를 기하학적으로 유도하려면 각 항목의 질량에 따라 단위 단순체를 하위 단순체로 나눈 확률 분포를 나타낸다. 이와 같은 방식으로 표현된 두 개의 분포를 서로 겹쳐놓고 각 항목에 해당하는 단순체를 교차시키면 남은 면적이 분포의 확률 자카드 지수와 같다.

서로 최대한 많이 충돌하는 확률 변수를 구성하는 문제를 생각해 보자. 즉, $X\backslash sim\; x$ 및 $Y\backslash sim\; y$인 경우, $X$와 $Y$를 구성하여 $\backslash Pr[X=Y]$를 최대화하려고 한다. 두 개의 분포 $x,y$만 따로 살펴보면, 얻을 수 있는 가장 높은 $\backslash Pr[X=Y]$는 $1\; -\; \backslash text\{TV\}(x,y)$로 주어지며 여기서 $\backslash text\{TV\}$는 총 변동 거리이다. 그러나 특정 쌍의 최대화에만 관심이 있는 것이 아니라, 임의의 쌍의 충돌 확률을 최대화하려는 경우를 생각해 보자. 각 분포 $x$에 대해 하나씩, 무한한 수의 확률 변수를 구성하고 모든 쌍 $x,y$에 대해 $\backslash Pr[X=Y]$를 최대화하려고 할 수 있다. 아래에 설명된 강력한 의미에서, 확률 자카드 지수는 이러한 확률 변수를 정렬하는 최적의 방법이다.

임의의 샘플링 방법 $G$ 및 이산 분포 $x,y$에 대해, $\backslash Pr[G(x)\; =\; G(y)]\; >\; J\_\backslash mathcal\{P\}(x,y)$인 경우, $J\_\backslash mathcal\{P\}(x,z)>J\_\backslash mathcal\{P\}(x,y)$이고 $J\_\backslash mathcal\{P\}(y,z)>J\_\backslash mathcal\{P\}(x,y)$인 일부 $z$에 대해 또는 이다.

즉, 어떤 샘플링 방법도 다른 쌍에서 $J\_\backslash mathcal\{P\}$보다 충돌 횟수가 적어지면 한 쌍에서 $J\_\backslash mathcal\{P\}$보다 더 많은 충돌을 달성할 수 없으며, 여기서 감소된 쌍은 $J\_\backslash mathcal\{P\}$에 따라 증가된 쌍보다 더 유사하다. 이 정리는 집합의 자카드 지수(균일 분포로 해석되는 경우)와 확률 자카드에 대해 참이지만 가중 자카드에는 적용되지 않는다. (이 정리는 모든 분포에 대한 공동 분포를 설명하기 위해 "샘플링 방법"이라는 단어를 사용하는데, 이는 이를 충돌 확률로 달성하는 가중 민해싱 알고리즘의 사용에서 파생되기 때문이다.)

이 정리는 심플렉스 표현을 사용하여 세 요소 분포에 대한 시각적 증명이 있다.

6. 타니모토 유사도 및 거리

문헌과 인터넷에는 다양한 형태의 함수가 Tanimoto 유사도 및 Tanimoto 거리로 설명되어 있다. 이들 대부분은 자카드 유사도와 자카드 거리의 동의어이지만, 일부는 수학적으로 다르다. 많은 자료는 IBM 기술 보고서를 핵심 참고 문헌으로 인용한다.

1960년 10월에 출판된 "식물 분류를 위한 컴퓨터 프로그램"에서 유사도 비율을 기반으로 한 분류 방법과 파생된 거리 함수가 제시되었다. 이것이 "Tanimoto 유사도"와 "Tanimoto 거리"라는 용어의 의미에 대한 가장 권위 있는 출처로 보인다. 유사도 비율은 자카드 유사도와 동일하지만, 거리 함수는 자카드 거리와 같지 않다.

해당 논문에서는 고정 크기 배열의 각 비트가 모델링되는 식물의 특성 존재 여부를 나타내는 비트맵에 대해 "유사성 비율"이 제시되어 있다. 이 비율의 정의는 공통 비트 수를 두 샘플 중 하나라도 설정된 (즉 0이 아닌) 비트 수로 나눈 값이다.

수학적 용어로 표현하면, 샘플 X와 Y가 비트맵이고, $X\_i$가 X의 i번째 비트이며, $\backslash land\; ,\; \backslash lor$가 각각 비트 단위 and, or 연산자이면, 유사성 비율 $T\_s$는 다음과 같다.

:$T\_s(X,Y)\; =\; \backslash frac\{\backslash sum\_i\; (\; X\_i\; \backslash land\; Y\_i)\}\{\backslash sum\_i\; (\; X\_i\; \backslash lor\; Y\_i)\}$

각 샘플이 대신 속성 집합으로 모델링되면, 이 값은 두 집합의 자카드 지수와 같다. 자카드는 이 논문에 인용되지 않았으며, 저자들이 이를 인지하지 못했을 가능성이 높다.

타니모토는 이 비율을 기반으로 하여, 0이 아닌 유사성을 가진 비트맵에 대해 정의된 "거리"를 정의한다.

:$T\_d(X,Y)\; =\; -\backslash log\_2\; (\; T\_s(X,Y)\; )$

이 계수는 의도적으로 거리 메트릭이 아니다. 이는 서로 매우 다른 두 표본이 모두 세 번째 표본과 유사할 가능성을 허용하기 위해 선택되었다. 삼각 부등식의 속성을 부정하는 예시를 쉽게 구성할 수 있다.

7. 응용

자카드 거리는 종종 자카드 거리 $1-T\_s$와 동의어로 오해되어 언급된다. 이 함수는 올바른 거리 메트릭이다. "타니모토 거리"는 종종 올바른 거리 메트릭이라고 언급되는데, 아마도 자카드 거리와의 혼동 때문일 것이다.

자카드 또는 타니모토 유사성이 비트 벡터로 표현되는 경우 다음과 같이 쓸 수 있다.

:$f(A,B)\; =\backslash frac\{\; A\; \backslash cdot\; B\}\{\backslash |A\backslash |^2\; +\backslash |B\backslash |^2\; -\; A\; \backslash cdot\; B\}$

여기서 동일한 계산은 벡터 스칼라 곱과 크기로 표현된다. 이 표현은 비트 벡터(각 차원의 값이 0 또는 1임)에 대해 다음과 같은 사실에 의존한다.

:$A\; \backslash cdot\; B\; =\; \backslash sum\_i\; A\_iB\_i\; =\; \backslash sum\_i\; (\; A\_i\; \backslash land\; B\_i)$

그리고

:$\backslash |A\backslash |^2\; =\; \backslash sum\_i\; A\_i^2\; =\; \backslash sum\_i\; A\_i.$

이것은 잠재적으로 혼란스러운 표현인데, 벡터로 표현된 함수가 더 일반적이기 때문이다(도메인이 명시적으로 제한되지 않는 한). $T\_s$의 속성이 $f$로 반드시 확장되는 것은 아니다. 특히, 차이 함수 $1-f$는 삼각 부등식을 유지하지 않으므로 올바른 거리 메트릭이 아니지만, $1\; -\; T\_s$는 그렇지 않다.

이 공식을 사용하여 "타니모토 거리"를 정의하고, "타니모토 거리는 올바른 거리 메트릭이다"라는 문구를 결합하면, 함수 $1-f$가 실제로 벡터 또는 일반적인 멀티셋에 대한 거리 메트릭이라는 잘못된 결론으로 이어질 위험이 있다. 반면, 유사성 검색 또는 클러스터링 알고리즘에서 사용하면 올바른 결과를 생성하지 못할 수 있다.

Lipkus는 $f$와 동일한 타니모토 유사성 정의를 사용하며, 타니모토 거리를 함수 $1-f$로 언급한다. 그러나 논문 내에서 문맥은 임의의 벡터 A에 대해 $A\_i\; \backslash in\; \backslash \{0,W\_i\backslash \}.$가 되도록 하는 (양의) 가중치 벡터 $W$의 사용으로 제한된다는 점이 명확히 밝혀져 있다. 이러한 상황에서 함수는 올바른 거리 메트릭이므로, 이러한 가중치 벡터에 의해 관리되는 벡터 집합은 이 함수 아래에서 메트릭 공간을 형성한다.

이진 분류에 사용되는 오차 행렬에서 자카드 지수는 다음 공식으로 나타낼 수 있다.

:$\backslash text\{자카드\; 지수\}\; =\; \backslash frac\{TP\}\{TP\; +\; FP\; +\; FN\}$

여기서 TP는 참 양성, FP는 거짓 양성, FN은 거짓 음성이다.

다른 이름	자카드 유사도 계수 자카드 지수 교차-합집합 지수
유형	유사도 지수
분야	생태학 계통학 정보 검색 텍스트 마이닝

정의

수식 (집합 A와 B의 경우)	A와 B의 교집합/A와 B의 합집합 = A와 B의 교집합 / (|A| + |B| - A와 B의 교집합)
설명	두 표본 집합 간의 유사성을 측정하는 데 사용됨.
값의 범위	'[0, 1]' (0은 집합이 겹치지 않음을 의미, 1은 집합이 동일함을 의미)

활용

사용 예시	객체 탐지 이미지 분할
참고 자료	유클리드 거리 코사인 유사도 편집 거리 해밍 거리 상관계수 Dice 계수 중복 계수