Índice Jaccard

O índice de Jaccard, também conhecido como coeficiente de similaridade de Jaccard, é uma estatística usada para mensurar a similaridade e a diversidade de conjuntos de amostras . Foi desenvolvido por Grove Karl Gilbert em 1884 como sua razão de verificação (v) e agora é frequentemente mencionado como Índice de Sucesso Crítico em meteorologia. Mais tarde, foi desenvolvido de forma independente por Paul Jaccard, originalmente dando o nome francês "coefficient de communauté", e formulado de forma independente novamente por T. Tanimoto. Assim, o índice Tanimoto ou coeficiente Tanimoto também são usados em alguns campos. No entanto, eles são idênticos em geral, considerando a proporção de Interseção sobre União. O coeficiente de Jaccard mensura a similaridade entre conjuntos de amostras finitos, e é definido como o tamanho da interseção dividido pelo tamanho da união dos conjuntos de amostras:

$J(A,B)={{|A\cap B|} \over {|A\cup B|}}={{|A\cap B|} \over {|A|+|B|-|A\cap B|}}.$

Observe que, de forma inerente, $0\leq J(A,B)\leq 1.$ Se A interseção B é vazia, então J(A,B) = 0. O coeficiente de Jaccard é amplamente utilizado em ciência da computação, ecologia, genômica e outras ciências, onde dados binários ou binarizados são usados. Tanto a solução exata quanto métodos de aproximação estão disponíveis para testar hipóteses com o coeficiente de Jaccard.

A similaridade de Jaccard também se aplica a "bags", ou seja, Multiconjuntos . Isso tem uma fórmula semelhante, mas os símbolos significam interseção de multiconjuntos e soma de multiconjuntos (não união). O valor máximo é 1/2.

$J(A,B)={{|A\cap B|} \over {|A\uplus B|}}={{|A\cap B|} \over {|A|+|B|}}.$

A distância Jaccard, que mensura diferença entre conjuntos de amostras, é complementar ao coeficiente de Jaccard e é obtido pela subtração do coeficiente de 1, ou, igualmente, pela divisão da diferença entre os tamanhos da união e interseção de dois conjuntos pelo tamanho da união:

$d_{J}(A,B)=1-J(A,B)={{|A\cup B|-|A\cap B|} \over |A\cup B|}.$

Uma interpretação alternativa da distância de Jaccard é a razão entre o tamanho da diferença simétrica $A\triangle B=(A\cup B)-(A\cap B)$ e a união. A distância de Jaccard é comumente usada para calcular uma matriz n × n para agrupamento e escalonamento multidimensional de n conjuntos de amostras.

Esta distância é uma métrica na coleção de todos os conjuntos finitos.

Há também uma versão da distância Jaccard para medidas, incluindo medidas de probabilidade . Se $\mu$ é uma medida em um espaço mensurável $X$, então definimos o coeficiente de Jaccard por:

$J_{\mu }(A,B)={{\mu (A\cap B)} \over {\mu (A\cup B)}},$

e a distância de Jaccard por:

$d_{\mu }(A,B)=1-J_{\mu }(A,B)={{\mu (A\triangle B)} \over {\mu (A\cup B)}}.$

Deve-se ter cuidado se $\mu (A\cup B)=0$ ou $\infty$, pois essas fórmulas não estão bem definidas nesses casos.

Similaridade de atributos binários assimétricos

Dados dois objetos, A e B, com n atributos binários cada um, o coeficiente Jaccard é uma medida útil da sobreposição que A e B compartilham através de seus atributos. Cada atributo de A e B podem ser 0 ou 1. O número total de cada combinação de atributos, de ambos A e B, são dados pelo seguinte:

$M_{11}$ representa o número total de atributos em que A e B têm o valor 1.

$M_{01}$ representa o número total de atributos onde o atributo de A é 0 e o atributo de B é 1.

$M_{10}$ representa o número total de atributos onde o atributo de A é 1 e o atributo de B é 0.

$M_{00}$ representa o número total de atributos onde A e B têm um valor de 0.

Cada atributo deve se encaixar em uma dessas quatro categorias, ou seja:

$M_{11}+M_{01}+M_{10}+M_{00}=n.$

Então, coeficiente de similaridade Jaccard, J, é dado por:

$J={M_{11} \over M_{01}+M_{10}+M_{11}}.$

E a distância Jaccard, d_J, e dado por:

$d_{J}={M_{01}+M_{10} \over M_{01}+M_{10}+M_{11}}=1-J.$

Análises estatísticas podem ser feitas baseando-se nos coeficientes de similaridade Jaccard, e consequentemente métricas relacionadas. Dados dois conjuntos de amostras A e B com n atributos, um teste estatístico pode ser conduzido para avaliar se uma sobreposição tem significância estatística. A solução exata é possível, porém os custos computacionais podem aumentar quanto maior o valor de n.Métodos estimativos são possíveis por distribuição multinomial ou por bootstrapping.

