자카드 지수
"오늘의AI위키" 는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키" 의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차 보기/숨기기
2. 정의
자카드 지수는 유한 표본 집합 간의 유사성을 측정하는 방법으로, 교집합의 크기를 합집합의 크기로 나눈 값으로 정의된다. [5] :J(A, B) = \frac
= \frac. A와 B의 교집합이 없으면, ''J''(''A'', ''B'') = 0이다. 자카드 지수는 0과 1 사이의 값을 가지며, 컴퓨터 과학, 생태학, 유전체학 등 이진 또는 이진화된 데이터 를 사용하는 여러 과학 분야에서 널리 사용된다. [5] 자카드 유사성은 가방(멀티셋)에도 적용할 수 있다. 이 경우, 사용되는 기호는 가방 교집합과 가방 합(합집합 아님)을 나타내며, 최댓값은 1/2이다. [6] :J(A, B) = \frac = \frac.
2. 1. 자카드 거리
'''자카드 거리'''는 표본 집합 간의 ''비''유사성을 측정하며, 자카드 지수와 상호 보완적이다. 자카드 거리는 자카드 지수를 1에서 빼거나, 두 집합의 합집합과 교집합의 크기 차이를 합집합의 크기로 나누어 얻는다. [7] [8] [9] : d_J(A, B) = 1 - J(A, B) = \frac. 자카드 거리의 다른 해석은 대칭 차이 A \mathbin\triangle B = (A \cup B) - (A \cap B) 의 크기를 합집합으로 나눈 비율이다. 자카드 거리는 ''n''개의 표본 집합의 클러스터링 및 다차원 척도법을 위한 ''n'' × ''n'' 행렬을 계산하는 데 일반적으로 사용된다. 이 거리는 모든 유한 집합 모음에 대한 메트릭 이다. 측도를 포함한 확률 측도에 대한 자카드 거리 버전도 있다. \mu 가 가측 공간 X 에 대한 측도이면, 자카드 지수는 다음과 같이 정의한다. : J_\mu(A, B) = \frac{\mu(A \cap B)}{\mu(A \cup B)}, 그리고 자카드 거리는 다음과 같다. : d_\mu(A, B) = 1 - J_\mu(A,B) = \frac{\mu(A \mathbin\triangle B)}{\mu(A \cup B)}. \mu(A \cup B) = 0 또는 \infty 인 경우, 이러한 공식이 정의되지 않으므로 주의해야 한다. MinHash 최소 현명 독립 순열 지역 민감 해싱 스키마를 사용하여, 각 집합이 해시 함수 의 최소값에서 파생된 상수 크기 시그니처로 표현되는 집합 쌍의 자카드 유사성 지수의 정확한 추정치를 효율적으로 계산할 수 있다.
3. 이진 속성
두 객체 ''A''와 ''B''가 각각 ''n''개의 이진 속성을 가질 때, 자카드 지수는 ''A''와 ''B''가 속성을 공유하는 정도를 측정하는 데 유용한 척도이다. ''A''와 ''B''의 각 속성은 0 또는 1의 값을 가질 수 있다. ''A''와 ''B'' 모두에 대한 각 속성 조합의 총 개수는 다음과 같이 나타낼 수 있다.
M_{11} : ''A''와 ''B''가 모두 1의 값을 갖는 속성의 총 개수M_{01} : ''A''의 속성이 0이고 ''B''의 속성이 1인 속성의 총 개수M_{10} : ''A''의 속성이 1이고 ''B''의 속성이 0인 속성의 총 개수M_{00} : ''A''와 ''B''가 모두 0의 값을 갖는 속성의 총 개수0 1 0 M_{00} M_{10} 1 M_{01} M_{11}
각 속성은 이 네 가지 범주 중 하나에 속해야 하며, 이는 다음을 의미한다. :M_{11} + M_{01} + M_{10} + M_{00} = n. 자카드 유사성 지수 ''J''는 다음과 같이 주어진다. :J = {M_{11} \over M_{01} + M_{10} + M_{11}}. 자카드 거리 ''d''''J'' 는 다음과 같이 주어진다. :d_J = {M_{01} + M_{10} \over M_{01} + M_{10} + M_{11}} = 1 - J. 자카드 유사성 지수와 그에 따른 관련 메트릭을 기반으로 통계적 추론을 할 수 있다. [5] ''n''개의 속성을 가진 두 개의 표본 집합 ''A''와 ''B''가 주어지면, 겹침이 통계적으로 유의 한지 확인하기 위한 통계적 검정을 수행할 수 있다. 정확한 해는 구할 수 있지만, ''n''이 증가함에 따라 계산 비용이 많이 들 수 있다. [5] 다항 분포 를 근사하거나 부트스트래핑을 통해 추정 방법을 사용할 수 있다. [5]
3. 1. 단순 일치 계수(SMC)와의 비교
자카드 지수는 단순 일치 계수(SMC)와 매우 유사하지만, 중요한 차이점이 있다. 단순 일치 계수(SMC)는 두 집합이 모두 속성을 가지지 않는 경우(M00 )도 유사도에 포함하지만, 자카드 지수는 두 집합 중 적어도 하나가 속성을 가진 경우(M11 , M01 , M10 )만을 고려한다. 다음은 슈퍼마켓에서 두 고객의 장바구니를 비교하는 예시이다.슈퍼마켓 장바구니 비교 예시 고객 상품 목록 자카드 지수 SMC 고객 1 소금, 후추 1/3 0.998 고객 2 소금, 설탕
위 표에서 두 고객 모두 소금을 구매했으므로 M11 = 1이다. 고객 1은 후추를 구매했지만 고객 2는 구매하지 않았으므로 M10 = 1, 고객 2는 설탕을 구매했지만 고객 1은 구매하지 않았으므로 M01 = 1이다. 나머지 997개 상품은 두 고객 모두 구매하지 않았으므로 M00 = 997이다. 이 경우 자카드 지수는 1 / (1 + 1 + 1) = 1/3 이지만, SMC는 (1 + 997) / (1 + 1 + 1 + 997) = 0.998이다. SMC는 두 고객이 구매하지 않은 상품의 개수(M00 )가 매우 크기 때문에 유사도가 매우 높게 나타난다. 하지만, 실제로 두 고객의 장바구니는 겹치는 상품이 적으므로 자카드 지수가 더 적절한 유사도 척도라고 할 수 있다. 따라서, 시장 바구니 분석과 같이 두 집합이 전체 항목 중 일부만 포함하는 경우에는 자카드 지수가 더 유용하다. 반면, 0과 1이 동등한 정보를 가지는 대칭적인 경우에는 SMC가 더 적합하다. 예를 들어, 성별과 같이 두 가지 값(0 또는 1)으로 표현되는 더미 변수를 비교할 때는 SMC가 더 나은 결과를 제공한다.
4. 가중 자카드 지수 및 거리
'''자카드 거리'''는 표본 집합 간의 ''비''유사성을 측정하며, 자카드 지수와 상호 보완적이다. 자카드 거리는 자카드 지수를 1에서 빼거나, 두 집합의 합집합과 교집합의 크기 차이를 합집합의 크기로 나누어 얻는다. [7] [8] [9] :d_J(A, B) = 1 - J(A, B) = \frac
. 자카드 거리의 다른 해석은 대칭 차이 A \mathbin\triangle B = (A \cup B) - (A \cap B) 의 크기를 합집합으로 나눈 비율이다. 자카드 거리는 ''n''개의 표본 집합의 클러스터링 및 다차원 척도법을 위한 행렬을 계산하는 데 일반적으로 사용된다. 측도를 포함한 확률 측도에 대한 자카드 거리 버전도 있다. \mu 가 가측 공간 X 에 대한 측도이면, 자카드 지수는 다음과 같이 정의된다. :J_\mu(A, B) = \frac{\mu(A \cap B)}{\mu(A \cup B)}, 그리고 자카드 거리는 다음과 같다. :d_\mu(A, B) = 1 - J_\mu(A,B) = \frac{\mu(A \mathbin\triangle B)}{\mu(A \cup B)}. 만약 \mathbf{x} = (x_1, x_2, \ldots, x_n) 와 \mathbf{y} = (y_1, y_2, \ldots, y_n) 가 모든 실수 x_i, y_i \geq 0 을 갖는 두 벡터라면, 이들의 자카드 유사성 지수(Ruzicka 유사성이라고도 알려져 있음)는 다음과 같이 정의된다. :J_\mathcal{W}(\mathbf{x}, \mathbf{y}) = \frac{\sum_i \min(x_i, y_i)}{\sum_i \max(x_i, y_i)}, 그리고 자카드 거리(Soergel 거리라고도 알려져 있음)는 다음과 같다. :d_{J\mathcal{W}}(\mathbf{x}, \mathbf{y}) = 1 - J_\mathcal{W}(\mathbf{x}, \mathbf{y}). 더욱 일반화하여, 만약 f 와 g 가 측정 가능한 공간 X 에서 측도 \mu 를 갖는 두 개의 음이 아닌 측정 가능한 함수라면, 다음과 같이 정의할 수 있다. :J_\mathcal{W}(f, g) = \frac{\int\min(f, g) d\mu}{\int \max(f, g) d\mu}, 여기서 \max 와 \min 은 점별 연산자이다. 그러면 자카드 거리는 다음과 같다. :d_{J\mathcal{W}}(f, g) = 1 - J_\mathcal{W}(f, g).
5. 확률 자카드 지수 및 거리
자카드 거리는 표본 집합 간의 ''비''유사성을 측정하며, 자카드 지수를 1에서 빼거나, 두 집합의 합집합과 교집합의 크기 차이를 합집합의 크기로 나누어 얻는다. [7] [8] [9] : d_J(A, B) = 1 - J(A, B) = \frac
. 자카드 거리의 다른 해석은 대칭 차이 A \mathbin\triangle B = (A \cup B) - (A \cap B) 의 크기를 합집합으로 나눈 비율이다. 측도를 포함한 확률 측도에 대한 자카드 거리 버전도 있다. \mu 가 가측 공간 X 에 대한 측도이면, 자카드 지수는 다음과 같이 정의한다. : J_\mu(A, B) = \frac{\mu(A \cap B)}{\mu(A \cup B)}, 그리고 자카드 거리는 다음과 같다. : d_\mu(A, B) = 1 - J_\mu(A,B) = \frac{\mu(A \mathbin\triangle B)}{\mu(A \cup B)}. \mu(A \cup B) = 0 또는 \infty 인 경우, 이러한 공식이 정의되지 않으므로 주의해야 한다. 확률 분포와 해당 지원 집합 사이에서 연속적인 일반화는 다음과 같다. :J_\mathcal{P}(x,y) = \sum_{x_i\neq 0, y_i \neq 0} \frac{1}{\sum_{j} \max\left(\frac{x_j}{x_i}, \frac{y_j}{y_i}\right)} 이는 "확률" 자카드라고 불린다. [10] 이는 확률 벡터에 대한 가중 자카드에 대해 다음과 같은 경계를 갖는다. :J_\mathcal{W}(x,y) \leq J_\mathcal{P}(x,y) \leq \frac{2J_\mathcal{W}(x,y)}{1+J_\mathcal{W}(x,y)} 여기서 상한은 (가중) 쇠렌센-다이스 계수이다. 해당 거리인 1 - J_\mathcal{P}(x,y) 는 확률 분포에 대한 메트릭이며, 음수가 아닌 벡터에 대한 의사 메트릭이다. 확률 자카드 지수는 단순체의 교차 면적으로 기하학적으로 해석될 수 있다.확률 자카드 지수는 단순체의 교차로 해석될 수 있다. 단위 k -단순체의 모든 점은 k+1 개의 요소에 대한 확률 분포에 해당하는데, 그 이유는 단위 k -단순체가 합이 1이 되는 k+1 차원의 점 집합이기 때문이다. 확률 자카드 지수를 기하학적으로 유도하려면 각 항목의 질량에 따라 단위 단순체를 하위 단순체로 나눈 확률 분포를 나타낸다. 이와 같은 방식으로 표현된 두 개의 분포를 서로 겹쳐놓고 각 항목에 해당하는 단순체를 교차시키면 남은 면적이 분포의 확률 자카드 지수와 같다. 서로 최대한 많이 충돌하는 확률 변수를 구성하는 문제를 생각해 보자. 즉, X\sim x 및 Y\sim y 인 경우, X 와 Y 를 구성하여 \Pr[X=Y] 를 최대화하려고 한다. 두 개의 분포 x,y 만 따로 살펴보면, 얻을 수 있는 가장 높은 \Pr[X=Y] 는 1 - \text{TV}(x,y) 로 주어지며 여기서 \text{TV} 는 총 변동 거리이다. 그러나 특정 쌍의 최대화에만 관심이 있는 것이 아니라, 임의의 쌍의 충돌 확률을 최대화하려는 경우를 생각해 보자. 각 분포 x 에 대해 하나씩, 무한한 수의 확률 변수를 구성하고 모든 쌍 x,y 에 대해 \Pr[X=Y] 를 최대화하려고 할 수 있다. 아래에 설명된 강력한 의미에서, 확률 자카드 지수는 이러한 확률 변수를 정렬하는 최적의 방법이다. 임의의 샘플링 방법 G 및 이산 분포 x,y 에 대해, \Pr[G(x) = G(y)] > J_\mathcal{P}(x,y) 인 경우, J_\mathcal{P}(x,z)>J_\mathcal{P}(x,y) 이고 J_\mathcal{P}(y,z)>J_\mathcal{P}(x,y) 인 일부 z 에 대해 \Pr[G(x) = G(z)] < J_\mathcal{P}(x,z) 또는 \Pr[G(y) = G(z)] < J_\mathcal{P}(y,z) 이다. [10] 즉, 어떤 샘플링 방법도 다른 쌍에서 J_\mathcal{P} 보다 충돌 횟수가 적어지면 한 쌍에서 J_\mathcal{P} 보다 더 많은 충돌을 달성할 수 없으며, 여기서 감소된 쌍은 J_\mathcal{P} 에 따라 증가된 쌍보다 더 유사하다. 이 정리는 집합의 자카드 지수(균일 분포로 해석되는 경우)와 확률 자카드에 대해 참이지만 가중 자카드에는 적용되지 않는다. (이 정리는 모든 분포에 대한 공동 분포를 설명하기 위해 "샘플링 방법"이라는 단어를 사용하는데, 이는 이를 충돌 확률로 달성하는 가중 민해싱 알고리즘의 사용에서 파생되기 때문이다.) 이 정리는 심플렉스 표현을 사용하여 세 요소 분포에 대한 시각적 증명이 있다.세 요소 분포에 대한 확률 자카드 지수의 최적성에 대한 시각적 증명
6. 타니모토 유사도 및 거리
문헌과 인터넷에는 다양한 형태의 함수가 Tanimoto 유사도 및 Tanimoto 거리로 설명되어 있다. 이들 대부분은 자카드 유사도 와 자카드 거리의 동의어이지만, 일부는 수학적으로 다르다. 많은 자료 [11] 는 IBM 기술 보고서 [12] 를 핵심 참고 문헌으로 인용한다. 1960년 10월에 출판된 "식물 분류를 위한 컴퓨터 프로그램" [13] 에서 유사도 비율을 기반으로 한 분류 방법과 파생된 거리 함수가 제시되었다. 이것이 "Tanimoto 유사도"와 "Tanimoto 거리"라는 용어의 의미에 대한 가장 권위 있는 출처로 보인다. 유사도 비율은 자카드 유사도와 동일하지만, 거리 함수는 자카드 거리와 ''같지 않다''. 해당 논문에서는 고정 크기 배열의 각 비트가 모델링되는 식물의 특성 존재 여부를 나타내는 비트맵에 대해 "유사성 비율"이 제시되어 있다. 이 비율의 정의는 공통 비트 수를 두 샘플 중 하나라도 설정된 (''즉'' 0이 아닌) 비트 수로 나눈 값이다. 수학적 용어로 표현하면, 샘플 ''X''와 ''Y''가 비트맵이고, X_i 가 ''X''의 ''i''번째 비트이며, \land , \lor 가 각각 비트 단위 and , or 연산자이면, 유사성 비율 T_s 는 다음과 같다. : T_s(X,Y) = \frac{\sum_i ( X_i \land Y_i)}{\sum_i ( X_i \lor Y_i)} 각 샘플이 대신 속성 집합으로 모델링되면, 이 값은 두 집합의 자카드 지수와 같다. 자카드는 이 논문에 인용되지 않았으며, 저자들이 이를 인지하지 못했을 가능성이 높다. 타니모토는 이 비율을 기반으로 하여, 0이 아닌 유사성을 가진 비트맵에 대해 정의된 "거리"를 정의한다. :T_d(X,Y) = -\log_2 ( T_s(X,Y) ) 이 계수는 의도적으로 거리 메트릭이 아니다. 이는 서로 매우 다른 두 표본이 모두 세 번째 표본과 유사할 가능성을 허용하기 위해 선택되었다. 삼각 부등식의 속성을 부정하는 예시를 쉽게 구성할 수 있다.
7. 응용
자카드 거리는 종종 자카드 거리 1-T_s 와 동의어로 오해되어 언급된다. 이 함수는 올바른 거리 메트릭이다. "타니모토 거리"는 종종 올바른 거리 메트릭이라고 언급되는데, 아마도 자카드 거리와의 혼동 때문일 것이다. 자카드 또는 타니모토 유사성이 비트 벡터로 표현되는 경우 다음과 같이 쓸 수 있다. :f(A,B) =\frac{ A \cdot B}{\|A\|^2 +\|B\|^2 - A \cdot B} 여기서 동일한 계산은 벡터 스칼라 곱과 크기로 표현된다. 이 표현은 비트 벡터(각 차원의 값이 0 또는 1임)에 대해 다음과 같은 사실에 의존한다. :A \cdot B = \sum_i A_iB_i = \sum_i ( A_i \land B_i) 그리고 :\|A\|^2 = \sum_i A_i^2 = \sum_i A_i. 이것은 잠재적으로 혼란스러운 표현인데, 벡터로 표현된 함수가 더 일반적이기 때문이다(도메인이 명시적으로 제한되지 않는 한). T_s 의 속성이 f 로 반드시 확장되는 것은 아니다. 특히, 차이 함수 1-f 는 삼각 부등식 을 유지하지 않으므로 올바른 거리 메트릭이 아니지만, 1 - T_s 는 그렇지 않다. 이 공식을 사용하여 "타니모토 거리"를 정의하고, "타니모토 거리는 올바른 거리 메트릭이다"라는 문구를 결합하면, 함수 1-f 가 실제로 벡터 또는 일반적인 멀티셋에 대한 거리 메트릭이라는 잘못된 결론으로 이어질 위험이 있다. 반면, 유사성 검색 또는 클러스터링 알고리즘에서 사용하면 올바른 결과를 생성하지 못할 수 있다. Lipkus [8] 는 f 와 동일한 타니모토 유사성 정의를 사용하며, 타니모토 거리를 함수 1-f 로 언급한다. 그러나 논문 내에서 문맥은 임의의 벡터 ''A''에 대해 A_i \in \{0,W_i\}. 가 되도록 하는 (양의) 가중치 벡터 W 의 사용으로 제한된다는 점이 명확히 밝혀져 있다. 이러한 상황에서 함수는 올바른 거리 메트릭이므로, 이러한 가중치 벡터에 의해 관리되는 벡터 집합은 이 함수 아래에서 메트릭 공간을 형성한다. 이진 분류에 사용되는 오차 행렬에서 자카드 지수는 다음 공식으로 나타낼 수 있다. :\text{자카드 지수} = \frac{TP}{TP + FP + FN} 여기서 TP는 참 양성, FP는 거짓 양성, FN은 거짓 음성이다. [14]
참조
[1]
논문
The Finley Affair: A Signal Event in the History of Forecast Verification
[2]
웹사이트
Forecast Verification Glossary
https://www.swpc.noa[...]
2023-05-21
[3]
논문
Étude comparative de la distribution florale dans une portion des Alpes et des Jura
https://www.e-period[...]
[4]
논문
The Distribution of the Flora in the Alpine Zone.1
1912-02
[5]
논문
Jaccard/Tanimoto similarity test and estimation methods for biological presence-absence data
2019-12
[6]
서적
Mining of Massive Datasets
Cambridge
[7]
논문
A note on the triangle inequality for the Jaccard distance
2019-04
[8]
논문
A proof of the triangle inequality for the Tanimoto distance
[9]
논문
Distance between sets
[10]
서적
2018 IEEE International Conference on Data Mining (ICDM)
[11]
서적
Intelligent Surveillance Systems
Springer
[12]
논문
An Elementary Mathematical theory of Classification and Prediction
1958-11-17
[13]
논문
A Computer Program for Classifying Plants
1960-10
[14]
논문
Metrics for evaluating 3D medical image segmentation: analysis, selection, and tool
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com