Diferença do coeficiente de correlação simples (SMC)

Quando usado para atributos binários, o índice Jaccard é muito similar ao coeficiente de correlação simples. A diferença principal é que o SMC tem o termo $M_{00}$ no numerador e no denominador, enquanto o índice Jaccar não o tem. Portanto, o SMC leva em conta tanto presenças mútuas (quando um atributo está presente em ambos conjuntos) e ausências mútuas (quando um atributo está ausente em ambos conjuntos) enquanto combina e compara com o número total de atributos no universo, enquanto o índice Jaccard considera apenas presenças mútuas enquanto combina e compara com o número de atributos que foram escolhidos por ao menos um de dois conjuntos.

Na análise da cesta de mercado, por exemplo, a cesta de dois clientes que desejamos comparar pode conter apenas uma pequena fração de todos os produtos disponíveis na loja, então o SMC normalmente vai informar um valor muito alto de similaridades, mesmo que as cestas carreguem pouquíssima semelhança, tornando assim o índice Jaccard mais apropriado para mensurar similaridade neste contexto. Por exemplo, considere um supermercado que 1000 produtos e dois clientes. A cesta do primeiro cliente contém sal e pimenta e a cesta do segundo contém sal e açúcar. Neste cenário, a similaridade entre as duas cestas medida pelo índice Jaccard seria de 1/3, mas seria 0.998 usando o SMC.

Em outros contextos, onde 0 e 1 carregam informações equivalentes (simetria), o SMC é uma medição de similaridade melhor. Por exemplo, vetores de variações demográficas armazenadas em variáveis fictícias (ou variáveis dummy), como gênero, seriam melhor comparados com o SMC que com o índice Jaccard já que o impacto do gênero na similaridade deve ser igual, independentemente se "macho" é definido como 0 e "fêmea" como 1 ou o oposto. Entretanto, quando temos variáveis fictícias simétricas, pode-se replicar o comportamento do SMC separando as variáveis em dois atributos binários (neste caso, macho e fêmea), e assim transformando-os em atributos assimétricos, permitindo o uso do índice Jaccard sem introduzir viéses. Ainda assim, o SMC permanece mais eficiente do ponto de vista computacional em casos de variáveis fictícias simétricas, já que não requer dimensões extras.

Similaridade e distância Jaccard ponderadas

Se $\mathbf {x} =(x_{1},x_{2},\ldots ,x_{n})$ e $\mathbf {y} =(y_{1},y_{2},\ldots ,y_{n})$ são dois vetores com $x_{i},y_{i}\geq 0$ reais, então o coeficiente de similaridade Jaccard deles (também conhecido como similaridade de Ruzicka) é definido por:

$J_{\mathcal {W}}(\mathbf {x} ,\mathbf {y} )={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}},$

E a distância Jaccard (também conhedida como distância Soergel) por:

$d_{J{\mathcal {W}}}(\mathbf {x} ,\mathbf {y} )=1-J_{\mathcal {W}}(\mathbf {x} ,\mathbf {y} ).$

Com ainda mais generalidades, se $f$ e $g$ são duas funções mensuráveis não-negativas em um espaço mensurável $X$ com medida $\mu$, então podemos definir:

$J_{\mathcal {W}}(f,g)={\frac {\int \min(f,g)d\mu }{\int \max(f,g)d\mu }},$

Onde $\max$ and $\min$ são operadores pontuais. Então a distância Jaccard é:

$d_{J{\mathcal {W}}}(f,g)=1-J_{\mathcal {W}}(f,g).$

Então, por exemplo, para dois conjuntos mensuráveis $A,B\subseteq X$, temos que $J_{\mu }(A,B)=J(\chi _{A},\chi _{B}),$ onde $\chi _{A}$ e $\chi _{B}$ são funções características do conjunto correspondente.

Distância e similaridade Jaccard de probabilidades

A similaridade ponderada Jaccard descrita anteriormente generaliza o índice Jaccard para vetores positivos, onde um conjunto corresponde a um vetor bináriodado pela função indicadora,ou seja $x_{i}\in \{0,1\}$. Contudo, ela não generaliza o índice Jaccard para distribuições de probabilidades, onde um conjunto corresponde a uma distribuição de probabilidades uniforme, ou seja:

$x_{i}={\begin{cases}{\frac {1}{|X|}}&i\in X\\0&{\text{senão}}\end{cases}}$

É sempre menor se os conjuntos diferem em tamanho. Se $|X|>|Y|$, e $x_{i}=\mathbf {1} _{X}(i)/|X|,y_{i}=\mathbf {1} _{Y}(i)/|Y|$ então:

$J_{\mathcal {W}}(x,y)={\frac {|X\cap Y|}{|X\setminus Y|+|X|}}<J(X,Y).$

O índice Jaccard de probabilidades pode ser interpretado como interseções de simplices.

Em vez disso, uma generalização que é contínua entre distribuições de probabilidades e seus conjuntos de suporte correspondentes é:

$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)}}$

É chamada de "Probabilidade" Jaccard. Tem os vínculos a seguir com o Jaccard Ponderado em vetores de probabilidade.

$J_{\mathcal {W}}(x,y)\leq J_{\mathcal {P}}(x,y)\leq {\frac {2J_{\mathcal {W}}(x,y)}{1+J_{\mathcal {W}}(x,y)}}$

Aqui o vínculo superior é o coeficiente Sørensen–Dice (ponderado). A distância correspondente, $1-J_{\mathcal {P}}(x,y)$, é uma métrica sobre distribuições de probabilidade, e uma pseudométrica sobre vetores não-negativos.

O Índice de Probabilidade Jaccard tem uma interpretação geométrica como a área de uma interseção de simplices. Todo ponto em uma unidade $k$-simplex corresponde a uma distribuição de probabilidade em $k+1$ elementos, porque a unidade $k$-simplex é um conjunto de pontos em $k+1$ dimensões que a soma resulta em 1. Para derivar o Índice de Probabilidade Jaccard geometricamente, represente a distribuição de probabilidade como uma unidade simplex dividida em subsimplices, de acordo com a massa de cada item. Se você sobrepor duas distribuições representadas desta maneira, e cruzar as simplices correspondentes de cada item, a área que permaneçe é igual ao Índice de Probabilidade Jaccard das distribuições.

Otimização do Índice de Probabilidade Jaccard

Uma prova visual da otimização do Índice de Probabilidade Jaccard em 3 distribuições de elementos

Considere o problema de construir variáves aleatórias tais que estas colidam entre si o máximo possível. Isto é, se $X\sim x$ e $Y\sim y$, gostaríamos de construir $X$ e $Y$ para maximizar $\Pr[X=Y]$. Se olharmospara apenas duas distribuições $x,y$ isoladas, o maior $\Pr[X=Y]$ que obtemos é dado por $1-{\text{TV}}(x,y)$ onde ${\text{TV}}$ é a distância da Variação Total. Entretando, suponha que não estamos apenas almejando maximizar este par em particular, mas maximizar a probabilidade de colisão de qualquer par arbitrário. É possível construir um número infinito de variáveis aleatórias, uma para cada distribuição $x$, e buscar a maximização de $\Pr[X=Y]$ para todos os pares $x,y$. Pode-se assumir que a Índice de Probabilidade Jaccard é uma forma otimizada de alinhar estas variáveis aleatórias, como descrito abaixo:

Para qualquer método de amostragem $G$ e distribuições discretas $x,y$, se $\Pr[G(x)=G(y)]>J_{\mathcal {P}}(x,y)$ então para uns $z$ onde $J_{\mathcal {P}}(x,z)>J_{\mathcal {P}}(x,y)$ e $J_{\mathcal {P}}(y,z)>J_{\mathcal {P}}(x,y)$, ou $\Pr[G(x)=G(z)]<J_{\mathcal {P}}(x,z)$ ou $\Pr[G(y)=G(z)]<J_{\mathcal {P}}(y,z)$.

Isto é, nenhum método de amostragem pode retornar mais colisões que $J_{\mathcal {P}}$ em um par sem retornar menos colisões que $J_{\mathcal {P}}$ em outro par, onde o par reduzido é mais similar sob $J_{\mathcal {P}}$ que o par aumentado. Este teorema é válido para o Índice Jaccard de conjuntos (se interpretado como distribuições uniformes) e a probabilidade Jaccard, mas não para o Jaccard ponderado. (Este teorema usa o termo "método de amostragem" para descrever uma distribuição conjunta sobre todas distribuições em um espaço, pois deriva do uso de algoritmos ponderados minhashing que retornam isto como suas probabilidades de colisão.)

Este teorema tem uma prova visual em três distribuições de elementos usando a representação simplex.

Similaridade e distância Tanimoto

Várias formas de função descritas como similaridade Tanimoto e distância Tanimoto ocorrem na literatura e Internet. A maioria destas são sinônimos da similaridade Jaccard e distância Jaccard, mas têm diferenças matemáticas. Várias fontes citam um Relatório Técnico IBM como referência seminal. O relatório está disponível em várias bibliotecas.

Em "A Computer Program for Classifying Plants" ("Um programa computacional para classificar plantas", em português), publicado em Outubro de 1960, um método de classificação baseado na razão de similaridade, e um função de distância derivada, são apresentados. Aparentemente, esta é a principal fonte para o significado dos termos "similaridade Tanimoto" e "distância Tanimoto". A razão de similaridade é equivalente à similaridade Jaccard, mas a função de distância não é equivalente à distância Jaccard.

As definições de Tanimoto para similaridade e distância

Neste artigo, a "razão de similaridade" é dada na forma de bitmaps, onde cada bit de uma malha de tamanho fixo representa a presença ou ausência de uma característica na planta sendo modelada. A definição da razão é o número de bits em comum, dividido pelo número de conjuntos de bits (isto é, não-zero) em cada amostra.

Apresentando em termos matemáticos, se amostras X e Y são bitmaps, $X_{i}$ é o ith bit de X, e $\land ,\lor$ são operadores lógicos "e, ou" respectivamente, então a razão de similaridade $T_{s}$ é:

$T_{s}(X,Y)={\frac {\sum _{i}(X_{i}\land Y_{i})}{\sum _{i}(X_{i}\lor Y_{i})}}$

Em vez disso, se cada amostra é modelada como um conjunto de atributos, este valor é igual ao coeficiente Jaccard de dois conjuntos. Jaccard não é citado neste artigo, e parece que os autores não estavam cientes desta relação.

Tanimoto continua a definir o "coeficiente de distância" baseado nesta razão, definida por bitmaps como similaridade não-zero:

$T_{d}(X,Y)=-\log _{2}(T_{s}(X,Y))$

Este coeficinte não é, deliberadamente, uma métrica de distância. Foi escolhido permitir a possibilidade de dois espécimes, que são bem diferentes entre si, a serem similares a um terceiro. É fácil construir um exemplo que refuta a propriedade da desigualdade triangular.

Outras definições da distância Tanimoto

A distância Tanimoto é comumente mencionada, erroneamente, como um sinônimo da distância Jaccard $1-T_{s}$. Esta função é uma métrica de distância apropriada. A "distância Tanimoto" é comumente definida como sendo uma métrica de distância apropriada, provavelmente devido à esta confusão com a distância Jaccard.

Se a similaridade Jaccard ou Tanimoto é expressa por um vetor bit, então pode ser escrita como:

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

Onde o mesmo cálculo é expresso em termos de produto e magnitude de vetor escalar. Esta representação baseia-se no fato de que, para um vetor bit (onde o valor de cada dimensão é 0 ou 1):

$A\cdot B=\sum _{i}A_{i}B_{i}=\sum _{i}(A_{i}\land B_{i})$

e

$\|A\|^{2}=\sum _{i}A_{i}^{2}=\sum _{i}A_{i}.$

Está é uma representação potencialmente confusa, pois a função expressa sobre vetores é mais genérica, a não ser que seu domínio seja restrito explicitamente. Propriedade de $T_{s}$ não se estendem necessariamente à $f$. Particularmente, a função diferencial $1-f$ não preserva a desigualdade triangular, portanto não é uma métrica de distância apropriada, enquanto $1-T_{s}$ o é.

Há um risco real de que a combinação da "distância Tanimoto" sendo definida usando esta fórmula, em conjunto com a declaração "a distância Tanimoto é uma métrica de distância apropriada" levará à falsa conclusão de que a função $1-f$ é de fato uma métrica de distância sobre vetores ou multiconjuntos em geral, enquanto seu uso na busca por similaridades ou aglutinação de algoritmos pode falhar na produção de resultados corretos.

Lipkus usa a definição da similaridade de Tanimoto que é equivalente à $f$, e refere-se a distância Tanimoto como a função $1-f$..Porém, é esclarecido no artigo que o contexto é restrito pelo uso de um vetor ponderado (positivo) $W$ tal que, para qualquer vetor A sendo considerado, $A_{i}\in \{0,W_{i}\}.$ Sob estas circunstâncias, a função é uma métrica de distância apropriada, e então um conjunto de vetores governado por tal vetor ponderado forma um espaço métrico sob esta função.

Índice Jaccard em matrizes de confusão de classificação binária

Em matrizes de confusão usadas para classificação binária, o índice Jaccard pode ser arranjado na seguinte fórmula:

${\text{Jaccard index}}={\frac {TP}{TP+FP+FN}}$

Onde TP são os positivos reais, FP os falsos positivos e FN os falsos negativos.

Veja também

• Distância Hamming
• Correlação
• Informação mútua, uma variante normalizada na qual é uma distância Jaccard entrópica.

Ligações externas

• Introduction to Data Mining lecture notes from Tan, Steinbach, Kumar
• SimMetrics a sourceforge implementation of Jaccard index and many other similarity metrics
• A web-based calculator for finding the Jaccard Coefficient
• Tutorial on how to calculate different similarities
• Intersection over Union (IoU) for object detection
• Kaggle Dstl Satellite Imagery Feature Detection - Evaluation
• Similarity and dissimilarity measures used in data science